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

                        (33.12)

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

3. Формы , содержащие три одночлена, для которых справедливо сделанное выше замечание о неприводимости:

    (33.13)

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

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

       (33.14)

Таким образом, существует  приведенных форм, состоящих из четырех одночленов.

5. Формы , содержащие пять одночленов:

(33.15)

Существует шесть приведенных форм, содержащих пять одночленов.

6. Формы , содержащие шесть одночленов:

                  (33.16)

Имеется только одна приведенная форма, содержащая шесть одночленов.

Всего имеем:

приведенных полиномиальных форм.