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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М. В. ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи УДК 519.7

Орехова Елена Андреевна

О КРИТЕРИЯХ ПОЛНОТЫ ПО НЕЯВНОЙ ВЫРАЗИМОСТИ В ТРЕХЗНАЧНОЙ ЛОГИКЕ

01.01.09—дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

МОСКВА - 2004

Работа выполнена на кафедре дискретной математики механико-математического факультета Московского государственного университета им. М. В. Ломоносова.

Научный руководитель — доктор физико-математических наук,

профессор О. М. Касим-Заде.

Официальные оппоненты доктор физико-математических наук,

профессор М. М. Глухов; кандидат физико-математических наук, профессор В. А. Стеценко.

Ведущая организация — Институт математики

им. С.Л.Соболева СО РАН.

Зашита диссертации состоится "16" апреля 2004 г. в 16 ч. 15 мин. на заседании диссертационного совета Д.501.001.84 в Московском государственном университете им. М. В Ломоносова по адресу 119992, ГСП-2, Москва, Ленинские горы, МГУ, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан "16" марта 2004 г.

Ученый секретарь диссертационного совета Д.501.001.84 в МГУ доктор физико-математических наук, профессор

В.Н.Чубариков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы.

Понятие неявной выразимости было введено в рассмотрение А. В. Кузнецовым1 наряду с другими обобщениями понятия выразимости функций /с-значной логики посредством суперпозиций (функциональной выразимости): неявной сводимостью и параметрической выразимостью..

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

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

' Лх(х1,..., жп,у1,..., ур, г) = #1(2:1,..., х„, 2/1,..., ур, г), А2(хи...,хп,уи...,ур,г) = В2{хи--.,хп,у1,...,ур,г),

ь 'Ля(®1. • • •. хп, Уи..., Ур, г) = Бт(11, ...,ХП,У1,...,УР, г).

где >4!,..., Лт, Ву,Вт — функции, явно выразимые над системой Е.

Указанная система уравнений называется параметрическим представлением функции /(хь..., хп), / € Рк, над системой функций Е, если она имеет хотя бы одно решение

ур = др(х 1,...,хп), г = д0(х1,...,х„),

где <^(х 1,...,хп) е Рк, г = 0,... ,р, — функции от основных переменных, причем для любого такого решения имеет место равенство <?о(хь..., хп) = }{х\,..., хп). Если параметры отсутствуют (т. е. р = 0), то говорят, что рассматриваемая система уравнений является неявным представлением функции /(хь..., х„) над Е.

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

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

НОС. НАЦИОНАЛЬНАЯ ] БИБЛИОТЕКА I

Я

С. Петербург

09 ЮО

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

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

Использование термина "неявное расширение" случае неявной выразимости обосновано тем, что отношение неявной выразимости в Рк при к > 3 не транзитивно. Если функция / неявно выразима над /(Е), т.е. принадлежит 1(1(12)), то из этого, вообще говоря, не следует, что функция / неявно выразима над Е. Более того, неявное расширение J(E) системы функций Е может не совпадать не только со своим неявным расширением J(/(E)), но и со своим явным замыканием £(/(Е)).

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

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

Функция/ называется вырашмой над системой функций Е по неявной сводимости, если найдется meNтакое, что f принадлежит Im(Е). Класс, состоящий из всех функций, выразимых над Е по неявной сводимости, называется ¡амыканием системы функмий Е по неявной сводимости и обозначается /°°(Е). Таким образом, /°°(Е) = (J /т(Е).

т=0

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

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

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

Проблема функциональной полноты в двузначной логике была

решена Э.Постом2. Им была описана структура всех замкнутых по суперпозиции классов в Р2 и показано, что число замкнутых классов в Р2 счетно, при этом всякий замкнутый класс имеет конечный базис. Критерий полноты в Р2 был независимо получен С. В. Яблонским3. Впоследствии им4 был получен критерий функциональной полноты в трехзначной логике Р3. Как и в Р2, в Р3 была найдена конечная система предпол-ных классов, из невхождения системы функций в которые следует ее полнота. Критерий функциональной полноты в терминах предполных классов в Р4 получил А. И Мальцев. А. В. Кузнецовым5 было доказано, что система всех предполных классов в Рк конечна при любом конечном к. Теорема Кузнецова дает алгоритм построения такой системы классов, хотя этот алгоритм даже при небольших значениях к связан с трудоемкими вычислениями и мало пригоден для практического использования. Нахождению всех предполных классов в Рк при произвольных конечных значениях к было посвящено немало работ, завершением которых стала работа И. Розенберга6. Описание предполных классов у И. Розенберга основано на введенном А. В. Кузнецовым понятии сохранения предиката.

Для многозначных логик Рк при к>3 одним из важнейших результатов, касающихся функциональной полноты, является критеий Слупец-кого7 функциональной полноты систем, содержащих все одноместные функции.

Еще одна задача, относящаяся к теории функциональной полноты, — это задача распознавания в Рк шефферовых функций. Шефферовой называется функция, которая одна составляет полную в Рк систему. Простейший критерий шефферовости был получен Н. М. Мартином8 на осно-

2Post В. L. Introduction to a general theory of elementary propositions // Amer. J.

Post Б. L. Two-valued iterative systems of mathematical logic - Ann. Math. Studies,

3Яновская С. А. Математическая логика и основания математики // Математика в СССР за сорок лет. T. I. М.: Физматлит, 1959. С. 13-120.

^Яблонский C.B. Функциональные построения в fc-значной логике // Тр. МИАН им. В. А. Стеклова. Т. LI. - M.: Изд-во АН СССР, 1958. С. 5-142.

5Кузнецов A.B. О проблемах тождества и функциональной полноты алгебраических систем. //В кн.: Труды 3-го Всесоюзного математического съезда. Т. 2 -

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

TSlupecki J. Kriterium pelnosci wielowartosciowych systemow logiki zdan // Comptes Rendus des Seances de la Société des Sciences et des Lettres de Varsovie, Cl. III, 1939,32,

'Martin N.M. The Sheffer functions of 3-valued logic // J. Symb. Logic. 1954. V. 19,

ве критерия Слупецкого. В дальнейшем были получены другие критерии шефферовости в Р2, Р3 и Рк при к > 3, основанные на результатах Э. Л. Поста, С. В. Яблонского и И. Розенберга. Критерий шефферо-вости в Рк в терминах минимальной системы предполных классов дан В. Б. Кудрявцевым9. Большое значение для целей данной работы имеет критерий Руссо10.

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

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

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

"Rousseau G. Completeness in finite algebras whith a single operation // Proc. Amer. Math Soc. 18 (1967), p. 1009-1013.

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

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

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

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

15Куку И. В., Раца M. Ф. Критерий параметрической полноты в логике простейшей псевдобулевой алгебры с несравнимыми элементами // Сборник трудов семинара по дискретной математике и ее приложениям / Под ред. О. Б. Лупанова. - М.: Изд-во механико-математического факультета МГУ, 1997. - С. 52.

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

Раца М. Ф., Куку И. В. О полноте по неявкой сводимости в логике первой матрице

Критериев полноты по неявной выразимости в трехзначной логике Рз и в Р* при А; > 3 до настоящего времени известно не было.

Цель работы.

Основная цель диссертации — получение критериев неявной полноты и неявной шефферовости в трехзначной логике Р3.

Основные методы исследования.

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

Научная новизна.

Все основные результаты диссертации являются новыми. В диссертации получены следующие основные результаты.

1. Найден критерий неявной полноты в к-значной логике при к >2, являющийся в некотором смысле аналогичным критерию Слупецкого. Как и критерий Слупецкого, его удалось усилить за счет сокращения количества необходимых одноместных функций.

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

3. Получен критерий неявной полноты в трехзначной логике: найдена система всех минимальных неявно полных явно замкнутых классов. Показано, что таких классов всего 27, все они конечнопорожденные, и для каждого класса построена порождающая его система. Таким образом, установлено, что класс функций неявно полон в Рз тогда и только тогда, когда над ним явно выразима одна из описанных в работе 27 конечных систем функций.

4. Как следствие из критерия неявной полноты в Рз доказано, что число неявно предполных в Рз классов конечно, и система всех неявно предполных в Рз классов является критериальной по неявной полноте, т. е. всякий класс неявно полон в Рз тогда и только тогда, когда он не содержится ни в одном неявно предполном классе.

Яськовского // Известия АН МССР. Серия физико-технических и математических

5. Показано, что проблема неявной полноты конечных систем функций в Рз алгоритмически разрешима.

Теоретическая и практическая ценность.

Работа носит теоретический характер. Ее результаты могут быть использованы при дальнейших исследованиях по проблемам выразимости в многозначных логиках. Результаты работы могут быть полезна специалистам Московского государственного университета им. М. В. Ломоносова, Института прикладной математики им. М. В. Келдыша РАН, Вычислительного центра им. А.А.Дородницына РАН, Института математики им. С. Л. Соболева СО РАН, Нижегородского государственного университета им. М. В. Лобачевского, Новосибирского государственного университета, Санкт-Петербургского государственного университета.

Апробация результатов.

Результаты диссертации докладывались на XI Международной школе-семинаре «Синтез и сложность управляющих систем» (Нижний Новгород, 2000 г.), в МГУ им. М.В. Ломоносова на спец. семинаре «Модели и методы дискретной математики» под руководством д.ф.м.н., профессора. О.М.Касим-Заде (2001 и 2002 г.г.) и на научно-исследовательских семинарах «Синтез управляющих систем» (2002 и 2003 г.г.) и «Математические вопросы кибернетики» (2003 г.) под руководством академика РАН, профессора О.Б.Лупанова , на V международной конференции «Пограничные вопросы теории моделей и универсальной алгебры» (Новосибирск, 2003 г.), на семинаре ИМ СО РАН и НГУ «Дискретный анализ» под руководством проф. А. А. Евдокимова и проф. А. Д. Коршунова (Новосибирск, 2003 г.), на XV! Международной школе-семинаре «Синтез и сложность управляющих систем» (Нижний Новгород, 2003 г.), 28 Ав-стралазийской конференции по комбинаторной математике и комбинаторным вычислениям (The 28th Australasian Conference on Combinatorial Mathematics and Combinatorial Computing) (Мельбурн, Австралия, 2003 г.).

Публикации.

Основные результаты диссертации опубликованы в пяти работах, список которых приведен в конце автореферата.

Структура и объем диссертации.

Диссертация состоит из введения и трех глав, разбитых на параграфы. Общий объем диссертации составляет НО страниц. Список литературы включает 28 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Введение.

Во введении дан краткий исторический обзор проблемы, приведены основные определения и известные результаты, перечислены основные результаты диссертации.

Глава 1.

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

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

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

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

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

В диссертации установлено, что относительно неявной выразимости аналогичными свойствами обладает минимальный явно замкнутый над-класс класса всех одноместных функций Р^ — класс квазилинейных функций18. Функция называется квазилинейной, если она имеет вид:

/(х 1,... ,х„) = <?(/i(xi) © • • • ф /„(х„)),

где <7,/i,-..,/n — одноместные функции, афоозначает сложение по модулю к.

,eSlupecki J. Kriterium pelnosci wielowartosciowych systemow logiki zdan // Comptes Rendus des Seances de la Société des Sciences et des Lettres de Varsovie, Cl. III, 1939,32, p. 102-128.

17Яблонский С. В. Функциональные построения в fc-значной логике // Тр. МИАН им. В. А.Стеклова. - Т. LI. - M.: Изд-во АН СССР, 1958. С. 5-142.

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

Глава 1 состоит из двух разделов.

В разделе 1.1 сформулирован и доказан критерий неявной полноты систем функций в Р*, к ^ 2, содержащих все одноместные функции.

Теорема19 1. Пусть система функций из Рк, содержит все

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

Как и критерий Слупецкого, эту теорему можно усилить. В разделе 1.1 доказаны две теоремы, усиливающие этот критерий.

Теорема 3. Пусть система функций из Рк, к ^ 1, содержит все одноместные функции, принимающие не более двух значений. Тогда для неявной полноты этой системы необходимо и достаточно, чтобы она содержала также хотя бы одну неквазилинейную функцию.

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

В разделе 1.2 рассмотрено важное следствие критерия неявной полноты. Показано, что в Рк при к ^ 4 класс одноместных функций полон по неявной сводимости (для к = 4 этот результат установлен О. М. Касим-Заде). Показано также, что при к = 3 неявное расширение класса 9Тз совпадает с ним самим, а поэтому в Р3 класс одноместных функций не полон по неявной сводимости. При этом, из результатов А. Ф. Данильченко20 следует, что класс Р^ одноместных функций параметрически полон в Рк при к > 3.

Система всех одноместных функций не полна в Р2 ни функционально, ни параметрически, ни — как следствие — неявно и по неявной сводимости.

Указанные результаты иллюстрирует таблица 1. В графе таблицы стоит знак «+», если класс Р^ полон в Рк по соответствующему строке таблицы типу выразимости, и знак в противном случае.

"Нумерация теорем в автореферате соответствует их нумерации в диссертации.

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

Таблица 1

Тип выразимости Р2 Рз Рк,к> 4

Явная выразимость Неявная выразимость Неявная сводимость Параметрическая выразимость - - + - + +

Глава 2.

Во второй главе решается проблема неявной шефферовости в Р3.

Аналогично понятию шефферовой функции, для неявной выразимости естественным образом возникает понятие неявно шефферовой функции.

Функция /(11,..., х„) е Рк, где к > 2, такая, что /({/}) = Р*, называется неявно шефферовой.

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

Функции А-значной логики }{х\,...,х„) и д(х1г.. .,х3) называются перестановочными, если для любых значений переменных ху е (г = 1,2,..., п; з = 1,2,..., в) выполняется соотношение

9(/(®11.....^па), /(^12.....хп2),..., /(хи> ■ • •, хп,)) —

/(д(х ......^1»), д(х2и..., х2,),. • •, д(х„ ь..., х„,)).

Функция д{х 1,...,х„) е Рк называется двойственной функции /(хь ..., х„) е Рк относительно некоторой подстановки <т на ¿-элементном множестве Ек = {0,1,..., к — 1}, если для любых значений переменных XI,... ,хп выполняется соотношение

......2п)) = 5(^(2:1), ••.,

Функция /, двойственная самой себе относительно подстановки а, называется самодвойственной относительно этой подстановки.

Под самодвойственной21 в Р3 функцией в работе понимается функция, самодвойственная относительно циклической подстановки (012) на множестве Е3 — {0,1,2}.

г1см. Яблонский С. В. Функциональные построения в ¿-значной логике // Тр. МИ-АН им. В. А. Стеклова. - Т. 1Л. - М.: Иэд-во АН СССР, 1958. - С. 5-142.

Функция трехзначной логики Р3 сохраняет двухэлементное подмножество72 {а,Ь}, где а и 6 различные элементы из Е3 если на любых наборах, состоящих из элементов а, 6, она принимает значения а или Ь.

Для всякого нетривиального разбиения {а, Ь}, {с} множества Ез, Ез = {о,Ь}и{с}, введем на множестве наборов Щ следующее отношение эквивалентности22. Наборы а и /3 называются эквивалентными относительно разбиения {о,Ь},{с}, если компоненты набофи/8с одинаковыми номерами либо обе равны с, либо обе принадлежат множеству {о, Ь}. Класс эквивалентности относительно разбиения {а,Ь},{с} называется блоком эквивалентных наборов или просто блоком. Все наборы одного блока содержат в некоторых п — 5 фиксированных разрядах значение с, а в остальных з разрядах — значения а, 6, образующие все возможные поднаборы га).

Функция трехзначной логики Рз сохраняет разбиение {а, Ь}, {с}, если на любых наборах, эквивалентных относительно этого разбиениях, она принимает эквивалентные значения .

Произвольной функции /(х), сохраняющей двухэлементное подмножество {а, 6}, на этом подмножестве можно естественным образом поставить с соответствие некоторую булеву функцию с помощью отображения а —► 0, Ь —► 1. Назовем эту функцию {0,1}-образом функции /(х).

Пусть А — замкнутый по суперпозиции класс булевых функций. Обозначим через Ед"'^ класс всех функций трехзначной логики сохраняющих подмножество {а,Ь}, {0,1}-образы которых принадлежат классу А. Класс замкнут по суперпозиции.

При рассмотрении функций трехзначной логики, сохраняющих нетривиальное разбиение, также можно установить связь этих функций с функциями из Каждому блоку наборов можно сопоставить либо константу с, либо некоторую булеву функцию с помощью отображения а —► 0,Ь —► 1, которую будем называть булевым ограничением функции / на этом блоке.

Пусть А — замкнутый по суперпозиции класс булевых функций. Обозначим через класс всех функций трехзначной логики, сохраняющих разбиение {а, Ь}, {с}, у которых все булевы ограничения на блоках принадлежат классу А. Класс Е^&Ы«} замкНуХ по суперпозиции.

Обозначим24 через Т^Т^ и классы функций в Рз, сохраняющих

32см. Яблонский С. В. Функциональные построения в &-значной логике // Тр. МИ-АН им. В. А. Стеклопа. - Т. Ц. - М.: Иэд-во АН СССР, 1958. - С. 5-142.

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

!4эти обозначения соответствуют принятым в:

константы 0,1 и 2 соответственно, и через S3 класс функций, самодвойственных относительно циклической подстановки (012).

Обозначим через То и T1 классы булевых функций, сохраняющие константы 0 и 1 соответственно, через S — класс самодвойственных функций, через L — класс линейных функций, через К — класс функций, состоящий из всех конъюнкций переменных и констант, а через D — класс функций, состоящий из всех дизъюнкций переменных и констант. Классы То, T1, 5, L, К и D можно также определять как классы всех функций, перестановочных соответственно с константой 0, с константой 1, с функцией отрицания х, с линейной функцией х\ ф х% ф хз (mod 2), с конъюнкцией двух переменных ii & хг и с дизъюнкцией двух переменных

В диссертации установлен следующий критерий неявной шефферо-вости в трехзначной логике.

Теорема 8 Функция f является неявно шефферовой в P¡ тогда и только тогда, когда она не принадлежит ни одному из следующих 22

*•unrrn«• ТЗ 7* ТЗ <?3 Г{0.1) Г{0,2} у{1,2} у{0,1},{2} „{0,1}, {2} г{0,2},{1} классов, ¿q, j.1, ±2, «э , ¿jS , ¿jS , ¿jS , ¿JTg , ¿jT¡ , ¿jjl ,

Г{0,2>,{1} V{1.2},{0} V{1,2},{0} v{0.1>,{2} г{0,2},{1} r(l,2},{0} -{0,1},{2} у,{0,2),{1} y{1.2},{0} yi{0,l},{2} V{0,2}.{1} -{1,2},{0}

^K > D >^D > D

Двухэлементное подмножество множества Е3 = {0,1,2} будем называть чужим для разбиения, если элементы рассматриваемого подмножества не эквивалентны относительно этого разбиения. Соответственно, разбиения, относительно которых элементы этого подмножества не эк-Бивалентны, будем называть чужими для него.

Функции из класса £Íe'b* будем называть {а, Ъ}-самодвойственными, функции из класса — блочно-линейными относительно разбие-

ния {а, Ь}, {с}, функции из класса üj^'M -блочно-перестановочными с конъюнкцией относительно разбиения {о, Ь}, {с}, функции из класса ^К'ЬМ — блочно-перестановочными с дизъюнкцией относительно разбиения {о, 6}, {с}.

В диссертации получена следующая эквивалентная формулировка критерия шефферовости в

Теорема 9. Функция f является неявно шефферовой в Рз тогда и только тогда, когда она не сохраняет констант, иудовлетворяет одному из условий:

Яблонский С. В. Функциональные построения в k-значной логике // Тр. МИАН им. В. А. Стеклова. - Т. LI. - М.: Изд-во АН СССР, 1958. - С. 5-142.

1. f не сохраняет двухэлементных подмножеств, нетривиальных разбиений и неявляется самодвойственной;

2./сохраняет некоторое двухэлементное подмножество {а,Ь}, не сохраняет чужих ему нетривиальных разбиений и не является {а, Ь}-самодвойственной;

3. / не сохраняет двухэлементных подмножеств, сохраняет неко-

торое нетривиальное разбиение {а, Ь}, {с} и относительно это-горазбиения неявляется блочно-линейной, блочно-самодвойственной, блочно-перестановочной с конъюнкцией или блочно-переста-новочной с дизъюнкцией.

Глава 2 состоит из трех разделов.

В разделе 2.1 даются необходимые определения и формулируются известные результаты, использующиеся при доказательстве критерия.

Во разделе 2.2 формулируются и доказываются необходимые условия неявной шефферовости.

В разделе 2.3 формулируются и доказываются два приведенных выше эквивалентных критерия неявной шефферовости в Рз.

Глава 3.

Распространенным подходом к решению задач о полноте в функциональных системах является описание соответствующей системы всех предполных классов. Как было отмечено выше, отношение неявной выразимости в Рк при к>3 не транзитивно. Поэтому в диссертации при поиске критерия неявной полноты в Р3 был выбран другой подход: вместо неявно предполных, т. е. максимальных по включению неявно неполных систем, искать минимальные неявно полные системы. Поскольку неявное расширение класса совпадает с неявным расширением его явного замыкания, рассмотрение произвольных систем функций можно свести к рассмотрению явно замкнутых классов. Установлено следующее. В Рз существует 27 конечных неявно полных систем функций, порождающих 27 различных явно замкнутых классов, каждый из которых неявно полон и не содержит другого явно замкнутого и неявно полного класса. При этом всякий неявно полный явно замкнутый класс содержит один из указанных 27 классов. Все 27 систем функций, порождающих эти классы, перечислены в таблице 2. Таким образом, в диссертации установлен следующий критерий неявной полноты в Рз.

Теорема 22. Система функций ]¥неявно полна в Р3 тогда и только тогда, когда над Ц^явновыразимахотябыоднаиз 27 системфункций, приведенных втаблице 2.

В таблице 2, как и всюду в диссертации, для задания функций используются таблицы значений. Одноместная функция /(х) задается таблицей размера 3 х 1, в которой строка г содержит значение /(¿), двуместная функция /(х, у) — таблицей размера 3 х 3, в которой на пересечении строки 1 и столбца / содержится значение /(г, Например, одномест-

1

ная функция /(х) = х +1 задается таблицей, а двуместная функция

О

Для сокращения выкладок при доказательстве теоремы 22 в диссертации применен принцип двойственности. С точностью до двойственности, для установления критерия неявной полноты в Р3 необходимо всего 6, а не 27 конечных систем функций.

Система всех функций, двойственных функциям некоторой системы V/ относительно фиксированной подстановки с, называется двойственной системе IV относительно этой подстановки.

С точностью до двойственности, установленный в диссертации критерий неявной полноты в Р3 формулируется в следующем виде.

Теорема 21. Система функций Жнеявно полна вР3 тогда и только тогда, когда над ней явно выразима хотя бы одна из систем функций:

0 1 1 0 0 0 1

1 1 1 , 0 1 0

1 1 1 0 0 0 /

0 0 0 0 1 1 0 1

0 1 1 , 1 1 1 , 0 ,0,1 >;

0 1 1 1 1 1 1 1

0 0 2 0 1 2 1 1

0 1 2 , 1 1 2 , 1 Д1 ;

2 2 2 2 2 2 0 /

0 0 2 0 1 2 ООО

0 1 2 , 1 1 2 , 0 0 2 ,С

2 2 2 2 2 2 0 0 2

0 0 2 0 1 2 2 1

0 1 2 , 1 1 2 . 2 ,0,1,2 >

2 2 2 2 2 2 0 1

{ 0 0 2 0 1 2 2 0 1 2,1 1 2,2 112 112 0

или система, двойственная одной изних.

Из критерия неявной полноты в Рз вытекает несколько следствий.

Теорема 23. Всякая неявно полная в Рз система содержит конечную неявно полную подсистему.

Теорема 24. Проблема распознавания неявной полноты конечных систем функций в Рз алгоритмическиразрешима.

Теорема 25. Число неявно предполных классов в Рз конечно. Всякая система функций трехзначной логики неявно полна в Рз тогда и только тогда, когда она целиком не содержится ни в одном из неявно предполныхклассов.

Глава 3 состоит из четырех разделов.

Для нахождения всех минимальных неявно полных явно замкнутых классов в Рз по отдельности рассматриваются явно замкнутые классы, содержащие ни одной, одну, две или все три константы и входящие в различные явно предполные классы.

В разделе 3.1 установлен критерий-неявной полноты в трехзначной логике для явно замкнутых классов, не содержащих констант.

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

В разделе 3.3 рассмотрен случай, когда исследуемый явно замкнутый класс содержит две константы.

В разделе 3.4 рассмотрен последний случай, когда исследуемый явно замкнутый класс содержит все три константы, и установлен критерий неявной полноты в Рз.

Автор выражает глубокую благодарность своему научному руководителю, профессору Октаю Мурадовичу Касим-Заде, за постановку задачи, многочисленные обсуждения, постоянную поддержку и внимание к работе.

ООО 011 0 1 0,1 1 1 ,0,1 ООО 111 ООО 022 0 0 0 , 2 2 2 ,0,2 0 0 2 2 2 2

111 2 2 2 1 1 1,2 1 2 , 1,2 1 1 2 2 2 2 ООО 011 0 0 1 1,1 1 1,0,1 0 11 111 1

ООО 0 2 2 0 0 2 2,2 2 2, 2,2 0 2 2 2 2 2 0 112 111 1 1 1 2,1 1 1,2,1 2 2 2 1 1 2 2

0 10 ООО 1 1 1 1,0 1 0 , 1 ,0 0 10 ООО 0 0 0 2 ООО 2 0 0 2,0 0 0,0,0 2 2 2 0 0 2 2

2 1 2 2 2 2 2 1 1 1,2 1 2,1,2 2 1 2 2 2 2 1 0 0 2 0 1 2 1 0 1 2,1 1 2,1,0 2 2 2 2 2 2 0

0 10 0 12 2 1 1 1,1 1 1,0,0 0 12 2 12 2 ООО ООО 2 0 1 2-, 0 1 1,1,2 0 2 2 0 1 2 1

0 0 2 0 1 2 0 0 1 2,1 1 2,0,1 2 2 2 2 2 2 1 0 10 0 12 0 1 1 1,1 1 1,2,2 0 12 2 12 0

ООО ООО 1 0 1 2,0 1 1,2,1 0 2 2 0 1 2 2 002 012 ООО 0 1 2,1 1 2,0 0 2,1 222 222 002

0 10 0 12 ООО 1 1 1,1 1 1,0 1 0,2 012 212 010 ООО ООО 022 0 1 2,0 1 1,0 2 2,1 022 012 222

0 0 2 0 1 2 1 1 2 0 1 2,1 I 2,1 1 1,0 222 222 112 010 012 212 1 1 1,1 1 1,2 1 2,0 012 212 222

ООО ООО 011 0 1 2,0 1 1,1 1 1,2 0 2 2 0 1 2 0 1 1 0 0 2 0 1 2 2 0 1 2,1 1 2, 2,0,1 2 2 2 2 2 2 0

0 10 0 12 1 1 1 1,1 1 1 , 0 ,0,2 0 12 2 12 1 ООО ООО 2 0 1 2,0 1 1 , 0 ,1,2 0 2 2 0 1 2 0

0 1 2 0 0 2 2 1 1 2,0 1 2,2 112 112 0 0 10 0 12 1 2 1 2,2 1 2,0 0 12 2 12 1

0 11 0 11 2 0 1 2,0 1 1,0 0 2 2 0 1 2 0

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. Орехова Е.А. О соотношении неявной и параметрической полноты в трехзначной логике // Материалы XI Международной школы-семинара «Синтез и сложность управляющих систем» (Нижний Новгород, 20-25 ноября 2000 г.) - М: Изд-во центра прикладных исследований при механико-натематическом факультете МГУ, 2001. С. 135.

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

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

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

5. Орехова Е. А. О критерии полноты по неявной выразимости в трехзначной логике // Материалы XIV Международной школы-семинара «Синтез и сложность управляющих систем» (Нижний Новгород, 27 октября - 1 ноября 2003 г.) - М: Изд-во центра прикладных исследований при механико-натематическом факультете МГУ, 2003. С. 123-127.

Издательство ЦПИ при механико-математическом факультете МГУ им. М.В. Ломоносова. Подписано в печать оз.гооЬх.

Формат 60x90 1/16. Усл. печ. л.

Тираж 100 экз. Заказ

Лицензия на издательскую деятельность ИД В 04059,

от 20.02.2001г.

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета и Франко-русского центра им. Л.М. Ляпунова.

» -5352

Введение

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,/ь .,/п — одноместные функции, а ® обозначает сложение по модулю к.

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.