Составители:
Рассмотрим применение метода Квайна на примере минимизации
функции, заданной таблицей истинности:
x
1
00001111
x
2
00110011
x
3
01010101
F(x
1
, x
2
, x
3
)11100100
Записываем СДНФ функции:
321321321321321
),,( xxxxxxxxxxxxxxxf ∨⋅⋅∨⋅⋅=
⋅
⋅
∨
⋅
⋅
Попарно сравнивая члены СДНФ выявляем склеивающиеся пары
членов:
1-й и 2-й члены (результат склеивания
21
xx
⋅
);
1-й и 3-й члены (результат склеивания
31
xx
⋅
);
2-й и 4-й члены (результат склеивания
32
xx
⋅
).
Результаты операции склеивания вводим в выражение функции и
проводим операцию поглощения ими членов исходного выражения:
323121
321321321321321
),,(
xxxxxx
xxxxxxxxxxxxxxxf
⋅∨⋅∨⋅
∨
⋅
⋅
∨
⋅
⋅
∨⋅⋅∨⋅⋅=
Член
21
xx ⋅ поглощает те члены исходного выражения, которые
содержат
21
xx ⋅ , т.е. первый и второй. Эти члены вычеркиваются. Член
31
xx
⋅
поглощает первый и третий, а
32
xx
⋅
- второй и четвертый члены исходного
выражения.
Дальнейшее проведение операций склеивания и поглощения
оказывается невозможным, сокращенная форма выражения:
323121321
),,( xxxxxxxxxf ⋅∨⋅∨⋅=
.
Для перехода к минимальной форме строим импликантную матрицу.
321
xxx ⋅⋅
321
xxx
⋅
⋅
321
xxx
⋅
⋅
321
xxx ⋅
⋅
21
xx ⋅
x x
31
xx ⋅
x
x
32
xx ⋅
x
x
Ядро составляют импликанты
31
xx
⋅
и
32
xx
⋅
, которые перекрывают все
столбцы импликантной матрицы. Т.о. минимальная дизъюнктивная
нормальная форма заданной функции:
3231321
),,( xxxxxxxf ⋅∨⋅= .
Минимизация логических функций методом Квайна - Мак-Класки
Мак-Класки предложил прием, который на этапе нахождения
сокращенных ДНФ и КНФ упрощает процесс минимизации и, кроме того,
позволяет описать этот процесс для выполнения на ЭВМ. Прием
предусматривает следующую последовательность действий для получения
сокращенной ДНФ:
16
Рассмотрим применение метода Квайна на примере минимизации
функции, заданной таблицей истинности:
x1 0 0 0 0 1 1 1 1
x2 0 0 1 1 0 0 1 1
x3 0 1 0 1 0 1 0 1
F(x1, x2, x3) 1 1 1 0 0 1 0 0
Записываем СДНФ функции:
f ( x1 , x2 , x3 ) = x1 ⋅ x2 ⋅ x3 ∨ x1 ⋅ x2 ⋅ x3 ∨ x1 ⋅ x2 ⋅ x3 ∨ x1 ⋅ x2 ⋅ x3
Попарно сравнивая члены СДНФ выявляем склеивающиеся пары
членов:
1-й и 2-й члены (результат склеивания x1 ⋅ x2 );
1-й и 3-й члены (результат склеивания x1 ⋅ x3 );
2-й и 4-й члены (результат склеивания x 2 ⋅ x3 ).
Результаты операции склеивания вводим в выражение функции и
проводим операцию поглощения ими членов исходного выражения:
f ( x1 , x 2 , x3 ) = x1 ⋅ x 2 ⋅ x3 ∨ x1 ⋅ x 2 ⋅ x3 ∨ x1 ⋅ x 2 ⋅ x3 ∨ x1 ⋅ x 2 ⋅ x3 ∨
x1 ⋅ x 2 ∨ x1 ⋅ x3 ∨ x 2 ⋅ x3
Член x1 ⋅ x2 поглощает те члены исходного выражения, которые
содержат x1 ⋅ x2 , т.е. первый и второй. Эти члены вычеркиваются. Член x1 ⋅ x3
поглощает первый и третий, а x2 ⋅ x3 - второй и четвертый члены исходного
выражения.
Дальнейшее проведение операций склеивания и поглощения
оказывается невозможным, сокращенная форма выражения:
f ( x1 , x2 , x3 ) = x1 ⋅ x2 ∨ x1 ⋅ x3 ∨ x2 ⋅ x3 .
Для перехода к минимальной форме строим импликантную матрицу.
x1 ⋅ x2 ⋅ x3 x1 ⋅ x2 ⋅ x3 x1 ⋅ x2 ⋅ x3 x1 ⋅ x2 ⋅ x3
x1 ⋅ x2 x x
x1 ⋅ x3 x x
x2 ⋅ x3 x x
Ядро составляют импликанты x1 ⋅ x3 и x2 ⋅ x3 , которые перекрывают все
столбцы импликантной матрицы. Т.о. минимальная дизъюнктивная
нормальная форма заданной функции:
f ( x1 , x2 , x3 ) = x1 ⋅ x3 ∨ x2 ⋅ x3 .
Минимизация логических функций методом Квайна - Мак-Класки
Мак-Класки предложил прием, который на этапе нахождения
сокращенных ДНФ и КНФ упрощает процесс минимизации и, кроме того,
позволяет описать этот процесс для выполнения на ЭВМ. Прием
предусматривает следующую последовательность действий для получения
сокращенной ДНФ:
16
