О критериях полноты по неявной выразимости в трехзначной логике

• Автор: Орехова, Елена Андреевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Москва
• Количество страниц: 110 с.

Виедение
1 Аналог критерия Слупецкого для неявной выразимости
в Рк
1.1 Критерий неявной полноты в /с-значной логике
1.2 Следствия из критерия неявной полноты. Полнота по неявной сводимости и параметрической выразимости в Рк при
к ^ 2 систем, содержащих все одноместные функции
2 Критерий неявной шефферовости в трёхзначной логике 30 • 2.1 Основные определения и известные результаты
2.2 Необходимые условия неявной шефферовости
2.2.1 Функции, сохраняющие подмножество
2.2.2 Функции, сохраняющие разбиение
2.3 Критерий неявной шефферовости
2.3.1 Функции, сохраняющие подмножество
2.3.2 Функции, сохраняющие разбиение
3 Критерий неявной полноты в трёхзначной логике
3.1 Неявно полные классы, не содержащие констант
3.2 Класс
3.3 Неявно полные классы, содержащие две константы
3.4 Неявно полные классы, содержащие три константы
3.4.1 Классы сохранения разбиений
3.4.2 Классы монотонных функций
3.4.3 Классы вида Т|.,
3.4.4 Класс Слупецкого
3.4.5 Основной результат

Настоящая диссертация посвящена исследованию проблемы полноты по неявной выразимости в трехзначной логике /3.
Понятие неявной выразимости является одним из обобщений понятия функциональной выразимости функций А>зпачной логики (выразимости функций /г-значной логики посредством суперпозиций), введенных А. В. Кузнецовым [11] наряду с другими: неявной сводимостью и параметрической выразимостью.
Функция называется выразимой над системой Е посредством суперпозиций (или функционально выразимой) [18], если ее можно представить в виде суперпозиции функций нз Е. Множество всех функций, выразимых по суперпозиции над системой Е, называется замыканием по суперпозиции (или просто замыканием) системы Е и обозначается через
Функция называется явно выразимой [11] над системой Е, если она выразима над системой Еи(х} посредством суперпозиций. Множество всех функций, явно выразимых над системой Е, называется явным замыканием системы Е и обозначается через Е{Е).
Рассмотрим систему функций к-значной логики Е и систему уравнений над Е:
Аі(хи...,хп,уи...,ур,г) = В1(хі хп,уі ур, г), А2{хи...,хп,уі ур,г} = В2{х1 х„,уі ур,г),
. Атп(хі, • • -, хп, у 1, - • ■ , Ур, -) = Вт(х і хпі у і, . . . , Ур> х).
где Лі,, Ат, В і Вт — функции, явно выразимые над системой Е.
Говорят, что указанная система уравнений является параметрическим представлением функции /(її хп), / Є Рк, над системой функций Е, если она имеет хотя бы одно решение Уі 1?і(хі, - • •) х„),
Ур = 9Р(х Z 5о(хі, • • • ) Хп),
где , £„) Є Рк,і=0 р, — функции от основных переменных,
причём для любого такого решения имеет место равенство до{х хп) = /(хь... ,хп). Если параметры отсутствуют (т. е. р = 0), то говорят, что рассматриваемая система уравнений является неявным представлением функции /(хь ..., хп) над Е.
Функция / называется параметрически (неявно) въцюзимой над системой Е, если для псе существует параметрическое (неявное) представление над Е.
Множество всех функций, параметрически (неявно) выразимых над системой Е, называется параметрическим замыканием (неявным расширением) системы Е.
Параметрическое замыкание системы Е обозначается через Р(Е), а неявное расширение через /(Е).
Отметим тот факт, что в случае неявной выразимости используется термин "неявное расширение", в то время как в случае параметрической — "параметрическое замыкание".
Действительно, отношение неявной выразимости в 1 при к ^ 3 не транзитивно. А именно, если функция / неявно выразима над 1(Е), т. е. принадлежит /(/(Е)), то из этого, вообще говоря, не следует, что функция / неявно выразима над Е. Более того, неявное расширение /(Е) системы функций Е может не совпадать не только со своим неявным расширением /(/(Е)), но и со своим явным замыканием Р(/(Е)).
В качестве примера, иллюстрирующего это свойство неявной выразимости, можно привести класс Р4Х* всех одноместных функций в Р4. Как показано в диссертации, его неявное расширение не совпадает с Р4, по полно в Р4 по суперпозиции.
Параметрическая выразимость транзитивна в вышеуказанном смысле, и операция параметрического замыкания является операцией замыкания в обычном смысле (подробнее см. [И]).
Обозначим через Іт(Е) результат т-й итерации операции неявного расширения по отношению к системе Е, полагая /Х(Е) = /(Е) и /т(Е) = 7(/т_1(Е)) для всякого натурального т, т > 2.
Функция / называется выразимой над системой функций Е по неявной сводимости [11], если найдется т Є N такое, что / принадлежит

Достаточно доказать, что для любого набора 7 = (71,, 7,1+1) найдётся пара функций А(х х,... ,хп+х) и В(х 1,... ,аг„+1), совпадающих на всех наборах, кроме 7ь ..., 7п+1-Ввсдём обозначения:
Покажем, что для любого набора 7, такого, что 71 = • • ■ = 7т = О, 7т+і = • • ■ = 7і = 1> 7і+і = • ■ • = 7п+і = 2, над системой Е явно выразимы функции А и Вх, которые всюду на блоке, содержащем 7, совпадают и принимают различные значения только на наборе 7. Группы компонент, равных 0, 1 или 2, в наборе 7 могут, вообще говоря, отсутствовать. Рассмотрим все возможные случаи.
1) т = і = 0. Тогда рассматриваемый блок состоит из единственного набора 7 и ЛДх) = 50(52(2:,,)), Вх(х) = 51(52(2:,,)).
2) т = 1, г = 0. Тогда А{х) = хх, В{х) = д{х).
3) т > 2, Ь = 0. Тогда ЛДх) = От(хи .. .,хт), Вх(х) = 5і(хі).
4) т = 0, ^ = 1. Тогда ^(х) = до{хі), В{х) = хх.
5) т = 0, і > 2. Тогда ЛДх) = К1(хх,-.. , х(), #х(х) = 50(2:1).
6) ш > 0, і > 0. Тогда Ах(х) = /Гт+1(хь... ,хт, <7о(хт+1)), Дх(х) = /Гт+1(х1,... ,хт, В1~т+1(хт+х,... ,£(, Возьмём произвольную функцию <7(2:1 х3). Рассмотрим функцию
Г 9{х), при у е {0,1},<7(х) € {0, 1}, Рх(д(хх х3),д2{у)) = < 2,при у = 2,
( а, при у 6 {0,1},д(х) = 2.
Построим теперь функции Л(х],... .Хп-н) и В(хь ... ,хп+1), полагая:
А = (^(... Р(... РДЛДх), 52(27)), 52(2:2)), • ■ ■, 52(24)), Х1+1), • ■ •, хп+х),
В = (^(... РД... РДПДх),52(11)),52(2:2)), • • • ,52(27)), хьн) хп+х).
Эти функции не совпадают только на одном блоке, на котором они равны А и Вх соответственно, и различны только на наборе 7. На остальных блоках по построению А = В. Лемма доказана.
К’(х х х3) = Р2{Р2(... Р2(хх,х2),х3),... ,х3), 1Г(х х х.) = Рз(Р3(. ..Л3(хьх2),хз),.. .,х5).
Рх(д(хх ха),у)
Тогда