Методические указания к изучению курса "Дискретная математика" и решению задач для студентов специальности 200900



страница3/9
Дата01.05.2016
Размер0.61 Mb.
ТипМетодические указания
1   2   3   4   5   6   7   8   9

Логические следствия


Формула В именуется логическим следствием совокупности формул А1, А2 , ..., Аm, если каждый набор логических значений переменных, обращающий в истину все формулы А1, А2 , ..., Аm, обращает в истину и формулу В.

Теорема 1. Формула В является логическим следствием формул А1, А2 , ..., Аm тогда и только тогда, когда формула
А1 & А2 & ...& Аm B
является теоремой ИВ.

Теорема 2. Формула В является логическим следствием формул А1, А2 , ..., Аm тогда и только тогда, когда формула
А1 & А2 & ...& Аm & B
противоречива.

Из теорем 1 и 2 следует, что проверка, является ли формула B логическим следствием совокупности формул {А1, А2 , ..., Аm}, сводится к доказательству общезначимости или противоречивости некоторой ППФ.

Рассмотрим следующий пример.

Пример 2. Предполагается доказать справедливость следующих утверждений

1. Если Джон убийца и пистолет у него, то Смит пистолет обнаружит;

2. Если Смит обнаружит пистолет и передаст его Бобу, то Смит рапорт не напишет;

3. Если босс к делу причастен, то Смит передаст пистолет Бобу и напишет рапорт.

Требуется доказать, что если Джон убийца и пистолет у него, то босс к делу не причастен.

Запишем посылки 1 – 3 в символическом виде:


А&В C; (1)

C&D E; (2)

F D&E. (3)
В принятых обозначениях требуется доказать справедливость следующего заключения:
А&В F. (4)

Покажем, что из истинности всех посылок следует истинность заключения, т.е. что утверждение (4) является логическим следствием утверждений (1) – (3).

Совокупность посылок представляем в виде формулы
(А&В C)&(C&D E)&(F D&E).
Эта формула эквивалентна следующей КНФ:
K1=( А В C) & ( C D E)&( F D) &( F E).
Формулу (4) также представим в виде КНФ:
K2=( А В F).
Согласно теореме 2, формула (4) является логическим следствием формул (1) – (3) тогда и только тогда, когда формула K1& K2 противоречива. Имеем
K1& K2=( А В C) & ( C D E)&( F D) &( F E)&A&B&F=

A&B&F&C&( D E)&D&E.
Противоречивость последней формулы очевидна, ибо три дизъюнкта, ( D E), D и Е, одновременно не могут быть истинными. Таким образом, заключение (4) действительно вытекает из утверждений (1)- (3), является их логическим следствием.

Далее общезначимые формулы будем обозначать символом , а противоречивые – символом . Как очевидно, A A= и A& A=.

Как известно, проблема определения по КНФ, является ли она выполнимой (непротиворечивой), относится к числу NP-полных. В предположении Р NР полиномиальных по временной вычислительной сложности (числу выполняемых элементарных операций) алгоритмов решения этой проблемы не существует. Выполнимость КНФ от n переменных может быть определена путем последовательного тестирования всех наборов логических значений этих переменных (общее число наборов равно 2n).

Практика показала, что достаточно часто эффективным средством определения противоречивости КНФ является принцип резолюции.


  1. Принцип резолюции для логики высказываний


Легко проверяется, что формула
[(А В)&(B C)] (A C) (1)
общезначима, т. е. является теоремой ИВ.

Лемма. Пусть в КНФ K(X1, X2,,Xn) входят дизъюнкты D1 и D2 ,причем D1 представим в виде D1' Xi , а D2 в виде D2' Xi . Тогда логическим следствием входящих в КНФ утверждений (дизъюнктов) является дизъюнкт D1' D2'.

Действительно, дизъюнкт D2' Xi эквивалентен формуле Xi D2'. В формулу (1) вместо A подставим D1', вместо В - Xi и вместо С - D2'. Получаем следующую теорему ИВ:


[(D1' Xi)&( Xi D2')] (D1' D2').
Так как утверждения D1' Xi и Xi D2' входят в состав КНФ в качестве логического следствия образующих КНФ K(X1, X2,,Xn) дизъюнктов, получаем D1' D2'. Лемма доказана.

Формула D1' D2' называется резольвентой формул D1= D1' Xi и D2= D2' Xi . Резольвента D1' D2' - логическое следствие дизъюнктов D1 и D2.

Резольвентой однолитерных дизъюнктов X и X является противоречивая формула (пустой дизъюнкт) .

Идея принципа резолюции заключается в проверке, выводим ли из дизъюнктов, составляющих КНФ K(X1, X2,…,Xn,), пустой дизъюнкт. Вывод конструируется последовательным построением резольвент. Выводимость из КНФ пустого дизъюнкта означает ее противоречивость.



Пример 3. Задана КНФ K(P,Q) = (Р Q) & ( Р Q) & (Р Q) & ( Р Q). Требуется доказать ее противоречивость,

В состав рассматриваемой КНФ входят четыре дизъюнкта:

1) Р Q;

2) Р Q;

3) Р Q;

4) Р Q.

Строим следующие резольвенты (для каждой записываемой резольвенты в скобках указываются номера исходных для нее дизъюнктов):

5)Q (1,2);

6) Q (3,4);

7)  (5,6).

Из составляющих КНФ K(P,Q) дизъюнктов в качестве логического следствия выведен пустой дизъюнкт. Это означает противоречивость данной КНФ.

В дизъюнктах D1' Xi и D2' Xi вхождения переменой Xi именуются контрарными. Так, в дизъюнктах 1) и 2), 3) и 4) контрарны вхождения буквы P; в дизъюнктах 5) и 6) контрарны вхождения буквы Q. Пустой дизъюнкт есть резолюция контрарных литер.



Пример 4. Известно следующее: прямая L1 либо параллельна прямой L2, либо совпадает с ней; параллельные прямые не имеют общих точек; прямые L1 и L2 имеют общую точку. Методом резолюции требуется доказать, что прямые L1 и L2 совпадают.

Исходные предположения на языке ИВ записываются следующим образом:

1) A B;

2) A C;

3) C.

Требуется доказать справедливость утверждения B. Утверждение B является логическим следствием предположений 1),2),3) тогда и только тогда, когда формула


(A B)&(A C)& C & B

невыполнима.

Так как формула A C эквивалентна A C, нам требуется показать противоречивость следующей совокупности дизъюнктов:
1') A B;

2') A C;

3') C;

4') B.


Конструируем резольвенты:
5') A (1', 4');

6') C (5', 2');

7')  (3', 6').
Итак, прямые L1 и L2 действительно совпадают.

Пример 5. Если футбольная команда A выигрывает, то город А' торжествует; если команда В выигрывает, то торжествует город B'. Выигрывает либо команда A, либо команда В. Однако, если команда A выигрывает, то город В' не торжествует; если выигрывает команда В, то город А' не торжествует. Требуется доказать, что город А' торжествует тогда и только тогда, когда не торжествует город В'.

Запишем посылки и заключения на языке ИВ:

1) A А';

2) В В';

3) A B;

4) A В';

5) В А';

6) (А' В')&( В' А').

Отметим, что

[(А' В')&( В' А')]= (А'&В') ( В' А')=

(А' В')& ( А' В').

Таким образом, требуется доказать противоречивость следующей совокупности дизъюнктов:

1) A А'; 2) В В'; 3) A B; 4) A В';

5) В А'; 6) А' В'; 7) В' А'.

Конструируем резольвенты:

8) А' В (1,3);

9) В А' (2,6);

10) А' (8,9);

11 ) A А' (3,5);

12 ) A А' (4,7);

13) А' (11,12);

14)  (10,13).

Решение закончено.



Теорема о полноте принципа резолюций. Если конечная совокупность дизъюнктов противоречива, то данный факт можно доказать, основываясь на принципе резолюции, т. е. путем последовательного конструирования резольвент, вплоть до получения пустого дизъюнкта.

Верхняя оценка временной вычислительной сложности, основанная на принципе резолюции алгоритма проверки противоречивости КНФ, экспоненциальна, что связано с NР полнотой рассматриваемой проблемы.

При реализации данного алгоритма осуществляется поиск вывода пустого дизъюнкта. Некоторые направления поиска могут оказаться тупиковыми, полученные при этом результаты в найденном выводе пустого дизъюнкта не используются.

Так возникает вопрос о построении стратегий поиска, обеспечивающих в случае противоречивости рассматриваемой совокупности утверждений достаточно быстрый вывод пустого дизъюнкта (по оценке "в среднем").





  1. Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7   8   9


База данных защищена авторским правом ©zodorov.ru 2017
обратиться к администрации

    Главная страница