МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Ижевский государственный технический университет»

(ИжГТУ)

Факультет «Математика и естественные науки»

Кафедра «Прикладная математика и информатика»

Лабораторная работа №1

по теме: «Минимизация функций алгебры логики»

Выполнил:

студент группы 3-78-3

Симонов М.В.

Проверил:

ст. преподаватель

Юманова И.Ф.

Ижевск

2011

Метод карт Карно

1. Постановка задачи

Используя язык высокого уровня Pascal, минимизируем функцию методом карт Карно для трёх переменных.

2. Краткие теоретические сведения

Этот метод наиболее удобен для решения инженерных задач, т.к. позволяет упростить поиск склеивающихся членов, но он ограничен числом аргументов данной функции. Практически минимизация по методу карт Карно производится для функций с числом аргументов не более восьми .

Карта Карно представляет собою специальную таблицу функции.

Рассмотрим карту для функции 2-х переменных.

							x1 x2	0	1
0	0	1	x1=0	1	0		0	1	0
0	1	0
1	0	1	x1=1	1	1		1	1	1
1	1	1

Можно упростить карту, если для аргументов ввести символические обозначения черточкой, поставив ее там, где они равны единице.

	1	0
	1	1

В карту вносятся значения функции, соответствующие наборам переменных.

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

Записав члены СДНФ функции в соответствующих клетках, можно легко это увидеть. Например, в приведенной выше карте

.

Члены столбца склеиваются той переменной, которой соответствует весь столбец, а строки – вся строка.

Рассмотрим карту Карно для функции 3-х переменных. Карту будем строить с симметричным расположением аргументов, один из них расположим с одной стороны, два других – с другой.

Разделим карту двумя осями, симметрично которым и будем располагать аргументы (см. карту).

Каждая клетка карты соответствует членам СДНФ функции, содержащим 3 знака.

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

Так можно склеить клетки 1 и 5, 1 и 2 и т.д., а также 2, 3, 6, 7; 1, 5, 4, 8 и т.д.

Если представить карту свернутой по вертикали в цилиндр, то крайние клетки окажутся рядом, их тоже можно склеить.