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

Незначительное усиление теоремы из [Martin 1954] приводит к следующей характеризации функции Шеффера для Рn:

Функция из Рп, гд е является функцией Шеффера m.m.m., когд апорождает все функции одной переменной, принимающие не более п-1 значений [Яблонский 1958].

По сути это является еще одним критерием функциональной полноты для Рп.

Интересно получить критерий для двузначных функций Шеффера в терминах предполных классов Розенберга, что и было сде­лано в [Rousseau 1967]):

( Здесь есть класс, сохраняющий одноместные центральные предикаты. О свойствах этого класса и функции Шеффера для него см. также в [Кудрявцев 1970].)

В [Schofteld 1969] было показано, что эти условия независимы. Отсюда следует, что функция Шеффера существует для любого из указанных классов и что все другие классы не имеют никакой функции Шеффера. А. Роуз показал [Rose 1969], что не для каждого множества функций

n-значной ло­гики существует штрих Шеффера.

В [Rosenberg 1978] приводится библиография по функциям Шеффера включительно по 1978 г. Теория двуместных штрихов Шеффера для Рn

и эффективные правила их построения даны [Pinkava 1981]. О симметрических (коммутативных) функциях Шеффера см. в [Stojmenovic 1989]. Ранее было известно, что в Р3 имеется 90 двуместных коммутативных функций Шеффера.

В каждом случае, однако, возникает проблема построения функции Шеффера для функционально неполных логик. Для неко­торых трехзначных логик мы этот вопрос рассмотрели в разделе (3.6).

7.3.4.1. Функция Шеффера для

Интересен следующий результат, который понадобится нам в дальнейшем. Дж. Мак-Кинси [McKinsey 1936] сконструировал функцию (штрих) Шеффера для n-значной логики Лукасевичав следующем виде:

где С и N - импликация и отрицание в нотации Лукасевича, а скобки указывают на п-2 вхождение заключенного в них выражения. Для единообразия обозначим функцию Еху как

Используя Ji(х)-функции, которые не были известны Дж. Мак-Кинси, можно значительно упростить определение Заме тим, что Тогда

Применив контрапозицию к консеквенту, получим нужное оп-ределение:

Для сравнения с импликацией Лукасевичаопределим

следующим образом:

Теперь нужно посредством определить функции ~х и

Мак-Кинси это делает следующим образом:

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

средством Еn. Таким образом, для любого

Исследования штриха Шеффера для работой Мак-Кинси не закончились. А. Роуз [Rose 1952] обратил внимание, что функция не является коммутативной, и предложил новое определение штриха Шеффера для которое значительно проще:

Однако новый штрих Шеффера не имеет места для случая, ко­гда

п = 3i, поскольку i тогда является неподвижной точкой. Инте­ресно, что точно такой же штрих Шеффера для был построен в [Hendry and Massey 1969]. Наконец, А. Роуз [Rose 1968] доопределяет функцию таким образом, что она является штрихом Шеффера для любого

7.4. Принципиальные отличия многозначной логики от двузначной. Континуальность

В книге Э. Поста [Post 1941] поставлен также вопрос об описании всех замкнутых классов в Рn. На положительное решение вопроса дал некоторые основания сам Пост, предложив двузначную интер­претацию логик Рn (см. ниже раздел 10.6)

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

Первое качественное отличие (не количественное, как, напримёр, рост числа функций или числа предполных классов при росте числа истинностных значений п) было обнаружено ­цовым в 1951 г. при обобщении теоремы Жегалкина (см. 1.3.1):

Функцию п-зпачной логики можно представить полиномом по mod п т. т.т., когда п есть простое число (см. [Яблонский 1986]),

Но главные отличия следующие. доказал, что в от­личие от Р2 для всякогосуществует в Рп замкнутый класс, не имеющий базиса [Янов и Мучник 1959], а доказал, что для всякого существует в Рn замкнутый класс со счетным базисом [Янов и Мучник 1959]. Подробное доказательство см. в [Яблонский 1986]. Непосредственно к этой второй теореме примыкает следующий результат : для всякого п Рп содержит континуум различных замкнутых классов.

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

Отметим также несколько неожиданный факт при переходе от 7 к 8 при изучении предполных классов в Рn :

Длясуществует предполный класс такой, что F

не имеет конечного базиса [Tardos 1986] (см. также [Михеева 1986]).

В силу основной трудности (континуальности множества замкнутых классов) исследуется «локальная» информация о струк­туре окрестности некоторого произвольного замкнутого класса. На один результат, относительно мощности замкнутых классов в са­мих предполных классах, стоит сослаться (см. [Марченков 1983] и [Demetrovics andHannak 1983].

Пусть и пусть F есть произвольный предполный класс из

Рп. Тогда мощность решетки замкнутых классов множества F континуальна, т. е. т. т.т,, когда F не является пред-

полным классом типа Если F — предполный класс типа тогда в случае, когда п =рп, где р есть простое число, если

в остальных случаях.

Целая серия работ в изучении решеток клонов принадлежит (см., например, [Bulatov 2001]).

7.5. Трехзначные логики: функциональные свойства

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

1) классификация функций и число базисов;

2) критерий функциональной полноты для различных не­функционально полных логик;

3) мощностные характеристики множеств замкнутых классов в этих логиках.

7.5.1. Классы функций и базисы для Р3

В первую очередь интересует число базисов в самой Р3. Известно, что функции из Р3 можно классифицировать, используя предполные классы. Вначале определяются классы функций (вектора) отосительно того, является или нет какая-либо функция элементом предполного класса. Относительно этих векторов вычисляются полные базисы (агрегаты). Впервые для Р3 это было проведено в [Miyakawa 1971]. Уточнение результатов этой работы сделано в [Stojmenovic 1984], откуда следует, что число классов функций в Р3 есть 406 и число базисов есть б 239 721. Также установлено, что максимальный ранг базиса не превышает 6. При этом указано число базисов для каждого из рангов от 1 до 6. Расчеты велись с помощью компьютерной программы. Таким образом, выяснена точная структура Р3.