§ 4.4. Преобразования и полифеки

Полифеками называются универсальные функции, любой из которых достаточно для построения исчисления высказываний^*. Сети, использующие конечное число только одной из этих функций, в состоянии воспроизвести любую функцию исчисления высказываний. Одним из полифеков, в частности, является штрих Шеффера.

^* (Термин "полифек" (polyphek) введен Блюмом [16].)

Чтобы определить, является ли функция n переменных, заданная точечной диаграммой D^τ, полифеком, необходимо использовать введенное в работе [16] понятие преобразований. Преобразования могут изменять логические функции, вычисляемые нейронной сетью, или функции входящих в сеть формальных нейронов, но только так, чтобы не изменить надежность сети.

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

В связи с тем, что любую логическую функцию можно представить, используя только конъюнкцию или дизъюнкцию и отрицание, функцию запишем в виде Φ (X, Y, ∨,&)9 где X является логической переменной, вход которой возбужден, а Y - логической переменной, вход которой не возбужден. Тогда, например, если

Ф(Х, Y, ∨, &) = (a₁&a₂&a₃)∨(a₁&a₂&a₃)

то

что в терминах диаграмм Венна показано на рис. 4.24.

В [16] рассматривается три вида преобразований: дополнение (complement) С, двойственность (dual) D и перестановка (permutation) Р. Суть этих преобразований сводится к следующему:

(4.5)

Рис. 4.24

Рис. 4.25

На рис. 4.25 в терминах диаграмм показаны два примера применения преобразований С, D и Р. Из (4.5) следует, что

Отсюда видно, что

Аналогично

Отсюда

Так как

то

Так как

то

Так как

то

Наконец, так как

то

Применим операцию преобразований к нейронным сетям, обозначаемым, как это принято в настоящей работе, в виде

где Φ - результирующая функция, вычисляемая сетью.

Под записью CD^τ_r,i, DD^τ_r,i, PD^τ_r,i будем понимать применение данного вида преобразования ко всем диаграммам данного ранга. Тогда можно показать, что

Комбинируя между собой уравнения (4.13)- (4.16), можно получить ряд новых соотношений. Так, например, уравнения (4.13) и (4.14) дают

а (4.17) и (4.15)

Последнее соотношение весьма важно для анализа и синтеза логически стабильных сетей (§ 4.5); оно позволяет одни логически стабильные сети преобразовать в другие логически стабильные сети. Покажем это на конкретном примере. На рис. 4.30 приведена логически стабильная сеть, вычисляющая функцию Φ = а₁ а̄₂ ∨ a₁a₂ при трех последовательных значениях порогов у нейронов. Применим ко всем диаграммам нейронов этой сети преобразования DC. Эти преобразования показаны в терминах точечных и порядковых диаграмм на рис. 4.26.

Рис. 4.26

Полученная в результате преобразований функция Φ₁ = а₁а₂ ∨ ā₁а̄₂ является, во-первых, логически стабильной при трех значениях порогов и получена из функции Φ путем применения к последней преобразований DC, т. е.

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

В работе [16] дано необходимое и достаточное условие обладания функцией свойством дополнения: для того чтобы точечная диаграмма D^τ логических переменных a ,..., а_n могла дополнять функцию Φ, необходимой достаточно, чтобы в нулевой ячейке имелась точка и чтобы в ячейке 2ⁿ - 1 ее не было.

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

Любая функция Φ, которая может дополнять и которая удовлетворяет условию Φ ≠ CDΦ, является полифеком. Иначе говоря, логическая функция Φ есть полифек тогда и только тогда, когда

1) ее точечная диаграмма D^τ содержит точку в нулевой ячейке, не содержит точку в последней (т. е. 2ⁿ - 1) ячейке и

2) удовлетворяется условие Φ ≠ CDΦ.

При двух переменных первому условию теоремы из общего числа 2²² = 16 функций удовлетворяют четыре функции: a₁, a₂, ā₁ā₂, ā₁∨ā₂ ибо у остальных двенадцати функций либо отсутствует точка в нулевой ячейке, либо имеется точка в ячейке 2ⁿ - однако второму условию теоремы из четырех рассмотренных функций удовлетворяют только две последние (рис. 4.27). Эти две функции являются штрихом Шеффера и стрелкой Пирса.

Общее число полифеков N для функции n переменных определяется из формулы

(4.19)

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

поэтому при n ≥ 4 ее можно считать приближенно равной

Рис. 4.27