Графический метод минимизации: карты Карно-Вейча

Методические указания

· Конъюнкция называется элементарной, если в ней каждая переменная встречается не более одного раза.

· Дизъюнкция элементарных конъюнкций называется ДНФ.

· Для функции от n переменных ДНФ, состоящая из конъюнкций ранга n, называется ДСНФ.

· Ранг конъюнкции – это количество переменных, которые ее образуют.

· Длина ДНФ L – это число конъюнкций, которые ее составляют.

· Кратчайшей ДНФ называется такая ДНФ, которая имеет наименьшую длину L по сравнению с другими ДНФ, которые эквивалентны данной функции.

· Минимальной ДНФ называется такая ДНФ, которая имеет наименьшее число букв по сравнению с другими ДНФ, которые эквивалентны данной функции.

Рассмотрим проблему минимизации для геометрического способа задания области значений ФАЛ.

Сопоставим различным геометрическим элементам этого куба конъюнкции различных рангов. У нас есть вершины, ребра, грани и сам куб. Сумма размерности геометрического эквивалента и ранга конъюнкции равна числу аргументов ФАЛ.

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

По аналогии, каждая конъюнкция большего ранга покрывается всеми конъюнкциями меньшего ранга.

· Геометрические эквиваленты еще называют интервалами.

· Интервалом L-го ранга называется подмножество вершин куба, соответствующих конъюнкции ранга L.

Например, конъюнкции соответствует 4 вершины: 100, 101, 110, 111.

На кубе отмечают вершины, где ФАЛ равна 1. Эти вершины образуют подмножество Т₁. Для того чтобы задать ДНФ на кубе, необходимо задать покрытие всех вершин.

Задача о минимизации рассматривается как задача о нахождении минимальной ДНФ

Необходимо найти Т₁, при котором R будет минимальным.

Некоторый интервал J называется максимальным, если не существует никакого другого интервала J’, у которого ранг меньше, чем у J, и такого, что выполняется следующее соотношение .

Пример:

пусть есть функция, которая равна 1 в отмеченных точках.

J₁ и J₃ – максимальные интервалы

J₂ не является максимальным

ДНФ называется сокращенной (СДНФ), если она соответствует покрытию множества Т₁ всеми максимальными интервалами.

В данном примере СДНФ = .

Минимальная ДНФ получается из СДНФ путем выбрасывания из покрытия множества Т₁ максимальными интервалами некоторых “лишних” интервалов

Пункты решения задачи по минимизации:

1. Построение по заданной функции СДНФ;

2. Выбрасывание из СДНФ “лишних” максимальных интервалов.

Итак, минимальная форма неоднозначна, так как может быть несколько минимальных форм.

Четырехмерное пространство

Метод Квайна

Предположим, что функция задана в ДСНФ. Ее элементарные конъюнкции ранга n будем называть минитермами ранга n.

Этапы:

1. Нахождение первичных импликант.

Все минитермы данной ФАЛ сравниваются между собой попарно. Если минитермы m_i и m_j таковы, что их можно попарно представить в виде , то мы выписываем конъюнкцию, которая является минитермом ранга n-1: .

Пример:

Минитермы n-го ранга, для которых произошло склеивание отмечаются.

После построения всех минитермов (n-1)-го ранга вновь сравнивают их попарно, выписывают минитермы (n-2)-го ранга и отмечают склеивающиеся минитермы (n-1)-го ранга и т.д. Этап заканчивается, когда вновь полученные минитермы n-го ранга уже не склеиваются между собой.

Все неотмеченные минитермы называются первичными или простыми импликантами. Пример:

2. Расстановка меток. Для данной функции

где - первичные импликанты

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

Минитермы						B	C	E	F
Первичные импликанты
	Ö			Ö		Ö			Ö
		Ö	Ö
		Ö					Ö
			Ö	Ö
					Ö	Ö
							Ö	Ö
								Ö	Ö

3. Нахождение существенных импликант.

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

Поэтому из таблицы меток исключаем строки, соответствующие существенным импликантам, и столбцы минитермов, покрываемых ими.

Пример: Для нашей функции f существенная импликанта .

4. Вычеркивание лишних столбцов.

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

5. Вычеркивание лишних первичных импликант.

Если после этапа 4 в таблице есть строки без единой метки, то они вычеркиваются.

6. Выбор минимального покрытия максимальными интервалами.

Исследуется полученная таблица: выбирается такая совокупность первичных импликант, которая включает метки во всех столбцах (по крайней мере по 1 в каждом столбце). При нескольких вариантах отдается предпочтение варианту покрытия с минимальным суммарным числом букв в простых импликантах.

Метод Мак-Класки

Идея метода:

1. Всем минитермам ставим в соответствие их двоичный эквивалент.

Например,

2. Все номера-минитермы разбиваем на группы по числу единиц в этих номерах.

3. Попарное сравнение можно производить только между соседними группами, т.к. только эти группы отличаются для входящих в них минитермов в одном разряде.

4. Преобразование новых минитермов: в разрядах, соответствующих исключенным переменным, ставим черточку. Такая модификация удобна еще и отсутствием громоздкой записи.

Например,

Пример:

Задана функция, которая равна единице на наборах с номерами – 0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 15.Минимизировать ее методом Мак-Класки

Решение

0000* – нулевая группа

0001*, 0010*, 0100*, 1000* - первая группа

0011*, 0110*, 1001* - вторая группа

0111*, 1011* - третья группа

1111* - четвертая группа

000_*, 00_0*, 0_00*, _000* - нулевая

00_1*, _001*, 001_*, 0_10*, 01_0*, 100_* - первая

0_11*, _011*, 011*_, 10_1* - вторая

_111*, 1_11* - третья

00__, _00 _, 0__0 – нулевая

_0_1, 0_1_ – первая

__11 – вторая

Далее строим таблицу и расставляем метки, как и в методе Квайна.


00__	Ö	Ö	Ö	Ö
_ 00 _	Ö	Ö						Ö	Ö
0__0	Ö		Ö		Ö	Ö
_0_1		Ö		Ö					Ö	Ö
0_1_			Ö	Ö		Ö	Ö
__11				Ö			Ö			Ö	Ö

Производим преобразования таблицы согласно 3-6 пунктам метода Квайна. В результате получаем .

Графический метод минимизации: карты Карно-Вейча

Карты Карно – другой графический метод отображени булевых функций. Это специальные таблицы, задающие ФАЛ. Они сформированы так, чтобы облегчить процесс склеивания. Карты Карно используются при n=2,3,4,5,6 в случае, при n>6 они практически непригодны. Диаграммы Вейча принципиально не отличаются лишь порядком следования наборов значений и обзначениями (Карно – {0,1}; Вейча – ().

Основные принципы построения.

1) Карты Карно – это такие таблицы задания ФАЛ или плоская развертка n-мерных кубов, что склеивающиеся между собой конституенты единицы или нуля расположены в соседних клетках: по горизонтали и по вертикали клетки таблицы отличаются лишь значением одной переменной.

2) Клетки, расположенные по краям таблицы считаем соседними и обладают этим же свойством.

1) n=2