Материал: Рабкин Е. Л., Фарфоровская Ю. Б. Дискретная математика. Булевы фукции и теория графов

Пример 1. Привести выражение к ДНФ, а затем сократить ее (если это возможно).

Решение. “Понижаем” отрицания по правилу де Моргана. Получаем

По правилу Блейка (имеются

дизъюнктные слагаемые, содержащие у и ) к последнему выражению можно добавить слагаемое x z , которое поглотит второе слагаемое в L.

Ответ: L = xy xz

В задачах 1–10, б) надо просто применять правило Блейка, а затем уже правило поглощения

Теорию, применяемую к задачам 11–20, подробно обсуждали в разд. 3, 6, поэтому ограничимся решением примеров.

Пример 2а. Дана ДНФ . Требуется для этой функции найти полином Жегалкина и перейти от ДНФ к КНФ, а затем и к СКНФ. Сначала найдем полином Жегалкина (вторым способом). Для этого ставим двойное отрицание и по правилам де Моргана “убираем” дизъюнкцию, потом “убираем”

отрицания по правилу. После этого раскрываем скобки, учитывая при этом, что четное число слагаемых (по модулю 2) равно 0, а нечетное – одному такому слагаемому. Тогда

((x+1)(y+1)+1)(xy(z+1)+1)+1=(xy+x+y+1+1)(xyz+xy+1)+1=

=(xy+x+y)(xyz+xy+1)+1= xyz + xyz + xyz + xy+xy+ xy+ xy +

+x+ y+1 = xyz+x+y+1.

Последнее выражение и является полиномом Жегалкина.

Для того чтобы перейти к КНФ для выражения L (в соответствии с разд. 3) ставим над L два отрицания и, оставляя временно верхнее отрицание без изменения, приводим оставшееся выражение к ДНФ. Затем по правилу де Моргана получаем КНФ. Таким образом, можем получить

.

Далее по правилу Блейка можем из последнего выражения исключить yz, тогда получим:

. Это и есть КНФ.

Чтобы из последнего выражения получить СКНФ, нужно в первой и второй дизъюнкции добавить

, а в третьей – Затем воспользуемся распределительным законом:

Последнее выражение и есть СКНФ.

Пример 2,б. Пусть имеется выражение . Требуется записать L в виде ДНФ, а затем перейти к СДНФ.

36

Ясно, что ДНФ можно получить простым раскрытием скобок. В обеих скобках есть , которое поглощает слагаемые, содержащие , поэтому . Это и есть ДНФ. Для того чтобы

получить СДНФ, умножаем на , а умножаем на (y и раскрываем скобки. Тогда

.

С самого начала надо позаботиться о правильном порядке переменных, что требуется для СДНФ, но последнее выражение еще не является СДНФ, так как содержит два одинаковых слагаемых. После уничтожения одного из них получим окончательный ответ:

Разберем пример решения задач типа 21–30.

Пример 3. Пусть требуется для функции

f(x, y, z) = (x ~ z) | ((x y) ~ (y z)):

а) составить таблицу истинности;

б) написать для неё СДНФ или СКНФ (если это возможно);

в) сократить СДНФ по карте Карно;

г) найти по таблице истинности полином Жегалкина.

Решение:

а) в таблицу истинности данной функции полезно включить таблицы истинности промежуточных функций:

б) составить СДНФ и СКНФ по полученной таблице. В соответствии с теорией разд. 4 СДНФ составляется по единицам таблицы истинности, причем если f(x, y, z) = 1, то если х = 0, в соответствующей

37

конъюнкции СДНФ берется , а если х = 1 в СДНФ берется х. Аналогично поступают и с другими переменными, поэтому СДНФ для данной функции имеет вид:

.

СКНФ составляется по нулям таблицы истинности, т. е. если

f(x, y, z) = 0 и х = 0, то в соответствующей дизъюнкции берётся х, а если х = 1, то . Таким образом, СКНФ для данной функции имеет вид:

.

Заметим, что по определению СДНФ и СКНФ, переменные (в каждой конъюнкции и дизъюнкции соответственно) должны следовать в одинаковом порядке;

в) составим полином Жегалкина по таблице истинности. Напишем его сначала с неопределёнными коэффициентами:

f(x, y, z) = 0 + 1x+ 2y+ 3 z+ 4xy+ 5xz+ 6 yz+ 7xyz.

Подставим в него по очереди все 8 наборов переменных и найдём коэффициенты полинома Жегалкина.

x = 0, y = 0, z = 0: 0 = 0;

x = 0, y = 0, z = 1: 3 = 1;

x = 0, y = 1, z = 0: 2 = 0;

x = 0, y = 1, z = 1: 2 + 3 + 6 = 1, 6 = 0;

x = 1, y = 0, z = 0: 1 = 1;

x = 1, y = 0, z = 1: 1 + 3 + 5 = 0, 5 = 0;

x = 1, y = 1, z = 0: 1+ 2 + 4 = 1, 4 = 0;

x = 1, y = 1, z = 1: 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 =0.

Так как 0 = 2 = 4 = 5 = 6 = 0, тогда 1 + 3 + 7 = 0, откуда 7 = 0, и полином Жегалкина для данной функции имеет вид: f(x, y, z) = x+ z (для данной функции у является фиктивной переменной);

г) составим теперь для данной функции карту Карно и сократим её. Сначала составим таблицу:

Откуда f(x, y, z) =. Опять оказалось, что у – фиктивная переменная.

В задачах 31–40 требуется по карте Карно для функции 4 переменных составить сокращённую ДНФ. Надо иметь в виду, что карты Карно соединяются по кругу. Число единиц, которые можно объединять, равно 2, 4, 8, … (прямая, плоскость и т. д.)

38

Пример 4.

Получаем всего 4 объединения, т. е. 4 конъюнкции в ДНФ: f = (x1,x2, x3,x4)

=

Заметим, что при правильно составленном объединении единиц правило Блейка может привести только к ДНФ с тем же числом символов переменных (в нашем примере их 11).

В задачах 41–50 требуется в данных наборах из 4 или 5 функций найти базисы и полные наборы функций (полные наборы – это наборы функций, содержащих базис).

Пример 5. Пусть имеется набор функций: 1) f1(x, y, z) = (x y (y~ z),

2) f2(x, y) = x + y x, 3) f3(x, y, z) = x ~ (y z), 4) f4(x, y) = x + 5) f5 (x, y, z) = = x y z

Составляем таблицу истинности для каждой из этих 5 функций (для f2 и f4 таблицу можно составить отдельно).

Отсюда очевидно, что f1(x, y, z) T0 (принадлежит Т0) и f1 T1, f1 M, S (т. е. не принадлежит Т1 , М, S), аналогично f3 T0 , M, S и f3 Т1. Функция f5 Т1 и f5 Т0, М, S. Осталось проверить линейность этих

функций.

f3 = x ~ (y z) = = x + yz + 1 – нелинейна;

f5 = x y z = = (x y + 1) z + 1 = x y z + z + 1 – нелинейна.

39

Для f1 требуется проверка нелинейности. Составим полином Жегалкина для f1:

P = 0 + 1 x + 2 y + 3 z + 4 x y + 5 x z + 6 y z + 7 x y z. Находим последовательно 1 : 0 = 0, 3 = 1, 2 = 1, 6 = 0, 1 = 0, 5 = 0, 4 = 1; значит, функция f1 нелинейна, что, впрочем,

следует и из того, что f1 в таблице истинности содержит нечетное число единиц (равное 3).

Для f2 и f4 составляем свои таблицы истинности.

Отсюда следует, что f2 T0, f2 T1 f2 M, S; является полиномом Жегалкина f2=x + xy; f4 = x + y + 1

и, значит, f4 L, также f4 T1 , но

f4 M, S. Все эти сведения сведём в таблицу Поста.

Таким образом, базисами являются: f1 и f3; f1 и f4; f2 и f4; f1 и f5, f2 и f5. Полными наборами будут любые наборы, содержащие какой-нибудь базис.

В задачах 51–60 требуется по данному ориентированному графу составить структурную матрицу, а по ней (методами булевой алгебры) найти все пути из вершины i в вершину j, а затем (отрицанием этих путей) найти все сечения между двумя указанными вершинами. Пусть дан ориентированный граф (рис. 12) , причем ребра a,b,h являются ориентированными (их направление указано стрелками), а остальные ребра не ориентированы. Требуется методами булевой алгебры найти пути и сечения между вершинами 2 и 4.

40