Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
ГЛАВА ВТОРАЯ. МИНИМИЗАЦИЯ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ2-1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯВ § 1-7 показано, что любая функция алгебры логики может быть записана в виде ДСНФ или КСНФ. Покажем теперь, что такая запись в ряде случаев является неэкономной, для чего рассмотрим следующий пример. Пример 2-1. Пусть задана ДСНФ
Преобразуем эту ДСНФ следующим образом. Добавим еще один конъюнктивный член
Теперь преобразуем это выражение, используя сочетательное и распределительное свойства конъюнкции и дизъюнкции:
Используя свойство дизъюнкции Аналогично предыдущему делаем дальнейшие преобразовании
Из примера видна неэкономность совершенных нормальных форм для представления функций алгебры логики. Проблема простейшего представления функций сводится к проблеме выбора базиса и проблеме наиболее экономного представления функций в этом базисе. В настоящее время существенные результаты в решении задачи минимизации получены лишь для базиса, состоящего из отрицания, конъюнкции и дизъюнкции. Именно этот базис и будет рассматриваться на протяжении всей этой главы, за исключением последних параграфов. Для уточнения постановки задачи о минимизации дадим ряд определений. Определение Определение 2-2. Рангом элементарной конъюнкции называется число букв, образующих эту конъюнкцию. Определение 2-3. Дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ). Определение 2-4. Дизъюнктивная нормальная форма для функции Из этого определения следует, что в ДСНФ входят конъюнкции наибольшего возможного для данной функции ранга. Поэтому с точки зрения ранга конъюнкций, входящих в ДНФ, ДСНФ является наиболее сложной. Определение 2-5. Длиной ДНФ назовем число элементарных конъюнкций, образующих эту ДНФ. Длину ДНФ будем обозначать буквой I. Определение 2-6. Дизъюнктивная нормальная форма, имеющая наименьшую длину по сравнению со всеми другими ДНФ, эквивалентными данной функции, называется кратчайшей ДНФ (КДНФ). Определение 2-7. Дизъюнктивная нормальная форма, содержащая наименьшее число букв Определения, аналогичные определениям 14—20, можно дать и для случая конъюнктивных нормальных форм. В дальнейшем ограничимся рассмотрением класса дизъюнктивных нормальных форм. При необходимости читатель сам может повторить все нижеследующие утверждения для случая конъюнктивных нормальных форм.
Рис. 2-1. Еще раз подчеркнем, что мы рассматриваем лишь класс аналитических представлений для функций
где Вернемся вновь к геометрической интерпретации области определения функции алгебры логики. Для наглядности будем рассматривать функцию трех переменных. При этом в наших рассуждениях нигде не будем опираться на выбранное число аргументов, поэтому все полученные результаты будут носить универсальный характер. На рис. 2-1 показана область определения для произвольной функции трех переменных. Элементам куба сопоставлены конъюнкции различного ранга: вершинам куба сопоставляются конъюнкции третьего ранга, ребрам куба — конъюнкции второю ранга, граням куба — конъюнкции первого ранга. Отметим при этом, что сумма размерности геометрического эквивалента и ранга, сопоставляемой этому геометрическому эквиваленту конъюнкции, постоянна и равна числу аргументов функции (в нашем случае она равна трем). Каждый геометрический эквивалент меньшей размерности покрывается всеми геометрическими эквивалентами большей размерности. По аналогии будем говорить о покрытии конъюнкции большего ранга соответствующими конъюнкциями меньшего ранга. Так, например, конъюнкции
Для этой операции чаще употребляется термин склеивание, которого мы и будем придерживаться в дальнейшем. Условимся называть геометрические эквиваленты интервалами. Определение 2-8. Интервалом Например, конъюнкции соответствует множество вершин с координатами Теперь заметим, что при задании некоторой функции алгебры логики автоматически задается множество ее единичных значений. Вершины, соответствующие наборам аргументов, на которых функция принимает единичное значение, образуют множество Пример 2-2. На рис. 2-2 последовательно показано построение покрытия для функции
и преобразованной за счет вынесения за скобки
На рис. 2-2,а изображено покрытие интервалами третьего ранга, что соответствует представлению функции в ДСНФ, а на рис. 2-2, б - покрытие интервалами второго ранга, что соответствует представлению функции в виде упрощенной ДНФ. Таким образом, установлено взаимно однозначное соответствие между заданием функции в виде некоторой ДНФ и покрытием множества
Рис. 2-2. Будем теперь рассматривать задачу о минимизации данной функции алгебры логики как задачу о нахождении минимальной дизъюнктивной нормальной формы для этой функции. Если обозначить ранги всех интервалов, образующих покрытие для данной функции, через
характеризует собой суммарный ранг ДНФ, который численно совпадает с числом букв, входящих в данную ДНФ. Учитывая определение 2-7, можно сформулировать теперь задачу о минимизации как задачу о нахождении покрытия множества Определение 2-9. Интервал
Рис. 2-3.
Рис. 2-4. Пример 2-3. Для функции примера 2-1 максимальными интервалами будут интервалы Интервал
Определение 2-10. ДНФ, соответствующая покрытию множества Г всеми максимальными интервалами, называется сокращенной ДНФ (СДНФ). Пример 2-4. На рис. 2-4,а показано покрытие множества
Необходимо отметить, что СДНФ в общем случае не является минимальной. В этом можно убедиться, сравнив покрытия, приведенные на рис. 2-2, б и 2-4,а. Покрытие, показанное на рис. 2-2, б, дает МДНФ, а покрытие показанное на рис. 2-4,а — СДНФ. При этом число букв в МДНФ равно четырем, а в СДНФ — шести. Теорема 2-1. Минимальная ДНФ получается из сокращеной ДНФ путем выбрасывания из покрытия множества Для доказательства достаточно показать, что покрытие, соответствующее МДНФ, состоит только из максимальных интервалов. Это очевидно, так как в противном случае в МДНФ можно было бы заменить немаксимальные интервалы включающими их максимальными интервалами и число букв в ДНФ сократилось бы. Это противоречит тому, что рассматриваемая ДНФ является минимальной. Теорема доказана. Определение 2-11. Дизъюнктивная нормальная форма называется тупиковой, если при удалении из нее любой конъюнкции получаемая в результате ДНФ не является эквивалентной исходной. Для того чтобы показать отличие МДНФ от КДНФ, рассмотрим функцию
Этой функции соответствует покрытие, показанное на рис. 2-4,б. Заметим, что никакое сокращение числа максимальных интервалов для нее невозможно. Однако ясно, что минимальное покрытие состоит из грани (имеющейся на рисунке) и ребра, соединяющего эту грань с вершиной, соответствующей конъюнкции
|
1 |
Оглавление
|