РК2

Задание I Типа V

1. Построить карту Карно

Индекс	a	b	c	d	Значение F
0	0	0	0	0	1
1	0	0	0	1	1
2	0	0	1	0	0
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	1
6	0	1	1	0	0
7	0	1	1	1	1
8	1	0	0	0	0
9	1	0	0	1	0
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	0
13	1	1	0	1	0
14	1	1	1	0	1
15	1	1	1	1	1

2. Найти СкДНФ

Выпишем все склейки:

• $K_1=\bar{A}\bar{B}\bar{C}\bar{D}\cup \bar{A}\bar{B}\bar{C}D=\bar{A}\bar{B}\bar{C}$ Синяя
• $K_2=\bar{A}\bar{B}\bar{C}D\cup \bar{A}B\bar{C}D=\bar{A}\bar{C}D$ Фиолетовая
• $K_3=\bar{A}B\bar{C}D\cup \bar{A}BCD=\bar{A}\bar{B}\bar{D}$ Зелёная
• $K_4=\bar{A}BCD\cup ABCD=BCD$ Оранжевая
• $K_5=ABCD\cup ABC\bar{D}\cup A\bar{B}C\bar{D}\cup A\bar{B}CD=AC$ Красная

СкДНФ$=K_1\cup K_2\cup K_3\cup K_4\cup K_5=\bar{A}\bar{B}\bar{C}\cup \bar{A}\bar{C}D\cup \bar{A}\bar{B}\bar{D}\cup BCD\cup AC$

3. Найти ядро

Ядровая склейка - та, без которой остаётся хотя бы одна непокрытая другими склейками единица $=>$ найдём единицы, покрываемые только одной склейкой

a	b	c	d	Импликанты, покрывающие клетку
0	0	0	0	$K_1$
0	0	0	1	$K_1,K_2$
0	1	0	1	$K_2,K_3$
0	1	1	1	$K_3,K_4$
1	0	1	0	$K_5$
1	0	1	1	$K_4,K_5$
1	1	1	0	$K_5$
1	1	1	1	$K_5$

$\bar{A}\bar{B}\bar{C}\bar{D}$ покрыта только $K_1$
$ABC\bar{D},A\bar{B}C\bar{D},A\bar{B}CD$ покрыты только $K_5$
Следовательно:
Ядро: $K_1\cup K_5=\bar{A}\bar{B}\bar{C}\cup AC$

4. Найти вспомогательную функцию Патрика

Чтобы найти функцию Патрика, выпишем конъюнкцию дизъюнкций пересекающихся неядровых склеек:

$H=(K_2\cup K_3)\cap (K_3\cup K_4)=K_2{K}_3\cup K_2{K}_4\cup K_3\cup K_3{K}_4=K_2{K}_3\cup K_2{K}_4\cup K_3(1\cup K4)=$
$K_3(K_2\cup 1)\cup K_2{K}_4=K_3\cup K_2{K}_4$

5. Найти тупиковые ДНФ

$H=K_3\cup K_2{K}_4=>$ тупиковые ДНФ:
$K_1\cup K_5\cup K_3=\bar{A}\bar{B}\bar{C}\cup AC\cup \bar{A}BD$
$K_1\cup K_5\cup K_2\cup K_4=\bar{A}\bar{B}\bar{C}\cup AC\cup \bar{A}\bar{C}D\cup BCD$

6. Найти МДНФ

МДНФ - тупиковая ДНФ с наименьшим количеством литералов $=>$ определим количество литералов в полученных тупиковых ДНФ:
$\bar{A}\bar{B}\bar{C}\cup AC\cup \bar{A}BD$ - 8 литералов
$\bar{A}\bar{B}\bar{C}\cup AC\cup \bar{A}\bar{C}D\cup BCD$ - 11 литералов
$=>$ $\bar{A}\bar{B}\bar{C}\cup AC\cup \bar{A}BD$ - МДНФ

7. Найти КрДНФ

КрДНФ - тупиковая ДНФ, состоящая из наименьшего количества элементарных конъюнкций $=>$ определим количество элементарных конъюнкций в полученных тупиковых ДНФ: $\bar{A}\bar{B}\bar{C}\cup AC\cup \bar{A}BD$ - 3 конъюнкции
$\bar{A}\bar{B}\bar{C}\cup AC\cup \bar{A}\bar{C}D\cup BCD$ - 4 конъюнкции
$=>\bar{A}\bar{B}\bar{C}\cup AC\cup \bar{A}BD$ - КрДНФ

8. Отметить МДНФ на карте Карно

Задание II Типа V

1. Построить карту Карно

Индекс	a	b	c	d	Значение F
0	0	0	0	0	1
1	0	0	0	1	1
2	0	0	1	0	1
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	0
6	0	1	1	0	1
7	0	1	1	1	0
8	1	0	0	0	0
9	1	0	0	1	0
10	1	0	1	0	0
11	1	0	1	1	0
12	1	1	0	0	1
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	1

2. Найти СкДНФ

Выпишем все склейки:

• $K_1=\bar{A}\bar{B}\bar{C}\bar{D}\cup \bar{A}\bar{B}\bar{C}D=\bar{A}\bar{B}\bar{C}$ Синяя
• $K_2=\bar{A}\bar{B}\bar{C}\bar{D}\cup \bar{A}\bar{B}C\bar{D}=\bar{A}\bar{B}\bar{D}$ Оранжевая
• $K_3=\bar{A}\bar{B}C\bar{D}\cup \bar{A}BC\bar{D}=\bar{A}C\bar{D}$ Зелёная
• $K_4=\bar{A}BC\bar{D}\cup ABC\bar{D}=BC\bar{D}$ Фиолетовая
• $K_5=AB\bar{C}\bar{D}\cup AB\bar{C}D\cup ABCD\cup ABC\bar{D}=AB$ Красная

СкДНФ$=K_1\cup K_2\cup K_3\cup K_4\cup K_5=\bar{A}\bar{B}\bar{C}\cup \bar{A}\bar{B}\bar{D}\cup \bar{A}C\bar{D}\cup BC\bar{D}\cup AB$

3. Найти ядро

Ядровая склейка - та, без которой остаётся хотя бы одна непокрытая другими склейками единица $=>$ найдём единицы, покрываемые только одной склейкой

a	b	c	d	Импликанты, покрывающие клетку
0	0	0	0	$K_1,K_2$
0	0	0	1	$K_1$
0	0	1	0	$K_2,K_3$
0	1	1	0	$K_3,K_4$
1	1	0	0	$K_5$
1	1	0	1	$K_5$
1	1	1	0	$K_5$
1	1	1	1	$K_4,K_5$

$\bar{A}\bar{B}\bar{C}D$ покрыта только $K_1$
$AB\bar{C}\bar{D},AB\bar{C}D,ABC\bar{D}$ покрыты только $K_5$
Следовательно:
Ядро: $K_1\cup K_5=\bar{A}\bar{B}\bar{C}\cup AB$

4. Найти вспомогательную функцию Патрика

Чтобы найти функцию Патрика, выпишем конъюнкцию дизъюнкций пересекающихся неядровых склеек:
$H=(K_2\cup K_3)\cap (K_3\cup K_4)=K_2{K}_3\cup K_2{K}_4\cup K_3\cup K_3{K}_4=K_2{K}_3\cup K_2{K}_4\cup K_3(1\cup K4)=$
$K_3(K_2\cup 1)\cup K_2{K}_4=K_3\cup K_2{K}_4$

5. Найти тупиковые ДНФ

$H=K_3\cup K_2{K}_4=>$ тупиковые ДНФ:
$K_1\cup K_5\cup K_3=\bar{A}\bar{B}\bar{C}\cup AC\cup \bar{A}BD$
$K_1\cup K_5\cup K_2\cup K_4=\bar{A}\bar{B}\bar{C}\cup AC\cup \bar{A}\bar{C}D\cup BCD$

6. Найти МДНФ и КрДНФ

МДНФ - тупиковая ДНФ с наименьшим количеством литералов $=>$ определим количество литералов в полученных тупиковых ДНФ:
$\bar{A}\bar{B}\bar{C}\cup AB\cup \bar{A}C\bar{D}$ - 8 литералов
$\bar{A}\bar{B}\bar{C}\cup AB\cup \bar{A}\bar{B}\bar{D}\cup BC\bar{D}$ - 11 литералов
$=>\bar{A}\bar{B}\bar{C}\cup AB\cup \bar{A}C\bar{D}$ - МДНФ

КрДНФ - тупиковая ДНФ, состоящая из наименьшего количества элементарных конъюнкций $=>$ определим количество элементарных конъюнкций в полученных тупиковых ДНФ:
$\bar{A}\bar{B}\bar{C}\cup AB\cup \bar{A}C\bar{D}$ - 3 конъюнкции
$\bar{A}\bar{B}\bar{C}\cup AB\cup \bar{A}\bar{B}\bar{D}\cup BC\bar{D}$ - 4 конъюнкции
$=>\bar{A}\bar{B}\bar{C}\cup AB\cup \bar{A}C\bar{D}$ - КрДНФ

7. Отметить МДНФ на карте Карно

Задание I Типа III

Построить полином Жегалкина двумямя способами для функции:
$F(x,y,z)=(\overline{X\cap Z})\oplus (X|(Y\to \bar{Z}))$

Через СДНФ:

1. Найдём СДНФ для F(x,y,z):

X	Y	Z	$\bar{Z}$	$Y\to \bar{Z}$	$\overline{X\cap Z}$	$X\Vert (Y\to \bar{Z})$	F	СДНФ
0	0	0	1	1	1	1	0
0	0	1	0	1	1	1	0
0	1	0	1	1	1	1	0
0	1	1	0	0	1	1	0
1	0	0	1	1	1	0	1	$X\bar{Y}\bar{Z}$
1	0	1	0	1	0	0	0
1	1	0	1	1	1	0	1	$XY\bar{Z}$
1	1	1	0	0	0	1	1	$XYZ$

СДНФ=$X\bar{Y}\bar{Z}\cup XY\bar{Z}\cup XYZ$

2. Переведём СДНФ в СПНФ
   $X\bar{Y}\bar{Z}\cup XY\bar{Z}\cup XYZ$
   $=>$
   $X\bar{Y}\bar{Z}\oplus XY\bar{Z}\oplus XYZ$

3. Избавляемся от отрицаний и преобразовываем
   $X\bar{Y}\bar{Z}\oplus XY\bar{Z}\oplus XYZ=X(Y\oplus 1)(Z\oplus 1)\oplus XY(Z\oplus 1)\oplus XYZ=$
   $(XY\oplus X)(Z\oplus 1)\oplus XYZ\oplus XY\oplus XYZ=XYZ\oplus XY\oplus XZ\oplus X\oplus XYZ\oplus XY\oplus XYZ=$
   $(XYZ\oplus XYZ)\oplus (XY\oplus XY)\oplus XYZ\oplus XZ\oplus X=0\oplus 0\oplus XYZ\oplus XZ\oplus X=XYZ\oplus XZ\oplus X$
   $P(F)=X\oplus XZ\oplus XYZ$

Методом неопределённых коэффициентов:

По формуле: $P(F)=k_0\oplus k_{1}X\oplus k_{2}Y\oplus k_{3}Z\oplus k_{12}XY\oplus k_{13}XZ\oplus k_{23}YZ\oplus k_{123}XYZ$
Где $k_i$ - коэффициенты такие, что:

X	Y	Z	F	-	Формула
0	0	0	0	=	$k_0$
1	0	0	1	=	$k_0\oplus k_1$
0	1	0	0	=	$k_0\oplus k_2$
0	0	1	0	=	$k_0\oplus k_3$
1	1	0	1	=	$k_0\oplus k_1\oplus k_2\oplus k_{12}$
1	0	1	0	=	$k_0\oplus k_1\oplus k_3\oplus k_{13}$
0	1	1	0	=	$k_0\oplus k_2\oplus k_3\oplus k_{23}$
1	1	1	1	=	$k_0\oplus k_1\oplus k_2\oplus k_3\oplus k_{12}\oplus k_{13}\oplus k_{23}\oplus k_{123}$

Вычислим коэфициенты:

• $k_0=0$
• $k_1=1:k_0\oplus k_1=1;0\oplus k_1=1$
• $k_2=0:k_0\oplus k_2=0;0\oplus k_2=0$
• $k_3=0:k_0\oplus k_3=0;0\oplus k_3=0$
• $k_{12}=0:k_0\oplus k_1\oplus k_2\oplus k_{12}=1;0\oplus 1\oplus 0\oplus k_{12}=1$
• $k_{13}=1:k_0\oplus k_1\oplus k_3\oplus k_{13}=0;0\oplus 1\oplus 0\oplus k_{13}=0$
• $k_{23}=0:k_0\oplus k_2\oplus k_3\oplus k_{23}=0;0\oplus 0\oplus 0\oplus k_{23}=0$
• $k_{123}=1:k_0\oplus k_1\oplus k_2\oplus k_3\oplus k_{12}\oplus k_{13}\oplus k_{23}\oplus k_{123}=1;0\oplus 1\oplus 0\oplus 0\oplus 0\oplus 1\oplus 0\oplus k_{123}=1$
  Подставим коэфициенты в изначальное уравнение:
  $P(F)=X\oplus XZ\oplus XYZ$

Задание I Типа IV

Дано множество булевых функций $F=${$f_1,f_2,f_3,f_4$}

$f_1=x\oplus y\oplus z$	$f_2=x\to y\cap z$	$f_3=1$	$f_4=xyz$

Задание:

1. Для каждой функции определить принадлежность к классу Поста и составить критериальную таблицу с обоснованием.

Построим таблицы истинности для всех функций:

$x$	$y$	$z$	$f_1$	$f_2$	$f_3$	$f_4$
0	0	0	0	1	1	0
0	0	1	1	1	1	0
0	1	0	1	1	1	0
0	1	1	0	1	1	0
1	0	0	1	0	1	0
1	0	1	0	0	1	0
1	1	0	0	0	1	0
1	1	1	1	1	1	1

Проверим функции на принадлежность к классам Поста:
$T_0:$
Если значение функции от набора (0,0,0) не является нулём, то функция не содержит константу 0.

• $f_1\in T_0$, так как $f_1(0,0,0)=0$
• $f_2\notin T_0$, так как $f_2(0,0,0)\ne 0$
• $f_3\notin T_0$, так как $f_3(0,0,0)\ne 0$
• $f_4\in T_0$, так как $f_4(0,0,0)=0$

$T_1:$
Если значение функции от набора (1,1,1) не является единицей, то функция не содержит константу 1.

• $f_1\in T_1$, так как $f_1(1,1,1)=1$
• $f_2\in T_1$, так как $f_2(1,1,1)=1$
• $f_3\in T_1$, так как $f_3(1,1,1)=1$
• $f_4\in T_1$, так как $f_4(1,1,1)=1$

$S:$
Если значение функции от набора, противоположного данному, не противоположно значению функции от данного набора, то такая функция не самодвойтсвенна.

• $f_1\in S$
• $f_2\notin S$, так как $f_2(0,0,0)=f_2(1,1,1)$
• $f_3\notin S$, так как $f_3(0,0,0)=f_3(1,1,1)$
• $f_4\notin S$, так как $f_4(0,0,1)=f_4(1,1,0)$

$M:$
Если значение функция от набора, большего данного, меньше значения функции от данного набора, то такая функция не монотонна.

• $f_1\notin M$, так как $f_1(0,1,1)<f_1(0,1,0)$
• $f_2\notin M$, так как $f_2(1,0,0)<f_2(0,1,1)$
• $f_3\in M$
• $f_4\in M$

$L:$
Если полином Жегалкина этой функции нельзя представить без конъюнкций, либо если количество единиц в ней $\ne 4$, то она не линейная.

• $f_1\in L$, так как $P(f_1)=x\oplus y\oplus z$
• $f_2\notin L$, так как единиц: 5 $\ne$ 4
• $f_3\in L$, так как $P(f_3)=1$
• $f_4\notin L$, так как единиц: 1 $\ne$ 4

	$T_0$	$T_1$	$S$	$M$	$L$
$f_1$	+	+	+	-	+
$f_2$	-	+	-	-	-
$f_3$	-	+	-	+	+
$f_4$	+	+	-	+	-

2. Определить полноту булевых функций F по критериальной таблице с обоснованием.

Чтобы функция была полной, нужно, чтобы в каждом столбце таблицы был хотя бы один минус $=>$ функция $F=${$f_1,f_2,f_3,f_4$} неполная, так как в стобце $T_1$ нет минусов.