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

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

Доказательство.

Пусть каждая элементарная дизъюнкция КНФ, равносильной исходной формуле, содержит некоторую переменную вместе с её отрицанием. Рассмотрим произвольную элементарную дизъюнкцию и пусть в ней содержится некоторая переменная x и её отрицание , тогда, из-за того, что xV =1,эта элементарная конъюнкция будет равна 1. Так для всех элементарных конъюнкций КНФ.

Пусть исходная формула является тождественно истиной. Рассмотрим КНФ ей равносильную и предположим, что в некоторой элементарной дизъюнкции этой КНФ нет пары типа x и . Тогда рассмотрим набор из 0 и 1, такой, что в этом наборе компонента равна 1, если в рассматриваемой элементарной дизъюнкции ей соответствующая переменная входит под знаком отрицания и равна 0, если соответствующая переменная входит без знака отрицания. Тогда на этом наборе элементарная дизъюнкция будет равна 0, тем самым и значение КНФ на этом наборе будет равно 0, что противоречит тожественной истинности исходной формулы.