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

Решение.

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

xyz	x ~ z	x y	y z	(x y) ~ (y z)	(x~ z)|((x y) ~ (y z)

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

.

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

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

Таким образом, СКНФ для данной функции имеет вид:

.

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

в) Составим полином Жегалкина по таблице истинности. Напишем его сначала с неопределёнными коэффициентами: f(x, y, z) = a₀ + a₁x+a₂y+a₃ z+a₄xy+a₅xz+a₆ yz+a₇xyz.

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

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

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

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

x = 0, y = 1, z = 1: a₂ + a₃ + a₆ = 1, a₆ = 0;

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

x = 1, y = 0, z = 1: a₁ + a₃ + a₅ = 0, a₅ = 0;

x = 1, y = 1, z = 0: a₁+ a₂ + a₄ = 1, a₄ = 1;

x = 1, y = 1, z = 1: a₀ + a₁ + a₂ + a₃ + a₄ + a₅ +a₆ + a₇ = 0.

Так как a₀ =a₂ =a₄ =a₅ = a₆ = 0, то a₁ +a₃ +a₇ = 0, откуда a₇ = 0, и полином Жегалкина для данной функции имеет вид: f(x, y, z) = x+ z (таким образом, для данной функции у является фиктивной переменной).

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

xy z	00 01 11 10
0	0 0 1 1 1 1 0 0

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

5.2. Требуется по карте Карно для функции 4-х переменных составить сокращённую ДНФ.

х1, х2 х3 , х4	00 01 11 10
00	1 1 0 1 0 1 0 0 0 0 1 0 1 1 0 1

Решение.

Надо иметь в виду, что карты Карно соединяются по кругу. Число единиц, которые мы можем объединять, равно 2, 4, 8, … (прямая, плоскость и т. д.). Получаем всего 4 объединения, т. е. 4 конъюнкции в ДНФ:

.

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