8-4. ПРЕДСТАВЛЕНИЕ k-ЗНАЧНЫХ ФУНКЦИЙ В ВИДЕ НОРМАЛЬНЫХ ФОРМ

Рассмотрим конъюнкцию

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

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

Справедливость теоремы очевидна. Представление функции в соответстви с теоремой 8-4 будем называть -значной дизъюнктивной совершенной нормальной формой (КДСНФ).

Пример 8-2. Записать в ТДСНФ функцию, заданную следующей таблицей:

В соответствии с (8-11) выписываем ТДСНФ данной функции, опуская те наборы на которых

Рассмотрим теперь дизъюнкцию

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

Теорема 8-5. Любая функция -шачной логики может быть представлена в следующей форме:

Это представление носит название -значной конъюнктивной совершенной нормальной формы (ККСНФ).

Пример 8-3. Записать в ПКСНФ (пятизначной КСНФ) функцию, определенную следующей таблицей:

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

Используя соотношение (8-12), пишем ПКСНФ:

Функции конъюнкции и дизъюнкции в -значной логике имеют свойства, аналогичные свойствам двузначных

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

Это позволяет исключить из полной системы, состоящей из характеристических функций, констант, дизъюнкций, инверсии и конъюнкции, либо дизъюнкцию, либо конъюнкцию. Соотношение (8-10) показывает, что инверсия также может быть исключена при сохранении конъюнкции и дизъюнкции. Отметим, что доказательство теоремы 8-4 соответствует доказательству полноты системы Россера и Тьюкетта.

Полная система Россера и Тьюкетта является прямым аналогом двузначных представлений в виде ДСНФ и КСНФ. Проблема минимизации ставится здесь также аналогичным образом. Более подробно этот вопрос будет рассмотрен в гл. 9, для случая трехзначной логики.

Перейдем теперь к рассмотрению аналитического представления в системе, предложенной Н. Н. Айзенбергом и 3. Л. Рабиновичем.

Операцию, определенную в соответствии с (8-8), назовем квазиконъюнкцией и будем обозначать значком а операцию, определенную с помощью (8-9), — квазидизъюикцией и будем обозначать ее значком V Эти операции обладают следующими свойствами, которые могут доказаны читателями самостоятельно:

Введем обозначение для -кратного применения циклического отрицания к . Операцию квазиконъюнкции вида будем обозначать как . Имеют место следующие соотношения:

Соотношение (8-19) является обобщением формулы де Моргана. Введем характеристические функции следующего вида:

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

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

Пример 8-4. Записать в виде разложения (8-21) функцию из примера 8-2:

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

Тогда легко доказывается следующая теорема.

Теорема 8-7. Любая функция в -значной логике может быть представлена в виде формы:

В соотношении (8-23) используются операции сложения и умножения по модулю