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

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

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

• 1) она не содержит знаков —<-«, у;
• 2) знаки отрицания стоят только при переменных.

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

• 1) формулы с конъюнктивной нормальной формой;
• 2) формулы с дизъюнктивной нормальной формой.

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

где B_l5 В₂ … B_n— элементарные дизъюнкции, то есть представляет собой конъюнкцию элементарных дизъюнкций.

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

где В_1? В₂ … В_п— элементарные конъюнкции, то есть представляет собой дизъюнкцию элементарных конъюнкций.

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

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

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

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

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

Таблица 10

Окончание табл. 10