33. Полиномиальные формы

С помощью двойственных законов дистрибутивности (32.18) и (32.19) любую функцию можно представить в полиномиальной форме относительно операции или .

Для начала рассмотрим пример. Пусть

. (33.1)

Эта функция записана в полиномиальной форме относительно .

Используя закон (32.19), функцию (33.1) можно преобразовать в полиномиальную форму относительно :

. (33.2)

Рассмотрим другой пример. Пусть

, (33.3)

поскольку третий член поглощается вторым. Далее, используя закон (32.18), получаем выражение

, (33.4)

которое дает полиномиальную форму относительно , тогда как представляет собой соответствующую полиномиальную форму относительно .

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

Максимальный одночлен. Пусть функция выражена в полиномиальной форме относительно . Об одночлене такой полиномиальной формы говорят, что он максимальный (употребляется также термин «собственный»), если он не поглощается никаким другим одночленом этой полиномиальной формы. Соответствующее определение дается максимальному одночлену в полиномиальной форме относительно .

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

Аналитической функции могут соответствовать несколько приведенных полиномиальных форм. Рассмотрим пример. Следующие две приведенные полиномиальные формы:

(33.5)

(33.6)

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

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

Пример. Функция

(33.7)

представлена в приведенной полиномиальной форме относительно . Соответствующая ей приведенная полиномиальная форма относительно имеет вид

. (33.8)

Тождественность двух функций нечетких переменных. Достаточное условие тождественности двух функций нечетких переменных состоит в том, чтобы их можно было привести к одной и той же приведенной полиномиальной форме относительно (соответственно относительно ). Необходимое и достаточное условие состоит в том, чтобы у этих функций была одна и та же таблица значений.

Теорема. Число различных приведенных полиномиальных форм относительно переменных конечно и равно верхней грани числа различных аналитических функций нечетких переменных.

Как можно видеть из следующего ниже перечня, эти приведенные полиномиальные формы представлены как элементы свободной дистрибутивной решетки с образующими и перечисляются тем же образом. Так, при существует 4 различные формы; при - 166, при - 7 828 532, ...; но это число различных форм всегда остается конечным, поскольку число элементов свободной дистрибутивной решетки с образующими всегда конечно, если конечно .

Перечисление всех приведенных форм нечетких переменных - нелегкая проблема. Для одной переменной это тривиально. Имеем

, (33.9)

т. е. четыре приведенные формы. Заметьте, что нужно отличать, например, от , поскольку

, если , и , если . (33.10)

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

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

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

1.Формы , содержащие один одночлен:

(33.11)

Здесь имеется приведенных форм, состоящих из одного одночлена.

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