6.2. Многозначная пороговая логика

6.2.1. Теоретические основы

Исследования многозначной пороговой логики возникли в начальный период исследований пороговой логики. За важной работой [7] по описанию свойств пороговых (двоичных) функций последовали пионерские работы [8, 9] по троичной пороговой логике. На протяжении последующего десятилетия основное внимание исследователей привлекла именно троичная пороговая логика, что определялось, вероятно, появлением возможности для ее приборной реализации на основе дискретных полупроводниковых компонент. В числе наиболее важных результатов данного периода можно упомянуть работы, посвященные описанию свойств троичных пороговых функций [10, 11], подсчету и классификации всех трехместных троичных пороговых функций [12, 13], откуда следует, что существует 85 629 таких функций (в то время как рядом авторов независимо указывалось на существование 471 двухместных троичных пороговых функций), а также табличный метод реализации троичных пороговых функций с числом переменных, достигающим трех [13, 14].

Первыми публикациями по многозначной пороговой логике (за исключением троичной), по-видимому, являются работы [15—17]. Интересно заметить, что в [15] набор корней единицы был использован в качестве области определения -значных функций, а для исследования пороговых функций использовались методы гармонического анализа функций. Данный подход, однако, не получил дальнейшего развития в последующей литературе. С другой стороны, в [16] в качестве области

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

Следующее определение представляет собой упрощенный вариант материала, изложенного в работе [17].

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

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

где обозначает внутреннее произведение и X.

Становится ясно, что, если система (6.1) имеет решение, тогда она имеет бесконечно много решений. Большая их часть удовлетворяет более жесткой системе неравенств со знаком вместо

Следует отметить, что определение не требует, чтобы функция устанавливала фактически многооднозначное соответствие. Если не принимает заданного значения в V, это только означает, что в существуют X, такие что и в (6.1) выражение все еще является формально правильным, но не имеет решений. (Функция устанавливает нестрогое многооднозначное соответствие, если для любого существует по крайней мере одно такое что

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

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

Рассмотрим пример троичной пороговой функции на рис. 6.1. Введем следующее обозначение. Если — пороговая функция с весовым вектором и пороговым вектором Т, то запишем и назовем структурой Отсюда для примера на рис. 6.1 получим, что

Лемма 6.1

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

Доказательство: Следует непосредственно из уравнения (6.1).

Лемма 6.2

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

Доказательство: Пусть Тогда Пусть будет таким, что для всех Отсюда следует, что

Рис. 6.1, Пример двуместной четырехуровневой пороговой функции.

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

Положим в данном случае Так как то можно записать

но

Определим Тогда

Отсюда следует

На рис. 6.2 показана функция от функции где является функцией, ранее изображенной на рис. 6.1.

Следствие 6.1

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

Рис. 6.2. Четырехуровневая пороговая функция, полученная из функции, заданной на рис. 6.1 путем замены второго аргумента на его дополнение.

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

Лемма 6.3

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

Доказательство:

Умножая на получим

Пусть Более того, прибавим к обеим частям второго члена приведенного выше выражения. Это приводит к

Пример

Пусть — функция, представленная на рис. 6.1. Тогда справедливо следующее:

Следствие 6.2

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

Доказательство

Следует непосредственно из лемм 6.2 и 6.3. Пример представлен на рис. 6.3.

Лемма 6.4

Пусть является пороговой функцией. Ее структура при этом удовлетворяет строгому варианту уравнения (6.1). Пусть так что если для всех принадлежащих V. Тогда справедливо для если и

положительная бесконечно малая величина)

Доказательство: Из определения и строгого неравенства для становится ясно, что

Другими словами:

Не существует X такого, что

Для всех X, таких что или Иначе

Если заменить элементы Т на соответствующие элементы Т и на в уравнении (6.1), то изменяется все выражения, кроме двух, а именно

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

Рис. 6.3. Двойственная функция, полученная из функции, показанной на рис, и ее пороговая структура,

Следствие 6.3

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

Лемма 6.5

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

Доказательство: Следует непосредственно из уравнения (1) и свойства коммутативности суммы в

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