Логические (булевы) функции основные логические функции

Пример 2а. Дана ДНФ  . Требуется для этой функции найти полином Жегалкина и перейти от ДНФ к КНФ, а затем и к СКНФ. Сначала найдем полином Жегалкина (вторым способом). Для этого ставим двойное отрицание и по правилам де Моргана “убираем” дизъюнкцию, потом “убираем” отрицания по правилу . После этого раскрываем скобки, учитывая при этом, что четное число слагаемых (по модулю 2) равно 0, а нечетное – одному такому слагаемому. Тогда
((x+1)(y+1)+1)(xy(z+1)+1)+1=(xy+x+y+1+1)(xyz+xy+1)+1=
= (xy+x+y)(xyz+xy+1)+1= xyz + xyz + xyz + xy+xy+ xy+ xy +
+ x+ y+1 = xyz+x+y+1.
Последнее выражение и является полиномом Жегалкина.
Для того чтобы перейти к КНФ для выражения L (в соответствии с разд. 3) ставим над L два отрицания и, оставляя временно верхнее отрицание без изменения, приводим оставшееся выражение к ДНФ. Затем по правилу де Моргана получаем КНФ. Таким образом, можем получить
.
Далее по правилу Блейка можем из последнего выражения исключить yz, тогда получим:  . Это и есть КНФ.
Чтобы из последнего выражения получить СКНФ, нужно в первой и второй дизъюнкции добавить  , а в третьей –   Затем воспользуемся распределительным законом:

Последнее выражение и есть СКНФ.
Пример 2,б. Пусть имеется выражение  . Требуется записать L в виде ДНФ, а затем перейти к СДНФ.
Ясно, что ДНФ можно получить простым раскрытием скобок. В обеих скобках есть  , которое поглощает слагаемые, содержащие  , поэтому .  Это и есть ДНФ. Для того чтобы получить СДНФ,  умножаем на  , а  умножаем на (y  и раскрываем скобки. Тогда
.
С самого начала надо позаботиться о правильном порядке переменных, что требуется для СДНФ, но последнее выражение еще не является СДНФ, так как содержит два одинаковых слагаемых. После уничтожения одного из них получим окончательный ответ:
Разберем пример решения задач типа 21–30.