Доказательства равенства логических функций

Если требуется сравнить две логические функции f₁ и f₂, то следует преобразовать их или представить в виде

а) Таблиц истинности – ТИ₁ и ТИ₂;

б) СДНФ – СДНФ₁ и СДНФ₂;

в) СКНФ – СКНФ₁ и СКНФ₂;

г) Полиномов Жегалкина.

Сравнение логических функций с помощью таблиц истинности – это стандартный прием, а почему сравнение логических функций удобно проводить в совершенных формах или в форме полинома Жегалкина? Ответ прост: логическая функция может иметь много формул, ее представляющих, но совершенные формы и полином жегалкина у нее единственны.

Замечание: От СДНФ легко можно перейти к СКНФ, (а от СКНФ к СДНФ) – если СДНФ имеет k конъюнкций, то СКНФ будет иметь 2ⁿ – k дизъюнкций, где n – число переменных (если СКНФ имеет k дизъюнкций, то СДНФ будет иметь 2ⁿ – k конъюнкций).

Пример:Доказать, что .

1. Раскрываем скобки в левой части и упрощаем

В результате получили выражение идентичное правой части.

2. Переход к СДНФ удобно производить от ДНФ.

Если установить порядок входных переменных xyz, z – младшая переменная, то единичными наборами (для которых определена СДНФ) являются 7, 6, 5, 3, 1 (определяем по значениям переменных), а нулевыми наборами (для которых надо написать произведение сумм) будут 0, 2, 4, поэтому для СКНФ получаем

Не забывайте: если в СКНФ переменная без отрицания, то в соответствующем входном наборе она имеет значение 0, если с отрицанием, то 1.

3. Переход к СКНФ удобнее производить от КНФ

Как видим, результаты преобразований совпали, следовательно, тождество доказано.

4. По СДНФ или по СКНФ легко построить таблицу истинности (табл. 35).