118 |
Глава 3. Булевы функции (БФ) |
|
|
=x01x02f(0; 0; x3)_x01x12f(0; 1; x3)_ x11x02f(1; 0; x3)_x11x12f(1; 1; x3) =
=x¹1x¹20 _ x¹1x20 _ x1x¹21(0 ! x3) _ x1x2(1 ! x3) =
=0 _ 0 _ x1x¹2 _ x1x2x3 = x1x¹2 _ x1x2x3:
Следствие 1.
f(x1; : : : ; xk; xk+1 : : : ; xn) =
xkf(x1; : : : ; xk¡1; 1; xk+1 : : : ; xn) _ x¹kf(x1; : : : ; xk¡10; xk+1 : : : ; xn):
Д о к а з а т е л ь с т в о . Без умаления общности положим k = 1: При x1 = 0 получим
¹
f(0; x2; : : : ; xn) = 0f(1; x2; : : : ; xn) _ 0f(0; x2; : : : ; xn) = = f(0; x2; : : : ; xn):
При x1 = 1 получим
¹
f(1; x2; : : : ; xn) = 1f(1; x2; : : : ; xn) _ 1f(0; x2; : : : ; xn) = = f(1; x2; : : : ; xn):
Следствие 2. f(x1; : : : ; xn) =
Wxs11 ¢ ¢ ¢ xsnn f(s1; : : : ; sn)
f(s1;:::;sk)=1
–продолжили разложение Шеннона до k = n и выбрали все ненулевые f(s1; : : : ; sn):
СДНФ |
Следствие 3. Любая булева функция (кро- |
||||
ме 0) имеет единственное представление в |
|||||
|
|
виде f(x1; : : : ; xn) = |
|
x1s1 ¢ ¢ ¢ xnsn : |
|
|
|
|
f(s1 |
;:::;s |
)=1 |
|
|
|
W k |
|
|
Д о к а з а т е л ь с т в о . Из следствия 2 |
|
|
|||
f(x1; : : : ; xn) = |
|
|
x1s1 ¢ ¢ ¢ xnsn f(s1; : : : ; sn) = |
|
|
|
(s1 |
;:::;s |
) |
|
|
|
W k |
|
|
|
|
3.3. |
Разложение функции по переменным |
119 |
||||||
|
|
|
|
|
|
|
|
|
= |
|
|
x1s1 ¢ ¢ ¢ xnsn f(s1; : : : ; sn) = |
|
|
|
x1s1 ¢ ¢ ¢ xnsn : |
|
f(s |
;:::;s |
)=1 |
f(s1 |
;:::;s |
)=1 |
|
|
|
|
1 |
W k |
|
W k |
|
|
|
|
Такое представление называется совершенной дизъюнктивной нормальной формой (СДНФ).
Следствие 3. можно сформулировать в виде теоремы:
Всякая булева функция (кроме 0) имеет единственную СДНФ. Следствие 4. Любая булева функция может быть выражена через отрицание, конъюнкцию и дизъюнкцию (¹; ¢; _).
Д о к а з а т е л ь с т в о . Если f = 0; то 0 = xx:¹ Если f 6= 0; то смотри следствие 3.
Построение СДНФ по таблице истинности выполняется в точности в соответствии со следствием 3. Для каждой очередной строки, в которой значение функции равно 1 (f(s1; : : : ; sk) = 1), формируется конъюнкция всех переменных: если значение пере-
менной xi = 0; то в конъюнкцию эта переменная входит в степени 0 (x0i ), то есть с отрицанием, в противном случае – в степени 1 (x1i ), то есть без отрицания. Дизъюнкция всех конъюнкций образует СДНФ.
Пример 3.15.
Таблица 3.8. Построение СДНФ по таблице истинности
|
|
x1 |
x2 |
x3 |
|
f |
|
Конъюнкция |
0 |
|
0 |
0 |
0 |
|
0 |
|
|
1 |
|
0 |
0 |
1 |
|
1 |
|
x¹1x¹2x3 |
2 |
|
0 |
1 |
0 |
|
0 |
|
|
3 |
|
0 |
1 |
1 |
|
1 |
|
x¹1x2x3 |
4 |
|
1 |
0 |
0 |
|
0 |
|
|
5 |
|
1 |
0 |
1 |
|
1 |
|
x1x¹2x3 |
6 |
|
1 |
1 |
0 |
|
0 |
|
|
7 |
|
1 |
1 |
1 |
|
1 |
|
x1x2x3 |
f(x1; x2; x3) = x¹1x¹2x3 _ x¹1x2x3 _ x1x¹2x3 _ x1x2x3: J
120 |
Глава 3. Булевы функции (БФ) |
|
|
СКНФ
Теорема 3.6 Любую булеву функцию (кроме 1) можно представить в виде
f(x1; : : : ; xn) = |
V |
(x1s¹1 _ ¢ ¢ ¢ _ xns¹n ) |
f(s1;:::;sn)=0
До к а з а т е л ь с т в о . Любую функцию, в том числе f¤(x1; : : : ; xn) = f¹(¹x1; : : : ; x¹n) можно представить в СДНФ:
f¤(x1; : : : ; xn) = |
|
_ k |
x1s1 ¢ ¢ ¢ xnsn |
|
f¤(s1 |
|
|||
|
|
;:::;s |
)=1 |
|
f = f¤¤: Найдем двойственную к f¤ функцию f : |
||||
f(x1; : : : ; xn) = |
|
|
(x1s¹1 _ ¢ ¢ ¢ _ xns¹n ) |
|
f(s1 |
;:::;s |
|
)=0 |
|
^n |
|
|
||
Такая форма представления функции f(x1; : : : ; xn) называется совершенной конъюнктивной нормальной формой (СКНФ).
Эту теорему можно сформулировать в виде:
Всякая булева функция (кроме 1) имеет единственную СКНФ.
Построение |
Построение СКНФ по таблице истинно- |
сти выполняется в соответствии с теоремой |
|
СКНФ по |
3.6. Для каждой очередной строки, в ко- |
таблице |
торой f(s1; : : : ; sk) = 0, формируется дизъ- |
истинности |
юнкция: если значение переменной xi = 0; |
|
то в дизъюнкцию эта переменная входит |
степени 1 (x1i ), в противном случае – в степени 0 (x0i ). Конъюнкция всех дизъюнкций образует СКНФ.
Пример 3.16. Построим СКНФ для функции из примера 3.15.
Таблица 3.9. Построение СКНФ по таблице истинности
3.3. Разложение функции по переменным |
121 |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
x2 |
x3 |
|
f |
|
Дизъюнкция |
|
|
|
0 |
|
0 |
0 |
0 |
|
0 |
|
x1 _ x2 _ x3 |
|
|
|
1 |
|
0 |
0 |
1 |
|
1 |
|
x1 _ x¹2 _ x3 |
|
|
|
2 |
|
0 |
1 |
0 |
|
0 |
|
|
|
|
|
3 |
|
0 |
1 |
1 |
|
1 |
|
x¹1 _ x2 _ x3 |
|
|
|
4 |
|
1 |
0 |
0 |
|
0 |
|
|
|
|
|
5 |
|
1 |
0 |
1 |
|
1 |
|
x¹1 _ x¹2 _ x3 |
|
|
|
6 |
|
1 |
1 |
0 |
|
0 |
|
|
|
|
|
7 |
|
1 |
1 |
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
f(x1; x2; x3) = (x1 _x2 _x3)(x1 _x¹2 _x3)(¹x1 _x2 _x3)(¹x1 _x¹2 _x3):
Представление формул в СДНФ и СКНФ
Пусть функция f(x1; : : : ; xn) представлена формулой F в некотором базисе (f1; : : : ; fk). Любая функция может быть выражена через три базисные операции (¹; ¢; _). Преобразование формулы к совершенным формам выполняется за несколько шагов.
1.Каждую подформулу (и сама формулу F ) выражают через базисные операции (¹; ¢; _), используя разложение Шеннона или равносильные преобразования.
2.Отрицание вносят непосредственно к переменным, ис-
¹
пользуя инволютивность отрицания (F = F ) и законы де Моргана.
3. Применяя нужное число раз дистрибутивные законы, формулу приводят к виду _ x01 ¢ ¢ ¢ x0k или ^x01 _ ¢ ¢ ¢ _ x0k; где x0i
–переменная или отрицание переменной (литерал).
4.Приведение подобных. Используя идемпотентность конъюнкции (дизъюнкции), удаляют повторные вхождения переменных в каждую конъюнкцию (дизъюнкцию) и повторные вхождения одинаковых конъюнкций в дизъюнкцию и одинаковых дизъюнкций в конъюнкцию. В результате формула не содержит повторных переменных, конъюнкций и дизъюнкций.
Определение. Форма представления формулы в виде _ x01 ¢ ¢ ¢ x0k
называется дизъюнктивной нормальной формой (ДНФ).
122 |
Глава 3. Булевы функции (БФ) |
|
|
Конъюнкция x01 ¢ ¢ ¢ x0k, в которой все переменные различны, называется элементарной конъюнкцией (ЭК).
Число переменных, образующих ЭК, называется ее рангом. ЭК ранга n называется полной.
Длина ДНФ – это число ее элементарных конъюнкций Ранг ДНФ – это сумма рангов ЭК, образующих ДНФ. Две ЭК ортогональны по переменной xi; если xi входит в
одну конъюнкцию с отрицанием, а в другую без отрицания. (В СДНФ все конъюнкции попарно ортогональны).
Две ЭК смежны по переменной xi; если они ортогональны только по одной переменной xi:
Две ЭК являются соседними по переменной xi; если ортогональны только по xi; а все остальные переменные одинаковы.
Определение. Форма представления формулы в виде ^(x01 _
¢ ¢ ¢_x0k) называется конъюнктивной нормальной формой (КНФ). Дизъюнкция x01 _ ¢ ¢ ¢ _ x0k, в которой все переменные раз-
личны, называется дизъюнктом (клозом)1.
Число переменных дизъюнкта – это его ранг. Полный дизъюнкт (ранга n) содержит все n переменных
Ранг КНФ – это сумма рангов дизъюнктов, образующих КНФ.
Число дизъюнктов в КНФ – это ее длина.
Примеры 3.17.
1. Представить в ДНФ и КНФ формулу (x1 _ x¹2)(x3 ! x4).
(x1 _ x¹2)(x3 ! x4) =
=x¹1x2(¹x3 _ x4) =
=x¹1x2x¹3 _ x¹1x2x4
закон де Моргана и x3 ! x4 = x¹3 _ x4;
КНФ, дизъюнкты x¹1; x2; x¹3 _ x4;
ДНФ, ЭК x¹1x2x¹3; x¹1x2x4:
Ранги дизъюнктов 1, 1 и 2 соответственно, ранг КНФ равен 4 (1 + 1 + 2), длина КНФ равна 3.
Ранги ЭК 3 и 3 соответственно, ранг ДНФ равен 6 (3 + 3), длина ДНФ равна 2.
2. ЭК x¹1x¹2x3 и x1x2x3 ортогональны по переменным x1 и x2; x¹1x2x3 и x1x¹2x3 также ортогональны по x1 и x2:
1Клоз – лат., англ. clause, предложение.
3.3. Разложение функции по переменным |
123 |
|
|
|
|
ЭК x¹1x2x¹3 и x2x3x4 – смежны по x3, а x¹1x¹2x3 и x¹1x2x3 – соседние по x2: J
5. Если в некоторой элементарной конъюнкции K или дизъюнкте C не содержится переменная xj, то ее добавляют:
K ¢ 1 = K(xj _ x¹j) = Kxj _ Kx¹j;
C _ 0 = D _ xjx¹j = (C _ xj)(C _ x¹j):
6.Сортировка. Используя коммутативность, переменные
вкаждой ЭК (каждом дизъюнкте) сортируют в лексикографическом порядке.
Пример 3.18. Дополнить ДНФ и КНФ до совершенных.
¹ |
¹ |
ДНФ: ab _ bc = (c _ c¹)ab _ bc(a _ a¹) = |
|
¹ |
¹ |
cab _ cab¹ _ bca _ bca:¹ |
|
В полученной СДНФ упорядочиваем переменные: |
|
¹ |
¹ |
abc _ abc¹ _ abc _ a¹bc: |
|
¹ |
¹ |
КНФ: (a _ b)(b _ c) = cc¹ _ (a _ b)(b _ c) _ aa¹ = |
|
|
¹ |
= (c _ a _ b)(¹c _ a _ b)(b _ c) = |
|
|
¹ |
|
|
= (c _ a _ b)(¹c _ a _ b)(b _ c) _ aa¹ = |
|||
|
¹ |
|
¹ |
= (c _ a _ b)(¹c _ a _ b)(b _ c _ a)(b _ c _ a¹): |
|||
В полученной CКНФ упорядочиваем переменные: |
|||
|
|
¹ |
¹ |
(a _ b _ c)(a _ b _ c¹)(a _ b _ c)(¹a _ b _ c): |
|||
Представление |
При рассмотрении полных систем функ- |
||
БФ |
ций нам понадобится еще одна форма раз- |
||
полиномами |
ложения булевых функций – полиномы |
||
Жегалкина |
Жегалкина. Рассмотрим некоторые свой- |
||
a © b = b © a |
ства операции ©: |
||
|
(коммутативность); |
||
a © (b © c) = (a © b) © c |
(ассоциативность); |
||
a(b © c) = ab © ac |
(дистрибутивность); |
||
a © 0 = a; a © 1 = a;¹ |
|
|
|
a © b © ab = a _ b; |
|
|
|
a © a = 0: |
|
|
|
Определение. Функция f(x1; : : : ; xn) представлена в форме
полинома Жегалкина, если она имеет вид
124 Глава 3. Булевы функции (БФ)
f(x1; : : : ; xn) =
a0 © a1x1 © ¢ ¢ ¢ © anxn©
©a12x1x2 © ¢ ¢ ¢ © an¡1;nxn¡1xn©
©a123x1x2x3 © ¢ ¢ ¢ © an¡2;n¡1;nxn¡2xn¡1xn©
¢ ¢ ¢ ¢ ¢ ¢
©a1;:::;nx1x2 ¢ ¢ ¢ xn;
ai:::k 2 f0; 1g – коэффициенты полинома, длина полинома – это число ЭК полинома, степень полинома – наибольший из рангов ЭК, входящих в полином.
З а м е ч а н и е.
Константа 1 считается полиномом длины 1 и степени 0, константа 0 – полиномом длины 0 и степени 0. I
Определение. Полином линейный, если его степень 6 1:
Пример 3.19. 1 © x3 © x1x2 © x2x4x5x6 – полином Жегалкина, его длина равна 4, степень равна 4.
Полином 1 © x1 © x2 © x5 – линейный. J
Теорема 3.7 Любую булеву функцию можно единственным образом представить в виде полинома Жегалкина.
Д о к а з а т е л ь с т в о . (Конструктивное.) Если f = 0; то f = a0 = 0 – полином Жегалкина.
Если f 6= 0; то f можно представить (единственным образом) в форме СДНФ. В СДНФ операцию _ заменяют на ©: Почему можно это сделать? Для двух различных ЭК Ki и Kj
Ki _ Kj = Ki © Kj © KiKj (свойство операции ©:)
Так как все конъюнкции в СДНФ попарно ортогональны, то
KiKj = 0 и Ki _ Kj = Ki © Kj: Переменные с отрицанием x¹ заменяют на x © 1: Затем раскрывают скобки и приводят
подобные (x © x = 0).
Единственность представления полиномом Жегалкина следует из единственности представления в СДНФ.
Пример 3.20. Представить СДНФ
f(x1; x2; x3) = x¹1x¹2x3 _ x¹1x2x3 _ x1x¹2x3
полиномом Жегалкина.