1. Булева алгебра
Сравнение основных свойств множеств и логики высказываний показа-ло, что эти свойства имеют много общих черт. Данное обстоятельство нашло свое воплощение в общей теории, известной как булева алгебра.
Свое название теория получила в честь Дж. Буля, основоположника математической логики.
Операция, заданная на некотором множество, называется бинарной, ес-ли она действует на два элемента этого множества и ее результатом является элемент этого же множества.
Операция, заданная на множестве, называется унарной, если она дейст-вует на один элемент множества и ее результатом является элемент этого же множества.
Булева алгебра есть множество В, содержащее специальные элементы 1 и 0, на котором заданы бинарные операции + и • и унарная операция '.
.............
4. Нормальные формы и полиномы
Возведение в степень булевых функций определяется так:
, .
Элементарной конъюнкцией называется выражение , где все переменные, вошедшие в состав конъюнкции, различны, .
Дизъюнктивной нормальной формой (ДНФ) данной булевой функции называется ее представление в виде дизъюнкции некоторых элементарных конъюнкций.
Для любой булевой функции справедлива формула дизъ-юнктивного разложения по совокупности переменных:
.
Эта формула остается справедливой и для разложения не только по первым k переменным.
Совершенной дизъюнктивной нормальной формой (СДНФ) данной бу-левой функции называется ее представление в виде:
...............