Математика / 2. Перспективы информационных систем

Шматова Е. В.

НИИ ПМА КБНЦ РАН, Россия, г. Нальчик

О представимости k-значной логической

функции операциями псевдосложения

Известно, что любое непрерывное преобразование, можно аппроксимировать при помощи вычислительной сети, построенной на базе элементов, реализующих внешнее суммирование и непрерывную скалярную функцию. Большой интерес представляют прямые алгебраические суммы, которые позволяют одновременно формировать архитектуру вычислительной сети и настраивать ее параметры, не прибегая к решению сложных оптимизационных задач для достижения корректности ее функционирования [1].

В работе предлагается алгоритм представимости k-значной логической функции операциями псевдосложения на примере трехзначной логики.

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

Алгоритм строится в виде дерева.

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

, (1)

Значит

, , , (2)

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

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

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

Проиллюстрируем работу алгоритма на примере логики Гейтинга.

Пусть дана трехзначная логика Гейтинга ,. И пусть задано: . Построим дерево решений для данного примера.

Рассмотрим 1 ветвь: необходимо, чтобы , но это противоречит условию . Значит, эту ветку можно отбросить.

Рассмотрим 2 ветвь . Такое возможно, поэтому строим ветви далее:

1. - невозможно, следовательно, ветку можно отбросить;

2. - невозможно, следовательно, ветку можно отбросить;

3. - возможно.

Восстанавливая цепочку действий, получим: , , . Отсюда можно сделать вывод: что полученное множество решений (будем называть классом решений) обладает свойством коммутативности (таб. 1).

Рассмотрим 3 ветвь: . Такое, возможно, поэтому строим ветви далее:

1. - невозможно, следовательно, ветку можно отбросить;

2. – невозможно, следовательно, ветку можно отбросить;

3. - возможно. Восстановим цепочку действий, получим: , , . Т.е. получили таблицу истинности без учета свойства коммутативности (таб. 2). Если же учесть коммутативность, то получим табл.3.

Табл.1. Табл.2. Табл.3.

	0		1		0		1		0		1
0	0		1	0	0		1	0	0		1
							1				1
1	1			1	1			1	1	1

Совокупность занятых ячеек в таблице соответствует тем необходимым условиям существования для реализации заданного тождества. А пустые ячейки соответствуют несущественным условиям, значит каждая свободная ячейка порождает три возможных варианта: 0, ,1. Это дает возможность установить точное число функций в классе решений (мощность).

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

1) табл.1 - количество функций в классе решений равно 9 (свойство коммутативности выявлено в процессе поиска решения и не является наперед заданным);

2) табл.2 количество функций в классе решений равно 9. Если свойство коммутативности считать наперед заданным, то количество функций в классе решений будет равно 3 (табл.3).

Утверждение. Если при поиске класса решений коммутативность не выявляется сама, а налагается как дополнительное условие, то это уменьшает мощность множества допустимых решений.

Это связано с тем, что уменьшается количество свободных ячеек в таблице истинности.

Таким образом, можно доказать следующую теорему.

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

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

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

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

Литература.

1. Шибзухов З.М. О некоторых конструктивных и корректных классах алгебраических. Доклады РАН. 2010. Т.432, №4. С.465-468.

2. Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001. 384 с.