Первый этап

Переход от табличной формы к аналитической

Аналитический способ представления

Для этого нужно ввести множество функций, а также правила зависимости функций от набора переменных, т.е. формулы – аналитические выражения на основе операций булевой алгебры.

Всякую логическую функцию можно представить в виде СДНФ и СКНФ. Причем у каждой булевой функции может быть только по одной СДНФ и СКНФ.

Таблица 2.4 – Функция 3 – х переменных

х1 х2 х3	F	конституента 1	конституента 0
0 0 0			х1 Ú х2 Ú х3
0 0 1		ù х1 ù х2 х3
0 1 0		ù х1 х2 ù х3
0 1 1			х1 Ú ù х2 Úù х3
1 0 0			ù х1 Ú х2 Ú х3
1 0 1		х1 ù х2 х3
1 1 0		х1 х2 ù х3
1 1 1			ù х1 Úù х2 Ú ù х3

Отсюда переходим к аналитическим выражениям логической функции:

СДНФ: F = ù х₁ ù х₂ х₃ Ú ù х₁ х₂ ù х₃ Ú х₁ ù х₂ х₃ Ú х₁ х₂ ù х₃,

СКНФ: F = (х₁ Ú х₂ Ú х₃) (х₁ Ú ù х₂ Úù х₃) (ù х₁ Ú х₂ Ú х₃) (ù х₁ Úù х₂ Ú ù х₃).

Примечание: функция, для которой не существует СДНФ – константа 0, функция, для которой не существует СКНФ – константа 1.

2.4.6 Минимизация функций методом Квайна – Мак-Класки

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

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

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

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

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

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

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

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

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

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

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

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

1. Записываем номера конституент единицы: 0001, 0100, 0101, 0110, 0111, 1000, 1001, 1100, 1101.

2. Группируем их по числу единиц:

Таблица 2.5 – Группы номеров по числу единиц

0001, 0100, 1000

0101, 0110, 1001, 1100

0111, 1101

3. Производим склейки номеров. Результат заносим в новую таблицу:

Таблица 2.6 – Первая склейка номеров

0001, 0100, 1000

0101, 0110, 1001, 1100

0111, 1101

Таблица 2.7 – Результаты первой склейки

0_01, _001, 100_, 1_00, 010_, 01_0, _100

1_10, _101, 011_, 1_01, 110_

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

Таблица 2.8 – Вторая склейка

0_01, _001, 100_, 1_00, 010_, 01_0, _100

1_10, _101, 011_, 1_01, 110_

Таблица 2.9 – Результаты второй склейки

_ _ 01, _ _ 01, 1_0_, 1_0_, 01_ _, 01_ _, _10_, _10_

5. Со всех таблиц выбираем импликанты, которые не участвовали в склейках и все, что осталось после склеек. Убираем повторяющиеся импликанты.

6. Записываем сокращенную ДНФ:

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

Дата добавления: 2015-08-31