2.4.5. Минимизация по картам Карно.

f(x₁,x₂,x₃,x₄) = (0011 1101 0010 1100).

Таблица истинности (табл. 2.8). Карта Карно (рис. 2.2).

СокрДНФ: f(x,y,z)=x₂⌐x₃V⌐x₁x₃x₄V⌐x₁x₂x₄V⌐x₁⌐x₂x₃V⌐x₂x₃x⌐x₄.

Матрица Квайна (табл. 2.9).

МДНФ: f(x,y,z)=x₂⌐x₃V⌐x₁x₃x₄V⌐x₂x₃x⌐x₄.

Таблица 2.8

№	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
x1	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
x2	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
x3	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
x4	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
F	0	0	1	1	1	1	0	1	0	0	1	0	1	1	0	0

Рис. 2.2

Таблица 2.9

	*10*	0*11	01*1	001*	*010
0010				+	(+)
0011		(+)		+
0100	(+)
0101	(+)		+
0111		(+)	+
1010					(+)
1100	(+)
1101	(+)

2.4.6. Полнота системы булевых функций.

J = {xV⌐y, ⌐x↔y}.

F₁ = xV⌐y,

F₂ = ⌐x↔y.

Таблица истинности (табл. 2.10).

Таблица 2.10

x	y	F1	F2
0	0	1	0
0	1	0	1
1	0	1	1
1	1	1	0

Классы Поста:

F₁:

P₀: F₁(0,0) = 1, => P0 = 0,

P₁: F₁(1,1) = 1, => P₁ = 1,

P_S: F₁(x,y) = ⌐F₁(⌐x,⌐y),

F₁(0,0) =1 <> ⌐F₁(⌐0,⌐0) = ⌐ F₁(1,1) = ⌐1 = 0,

=> P_S = 0,

P_M: F₁(0,0) = 1, F₁(0,1)=0, => P_M = 0,

P_L: F₁(x,y) = xV⌐y = xV(1+y) = (xV1)+(xVy) = 1+(xVy) = 1+x+y+xy, => P_L = 0.

F₂:

P₀: F₂(0,0) = 0, => P₀ = 1,

P₁: F₁(1,1) = 0, => P₁ = 0,

P_S: F₁(x,y) = ⌐F₁(⌐x,⌐y),

F₁(0,0) = 0 <> ⌐F₁(⌐0,⌐0) = ⌐ F₁(1,1) = ⌐0 = 1,

=> P_S = 0,

P_M: F₁(1,0) = 1, F₁(1,1)=0, => P_M = 0,

P_L: F₁(x,y) = ⌐x↔y = ⌐xyVx⌐y = ⌐xy+x⌐y+⌐xyx⌐y = ⌐xy+x⌐y =

= (1+x)y+x(1+y) = y+xy+x+xy = x+y, => P_L = 1.

По теореме Поста (табл. 2.11) система J = {xV⌐y, ⌐x↔y} является базисом, т.к. для каждого класса Поста нашлась функция из системы J, не принадлежащая этому классу .

Таблица 2.11

	P0	P1	PS	PM	PL
F1	–	+	–	–	–
F2	+	–	–	–	+

Список литературы

1. Новиков Ф.А., Дискретная математика для программистов. Учебник для ВУЗов. 2-е изд. // СПб: Питер, 2005. – 364 с.

2. Судоплатов С.В., Овчинникова Е.В., Дискретная математика. Учебник. 2-е изд. // Москва – Новосибирск: ИНФРА-М – НГТУ, 2005. – 256 с.