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