2-9. ПРЕОБРАЗОВАНИЯ И МИНИМИЗАЦИЯ В БАЗИСЕ, СОСТОЯЩЕМ ИЗ ФУНКЦИИ ВЕББА ИЛИ ИЗ ФУНКЦИИ ШЕФФЕРА

Ранее было показано, чт.о функции Вебба и Шеффера образуют базисы, состоящие только из одной функции. Будем называть такие базисы монофункциональными.

В последнее время возник большой интерес к монофункциональным базисам. Поэтому рассмотрим их более подробно. В § 1-2 и 1-5 были введены двухместные функции Вебба и Шеффера. По аналогии с ними введем с помощью таблицы -местные функции Вебба и Шеффера:

При из этой таблицы получаются двухместные функции Вебба и Шеффера, а при обе функции вырождаются в функцию отрицания. Поэтому мы в дальнейшем будем вместо писать соответственно х.

Для введенных функций по-прежнему справедлив переместительный закон и несправедлив сочетательный закон.

По аналогии с (1-20) можно написать следующие соотношения:

При раскрытии скобок аналогично соотношениям (1-21) получим:

Заметим, что если или равны единице, то эти соотношения выразятся несколько иначе. Например, при

Наконец, приведем соотношения, показывающие связь между многоместными функциями Вебба и Шеффера:

Эти соотношения аналогичны соотношениям (1-22) и формулам де Моргана.

Справедливость всех вышеприведенных соотношений можно установить при помощи таблиц функций.

В дальнейшем мы в основном будем рассматривать базис, построенный на основе многоместной функции Вебба.

Рассмотрим равенство (1-25) из § 1-7. Из (1-25) легко получить:

если выбрать характеристические функции единицы для множества номеров наборов, на которых функция обращается в нуль. Применяя последнее из соотношений (2-20), получаем одну из двух совершенных нормальных форм в базисе Вебба:

Если использовать характеристические функции единицы для множества то получится другая совершенная нормальная форма, которая проще предыдущей, если у функции в таблице истинности нулей больше, чем единиц:

Если обращается в нуль только на одном наборе, то в правой части (2-24) останется только один инвертированный операнд. Если же обращается в единицу только на одном наборе, отрицание в правой части соотношения (2-25) исчезает.

Для получения аналогичных нормальных форм в базисе Шеффера можно использовать (1-28) и характеристические функции нуля.

Перейдем теперь к аналитическому выражению характеристических функций единицы в базисе Вебба. В § 1-7 было получено выражение

Если применить последнее из соотношений (2-20), то

и мы можем написать, что

и получить выражение для характеристической функции единицы:

при условии, что

Теперь мы можем сформулировать алгоритм перехода от табличного задания функции к ее записи в виде совершенной нормальной формы в базисе -местной функции Вебба вида, например, (2-24):

К Выбрать в таблице задания функции все наборы аргументов, на которых функция обращается в нуль.

2. Выписать термы типа (2-26), соответствующие этим наборам аргументов. При этом, если аргумент входит в данный набор как нуль, он вписывается без изменения. Если же входит в данный набор как единица, то вписывается его отрицание.

3. Все полученные выражения характеристических функций объединяются местной операцией Вебба, где — количество нулей заданной функции.

Пример 2-20. Построить совершенную нормальную форму вида (2-24) для следующей таблично заданной функции:

В соответствии с алгоритмом получаем:

Перейдем теперь к проблеме минимизации в монофункциональных базисах. Существует,два подхода проблеме минимизации: либо по аналогии с минимизацией в классе ДНФ строится специальный метод минимизации

для монофункционального базиса, либо минимизация производится в классе ДНФ, а затем строится специальный метод перехода от базиса конъюнкция, дизъюнкция, отрицание к монофункциональному базису. Рассмотрим сначала первый подход на примере минимизации в базисе, состоящем из функции Вебба.

Все определения из § 2-1 имеют свои аналоги для рассматриваемого базиса. Совершенной нормальной формой в дальнейшем будем считать выражение (2-24), операнды которого будут иметь наибольший возможный для данной функции ранг. Определение минимальной нормальной формы вполне аналогично определению 2-13.

Понятиям интервал и максимальный интервал из геометрической интерпретации области определения функции алгебры логики соответствовали понятия импликанта и простая импликанта при минимизации в классе ДНФ. В базисе Вебба соответствующие понятия будем называть инверсантой и простой инверсаной.

Инверсанта и функции характеризуется тем, что всегда из следует Очевидно, что все из (2-24) являются инверсантами заданной функции Отметим, что тоже является инверсантой функции

По аналогии с классическим базисом будем говорить, что выражение в базисе Вебба, операндами которого являются все простые инверсанты заданной функции, является сокращенной нормальной формой функции. Минимальная нормальная форма будет получаться из сокращенной выбрасыванием некоторых инверсантов. Определение тупиковой формы в рассматриваемом базисе формулируется по аналогии с определением 2-11 из того же § 2-1.

Прежде чем перейти к рассмотрению применения в базисе Вебба некоторых известных из классического базиса методов минимизации, рассмотрим эквивалентные преобразования, приводящие к операциям склеивания и поглощения в алгебре Вебба.

Через будем обозначать выражение, которое описывает -местную операцию Вебба над операндами.

Лемма. Если то эквивалентно которое получается из объединением в одном операнде любых операндов с помощью введения общего для них отрицания.

Другими словами,

где — произвольные термы и

Чтобы доказать справедливость леммы, рассмотрим все возможные случаи, полагая

1. Для все Но тогда и и в согласии с четвертым тождеством (2-20) обе стороны равенства (2-27) превращаются в

2. Среди имеется хотя бы одна единица. Но тогда и и в согласии с третьим тождеством из (2-20) обе стороны равенства (2-27) обращаются в нуль.

Введем теперь операции следующих типов: склеивания

неполного склеивания

(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.

Воспользуемся случаем показать одну возможность табличного расположения минитермов, преимущество которого состоит в большей наглядности. В этой таблице минитермы одного ранга образуют столбец, а различные группы выделены горизонтальными линиями:

Составление таблицы начинается с первого столбца для минитермов четвертого ранга, которые соответствуют нулям функции. Слева показаны номера групп только для этого столбца.

По неотмеченным наборам строится сокращенная нормальная форма, учитывая что нулю в наборе соответствует а единице —

Как и в предыдущем примере, единственная переменная вырожденного минитерма инвертируется.

В данном случае сокращенная нормальная форма совпадает с минимальной. Если бы этого не было, то пришлось бы строить таблицу инверсант и производить расстановку меток обычным способом.

Отметим, что минимальная ДНФ этой же функции более сложна:

Рассмотрим теперь второй из подходов к минимизации, о котором мы говорили выше. Напомним, что в этом случае минимизация проводится в классическом базисе, а затем полученное минимальное выражение переводится в монофункциональный базис таким образом, чтобы по возможности сохранялась минимальность. Е. И. Пупыревым было показано, что существует такой метод перехода от минимальной ДНФ к ее представлению в монофункциональном базисе, при котором сложность вновь получаемого представления либо минимальна в данном монофункциональном базисе, либо отличается

От этой сложности на одну букву. Этот результат говорит еще раз о тесной связи этих базисов между собой. Метод перехода, предложенный Е. И. Пупыревым, указан в литературе, приведенной в конце книги.