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

В [Карпенко 2009] показано, что нетрудно подобрать две функции, например, внутреннюю и внешнююконъюнкции (см. раздел 3.3.1) из В3 такие, что Из теоремы о критерии функциональной полноты В3 следует, что множество внутренних функцийи множество внешних функ­цийне пересекаются. Это значит, что условие (а) из вышепри­веденного критерия счётности в В3 не выполняется. Однако выше­приведенный критерий счётности составляет всего лишь необходимое условие.

Рассмотрим еще одно предположение в пользу континуально­сти В3. Как уже говорилось (см. раздел6.3), в [Ангиаков и Рычков 1982] предложен метод гильбертовской аксиоматизации широкого класса многозначных логик, основанный на расширении классиче­ской логики С2. Для этого должны выполняться следующие усло­вия:

(1) Алгебра является квазирешеткой;

(2) Наличие всех Ji-операторов;

(3) Ограничения операций на подмножество {0, 1} множества Vn суть обычные классические операции отрицания, дизъюнкции, конъюнкции и импликации соответственно. Логика В3 все эти условия ыполняет, но не выполняет их логика G3: не все

Ji-операторы здесь имеют место. Однако все Ji - операторы и не нужны, достаточно, J0 или J1, поскольку с их помощью строится трехзначный нормальный изоморф С2 (см. раздел 3.3.1). Таким об­разом, задается некоторый "минимум" функциональных свойств, который достаточен для аксиоматизации некоторой трехзначной логики Заметим, что логика Холдена Нз не содержит операто­ров и поэтому не имеет нормального изоморфа, а значит, не может быть аксиоматизирована как расширение С2.

7.5.3.1. Гипотеза о критерии континуальности трехзначных логик

В связи со сказанным выше в качестве гипотезы можно сформули­ровать следующий критерий континуальности трехзначных логик. Пусть есть мощность множества F. Для класса F, со-

ответсвующего некоторой трехзначной логике т. т.т.,

когда L3 аксиоматизируема как расширение С2.

Таким образом, функциональные свойства некоторого множе­ства функций F связываются с чисто логическими свойствами класса формул соответствующей логики L3.

7.5.4. S-классификация

Поскольку не представляется никакой возможности классифициро­вать континуум замкнутых классов, в конце 70-х - начале 80-х го­дов XX ст. появились идеи, которые могли бы привести к конечным либо счетным классификациям. Наибольшее распространение получила идея

S-классификации, основанная на новой операции, названной

S-замыканием. Пусть S-замыканием множества F называет-

ся замыкание F, которое наряду с любой функцией f содержит так­же все двойственные к ней функции. Показано, что при любом n, п ≥ 3, число замкнутых классов в S-классификации конечно, хотя и зависит от п эспоненциальным образом.

Например, S-классификация функций трехзначной логики со­стоит всего из 48 классов и при этом можно обойтись без исполь­зования критерия функциональной полноты, основанного на просмотре всех предполных классов. Как раз полному описанию всех этих 48 классов и посвящена работа [Марченков 2001].

7.6. Логики Лукасевичаи простые числа

Здесь нам будет удобней работать со следующей формулировкой конечнозначных логик Лукасевича, которая эквивалентна исход-

ной. Под n+1-значной матрицей Лукасевича будем понимать

матрицу следующего вида:

где

{п} — множество выделенных значений.

Функцииопределяются на множестве Vn+1 сле-

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

Функции.определяются через исходные:

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

Ранее отмечалось (см. 7.3.3.2.1), что множество функций является функционально предполным в Р3, т. е. оказалось одним из предполных классов Яблонского, а именно тем, который сохра­няет 0 и 2 и обозначается посредством T3. Таким образом, Возникает следующий нетривиальный вопрос: каковы функцио­нальные свойства множества функций для любого n?

7.6.1. Функциональные свойства (теорема )

Ответ на поставленный выше вопрос дан в тезисах доклада [Финн 1970], а затем опубликовано подробное доказатель­ство в [Бочвар, Финн 1972].

Пусть есть функции, определяемые следующим образом:

Истинностными таблицами, отвечающими указанным функци­ям, будут таблицы вида

где

Обозначим посредством In+1 множество всех -функций,

определимых в Tn+1.

Лемма 1. Множество функций является функционально пред - полным в Pn+1 т. т.т,, когда все функцнпринадле-

жат Причем, если — предполное в Pn+1 множество функ­ций, то [Бочвар и Финн 1972].

Доказательство леммы 1 есть по существу доказательство сле­дующего утверждения: любая функция которая не равна константе 0, определима посредством суперпозиции I-функций и J-функций (эта суперпозиция есть аналог совершенной дизъюнктивной нормальной формы для двузначной логики)

( В связи с этим обратим внимание на следующий результат в [Бочвар и Финн 1972, теорема 4]: каждая тождественно неравная 0 функция имеет I-J-совершенную дизъюнктивную нормальную форму т. т.т., когда где р — простое число, а β — натуральное число, В [Agitzzzoli, D 'Antona and Marra 2005], применяя специальную технику (Впт hats), строится аналог булевской СДНФ для кода п есть простое число (вместо дизъюнкции берется функ-

цияЗдесь же этот результат распространяется на произвольную )

Таким образом, ответственным за предполноту в Pn+1 яв­ляется наличие в множества функций Iп+1. Возникает вопрос: для каких п имеет место т. е. для каких

Лемма 2. т. т.т., когда п есть простое число [Бочвар и

Финн 1972].

Доказательство леммы 2 хотя и весьма громоздко, но является конструктивным, так как указан алгоритм построения суперпози­ций исходных базисных функций равных соответст­вующим -функциям. Отсюда, в частности, следует, что при п = р, где р - простое число, можно указать эффективный способ по­строения формулы, отвечающей функции использующий I-функции и нормальные формы (I-J-с. д.н. ф.), рассмотренные при доказательстве леммы 1.