Законы булевой алгебры

Законами булевой алгебры называются следующие равносильности:

1. Идемпотентность

.

2. Коммутативность

.

3. Ассоциативность

.

4. Дистрибутивность

.

5. Закон поглощения

.

6. Закон склеивания

.

7. Закон нуля

.

8. Закон единицы

.

9. Закон дополнения

.

10. Инволютивность

.

11. Законы де Моргана

.

Тема 3.5. СДНФ и СКНФ

Определим степень следующим образом:

, т.е. , .

Выражение вида

называется полной совершенной элементарной конъюнкцией.

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

Выражение вида

называется полной совершенной элементарной дизъюнкцией.

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

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

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

ПРИМЕР:

На этом примере покажем связь между таблицей истинности и функцией и ее совершенными нормальными формами:

х1	х2

СДНФ:

СКНФ:

.

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

х1	х2		элементарные конъюнкции

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

х1	х2		элементарные дизъюнкции