Множества. Комбинаторика. Отношения (стр. 9 )

освободиться от логических связок Þ, Û, Å, ½, ¯.

2)С помощью законов двойственности отнести знаки только к переменным (тесное отрицание).

3) С помощью закона дистрибутивности & относительно Ú перейти к дизъюнкции конъюнкций.

4) Воспользоваться законами идемпотентности & и Ú.

Пример.

.

Упражнения

Приведите к СДНФ функции:

1)  F(x, y) =. Ответ: .

2)  F(x, y, z) =.

Ответ: .

3)  F(x, y, z) =. Ответ: .

4)  F(x, y, z) =. Ответ: .

5)  F(x, y, z) =. Ответ: .

6)  F(x, y, z) =. Ответ: .

2.1.8. Совершенная конъюнктивная нормальная форма

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

,

,

.

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

ТЕОРЕМА. Для любой функции, не являющейся тождественно истинной, существует и притом единственная, эквивалентная ей СКНФ.

Доказательство. , ,

.

Отсюда , для любого набора значений переменных. Так как числа всех различных n-местных б. ф. и СКНФ от тех же переменных совпадают, то представление б. ф. в виде СКНФ возможно единственным образом. <

Пример. Построить СКНФ для f = (10001110).

.

Упражнения

Приведите к СКНФ функции.

1) . Ответ: .

2) . Ответ: .

2.1.9. Принцип двойственности

Функцию называют двойственной функции . Например,

, , , .

Ясно, что , т. е. функции f* и f двойственны друг другу.

ТЕОРЕМА. Если булева функция записана в виде суперпозиции &, Ú, Ø, то двойственная ей получается заменой каждой дизъюнкции на конъюнкцию, а каждой конъюнкции на дизъюнкцию.

Доказательство проведем методом полной математической индукции по числу операций над переменными. Без ограничения общности можно считать, что отрицание относится только к переменным. База индукции имеется в силу того, что .

Гипотеза индукции. Пусть утверждение теоремы верно для функции получающейся с помощью s операций &, Ú, Ø.

Право перехода. Пусть дана функция f(x1,…,xn), полученная с помощью s+1 операции &, Ú, Ø. Если, например, последняя операция конъюнкция, т. е. f = g & h, то

.

По гипотезе индукции g* и h* можно получить заменой в g и h, соответственно, каждой & на Ú и наоборот, т. е. f* может быть получена из f таким же образом. <

Упражнение

1) Докажите, что если б. ф. f является суперпозицией б. ф. g1,…,gs, то f* является суперпозицией той же структуры функций g1*,…,gs*.

2.1.10. Полином Жегалкина

Если в ЭК нет отрицаний переменных, то она называется монотонной элементарной конъюнкцией (Мон. ЭК). Например, 1, x, y, xy – все монотонные ЭК от переменных x, y; или 1, x, y, z, xy, xz, yz, xyz – все Мон. ЭК от переменных x, y, z. Сумма по модулю 2 различных монотонных элементарных конъюнкций называется полиномом Жегалкина.

ТЕОРЕМА. Любую булеву функцию можно представить в виде полинома Жегалкина, причем, единственным образом с точностью до коммутативности & и Å.

Доказательство. Так как , то любую б. ф. можно представить в виде суперпозиции &, Å, 0, 1. Так как число всех различных полиномов Жегалкина от x1,…,xn равно , т. е. числу всех различных n-местных б. ф., то любую б. ф. представить в виде полинома Жегалкина можно лишь единственным способом. <

Пример. Найти полином Жегалкина для функции f = (11111000).

Решение. Применим метод неопределенных коэффициентов.

x1x2x3	k0=1	k1=x1	k2=x2	k3=x3	k4=x1 x2	k5=x1 x3	k6=x2 x3	k7=x1 x2 x3	f
000	1	0	0	0	0	0	0	0	1
001	1	0	0	1	0	0	0	0	1
010	1	0	1	0	0	0	0	0	1
011	1	0	1	1	0	0	1	0	1
100	1	1	0	0	0	0	0	0	1
101	1	1	0	1	0	1	0	0	0
110	1	1	1	0	1	1	0	0	0
111	1	1	1	1	1	1	1	1	0

Если , то получим систему уравнений:

a0 = 1 a0 = 1

a0 Å a3 = 1 a3 = 0

a0 Å a2 = 1 a2 = 0

a0 Å a1 = 1 a6 = 0

a0 Å a2 Å a3 Å a6 = 1 a1 = 0

a0 Å a1 Å a3 Å a5 = 0 a5 = 1

a0 Å a1 Å a2 Å a4 = 0 a4 = 1

a0 Å a1 Å a2 Å a3 Å a4 Å a5 Å a6 Å a7 = 0 a7 = 1

Отсюда f = K0 Å K4 Å K5 Å K7 = 1 Å x1x2 Å x2x3 Å x1x2 x3.

Пример:

найти полином Жегалкина следующих функций:

1)  f(x, y, z) =.

2)  f(x, y, z) = (xÛz)Úy.

Решение:

1) Мы должны получить сумму по модулю 2 монотонных элементарных конъюнкций. Вспомним, что =xÅ1 и закон Моргана . Тогда получаем:

f(x, y, z)= ====