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

• Стартостин Михаил Васильевич
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Стартостин Михаил Васильевич

2.2.1 Классы типа Ш

2.2.2 Классы типа У

2.3 Классы типа Е

2.3.1 Классы функций, сохраняющих подмножество

2.3.2 Классы функций, сохраняющих разбиение

2.4 Классы монотонных функций

2.4.1 Классы типа КМ

2.4.2 Классы типа И,

2.4.3 Классы типа Q

2.4.4 Классы типа Г

2.5 Класс квазилинейных функций

3 Полнота описания

3.1 Классы без констант

3.2 Классы с одной константой

3.3 Классы с двумя константами

3.4 Классы с тремя константами

3.4.1 Классы типа и

3.4.2 Классы типа М

3.4.3 Классы типа Т1

3.4.4 Класс Ь

3.4.5 Класс Слупецкого

3.5 Основные результаты

Заключение

Список литературы

Введение

Введение диссертации (часть автореферата) на тему «Критериальная система неявно предполных классов в трехзначной логике»

Актуальность темы

Диссертационная работа относится к одному из центральных разделов дискретной математики и математической кибернетики — теории функциональных систем. Важное место в теории функциональных систем занимают задачи выразимости и полноты.

Проясним постановку этих задач на примере операции суперпозиции на множестве функций к-значной логики. Определение операции суперпозиции приведено в первой главе.

Множество {0,1,..., к — 1} будем обозначать через Ек. Функцией к-значной логики от п переменных называется произвольное отображение f: Е^ ^ Ек вместе с упорядоченным набором переменных. Множество всех функций к-значной логики обозначается через Рк. Булевой функцией называется функция двузначной логики.

Система1 функций £ С Рк называется полной по суперпозиции (или функционально полной), если суперпозициями над £ можно получить произвольную функцию к-значной логики.

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

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

Важным объектом, связанным с вопросами выразимости, является множество всех функций, выразимых над заданной системой £. В случае операции суперпозиции это множество называется замыканием £ по суперпозиции (или функциональным замыканием £) и обозначается через [£]. Оператор, сопоставляющий произвольной системе £ С Рк ее замыкание по суперпозиции, является оператором замыкания в общем смысле, а именно, обладает следующими свойствами [17]:

1. £ С [£] (экстенсивность),

2. £ С П ^ [£] С [П] (изотонность),

хСлова «система», «множество» и «класс» в работе считаются синонимами, но используются в разных контекстах.

3. [Е] = [[Е]] (идемпотентность).

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

Ряд основополагающих результатов, относящихся к проблемам выразимости и полноты по суперпозиции в P2 был получен Э. Постом [57,58]. В частности, он построил решетку всех замкнутых по суперпозиции классов в P2, указал для каждого из них конечный базис и показал, что число замкнутых по суперпозиции классов в P2 счетно. Кроме того, он получил критерий полноты, который, используя современную терминологию, можно сформулировать следующим образом: система булевых функций полна по суперпозиции тогда и только тогда, когда она не содержится целиком ни в одном из пяти предпол-ных классов функций: T0 (класс функций, сохраняющих константу 0), T (класс функций, сохраняющих константу 1), S (класс самодвойственных функций), M (класс монотонных функций), L (класс линейных функций) — здесь и далее обозначения замкнутых по суперпозиции классов в P2 даны по [42]. Определения этих классов приводятся в первой главе диссертации. Эти классы являются максимальными по включению неполными по суперпозиции классами. Понятие предполного по суперпозиции класса ввел А.В. Кузнецов [48]. В дальнейшем понятие предполного класса распространилось и на другие виды выразимости.

В общем случае класс функций A С Pk называется предполным в классе функций B С Pk, если A не является полным в B, но становится таким при добавлении к A любой функции из множества B \ A. Предполный в Pk класс обычно называют предполным без каких-либо уточнений. Понятие пред-полного класса оказалось удобным и продуктивным при исследовании задач выразимости и, в частности, проблем полноты. Значительная часть диссертации посвящена описанию предполных классов для исследуемого в работе вида выразимости (неявная выразимость).

После работы Э. Поста была выдвинута гипотеза, состоящая в том, что решетка замкнутых классов в полной k-значной логике Pk при k > 3 устроена во многом аналогично решетке в P2. В частности, предполагалось, что каждый замкнутый класс в Pk имеет конечный базис, и решетка замкнутых классов в Pk счетна. Однако результаты Ю.И. Янова и А.А. Мучника [47] о существовании в Pk как классов, не имеющих базиса, так и классов, имеющих счетный базис, заставили отказаться от этого предположения. Одним из важнейших следствий последнего из упомянутых результатов стало доказательство того факта, что при k > 3 мощность множества всех замкнутых классов в Pk равна мощности континуума [47].

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

доказал (см. [44]), что при любом значении k в Pk имеется конечное число пред-полных по суперпозиции классов, и предложил конструкцию, позволяющую в некотором смысле "эффективно" (за конечное число шагов) строить все такие классы (впрочем, достижение этой цели уже при небольших значениях k требует слишком больших вычислений, чтобы применять такую конструкцию на практике).

Все предполные по суперпозиции классы функций трехзначной логики были найдены С.В. Яблонским [44]. Таких классов оказалось 18, их определения приводятся в первой главе диссертации. В P4 все предполные по суперпозиции классы описаны А. И. Мальцевым [21]. Кроме того, Яблонский указал несколько семейств предполных классов при произвольных значениях k [44]. Важные результаты в этом направлении были получены А.В. Кузнецовым [48].

Также проблемами описания предполных по суперпозиции классов функций конечнозначных логик Pk занимались Р.А. Байрамов, Е.Ю. Захарова, В.Б. Кудрявцев, Д. Лау, Ло Чжу-Кай, В.В. Мартынюк, Пан Юн-Цзе, И. Розенберг, Г. Тардош и другие — см., в частности, [3,10,11,20,23,34,55,59,64]. Окончательное решение задачи описания всех предполных по суперпозиции классов получил И. Розенберг [59]. Он показал, что система функций является предполной по суперпозиции в Pk тогда и только тогда, когда она совпадает с одним из классов из следующих шести семейств: M, S, U, L, C, B — обозначения даны по [55].

Результат Розенберга касается описания "верхнего уровня" решетки замкнутых по суперпозиции классов в Pk при k > 3. Изучению других частей этой решетки посвящены работы [7,27,30,38,43,49,50,62] и другие. Отдельно выделим работы, в которых рассматривается трехзначная логика: [9,26,28,53,54].

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

Отметим, что многие вопросы теории функциональных систем можно формулировать на языке универсальной алгебры. Использование алгебраического подхода для решения таких вопросов можно найти, например, в работах [2,35, 51,55,63].

Кроме выразимости по суперпозиции в теории функциональных систем рассматриваются различные другие виды выразимости. В частности, интерес представляет изучение видов выразимости, обобщающих выразимость по суперпозиции. Отметим в этом плане понятие слабой выразимости по суперпозиции [48]. При рассмотрении задачи слабой выразимости к функциям системы добавляются все константы. Также изучению различных обобщений выразимости по суперпозиции посвящены работы [1,18,19,24,25,29,36,40] и другие.

А. В. Кузнецов, в частности, предложил рассматривать понятия параметрической и неявной выразимости [19].

Следуя работе [15], дадим ряд определений. Пусть £ — система функций k-

значной логики. Через Е(Е) обозначим явное замыкание Е — систему [Е и {х}] [19]. Рассмотрим систему уравнений

(Л (хь... ,ж„,у1,... ,ур,г) = £1(2:1,... ,жга,уь ... ,ур,г), А2(х1,... ,хп,у1,... ,Ур,г) = £2(21,... ,хп,у1,... ,Ур,г),

Ат (Х1, . . . ,ХП,У1, . . . ,Ур,г) = Вт(Х1, ... ,ХП,У1, ... ,Ур,г),

где А1,... , Ат, В1,... , £т — функции из Е(Е). Переменные х1,... , хп будем называть основными переменными, переменные у1,... ,ур — параметрами, а г — выделенной переменной. Говорят, что данная система является параметрическим представлением функции /(х1,..., хп) € Рк, если она имеет хотя бы одно решение вида

У1 = #1(21,... ,Хп),

Ур 9р(х 1,..., хп), г = #о(х1,... ,хп), причем для каждого решения такого вида выполнено равенство

#о(х1, . . . ,хп) = /(хь . . . ,хп).

Функция называется параметрически выразимой над системой функций Е, если для нее существует параметрическое представление над Е. Если для функции /(х1,... ,хп) существует параметрическое представление над Е, в котором р =0 (то есть параметры отсутствуют), то соответствующая система уравнений называется неявным представлением функции /, а функция / называется неявно выразимой над системой функций Е. Подробнее об этом см. [15].

В качестве примеров рассмотрим два неявных (а следовательно и параметрических) представления в Р2. Система

Г х&г = 0, \ х V г =1.

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

х ^ (у ^ г) = х ^ х, г ^ "х "х ^ ^х, г ^ у = х ^ х.

эквивалентна уравнению г = х&у. Таким образом, в двузначной логике конъюнкция неявно выразима через импликацию.

Следуя [13], будем обозначать через P(S) параметрическое замыкание системы S — множество всех функций,

параметрически выразимых над S, а через через I(S) неявное расширение системы S — множество всех функций, неявно выразимых над S. Система функций S называется параметрически (неявно ) замкнутой, если P (S) = S (соответственно I(S) = S). Оператором параметрического замыкания (оператором неявного расширения) будем называть отображение, которое каждому множеству функций k-значной логики сопоставляет его параметрическое замыкание (неявное расширение).

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

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

S Ç [S] Ç E(S) Ç I (S) Ç P (S).

Кроме того, I (S) = I ([S]) и P (S) = P ([S]), что позволяет без ограничения общности рассматривать неявное расширение и параметрическое замыкание только замкнутых по суперпозиции классов.

Функции k-значной логики f (xi,..., Xn) и g(xi,..., Xs) называются перестановочными, если для любых значений переменных Xj G Ek (i = 1, 2, ...,n; j = 1, 2,... , s) выполняется соотношение

g(f (xii, . . . ,Xni),f(Xi2, . . . ,Xn2), . . . ,f (Xi s , . . . , Xns))

= f (g(Xii, . . . , Xis), g(X2i, . . . , X2s), . . . , g(X ni , . . . , Xns)) .

Множество всех функций, перестановочных с каждой функцией системы S, называется централизатором системы S (см. [8,17,19]) и обозначается через (S). А.В. Кузнецов доказал [19], что при всяком натуральном k > 2 параметрическое замыкание любой системы S функций k-значной логики совпадает с ее бицентрализатором, т.е. P (S) = ((S)).

Кроме того, он перечислил все параметрически замкнутые классы в P2, которых оказалось 25. Это классы

P2, То, Ti, Toi, S, Soi, SL, L, Lo, Li, Loi, K,Ko,Ki,Koi,D,Do,Di,Doi,U,MU,SU,Uo,Ui,Uoi.

Из этого списка нетрудно выделить список параметрически предполных (максимальных по включению параметрически неполных) классов. Такими являются классы T0,Ti, S, L,K,D (см. [14]).

Также А. В. Кузнецов [19] сформулировал ряд проблем, относящихся к параметрической и неявной выразимостям. В частности, Кузнецова интересовал

вопрос о конечности числа параметрически замкнутых классов в Рк при произвольном к > 2. В Р3 конечность числа параметрически замкнутых классов доказана его ученицей А. Ф. Данильченко [8]. В общем случае (для всех к > 2) задача решена положительно С. Баррисом и Р. Уиллардом [52].

Все параметрически предполные классы в Р3 были найдены Данильченко [8]. Описание параметрически предполных классов в Рк при к > 4 на данный момент, по-видимому, отсутствует.

Понятие неявной выразимости существенно отличается по своим свойствам от понятия параметрической выразимости в Рк при к > 3. В частности, оператор параметрического замыкания является оператором замыкания в обычном смысле (то есть является экстенсивным, монотонным и идемпотентным, см. [17, 19]). Напротив, в общем случае оператор неявного расширения не является оператором замыкания, так как не обладает свойством идемпотентности (при произвольном к > 3 в Рк существуют такие системы функций Е, что I(I(Е)) = I(Е) [19]). Первый пример системы, параметрическое замыкание которой отлично от ее неявного расширения, был построен Данильченко в Р3 (см. [19]). Кроме того, О. М. Касим-Заде показал, что мощность множества всех неявных расширений систем функций в Рк при к > 3 совпадает с мощностью континуума.

Он же решил еще одну проблему, поставленную Кузнецовым в [19]. А именно доказал, что в Р2 неявное расширение любой системы функций совпадает с ее параметрическим замыканием [12]. В частности, это означает, что в Р2 имеется ровно 6 неявно предполных классов: Т0,7\, 5", Ь, К, Д. Тем самым был установлен критерий неявной полноты в Р2 в терминах неявно предполных классов.

Кроме того, Касим-Заде был предложен критерий неявной полноты в Р2 иного рода (см. [14]): система функций неявно полна тогда и только тогда, когда ее явное замыкание целиком содержит класс монотонных функций М. Класс М является единственным минимальным по включению замкнутым по суперпозиции неявно полным классом в Р2. В Р3 аналогичный критерий неявной полноты получила Е. А. Орехова [33]. Она описала все минимальные неявно полные замкнутые по суперпозиции классы в Р3, которых оказалось 27.

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

Позднее Касим-Заде доказал критерий неявной полноты в Рк при произвольном к > 2, позволяющий устанавливать неявную полноту системы функций по множеству функций от трех переменных, лежащих в замыкании этой систе-

мы по суперпозиции. Одним из следствий этого критерия стало то, что любая неполная система функций в Рк расширяется до некоторого неявно предполного класса и число таких классов в Рк конечно при любом к > 2 [16].

Из соотношений между выразимостью по суперпозиции, неявной выразимостью и параметрической выразимостью следует, что любой неявно предполный класс содержится в некотором предполном по суперпозиции классе. А любой параметрически предполный класс содержится в некотором неявно предпол-ном. Таким образом, если некоторый класс предполон как по суперпозиции, так и по параметрической выразимости, то он автоматически оказывается неявно предполным. Такими являются некоторые классы функций трехзначной логики, найденные Данильченко [8].

Кроме того, неявно предполными являются все классы из критерия неявной шефферовости [32]. Помимо этого, в работах Ореховой можно найти еще два неявно предполных класса в Р3. Один из них (класс Я'2) — в уже упомянутой работе [33], другой — класс квазилинейных функций n [7] — в работе [31], где доказано, что он является неявно предполным при любом значении к > 3.

Цели работы

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

Объект и предмет исследования

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

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

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

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

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

1. Впервые получен критерий неявной полноты в терминах неявно предпол-ных классов.

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

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

4. Доказан критерий слабой неявной полноты.

Основные положения, выносимые на защиту

На защиту выносятся: обоснование актуальности, научная значимость работы, а также следующие положения.

1. Доказана полнота описания неявно предполных классов в Р3. Тем самым установлен критерий неявной полноты в трехзначной логике в терминах неявно предполных классов.

2. Доказана неявная предполнота нескольких семейств классов функций в Р3.

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

4. Установлен критерий слабой неявной полноты в Р3.

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

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

Апробация работы

Результаты диссертации докладывались на следующих семинарах и всероссийских и международных конференциях:

1. XII Международный научный семинар «Дискретная математика и ее приложения» имени академика О. Б. Лупанова, МГУ, Россия, 20-25 июня 2016 г.

2. XIII Международная научная конференция студентов, магистрантов и молодых ученых, МГУ им. М. В. Ломоносова, Россия, 10-14 апреля 2017 г.

3. Международная научная конференция студентов, аспирантов и молодых ученых «Ломоносов-2018», Москва, Россия, 9 апреля - 13 мая 2018 г.

4. Семинар «Теоретическая кибернетика», ИПМ им. М. В. Келдыша, 6 февраля 2019 г.

5. Международная научная конференция студентов, аспирантов и молодых ученых «Ломоносов-2019», Москва, Россия, 8-12 апреля 2019 г.

6. XIII Международный семинар «Дискретная математика и ее приложения», Москва, Россия, 17-22 июня 2019 г.

7. Международная научная конференция студентов, аспирантов и молодых ученых «Ломоносов-2020», Москва, Россия, 10-27 ноября 2020 г.

8. Научно-исследовательский семинар по алгебре, механико-математический факультет МГУ им. М. В. Ломоносова, 7 декабря 2020 г.

9. Семинар «Математические вопросы кибернетики», механико-математический факультет МГУ им. М. В. Ломоносова, 19 марта 2021 г.

10. Объединенное заседание кафедры алгебры и математической логики, кафедры теоретической кибернетики и семинара «Теория вычислимости», институт математики и механики К(П)ФУ, 3 июня 2021 г.

Публикации

Основные результаты по теме диссертации изложены в 6 работах автора [6570], 3 из которых опубликованы в рецензируемых научных изданиях, индексируемых Web of Science, Scopus и RSCI, рекомендованных для защиты в диссертационном совете МГУ по специальности 01.01.09 — дискретная математика и математическая кибернетика [65-67].

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

Диссертация состоит из введения, трех глав, заключения и списка литературы из 70 наименований. В диссертации принята сквозная нумерация утверждений (теорем, лемм и др.). Каждое утверждение нумеруется тремя числами: номером главы, номером параграфа в этой главе и номером утверждения в этом параграфе. Во введении используется отдельная нумерация утверждений отличная от нумерации внутри глав. Общий объем диссертации 133 страница.

Содержание диссертации

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

В первой главе приводятся необходимые определения, а также доказываются некоторые вспомогательные утверждения. Кроме того, для удобства читателей приводятся описания предполных по суперпозиции классов в P2 и P3, а также порождающие системы для минимальных неявно полных замкнутых по суперпозиции классов в P3 (которые для краткости обычно будем называть минимальными неявно полными классами).

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

Так, в первом параграфе рассматриваются неявно предполные классы, которые также являются предполными по суперпозиции. Это классы самодвойственных функций, линейных функций, а также классы функций, сохраняющих константы. Их неявная предполнота утверждается в теоремах 2.1.1, 2.1.2 и 2.1.3 на страницах 29-30.

Во втором параграфе рассматриваются некоторые неявно предполные классы, являющиеся пересечением нескольких предполных по суперпозиции. Такими являются классы функций Шс, где с Е Е3, сохраняющих два нетривиальных разбиения [69] (см. теорему 2.2.1 на стр. 31), а также классы вида УС = Т{а,Ь},о П и{а,ь},{с} П Т{с}д, где а, Ь и с — попарно различные элементы из Е3 = {0,1, 2}, а классы Т{аЬ},0, Ц/{а,Ь},{с} и Т{с}д — предполные по суперпозиции классы функций трехзначной логики, описания которых приводятся в первой главе. Неявная предполнота классов такого вида утверждается в теореме 2.2.2 на странице 33.

В третьем параграфе обсуждаются неявно предполные классы типа Е. Они делятся на два семейства: классы Е^ и классы Е^ , где Ш — некоторый замкнутый по суперпозиции класс булевых функций, а а, Ь и с — попарно различные значения из Е3.

Первому семейству принадлежат классы, которые состоят из функций, сохраняющих некоторое двухэлементное подмножество {а,Ь}.

Пусть функция f Е Р3 сохраняет подмножество {0,1}. Булевым ограничением функции f назовем булеву функцию f, совпадающую с f на всех двоичных наборах. Множество всех функций, сохраняющих подмножество {0,1}, булевы ограничения которых принадлежат заданному классу булевых функций Ш, обозначается через е|°,1}.

В теореме 2.3.5 на странице 39 утверждается, что, если Ш совпадает с одним из классов 5", Ь, К, Д то класс е|°,1} является неяно предполным в Р3.

Классы Е^^

двойственны классам Е^/ } относительно подстановки

Подробнее о понятии двойственности и об определении классов Е^/ } см. стр. 22 и 36 соответственно.

Классы из семейства Е^,Ь}{с} определяются похожим образом. Функции в них сохраняют разбиение {а,Ь}{с}.

Рассмотрим разбиение {0,1}{2}. Оно порождает разбиение множества ЕП на классы эквивалентных наборов (так называемые блоки наборов). Наборы считаются эквивалентными, если у них совпадают номера компонент, содержащих значение 2. Рассмотрим функцию f € Р3, сохраняющую разбиение {0,1}{2}, и некоторый блок наборов В. Если функция на всех наборах блока В принимает булевы значения, то этому блоку естественным образом сопоставляется булева функция, называемая булевым ограничением на блок. Если же на этом

012

а Ь с

блоке f тождественно равна константе 2, то этому блоку сопоставляется константа 2. В таком случае будем говорить, что булево ограничение функции f на блок В не определено. Через е|°'1}{2} обозначается множество всех функций, сохраняющих разбиение {0,1}{2}, у которых либо ни для одного блока не определено булево ограничение на блок, либо все булевы ограничения на блоки принадлежат заданному классу булевых функций Ш. В теоремах 2.3.9 и 2.3.10 на страницах 44 и 45 соответственно утверждается, что, если Ш совпадает с одним из классов К, Д,Ь,То,Т1, то класс е|°'1}{2} является неяно предполным в Рз.

Классы Е^ двойственны классам Е^ относительно подстановки 0 1 ^. Подробнее об определении классов е|^'ь}{с} см. стр 41.

Классы Е^'Ь} и е|^'Ь}{с} рассматривались Ореховой в работе [32].

Отметим, что классы булевых функций Т0, Т1, £, Ь, К, Д которые участвуют в определении неявно предполных классов типа Е, являются неявно предпол-ными в Р2.

Для формулировки результатов четвертого параграфа требуется понятие сохранения предиката [6,48].

Говорят, что функция к-значной логики f(х1,...,хп) сохраняет предикат, а(ж1,... , хт), определенный на Е^, если для любых наборов <51,...,<5га, где <5г = («1, «2,... , ^т), на которых предикат а принимает истинное значение, на наборе

^ («ъа2,..., о,f , а2,..., ),..., f «т,..., «т))

он также истинен. Далее мы будем отождествлять ложное и истинное значения предиката с булевыми значениями 0 и 1 соответственно. Говорят, что класс функций к-значной логики является классом сохранения предиката а, если он содержит те и только те функции, которые сохраняют предикат а. Класс сохранения предиката а будем обозначать через Ро/(а). Если класс функций можно задать как класс сохранения некоторого предиката, то он называется предикатно описуемым. Порядком предиката называется число переменных, от которых зависит данный предикат.

В четвертом параграфе рассматриваются классы монотонных функций. Некоторые из этих классов состоят из функций, монотонных относительно некоторого линейного порядка. Другие — из функций, монотонных относительно некоторого порядка, в котором некоторое значение а Е Е3 больше двух остальных, а те, в свою очередь, не сравнимы. Такой порядок будем обозначать Ла.

Для всякого отношения порядка < определим трехместные предикаты р и

р':

р(а, 1, с) = 1 ^ ((а < 1) Л (с = 1)) V ((1 < а) Л (с = а)),

Список литературы диссертационного исследования кандидат наук Стартостин Михаил Васильевич, 2021 год

Список литературы

[1] Акулов Я. В. О полноте систем функций для классов расширенной суперпозиции // Вестник МГУ. Серия 1. Математика. Механика. — 2011. — № 1. — С. 36-41.

[2] Артамонов В. А., Салий В. Н., Скорняков Л. А. и др. Универсальные алгебры. // Общая алгебра. Т. 2. — М.: Физматлит, 1991. — С. 295-367.

[3] Байрамов Р. А. Об одной серии предполных классов в k-значной логике // Кибернетика. — 1967. — Вып. 1. — С. 7-9.

[4] Биркгоф Г. Теория решеток // М.: Наука, 1984.

[5] Блохина Г. Н. О предикатном описании классов Поста // Дискретный анализ. Вып. 16. Новосибирск, 1970.

[6] Боднарчук В. Г., Калужнин Л. А., Котов В. Н., Ромов Б. А. Теория Галуа для алгебр Поста // Кибернетика. — 1969. — Вып 3. — С. 1-10.

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

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

[9] Деметрович Я., Мальцев И. А. О строении клона Бурле на трехэлементном множестве // Acta Cybernet. — 1989. — Vol. 9, № 1. — P. 1-25.

[10] Захарова Е. Ю. Критерий полноты системы функций из Pk // Проблемы кибернетики. — 1967. — Вып. 18. — С. 5-10.

[11] Захарова Е. Ю., Кудрявцев В. Б., Яблонский С. В. О предполных классах в k-значных логиках // Доклады АН СССР. — 1969. — Т. 186, № 3. — С. 509-512.

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

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

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

[15] Касим-Заде О. М. О сложности параметрических представлений булевых функций // Математические вопросы кибернетики. — 1998. — Вып. 7. — С. 85-160.

[16] Касим-Заде О. М. О неявной полноте в k-значной логике // Вестник МГУ. Серия 1. Математика. Механика. — 2007. — №3. — С. 9-13.

[17] Кон П. Универсальная алгебра. М.: Мир, 1968.

[18] Кудрявцев В. Б. Относительно S-систем функций k-значной логики // Доклады АН СССР. — 1971. — Т. 199, № 1. — С. 20-22.

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

[20] Ло Чжу-Кай. О предполноте классов функций, сохраняющих разбиение // Acta sc. natur. Univ. Jilinensis. — 1963. — № 2.

[21] Мальцев А. И. Итеративные алгебры Поста. — Новосибирск: Ново-сиб. гос. ун-т, 1976.

[22] Мальцев А. И. Избранные труды Т. 2. Математическая логика и общая теория алгебраических систем. — М.: Наука, 1976.

[23] Мартынюк В. В. Исследование некоторых классов в многозначных логиках // Проблемы кибернетики. — 1960. — Вып. 3. С. 49-60.

[24] Марченков С. С. S-классификация функций многозначной логики // Дискретная математика. — 1997. — Т. 9, № 3. — С. 125—152.

[25] Марченков С. С. О выразимости функций многозначной логики в некоторых логико-функциональных языках // Дискретная математика. — 1999. — Т. 11, № 4. — С. 110—126.

[26] Марченков С. С. Дискриминаторные классы трехзначной логики // Математические вопросы кибернетики. — 2003. — Вып. 12. — С. 15-26.

[27] Мещанинов Д. Г. О некоторых свойствах надструктуры класса полиномов в Pk // Математические заметки. — 1988. — Т. 44, № 5. — С. 673—681.

[28] Нгуен Ван Хоа. О структуре самодвойственных замкнутых классов трехзначной логики P3 // Дискретная математика. — 1992. — Т. 4, № 4. — С. 82-95.

[29] Нгуен Ван Хоа. Описание замкнутых классов k-значной логики, сохраняемых всеми автоморфизмами // Дискретная математика. — 1993. — Т. 5, № 4. — С. 87—108.

[30] Нечаев А. А. Критерий полноты систем функций рп-значной логики, содержащих операции сложения и умножения по модулю pn // Методы дискретного анализа в решении комбинаторных задач. — 1980. — Вып. 34. — C. 74—89.

[31] Орехова Е. А. Об одном критерии неявной полноты в k-значной логике // Математические вопросы кибернетики. — 2002. — Вып. 11. — С. 77-90.

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

[33] Орехова Е. А. Об одном критерии неявной полноты в трёхзначной логике // Математические вопросы кибернетики. — 2003. — Вып. 12. — С. 27-74.

[34] Пан Юн-Цзе. Один разрешающий метод для отыскания всех предполных классов в многозначной логике // Acta sc. natur. Univ. Jilinensis. — 1962. — № 2.

[35] Перязев Н. А. Клоны, ко-клоны, гиперклоны и суперклоны // Учёные записки Казанского государственного университета. Серия Физ.-матем. науки. — 2009. — 151, № 2. — C. 120-125.

[36] Подолько Д. К. О классах функций, замкнутых относительно специальной операции суперпозиции // Вестник МГУ. Серия 1. Математика. Механика. — 2013. — №6. — С. 54-57.

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

[38] Ремизов А. Б. О надструктуре замкнутого класса полиномов по модулю k // Дискретная математика. — 1989. — Т. 1, № 1. — С. 3-15.

[39] Саломаа А. Некоторые критерии полноты для множеств функций многозначной логики // Кибернетический сборник. — 1964. — Вып. 8. — С. 7-32.

[40] Тарасова О. С. Классы функций k-значной логики, замкнутые относительно операций суперпозиции и перестановки // Математические вопросы кибернетики. — 2004. — Вып. 13. — С. 59-112.

[41] Толстова Ю. Н. О моделировании /-значной логики в k-значной (k > I) // Проблемы кибернетики. — 1967. — Вып. 18. — С. 67-82.

[42] Угольников А. Б. Классы Поста. М.: Изд.-во ЦПИ при мех.-мат. факультете МГУ, 2008.

[43] Черепов А. Н. Описание структуры замкнутых классов в Pk, содержащих класс полиномов// Проблемы кибернетики. — 1983. — Вып. 40. — С. 5-18.

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

[45] Яблонский С. В. Основные понятия кибернетики // Проблемы кибернетики. — 1959. — Вып. 2. — С. 7-38.

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

[47] Янов Ю. И., Мучник А. А. О существовании k-значных замкнутых классов, не имеющих конечного базиса // Доклады АН СССР. — 1959. — Т. 127, № 1. — С. 44-46.

[48] Яновская С. А. Математическая логика и основания математики // Математика в СССР за 40 лет. Т. 1. — М.: Физматлит, 1959. — С. 13-120.

[49] Bagyinszki J., Demetrovics J. The structure of linear classes in prime-valued logics // Banach Center publications. — 1982. — Vol. 7. — P. 105-123.

[50] Baker К., Pixley A. Polynomial interpolation and the Chinese remainder theorem for algebraic systems // Mathematische Zeitschrift. — 1975. — Vol. 143. — P. 165-174.

[51] Burris S., Sankappanavar, H. P. A course in universal algebra. Berlin: SpringerVerlag, 1981.

[52] Burris S., Willard R. Finitely many primitive positive clones // Proceedings of the American Mathematical Society. — 1987. — Vol. 101, № 3. — P. 427-430.

[53] Csakany B. All minimal clones on three-element set // Acta Cybernet. — 1983. — Vol. 6, № 3. — P. 227-238.

[54] Lau D. Submaximalle Klassen von P3 // J. Inf. Process. Cybern. — 1982. — Vol. 18, № 4/5. — P. 227-243.

[55] Lau D. Function Algebras on Finite Sets. — Springer, 2006.

[56] Martin N. M. The Sheffer functions of 3-valued logic // The Journal of Symbolic Logic. — 1954. — Vol. 19, № 1. — P. 45-51.

[57] Post E. L. Introduction to a general theory of elementary propositions // American Journal of Mathematics. — 1921. — Vol. 43. — P. 143-185.

[58] Post E. L. Two-valued iterative systems of mathematical logic // Princeton University Press, 1941.

[59] Rosenberg I. G. Uber die funktionale Vollständigkeit in den mehrwertigen Logiken // Rozpravy Cs. Akad. Ved. Ser. Rada Mat. Prirod. Sci. — 1970. — Vol. 80. — P. 3-93.

[60] Rousseau G. Completeness in finite algebras with a single operation // Proceedings of the American Mathematical Society. — 1967. — Vol. 18, №6. — P. 1009-1013.

[61] Slupecki J. Kryterium pelnosci wielowartosciowych systemow logiki zdan // Comptes rendus des seances de la Societe des Sciences et des Lettres de Varsovie, Cl. III — 1939. — Vol. 32. — P. 102-110.

[62] Szendrei A. On closed sets of linear operations over a finite set of square-free cardinality // Elektron. Informationsverarb. und Kybernet. — 1978. — Vol. 14, № 11. — P. 547-559.

[63] Szendrei A. Clones in Universal Algebra. — Montreal: Les Presses de l'Universite de Montreal, 1986.

[64] Tardos G. A not finitely generated maximal clone of monotone operations // Order. — 1986. — № 3. — P. 211-218.

Работы автора по теме диссертации

[65] Старостин М. В. Неявно предполные классы и критерий неявной полноты в трехзначной логике // Вестник МГУ. Серия 1. Математика. Механика. — 2018. — №2. — С. 56-59.

[66] Старостин М. В. О некоторых неявно предполных классах функций, сохраняющих подмножества // Вестник МГУ. Серия 1. Математика. Механика. — 2018. — №6. — С. 36-40.

[67] Старостин М. В. О некоторых неявно предполных классах монотонных функций в Pk // Дискретная математика. — 2018. — Т. 30, № 4. — С. 106— 114.

[68] Старостин М. В. Критерий неявной полноты в трехзначной логике // Материалы XII Международного семинара «Дискретная математика и ее приложения» имени академика О. Б. Лупанова (Москва, МГУ, 20—25 июня 2016 г.). — М.: Издательство механико-математического факультета МГУ, 2016. — С. 226-229.

[69] Старостин М. В. О классах самодвойственных функций неявно предполных в Pk // Материалы XIII Международного семинара «Дискретная математика и ее приложения» имени академика О. Б. Лупанова (Москва, МГУ, 17—22 июня 2019 г.). — М.: Издательство механико-математического факультета МГУ, 2019. — С. 182-184.

[70] Старостин М. В. Implicit completeness criterion in three-valued logic in terms of maximal classes [Электронный ресурс] // arXiv.org. URL: https://arxiv.org/abs/2103.16631 (дата обращения: 30.08.2021)