diskr_edit (1023554), страница 13
Текст из файла (страница 13)
x1Vx2 x1Vx2Vx3) & (x1Vx2Vx3).
x1Vx3 (x1Vx3Vx2)&(x1Vx3Vx2).
x2 Vx3 (x2Vx3Vx1) & (x2Vx3Vx1).
Поэтому имеем:
f(x1, x2, x3) x1Vx2Vx3)&(x1Vx2Vx3)&x1Vx3Vx2)&(x1Vx3Vx2)&(x2Vx3Vx1)&(x2 V x3Vx1).
3. Применив шаг 5, получим:
f(x1, x2, x3) (x1Vx2Vx3)&(x1Vx2Vx3)&(x1Vx2Vx3)&(x1Vx2Vx3)&(x1Vx2Vx3)&(x1 Vx2Vx3).
4. Замечаем, что 1-ый и 3-ий, а также 4-ый и 5-ый дизъюнктивные члены полученного выражения совпадают, применяем шаг 6 и получим окончательно СКНФ формулы f(x1, x2, x3):
f(x1, x2, x3) (x1Vx2Vx3)&(x1Vx2Vx3)&(x1Vx2Vx3)&(x1Vx2Vx3).
4.7. Разложение булевой функции по переменным
Пусть s принимает значения 0 или 1, т.е. s
{0, 1}.
Введем
обозначение:
xs = x, если s = 0, xs = x, если s = 1.
Т.е. x0 = x, x1 = x.
Очевидно, что xs = 1, если x = s и xs = 0, если x 
s.
Теорема 4.5 (о разложении булевой функции по переменным).
Каждая булева функция f(x1, x2, ... , xn) может быть представлена в виде:
f(x1, x2, ... , xn) = f(x1, x2, ... , xm, xm+1, ... , xn) =
V x1s1&x2s2&...&xmsm& f(s1, s2, ... sm, xm+1, ... , xn), (4.1)
m
n, где дизъюнкция берется по всем наборам (s1, s2, ... , sm) (их 2m).
Например, для m = 2, n = 4 разложение (4.1) включает в себя четыре (2m = 22 =4) конъюнкции и имеет вид:
f(x1, x2, x3, x4) = x
&x
&f(0, 0, x3, x4) V x &x
&f(0, 1, x3, x4) V x
& x &f(1, 0, x3, x4) V x & x &f(1, 1, x3, x4) = x1&x2&f(0, 0, x3, x4) V x1&x2&f(0, 1, x3, x4) V x1&x2&f(1, 0, x3, x4) V x1&x2&f(1, 1, x3, x4).
Доказательство теоремы 4.5.
Теорема будет доказана, если показать, что равенство (4.1) выполняется для произвольного набора переменных (y1, y2, ... , ym, ym+1, ... , yn) .
Подставим этот произвольный набор переменных в левую и правую части равенства (4.1).
В левой части получим f (y1, y2, ... , yn) .
Т. к. ys = 1 только, когда y = s, то среди 2m конъюнкций y1s1&y2s2&...&ymsm в правой части (4.1) только одна обратится в 1 – та, в которой y1 = s1,…, ym = sm. Все остальные конъюнкции равны 0. Поэтому в правой части (4.1) получим:
y1y1&y2y2&...&ymym&f(y1, y2, ... , ym, ym+1, ... , yn) = f(y1, y2, ... , yn) .
Теорема 4.5 доказана.
Теорема 4.6 (о представлении булевой функции формулой в СДНФ),
Всякая булева функция f(x1, x2, ... , xn), не равная тождественно 0, может быть представлена формулой в СДНФ, которая определяется однозначно с точностью до перестановки дизъюнктивных членов.
Доказательство.
При m = n получим важное следствие теоремы 4.5:
f(x1, x2, ... , xn) = V x1s1&x2s2&...&xnsn, (4.2)
f(s1, s2, ... , sn) = 1
где дизъюнкция берется по всем наборам (s1, s2, ... , sn), на которых f = 1.
Очевидно, что разложение (4.2) есть не что иное, как СДНФ формулы f, которая содержит столько конъюнкций, сколько единиц в таблице значений f. Следовательно, СДНФ для всякой булевой функции единственна с точностью до перестановки ее дизъюнктивных членов.
Очевидно также, что для булевой функции f(x1, x2, ... , xn), тождественно равной 0, разложение (2) не существует.
В силу изложенного для получения формулы булевой функции f(x1, x2, ... , xn) в СДНФ можно воспользоваться следующим алгоритмом.
Алгоритм 4.3. (Алгоритм представления булевой функции, заданной таблицей, формулой в СДНФ).
Шаг 1. Выбираем в таблице все наборы переменных s1, s2, ... , sn, для которых значение f равно 1, т. е. f (s1, s2, ... , sn) = 1.
Шаг 2. Для каждого такого набора (строки таблицы) составляем конъюнкцию x1s1&x2s2&...&xnsn, где xisi = xi, если si = 1 и xisi =xi, если si = 0, i = 1, 2, ... ,n.
Шаг 3. Составляем дизъюнкцию всех полученных конъюнкций. В результате получится формула данной функции в СДНФ.
Пример 4.15.
Найдем формулу в СДНФ для функции f(x1, x2, x3), заданной таблицей 4.4.
1. Выберем в таблице строки, где f(x1, x2, x3) =1. Это 4-ая, 5-ая. 6-ая и 8-ая строки.
2. Для каждой выбранной строки составляем конъюнкции по правилу, указанному в шаге 2. Получим соответственно для четырех выбранных строк:
x10&x21&x31 = x1 &x2&x3.
x11&x20&x30 = x1&x2&x3.
x11&x20&x31 = x1&x2&x3 .
x11&x21&x31 = x1&x2&x3 .
3. Составляем дизъюнкцию всех полученных конъюнкций и находим СДНФ:
f(x1, x2, x3) = x1&x2&x3V x1&x2&x3 V x1&x2&x3 V x1&x2&x3.
Убеждаемся, что это выражение совпадает с полученным ранее в примере 4.13 представлением нашей формулы в СДНФ.
Замечание. Если булева функция задана формулой в СДНФ, то, применяя алгоритм 4.3 в обратной последовательности, легко можем получить таблицу значений этой функции.
Теорема 4.7 (о представлении булевой функции формулой в СКНФ),
Всякая булева функция f(x1, x2, ... , xn), не равная тождественно 1, может быть представлена формулой в СКНФ, которая определяется однозначно с точностью до перестановки дизъюнктивных членов.
Доказательство.
Рассмотрим функцию f(x1, x2, ... , xn). В соответствии с теоремой 4.6, если она не равна тождественно 0, существует ее формула в СДНФ. Обозначим эту формулу F1. Очевидно, условие, что функция f(x1, x2, ... , xn) не равна тождественно 0, равносильно условию, что функция f(x1, x2, ... , xn) не равна тождественно 1. Кроме того, по закону де Моргана формула F2 F1 находится в СКНФ (отрицание конъюнкции есть дизъюнкция отрицаний). По закону двойного отрицания
F2 F1 f(x1, x2, ... , xn) f(x1, x2, ... , xn),
что и доказывает теорему.
Для получения формулы булевой функции f(x1, x2, ... , xn) в СКНФ следует воспользоваться следующим алгоритмом.
Алгоритм 4.4. (Алгоритм представления булевой функции, заданной таблицей, формулой в СКНФ)
Шаг 1. Выбираем в таблице все наборы переменных s1, s2, ... , sn, для которых значение f (s1, s2, ... , sn) = 0.
Шаг 2. Для каждого такого набора (строки таблицы) составляем дизъюнкцию
x1 s1Vx2s2V...Vxnsn, где xi si = xi, если si = 0 и xi si = xi, если si = 1, i = 1, 2, ... , n.
Шаг 3. Составляем конъюнкцию всех полученных дизъюнкций. В результате получится СКНФ.
Пример 4.16.
Найдем формулу в СКНФ для функции f(x1, x2, x3), заданной таблицей 4.4.
1. Выберем в таблице строки, где f(x1, x2, x3) = 0. Это 1-ая, 2-ая и 3-я и 7-ая строки.
2. Для каждой выбранной строки составляем дизъюнкции по правилу, указанному в шаге 2. Получим соответственно для трех выбранных строк:
x11Vx21Vx31 = x1Vx2Vx3.
x11Vx21Vx30x1Vx2Vx3.
x11Vx20Vx31 = x1Vx2Vx3.
x10Vx20Vx31 = x1Vx2V x3.
3. Составляем конъюнкцию всех полученных дизъюнкций и находим СКНФ:
f(x1, x2, x3) = x1Vx2Vx3)&(x1Vx2Vx3)&(x1Vx2Vx3)&(x1Vx2Vx3).
Это выражение совпадает с полученным ранее в примере 4.14 представлением нашей формулы в СКНФ.
Замечание. Т. к. всего строк в таблице функции 2n, то, если число дизъюнктивных членов в СДНФ равно p, а число конъюнктивных членов в СКНФ равно q, то p+q=2n.
Так, для функции, рассмотренной в примерах 4.15 и 4.16, n = 3, p = 4, q = 4, p + q = 8 = 23.
4.8. Минимизация формул булевых функций в классе дизъюнктивных
нормальных форм
Как было установлено выше, произвольная булева функция может быть представлена формулой в ДНФ и КНФ, причем такое представление неоднозначно. Равносильными преобразованиями можно получить формулу, содержащую меньшее число вхождений переменных. Например, две различные формулы: f1(x1, x2) = x1V x1&x2 V x2 и f2(x1, x2) = x1 V x2 равносильны, так как в силу 2-го закона поглощения (равносильность 6б из раздела 4.3) x1 V x1&x2 x1.
Но в формуле f1(x1, x2) содержится четыре вхождений переменных, а в формуле f2(x1, x2) – два.
Определение 4.10. ДНФ называется минимальной, если она содержит наименьшее общее число вхождений переменных среди всех равносильных ей ДНФ.
Определение 4.11. Импликантом булевой функции f(x1, x2, ... , xn) называется элементарная конъюнкция С, не равная тождественно 0, такая что C V f 
f. Отметим, что любая конъюнкция любой ДНФ в силу закона идемпотентности (равносильность 5б) является импликантом этой функции.
Определение 4.12. Импликант C функции f называется простым импликантом, если после отбрасывания любой переменной из C получается элементарная конъюнкция, не являющаяся импликантом функции f.
Пример 4.17.
Для функции x&yVx&zVx&y&z x&(yVz) конъюнкции x&y и x&z – простые импликанты, а x&y&z – импликант, но не простой.
Определение 4.13. Дизъюнкция всех простых импликантов булевой функции f называется сокращенной ДНФ функции f.
Для нахождения сокращенной ДНФ используется следующий алгоритм, в основе которого лежит метод Квайна.
Алгоритм 4.5. (Алгоритм Квайна построения сокращенной ДНФ).
Шаг 1. Находим для данной булевой функции f ее формулу F, находящуюся в СДНФ.
Шаг 2. Находим все простые импликанты функции f. Для этого все элементарные конъюнкции формулы F попарно сравниваем между собой. Если две элементарные конъюнкции таковы, что они имеют вид C&xi и C&xi, то выписываем конъюнкцию С. Это является следствием 1-го закона расщепления (склеивания) (равносильность 7а). Конъюнкция С содержит n - 1 вхождение переменных. Элементарные конъюнкции, для которых произошло склеивание, помечаем. После построения всех конъюнкций, включающих n - 1 вхождение переменных, вновь сравниваем их попарно, производим, если возможно, склеивание, выписываем полученные конъюнкции из n - 2 членов, помечаем склеивающиеся конъюнкции из n - 1 членов и т. д. Процесс заканчивается, когда дальнейшее склеивание невозможно. Все непомеченные элементарные конъюнкции являются простыми импликантами. Их дизъюнкция даст нам формулу F1, равносильную F, находящуюся в ДНФ и состоящую из простых импликантов, т.е. сокращенную ДНФ.
Пример 4.18.
Найдем сокращенную ДНФ функции из примера 4.4:
f(x1, x2, x3) = (x2
x3) ~(x1Vx2).
1. Шаг 1 был выполнен ранее (см. примеры 4.13, 4.15). СДНФ формулы f(x1, x2, x3) является формула
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
