112 |
Глава 3. Булевы функции (БФ) |
|
|
3.2 Равенство булевых функций
Определение. Булевы функции равны
f1(x1; : : : ; xn) = f2(x1; : : : ; xn);
если на одинаковых наборах значений переменных они принимают одинаковые значения.
Если функции зависят от разного числа переменных, то об их равенстве или неравенстве нельзя судить без дополнительных соглашений.
Переменная xi называется фиктивной для булевой функции, если
f(x1; : : : ; xi¡1; 0; xi+1; : : : ; xn) = f(x1; : : : ; xi¡1; 1; xi+1; : : : ; xn)
при любых наборах значений остальных переменных.
Переменная x; не являющаяся фиктивной называется существенной, при этом функция f существенно зависит от x: Примеры 3.7. 1. Для функций одной переменной 0 и 1 переменная x является фиктивной.
2. Для функций двух переменных:
Таблица 3.5. Фиктивные переменные
x1 |
0011 |
|
Фик- |
x2 |
0101 |
|
тивные |
f0 |
0000 |
|
x1; x2 |
f3 |
0011 |
|
x2 |
f5 |
0101 |
|
x1 |
f10 |
1010 |
|
x1 |
f12 |
1100 |
|
x2 |
f15 |
1111 |
|
x1; x2 |
Фиктивную переменную xi можно удалить из таблицы следующим образом: вычеркнуть столбец xi и все строки, в которых xi = 1 (или все строки, в которых xi = 0.)
Пример 3.8. Для f12(x1; x2) (x2 – фиктивная): вычеркнув столбец x2 и строки 1 и 3 из таблицы
3.2. Равенство булевых функций |
|
|
|
113 |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
x2 |
|
f12 |
|
|
|
|
|
|
|
|
|
|
0 |
|
0 |
0 |
|
1 |
|
|
|
|
x1 |
|
f |
|
|
|
1 |
|
0 |
1 |
|
1 |
получим |
|
0 |
|
0 |
|
1 |
. |
|
|
2 |
|
1 |
0 |
|
0 |
|
|
1 |
|
1 |
|
0 |
|
|
|
3 |
|
1 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Полученная функция одной переменной – отрицание. J
Теперь можно уточнить определение равенства булевых функций.
Определение. Булевы функции f1(x1; : : : ; xn) и f2(y1; : : : ; ym)
равны (с точностью до фиктивных переменных), если f2 может быть получена из f1 введением или удалением фиктивных переменных.
Таким образом, можно сравнивать функции с разным числом переменных. В дальнейшем булевы функции рассматриваются с точностью до фиктивных переменных. Это позволяет считать, что все булевы функции (в данной системе функций) зависят от одних и тех же переменных.
Уточнение. Булевы функции f1 и f2 равны, если их существенные переменные равны и на каждом наборе значений переменных функции f1 и f2 принимают равные значения.
Равносильные |
Одна и та же булева функция над данным |
базисом © может иметь множество реали- |
|
формулы |
заций формулами. Для сравнения формул |
|
вводится понятие равносильности. |
Определение. Формулы F1 и F2, реализующие равные булевы функции, называются равносильными F1 = F2.
Равносильность формул можно доказать с помощью построения таблиц функций, реализованных этими формулами.
Пример 3.9. Доказать равносильность x _ yz = (x _ y)(x _ z):
Таблица 3.6. Равносильные формулы
114 |
|
|
|
|
|
Глава 3. Булевы функции (БФ) |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
y |
z |
|
x _ yz |
(x _ y)(x _ z) |
||
|
0 |
0 |
0 |
|
0 |
|
0 |
|
|
0 |
0 |
1 |
|
0 |
|
0 |
|
|
0 |
1 |
0 |
|
0 |
|
0 |
|
|
0 |
1 |
1 |
|
1 |
|
1 |
|
|
1 |
0 |
0 |
|
1 |
|
1 |
|
|
1 |
0 |
1 |
|
1 |
|
1 |
|
|
1 |
1 |
0 |
|
1 |
|
1 |
|
|
1 |
1 |
1 |
|
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
Функции, реализованные равносильными формулами x _ yz и (x _ y)(x _ z), равны. J
Равносильность формул можно доказать с помощью известных равносильных преобразований. В базисе © = f¹; ^; _g для краткости и наглядности обозначим _ через +, ^ будем опускать.
Для любых формул a; b; c следующие равносильности можно проверить с помощью соответствующих таблиц. В логике некоторые из этих равносильностей называются законами.
a + b = b + a; |
ab = ba; |
(коммутативность); |
a + (b + c) = (a + b) + c; |
a(bc) = (ab)c; |
(ассоциативность); |
a + bc = (a + b)(a + c); |
a(b + c) = ab + ac; |
(дистрибутивность); |
a + 0 = a; |
a ¢ 1 = a; |
|
a + a¹ = 1; |
aa¹ = 0; |
|
Эти 5 пар равносильностей представляют собой аксиомы абстрактной булевой алгебры (см. стр. 29). Следующие равносильности можно либо вывести из аксиом, либо проверить по таблицам истинности.
a + a = a; |
a a = a |
(идемпотентность); |
|||
a + 1 = 1; |
a 0 = 0; |
|
|||
|
|
¹ |
|
¹ |
(законы де Моргана); |
|
|
||||
a + b = a¹ b; |
a b = a¹ + b |
||||
a + a b = a; |
a (a + b) = a |
(поглощение); |
|||
a¹ = a |
|
|
(двойное отрицание); |
||
ab + ab¹ = b; |
(a + b)(¹a + b) = b |
(склеивание); |
|||
ab + ac¹ = |
ab + ac¹ + bc |
|
|||
|
|
|
(обобщенное склеивание): |
||
3.2. Равенство булевых функций |
115 |
|
|
|
|
Двойственные Определение. Функция
функции
f¤(x1; : : : ; xn) = f¹(¹x1; : : : ; x¹n)
называется двойственной к функции f(x1; : : : ; xn) 2 Pn.
Примеры 3.10.
1.(xy)¤ = (¹xy¹) = x + y;
2.(x + y)¤ = (¹x + y¹) = xy; J
Для получения таблицы функции f(¹x1; : : : ; x¹n) нужно перевернуть таблицу исходной функции f(x1; : : : ; xn), а для получения таблицы функции f¹(¹x1; : : : ; x¹n) еще и инвертировать столбец значений функции f(¹x1; : : : ; x¹n).
Пример 3.11. Построим таблицу функции, двойственной к функции © :
Таблица 3.7. Двойственные функции
x |
y |
|
©(x; y) |
©(¹x; y¹) |
©¤(x; y) |
0 |
0 |
|
0 |
0 |
1 |
0 |
1 |
|
1 |
1 |
0 |
1 |
0 |
|
1 |
1 |
0 |
1 |
1 |
|
0 |
0 |
1 |
|
|
|
|
|
|
Таким образом, функция двойственная к © есть $ (©¤ =$). J
Другие пары двойственных функций: _¤ = ^; ^¤ = _; 0¤ = 1;
1¤ = 0; j¤ =#; #¤= j.
Теорема 3.3
f¤¤(x1; : : : ; xn) = f(x1; : : : ; xn):
Д о к а з а т е л ь с т в о .
(f¹¤(¹x1; : : : ; x¹n))¤ = f¹(x¹1; : : : ; x¹n) = f(x1; : : : ; xn):
Определение. Функция f называется самодвойственной, если f¤ = f:
Пример 3.12. Отрицание и тождественная функция самодвойственны:¹¤ =¹
116 |
Глава 3. Булевы функции (БФ) |
|
|
Теорема 3.4 (Принцип двойственности.) Функция, двойственная суперпозиции функций, равна суперпозиции двойственных функций:
f¤(f1; : : : ; fm) = f¤(f1¤; : : : ; fm¤ )
Д о к а з а т е л ь с т в о . f¤(f1; : : : ; fm) =
f¹(f1(¹x1; : : : ; x¹n); : : : ; fm(¹x1; : : : ; x¹n)) =
f¹(f¹1(¹x1; : : : ; x¹n); : : : ; f¹m(¹x1; : : : ; x¹n)) = f¹(f¹1¤(x1; : : : ; xn); : : : ; f¹m¤ (x1; : : : ; xn)) = f¤(f1¤(x1; : : : ; xn); : : : ; fm¤ (x1; : : : ; xn))
из определения
f¤(x1; : : : ; xn) = f¹(¹x1; : : : ; x¹n):
З а м е ч а н и е. Принцип двойственности сформулирован для суперпозиции любых функций. Если ограничиться только базисными функциями, то принцип двойственности переносится на формулы.
Следствие 1. Если формула F реализует функцию
f(x1; : : : ; xn), то двойственная ей формула F ¤ реализует двой-
ственную функцию f¤(x1; : : : ; xn):
Следствие 2.
F1 = F2 ) F1¤ = F2¤
Примеры 3.13.
1.a + b = b + a ) ab = ba:
¹¹
2.a + b = a¹b ) ab = a¹ + b: J
3.3Разложение функции по переменным (разложение Шеннона)
Введем обозначение |
(x;¹ s = 0: |
xs = |
|
|
x; s = 1; |
xs имеет следующие свойства.
3.3. Разложение функции по переменным |
117 |
|||||||||
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
||
|
x |
s |
xs |
|
Комментарий |
|
|
|
||
|
0 |
0 |
1 |
|
0 |
0 |
¹ |
|
|
|
|
|
|
= 0 = 1 |
xs = 1 () x = s |
||||||
|
0 |
1 |
0 |
|
01 = 0 |
|||||
|
1 |
0 |
0 |
|
1 |
0 |
¹ |
1s = s; 0s = s¹ |
||
|
|
|
= 1 = 0 |
|
|
|
||||
|
1 |
1 |
1 |
|
11 |
= 1 |
|
|
|
|
Теорема |
3.5 Любую функцию f(x1; : : : ; xn) |
можно предста- |
||||||||
вить в виде
f(x1; : : : ; xk; xk+1 : : : ; xn) =
(?)
_
xs11 ¢ ¢ ¢ xskk f(s1; : : : ; sk; xk+1; : : : ; xn);
(s1;:::;sk)
(дизъюнкция по всем возможным наборам (s1; : : : ; sk)):
Д о к а з а т е л ь с т в о . Покажем, что равенство выполняется для любого набора значений переменных a1; : : : ; an:
f(a1; : : : ; ak; ak+1 : : : ; an) =
_
as11 ¢ ¢ ¢ askk f(s1; : : : ; sk; ak+1; : : : ; an);
(s1;:::;sk)
Рассмотрим выражение as11 ¢ ¢ ¢ askk : Если хотя бы одно из значений asii = 0; то и as11 ¢ ¢ ¢ askk = 0: Тогда и
as11 ¢ ¢ ¢ askk f(s1; : : : ; sk; ak+1; : : : ; an) = 0:
Выражение as11 ¢ ¢ ¢ askk = 1 только в том случае, когда s1 = a1; : : : ; sk = ak (xs = 1 () x = s): При этом
f(s1; : : : ; sk; ak+1; : : : ; an) = f(a1; : : : ; ak; ak+1; : : : ; an):
Равенство (?) выполняется при любом наборе значений
переменных (x1; : : : ; xn): £
Формула (?) называется разложением Шеннона.
Пример 3.14. Найти разложение Шеннона по переменным x1; x2 булевой функции f(x1; x2; x3) = x1(x2 ! x3) :
f(x1; x2; x3) = |
xs1 xs2 f(s1; s2; x3) = |
|
|
1 |
2 |
;s |
) |
|
(s1W2 |
|
|