Задание 5. Тема Нормальные формы. Понятия тупиковой, минимальной и сокращенной днф. Методы получения сокращенной и минимальной днф

• Название: Тема Нормальные формы. Понятия тупиковой, минимальной и сокращенной днф. Методы получения сокращенной и минимальной днф
• Дата: 12.04.2023
• Размер: 54.93 Kb.
• Имя файла: Задание 5.docx
• Тип: Документы; #1057538

Практическое задание 5

Тема 4.3. Нормальные формы. Понятия тупиковой, минимальной и сокращенной ДНФ. Методы получения сокращенной и минимальной ДНФ

Формулировка задания 4

Для данных функций и , заданных векторно в табл. 5.1, проделать следующее.

1. Записать их СДНФ и СКНФ.

2. Методом Квайна найти сокращенную ДНФ.

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

4. С помощью матрицы Квайна найти минимальную ДНФ, указать ее сложность.

5. Найти минимальную ДНФ данной функции с помощью карт Карно, сравнить полученный результат с ДНФ, найденной в п. 4.

Таблица 5.1

№	f	g
1	1011 1100	1111 0101 0011 1101
2	0111 1010	1101 1110 1010 1110
3	1001 1001	0111 0001 1111 1101
4	1110 1110	1011 1111 1111 1000
5	1010 1111	1101 0101 1101 1111
6	0110 1111	1111 1110 1010 0011
7	1000 0110	111 0010 0111 1110
8	0111 0110	1100 1110 1111 1011
9	1110 0110	1100 0110 1111 0111
10	0111 1110	1011 1111 1110 0010

Рекомендации по выполнению задания

Номер варианта задания вы можете определить, используя табл. 5.2, по первой букве вашей фамилии. Решение расписывать как можно подробнее, описывать формулы, которыми пользуетесь во время решения, – обязательно. Обязательно должно быть записано условие задания, ответ.
Таблица 5.2

Выбор варианта задания

Буква	А, Ф, Э	Б, М, Х	В, Ю	Г, У,Я	Д, Ч, С	Е, Н, П	Ж, О, З	И, Ц	К, Т, Ш, Щ	Л, Р
№ вар.	1	2	3	4	5	6	7	8	9	10

Указания по выполнению работы

Для данных функций и , заданных векторно, проделать следующее:

1. Записать их СДНФ и СКНФ.

2. Методом Квайна найти сокращенную ДНФ.

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

4. С помощью матрицы Квайна найти минимальную ДНФ, указать ее сложность.

5. Найти минимальную ДНФ данной функции с помощью карт Карно, сравнить полученный результат с ДНФ, найденной в п. 4.

Решение

Распишем таблицы истинности функций.

x y z 000 1 001 1 010 0 011 1 100 0 101 0 110 1 111 1

x y z t f(x,y,z,t) 0000 1 0001 1 0010 1 0011 0 0100 0 0101 1 0110 1 0111 1 1000 0 1001 0 1010 1 1011 0 1100 1 1101 1 1110 1 1111 1

1. 
   СДНФ:
   

СКНФ:





2. Найдем сокращенную ДНФ из записанной СДНФ. Для более легкого восприятия символы переменных заменим на показатели степеней переменных. Например, вместо будем употреблять набор 0-1-. В этом случае СДНФ булевой функции будет соответствовать множество всех ее единичных наборов (т. е. тех наборов, на которых функция принимает значение 1). Выпишем единичные наборы данной булевой функции в таблицу, разбив их на группы в соответствии с количеством единичных компонент в наборах.

Тогда для применения формулы склеивания достаточно просмотреть всевозможные пары наборов, входящих в соседние группы.

0 0 0 +	0 0 –
0 0 1 +
	0 – 1
0 1 1 + 1 1 0 +
1 1 1 + I полоса
	1 1 – II полоса

Результаты склеивания наборов из 1-й полосы поместим во 2-й полосе, а наборы, участвующие в склеиваниях, пометим крестиком. Во второй полосе снова применяем, насколько возможно, операцию склеивания, записывая результаты в 3-ю полосу и т. д. После завершения процедуры склеивания все простые импликанты попадут в таблицу и не будут помечены крестиком.

Сокращенная ДНФ данной булевой функции имеет вид: .

0 0 0 0 +	0 0 0 - 0 0 – 0
0 0 0 1 + 0 0 1 0 +
	0 – 1 0 + - 0 1 0 +	- - 1 0 - - 1 0
0 1 0 1 + 0 1 1 0 + 1 0 1 0 + 1 1 0 0
		- 1 – 1 - 1 – 1 - 1 1 – - 1 1 – 1 1 - - 1 1 - - III полоса
0 1 1 1 + 1 1 0 1 + 1 1 1 0 +
	0 1 – 1 + - 1 0 1 + 0 1 1 – + - 1 1 0 + 1 – 1 0 + 1 1 0 – + 1 1 – 0 +
1 1 1 1 + I полоса
	- 1 1 1 + 1 1 – 1 + 1 1 1 - + II полоса

Сокращенная ДНФ данной булевой функции имеет вид: .

3. Для получения из сокращенной ДНФ минимальной ДНФ изобразим следующую таблицу – матрицу Квайна.

№ простой импликанты 1 2 3 Простые импликанты Единичные наборы 0 0 0 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1

№ простой импликанты 1 2 3 4 5 6 Простые импликанты Единичные наборы +0 0 0 0 1 1 +0 0 0 1 1 +0 0 1 0 1 1 +0 1 0 1 1 +0 1 1 0 1 1 +0 1 1 1 1 1 +1 0 1 0 1 +1 1 0 0 1 +1 1 0 1 1 1 +1 1 1 0 1 1 1 +1 1 1 1 1 1 1

4. Для функции f все три импликанты являются ядровыми (если в строке одна единица, то выделяем ее и столбцы с выделенными единицами дают ядровые импликанты). Поэтому сокращенная ДНФ является и минимальной, ее сложность равна шести.

Для функции g ядровыми импликантами являются 1, 3, 4 и 6. Отметим все строки, перекрываемые этими импликантами, знаком +. В результате получили, что ядровые импликанты обеспечивают единицы во всех строках и, значит, только они образуют минимальную ДНФ: , ее сложность равна девяти.

5. Найдем минимальную ДНФ с помощью карт Карно.

yz x 00 01 11 10 0 1 11 12 0 1 0 0 1 13 Максимальный размер прямоугольников равен двум, чтобы покрыть все единицы, требуется три прямоугольника. Запишем импликанты для каждого треугольника. Первый прямоугольник дает импликанту (единицы стоят в таких позициях, которые отличаются значениями z, а переменные x и y принимают значения нуль). Второй прямоугольник – , третий – . В результате мы получили минимальную ДНФ, , сложность которой равна шести. Эта полученная минимальная ДНФ отличается от полученной в пункте 4. Это связано с тем, что мы второй прямоугольник могли нарисовать не вертикальным, а горизонтальным. Самое главное, что сложности полученных ДНФ одинаковые. Этот пример еще раз подтверждает тот факт, что можно получить различные формулы для ДНФ, но все они будут иметь одинаковую сложность

zt xy 00 01 11 10 00 1 11 0 13 01 0 1 12 1 11 1 1 1 1 4 10 0 0 0 1 Рассмотрим возможные способы для изображения прямоугольников. Синим цветом выделены единицы, для которых существует единственный способ для образования прямоугольников. В результате все нарисованные для этих единиц прямоугольники покрыли и все остальные треугольники. Запишем импликанты для каждого треугольника. Первый прямоугольник дает импликанту . Второй прямоугольник – , третий – , четвертый – Минимальная ДНФ: , совпадает с полученной в пункте 4