Алгебра булевых функций

Пусть M – непустое множество элементов любой природы , в котором определены отношение равенства и три операции – сложение, умножение, отрицание, подчиняющиеся следующим аксиомам:

1) Коммутативные законы: а) x+y=y+x; б) x∙y=y∙x.

2) Ассоциативные законы: а) x+(y+z)=(x+y)+z; б) x∙(y∙z)=(x∙y)∙z.

3) Дистрибутивные законы: а) (x+y) z=(x∙z)+(y∙z); б) (x∙y)+z=(x+z)∙(y+z).

4) Законы идемпотентности: а) x+x=x; б) x∙x=x.

5) Закон двойного отрицания: .

6) Законы де-Моргана: а) ; б) .

7) Законы поглощения: а) ; б) .

Множество M называется булевой алгеброй.

64. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций.

Например, выражение является ДНФ.

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

Например, выражение является ДНФ, но не СДНФ. Выражение является СДНФ.

Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций (например выражение – КНФ).

Совершенной конъюнктивной нормальной формой (СКНФ) называется такая КНФ, у которой в каждую простую дизъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одинаковом порядке.

Например, выражение является СКНФ.

Пример 5.1. Пусть задана функция:

Видно, ее СДНФ содержит (по числу 1) 6 дизъюнктных слагаемых, но ее сокращенная ДНФ содержит (после объединения единиц) всего 2 буквы

f = x1Ъx2

Пример 5.2. Следующий пример показывает, “как соединять единицы по кругу”.

Здесь сокращенная ДНФ содержит 2 слагаемых (СДНФ содержала бы 5):

Пример 5.3. Пример показывает использование карт Карно при п = 4.

Здесь сокращенная ДНФ содержит 4 слагаемых (СДНФ содержит 8):