Минимизация систем булевых функций методом Квайна
Метод Петрика
Петрик формализовал второй этап минимизации, т.е. нахождение минимальной ДНФ – исключение лишних простых импликант. Данный метод позволяет свести работу с импликантной матрицей к аналитическим выражениям. По импликантной матрице строится так называемое конъюнктивное представление импликантной матрицы.
Алгоритм метода:
1. Все простые импликанты обозначаются буквами.
2. Для каждого i – го столбца матрицы строится дизъюнкция всех букв, обозначающих строки матрицы, пересечение которых с i – м столбцом отмечено ´.
3. Конъюнкция построенных дизъюнкций для всех столбцов матрицы и есть конъюнктивное представление импликантной матрицы.
4. К данному выражению можно применять все законы булевой алгебры с целью его упрощения. После раскрытия скобок и всех возможных поглощений получаем дизъюнкцию конъюнкций, каждая из которых содержит все импликанты тупиковой ДНФ.
{ Пример: Имеем после первого этапа минимизации следующую импликантную матрицу (смотри метод Квайна – Мак-Класки):
Таблица 2.19 – Импликантная матрица
| ù х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 ù х2 ù х3 х4 | х1 х2 ù х3ù х4 | х1 х2 ù х3 х4 | |
| ù х3 х4 = A | ´ | ´ | ´ | ´ | |||||
| х1 ù х3 = B | ´ | ´ | ´ | ´ | |||||
| ù х1 х2 = C | ´ | ´ | ´ | ´ | |||||
| х2 ù х3 = D | ´ | ´ | ´ | ´ | |||||
| F | A | C Ú D | A Ú C Ú D | C | C | B | A Ú B | B Ú D | A Ú B Ú D |
Отсюда конъюнктивное представление импликантной матрицы:
F = A (C Ú D) (A Ú C Ú D) C C B (A Ú B) (B Ú D) (A Ú B Ú D).
После раскрытия скобок и поглощений получаем минимальную ДНФ:
F = A C B = ù х3 х4 Ú ù х1 х2 Ú х1 ù х3 }
Алгоритм минимизации следующий:
1. Строится множество элементарных конъюнкций минимизируемой системы функций с приписыванием каждой конституенте единицы признака (номера) вхождения в i – ю функцию.
2. Составляется новая СДНФ j из этих конъюнкций.
3. Производится ее минимизация с учетом признаков вхождения. Строится импликантная матрица функции j с признаками вхождения: для каждой конституенты единицы отводится столько столбцов, сколько различных номеров функций содержит признак вхождения конституенты. Заполнение матрицы аналогично методу Квайна.
4. Выделяем для функции Fi импликанты с признаками i. Получаем минимальную ДНФ системы логических функций.
{Пример: Имеем функцию, заданную таблицей истинности:
Таблица 2.20 – Таблица истинности системы двух функций трех переменных
| x1 | x2 | x3 | F1 | F2 |
СДНФ функций:
F1 = ù x1 ù x2 ù x3 Ú x1 ù x2 x3 Ú x1 x2 ù x3 Ú x1 x2 x3 ,
F2 = ù x1 ù x2 ù x3 Ú ù x1 x2 ù x3 Ú ù x1 x2 x3 Ú x1 ù x2 x3 .
1. Множество элементарных конъюнкций с их признаками вхождения:
ù x1 ù x2 ù x3 (1, 2); x1 ù x2 x3 (1, 2); x1 x2 ù x3 (1);
x1 x2 x3 (1); ù x1 x2 ù x3 (2); ù x1 x2 x3 (2).
2. Составляем новую СДНФ и проверяем склейки:
1 2 3 4
j = ù x1 ù x2 ù x3 (1, 2) Ú x1 ù x2 x3 (1, 2) Ú x1 x2 ù x3 (1) Ú x1 x2 x3 (1) Ú
5 6
Ú ù x1 x2 ù x3 (2) Ú ù x1 x2 x3 (2).
1 – 2 : не клеятся; 2 – 3 : не клеятся; 3 – 5 : не клеятся;
1 – 3 : не клеятся; 2 – 4 : х1 ù х3 (1) ; 3 – 6 : не клеятся;
1 – 4 : не клеятся; 2 – 5 : не клеятся; 4 – 5 : не клеятся;
1 – 5 : ù х1 ù х3 (2); 2 – 6 : не клеятся; 4 – 6 : не клеятся ;
1 – 6 : не клеятся; 3 – 4 : х1 х2 (1) ; 5 – 6 : ù х1 х2 (2).
Сокращенная ДНФ системы функций будет:
j = ù x1 ù x2 ù x3 (1, 2) Ú x1 ù x2 x3 (1, 2) Ú x1 x2 (1) Ú x1 x3 (1) Ú
Ú ù x1 ù x3 (2) Ú ù x1 x2 (2).
3. Импликантная матрица будет слудующей:
Таблица 2.21 – Импликантная матрица системы двух функций
| ù x1 ù x2 ù x3 | ù x1 x2 ù x3 | ù x1 x2 x3 | x1 ù x2 x3 | x1 x2 x3 | x1 x2 ù x3 | |||
| ù x1 ù x3 (2) | ´ | ´ | ||||||
| x1 x3 (1) | ´ | ´ | ||||||
| x1 x2 (1) |  ´
| ´ | ||||||
| ù x1 x2 (2) |  ´
| ´ | ||||||
 ù x1 ù x2 ù x3 (1, 2)
| ´ | ´ | ||||||
| x1 ù x2 x3 (1, 2) |  ´
| ´ |
Таким образом минимальная ДНФ:
j = ù x1 ù x2 ù x3 (1, 2) Ú x1 ù x2 x3 (1, 2) Ú x1 x2 (1) Ú ù x1 x2 (2).
3. Минимальные ДНФ системы функций:
F1 = ù x1 ù x2 ù x3 Ú x1 ù x2 x3 Ú x1 x2 ,
F2 = ù x1 ù x2 ù x3 Ú ù x1 x2 Ú x1 ù x2 x3 .
Метод карт Карно (диаграммы Вейча)
Карта Карно – матричная форма представления булевых функций, заданной в СДНФ или СКНФ. Выглядят как развертка куба на площади. Аргументы записываются в таком порядке, чтобы соседние отличались не более, чем в одном разряде. В этом случае склейке подлежат наборы, для которых единицы (нули) располагаются в соседних клетках матрицы. Причем это должны быть прямоугольные конфигурации единиц (нулей), содержащие число клеток, равное целой степени 2.
Получающееся элементарное произведение (дизъюнкции для СКНФ) определяется как произведение переменных, не меняющих своего значения на всех склеиваемых наборах.