М атрица Карно.
Минимизацию при помощи матрицы Карно проиллюстрируем примером формулы с четырьмя переменными, так как в этом случае метод окажется наиболее эффективным.
Матрицу будем составлять следующим образом. Построим таблицу с четырьмя столбцами и четырьмя строками и обозначим столбцы конъюнкциями XY, XY, XY, XY, строки – конъюнкциями ZU, ZU, ZU, ZU:
| XY | XY | XY | XY |
ZU |
|
|
|
|
ZU |
|
|
|
|
ZU |
|
|
|
|
ZU |
|
|
|
|
П ересечение одного столбца и одной строки дает четырехчленную конъюнкцию, содержащую все четыре переменных, то есть определяет один член совершенной дизъюнктивной нормальной формы. Таблица позволяет получать все 16 таких членов.
XYZU; XYZU; XYZU; XYZU; XYZU, и т.д.
Таблица составлена так, что члены СДНФ, соответствующие соседним двум клеткам в столбце или строке, отличаются только одной переменной. Соседними в этом смысле являются также верхняя и нижняя клетки одного и того же столбца, левая и правая клетки одной и той же строки.
При минимизации формулы этим методом нужно ее сначала привести к совершенной дизъюнктивной нормальной форме.
Пусть нам дана следующая СДНФ:
XYZUXYZUXYZUXYZUXYZUXYZUXYZU XYZUXYZUXYZU.
В клетках таблицы ставим звездочки, соответствующие каждой четырехчленной конъюнкции, и соединяем звездочки, стоящие в соседних клетках, обведя их кривой. В каждой группе конъюнкций исключаем меняющиеся переменные.
| XY | XY | XY | XY |
ZU | * |
|
| * |
ZU | * | * | * | * |
ZU |
| * | * |
|
ZU | * |
|
| * |
Тогда четыре обведенных звездочки, расположенные в середине таблицы, дают YU (исключаются X и Z). Четыре верхние звездочки, расположенные по обе стороны таблицы, определяют YZ. Две нижние звездочки выражают YZU (исключается только одна переменная X).
Итак, минимальной дизъюнктивной нормальной формой нашей формулы является:
YUYZYZU.
Вынесение Y за скобку сокращает число контактов на единицу:
YUY(ZZU).
П риведем соответствующую контактную схему:
Она содержит лишь шесть контактов вместо 40, которые потребовались бы, если составлять схему непосредственно по СДНФ.
Использование матрицы Карно для минимизации формулы с двумя и тремя переменными малоэффективно, так как в этом случае лучше упростить формулы при помощи тождественных преобразований или графическим методом.
Что касается формул с пятью переменными, то для их упрощения использование матрицы Карно вполне возможно, причем существует несколько способов такого применения. Остановимся на одном из них, являющемся более наглядным в сравнении с другими.
Пусть дана следующая формула своей совершенной дизъюнктивной нормальной формой:
XYZTUXYZTUXYZTUXYZTUXYZTUXYZTU XYZTUXYZTUXYZTUXYZTUXYZTU.
Составим таблицу, в которой столбцы соответствуют трехчленным конъюнкциям переменных X, Y, Z и их отрицаниям, строки двухчленным конъюнкциям T, U и их отрицаниям. Наборы значений расположены так, что соседние клетки в столбце или строк отличаются друг от друга лишь одной цифрой. Звездочки, поставленные в клетках, соответствуют членам совершенной дизъюнктивной нормальной формы.
-
XYZ
000
001
011
010
110
111
101
100
TU
00
*
*
01
*
*
11
*
*
*
*
10
*
*
В соответствии с этой таблицей, составим две новые таблицы – одну для случая X=0, другую – для X=1.
|
| YZ |
|
| |
|
| 00 | 01 | 11 | 10 |
TU | 00 |
|
|
| 1 |
01 |
|
| * | * | |
| 11 |
| 2 | * | * |
| 10 |
| * |
|
|
X=0 |
-
YZ
3
00
01
11
10
TU
00
*
*
01
11
2
*10
*
X=1
Теперь уже значение X относится ко всей таблице, поэтому столбцы будут отражать лишь значения переменных Y и Z. Иначе говоря, первые цифры трехзначных чисел, обозначающих столбцы, выпадают и мы как бы получаем матрицы для четырех переменных Y, Z, T и U.
Четыре звездочки группы 1 в первой матрице означают исключение переменных Z и T, и вместо соответствующих четырех членов СДНФ остается один член, содержащий конъюнкцию YU. Во второй матрице на соответствующих столбцах звездочек не имеется, следовательно, переменная X не исключается.
В первой и второй матрицах в столбцах, помеченных набором 01, на одних и тех же местах имеются две звездочки (группа 2). Поскольку для первой матрицы X=0, а для второй X=1, то переменная X исключается. Меняются также значения второй цифры в наборах, отмечающих строки, исключается переменная U. Следовательно, вместо четырех членов СДНФ, соответствующих группе 2, остается член YZT.
Звездочки группы 3 находятся в одной и той же строке, поэтому переменные T и U не исключаются. В обозначениях столбцов меняется первая цифра, следовательно, исключается Y. Переменная X сохраняется, так как в первой матрице соответствующих звездочек не имеется. Таким образом, вместо двух членов СДНФ остается член XZTU.
Таким образом, минимальная дизъюнктивная нормальная форма данной формулы имеет вид:
XYUYZTXZTU.
Матрица Карно может применяться также для минимизации формул, содержащих шесть переменных, для формул же с большим количеством переменных она практически уже не используется ввиду громоздкости построений.
- Хакасский государственный университет им. Н.Ф.Катанова математическая логика
- Содержание
- Литература.
- Введение.
- Алгебра высказываний.
- §1. Высказывания и операции над ними.
- Упражнения.
- §2. Формулы алгебры высказываний. Виды формул.
- Упражнения.
- §3 Логическое следствие
- Основные методы установления верности логического следствия:
- Упражнения
- §4 Равносильность формул алгебры высказываний.
- Упражнения
- §5 Нормальные формы для формул алгебры высказываний.
- Отыскание нормальных форм Упражнения.
- Применение нормальных форм.
- Нахождение следствий из посылок.
- Нахождение посылок для данных следствий.
- § 6. Булевы функции (функции алгебры логики).
- Классы булевых функций.
- Упражнения.
- §7. Алгебра логики и релейно-контактные схемы.
- Анализ релейно-контактных схем. Упражнения.
- Синтез релейно-контактных схем.
- §8. Особые методы минимизации.
- Графический метод.
- М атрица Карно.
- Метод неопределенных коэффициентов.
- М етод минимизирующих карт.
- М етод Квайна.
- Упражнения.
- Примерные варианты контрольных работ.