10. Алгебра логики

10.1.Булева алгебра

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

- коммутативность
- ассоциативность
- дистрибутивность
- свойства констант
- свойства отрицания

Приведенные свойства позволяют получить ряд других важных законов:

-закон двойного отрицания
- законы де Моргана
- законы идемпотентности
- законы поглошения

Использование этих тождеств существенно упрощает запись логических формул.

10.2. Двойственность формул булевой алгебры

Из свойств, при­веденных в (10.1), видно, что в булевой алгебре, как и в алгебре множеств, имеет место, принцип двойственности. Взаимно двой­ственными операциями являются дизъюнкция и конъюнкция. За­меняя в некоторой формуле каждую операцию на двойственную ей, получаем двойственную формулу. Например, из формулы имеем .

На основе законов де Моргана выводится следующее положение: если и - двойственные формулы, то равносильна . Отсюда следует, что

=

т. е. двойственная формула выражается как отрицание формулы, полученной из исходной замещением каждой переменной ее отри­цанием. Таблица соответствия двойственной функции получается заменой аргументов и значений в исходной функции на противополож­ные, т. е. 0 заменяется на 1, а 1 - на 0. Если формулы и равносильны, то и двойственные им формулы и также равносильны.

Формула или функция, равносильная своей двойственной, называется самодвойственной. Самодвойственная функция на инверсных наборах принимает инверсные значения.

10.3. Нормальные формы

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

Функция приводится к нормальной форме следующим путем: 1) с помощью законов де Моргана формула преобразуется к такому виду, чтобы знаки отрицания относились только к отдельным переменным; 2) на основе первого (второго) дистрибутивного закона формула сводится к дизъюнкции конъюнкций (конъюнкции дизъюнкций); 3) полученное выражение упрощается и соответствии с тождествами и ( и ).

Пример:

- дизъюнктивная нормальная форма (ДНФ).

- конъюнктивная нормальная форма (КНФ).

Члены дизъюнктивной (конъюнктивной) нормальной формы, представляющие собой элементарные конъюнкции (дизъюнкции) k букв, называют минитермами (макстермами) k-го ранга. Так, в приведенных выше формах ху - минитерм второго ранга, хуг - минитерм третьего ранга, а - макстерм второго ранга.

Если исходная формула содержит другие операции, то они предварительно выражаются через дизъюнкцию, конъюнкцию и отри­цание, например:

Пример: