Дискретная математика (Задача 5, вариант 4). Задача 5, вариант 4. Задача 5 Для булевой функции а найти сокращенную днф

• Название: Задача 5 Для булевой функции а найти сокращенную днф
• Анкор: Дискретная математика (Задача 5, вариант 4
• Дата: 03.06.2022
• Размер: 61.51 Kb.
• Имя файла: Задача 5, вариант 4.docx
• Тип: Задача; #567694

Вариант 4

Задача 5

Для булевой функции



а) найти сокращенную ДНФ,

б) найти ядро функции,

в) получить все тупиковые ДНФ и указать, какие из них являются минимальными,

г) на картах Карно указать ядро и покрытия, соответствующие минимальным ДНФ.

Решение:

Найдём совершенную ДНФ

0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	1
0	1	0	0	1
0	1	0	1	1
0	1	1	0	0
0	1	1	1	0
1	0	0	0	1
1	0	0	1	1
1	0	1	0	1
1	0	1	1	0
1	1	0	0	0
1	1	0	1	1
1	1	1	0	1
1	1	1	1	1

Сокращенная ДНФ получается из полной ДНФ проведением всех операций склеивания и всех операций поглощения,

0000 0001 0010 0011 0100 0101 1000 1001 1010 1101 1110 1111

1, 2 000- 1, 3 00-0 1, 5 0-00 1, 7 -000 2, 4 00-1 2, 6 0-01 2, 8 -001 3, 4 001- 3, 9 -010 5, 6 010- 6, 10 -101 7, 8 100- 7, 9 10-0 8, 10 1-01 9, 11 1-10 - k 10, 12 11-1 - m 11, 12 111- - n

1,2,3,4 00-- - a 1,2,5,6 0-0- - b 1,2,7,8 -00- - c 1,3,7,9 -0-0 - d 2,6,8,10 --01 -e

Сокращённая дизъюнктивная нормальная форма,



импликантная матрица

	0000	0001	0010	0011	0100	0101	1000	1001	1010	1101	1110	1111
a = 00--	+	+	+	+	-	-	-	-	-	-	-	-
b=0-0-	+	+	-	-	+	+	-	-	-	-	-	-
c=-00-	+	+	-	-	-	-	+	+	-	-	-	-
d=-0-0	+	-	+	-	-	-	+	-	+	-	-	-
e=--01	-	+	-	-	-	+	-	+	-	+	-	-
k=1-10	-	-	-	-	-	-	-	-	+	-	+	-
m=11-1	-	-	-	-	-	-	-	-	-	+	-	+
n=111-	-	-	-	-	-	-	-	-	-	-	+	+

простые импликанты обозначены буквами,

запишем конъюнктивное представление матрицы,



конъюнкции, соответствующие столбцам матрицы, имеющим только один плюс, входят в состав ядра функции,

ядро функции



найдём все тупиковые ДНФ,

для того, чтобы найти все тупиковые ДНФ, для каждого столбца таблицы составляем дизъюнкцию импликант, для которых в столбце стоит плюс, составляем конъюнкцию дизъюнкций, соответствующих всем столбцам, и приводим её к дизъюнкции конъюнкций, каждая конъюнкция будет соответствовать тупиковой ДНФ,

















- длина тупиковой ДНФ,





найдём все тупиковые ДНФ































мы получили 5 тупиковых дизъюнктивных нормальных форм,











общей частью всех тупиковых ДНФ является ядро функции



минимальная ДНФ



карта Карно для функции имеет вид

		00	01	11	10
	00	1	1	1	1
	01	1	1
	11		1	1	1
	10	1	1		1

укажем ядро и покрытие, соответствующее минимальной ДНФ на карте Карно,

ядро




минимальная ДНФ





Ответ: сокращённая ДНФ


ядро


тупиковые ДНФ:











минимальная ДНФ