Материал: 5540

F1 (F2 F3) (F1 F2 ) (F1 F3) .

3. Удалить лишние конъюнкции и повторения переменных в конъюнкциях применяя закон:

F F F ;

F F F ;

F F 0;

FF 1.

4.Удалить константы с помощью правил операций с константами:

F1 F ;

F 1 1 ;

F 0 0 ;

F 0 F .

Пример 3.9. Приведите к ДНФ формулу:

А В А (В А С) (А (В С) В С).

(А В) (А В) (А (В С)) В С (А В) (А В) (А В С) (В С)

( А В) ( А В) ((А В) (В С)) ( А В) ( А В С)

В( А ( А С)) В ( А С) ( А В) (В С).

Элементарной дизъюнкцией называется дизъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.

КНФ формулы есть формула, имеющая вид конъюнкции элементарных дизъюнкций, т.е.

элементарных дизъюнкций содержит пропозициональную переменную и её отрицание F F , то следует удалить всю элементарную дизъюнкцию,

71

так как F F 1.

Процедура приведения ДНФ к КНФ:

1. Примените к F правило снятия двойного отрицания

2. С помощью закона де Моргана освободитесь от второго отрицания и преобразуйте отрицания элементарных конъюнкций в элементарные дизъюнкции.

Пример 3.10. Приведите к КНФ формулу:

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

Задача логики дать принцип рассуждения, то есть теорию вывода. Практически это сводится к получению критериев для решения механическим путём вопроса о том, можно ли некоторую цепь рассуждений, основываясь на её форме, считать правильной.

72

Мы знаем, например, что если истинно А, то, независимо от истинности

последовательность высказываний, проводимых в обоснование утверждения, при этом последнее высказывание в этой последовательности (заключение) может быть выведено из некоторых начальных высказываний (посылок).

Высказывание В (заключение) есть логическое следствие высказываний А1 , А2 ,..., Аm (посылок):

А1, А2 ,..., Аm B ,

если из конъюнкции посылок следует заключение, то есть всегда, когда

виде цепочки (т.е. конечной последовательности) формул, последней из которых является В, и притом такой цепочки, что наличие в ней каждой из формул Е обосновывается применением одного из следующих правил.

Правило р: формула Е есть посылка.

Правило t: формуле Е в цепочке предшествуют такие формулы А, …, С, что |= А ... С Е .

Иными словами, мы утверждаем, что А1 , А2 ,..., Аm B , если мы можем составить такую цепочку формул Е1, Е2 ,..., Еm (= B ), что каждая Е есть посылка (правило р) или же в этой цепочке есть предшествующие формулы такие, что если С – их конъюнкция, то С Е (правило t).

Приведём перечень некоторых тавтологических импликаций. То, что каждая из приведённых формул – тавтология, можно доказать, составив для неё таблицу истинности. Каждая из тавтологических импликаций порождает

73

некоторое правило вывода, а именно частный случай применения правила t, который обосновывается ссылкой только на одну эту тавтологию.

74

Задача 3.17. Постройте формальное доказательство логичности рассуждения.

Если человек занимается спортом, то он хочет быть здоровым. Хорошее здоровье ведёт к счастливой жизни. Кроме того, если человек занимается спортом, то он, как правило, стремится достичь высоких спортивных результатов. Наличие высоких результатов позволяет одержать победы на соревнованиях. Победы на соревнованиях влекут за собой всеобщее признание. Однако человек не хочет жить счастливо и иметь всеобщее признание. Значит, он не станет заниматься и спортом.

С изложенным выше связан, но отличается от него вопрос о непротиворечивости множества высказываний, которое предлагается рассматривать как систему посылок для вывода. Множество

75