2.11 Виписати всі функції, які покривають задану.

(¬X₁*¬X₂*¬X₃*¬X₄)

(¬X₁*¬X₂*¬X₃*X₄)

(¬X₁*¬X₂*X₃*¬X₄)

(¬X₁*¬X₂*X₃*X₄)

(¬X₁*X₂*X₃*¬X₄)

(¬X₁*X₂*X₃*X₄)

(X₁*¬X₂*¬X₃*X₄)

(X₁*¬X₂*X₃*X₄)

(X₁*X₂*¬X₃*¬X₄)

(X₁*X₂*X₃*X₄)

2.12 Записати в аналітичному виді ДДНФ заданої функції і мінімізувати її методом Квайна (безпосередньо по імплікантній матриці і з допомогою метода Петрика для пошуку тупикових ДНФ), методом Квайна – Мак-Класкі, а також за допомогою діаграм Вейча (карт Карно).

ДДНФ:

F(X₁,X₂,X₃,X₄)=(¬X₁*¬X₂*¬X₃*¬X₄)v(¬X₁*¬X₂*¬X₃*X₄)v(¬X₁*¬X₂*X₃*¬X₄)v

v(¬X₁*¬X₂*X₃*X₄)v(¬X₁*X₂*X₃*¬X₄)v(¬X₁*X₂*X₃*X₄)v(X₁*¬X₂*¬X₃*X₄)v

v(X₁*¬X₂*X₃*X₄)v(X₁*X₂*¬X₃*¬X₄)v(X₁*X₂*X₃*X₄).

Мінімізація методом:

• Квайна:

Функція у досконалій диз'юнктивній нормальній формі (ДДНФ) має вигляд:

F(X₁,X₂,X₃,X₄)=(¬X₁*¬X₂*¬X₃*¬X₄)v(¬X₁*¬X₂*¬X₃*X₄)v(¬X₁*¬X₂*X₃*¬X₄)v

v(¬X₁*¬X₂*X₃*X₄)v(¬X₁*X₂*X₃*¬X₄)v(¬X₁*X₂*X₃*X₄)v(X₁*¬X₂*¬X₃*X₄)v

v(X₁*¬X₂*X₃*X₄)v(X₁*X₂*¬X₃*¬X₄)v(X₁*X₂*X₃*X₄).

Виконавши попарне склеювання конституент одиниці, одержуємо множину імплікант 3-го рангу:

1-2: ¬X₁*¬X₂*¬X₃

1-3: ¬X₁*¬X₂*¬X₄

2-4: ¬X₁*¬X₂*X₄

2-7: ¬X₂*X₃¬*X₄

3-4: ¬X₁*¬X₂*X₃

3-5: ¬X₁*X₃*¬X₄

4-6: ¬X₁*X₃*X₄

4-8: ¬X₂*X₃*X₄

5-6: ¬X₁*X₂*X₃

6-10: X₂*X₃*X₄

7-8: X₁*¬X₂*X₄

8-10: X₁*X₃*X₄

F(X₁,X₂,X₃,X₄)=(¬X₁*¬X₂*¬X₃)v(¬X₁*¬X₂*¬X₄)v(¬X₁*¬X₂*X₄)v(¬X₂*X₃¬*X₄)v v(¬X₁*¬X₂*X₃)v(¬X₁*X₃*¬X₄)v(¬X₁*X₃*X₄)v(¬X₂*X₃*X₄)v(¬X₁*X₂*X₃)v

v(X₂*X₃* *X₄)v(X₁*¬X₂*X₄)v(X₁*X₃*X₄).

Таблиця покриттів:

	¬x1*¬x2*¬x3*¬x4	¬x1*¬x2*¬x3*x4	¬x1*¬x2*x3*¬x4	¬x1*¬x2*x3*x4	¬x1*x2*x3*¬x4	¬x1*x2*x3*x4	x1*¬x2*¬x3*x4	x1*¬x2*x3*x4	x1*x2*¬x3*¬x4	x1*x2*x3*x4
¬x1*¬x2*¬x3	1	1
¬x1*¬x2*¬x4	1		1
¬x1*¬x2*x4		1		1
¬x2*x3*¬x4			1	1
¬x1*¬x2*x3			1	1
¬x1*x3*¬x4			1		1
¬x1*x3*x4						1
¬x1*x2*x3					1	1
x2*x3*x4										1
x1*¬x2*x4							1	1
x1*x3*x4								1		1

Ядро F(X₁,X₂,X₃,X₄)= X₁*¬X₂*¬X₃*X₄.

Виконавши попарне склеювання конституент одиниці, одержуємо множину імплікант 2-го рангу:

1-5: ¬X₁*¬X₂

2-3: ¬X₁*¬X₂

3-11: ¬X₂*X₄

4-8: ¬X₂*X₄

5-9: ¬X₁*X₃

6-7: ¬X₁*X₃

7-12: X₃*X₄

8-10: X₃*X₄

Подальше склеювання імплікант неможливо. Тоді функцію можна записати у вигляді:

F(X₁,X₂,X₃,X₄)=(¬X₁*¬X₂)v(¬X₁*¬X₂)v(¬X₂*X₄)v(¬X₂*X₄)v(¬X₁*X₃)v(¬X₁*X₃)vv(X₃*X₄)v(X₃*X₄)=(¬X₁*¬X₂)v(¬X₂*X₄)v(¬X₁*X₃)v(X₃*X₄).

Таблиця покриттів:

	¬x1*¬x2*¬x3	¬x1*¬x2*¬x4	¬x1*¬x2*x4	¬x2*x3¬*x4	¬x1*¬x2*x3	¬x1*x3*¬x4	¬x1*x3*x4	¬x2*x3*x4	¬x1*x2*x3	x2*x3*x4	x1*¬x2*x4	x1*x3*x4
¬x1*¬x2	1	1	1		1
¬x2*x4			1								1
¬x1*x3				1	1	1	1
x3*x4							1	1		1		1

Ядро: F(X₁,X₂,X₃,X₄)=(¬x₁*¬x₂*¬x₃)v(¬x₁*¬x₂*¬x₄)v(¬x₂*x₃¬*x₄)v(¬x₁*x₃*¬x₄)v(¬x₂*x₃*x₄)v(x₂*x₃*x₄)v(x₁*¬x₂*x₄)v(x₁*x₃*x₄).

МДНФ:

F(X₁,X₂,X₃,X₄)=(¬X₁*¬X₂)v(¬X₂*X₄)v(¬X₁*X₃)v(X₃*X₄)v(X₁*X₂*¬X₃*¬X₄).

Тупікова ДНФ:

F(X₁,X₂,X₃,X₄)=(¬X₁*¬X₂)v(¬X₂*X₄)v(¬X₁*X₃)v(X₃*X₄)v(X₁*X₂*¬X₃*¬X₄).

• Квайна-Мак-Класкі:

K⁰= K¹= K²= Z=

	0000	0001	0010	0011	0110	1001	1100	0111	1011	1111
00xx	1	1	1	1
x0x1		1		1		1			1
0x1x			1	1	1			1
xx11				1				1	1	1

МДНФ:

F(X₁,X₂,X₃,X₄)=(¬x₁*¬x)v(¬x₂*x₄)v(¬x₁*x₃)v(x₃*x₄) v(X₁*X₂*¬X₃*¬X₄).

Тупікова ДНФ:

F(X₁,X₂,X₃,X₄)=(¬X₁*¬X₂)v(¬X₂*X₄)v(¬X₁*X₃)v(X₃*X₄)v(X₁*X₂*¬X₃*¬X₄).

• Діаграм Вейча:

X3X4
X1X2		00	01	11	10
	00	1	1	1	1
	01			1	1
	11	1		1
	10		1	1

F(X₁,X₂,X₃,X₄)=(¬x₁*¬x)v(¬x₂*x₄)v(¬x₁*x₃)v(x₃*x₄)v(X₁*X₂*¬X₃*¬X₄).

• Петрика:

	¬x1*¬x2*¬x3	¬x1*¬x2*¬x4	¬x1*¬x2*x4	¬x2*x3¬*x4	¬x1*¬x2*x3	¬x1*x3*¬x4	¬x1*x3*x4	¬x2*x3*x4	¬x1*x2*x3	x2*x3*x4	x1*¬x2*x4	x1*x3*x4
¬x1*¬x2	1	1	1		1
¬x2*x4			1								1
¬x1*x3				1	1	1	1
x3*x4							1	1		1		1

¬x₁*¬x=А

¬x₂*x₄=B

¬x₁*x₃=C

x₃*x₄=D

F=A*A*(AvB)*C*(AvC)*C*(CvD)*D*D*B*D=(A*(AVB))*B*(C*(AvC))*(D*(CVD))=A*B*C*D

Тупикова ДНФ містить чотири прості імпліканти: ¬x₁*¬x=А, ¬x₂*x₄=B, ¬x₁*x₃=C, x₃*x₄=D, і має вид:

F=(¬x₁*¬x)v(¬x₂*x₄)v(¬x₁*x₃)v(x₃*x₄)v(X₁*X₂*¬X₃*¬X₄).