2-8. ПОЛИНОМИАЛЬНЫЕ ПРЕДСТАВЛЕНИЯ И ИХ МИНИМИЗАЦИЯ

Определение 2-14. Полиномиальным представлением функций алгебры логики будем называть сумму по модулю два любого конечного множества попарно различных элементарных конъюнкций и констант.

В гл. 1 рассматривались два частных случая полиномиальных представлений ФАЛ: полиномиальная совершенная нормальная форма и полином Жегалкина.

Представим в виде ПСНФ

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

Если в (2-14) представить х как произвести умножение (конъюнкцию) и применить (1-16), то получим полиномиальное представление заданной функции в виде полинома Жегалкина. Любая функция имеет единственное представление такого вида.

Кроме представления (2-14), существует еще один способ полиномиального представления функций алгебры логики, заданных таблично.

Введем следующее обозначение:

Определение 2-15. Выражение назовем производной функции алгебры логики относительно переменной

Исходя из (2-15), можно доказать следующие свойства производной:

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

где А и В — некоторые полиномы.

Применяя (2-15), получаем:

Если для (2-17) найти частную производную, то, учитывая первое и третье соотношения из (2-16), получаем:

Условие того, что функция не будет существенно зависеть от переменной (определение 1-3), может быть теперь представлено в виде

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

где могут принимать независимо друг от друга значения 0 или 1; представляет произведение тех

переменных, которым в выраженном в двоичной системе счисления, соответствует единица; есть производная функция относительно всех переменных, найденная до подстановки значений входящих в представляем произведение членов для тех переменных, которые входят в Например, для функции пяти переменных числу соответствуют

Разложение (2-18) непосредственно вытекает из следующего представления любой функции алгебры логики:

где может принять любое из значений 0 или 1.

Доказать (2-19) можно простой проверкой.

Пример 2-13. Функция на основании (2-18) может быть представлена в виде

где

Разложение (2-18) позволяет при найти полином функции, заданной таблично. Особенностью такого полинома является то, что одна и та же переменная входит во все члены (элементарные конъюнкции) или с отрицанием, или без него. Если выбрать то можно получить полином Жегалкина этой функции.

Пример 2-14. Найти аналитическое представление функции двух переменных, заданной таблицей.

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

где

Если выбрать то

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

Пример 2-15. Если для функции примера 2-14 выбрать то получим

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

Метод неопределенных коэффициентов

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

Пример 2-16. Пусть задана функция

Задавая всевозможные наборы значений аргументов, получим следующую систему уравнений:

Задание некоторой функции определяет значение правых частей этой системы. Если на некотором наборе функция равна нулю, то для удовлетворения уравнения необходимо приравнять нулю все коэффициенты К, входящие в левую часть, кроме четного числа коэффициентов, равных единице (нуль считаем четным числом.). Эти коэффициенты подбираем так, чтобы они определяли члены возможно меньшего ранга. В уравнениях, в которых справа стоят единицы, необходимо, чтобы слева нечетное число коэффициентов было отличным от нуля. Такой прием следует из свойств (1-16).

Для заданной функции получим Выбранные в каждом уравнении коэффициенты обведены в рамку.

Геометрический метод

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

Пример 2-17. Для функции покрытие представлено на рис. 2-7; .

Метод импликантных таблиц

Этот метод представляет модификацию метода Квайна—Мак-Класки (см. § 2-4). Все минитермы записываются в виде их двоичных номеров. Кроме минитермов, на которых заданная функция принимает значение 1 (их в дальнейшем будем называть А-минитермами), в таблицу импликант включаются и некоторые из минитермов, на которых функция принимает значение 0.

Они определяются следующим образом: производим попарное сравнение всех Л-минитермов.

Рис. 2-7.

Если в сумме имеются две единицы, то берется любой из минитермов и пишутся четыре минитерма, которые получаются из или пэдстановкой на местах, соответствующих единицам, всех возможных комбинаций из Он 1. Если некоторые из полученных минитермов не Л-минитермы, то они будут искомыми минитермами. Их будем называть В-минитермами.

Пример 2-18.

Затем производится попарное склеивание всех А и В-минитермов. При этом из-за свойства (1-16) не будем отмечать минитермы, для которых произошло склеивание.

Пример 2-19. Для функции примера 2-18 таблица импликант имеет вид:

(см. скан)

В таблицу импликант включаются все А и В-минитермы, причем А-минитермы и В-минитермы разделяются, а в строках включаются все возможные полученные импликанты (включая А и В-минитермы).

Исследуется таблица импликант. Выбирается такая совокупность импликант, которая покрывает все столбцы Л-минитермов нечетное число раз и некоторые столбцы В-минитермов — четное число раз и которая содержит минимальное возможное число букв.

Недостатком приведенных выше методов является то, что при увеличении числа переменных перебор стано вится большим.

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