О критериях полноты по неявной выразимости в трехзначной логике тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Орехова, Елена Андреевна

• Орехова, Елена Андреевна
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Орехова, Елена Андреевна

Введение

1 Аналог критерия Слупецкого для неявной выразимости

1.1 Критерий неявной полноты в /г-значной логике.

1.2 Следствия из критерия неявной полноты. Полнота по неявной сводимости и параметрической выразимости в Р(~ при к систем, содержащих все одноместные функции

2 Критерий неявной шефферовости в трёхзначной логике

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] над системой Е, если она выразима над системой EjJ{x} посредством суперпозиций. Множество всех функций, явно выразимых над системой Е, называется явным замыканием системы Е и обозначается через -Е^Е).

Рассмотрим систему функций /с-зпачной логики Е и систему уравнений над Е:

Ai(xi,.,xn,yx,.,yp,z) = 5i(xi>.,xnij/i,.,T/p,2), ^ A2(xu.,xn,yu.,yp,z) = B2(x1,.,xn>yi,.,yp,z), Am(xi,.,xn,yi,.,yp,z) = Bm(xi,.,xn,yu.,yp,z). где Ai,., Am, Bi,., Bm — функции, явно выразимые над системой Е.

Говорят, что указанная система уравнений является параметрическим представлением функции f(x 1,., хп), / G Pk, над системой функций Е, если она имеет хотя бы одно решение

Ух = 9х{хи.,хп),

Ур ~ > • • • > 2 = 9o(xi,. ,хп), где gi(x 1,., хп) € Р^, г = О,. ,р, — функции от основных переменных, причём для любого такого решения имеет место равенство <70(^1 > • • хп) = /(х 1,., хп). Если параметры отсутствуют (т. е. р = 0), то говорят, что рассматриваемая система уравнений является неявным представлением функции f(xi,. ., х„) над Е.

Функция / называется параметрически (неявно) выразимой над системой Е, если для нее существует параметрическое (неявное) представление над Е.

Множество всех функций, параметрически (неявно) выразимых над системой Е, называется параметрическим замыканием (неявным расширением) системы Е.

Параметрическое замыкание системы Е обозначается через Р(Е), а неявное расширение через 7(E).

Отметим тот факт, что в случае неявной выразимости используется термин "неявное расширение", в то время как в случае параметрической — "параметрическое замыкание".

Действительно, отношение неявной выразимости в Р^ при k ^ 3 не транзитивно. А именно, если функция / неявно выразима над /(Е), т.е. принадлежит /(/(E)), то из этого, вообще говоря, не следует, что функция / неявно выразима над Е. Более того, неявное расширение /(Е) системы функций Е может не совпадать не только со своим неявным расширением /(/(E)), но и со своим явным замыканием Е{1{Е)).

В качестве примера, иллюстрирующего это свойство неявной выразимости, можно привести класс Р^ всех одноместных функций в Р4. Как показано в диссертации, его неявное расширение не совпадает с Р4, по полно в Р4 по суперпозиции.

Параметрическая выразимость транзитивна в вышеуказанном смысле, и операция параметрического замыкания является операцией замыкания в обычном смысле (подробнее см. [11]).

Обозначим через /т(Е) результат т-й итерации операции неявного расширения по отношению к системе Е, полагая /*(Е) = /(Е) и /Ш(Е) = /(/т1(Е)) для всякого натурального m, т ^ 2.

Функция / называется выразимой над системой функций Е по неявной сводимости [11], если найдется т G N такое, что / принадлежит т(Е). Класс, состоящий из всех функций, выразимых над Е по неявной сводимости, называется замыканием системы функций Е по неявной оо сводимости и обозначается /°°(Е). Таким образом, I°°(Е) = (J Im(Е). гп=о

Для любой системы функций Е выполняются включения: S С [Е] С Е(Е) С /(Е) С /°°(Е) С Р(Е).

Система Е С Д. называется явно (по суперпозиции (функционально), параметрически, неявно, по неявной сводимости) полной в Рк, если её явное замыкание (замыкание но суперпозиции, параметрическое замыкание, неявное расширение, замыкание по неявной сводимости) совпадает с Рк.

Система ЕС Рк называется явно (по суперпозиции (функционально), параметрически, неявно, по неявной сводимости) предполной в Рк, если эта система не является явно (по суперпозиции (функционально), параметрически, неявно, по неявной сводимости) полной в ft, в то время как любая система, содержащая ее в качестве собственной подсистемы, явно (по суперпозиции (функционально), параметрически, неявно, по неявной сводимости) полна в Рк.

В случае двузначной логики Р2 проблема функциональной полноты была полностью решена Э. Постом [24, 25]. Им была описана структура всех замкнутых по суперпозиции классов в Р2 и показано, что число замкнутых классов в Р2 счетно, при этом всякий замкнутый класс имеет конечный базис. Критерий полноты в Р2 был независимо получен С. В. Яблонским (см. [18], а также [20]). Впоследствии С. В. Яблонским [18] был получен критерий функциональной полноты в трехзначной логике Р3. Как и в Р2, в Р3 была найдена конечная система предполных классов, из невхождения системы функций в которые следует ее полнота. Критерий функциональной полноты в терминах предполных классов в Р4 получил А. И Мальцев [13]. А.В.Кузнецовым [12] было доказано, что система всех предполных классов в Рк конечна. Хотя теорема Кузнецова дает алгоритм построения такой системы классов, этот алгоритм даже при небольших значениях к связан с трудоемкими вычислениями и мало пригоден для практического использования. Нахождению всех предполных классов в Рк при произвольных конечных значениях к было посвящено немало работ, завершением которых стала работа И.Розспберга [26]. Описание предполных классов в [2G] основано на введенном А.В.Кузнецовым понятии сохранения предиката (см. [20]).

Для многозначных логик Рк при к ^ 3 одним из важнейших результатов, касающихся функциональной полноты, является теорема Слупецкого [28], утверждающая, что в Рt при к ^ 3 система функций, содержащая все одноместные функции, полна тогда и только тогда, когда она содержит существенную функцию (существенно зависящую более чем от одной переменной), принимающую все к значений.

Еще одна задача, относящаяся к теории функциональной полноты, — это задача распознавания в Рк шефферовых функций. Шеффсровой называется функция, которая одна составляет полную в Pk систему. Простейший критерий шефферовости был получен Н.М.Мартином [23] на основе критерия Слупецкого. В дальнейшем были получены другие критерии шефферовости в Р2, Рз и Р/с ПРИ к > 3, основанные на результатах Э.Л. Поста, С. В. Яблонского и И. Розеиберга. Критерий шефферовости в Pk в терминах минимальной системы предполных классов дан В. Б. Кудрявцевым [7]. Большое значение для целей данной работы имеет критерий Руссо [27], полученный как следствие теоремы Розенберга.

А. В. Кузнецов [11] привел примеры, доказывающие неэквивалентность функциональной, неявной, параметрической выразимости и неявной сводимости уже в Рз. Тем не менее, в Р2 параметрическая выразимость, неявная сводимость и неявная выразимость эквивалентны. Эквивалентность параметрической выразимости и неявной сводимости в Р2 была доказана А. В. Кузнецовым в работе [11], а позднее О. М. Касим-Заде [4] доказал эквивалентность параметрической и неявной выразимости. А. В. Кузнецовым [11] был получен критерий параметрической выразимости в Pk, а также полное описание системы всех параметрически замкнутых классов в Р2 и вытекающий из него критерий параметрической полноты в Р2. Критерий параметрической полноты в трёхзначной логике Рз был получен А. Ф. Данильчеико в работе [3]. А в работе [21] С. Баррисом и Р. Уиллардом была показана конечность числа параметрически замкнутых классов в Pk для всех конечных значений к. Критерий полноты по неявной выразимости в Р2 установлен О. М. Касим-Заде [4].

И. В. Куку и М. Ф. Раца были получены критерии полноты по параметрической выразимости и неявной сводимости для некоторых специальных логик [8, 9, 15, 16].

В настоящей диссертации решены несколько основных проблем, связанных с понятием полноты систем функций по неявной выразимости в Рз. А именно, установлены критерии неявной полноты систем функций в Рз и неявной шефферовости в Р3. Кроме того, установлен критерий неявной полноты в Рк при к > 2, в некотором смысле являющийся аналогом критерия Слупецкого.

Работа состоит из трех глав.

В первой главе формулируется и доказывается критерий неявной полноты в Pk, к ^ 2, аналогичный критерию Слупецкого.

Теорема (Е. Слупецкий). Для того, чтобы система функций из Рк, к ^ 3, содержащая все одноместные функции из Рбыла полной по суперпозиции, необходимо и достаточно, чтобы она содерэ/сала такэ/се существенную функцию, принимающую все к значений.

Теорема Слупецкого была усилена С. В. Яблонским [18].

Теорема (С.В.Яблонский). Для того, чтобы система функций из Pk, к ^ 3, содержащая все одноместные функции из Рк, выпускающие хотя бы одно значение, была полной по суперпозиции, необходимо и достаточно, чтобы она содерэ/сала также существенную функцию, принимающую все к значений.

Класс функций в Pk, состоящий из всех одноместных функций и всех существенных функций, выпускающих хотя бы одно значение, называют классом Слупецкого. Из теоремы Слупецкого следует, что этот класс является единственным предполным классом в Pk, содержащим все одноместные функции.

В диссертации показано, что относительно неявной выразимости аналогичными свойствами обладает минимальный замкнутый по суперпозиции надкласс класса всех одноместных функций Pj, — класс УХк квазилинейных функций [2]. Функция называется квазилинейной, если она имеет вид: f(xu .,хп) = g(fi(xi) © • • • ф /п(х„)), где <7,/ь .,/п — одноместные функции, а ® обозначает сложение по модулю к.

Список литературы диссертационного исследования кандидат физико-математических наук Орехова, Елена Андреевна, 2004 год

1. Блохина Г. Н. О предикатном описании классов Поста // Дискретный анализ. - 1970. - Вып. 1G. - С. 16-29.

2. Бурле Г. А. Классы А;-значных функций, содержащие все функции одной переменной // Дискретный анализ. 1967. - Вып. 10. - С. 3-7.

3. Данильченко А. Ф. О параметрической выразимости функций трёхзначной логики // Алгебра и логика. 1977. Т. 16, № 4. С. 397-416.

4. Касим-Заде О. М. О неявной выразимости булевых функций // Вестник МГУ. Серия 1. Математика. Механика. 1995. № 2. С. 44-49.

5. Касим-Заде О. М. Об одной метрической характеристике неявных и параметрических представлений булевых функций // Математические вопросы кибернетики. Вып. 6. М. :Наука, 1996. С. 133-188.

6. Касим-Заде О. М. О неявной выразимости в двузначной логике и криптоизоморфизмах двухэлементных алгебр // Доклады РАН. 1996. Т. 348, N 3. С. 299-301.

7. Кудрявцев В. Б. Функциональные системы. М.: Изд-во Московского университета, 1982.

8. Куку И. В., О параметрической полноте систем формул в цепных логиках // Известия АН МССР. Серия физико-технических и математических наук. 1988. - № 3.

9. Кузнецов А. В. Структуры с замыканием и критерии функциональной полноты // УМН. 1961. - Т. 16, вып. 2(98). - С. 201-202.

10. Кузнецов А. В. О средствах для обнаружения невыводимости или невыразимости //В кн.: Логический вывод. М.: Наука, 1979. С. 533.

11. Кузнецов А. В. О проблемах тождества и функциональной полноты алгебраических систем. //В кн.: Труды Третьего Всесоюзного математического съезда. Т. 2 М.: Изд-во АН СССР, 1956. С. 145-146.

12. Мальцев А. И. Итеративные алгебры Поста Новосибирск: Изд-во СО АН СССР, 1976.

13. Марченков С. С. ^-классификация функций трехзначной логики -М.:Физматлит, 2001. 80 с.

14. Раца М. Ф. О классе функций трехзначной логики, соответствующем первой матрице Яськовского // Проблемы кибернетики. Вып. 21. М.: Наука, 1969. С. 185-214.

15. Раца М.Ф., Куку И. В. О полноте по неявной сводимости в логике первой матрице Яськовского // Известия АН МССР. Серия физико-технических и математических наук. 1988. - № 1.

16. Толстова Ю.Н. О моделировании /-значной логики в А:-значной (к > I) //Проблемы кибернетики. Вып. 18. М.: Наука, 1967. С. 67-82.

17. Яблонский С. В. Функциональные построения в &-значной логике // Сборник статей по математической логике и её приложениям к некоторым вопросам кибернетики. М.: Изд-во АН СССР. 1958. С 270-360.(Труды математического ин-та им. В.А.Стеклова; Т. LI.).

18. Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.

19. Яновская С. А. Математическая логика и основания математики // Математика в СССР за сорок лет. Т. I. М.: Физматлит, 1959. С. 13120.

20. Burris S., Willard R. Finitely many primitive positive clones // Proc. of the American Mathematical Society. 1987 — V. 101, № 3. — P. 427-430.

21. Geiger D. Closed systems of functions and predicates // Pacific Journal of Mathimatics, Vol. 27, ЛП, 1968, p. 95-100.

22. Martin N. M. The Sheffer functions of 3-valued logic // Journal of Syinb. Logic. 1954. V. 19, N 1. P. 45-51.

23. Post E. L. Introduction to a general theory of elementary propositions // Amer. J. Math. 1921. V. 43 p. 163-165.

24. Post E. L. The two-valued iterative systems of mathematical logic — Annales of Math. Studies. V. 5. - Princeton: Princeton Univ. Press, 1941.

25. Rosenberg I. G. Uber die funktionale Vollstandigkeit in den mehrwertigen Logiken // Rozpravy Ceskoslovenske Akademie Ved. Rada Mat. Prirod. Ved 80 (1970), S. 3-93.

26. Rousseau G. Completeness in finite algebras with a single operation // Proc. of the American Mathematical Society. 1967. V. 18. P. 1009-1013.

27. Slupecki J. Kriterium pelnosci wielowartosciowych systemow logiki zdan // Comptes Rendus des Seances de la Societe des Sciences et des Lettres de Varsovie. CI. III. 1939. 32. P. 102-128Список публикаций автора по теме диссертации

28. Орехова Е. А. Об одном критерии неявной полноты в Ахзначной логике // Математические вопросы кибернетики. Вып. 11. М.: Физматлит,2002. С. 77-90.

29. Орехова Е. А. О критерии неявной шефферовости в трехзначной логике // Дискретный анализ и исследование операций. Серия 1. 2003. -Т. 10, № 3. - С. 82-105.

30. Орехова Е. А. О полноте по неявной выразимости в многозначных логиках // Алгебра и теория моделей 4. Новосибирск: Изд-во НГТУ,2003. С. 81-88.