Дискретно-непрерывная математика (стр. 48 )

Базис является минимальным, если при любом отождествлении переменных у всякой функции базиса получается неполная систе­ма. В [Шестопал 1961] доказано, что в Р2 имеется конечное число различных минимальных базисов и это число равно 48.

Заметим, что в ряде задач изучаются только соответствия меж­ду F и [F]. Тем самым фактически переходят к изучению оператора замыкания, который определяется посредством суперпозиций функций, а сама функциональная система (Рп, С) зачастую отожде­ствляется с многозначной логикой, т. е. (Рп, С) выступает в качестве модели многозначной логики. Эта модель, в отличие от рассмот­ренных выше алгебр истинностных значений, является алгеброй функций.

( Следуя [Малы/ев 1966] (см. также [Марченков 2000]), существу­ет чисто алгебраический способ определения понятий суперпозиции, замыка­ния и замкнутого класса. Введем следующие элементарные алгебраические операции: суть одноместные операции циклической перестановки переменных и транспозиции первых двух переменных. Если f- т-местная функция и то т-местные функции определяются соотношениями

есть одноместная операция отождествления первых двух переменных:

есть одноместная операция введения (первой) фиктивной переменной:

Наконец, * есть двуместная операция подстановки. Если f—m-местная, a g —k-местная функции, то f* g является (k+m-1)-местной функцией, которая опре­деляется тождеством

Алгебраназывается (полной) итеративной алгеброй функций [Laи 2006]. В случае, когда носителем является множество булевых функций Р2, алгебра называется итеративной алгеброй Поста (см. также [Малыше 1976]). Функция называется суперпозицией над если f может быть получена посредством применения конечного числа операций к функциям из F. Множество всех суперпозиций над называется замыканием F. Поэтому всякая подалгебра итеративной алгебры является замкнутым классом.)

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

7.2.1.1. Классы Поста

Наиболее сложной задачей, можно сказать, глобальной задачей для многозначной логики является описание решетки замкнутых клас­сов данной модели многозначной логики. В [Post 1921] установле­но, что мощность множества замкнутых классов в Р2 счётно, и только через двадцать лет, в [Post 1941] доказывается Большая тео­рема Поста, где дается полное описание решетки замкнутых клас­сов, каждый класс строится эффективно и показано, что каждый замкнутый класс имеет конечный базис. Эти классы названы клас­сами Поста. Их около 50, включая несколько бесконечных регу­лярных семейств. Из этих результатов следуют решения задач о выразимости, полноте (Малая теорема Поста), базисах и др. Так, максимальный ранг базиса не превышает 4, например,

Эта работа сыграла основополагающую роль в дальнейшем изучении функциональных свойств многозначных логик. Доказа­тельство Поста громоздко и довольно-таки сложно. В [Яблонский, Гаврилов и Кудрявцев 1966] результаты Поста излагаются в более доступной форме. Эта книга сыграла огромную роль в литературе, на многие годы определив характер исследований по замкнутым классам булевых функций. В 80-е годы появляется целый ряд новых доказательств, например, алгебраическое доказа­тельство в [Вегтап 1980] и компактное доказательство в [Угольни­ков 1988]. Последнее доказательство несколько модифицировано в [Марченков 2000]. Элементарное доказательство приводится в [Lau 2006].

7.3. Проблема функциональной полноты

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

моделью, и в синтезе автоматов, и в универсальной алгебре; но именно при рассмотрении многозначной логики как функци­ональной системы этой проблеме уделяется специальное внимание. Заметим, что в [Емельянов 1985] показано, что в п-значной логике для любого фиксированного п > 2 задача о выразимости функции посредством операции суперпозиции через функции определенной системы является NP трудной задачей, т. е. для её решения не существует полиномиальных алгоритмов.

Важнейшим свойством функциональной системы является свойство функциональной полноты (например, для того, чтобы можно было реализовать любую переключательную схему). Сис­тема функций из Рn называется функционально полной, если любая функция из Рп представима посредством су­перпозиций функций из системы F. Или, в терминах замыкания: F — полная система, если

Таким образом, указанная выше проблема приобретает здесь следующий вид: является ли некоторое множество F функциональ­но полным?

7.3.1. Примеры функционально полных систем

Приведем три конкретных примера функционально полных систем.

• Система Россера и Тюркетта

является полной в Рп (см. [Яблонский 1958], [Гиндикин 1972], [Лупанов 2007]). Здесь и в остальных примерах бу­дем исходить из последней работы.

Доказательство. Для функций n-значной логики имеет место представление, которое является аналогом совершенной дизъюнк­тивной нормальной формы:

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

так как (т. е. равны максимальному

значению из множества Vn ). Если же то

найдется такое, что Тогда(равно наименьшему значению из Vn ). Поэтому

Следовательно,

Поскольку рассматриваемая формула построена только из функций системы F , то F — полная система.

• Система Поста является полной

в Рn. Для доказательства нужно посредством суперпозиций этих функций выразить все функции системы Россера и Тюркетта.

Доказательство. Разобьем доказательство утверждения на не­сколько этапов.

Построим сначала константы. Рассмотрим функции

При каждом значении х измножество значений, принимаемых всеми этими функциями, равно Vn, Поэтому

Остальные константы получаются при помощи функции

Построим затем функции Рассмотрим

функцию

Если х = 0, то Если же