Читайте также:
|
|
Теорема. Пусть f (x 1, x 2,…, xn) – произвольная булева функция. Тогда
f (x 1, x 2,…, xn) = x 1× f (1, x 2,…, xn) Ú x 1’× f (0, x 2,…, xn);
f (x 1, x 2,…, xn) = (x 1Ú f (0, x 2,…, xn))(x 1’Ú× f (1, x 2,…, xn)).
Последовательно применяя данное разложение по переменным x 1, x 2,…, xn, можно получить формулу, содержащую лишь дизъюнкции, конъюнкции и отрицания. Например,
f (x, y) = f (1,1) xy Ú f (1,0) xy ’Ú f (0,1) x ’ y Ú f (0,0) x ’ y ’, (7)
f (x, y) = (f (1,1)Ú x ’Ú y ’)(f (1,0)Ú x ’Ú y)(f (0,1)Ú x Ú y ’)(f (0,0)Ú x Ú y). (8)
Разложение вида (7) называют совершенной дизъюнктивной нормальной формой (СДНФ), а разложение вида (8) — совершенной конъюнктивной нормальной формой (СКНФ). Нетрудно видеть, что в СДНФ (7) можно отбросить те слагаемые, для которых f (a, b)=0, а в СКНФ (8) — сомножители, где f (a, b)=1.
Элементарной конъюнкцией (конъюнктом) называют конъюнкцию переменных, быть может с их отрицаниями, в которой каждая переменная встречается не более одного раза.
Дизъюнкцию конечного числа конъюнктов называют дизъюнктивной нормальной формой (ДНФ). Таким образом, разложение (7) представляет собой ДНФ. Отличие СДНФ от ДНФ заключается в том, что в совершенной форме каждое слагаемое (конъюнкт) содержит все переменные и/или их отрицания.
Аналогичные определения со взаимной заменой дизъюнкций на конъюнкции приводят к понятиям: э лементарная дизъюнкция (дизъюнкт) и конъюнктивная нормальная форма (КНФ).
Принцип двойственности имеет место и для булевых функций. Двойственной к булевой функции f (x, y,…, z) называется функция
f *(x, y,…, z)= f ’(x ’, y ’,…, z ’).
Теорема. Если f (x, y,…, z) представлена формулой, содержащей лишь дизъюнкции, конъюнкции и отрицания, то двойственная функция f *(x, y,…, z) получается заменой в исходной формуле дизъюнкций на конъюнкции, а конъюнкций на дизъюнкции.
Примеры
1. Найти СДНФ и СКНФ для следующей функции:
xy | f
0 0 | 0
0 1 | 1
1 0 | 0
1 1 | 0
Решение. Воспользуемся разложениями (7) и (8):
f (x, y)= f (1,1) xy Ú f (1,0) xy ’Ú f (0,1) x ’ y Ú f (0,0) x ’ y ’=
=0 xy Ú0 xy ’Ú1 x ’ y Ú0 x ’ y ’= x ’ y, (СДНФ)
f (x, y)=(f (1,1)Ú x ’Ú y ’)(f (1,0)Ú x ’Ú y)(f (0,1)Ú x Ú y ’)(f (0,0)Ú x Ú y)=
=(0Ú x ’Ú y ’)(0Ú x ’Ú y)(1Ú x Ú y ’)(0Ú x Ú y)=)=(x ’Ú y ’)(x ’Ú y)(x Ú y). (СКНФ)
2. Построить СДНФ двойственной функции к f (x, y, z)= x ’→ yz.
Решение. Способ I. Воспользуемся определением двойственной формулы:
f *(x, y, z)= f ’(x ’, y ’, z ’)=(x ’’→ y ’ z ’)’=(x → y ’ z ’)’=(x ’Ú y ’ z ’)’=
=x ’’(y ’ z ’)’= x (y Ú z)= xy Ú xz.
Способ II. Воспользуемся теоремой двойственности. Исключим тождественными преобразованиями импликацию:
f (x, y, z)= x ’→ yz = x Ú yz.
Далее, заменим символы конъюнкции и дизъюнкции друг на друга:
f *(x, y, z)= x (y Ú z)= xy Ú xz.
Вопросы и упражнения для самостоятельной работы
4. Построить СДНФ и СКНФ для функций f 1, f 2, f 3 и f 4, заданных таблицей
x y z | f 1 f 2 f 3 f 4
0 0 0 | 0 1 1 1
0 0 1 | 0 0 1 1
0 1 0 | 1 1 0 1
0 1 1 | 1 1 0 1
1 0 0 | 1 0 1 1
1 0 1 | 1 0 0 1
1 1 0 | 1 1 0 1
1 1 1 | 1 0 0 1
5. Построить СДНФ и СКНФ для следующих функций:
а) x | y, б) x ↓ y, в) (x Å y)↓ z, г) x «(y Ú z), д) xy Å y ’ z Å x ’ z.
6. Построить двумя способами СКНФ и СДНФ двойственных функций f * для следующих функций:
а) x | y, б) x ↓ y, в) x Å y г) x Å yz, д) x |(y Å z).
Дата добавления: 2015-04-11; просмотров: 22 | Поможем написать вашу работу | Нарушение авторских прав |