Формула называется формулой с тесными отрицаниями, если в ней нет связок Þ и Û, и отрицания относятся только к пропозициональным переменным

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

Def: Произвольная дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой, а произвольная конъюнкция элементарных дизъюнкций называется конъюнктивной нормальной формой (Д.Н.Ф. и К.н.ф.).

Def: Д.н.ф. называется совершенной (с.д.Н.Ф.), если каждая переменная формулы входит в элементарную конъюнкцию ровно один раз – с отрицанием или без него.

Def: К.н.ф. называется совершенной (с.к.Н.Ф.), если каждая переменная формулы входит в элементарную дизъюнкцию ровно один раз – с отрицанием или без него.

Пример: Исчислить высказывание: ((А Þ В) Þ (Ø (С Ú А) Þ В)).

1 5 3 2 4

Внизу указан порядок операций.

1) Таблицы истинности:

А	В	С

В 5^ом столбце указана истинность всего составного высказывания при различных значениях истинности А, В и С.

2) С помощью формулы: (А Þ В) Û (Ø А Ú В) избавимся от импликаций:

(Ø А Ú В) Þ (С Ú А Ú В)

Ø (Ø А Ú В) Ú С Ú А Ú В и применим один из законов де Моргана.

(А Ù Ø В) Ú С Ú А Ú В - получена формула с «тесными» отрицаниями.

Запишем последнюю формулу в виде:

* (А Ù Ø В) Ú (С)Ú (А)Ú (В), трактуя каждую скобку как элементарную конъюнкцию, видим: дизъюнкцию элементарных конъюнкций, т.е. Д. Н.Ф. она не является совершенной т.к. в каждую скобку входят не все переменные формулы.

Запишем последнюю формулу в виде:

(А Ù Ø В) Ú (С Ú А Ú В) и применим дистрибутивный закон

(А Ú С Ú А Ú В) Ù (Ø В Ú С Ú А Ú В),

(А Ú С Ú В) Ù (Ø В Ú С Ú А Ú В), здесь последняя скобка есть тавтология, поэтому получаем: (А Ú В Ú С) и, трактуя скобку как элементарную дизъюнкцию, делаем заключение, что перед нами К.Н.Ф., причем С.К.Н.Ф. т.к. в элементарную дизъюнкцию входят все три переменные.

Примечание: С.К.Н.Ф. позволяет сказать, что исходная формула ложна только в одном случае, если А, В, С – ложны. Зная С.К.Н.Ф., легко написать и С.Д.Н.Ф если учесть, что отдельные элементарные конъюнкции описывают случаи истинности формы.

((А Ú В Ú С) Û (Ø А Ù В Ù С) Ú (А Ù Ø В Ù С) Ú (А Ù В Ù Ø С) Ú

(Ø А Ù Ø В Ù С) Ú (Ø А Ù В Ù Ø С) Ú (А Ù Ø В ÙØ С) Ú (Ø А Ù Ø В Ù Ø С)).

В записанной формуле слева от Û стоит С.К.Н.Ф. а справа С.Д.Н.Ф.

· Исчислить высказывание можно также, если смоделировать исходное составное высказывание эквивалентной электрической схемой.

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

При этом: конъюнкция А Ù В может быть промоделирована последовательным включением в цепь двух выключателей А и В, а дизъюнкция А Ú В - параллельным.