Дискретная математика (стр. 7 )

Рассмотрим функцию четырех аргументов:

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

Исключение составляют клетки, расположенные у границ карты. Для устранения этого исключения условно отождествляют противоположные границы карты – верхнюю с нижней и левую с правой.

Склеивающиеся клетки обводят таким образом, чтобы количество единиц в каждом контуре было максимально, а количество контуров - минимально. Количество единиц в контуре может быть равно . Полученные контуры следует описать конъюнкциями.

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

8.2. Метод Квайна поиска СокДНФ

Поэтапная минимизация логических функций предполагает следующий алгоритм минимизации: ДСНФ СокДНФ (Сокращенная ДНФ) ТДНФ (Тупиковая ДНФ) МДНФ (Минимальная ДНФ).

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

Операция полного склеивания: (члены и склеены по переменной ).

Операция неполного склеивания: .

Операция поглощения: (член поглощается членом ).

Порядок нахождения СокДНФ по Квайну:

1.  Преобразовать исходную логическую функцию к ДСНФ.

2.  В полученной ДСНФ выполнить все операции неполного склеивания.

3.  Выполнить все операции поглощения.

4.  Повторять шаги 2 и 3 до тех пор, пока среди конъюнкций не останется склеивающихся между собой.

Пример 1. Получить СокДНФ функции

1 - 2 *

1 - 3 *

1 - 4

1 - 5

1 - 6

2 - 3

2 - 4 *

2 - 5

2 - 6

3 - 4 *

3 - 5

3 - 6

4 - 5

4 - 6 *

5 - 6 *

1 - 2 2 - 3 * 3 - 4 4 - 5 5 - 6

1 - 3 2 - 4 3 - 5 4 - 6

1 - 4 * 2 - 5 3 - 6

1 - 5 2 - 6

1 - 6

– СокДНФ

Пример 2. Получить СокДНФ функции

1 - 2 * 2 - 3 * 3 - 4

1 - 3 2 - 4

1 - 4 *

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

Для нахождения тупиковых и минимальной ДНФ используется метод импликантных (импликативных) матриц.

Импликантная матрица – это таблица, в которой столбцы изображают конъюнкции ДСНФ, а строки – простейшие импликанты СокДНФ.

Составим импликантную матрицу для функции

(ДСНФ)

1 - 2 * 2 - 3 3 - 4 * 4 - 5 * 5 - 6 *

1 - 3 * 2 - 4 3 - 5 4 - 6

1 - 4 2 - 5 3 - 6

1 - 5 2 - 6 *

1 – 6

Дальнейшее склеивание невозможно. Следовательно, полученная запись – СокДНФ.

СокДНФ	ДСНФ
	Ö	Ö
	Ö		Ö
		Ö				Ö
			Ö	Ö
				Ö	Ö
					Ö	Ö

Идея метода заключается в том, что поиск «лишних» конъюнкций производится по способу накрытия конъюнкциями меньшего ранга конъюнкций большего ранга.

В строке против каждой простой импликанты ставится знак «Ö» под теми конституентами, которые поглощаются данной простой импликантой.

В тупиковую ДНФ должны входить импликанты, поглощающие все конъюнкции.

ТДНФ 1 =

ТДНФ 2 =

ТДНФ 3 =

ТДНФ 4 =

ТДНФ 5 =

Из полученных ТДНФ выбирается МДНФ:

ТДНФ 1 =

ТДНФ 3 =

8.3. Метод Квайна – Мак-Класки

Метод Квайна – Мак-Класки представляет собой модернизацию метода Квайна для нахождения простых импликант.

Основная идея метода заключается в том, что поиск склеивающихся аргументов следует вести среди конъюнкций, отличающихся друг от друга только одним аргументом.

Этапы поиска простейших импликант методом Квайна - Мак-Класки:

1.  Закрепить за аргументами определенные места в конъюнкции.

2.  Закодировать аргументы конъюнкций двоичными символами, причем если аргумент входит в конъюнкцию без инверсии, он кодируется единицей, если с инверсией – нулем.

3.  Получающиеся в результате такой перекодировки двоичные числа разбиваются на группы по числу единиц.

4.  Склеивающиеся аргументы нужно искать только между соседними группами.

5.  На месте склеивающихся аргументов будем ставить прочерк, а склеившиеся конъюнкции будем помечать *.

6.  Повторять шаги 3-5 до тех пор, пока среди конъюнкций не останется склеивающихся между собой.

Пример. Минимизировать функцию

= 0000 + 0001 + 0010 + 0011 + 0100 + 0110 + 0111 + +1000 + 1001 + 1011 + 1111

0 группа: 0000 *

1: 0001 * 0010 * 0100 * 1000 *

2: 0011 * 0110 * 1001 *

3: 0111 * 1011 *

4: 1111 *

0 группа: 000- * 00-0 * 0-00 * -000 *

1: 00-1 * 001- * 0-10 * 01-0 * -001 * 100- *

2: 0-11 * 011- * -011 * 10-1 *

3: -111 * 1-11 *

0 группа: 00-- 00-- 0--0 0--0 -00- -00-

1: 0-1- 0-1- -0-1 -0-1

2: --11 --11

= 00-- + 0--0 + -00- + 0-1- + -0-1 + --11

Для нахождения тупиковых и минимальной форм воспользуемся методом импликантных матриц.

Таблица 3.

Метод импликантных матриц

Сок. ДНФ	ДСНФ
0000	0001	0010	0011	0100	0110	0111	1000	1001	1011	1111
00--	Ö	Ö	Ö	Ö
0--0	Ö		Ö		Ö	Ö
-00-	Ö	Ö						Ö	Ö
0-1-			Ö	Ö		Ö	Ö
-0-1		Ö		Ö					Ö	Ö
--11				Ö			Ö			Ö	Ö

МДНФ = 0--0 + -00- + --11 =