Нормальная форма формул логики

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

Формула логики имеет нормальную форму, когда:

1) она не содержит знаков ®, «, Ú;

2) знаки отрицания стоят только при переменных.

 

По структуре все формулы логики, имеющие нормальную форму, можно разделить на два типа:

1) формулы с конъюнктивной нормальной формой (КНФ);

2) формулы с дизъюнктивной нормальной формой (ДНФ).

Формула логики высказываний имеет конъюнктивную нормальную форму (КНФ), если она имеет вид

В1 Ù В2 Ù … Вn,

где В1, В2, … Вn – элементарные дизъюнкции,

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

Формула логики высказываний имеет дизъюнктивную нормальную форму (ДНФ), если она имеет вид

В1 Ú В2 Ú … Вn,

где В1, В2, … Вn – элементарные конъюнкции,

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

Любая формула логики высказываний в результате ряда равносильных замен может быть приведена к конъюнктивной или дизъюнктивной нормальной форме.

Любая конъюнктивная нормальная форма путем эквивалентных преобразований может быть приведена к дизъюнктивной нормальной форме и наоборот. В логике высказываний, как и в рассмотренной ранее алгебре классов, действует принцип двойственности. В элементарной алгебре всякое выражение, составленное из букв и чисел с помощью знаков сложения и умножения, раскрытием скобок можно превратить в сумму произведений букв и чисел. Так же и в логике из формулы, не содержащей знаков импликации, эквиваленции и строгой дизъюнкции, легко построить двойственную ей и также справедливую. Для этого необходимо заменить знаки «Ù» на «Ú» и «Ú» на «Ù», константы И на Л и Л на И. Так, если применить принцип двойственности к закону противоречия pÙ =Л (то есть произвести требуемые замены), то получим закон исключения третьего pÚ =И. Аналогично применение принципа двойственности к первому закону де Моргана дает в результате второй закон. Если две формулы равносильны, то и двойственные им формулы тоже равносильны.

 

Во второй половине ХIХ века английский математик Джордж Буль (1815 – 1864) предложил алгебраический вариант логики, который принято называть «булевой алгеброй». По мысли Дж. Буля, операция конъюнкции может рассматриваться как специфическое логическое умножение, а операция дизъюнкции – как логическое сложение. Поэтому можно перейти к более простой символике: заменить знак «Ù» на знак умножения «·», а знак «Ú» на «+».

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

1) законы в конъюнктивной нормальной форме (КНФ);

2) законы в дизъюнктивной нормальной форме (ДНФ).