МИНИСТЕРСТВО ОБРАЗОВАНИЯ РФ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ «ЛЭТИ»

Кафедра МОЭВМ

Индивидуальное задание

по дисциплине «ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ»

Вариант №4

Выполнил:

Студент Баскаков Ю. Н.

Группа 2304

Проверил:

Красюк В. И.

Санкт-Петербург

2006

Т={0, 1, 2, 3, 4, 6, 8, 9, 10, 11, 12, 14, 17, 19, 21, 22, 25, 27}

1. Формальная постановка задачи минимизации булевской функции

Рассматривается функция алгебры логики, или булевская функция (БФ):

f: Bⁿ –> B, B = {0,1}.

БФ может быть задана таблицей (истинности, карта Карно), аналитическим (формула) или графическим (единичный гиперкуб) способом, а также множествами (истинности – T, ложности – F). В данном случае БФ задана набором значений аргументов, на которых функция принимает единичное значение, т.е. множеством истинности T:

T  Bⁿ, T = {} или T = {},

где – числовой эквивалент двоичного набора.

Необходимо найти аналитическое представление заданной БФ в виде минимальной формы, т.е. такой формы, в которой число символов не больше, чем в любой другой форме. В качестве таковой может выступать форма в виде дизъюнкции простых импликант приведенной (неизбыточной) системы.

Определения:

БФ  – импликанта БФ f, если .

Простая импликанта – импликанта, никакая часть которой не является импликантой.

Приведенная (неизбыточная) система простых импликант – система простых импликант БФ, не содержащая неизбыточных импликант.

Процесс минимизации БФ можно разбить на два этапа:

1. поиск системы простых импликант исходной функции;

2. построение приведенной системы простых импликант.

На первом этапе можно использовать процедуру Квайна-МакКласки либо численную процедуру на гиперкубах. Второй этап реализуется с использованием импликантной матрицы

2. Минимизация функции с помощью процедуры Квайна - Мак-Клаcски

Вариант № 4 (21) Т={0, 1, 2, 3, 4, 6, 8, 9, 10, 11, 12, 14, 17, 19, 21, 22, 25, 27}

index	const	1 уровень	2 уровень	3 уровень
0	0	[ 0, 1 ] (1)	[ 0, 1, 2, 3 ] (1)(2)	[ 0, 1, 2, 3, 8, 9, 10, 11 ] (1)(2)(8)
			[ 0, 1, 8, 9 ] (1)(8)
		[ 0, 2 ] (2)	[ 0, 2, 4, 6 ] (2)(4)	[ 0, 2, 4, 6, 8, 10, 12, 14 ] (2)(4)(8)
			[ 0, 2, 8, 10 ] (2)(8)
		[ 0, 4 ] (4)	[ 0, 4, 8, 12 ] (4)(8)
		[ 0, 8 ] (8)
1	1	[ 1, 3 ] (2)	[ 1, 3, 9, 11 ] (2)(8)	[ 1, 3, 9, 11, 17, 19, 25, 27 ] (2)(8)(16)
			[ 1, 3, 17, 19 ] (2)(16)
		[ 1, 9 ] (8)	[ 1, 9, 17, 25 ] (8)(16)
		[ 1, 17 ] (16)
	2	[ 2, 3 ] (1)	[ 2, 3, 10, 11 ] (1)(8)
		[ 2, 6 ] (4)	[ 2, 6, 10, 14 ] (4)(8)
		[ 2, 10 ] (8)
	4	[ 4, 6 ] (2)	[ 4, 6, 12, 14 ] (2)(8)
		[ 4, 12 ] (8)
	8	[ 8, 9 ] (1)	[ 8, 9, 10, 11 ] (1)(2)
		[ 8, 10 ] (2)	[ 8, 10, 12, 14 ] (2)(4)
		[ 8, 12 ] (4)
2	3	[ 3, 11 ] (8)	[ 3, 11, 19, 27 ] (8)(16)
		[ 3, 19 ] (16)
	6	[ 6, 14 ] (8)
		[ 6, 22 ] (16)
	9	[ 9, 11 ] (2)	[ 9, 11, 25, 27 ] (2)(16)
		[ 9, 25 ] (16)
	10	[ 10, 11 ] (1)
		[ 10, 14 ] (4)
	12	[ 12, 14 ] (2)
	17	[ 17, 19 ] (2)	[ 17, 19, 25, 27 ] (2)(8)
		[ 17, 21 ] (4)
		[ 17, 25 ] (8)
3	11	[ 11, 27 ] (16)
	14
	19	[ 19, 27 ] (8)
	21
	22
	25	[ 25, 27 ] (2)
4	27
5