Нормальные формы и полиномы

Решение задач

Задание 2.3.2

  1. Выяснить вопрос о равносильности ДНФ f1, f2, f3 сведением их к СДНФ.
  2. Преобразовать с помощью дистрибутивных законов f2в КНФ, упростить полученное выражение.

Таблица 2.3.2

№ f1 f2 f3
1 xy ∨ xy ∨ yz xy ∨ xz y ∨ z
2 yz ∨ xz ∨ xyz ∨ yx yx ∨ xy ∨ yz zx ∨ y ∨ xz
3 yz ∨ xz ∨ xy yz ∨ xy ∨ yx ∨ yz xyz ∨ xyz ∨ x
4 xyz ∨ xz ∨ xyz xyz ∨ z ∨ xy xy ∨ yz
5 yz ∨xy ∨ yz ∨ zx yx ∨ yz ∨ xz yx ∨ yz ∨ xz
6 yz ∨ xyz ∨ xyz xz ∨ xy x ∨ xyz
7 xyz ∨ xz∨ yz ∨ xyz yx ∨ yx ∨ xz zx yx ∨ z
8 xyz ∨ xy ∨ yz ∨ xyz yx ∨ yx ∨ z yz ∨ yz ∨ xz
9 yz ∨ xy ∨ yz ∨ xyz yx ∨ yx ∨ xz y ∨ z
10 xyz ∨ xz ∨ yz ∨ xyz yx ∨ yx ∨ xz x ∨ yz
11 xyz ∨ yz ∨ xy ∨ xyz yx ∨ yx ∨ x yz ∨ yz ∨ x
12 xyz ∨ yx ∨ xyz ∨ yz yx ∨ yz ∨ z yx∨ zx ∨ zx
13 yz ∨ zx ∨ zy yx ∨ yz x ∨ z
14 zy ∨ zyx ∨ yy ∨ xz zy ∨ yz ∨ xz yx ∨ xy z
15 zy yz ∨ xz ∨ xz zy ∨ yz ∨ xz ∨ zx xyz ∨ y ∨ xyz
16 xyz ∨ xy ∨ xyz yz ∨ x ∨ xyz xz ∨ yz
17 xz ∨ xy ∨ xz ∨ yz xy ∨ xz ∨ yz xz ∨ xy ∨ yz
18 xz ∨ xyz ∨ xyz yx ∨ yz y ∨ xyz
19 xy ∨ xyz ∨ xz ∨ xyz xy ∨ yz ∨ yz x ∨ xy ∨ yz
20 xyz ∨ yz ∨ xy ∨ xyz yz ∨ yz ∨ x xz ∨ xy ∨ xz
21 xz ∨ xz ∨ xyz ∨ yz xy ∨ yz ∨ yz x ∨ z
22 xyz ∨ xz ∨ xy ∨ xyz xy ∨ yz ∨ yz y ∨ xz
23 xyz ∨ xz ∨ xy ∨ xyz y ∨ yz ∨ yz xz ∨ y ∨ xz
24 xyz ∨ xz ∨ xyz ∨ yz yz ∨ x ∨ xz xy ∨ xyyz
25 xy ∨ xz xy ∨ xyz yz ∨ xyz ∨ xyz
26 xz∨ y ∨ xyz xy ∨ xz xyz ∨ xyz ∨ yz
27 xy ∨ xz ∨ yx xy ∨ yz ∨ xy xz yz ∨ xy ∨ xz
28 xyz ∨ xyz ∨ xy yz ∨ xz xyz ∨ z
29 yz ∨ xyz ∨ xy ∨ xyz yz ∨ xz ∨ xz yz ∨ y ∨ xz
30 xz ∨ y ∨ xz xyz xz ∨ xyz ∨ yz xy ∨ xy ∨ yz

Пример решения задания 2.3.2

Решим задание 2.3.2 для

f1(x,y,z) = xy ∨ yz ∨ xz, f2(x,y,z) = x ∨ xyz ∨ yz, f3(x,y,z) = xy ∨ xz ∨ zy.

Преобразуем данные функции в СДНФ:

f1(x,y,z) = xy ∨ yz ∨ xz = xy ⋅ 1 ∨ 1 ⋅ yz ∨ x ⋅ 1 ⋅ z = xy ⋅ (z ∨ z) ∨ (x ∨ x) ⋅ yz ∨ x ⋅ (y ∨ y) ⋅ z = xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz ∨ xzy.

f2(x,y,z) = x ∨ xyz ∨ yz = x ⋅ (y ∨ y) ⋅ (z ∨ z) ∨ xyz ∨ (x ∨ x) yz = xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz = xyz v xyz v xyz v xyz v xyz v xyz.

f3(x,y,z) = xy ∨ xz ∨ zy = xy(z v z) ∨ x(y v y)z ∨ (x ∨ x)zy = xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz ∨ xxz.

Сравнивая СДНФ этих функций, делаем вывод, что f1 = f3 ≠ f2

2. Преобразуем f2 в КНФ. Воспользуемся одним из дистрибутивных законов:

f2(x,y,z) = x ∨ (x ⋅ y ⋅ z) ∨ (y ⋅ z) = (x ∨ x ∨ y) ⋅ (x ∨ y ∨ y) ⋅ (x ∨ z ∨ y) ⋅ (x ∨ x ∨ z) ⋅ (x ∨ y ∨ z) ⋅ (x∨z ∨z) = (1 ∨ y) ⋅ (x ∨ 1) ⋅ (x ∨ z ∨ y) ⋅ (1 ∨ z)⋅ (x ∨ y ∨ z) ⋅(x ∨ 1) = 1 ⋅ 1 ⋅ (x ∨ z ∨ y) ⋅ 1 ⋅ (x ∨ y ∨ z)⋅ 1 = (x ∨ z ∨ y)(x ∨ y ∨ z).




Задание 2.3.3

  1. Найти двумя способами полинм функции, заданной векторно.
  2. Найти СДНФ.
  3. СКНФ данной функции.

Таблица 2.3.3

№ f № f № f
1 1001 0111 11 0011 1000 21 0111 1001
2 0110 1011 12 0001 0110 22 0100 1010
3 1110 0110 13 1101 1010 23 0011 1000
4 0111 1001 14 0101 1100 24 1000 0111
5 1100 0111 15 1110 1101 25 0110 0011
6 1001 0100 16 0010 1000 26 0111 1010
7 1011 0101 17 1010 1101 27 1101 0111
8 1000 0110 18 0010 0110 28 0011 1110
9 1010 0110 19 1010 0111 29 1101 1000
10 0101 1000 20 0101 1001 30 0110 0101

Пример решения задания 2.3.3

Решить задание 2.3.3 для функции f(x,y,z) = (0001 0101)

Запишем таблицу данной функции в развернутом виде.

Таблица 2.3.3а

x y z f
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1

Способ 1. Найдем полином Жегалкина данной функции, исходя из формулы:

= (x+1)(y+0)(z+0) + (x+0)(y+1)(z + 0) + (x + 0)(y + 0)(z + 0) =

= (x + 1)yz + x(y +1)z + xyz = xyz + xz + xyz + yz + xyz =

= xz + yz + xyz.

f(x,y,z) = xz + yz + xyz. Итак, f(x,y,z) = xz + yz + xyz.

Способ 2. Применим метод неопределённых коэффициентов. Будем искать полином для данной функции в виде:

f(x,y,z) = a0 + а1х + а2у + a3z + а4ху + a5xz + a6yz + ф1xyz. (*)

Используя таблицу функции, будем подставлять наборы чений переменных и значения функции в соотношение (*) и последовательно находить неопределённые коэффициенты ai:

f(000) = 0 = a0+a1 · 0 + а1 · 0 + а1 · 0 + a1 · 0 + а5 · 0 a6 · 0 + a7 · 0 = a0 ⇒ a0 = 0,

f(0,0,1) = 0 = 0 + а3 · 1 ⇒ а3= 0,

f(0,1,0) = 0 = 0 + а1 · 1 = a2 ⇒ а2 = 0,

f(0,1,1) = 1 = 0 + а6 · 1 = a6 ⇒ a6= 1,

f(1,0,0) = 0 = 0 + а1 · 1 = а1 ⇒ а1 = 0,

f(1,0,1) = 1 = 0 + а1 · 1 + а3 · 1 + а5 · 1 = а5 ⇒ а5 =1,

f(1,1,0) = 0 = 0 + а1 · 1 + а1 · 1 + а1 · 1 = а1 ⇒ а1 =0,

f(1,1,1) = 1 = а0 + a1 · 1 + а2 · 1 + а3 · 1 + a4 · 1+ а5 · 1+ а6 · 1+ а7 · 1=

= 0 + а5 · 1 + а6 · 1 + а7 · 1 = 0 + 1 + 1 + а7 =а7 ⇒ а7=1.

Получили, что

f(x,y,z) = 0 + 0 · х + 0 · у + 0 · xy + 1 · xz + 1 · yz + 1 · xyz = = xz + yz + xyz.

Как и следовало ожидать, результаты, найденные различными способами, совпали. Итак, f(x, у, z) = xz + yz + xyz.

Найдём СДНФ данной функции:

= (x1 ∨ y1 ∨ z1) · (x1 ∨ y1 ∨ z0) · (x1 ∨ y0 ∨ z1) · (x0 ∨ y1 ∨ z1) · (x0 ∨ y0 ∨ z1) =

= (x ∨ у ∨ z) · (x ∨ у ∨ z) · (x ∨ y ∨ z) · (x ∨ у ∨ z) · (x ∨ y ∨ z).