Содержание к диссертации
Введение
1 Аналог критерия Слупецкого для неявной выразимости в Рк 16
1.1 Критерий неявной полноты в /г-значной логике 16
1.2 Следствия из критерия неявной полноты. Полнота по неявной сводимости и параметрической выразимости в Рк при систем, содержащих все одноместные функции . 26
2 Критерий неявной шефферовости в трёхзначной логике 30
2.1 Основные определения и известные результаты 31
2.2 Необходимые условия неявной шефферовости 34
2.2.1 Функции, сохраняющие подмножество 35
2.2.2 Функции, сохраняющие разбиение 36
2.3 Критерий неявной шефферовости 41
2.3.1 Функции, сохраняющие подмножество 41
2.3.2 Функции, сохраняющие разбиение 46
3 Критерий неявной полноты в трёхзначной логике 51
3.1 Неявно полные классы, не содержащие констант 52
3.2 Класс 61
3.3 Неявно полные классы, содержащие две константы 66
3.4 Неявно полные классы, содержащие три константы 83
3.4.1 Классы сохранения разбиений 83
3.4.2 Классы монотонных функций 88
3.4.3 Классы вида ТІ;Л 90
3.4.4 Класс Слупецкого 102
3.4.5 Основной результат 102
- Следствия из критерия неявной полноты. Полнота по неявной сводимости и параметрической выразимости в Рк при систем, содержащих все одноместные функции
- Критерий неявной шефферовости
- Неявно полные классы, содержащие две константы
- Классы монотонных функций
Введение к работе
Настоящая диссертация посвящена исследованию проблемы полноты по неявной выразимости в трехзначной логике Рз.
Понятие неявной выразимости является одним из обобщений понятия функциональной выразимости функций /г-значной логики (выразимости функций Ахзначной логики посредством суперпозиций), введенных А.В.Кузнецовым [11] наряду с другими: неявной сводимостью и параметрической выразимостью.
Функция называется выразимой над системой Е посредством суперпозиций (или функционально выразимой) [18], если ее можно представить в виде суперпозиции функций из Е. Множество всех функций, выразимых по суперпозиции над системой Е, называется замыканием по суперпозиции (или просто замыканием) системы Е и обозначается через [Е].
Функция называется явно выразимой [11] над системой Е, если она выразима над системой EjJ{x} посредством суперпозиций. Множество всех функций, явно выразимых над системой Е, называется явным замыканием системы Е и обозначается через -Е^Е).
Рассмотрим систему функций /с-зиачной логики Е и систему уравнений над Е:
Аі(хі,...,хп,у!,...,ур,г) = Bx(xi,...,xn, t/i,..., уР, z), А2(хи..., хп, ух,..., ур, z) = В2{хи ...,хп, 7/1, ...,ур, z),
k Am(xi,...,xn,yi,...,yp,z) = Bm(xi,...,xn,yu...,yp,z).
где Лі,..., Ат, -Si,..., Bm — функции, явно выразимые над системой Е. Говорят, что указанная система уравнений является параметрическим представлением функции f(x\,..., хп), f Є Pk, над системой функ-
ций Е, если она имеет хотя бы одно решение
2/1 = 9i(xi,...,xn),
Ур = 9р\Х\) ) хп), z = 9o(xi,...,xn),
где gi(x\,..., хп) Є Pk, г — О,... ,р, — функции от основных переменных, причём для любого такого решения имеет место равенство go(xi,..., хп) = /(xi,..., хп). Если параметры отсутствуют (т. е. р = 0), то говорят, что рассматриваемая система уравнений является неявным представлением функции f(xi,..., хп) над Е.
Функция / называется параметрически (неявно) выразимой над системой Е, если для нее существует параметрическое (неявное) представление над Е.
Множество всех функций, параметрически (неявно) выразимых над системой Е, называется параметрическим замыканием (неявным расширением) системы Е.
Параметрическое замыкание системы Е обозначается через Р(Е), а неявное расширение через /(E).
Отметим тот факт, что в случае неявной выразимости используется термин "неявное расширение", в то время как в случае параметрической — "параметрическое замыкание".
Действительно, отношение неявной выразимости в Pk при к ^ 3 не транзитивно. А именно, если функция / неявно выразима над /(E), т.е. принадлежит /(/(E)), то из этого, вообще говоря, не следует, что функция / неявно выразима над Е. Более того, неявное расширение /(E) системы функций Е может не совпадать не только со своим неявным расширением /(/(E)), но и со своим явным замыканием Е(1(Т,)).
В качестве примера, иллюстрирующего это свойство неявной выразимости, можно привести класс Р\ всех одноместных функций в Р\. Как показано в диссертации, его неявное расширение не совпадает с Р\, по полно в Р^ по суперпозиции.
Параметрическая выразимость транзитивна в вышеуказанном смысле, и операция параметрического замыкания является операцией замыкания в обычном смысле (подробнее см. [11]).
Обозначим через /т(Е) результат т-й итерации операции неявного расширения по отношению к системе Е, полагая Iі(Е) = /(E) и /m(E) = /(/т_1(Е)) для всякого натурального т, тп ^ 2.
Функция / называется выразимой над системой функций Е по неявной сводимости [11], если найдется т Є N такое, что / принадлежит
/m(E). Класс, состоящий из всех функций, выразимых над Е по неявной сводимости, называется замыканием системы функций Е по неявной
сводимости и обозначается /(Е). Таким образом, /(Е) = (J /Ш(Е).
пг=0
Для любой системы функций Е выполняются включения:
S С [Е] С (Е) С /(E) С /(Е) С Р(Е).
Система Е С Pfc называется явно (по суперпозиции (функционально), параметрически, неявно, по неявной сводимости) полной в Рк, если её явное замыкание (замыкание но суперпозиции, параметрическое замыкание, неявное расширение, замыкание по неявной сводимости) совпадает
cPfe-
Система Е С Рк называется явно (по суперпозиции (функционально), параметрически, неявно, по неявной сводимости) предполной в Pfc, если эта система не является явно (по суперпозиции (функционально), параметрически, неявно, по неявной сводимости) полной в Рк, в то время как любая система, содержащая ее в качестве собственной подсистемы, явно (по суперпозиции (функционально), параметрически, неявно, по неявной сводимости) полна в Pfc.
В случае двузначной логики Р2 проблема функциональной полноты была полностью решена Э. Постом [24, 25]. Им была описана структура всех замкнутых по суперпозиции классов в Р2 и показано, что число замкнутых классов в Р2 счетно, при этом всякий замкнутый класс имеет конечный базис. Критерий полноты в Р2 был независимо получен С. В. Яблонским (см. [18], а также [20]). Впоследствии С. В. Яблонским [18] был получен критерий функциональной полноты в трехзначной логике Рз. Как и в Р2, в Р3 была найдена конечная система предполных классов, из невхождения системы функций в которые следует ее полнота. Критерий функциональной полноты в терминах предполных классов в Р4 получил А. И Мальцев [13]. А.В.Кузнецовым [12] было доказано, что система всех предполных классов в Рк конечна. Хотя теорема Кузнецова дает алгоритм построения такой системы классов, этот алгоритм даже при небольших значениях к связан с трудоемкими вычислениями и мало пригоден для практического использования. Нахождению всех предполных классов в Рк при произвольных конечных значениях к было посвящено немало работ, завершением которых стала работа И.Розспберга [26]. Описание предполных классов в [2G] основано на введенном А.В.Кузнецовым понятии сохранения предиката (см. [20]).
Для многозначных логик Рк при к ^ 3 одним из важнейших результатов, касающихся функциональной полноты, является теорема Слупец-
кого [28], утверждающая, что в Рк при к ^ 3 система функций, содержащая все одноместные функции, полна тогда и только тогда, когда она содержит существенную функцию (существенно зависящую более чем от одной переменной), принимающую все к значений.
Еще одна задача, относящаяся к теории функциональной полноты, — это задача распознавания в Рк шефферовых функций. Шефферовой называется функция, которая одна составляет полную в Рк систему. Простейший критерий шефферовости был получен Н.М.Мартином [23] на основе критерия Слупецкого. В дальнейшем были получены другие критерии шефферовости в Pz, Рз и Рк при к > 3, основанные на результатах Э. Л. Поста, С. В. Яблонского и И. Розепберга. Критерий шефферовости в Pfc в терминах минимальной системы предполных классов дан В. Б. Кудрявцевым [7]. Большое значение для целей данной работы имеет критерий Руссо [27], полученный как следствие теоремы Розенберга.
А. В. Кузнецов [11] привел примеры, доказывающие неэквивалентность функциональной, неявной, параметрической выразимости и неявной сводимости уже в Рз- Тем не менее, в Рг параметрическая выразимость, неявная сводимость и неявная выразимость эквивалентны. Эквивалентность параметрической выразимости и неявной сводимости в Р2 была доказана А. В. Кузнецовым в работе [11], а позднее О. М. Касим-Заде [4] доказал эквивалентность параметрической и неявной выразимости. А. В. Кузнецовым [11] был получен критерий параметрической выразимости в Р/с, а также полное описание системы всех параметрически замкнутых классов в Р2 и вытекающий из него критерий параметрической полноты в Р2. Критерий параметрической полноты в трёхзначной логике Рз был получен А. Ф. Данильченко в работе [3]. А в работе [21] С. Баррисом и Р. Уиллардом была показана конечность числа параметрически замкнутых классов в Pk для всех конечных значений к. Критерий полноты по неявной выразимости в Р2 установлен О. М. Касим-Заде [4].
И. В. Куку и М. Ф. Раца были получены критерии полноты по параметрической выразимости и неявной сводимости для некоторых специальных логик [8, 9, 15, 16].
В настоящей диссертации решены несколько основных проблем, связанных с понятием полноты систем функций по неявной выразимости в Рз. А именно, установлены критерии неявной полноты систем функций в Рз и неявной шефферовости в Рз. Кроме того, установлен критерий неявной полноты в Рк при к > 2, в некотором смысле являющийся аналогом критерия Слупецкого.
Работа состоит из трех глав.
В первой главе формулируется и доказывается критерий неявной пол-
поты в Pk, к ^ 2, аналогичный критерию Слупецкого.
Теорема (Е. Слупецкий). Для того, чтобы система функций из Pk, k ^ 3, содержащая все одноместные функции из Pk, была полной по суперпозиции, необходимо и достаточно, чтобы она содероісала также существенную функцию, принимающую все к значений.
Теорема Слупецкого была усилена С.В.Яблонским [18].
Теорема (С.В.Яблонский). Для того, чтобы система функций из Pk, к ^ 3, содероісащая все одноместные функции из Pk, выпускающие хотя бы одно значение, была полной по суперпозиции, необходимо и достаточно, чтобы она содероісала также существенную (функцию, принимающую все к значений.
Класс функций в Pk, состоящий из всех одноместных функций и всех существенных функций, выпускающих хотя бы одно значение, называют классом Слупецкого. Из теоремы Слупецкого следует, что этот класс является единственным предполным классом в Pk, содержащим все одноместные функции.
В диссертации показано, что относительно неявной выразимости аналогичными свойствами обладает минимальный замкнутый по суперпозиции надкласе класса всех одноместных функций PJ: ' — класс УХк квазилинейных функций [2]. Функция называется квазилинейной, если она имеет вид:
f(xi, ...,хп) = g(fi(xi) Є /пЫ),
где <7,/ъ . ,/п ~ одноместные функции, а обозначает сложение по модулю к.
Следствия из критерия неявной полноты. Полнота по неявной сводимости и параметрической выразимости в Рк при систем, содержащих все одноместные функции
Воспользуемся теоремой Слупецкого и получим, что система всех одноместных функций полна по неявной сводимости в Р4. Теорема доказана. Теорема 6. Система всех одноместных функций полна по неявной сводимости в Pk при k 4. Доказательство. Случай Р4 был рассмотрен в предыдущей теореме. Рассмотрим в Pk при к 5 одноместные функции, представленные в табл. 7. Покажем, что она задает неявное представление существенной функции, принимающей четыре значения. Эта функция на подмножестве {0,1,2,3} множества Ek совпадает с функцией, неявное представление которой было построено в теореме 5. Далее действуем аналогично доказательству теоремы 5. Возможные значения у из 1-го уравнения приведены в табл. 8, а возможные значения у из 2-го уравнения — в табл.9. Эта функция существенна и принимает четыре значения. Она выделяет вершину квадрата, т. е. является неквазилинейной. Воспользуемся теоремой 2 из настоящей работы и получим, что система всех одноместных функций полна по неявной сводимости в Рк при к 5. Теорема доказана. Доказательство. Предположим, что это не так, и существует функция, выделяющая вершину некоторого квадрата, для которой имеется неявное представление над классом 9Тз- Подставим в функцию и в ее неявное представление соответствующие константы на место всех постоянных компонент этого квадрата и получим неявное представление двухместной функции F(xi,x2), выделяющей вершину квадрата. Поскольку F принимает только три значения, какие-то два значения она на этом квадрате принимает дважды. Пусть этот квадрат — неявном представлении должно присутствовать уравнение для которого A{ot\,t) ф B{a\,t). И, как для каждого уравнения в неявном представлении, выполняются следующие равенства: Но {(сії, t), (а2, m), (аз, га), (Й4, t)} — квазиквадрат. Поэтому найдется такая вершина (cti,F(ai)), что Тогда B{a\,t) = B(ai,F(ai)) и A(ai,t) = B(ai,t).
Получили противоречие. Таким образом, наше предположение неверно, и класс У\3 совпадает со своим неявным расширением. Теорема доказана. Основываясь на полученных результатах, построим таблицу, иллюстрирующую полноту класса одноместных функций Р (а равно и класса Vlk, как следует из теорем 1 - 7) в Р& при различных значениях к по отношению к различным типам выразимости (табл. 11). Условимся ставить в графе таблицы знак «+», если класс PJ: полон в Pk по соответствующему строке таблицы типу выразимости, и знак «—» — в противном случае. Функция называется шефферовой, если она одна образует функционально полную систему. Для неявной выразимости [11] естественным образом возникает аналогичное понятие неявно шефферовой функции — функции, которая одна образует неявно полную систему. Простейший критерий шефферовости был получен Н. М. Мартином [23] на основе критерия Слупецкого. В дальнейшем на основании результатов Э. Л. Поста, С. В. Яблонского и И. Розенберга были получены другие критерии шефферовости в Р2, Рз и Р при к 3. В случае неявной выразимости известен только критерий неявной шефферовости в Лг, непосредственно вытекающий из результатов О. М. Ка-сим-Заде [4, 6]: в / функция является неявно шефферовой тогда и только тогда, когда она функционально шефферова, т. е. не сохраняет констант и несамодвойственная. В настоящей главе сформулирован и доказан критерий неявной шефферовости в Рз. Глава состоит из трех разделов. В первом разделе даются необходимые определения и формулируются известные результаты, используемые при доказательстве критерия, во втором формулируются и доказываются необходимые условия неявной шефферовости, в третьем формулируется и доказывается основная теорема — критерий неявной шефферовости В Рз. Дадим определения функционально шефферовой и неявно шефферовой функции. Определение 7. Функция /(хі,...,хп) Є Pfc, где к 2, такая, что [{/}] = Pfc, называется шефферовой (функционально шефферовой). Определение 8. Функция f(x-[,... ,хп) Є Pfc, где к 2, такая, что /({/}) = Pfc, называется неявно шефферовой. Приведем критерии функциональной шефферовости в Рг и Рз, необходимые для дальнейшего изложения. Эти критерии можно либо вывести из критериев полноты в Р2 и Рз соответственно [18], либо получить как следствия из общего критерия Руссо [27]. Теорема1 Г. Функция f шефферова в Р2 тогда и только тогда, когда она несамодвойствегшая и не сохраняет констант. Под самодвойственной в Рз функцией всюду в данной работе понимается функция, самодвойственная относительно циклической подстановки (012) на множестве Е3 = {0,1,2} (см. [18]). Теорема II . Функция f шефферова в Рз тогда и только тогда, когда она несамодвойственная и не сохраняет констант, двухэлементных подмноэ/сеств и нетривиальных разбиений. Как было замечено ранее, в Р2 всякая неявно шефферова функция является функционально шефферовой и наоборот. Приведем также два критерия неявной полноты в Р2. Эти результаты были получены О. М. Ка-сим-Заде. Первый из них сформулирован и доказан в работе [6], второй является непосредственным следствием первого. Под конъюнкцией и дизъюнкцией всюду в этой работе понимаются булевы функции двух переменных xhy и х V у соответственно. Понятие перестановочности описано ниже в данном разделе. Теорема III . Система функций Е неявно полна в Р2 тогда и только тогда, когда в ней содержатся функции: нелинейная, несамодвойственная, не сохраняющая константу 0, не сохраняющая константу 1, не перестановочная с конъюнкцией и не перестановочная с дизъюнкцией. Теорема IV. Система функций Е неявно полна в Р2 тогда и только тогда, когда над Е по суперпозиции выразимы константы 0 г 1, конъюнкция и дизъюнкция. Теоремы Г-IV эквивалентны теоремам I-IV из Ведения к диссертации.
Критерий неявной шефферовости
Сформулируем критерий неявной шефферовости в трехзначной логике. Обозначим через TQ,T? И Т23 классы функций в Р3, сохраняющих константы 0, 1 и 2 соответственно, и через 53 класс функций, самодвойственных относительно циклической подстановки (012) (эти обозначения соответствуют принятым в [18]). Теорема 8. Функция f является неявно шефферовой в Рз тогда и только тогда, когда она не припадлеэюит ни одному из следующих 22 icnnrmn- Т3 Т3 Т3 73 У 0,1 V 2} V{1,2 у 0-1}- 2} у{ 2}.(1} у(Д}.{2} {1,2),(0} {0,2),(1} {1,2),(0} r(0,l},{2} V{0,2},{1} v(l,2},(0} {0,1),(2} {0,2),(1} y{h2},{0] V{0,1},{2} V(0,2},{1} y,{l,2},{0} Как показано выше, непринадлежность функции этим классам является необходимым условием неявной шефферовости. Следовательно, необходимость условий теоремы доказана. Сопоставив условия теоремы 8 с критерием функциональной шефферовости в Р3, можно переформулировать критерий неявной шефферовости следующим образом. Теорема 9. Функция f является неявно шефферовой в Р3 тогда и только тогда, когда она не сохраняет констант, и удовлетворяет одному из условий: 1) f не сохраняет двухэлементных подмнооїсеств, нетривиальных разбиений и не является самодвойственной; 2) f сохраняет некоторое двухэлементное подмножество {а, Ь}, не сохраняет чужих ему нетривиальных разбиений и не является {а, Ь}-самодвойствениой; 3) f сохраняет некоторое нетривиальное разбиение {а, Ь}, {с}, не сохраняет двухэлементных подмножеств и относительно этого разбиения не является блочно-линейной, блочпо-самодвойственной, блочно-перестановочпой с конъюнкцией или блочно-перестановочпой с дизъюнкцией. Для доказательства достаточных условий рассмотрим отдельно функции, сохраняющие подмножество и функции, сохраняющие разбиение. Без ограничения общности будем считать, что исследуемая на шеффе-ровость функция сохраняет подмножество {0,1}. Теорема 10. Если функция f Є / сохраняет подмножество {0,1}, не сохраняет чужих ему нетривиальных разбиений, констант и не является {0,1} -самодвойственной, то она является неявно шефферовой вР3. Для доказательства этой теоремы используется несколько лемм. Лемма 8. Если функция / Є Рз сохраняет подмножество {0,1}, не сохраняет констант и не является {0,1} -самодвойственной, то над {/} по суперпозиции выразима функция F вида Доказательство. Утверждение леммы следует из критерия функциональной ШсфферОВОСТИ В Р-2,. Лемма 9. Система 93, состоящая из функций неявно полна в Р . Доказательство. Введём в рассмотрение функции Такая функция принимает только значения 0 и 1, причем значение 1 — только на наборе а. Уравнение является тождеством при (xi,..., хп) ф (c i,..., an), а при (х\,..., хп) = (ai,..., схп) обращается в верное равенство тогда и только тогда, когда у = /(QJ, ..., an). Написав такие уравнения для всех наборов а, получим неявное представление функции /(xi,..., хп). Теперь произвольную функцию вида An,...,Qn(xi,... ,хп) выразим через функции системы Ш.
Введём вспомогательную функцию представить в виде суперпозиции функций M(xi,x2) и одноместных функций hc(x), где с Є {0,1,2}: Лемма доказана. а также двух различных одноместных функций, принимающих только значения 0 и 1, причём значение 1 — только на одном наборе, неявно полна в Рз Доказательство. Рассмотрим все возможные пары одноместных функций, удовлетворяющих условиям леммы, и для каждой из них докажем полноту системы Е. Возможны три случая. Во всех трёх случаях полученные системы неявно полны по лемме 9. Лемма доказана. Лемма 11. Если функция / Є Рз сохраняет подмножество {0,1}, не сохраняет чужих ему разбиений, констант и не является {0,1}-самодвойственной, то над {/} по суперпозиции выразимы две различные одноместные функции, принимающие только значения 0 и 1, причём значение 1 — только на одном наборе. Доказательство. По лемме 8 над {/} по суперпозиции выразима 1 0 функция F вида: 0 0 . Далее, рассмотрим диагональ функции /, равную f(x,...,x). Обозначим сё через d(x). Эта функция имеет вид 1 0 , где а равно 0 или 1, поскольку / не сохраняет констант и сохраняет а подмножество {0,1}. Рассмотрим отдельно случаи: а = 0 и а = 1. 1) а — 0. В качестве одной из двух искомых одноместных функций возьмём d(x). Построим вторую функцию. Выразим по суперпозиции константы 0 и 1: Функция / не сохраняет разбиения {1,2}, {0}. Тогда найдутся два набора, эквивалентные относительно этого разбиения, на которых / принимает неэквивалентные значения. Для наибольшей ясности изложения рассмотрим отдельно случай, когда эта пара наборов принадлежит главному блоку, т. е. состоит из 1 и 2, а потом разберём случай пары наборов из произвольного блока. а) а — набор, состоящий из 1 и 2 такой, что /(а) ф 0. Заметим, что в этом случае достаточно рассмотреть один набор, поскольку /(1,..., 1) = . Подставим в / константу 1 вместо переменных, соответствующих единицам в наборе а, и отождествим все остальные переменные. Получим 6 одноместную функцию h{x) = 0 , где обозначим через t(x). Она равна 0 или 0 . В первом случае получаем искомую одноместную функцию. Во втором случае искомой функцией будет t(t(x)) = 1 . б) а и /3 — наборы, эквивалентные относительно разбиения {1,2}, {0}, на которых функция / принимает неэквивалентные значения. Поскольку а и Р эквивалентны, все нули, присутствующие в этих наборах, стоят в одних и тех же позициях. Подставим в / константу 0 вместо переменных, соответствующих пулям в этой паре наборов. Получим некоторую функцию / от меньшего числа переменных, принимающую неэквивалентные значения на двух эквивалентных наборах а и /3 , состоящих из 1 и 2. Значит, на одном из двух наборов а или /? значение функции / неэквивалентно / (1,...,1), причем, / (1,...,1) ф 2. Подставив в / константу 1 вместо всех единиц этого набора, получаем функцию h (x), равную 0 или 1 , где b ф 2, с ф 0. Первый случай уже факти чески разобран в предыдущем пункте. Во втором случае функция h (x) равна 1 или 1 . Первая из этих функций удовлетворяет требованиям искомой функции. Во втором случае имеем d(h(x)) = 0 . 1 2) а = 1. В качестве одной из двух искомых одноместных функций 0 возьмем d(d(x)) — 1 . Построим вторую. Выразим по суперпозиции
Неявно полные классы, содержащие две константы
Подставим в / функцию /2(2 ) вместо переменных х;, соответствующих 4-му и 6-му столбцам матрицы, и fs( j) вместо переменных Xj, соответствующих 5-му и 7-му столбцам матрицы Р. Отождествим переменные, соответствующие 4-му и 5-му, а также 6-му и 7-му столбцам матрицы. Остальным столбцам матрицы соответствуют константы. Подставим константы вместо соответствующих переменных. Получим функ d а цию двух переменных q(x,y), имеющую вид: , где a, b Є {0,1}. 6 2 а) d = 2. В этом случае рассмотрим функцию е(у) = q(0,y): е(0) = 2, е(2) ф 2. Тогда, действуя как в случае 1, получим функцию г(х). б) d ф 2. В этом случае /2(9(/2( )1 /2(2/))) = 22( ,2/)- Лемма доказана. Все функции из условий леммы 30 и леммы 31, кроме т{х) и Р22(я, у), принадлежат классу i?2, поэтому совокупность лемм 30 - 32 доказывает теорему. 3.3 Неявно полные классы, содержащие две константы 4. Неявно полные классы, содержащие две константы Пусть класс функций XV явно замкнут, неявно полон в Р3 и содержит ровно две константы (без ограничения общности — 0 и 1). Тогда все функции класса XV сохраняют подмножество {0,1}. Действительно, если это не так, то в XV найдется функция /, не сохраняющая это подмножество, т. е. на некотором наборе, состоящем из пулей и единиц, функция / принимает значение 2. Подставив константы 0 и 1 вместо соответствующих аргументов этой функции, получим константу 2. В табл. 14 приведен список всех одноместных функций, сохраняющих подмножество {0,1}. Поскольку все функции из W сохраняют подмножество {0,1}, класс XV должен быть полон неявно на этом подмножестве. Тогда к рассмат ривасмому случаю применим критерий неявной полноты в Р2. Согласно этому критерию, в W должны найтись две функции следующего вида: Поскольку эти функции на {0,1} имеют вид конъюнкции и дизъюнкции, будем называть их обобщенной конъюнкцией и обобщенной дизъюнкцией и будем для них использовать обозначения из двузначной логики & и V, подразумевая под этим любые функции такого вида. Основываясь на том, что над W существует неявное представление любой функции трехзначной логики, выясним, какие комбинации одноместных функций могут входить в класс W. Следовательно, взяв диагонали этих функций, получаем, что в W должны найтись две одноместные функции, различающиеся только на нулевом наборе.
Следовательно, взяв диагонали этих функций, получаем, что в W должны найтись две одноместные функции, различающиеся только на единичном наборе. Выпишем все пары одноместных функций, удовлетворяющие условиям пп. 1 и 2. 1. W содержит одну из следующих пар функций: Добавим к каждой паре все одноместные функции, которые можно получить из нее с помощью суперпозиций, и уберем константы и тривиальную функцию f(x) = х: Отбросим все повторяющиеся функции. Добавим к каждому набору функций все одноместные функции, которые можно получить из имеющихся функций с помощью суперпозиций (кроме констант и х): Следовательно, W содержит один из наборов одноместных функций: Рассмотрим каждый из этих наборов по отдельности. I. Покажем, что всякая система, содержащая обобщённую конъюнкцию, обобщённую дизъюнкцию и функции и(х) и v(x), неявно полна. Доказательство. Возьмем произвольный набор а. Для удобства записи будем считать, что ft! = = ат = 0, ftm+i = = ат+р = 1, ctm+p+i = = an = 2. Рассмотрим функцию — если хотя бы одна из переменных хт+і,..., хт+Р принимает значение — если xm+i = = хт+р = 1 и хотя бы одна из переменных Zm+p+ii ) хп принимает значение 0, то Оа(х\, , хп, у) = 0; — если хт+ї = — хт+р = 1, переменные хт+р+\,... ,хп принимают значения 1 и 2 и хотя бы одна из переменных х\,..., хт принимает значение 1 или 2, то Ой(жі,..., хп, у) = 1; — принимают значения 1 и 2, а хотя бы одна из переменных Хт+р+1, -,хп принимает значение 1, то OQ(XI, ..., хп, у) = 1; ЄСЛИ Х\ = Хул — и, Xm+i = Хтл -р = 1, Хт .р-\-\ = == Хп = 2, то 0&(xi,...,xnty) = у. Заметим, что т, р или п — т — р могут быть равны нулю. В этом случае соответствующие части выражения просто отбрасываются. Построим неявное представление произвольной функции /. Для каждого набора а в зависимости от значения f(a) включим в неявное представление следующие уравнения. 1. Если /(а) = 0, то Это уравнение обращается в тождество на всех наборах значений переменных х, кроме х = а, на котором обращается в верное равенство только при у = 0. 2. Если f(a) = 1, то Это уравнение обращается в тождество на всех наборах значений переменных х, кроме х = а, на котором обращается в верное равенство только при у = 1. 3. Если /(a) = 2, то Эти уравнения обращаются в тождества на всех наборах значений переменных х, кроме х = а, на котором первое обращается в верное равенство только при у = 0 и у — 2, второе — только при у = I и у = 2, а оба одновременно — только при у = 2. Таким образом, неявное представление функции / построено. Лемма доказана.
Классы монотонных функций
Пусть в W содержатся все три константы и класс W явно замкнут и неявно полон. При этом W содержится в классе монотонных функций и не содержится ни в одном из классов сохранения разбиений. Без ограничения общности далее будем рассматривать класс функций, монотонных относительно порядка 0 1 2. В табл. 20 приведен список всех одноместных функций, принадлежащих этому классу. общности будем считать, что d\ с/г- Поскольку обе рассматриваемые функции монотонны и их значения па наборах (0,1) и (1,0) — а и Ь соответственно — совпадают, верны d2 a, d\ d2 b. Отсюда следует, что значения первой Без ограничения общности будем считать, что d\ с - Поскольку обе b , где di 7 d2. d2 рассматриваемые функции монотонны и их значения па наборах (1,2) и (2,1) — бис соответственно — совпадают, верпы со) двойственна системе (5) относительно (0)(12) и неявно полна. Заметим, что из второй системы можно явно получить 2,1 1 1 , 112, подставив во вторую функцию 1 от обеих переменных. А эта система двойственна системе (6) относительно (1)(02) и неявно полна. Для монотонных функций теорема 20 доказана. Классы вида Т зд являются явно предполными в Рз [18]. Без ограничения общности будем далее рассматривать класс Т2І. Как показано в [18], fix) принадлежит Т2І тогда и только тогда, когда для любых чисел Qi,... ,ап, равных 0 и 1, функция /(х) па всех наборах /3 = (/?i,..., рп), где Pi ф ai(i = 1,2,..., п), выпускает по крайней мере одно из значений 0 или 1. Пусть в системе функций W содержатся все три константы и класс W явно замкнут и неявно полон. При этом W не содержится ни в одном из классов сохранения разбиений и ни в одном из классов монотонных функций. В табл. 21 приведен список всех одноместных функций, принадлежащих классу Т2)1. Заметим, что если W содержит функцию, не сохраняющую какое-либо разбиение, то она содержит одноместную функцию, не сохраняющую это разбиение. Действительно, нетрудно видеть, что найдутся два соседних набора, эквивалентных относительно этого разбиения, на котором рассматриваемая функция принимает неэквивалентные значения. Подставив теперь в нее константы, получим одноместную функцию с таким же свойством. Поскольку в классе Т\ х нет одноместной функции, не сохраняющей все три разбиения, можно выделить следующие три случая. 1. W содержит три одноместные функции отношения: b d\ d2, с d\ d2. Отсюда следует, что значения первой функции на всех наборах, кроме (2,2), меньше с . Тогда, подставляя эту функцию в одну из одноместных функций 2 и 0 , получим функцию 0 0 0 , а в одну из функций 2 и 1 1 1 — функцию 111. 1 1 2
Следовательно, если система W содержится в классе монотонных функций, не сохраняет разбиений {0,1}, {2} и {1,2}, {0} и неявно полна, то она содержит одну из пар функций: Система (10) двойственна системе (5) относительно (0)(12) и неявно полна. Заметим, что из второй системы можно явно получить 2,1 1 1 , 112, подставив во вторую функцию 1 от обеих переменных. А эта система двойственна системе (6) относительно (1)(02) и неявно полна. Для монотонных функций теорема 20 доказана. Классы вида Т зд являются явно предполными в Рз [18]. Без ограничения общности будем далее рассматривать класс Т2І. Как показано в [18], fix) принадлежит Т2І тогда и только тогда, когда для любых чисел Qi,... ,ап, равных 0 и 1, функция /(х) па всех наборах /3 = (/?i,..., рп), где Pi ф ai(i = 1,2,..., п), выпускает по крайней мере одно из значений 0 или 1. Пусть в системе функций W содержатся все три константы и класс W явно замкнут и неявно полон. При этом W не содержится ни в одном из классов сохранения разбиений и ни в одном из классов монотонных функций. В табл. 21 приведен список всех одноместных функций, принадлежащих классу Т2)1. Заметим, что если W содержит функцию, не сохраняющую какое-либо разбиение, то она содержит одноместную функцию, не сохраняющую это разбиение. Действительно, нетрудно видеть, что найдутся два соседних набора, эквивалентных относительно этого разбиения, на котором рассматриваемая функция принимает неэквивалентные значения. Подставив теперь в нее константы, получим одноместную функцию с таким же свойством. Поскольку в классе Т\ х нет одноместной функции, не сохраняющей все три разбиения, можно выделить следующие три случая. 1. W содержит три одноместные функции, каждая из которых сохраняет одно из разбиений. В табл. 28а) и 286) приведены все тройки функций с таким свойством. Эти системы двойственны относительно (01)(2). Класс Т д двойствен себе относительно этой подстановки. Поэтому будем рассматривать только первую. Расширим ее по суперпозиции, отбросив константы и селекторы (табл. 29). 2. IV содержит две одноместные функции, /1,/2, каждая из которых не сохраняет два разбиения, и одно из разбиений не сохраняют они обе. В табл. 30 - 37 приведены все пары функций с таким свойством. Заметим, что пары функций, приведенные в табл. 30 и 33, 31 и 32, 34 и 37 соответственно, двойственны относительно (01)(2). Поэтому будем рассматривать только системы, приведенные в табл. 30, 31, 34, 35 и 36. Расширим эти системы по суперпозиции, отбросив константы и тривиальные одноместные функции (табл. 30 , ЗГ, 34 , 35 и 36 ).