4.5. Проблема полноты в многозначной логике

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

Первое из этих понятий определяется следующим образом.

Определение 4.1

-Арным отношением на множестве является подмножество множества (декартово произведение взятое раз, т. е. является множеством упорядоченных наборов из элементов множества k). Унарные отношения на таким образом, являются просто подмножествами; широко известными примерами бинарных отношений являются отношения порядка и отношения эквивалентности. Множество является 4-арным отношением и бинарным отношением на которое часто фигурирует при проверке полноты в случае двоичных элементарных логических функций.

Определение 4.2

Функция сохраняет -арное отношение на тогда и только тогда, когда из

следует, что

Если аккуратно проследить за индексами, то можно увидеть, что определение эквивалентно такому утверждению: если задана матрица с строками и столбцами элементов такими, что каждый столбец является элементом тогда определенная для каждой строки, должна дать значение столбца, являющегося элементом Теперь рассмотрим случай самодвойственности для двоичных функций. (Рассмотрим многозначный случай в рамках определения соответствующих отношений.) Положим функцией трех переменных, как определено в табл. 4.1 (см. разд. 4.2). Положим, что, так же как и ранее, будет бинарным отношением на и 4-арным отношением на Тогда образуем следующие матрицы.

Пример 4.6

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

1. Отношения порядка с минимальным и максимальным элементом. Бинарное отношение является отношением порядка, если оно обладает рефлексивностью, транзитивностью и антисимметрично. Рефлексивность означает для всех Транзитивность означает, что из следует для всех Антисимметричность означает, что из следует

Пример 4.7

Рассмотрим случай четырехуровневой логики на множестве Тогда следующее множество является отношением порядка на

или, более кратко,

2. Бинарные отношения вида где Р является перестановкой с периодом где — длина, причем является простым числом.

Пример 4.8

Рассмотрим случай шестиуровневой логики на множестве и перестановки

Таблица 4.6. Коммутативная группа изоморфная

Таблица 4.7. Многозначная таблица логических значений, обсуждаемая в примере 4.12.

Результатом явится

3. Если для ряда являющихся простыми числами, тогда определим 4-арные отношения для выражения

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

Пример 4.9

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

В отношении имеются 4 члена:

Данный набор содержит все возможные заданные в табл. 4.6. Каждое уравнение порождает функцию четырех переменных.

4. Нетривиальные отношения эквивалентности. (Напомним, что отношения эквивалентности есть отношения рефлексивные, симметричные и транзитивные. Симметрия означает, что для выполняется

Пример 4.10

Рассмотрим случай многозначной логики, определенной на множестве шести элементов Тогда отношением эквивалентности является следующее отношение:

5. Центральное отношение на -Арное отношение является центральным тогда и только тогда, когда оно строго рефлексивно,

строго симметрично и его центр не является ни пустым, ни самим множеством Отношение является строго рефлексивным, если оно содержит все членов в таких, что при некоторых две компоненты равны, т. е. . (Заметим, что может содержать много других элементов, но оно должно включать по меньшей мере эти.) -Арное отношение является строго симметричным, если для выполняется для каждой перестановки Р, действующей на Центр -арного отношения на определяется как Заметим, что любое единичное отношение на не являющееся пустым и не содержащее само является центральным.]

Пример 4.11

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

6. Любоё отношение определяемое -упорядоченным классом Т эквивалентных отношений на (Класс эквивалентных отношений является -упорядочен-ным, если он удовлетворяет двум условиям. Во-первых, каждое должно иметь классов эквивалентности Во-вторых, оно должно представлять тот случай, что пересечение где не является пустым выбирают произвольно). Отношение, определяемое Т, представляет собой отношение состоящее из всех обладающих тем свойством, что по крайней мере два элемента эквивалентны по для всех

Пример 4.12

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

является отношением на так что два элемента должны быть эквивалентными по и два элемента должны быть эквивалентными по Список весьма длинен, и здесь будет представлено только несколько примеров. (0, 6, 7), (8, 6, 5), (6, 8, 0) и (6, 3, 7) принадлежат в то время как (0, 1, 2), (0, 3, 6), (0, 4, 8) и (5, 7, 0) не принадлежат %т.

Следующая теорема принадлежит Розенбергу [22].

Теорема

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

Данная теорема указывает на то, что поиск множества логически полных элементарных операций для совокупности оптических явлений должен быть в наибольшей степени связан с явлениями, разрушающими алгебраические структуры. Это находится в резком противоречии со случаем аналоговых вычислений, в которых операции сохраняют структуру в смысле линейной алгебры и линейных операторов. Детали конкретных видов алгебраических структур, которые должны быть разрушены, содержатся в шести типах отношений. Имеет ли данная теорема какой-нибудь практический смысл? И да, и нет. Она вполне полезна, если надо показать, что конкретные множества не являются полными. Для этого достаточно одного противоположного случая. Теорема также полезна для выработки подхода к вопросу, какие структуры надо разрушать.

Теорема, однако, имеет небольшое значение при определении полноты конкретного множества. Так, для пяти уровней следует проверить более 600 отношений; для 8 уровней число отношений превышает 500 миллиардов. (Подробное изложение данного вопроса можно найти в Часто для того, чтобы показать, что множество функций является полным, оказывается достаточным проявить небольшую изобретательность и сформировать из элементарных функций одну универсальную.

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

Дадим определение автоморфизма. Рассмотрим однозначное

отображение Ф множества А само в себя: , Ф — автоморфизм, если Наконец, нам необходимо понятие конгруэнтности на Пусть является эквивалентным отношением на Тогда является конгруэнтным на если для любого множества для справедливо

Теперь можно сформулировать теорему:

Логическая функция является универсальной на тогда и только тогда, когда:

1. Не существует соответствующей субалгебры на

2. Не существует нетривиального автоморфизма на

3. Не существует нетривиальной конгруэнтности на

Две хорошо известные универсальные функции являются функциями Уэбба и определяются так:

а также S-функция имеет вид

Доказательства не представляют большой сложности, но в случае затруднений следует обратиться к работе [2].

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

На этом изложение типов функций, искомых для получения полноты многозначной логики, завершено. Однако следует упомянуть раннюю теорему Слупецкого [33], так как она часто дает более простые тесты, чем теорема Розенберга. Изложение дается так, как в работе [2].

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

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