Второй этап

Первый этап.

Записываем СДНФ функции и одновременно нумеруем конституенты:

F = ù х₁ ù х₂ ù х₃ х₄ Ú ù х₁ ù х₂ х₃ х₄ Ú ù х₁ х₂ ù х₃ х₄ Ú ù х₁ х₂ х₃ х₄ Ú

1 2 3 4

Ú х₁ х₂ х₃ ù х₄ Ú х₁ х₂ х₃ х₄

5 6

Проверяем склейки между конституентами и записываем то, что остается после склеек (импликанты):

1 – 2: ù х₁ ù х₂ х₄ ; 2 – 3: не клеятся; 3 – 5: не клеятся;

1 – 3: ù х₁ ù х₃ х₄ ; 2 – 4: ù х₁ х₃ х₄ ; 3 – 6: не клеятся;

1 – 4: не клеятся; 2 – 5: не клеятся; 4 – 5: не клеятся;

1 – 5: не клеятся; 2 – 6: не клеятся; 4 – 6: х₂ х₃ х₄ ;

1 – 6: не клеятся; 3 – 4: ù х₁ ù х₂ х₄ ; 5 – 6: х₁ х₂ х₃.

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

F = ù х₁ ù х₂ х₄ Ú ù х₁ ù х₃ х₄ Ú ù х₁ х₃ х₄ Ú ù х₁ ù х₂ х₄ Ú х₂ х₃ х₄ Ú х₁ х₂ х₃.

1 2 3 4 5 6

Проверяем склейки между импликантами:

1 – 2: не клеятся; 2 – 3: ù х₁ х₄; 3 – 5: не клеятся;

1 – 3: не клеятся; 2 – 4: не клеятся; 3 – 6: не клеятся;

1 – 4: ù х₁ х₄; 2 – 5: не клеятся; 4 – 5: не клеятся;

1 – 5: не клеятся; 2 – 6: не клеятся; 4 – 6: не клеятся;

1 – 6: не клеятся; 3 – 4: не клеятся; 5 – 6: не клеятся.

Отсюда сокращенная ДНФ:

F = ù х₁ х₄ Ú х₂ х₃ х₄ Ú х₁ х₂ х₃.

Производится по импликантной матрице Квайна. В строках ее - простые импликанты – составляющие сокращенной ДНФ, а в столбцах - конституенты единицы из СДНФ.

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

Таблица 2.12 – Импликантная матрица Квайна

простые импликанты	конституенты единицы
		ù х1 ù х2 ù х3 х4	ù х1 ù х2 х3 х4	ù х1 х2 ù х3 х4	ù х1 х2 х3 х4	х1 х2 х3 ù х4	х1 х2 х3 х4
ù х1 х4	´	´	´	´
х2 х3 х4				´		´
х1 х2 х3					´	´

На пересечении строки импликанты, которая поглощает данную конститенту, с соответствующим конституенте столбцом, ставим ´.

Число крестиков в каждой строке определяется по соотношению:

2 ^{n – k}, где:

n – количество аргументов в конституенте единицы,

k – количество аргументов в простой импликанте.

Импликанты, которые в единственном числе поглощают конституенту единицы, являются базисными импликантами. Они образуют ядро булевой функции и должны обязательно войти в минимальную ДНФ.

Отсюда наша минимальная ДНФ выглядит таким образом:

F = ù х₁ х₄ Ú х₁ х₂ х₃. }

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

Мак-Класки формализовал метод минимизации Квайна на первом этапе – этапе нахождения простых импликант. Алгоритм метода следующий:

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

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

3. Производится склеивание между номерами по следующим правилам:

· склеиваются номера соседних групп, т.к. они отличаются только одним разрядом;

· склеиваемые номера отмечаются (зачеркиваются);

· каждый номер может участвовать в склейке произвольное число раз;

· выпадающие разряды заменяются прочерками.

4. Со всех групп выбираем импликанты, оставшиеся после склейки. Они и образуют сокращенную ДНФ.

Второй этап – нахождение минимальной ДНФ производится по импликантной матрице Квайна.

{ Пример: минимизировать следующую логическую функцию:

F (x₁, x₂, _, x₃, x₄) = Ú (1, 4, 5, 6, 7, 8, 9, 12, 13).

Дата добавления: 2014-01-06