Минимизация сложных высказываний
Как попасть из исходной точки в другую вершину, например в ту, которая обозначена цифрой /? Путь к вершине / проходит последовательно вдоль ребер, совпадающих с направлениями стрелок А, В и С (разумеется последовательность может быть и другой). И в этом случае существует обратное соответствие: вершинам четырехмерного куба соответствуют строго определенные четырехбуквенные произведения. Например… Читать ещё >
Минимизация сложных высказываний (реферат, курсовая, диплом, контрольная)
Совершенные дизъюнктивная и конъюнктивная формы применяются при выполнении задач минимизации сложных логических высказываний. Под минимизацией понимают такие действия над данной формулой, в результате которых получают новую формулу, содержащую меньшее количество букв.
Рассмотрим один из способов минимизации, при котором используется геометрический подход [9].
Представим себе куб (рис. 3.14, а), вдоль ребер которого осуществляется движение. Направления движения указаны стрелками Л, В и С. Исходным пунктом служит вершина куба, к которой направлены стрелки (если пользоваться понятиями аналитической геометрии, можно сказать, что начало системы координат находится в этой вершине).
Рис. 3.14. Куб: а) х = АВС;
Как попасть из исходной точки в другую вершину, например в ту, которая обозначена цифрой /? Путь к вершине / проходит последовательно вдоль ребер, совпадающих с направлениями стрелок А, В и С (разумеется последовательность может быть и другой).
Рассмотрим еще две вершины: 2 и 3 (рис. 3.14, б). В вершину 2 можно попасть, последовательно двигаясь по направлениям А и В. Отсутствие движения по направлению С обозначаем как С. Вершине / соответствует тройка букв А, /?, С, вершине 2 — АВС, а вершине 3 — АВС.
б) х = АВС + АВС
Если дано произвольное сложное высказывание, написанное в СДНФ, в которую входят трехбуквенные произведения, то каждому произведению соответствует определенная вершина куба. Справедливо и обратное: каждой вершине куба соответствует произведение трех простых высказываний.
Например, высказывание.
изображается точками /, 2, 3 и 4 куба (рис. 3.15, а), а точкам куба на рис. 3.15, б соответствует формула.
Рассмотрим куб на рис. 3.15, в, на котором отмечены две точки: У и 2. Этим точкам соответствует сложное высказывание.
В этом сложном высказывании можно вынести АВ за скобки, т. е. произвести слияние по букве С:
Для сложного высказывания.
изображенного на рис. 3.15, б, можно выполнить слияние по С (для первого и второго произведений) и по А (для третьего и четвертого произведений):
Рис. 3.15. Куб: а) х = АВС + АВС + АВС + АВС; б) х = АВС + АВС + АВС + АВС; в) х=АВС+АВС.
На основании рассмотренных примеров можно написать правило минимизации сложных трехбуквенных высказываний, написанных в СДНФ:
- 1. Отмечаем вершины куба, которые соответствуют трехбуквенным произведениям.
- 2. Если какие-либо две из отмеченных вершин лежат на одном ребре, для этих вершин вместо двух трехбуквенных произведений записываем одно двухбуквеннос (производим слияние по букве, для которой соответствующее ей направление совпадает с направлением ребра, к которому принадлежат отмеченные вершины).
На практике могут встречаться сложные высказывания, отдельные произведения которых содержат по четыре буквы. И в этом случае может быть применен геометрический подход к минимизации сложных высказываний.
Как известно, куб имеет три измерения: ширину, высоту и глубину, которые обозначим буквами А, В и С, соответствующими простым высказываниям. Поэтому введем в рассмотрение искусственный куб с четырьмя измерениями (рис. 3.16, а). Четвертое измерение получается при движении внутрь от вершин большого куба к соответствующим вершинам малого куба.
Рассмотрим использование четырехмерного куба для изображения сложных высказываний. Пусть имеется высказывание.
которое дано в СДНФ. Четырехбуквенные произведения соответствуют точкам 1 и 2. И в этом случае движение совершается по стрелкам А, В и С; кроме того, поскольку в четырехбуквенном произведении содержится буква Д имеется движение от достигнутой вершины большого (внешнего) куба внутрь к соответствующей вершине малого (внутреннего) куба. Если в четырехбуквенном произведении содержится буква Д то никакого движения внутрь нет.
Рис. 3.16. Четырехмерный куб: а) х = A BCD + ABCD; б) x = ABCD + ABCD+ABCD + ABCD + ABCD.
И в этом случае существует обратное соответствие: вершинам четырехмерного куба соответствуют строго определенные четырехбуквенные произведения. Например, кубу на рис. 3.16, б соответствует логическая формула
Правило минимизации сложных логических высказываний, содержащих четырехбуквенные произведения, заключается в следующем:
1. Отмечаются вершины куба, которые соответствуют четырехбуквенным произведениям.
2. Если какие-либо две из отмеченных вершин лежат на одном ребре (здесь в понятие «ребро» включается и мысленная линия, которая соединяет соответствующие вершины двух кубов), то для такого ребра вместо двух четырехбуквенных произведений пишется одно трехбуквенное (выполняется слияние в направлении буквы, для которой соответствующее ей направление совпадает с ребром с отмеченными вершинами).
Если сначала произвести слияние по букве Д то получится обыкновенный трехмерный куб.
В качестве примера минимизации рассмотрим сложное высказывание которому соответствует куб на рис. 3.17, а.
Рис. 3.17. Куб: а) х = ABCD+ ABCD + ABCD + ABCD; б) х= АВС + АВС+АВС+АВС + АВС + АВС.
Минимизация осуществляется с использованием ребер, соединяющих отмеченные вершины. На рис. 3.17, а используются два ребра между точками 1−2 и 3−4. Для этих ребер можно записать.
что по существу представляет собой слияние по буквам В и С. Окончательно получаем л = АСD + ABD.
Несмотря на простоту геометрического подхода к минимизации, в некоторых случаях конечный результат зависит от выбора ребер, по которым производится слияние. Рассмотрим для примера сложное высказывание, представленное следующей таблицей истинности:
А | В | с. | X |
Тому же высказыванию, записанному в СДНФ,.
соответствует куб на рис. 3.17, в.
Выполнив слияние по ребрам 1−3, 2−4, 5−6, получим.
или
Если выполнить слияние по ребрам 1−2,2−5, 3−4 и 4−6, то получим.
В первом случае слияние выполнено по трем ребрам, а во втором — по четырем. Во втором случае получен более простой результат. Результаты эквивалентны. Проверку можно выполнить, составив таблицу истинности.