8-5. ПОЛИНОМИАЛЬНЫЕ ПРЕДСТАВЛЕНИЯ В k-ЗНАЧНОЙ ЛОГИКЕ

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

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

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

где а — константа, представляют одноместные операторы над переменными.

В общем случае элементарное произведение имеет вид:

причем некоторые из членов могут отсутствовать.

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

где знак означает суммирование по модулю представляет сокращенную запись для

Выражение (8-25) назовем формулой разложения функций по характеристическим функциям переменной Мы ее можем написать в более общем виде:

где может принимать любое из значений представляет наименьший неотрицательный вычет по модулю

Покажем справедливость соотношения (8-26). Для этого докажем, что функции, стоящие в левой и правой частях соотношения (8-26), совпадают для любого значения

Пусть Из всех членов, стоящих в правой части (8-26), только в одном характеристическая функция принимает значение 1. Это будет функция с индексом Таким образом, всегда и с левой и с правой стороны получаем

Будем искать представление любой функции одной переменной в -значной логике в виде полинома

где - константы, a - одноместные операторы над представленные в общем виде в таблице, приведенной ниже.

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

Выражение (8-27) эквивалентно следующей системе сравнений, получаемой в результате подстановки всех возможных значений

Покажем, что условие единственности представления любой функции одной переменной в -значной логике в виде (8-27) является:

т. е. числа и должны быть взаимно простыми, где — определитель системы (8-28):

Система сравнений (8-28) равносильна системе

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

Из теории сравнений известно, что любое из сравнений первой степени (8-28) имеет единственное решение по если откуда следует наше утверждение.

В качестве примера приведем следующую систему операторов:

Можно показать, что определитель этой системы операторов всегда принимает значение 1 при любом

Определяя из сравнений (8-30) коэффициенты характеристических функций получаем:

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

Подставляя значения характеристических функций (8-31) в формулу разложения (8-26), получаем:

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

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

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

Теперь формула разложения (8-32) принимает вид:

Исходя из определения производных (8-33), легко доказать следующие их свойства:

1. Если

2. Если где — постоянная, то

Покажем, что любую функцию -значной алгебры можно разложить в ряд вида

где с представляет собой произведение членов

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

Для числу соответствует

Пример 8-5. Для полином имеет в самом общем случае вид:

Для доказательства разложения (8-35) применим метод математической индукции. При разложение имеет место на основании (8-34). Предположим, что оно имеет место для и покажем, что оно будет иметь место и при

Разложим функции переменной на основании (8-34):

Но, по предположению, каждую из функций можно разложить в ряд по первым переменным. Тогда

Если разложение (8-35) не будет содержать производные относительно свободного члена, которые для этого случая не определяются. Следовательно,

где а отличается от в том, что в нем нет членов

При разложения (8-35) и (8-36) позволяют найти коэффициенты полинома по заданной таблице истинности функций. Выбор тех или иных значений дает возможность отыскать полином с минимальным числом букв.

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

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

Применяя критерий (8-29), находим, что этому условию удовлетворяют 64 функции одной переменной в четырехзначной логике. Введенное понятие полиномиального представления в этом случае расширяется за счет того, что в элементарном произведении переменная и, или операторы могут иметь некоторую степень.

Нетрудно видеть, что одноместные операторы можно представить следующим образом:

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

Понятие полиномиального представления можно рассматривать в более общем виде, если вместо (8-27) искать представление любой функции одной переменной в виде

Для такого представления полученное условие (8-29) также остается действительным. Понятие элементарного

произведения расширяется тем, что оно будет содержать произведение некоторых (или всех) операторов

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

При простом модуле из теоермы Ферма для сравнений следует:

Умножая левую и правую части этого сравнения на и прибавляя 1, получим:

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

Отсюда получаем:

так как становится равным нулю только при

После того как в (8-38) произведено возведение в степень, умножение и сокращение, получаются полиномы характеристических функций. Степень этих полиномов не будет больше что следует из свойств сравнений и что видно из (8-38).

Рассмотрим более общий случай представления характеристических функций полиномами. Выражение (8-38) можно записать и в виде

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

При этом для каждой переменной значение можно выбрать произвольным образом (см. (8-39)]. От выбора значений будет зависеть число членов полинома, что дает возможность частичной минимизации.

Пример 8-6. При и числе переменных, равном двум, полином имеет вид:

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

Возводя в степень по биномиальной формуле выражение (8-39) и подставляя в (8-25) значения получаем:

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

где

Назовем выражение (8-41) производной фунции относительно Из самого способа определения производной очевидно, что выражение (8-41) эквивалентно выражению (8-33), где Нетрудно также видеть, что представление в виде полинома по степеням является частным случаем (8-27). Определитель представляет в этом случае хорошо известный определитель Вандермонда.

Пример 8-7. Для выражение (8-43) дает Это выражение совпадает с производной функции алгебры логики {см. (2-15), § 2-8].

Пример 8-8. Для выражение (8-40) имеет вид:

По формуле (8-41) получаем следующие определения производных в трехзначной логике:

Исходя из формулы разложения (8-12), получаем разложение в ряд вида (8-36).

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

Разложение (8-36) при для можно представить в виде

где

Множество всех функций переменных, представленных в виде (8-42), дает — димензиональное векторное пространство над полем чисел Базис этого векторного пространства составляют

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

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

Отсюда

где

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

Отсюда делаем вывод, что получили новый базис, имеющий вместо вектора а вектор

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

Будем говорить, что -значная логическая функция представляется полиномом

по модулю если

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

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

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

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

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

Теорема 8-8. Если то -нормированный нулевой полином по модулю

Действительно,

Далее имеем

что и требовалось доказать.

Легко доказать и обратное утверждение.

Теорема 8-9. Если — нор мированный нулевой полином по модулю то

Обозначим символом наименьшее целое положительное число, удовлетворяющее условию Тогда

Так как

— нормированный нулевой полином по модулю Но так как то не существует нормированного нулевого полинома по модулю степени, меньшей Пусть — полином, представляющий по модулю Вычитанием из полинома нормироваииого нулевого полинома

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

Заметим, что что следует из определения

Вычисление можно производить по следующей рекуррентной формуле.

Если

Действительно, так как то

Но если где

Из последнего равенства и того, что следует справедливость показываемой формулы.

Используя равенство и доказанную рекуррентную формулу, составим таблицу значений

(см. скан)

Пусть теперь разложение на взаимно простые множители, тогда справедлива следующая формула:

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

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

что и требовалось доказать.

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

Перейдем к вычислению или — простое число), для чего докажем несколько вспомогательных утверждений.

Теорема 8-10. Произвольный, полином , не Являющийся нуль-полиномом, имеет степень

Действительно, для утверждение очевидно. Пусть утверждение справедливо для и допустим, что для оно не верно, т. е. предположим, что существует полином

Тогда для всех таких, что полином

принадлежит .

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

Заметим, что лолином степени

представляет функцию, тождественно равную нулю по модулю что следует из теоремы Ферма.

Пусть — полином степени старший коэффициент которого взаимно прост с и пусть при этом старшие коэффициенты всех полиномов из степень каждого из которых меньше или равиа делится на Все функции из класса можно представить полиномами степени, меньшей или равной в чем можно убедиться, используя теорему о делении с остатком. Если то, очевидно, Теорема 8-11. Если

где удовлетворяет неравенству то все коэффициенты делятся на Каждый коэффициент можно представить в виде и пусть для определенности

Тогда полином

Так как то существует полином

Тогда полином

Полином из равен

Старший коэффициент этого полинома взаимно прост с поэтому Но так как по условию то откуда или

Последнее и означает, что можно представить в виде

Если удовлетворяет неравенству то существует некоторый полином вида

Действительно, из следует существование полинома

откуда

Теорема 8-12 Пусть удовлетворяет неравенствам . Пусть далее Тогда всякий полином вида не может принадлежать

Предположим, противное: пусть По доказанному откуда

Так как

Но тогда Полученное противоречие доказывает сформулированное утверждение.

Теорема 8-13. Для любой функции существует один и только один представляющий эту функцию полином степени такой, что

Так как , то представляется некоторым полиномом степени

Путем последовательного вычитания многочленов

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

Допустим, что два различных полинома, удовлетворяющих условиям теоремы, задают функцию Тогда их разность будет многочленом из степени Пусть I удовлетворяет неравенствам

Тогда и по теореме 8-12 полином не может принадлежать Полученное противоречие доказывает утверждение.

Так как мощность класса всех полиномов, удовлетворяющих условию теоремы 8-13 равна то получим следующую основную формулу:

Положим тогда формула перепишется более компактно

Пусть теперь функция представима в виде полинома по модулю Рассмотрим теперь произвольный набор значений аргументов функции

Каждое заменим сравнимым с ним вычетом взятым из полной системы наименьших неотрицательных вычетов по модулю Значение функции равное заменим сравнимым с ним вычетом из системы наименьших неотрицательных вычетов то модулю Этот последний обозначим через Тем самым мы определим функцию из Описанный способ построения функции естественным образом определяет отображение

Разобьем множество на классы: в один и тот же класс будем относить те элементы образы которых при отображении совпадают. В каждом классе зафиксируем по одному элементу. Обозначим через множество фиксированных представителей этих классов. Ясно, что

Теорема 8-14. Для любой функции существует один и только один полином вида

где .

Как следствие этого утверждения, получим следующую формулу:

Представляя полииомы по модулю в системе остаточных классов с основаниями легко устанавливается справедливость следующей формулы:

которая вместе с формулами (8-44), (8-45) позволяет вычислить мощность класса -значных логических функций от переменных, представимых полиномами по модулю

В качестве примера подсчитаем количество функций, представимых полиномами по модулю 24-32.

По таблице значений находим:

Применяя формулу (8-43), вычисляем значения

Подставляя эти значения в формулу (8-44), находим:

а по (8-45) получаем: