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

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

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

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

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

 

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

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

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

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

В1 Ù В2 Ù … Вn,

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

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

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

В1 Ú В2 Ú … Вn,

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

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

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

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

 

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

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

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

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

 

Законы	Формулы
КНФ	ДНФ
- удаления знака импликации		p®q = +q
- удаления знака строгой дизъюнкции	p Ú q = (p+q) ( + )	p Ú q = p + q
- удаления знака эквиваленции	p«q = (p+ ) ( +q)	p«q = pq +
- исключения третьего		p+ = И
- противоречия	p = Л
- исключения логических констант	pИ = p	p+Л = p
- исключения логических переменных	pЛ = Л	p+И = И
- идемпотентности	ppр… = p	p+p+р+…= p
- коммутативности	pq = qp	p+q = q+p
- ассоциативности	p(qr) = (pq)r = pqr	p+(q+r) = (p+q)+r = p+q+r
- дистрибутивности	p(q+r) = pq + pr	p+qr = (p+q)(p+r)
- поглощения	p(p+q) = p p( +q) = pq	p+pq = p p+ q = p+q
- де Моргана	pq = +	p+q =