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

Указа­ние этих предикатов и составляет содержание теоремы Розенберга о полноте в конечнозначных логиках. В результате, следуя И. Розенбергу, все предполные классы делятся на шесть типов (семейств):

• Тип — предполные классы монотонных функций;

• Тип — предполные классы самодвойственных функций;

• Тип — предполные классы функций, которые сохраняют нетривиальные предикаты эквивалентности;

• Тип - предполные классы квазилинейных функций;

• Тип - предполные классы функций, которые сохраняют центральные предикаты;

• Тип - предполные классы функций, которые сохраняют /г-универсальные предикаты.

(Заметим, что у И. Розенберга вместо предикатов выступают отношения, т. е. вводится понятие сохранения функцией f отношения)

В [Rosenberg 1970] доказывается, что все указанные семейства классов являются предполными, и устанавливается критерий функ­циональной полноты для Рп:

Это значительная теорема в многозначной логике. озенберга в более доступной форме из­лагается в [Lau. 2006]. Новое доказательство через модификацию некоторых идей имеется в [Quackenbush 1982]. Описание указан­ных шести типов классов и подробное доказательство их предполноты можно найти в [Яблонский, Гаврилов и Набебин 1997]. То же самое, но в более компактной форме имеется в [Марченков 2004].

Конечно, интересует вопрос о числе предполных классов п(п) в Рп для любого В [Захарова, Кудрявцев и Яблонский 1969] показано, что число п(п) асимптотически равно

где для нечетных и, для четных п. В этой работе,

основываясь на статье [Rosenberg 1965], вычисляется число пред­полных классов для каждого типа и в общем случае для

Полностью вопрос решен в [Rosenberg 1973], где определена также мощность каждого из указанных семейств предполных клас­сов. Для п(п) имеет место следующая таблица:

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

7.3.3.2.1. «Максимальный» предполный класс и его базис

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

Из теоремы Яблонского о функционально пред­полных классах функций в п-значной логике [Яблонский 1958] сле­дует, что данный класс функций Тп является предполным в Рп.

Пусть есть множество функций, соответствующее трех­значной логике Лукасевича т. е. В работе [Финн 1969] о функциональной предполноте показа­но, что

Рассмотрим матричное определение логики Тп, соответст­вующей множеству функций Тп, которую [Finn 1975] называет «максимальной п-значной непостовской логикой»:

где

— функции, определенные выше,

Сигнатуру матрицыможно значительно упростить. Пусть

[Карпенко 1989, где

1) если п = 3, то

2) если п > 3, то

Множество всех функций матрицы обозначим посред-

Ством

Теорема. для любого

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

Сначала определим вимпликацию Лукасевича

Легко показать, что

Поскольку отличается о т только для случая, когда

х = у и то остается проверить этот случай. Тогда

имеем

Следовательно, Поскольку

Как уже отмечалось, Б. Россер и А. Тюркетт [Rosser and Tvrquette 1952] показали, что для любогои любого

Отсюда,Остается показать, что

1) п = 3, Тогда :

2)Тогда

Таким образом, .

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

Таким образом,

В Карпенко 1989] построена также функция Шеффера для

7.3.4. Функции Шеффера

К проблеме функциональной полноты примыкает задача о базисах и в первую очередь представляют интерес базисы, состоящие из одной функции, которые называются функциями Шеффера. Пусть Тогда функция f из Рп есть функция Шеффера (или единст­венный генератор) для F, если любая функция из F выразима посредством конечного числа суперпозиций функции f, или, по-другому, если

[f] = F.

Уже говорилось, что в Р2 имеются только две полные системы, состоящие из одной функции: штрих Шеффера и стрелка Пирса

Понятно, что подобные функции также являются функциями Слупецкогo. Поскольку есть и есть то

имеется следующий критерий для двузначных функций Шеффера (см. [Шестопал 1961]):

В отличие от Р2, в Р3 имеется 3774 двуместных функций Шеф­фера (см, [Martin 1954]). В [Wheeler 1961] найдена формула, вы­числяющая число m-местных функций Шеффера в Р2.