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

(Число классов функций для Р2 есть 15 {Яблонский 1952] и число базисов (агре­гатов) есть 42 [Iburki, Naemura and Nosaki 1963]. Агрегат есть множество всех базисов, имеющих одно и то же множество характеристических векторов. На­пример, одно и то же множество характеристических векторов имеют функции Шеффера: они не входят ни в один из пяти предгголных классов.)

Обзор данной проблематики см. в [Miyakawa, Stojmenovic, Lau and Rosenberg 1987]. Алгоритмиче­скую проблематику, связанную с вычислениями, см. в книгах [Sto­jmenovic 1987] и [Miyakawa 1988]. Специально о классификации трехзначных функций см. [Miyakawa 2002].

7.5.2. Субмаксимальные клоны

Рассмотрим следующее полезное понятие, впервые введенное [Раца 1969]. Будем называть глубиной системы F функций в классе К0 наименьшее из таких натуральных чисел т, что существует убы­вающая последовательность классов удовлетворяю­щая двум условиям:

1) класс предполон в

2) система F является полной в Кт,

В частности, то, что глубина системы F в классе К0 равна 0, означа­ет, что F является полной в К0 (ср. это определение глубины с [Lau 2006]).

В [Rosenberg 1974] вводится понятие субмаксимального {submaximal) класса. Это такие предполные классы функций, глубина которых равна 2. Заметим, что каждый субмаксимальный класс яв­ляется клоном (см, [Lau 2006]).

Впервые это было вычислено в [Miyakawa 1979].

Как раз первым примером логики "глубины 2", чьи функцио­нальные свойства были тщательно изучены, была трехзначная ло­гика Рейтинга G3 (см. выше раздел 3.2). , ученик , показал, что класс функций G3 предполон в классе функций (как мы уже знаем класс предполон в Р3), и устано­вил критерий функциональной полноты для класса функций G3 [Раца 1965; 1969]. Здесь доказывается, что G3 имеет ровно 10 предполных классов, и система функций F полна в G3 т. т.т., когда F не включается ни в один из этих классов. Также доказывается, что, ранг базиса для G3 не превышает 6.

( Отсюда следует, что каждый предполный класс в G3 имеет глубину, равную 3. Одним из таких предполных классов в G3 является класс функций (см. определение трехзначной p-логики в разделе 3.2.2).)

Этапной работой, посвященной описанию всех субмаксималь­ных классов Р3, т. е. описанию всех предполных классов в каждом из предполных классов Яблонского для Р3, является статья [Lau 1982]. Эта работа стала основой для вычисления характеристиче­ских векторов и базисов для различных предполных в Р3 классов. Из 18 классов Яблонского эта работа уже выполнена для 8 классов. См. соответствующую литературу в [Miyakawa, Rosenberg and Sto-jmenovic 1990], где установлено, что в предполном классе Яблон­ского, сохраняющем 0, имеется 253 класса различных функций и 833 720 базисов.

Интереснейшим вопросом, который встает при изучении суб­максимальных клонов, есть вопрос о мощности каждого из этих клонов. Уже в [Раца 1969] был поставлен вопрос о мощности мно­жества замкнутых классов функций, соответствующего трехзнач­ной логике Рейтинга G3. Ответ оказался несколько неожиданным, хотя глубина клона G 3 равна 2:

Множество функций G3 включает континуум замкнутых классов со счетными базисами, а также континуум замкнутых классов, вообще не имеюгцих базиса [Раца 1982; 1990].

Для порождения континуального множества замкнутых клас­сов функций строит систему функций С, выраженную следующей формулой;

Где

Обозначим эти функции — двухместную, трехместную и т. д. символами С2, С3... соответственно. Например, С2 есть

Условимся для любых функцийи

из G3 обозначать символом результат подстановки в f

функции g вместо переменной хi. Тогда для всякого п = 2, 3, ... функция Сп является симметрической (т. е. при всякой перестановке аргументов остается равной себе) и удовлетворяет условиям:

Ф. Раца показывает, что при выполнении этих условий систе­ма функций С является независимой, откуда следует, что сущест­вует континуум различных замкнутых классов функций.

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

Общий ответ на поставленный выше вопрос о мощности суб­максимальных клонов дает следующая тео­рема [Bulatov, Lau and Stranch 1996]:

Всего P3 имеет 158 субмаксимальных клонов. Из них: 5 субмак-сималъных клонов имеют конечное множество замкнутых клас­сов;

7 субмаксимальных клонов имеют счетное множество клас­сов; остальные 146 субмаксимальных клонов имеют мощностъ континуума.

Более того, по отдельности указана мощность каждого из суб­максимальных клонов. В качестве следствия имеем вышеприведен­ный результат для G3. Но, подчеркнем, у при­ведены базисы для каждого предполного в G 3 класса функций. К сожалению, нет такого описания предполных классов для Одна­ко в [Cignoli and Monteiro 2006] имеется описание структуры мак­симальных подалгебр трехзначной алгебры Лукасевича, где поня­тие максимальной подалгебры соответствует понятию предполного класса функций.

7.5.3. Функциональные свойства В3

В статьях [Финн 1974], [Finn 1974] установил критерий функциональной полноты для класса функций Вз, соответствующе­го трехзначной логике Бочвара Вз (см. выше 3.3). Здесь доказыва­ется, что В3 имеет ровно 11 предполных классов, и система функ­ций F полна в В3 т. т.т., когда F не включается ни в один из этих классов. Отсюда также следует критерий функциональной полноты для множества внешних функций (см. в разделе 3.3.1 о внешних связках логики Бочвара В3): семь предполных классов. Также показал, что класс функций Н3, соответствующий трех­значной логике Холдена Н3 (см. выше раздел 3.3.3), включается в один из предполных классов Вз.

Тогда можно сделать предположение о глубине рассмотренных классов функций: '

где Ез есть класс функций, соответствующей трехзначной логике Эббингауза (см. 3.3.3).

Интересна гипотеза , что мощность множества замкнутых классов Вз является счетной, как и для Р2. Эта гипотеза основывалась на предположе­нии о том, что в В3 класс внутренних функций (который порож­дается функциями и класс внешних функций (областью значения которых является множество {0,1}) каждый сам по себе счетен, а в объединении они порождают всё множество функций Вз. Исходя из этого, гипотеза выглядит естест­венной.

Однако возможны и другие гипотезы. Обратим внимание на работу [Lau 1986] (см. также [Law 2006]), где дается следую­щий критерий счетности:

Пусть F есть подкласс Рп (или алгебра со счётным множест­вом элементов). Там существует отношение частичного порядка на F, удовлетворяющее следующим трем свойствам:

(b) каждая цепь является вполне упорядоченной (относи­тельно

(Т. е. каждое непустое подмножество обладает единственным минимальным эле­ментом.)

(с) каждая антицепь (относительно имеет только ко­нечное число элементов.

Тогда F имеет как наибольшее только счётное множество различных подклассов.

( Антицепью называется подмножество частично упорядоченного множества, со­стоящее из попарно несравнимых элементов, которых не меньше двух.)

Обратим внимание на свойство (а). Будем говорить, что функция не превосходит функцию и писать

если для любого набораизвыполняется