Необходимое и достаточное условия

Тождественной истинности (ложности) формул.

Чтобы выяснить равносильны ли формулы F и G, или, что-то тоже самое, будет ли формула F«Gтождественно истинной, можно составить их таблицы истинности. Однако, при большом числе переменных задача весьма трудоёмка. Следующие теоремы позволяют её упростить.

Теорема. Булева формула тождественно истинна в том и только в том случае, если каждая элементарная дизъюнкция любой равносильной ей КНФ содержит пару переменных x и её отрицание`x (т.е. равна 1).

Теорема. Булева формула тождественно ложна в том и только в том случает, если каждая элементарная конъюнкция любой равносильной ей ДНФ содержит пару: переменная x и её отрицание`x, т.е. `xx, равную 0.

Доказательство этих теорем основано на следующих леммах:

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

Лемма 2. Элементарная дизъюнкция является тождественно ложной тогда и только тогда, когда она содержит пару сомножителей: переменное и его отрицание.

Замечание. Чтобы выяснить, является формула тождественно истинной, не обязательно приводить формулу к КНФ. Например, пусть F=(`xÚy)A, где А - некоторая формула. Если x=1, а у=0, то`хÚу=0 и F=0 и F не может быть тождественно истинной. Аналогично, если F=`хуÚА, то при х=0 и у=1 `ху=1 и F= 1, а значит, F не может быть тождественно ложной.