Метод неопределенных коэффициентов.
Метод заключается в том, что для заданной формулы мысленно составляется дизъюнктивная нормальная форма, содержащая всевозможные конъюнкции из одного, двух и т. д. и наконец, всех переменных, входящих в формулу. Рассмотрим формулу с тремя переменными X, Y и Z.
В соответствии с каждой конъюнкцией дизъюнктивной нормальной формы коэффициент (какую-либо букву, например A) будем записывать с нижними и верхними индексами следующим образом:
вхождения X, Y и Z в конъюнкцию будем отмечать цифрами соответственно 1, 2 и 3, ставя их в качестве нижних индексов;
если значение переменной в данной конъюнкции 0 или 1, на соответствующем месте ставим 0 или 1 в качестве верхних индексов.
Например, конъюнкциям X, XY, XZ, YZ, XYZ, XYZ соответствуют коэффициенты , , , , , .
Пусть некоторая формула задана таблицей:
-
X
Y
Z
Значение формулы
0
0
0
0
0
0
1
0
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
1
1
1
1
0
Для набора значений переменных, указанных в каждой из строк таблицы, составим сумму (дизъюнкцию) коэффициентов, соответствующих всевозможным конъюнкциям, которые только можно образовать, и приравняем ее значению формулы при данном наборе:
| |
| |
| |
| |
| |
| |
| = | 0; |
| |
| |
| |
| |
| |
| |
| = | 0; |
| |
| |
| |
| |
| |
| |
| = | 1; |
| |
| |
| |
| |
| |
| |
| = | 0; |
| |
| |
| |
| |
| |
| |
| = | 1; |
| |
| |
| |
| |
| |
| |
| = | 0; |
| |
| |
| |
| |
| |
| |
| = | 1; |
| |
| |
| |
| |
| |
| |
| = | 0. |
Суммы равны 0 тогда и только тогда, когда все слагаемые равны 0, выпишем коэффициенты, равные 0.
= = = = = = = = = = = = = = = = = = = =0.
В оставшихся суммах, которые равны единице, исключим слагаемые, равные 0:
=1;
=1;
=1;
Таким образом, получаем следующую ДНФ:
YZXYZXZXYZXZYZXYZ;
т. е. YZXYZXZXYZXYZ.
Согласно закону поглощения нетрудно заключить, что полученная формула равносильна формуле YZXZ, которая и является минимальной ДНФ формулы, заданной нашей таблицей.
Прежде чем построить схему, вынесем Z за скобку: (XY)Z.
- Хакасский государственный университет им. Н.Ф.Катанова математическая логика
- Содержание
- Литература.
- Введение.
- Алгебра высказываний.
- §1. Высказывания и операции над ними.
- Упражнения.
- §2. Формулы алгебры высказываний. Виды формул.
- Упражнения.
- §3 Логическое следствие
- Основные методы установления верности логического следствия:
- Упражнения
- §4 Равносильность формул алгебры высказываний.
- Упражнения
- §5 Нормальные формы для формул алгебры высказываний.
- Отыскание нормальных форм Упражнения.
- Применение нормальных форм.
- Нахождение следствий из посылок.
- Нахождение посылок для данных следствий.
- § 6. Булевы функции (функции алгебры логики).
- Классы булевых функций.
- Упражнения.
- §7. Алгебра логики и релейно-контактные схемы.
- Анализ релейно-контактных схем. Упражнения.
- Синтез релейно-контактных схем.
- §8. Особые методы минимизации.
- Графический метод.
- М атрица Карно.
- Метод неопределенных коэффициентов.
- М етод минимизирующих карт.
- М етод Квайна.
- Упражнения.
- Примерные варианты контрольных работ.