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

У нас уже 176407 рефератов, курсовых и дипломных работ

Сделать закладку на сайт

Заказать диплом, курсовую, диссертацию

Быстрый переход к готовым работам

Мнение посетителей:

Книга жалоб
и предложений

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

Количество страниц	102

ВУЗ	МГИУ

Год сдачи	2010

Бесплатно Скачать	23600.doc

Содержание	Содержание Оглавление Введение 2 1 Аналог критерия Слупецкого для неявной выразимости в Рк 16 1.1 Критерий неявной полноты в /с-значной логике... 16 1.2 Следствия из критерия неявной полноты. Полнота по неявной сводимости и параметрической выразимости в Р^ при к ^ 2 систем, содержащих все одноместные функции ... 26 2 Критерий неявной шефферовости в трёхзначной логике 30 2.1 Основные определения и известные результаты... 31 2.2 Необходимые условия неявной шефферовости... 34 2.2.1 Функции, сохраняющие подмножество... 35 2.2.2 Функции, сохраняющие разбиение... 36 2.3 Критерий неявной шефферовости... 41 2.3.1 Функции, сохраняющие подмножество... 41 2.3.2 Функции, сохраняющие разбиение... 46 3 Критерий неявной полноты в трёхзначной логике 51 3.1 Неявно полные классы, не содержащие констант... 52 3.2 Класс Я? ... 61 3.3 Неявно полные классы, содержащие две константы... 66 3.4 Неявно полные классы, содержащие три константы... 83 3.4.1 Классы сохранения разбиений... 83 3.4.2 Классы монотонных функций... 88 3.4.3 Классы вида Т^л ... 90 3.4.4 Класс Слупецкого... 102 3.4.5 Основной результат... 102 Введение Настоящая диссертация посвящена исследованию проблемы полноты по неявной выразимости в трехзначной логике Рз. Понятие неявной выразимости является одним из обобщений понятия функциональной выразимости функций fc-значной логики (выразимости функций Ахзначной логики посредством суперпозиций), введенных А.В.Кузнецовым [11] наряду с другими: неявной сводимостью и параметрической выразимостью. Функция называется выразимой над системой Е посредством суперпозиций (или функционально выразимой) [18], если ее можно представить в виде суперпозиции функций из Е. Множество всех функций, выразимых по суперпозиции над системой Е, называется замыканием по суперпозиции (или просто замыканием) системы S и обозначается через [S]. Функция называется явно выразимой [11] над системой Е, если она выразима над системой EjJ{x} посредством суперпозиций. Множество всех функций, явно выразимых над системой S, называется явным за-мыканиель системы Е и обозначается через -E(E). Рассмотрим систему функций /с-значной логики S и систему уравнений над S: Ai(xi, ...,xn,y1,...,yp,z) = B1(xi,..., xn,yi, ...,yp, z), А2(хи..., хп, уи ..., ур, z) = В2{хи ..., хп, уи ..., ур, z), w Am(xi,...,xn,yi,...,yp,z) = Bm(xi,...,xn,yu...,yp,z). где А\,..., Am, B\y..., Bm — функции, явно выразимые над системой Е. Говорят, что указанная система уравнений является параметрическим представлением функции f(x\,..., хп), f G Pk, над системой функ- ций Е, если она имеет хотя бы одно решение УР = 9РЫ,...,хп), z = до(хи...,хп), где gi(xi,..., хп) € Я, г = 0,... ,р, — функции от основных переменных, причём для любого такого решения имеет место равенство да(х\, •••¦> %п) — /(xi,... ,хп). Если параметры отсутствуют (т.е. р = 0), то говорят, что рассматриваемая система уравнений является ¦неявным представлением функции /(хь ..., хп) над Е. Функция / называется параметрически (неявно) выразимой над системой S, если для нее существует параметрическое (неявное) представление над S. Множество всех функций, параметрически (неявно) выразимых над системой Е, называется параметрическим замыканием (неявным расширением) системы S. Параметрическое замыкание системы Е обозначается через Р(Е), а неявное расширение через /(Е). Отметим тот факт, что в случае неявной выразимости используется термин "неявное расширение", в то время как в случае параметрической — "параметрическое замыкание". Действительно, отношение неявной выразимости в Рк при к ^ 3 не транзитивно. А именно, если функция / неявно выразима над /(Е), т. е. принадлежит 7(/(Е)), то из этого, вообще говоря, не следует, что функция / неявно выразима над S. Более того, неявное расширение /(S) системы функций S может не совпадать не только со своим неявным расширением 7(/(Е)), но и со своим явным замыканием Е(1(Т,)). В качестве примера, иллюстрирующего это свойство неявной выразимости, можно привести класс Р4(1) всех одноместных функций в Pj. Как показано в диссертации, его неявное расширение не совпадает с Pj, по полно в Р} по суперпозиции. Параметрическая выразимость транзитивна в вышеуказанном смысле, и операция параметрического замыкания является операцией замыкания в обычном смысле (подробнее см. [11]). Обозначим через /т(Е) результат т-й итерации операции неявного расширения по отношению к системе S, полагая /(Е) = /(Е) и /Ш(Е) = /(/m~:L(E)) дЛЯ всякого натурального m, m ^ 2. Функция / называется выразимой над системой функций S по неявной сводимости [11], если найдется т G N такое, что / принадлежит /m(E). Класс, состоящий из всех функций, выразимых над Е по неявной сводимости, называется замыканием системы функций S по неявной сводимости и обозначается /°°(Е). Таким образом, /°°(Е) = [J /Ш(Е). 7П=0 Для любой системы функций Е выполняются включения: S С [Е] С ?(Е) С /(Е) С /°°(Е) С Р(Е). Система Е С Рк называется явно (по суперпозиции (функционально), параметрически, неявно, по неявной сводимости) полной в Рк, если её явное замыкание (замыкание по суперпозиции, параметрическое замыкание, неявное расширение, замыкание по неявной сводимости) совпадает сРк. Система Е С Рк называется явно (по суперпозиции (функционально), параметрически, неявно, по неявной сводимости) предполной в Рк, если эта система не является явно (по суперпозиции (функционально), параметрически, неявно, по неявной сводимости) полной в Pk, в то время как любая система, содержащая ее в качестве собственной подсистемы, явно (по суперпозиции (функционально), параметрически, неявно, по неявной сводимости) полна в Рк. В случае двузначной логики Р2 проблема функциональной полноты была полностью решена Э. Постом [24, 25]. Им была описана структура всех замкнутых по суперпозиции классов в Р2 и показано, что число замкнутых классов в Pi счетно, при этом всякий замкнутый класс имеет конечный базис. Критерий полноты в Р2 был независимо получен С. В. Яблонским (см. [18], а также [20]). Впоследствии С. В. Яблонским [18] был получен критерий функциональной полноты в трехзначной логике Рз. Как и в Р2, в Р3 была найдена конечная система предполных классов, из невхождения системы функций в которые следует ее полнота. Критерий функциональной полноты в терминах предполных классов в Р4 получил А. И Мальцев [13]. А.В.Кузнецовым [12] было доказано, что система всех предполных классов в Рк конечна. Хотя теорема Кузнецова дает алгоритм построения такой системы классов, этот алгоритм даже при небольших значениях к связан с трудоемкими вычислениями и мало пригоден для практического использования. Нахождению всех предполных классов в Рк при произвольных конечных значениях к было посвящено немало работ, завершением которых стала работа И.Розспберга [26]. Описание предполных классов в [2G] основано на введенном А.В.Кузнецовым понятии сохранения предиката (см. [20]). Для многозначных логик Рк при к ^ 3 одним из важнейших результатов, касающихся функциональной полноты, является теорема Слупец- кого [28], утверждающая, что в Pk при к ^ 3 система функций, содержащая все одноместные функции, полна тогда и только тогда, когда она содержит существенную функцию (существенно зависящую более чем от одной переменной), принимающую все к значений. Еще одна задача, относящаяся к теории функциональной полноты, — это задача распознавания в Рк шефферовых функций. Шеффсровой называется функция, которая одна составляет полную в Pk систему. Простейший критерий шефферовости был получен Н.М.Мартином [23] на основе критерия Слупецкого. В дальнейшем были получены другие критерии шефферовости в Рг, Рз и Pk при к > 3, основанные на результатах Э. Л. Поста, С. В. Яблонского и И.Розеиберга. Критерий шефферовости в Pk в терминах минимальной системы предполных классов дан В. Б. Кудрявцевым [7]. Большое значение для целей данной работы имеет критерий Руссо [27], полученный как следствие теоремы Розенберга. А. В. Кузнецов [11] привел примеры, доказывающие неэквивалентность функциональной, неявной, параметрической выразимости и неявной сводимости уже в Рз. Тем не менее, в Pi параметрическая выразимость, неявная сводимость и неявная выразимость эквивалентны. Эквивалентность параметрической выразимости и неявной сводимости в Р2 была доказана А. В. Кузнецовым в работе [11], а позднее О. М. Касим-Заде [4] доказал эквивалентность параметрической и неявной выразимости. А. В. Кузнецовым [11] был получен критерий параметрической выразимости в Pk, а также полное описание системы всех параметрически замкнутых классов в Р2 и вытекающий из него критерий параметрической полноты в Рг- Критерий параметрической полноты в трёхзначной логике Рз был получен А. Ф. Данильчеико в работе [3]. А в работе [21] С. Баррисом и Р. Уиллардом была показана конечность числа параметрически замкнутых классов в Pk для всех конечных значений к. Критерий полноты по неявной выразимости в Р2 установлен О. М. Касим-Заде [4]. И. В. Куку и М. Ф. Раца были получены критерии полноты по параметрической выразимости и неявной сводимости для некоторых специальных логик [8, 9, 15, 16]. В настоящей диссертации решены несколько основных проблем, связанных с понятием полноты систем функций по неявной выразимости в Рз. А именно, установлены критерии неявной полноты систем функций в Рз и неявной шефферовости в Рз. Кроме того, установлен критерий неявной полноты в Pk при к > 2, в некотором смысле являющийся аналогом критерия Слупецкого. Работа состоит из трех глав. В первой главе формулируется и доказывается критерий неявной пол- поты в Pk, к ^ 2, аналогичный критерию Слупсцкого. Теорема (Е. Слупецкий). Для того, чтобы система функций из Pk, к ^ 3, содержащая все одноместные функции из Pk, была полной по суперпозиции, необходимо и достаточно, чтобы она содерэ/сала manoice существенную функцию, принимающую все к значений. Теорема Слупецкого была усилена С.В.Яблонским [18]. Теорема (С.В.Яблонский). Для того, чтобы система функций из Pk, к ^ 3, содержащая все одноместные функции из Р^, выпускающие хотя бы одно значение, была полной по суперпозиции, необходимо и достаточно, чтобы она содероюала также существенную функцию, принимающую все к значений. Класс функций в Pfc, состоящий из всех одноместных функций и всех существенных функций, выпускающих хотя бы одно значение, называют классом Слупецкого. Из теоремы Слупецкого следует, что этот класс является единственным предполным классом в Р^, содержащим все одноместные функции. В диссертации показано, что относительно неявной выразимости аналогичными свойствами обладает минимальный замкнутый по суперпозиции надкласс класса всех одноместных функций PJ: — класс УХк квазилинейных функций [2]. Функция называется квазилинейной, если она имеет вид: f{xu ...,xn) = где g,fi,...,fn ~ одноместные функции, а ф обозначает сложение по модулю к. Глава 1 состоит из двух разделов. В первом разделе сформулирован и доказан критерий неявной полноты систем функций в Д, fc > 2, содержащих все одноместные функции, выпускающие хотя бы одно значение. Теорема1 1. Пусть система функций из Pk, к ^ 2, codepoicum все одноместные функции. Тогда для неявной полноты этой системы необходимо и достаточно, чтобы она содержала также хотя бы одну неквазилинейпую функцию. Как и критерий Слупецкого, эту теорему можно усилить. В первом разделе главы 1 доказаны две теоремы, усиливающие этот критерий. Теорема 3. Пусть система функций из Pk, k ^ 2, codepoicum все одноместные функции, принимающие не более двух значений. Тогда для хЗдесь и далее нумерация теорем соответствует их нумерации в диссертации. неявной полноты этой системы необходимо и достаточно, чтобы она содержала manoice хотя бы одну неквазилинейную функцию. Теорема 4. Пусть система функций из Pk, k ^ 3, содержит все одноместные функции, принимающие два значения, одно из которых фиксировано. Тогда для неявной полноты этой системы необходимо и достаточно, чтобы она содержала также хотя бы одну неквазилинейную функцию. Во втором разделе установлено несколько важных следствий этого критерия. Показано, что в Р^ при k ^ 4 класс одноместных функций полон по неявной сводимости (для к = 4 этот результат установлен О.М. Касим-Заде). Показано также, что при к — 3 неявное расширение класса 91з совпадает с ним самим, а поэтому в Р3 класс одноместных функций не полон по неявной сводимости. При этом, из результатов Л. Ф. Данильченко [3] следует, что класс Р? одноместных функций параметрически полон в Pfc при к ^ 3. Во второй главе решается проблема неявной шефферовости в Рз. Аналогично понятию шефферовой функции, для неявной выразимости естественным образом возникает понятие неявно шефферовой функции. Функция f{x\,.. .,хп) G Pjt, где к > 2, такая, что /({/}) = Р/с, называется неявно шефферовой. Приведем критерии функциональной шефферовости в Рг и Рз, необходимые для дальнейшего изложения. Эти критерии можно либо вывести из критериев полноты в Рг и Рз соответственно [18], либо получить как следствия из общего критерия Руссо [27]. Функции /с-значной логики f(x\,... ,хп) и g(xi,... ,xs) называются перестановочными, если для любых значений переменных хц G Ek {i = 1,2,..., n; j = 1,2,..., s) выполняется соотношение ,..., xns)) = f(g(xn,..., xls), g(x2U ..., x2s),..., g(xnU..., xns)). Обозначим через То и Т\ классы булевых функций, сохраняющие константы 0 и 1 соответственно, через S — класс самодвойственных функций, через L — класс линейных функций, через К — класс функций, состоящий из всех конъюнкций переменных и констант, а через D — класс функций, состоящий из всех дизъюнкций переменных и констант. Классы То, Ть S, L, К и D можно также определять как классы всех функций, перестановочных соответственно с константой 0, с константой 1, с функцией отрицания х, с линейной функцией х\ ф хг © х% (mod 2), с конъюнкцией двух переменных Xi & х2 и с дизъюнкцией двух переменных Х\ V %2- Теорема I. Функция f шефферова в Р2 тогда и только тогда, когда она ис принадлежит классам Tq, Т\ и S. Функция g(xi,... ,хп) 6 Рь называется двойственной функции f(x\, ...,хп) G Pk относительно некоторой подстановки о на fc-элементном множестве Ек = {0,1,..., к — 1}, если для любых значений переменных Х\,... ,хп выполняется соотношение a(f(xu ..., х„)) = ^((t(xi), ... а(хп)). Функция /, двойственная самой себе относительно подстановки а, называется самодвойственной относительно этой подстановки. Под самодвойственной в Р3 функцией всюду в данной работе понимается функция, самодвойственная относительно циклической подстановки (012) на множестве Е3 = {0,1,2} (см. [18]). Функция трехзначной логики Р3 сохраняет двухэлементное подмно-э/сество [18] {а, Ь}, где а и b — различные элементы из ?з, если на любых наборах, состоящих из элементов а, Ь, она принимает значения а или Ь [18]. Для всякого нетривиального разбиения {а, Ь), {с} множества Ез, Е^ — {a,b} U {с}, введём на множестве наборов Е% следующее отношение эквивалентности [18]. Наборы а и (3 называются эквивалентными относительно разбиения {а,Ь}, {с}, если компоненты наборов ос и /3 с одинаковыми номерами либо обе равны с, либо обе принадлежат множеству {а,Ь}. Класс эквивалентности относительно разбиения {а, Ь},{с} называется блоком эквивалентных наборов или просто блоком. Все наборы одного блока содержат в некоторых п — s фиксированных разрядах значение с, а в остальных s разрядах — значения а, Ь, образующие все возможные поднаборы (0 < s < п). Функция трехзначной логики Р3 сохраняет разбиение {а, Ь}, {с}, если на любых наборах, эквивалентных относительно этого разбиениях, она принимает эквивалентные значения [18](см. также [15]). Разбиения множества Е3 на два непустых подмножества будем называть нетривиальными, остальные — тривиальными. Теорема II. Функция f шефферова в Р3 тпогда и только тогда, когда она несамодвойственная и не сохраняет констант, двухэлементных подмноэ/сеств и нетривиальных разбиений. Как было замечено ранее, в Р2 всякая неявно шефферова функция является функционально шефферовой и наоборот. Приведем два критерия неявной полноты в Рг- Эти результаты были получены О. М. Касим-Заде. Первый из них сформулирован и доказан в работе [6], второй является непосредственным следствием первого. Теорема III. Система функций Е неявно полна в Рг тогда и только тогда, когда для каждого из классов: То, Т\, S, L, К, D, — в ней содержатся функция, ему не пршшдлежащая. Теорема IV. Система функций Е неявно полна в Р% тогда и только тогда, когда над Е по суперпозиции выразимы константы О и 1, конъюнкция двух переменных х&су и дизъюнкция двух переменных х V у. Из теоремы III следует, что в Р2 всякая неявно шефферова функция является функционально шефферовой и наоборот. В диссертации получен критерий неявной шефферовости в Pz в терминах критериальной системы классов. Описано 22 класса функций трёхзначной логики, таких, что функция является неявно шефферовой в Р3 тогда и только тогда, когда она не принадлежит пи одному из этих классов. Все эти классы описываются как классы функций, сохраняющих некоторые предикаты [20]. В общем случае, если функция является шефферовой, то она является и неявно шефферовой. Поэтому для установления критерия неявной шефферовости в Рз достаточно исследовать функции, не являющиеся функционально шефферовыми. В соответствии с критерием функциональной шефферовости в Р3, такими функциями являются: самодвойственные функции, а также функции, сохраняющие какую-либо константу, двухэлементное подмножество или нетривиальное разбиение. Классы самодвойственных и сохраняющих константы функций не полны неявно [3]. Следовательно, если функция самодвойственна или сохраняет константу, то она не является неявно шефферовой. Поэтому для установления критерия неявной шефферовости в Р$ достаточно исследовать на неявную шефферовость те функции, которые сохраняют двухэлементное подмножество или нетривиальное разбиение. Произвольной функции f(x), сохраняющей двухэлементное подмножество {а, &}, на этом подмножестве можно естественным образом поставить с соответствие некоторую булеву функцию с помощью отображения а —> 0, Ь —* 1. Назовем эту функцию {0, \}-образом функции f(x). Пусть А — замкнутый по суперпозиции класс булевых функций. Обозначим через ?д класс всех функций трехзначной логики сохраняющих подмножество {а,Ь}, {0,1}-образы которых принадлежат классу А. Класс Е^ ' замкнут по суперпозиции. При рассмотрении функций трехзначной логики, сохраняющих нетривиальное разбиение, также можно установить связь этих функций с функциями из Рг- Каждому блоку наборов можно сопоставить либо константу с, либо некоторую булеву функцию с помощью отображения а —> 0,6 —> 1, которую будем называть булевым ограничением функции / на этом блоке. Пусть А — замкнутый по суперпозиции класс булевых функций. Обозначим через ?д с' класс всех функций трехзначной логики, сохраняющих разбиение {а, Ь}, {с}, у которых все булевы ограничения на блоках принадлежат классу А. Класс Е^а' с* замкнут по суперпозиции. Обозначим через Т$, Т-р и Т% классы функций в Р3, сохраняющих константы 0, 1 и 2 соответственно, и через 53 класс функций, самодвойственных относительно циклической подстановки (012) (эти обозначения соответствуют принятым в [18]). В диссертации установлен следующий критерий неявной шефферо-вости в трехзначной логике. Теорема 8 Функция f является неявно шефферовой в Рз тогда и только тогда, когда она не принадлежит пи одному из следующих 22 чеппгтп- ТЗ ТЗ Г3 Я3 У{0'1} Г{0>2} T{h2} Vf0'1}-2} vf0-1}.^} у{0,2},{1} классов. 1 о > 11 > 12> ° > ^s > ^S > ^S > ^То > ^Ti > ^То ' } у,{1,2},{0} у.{1,2},{0} у{0,1},{2} V{O,2},{1} у,{1,2},{0} г{0,1},{2} Двухэлементное подмножество множества Е3 — {0,1,2} будем называть чужим для разбиения, если элементы рассматриваемого подмножества не эквивалентны относительно этого разбиения. Соответственно, разбиения, относительно которых элементы этого подмножества не эквивалентны, будем называть чужими для него. Функции из класса Е^' будем называть {а,Ь}-самодвойственными, функции из класса EJ°' — блочно-линейными относительно разбиения {а, Ь}, {с}, функции из класса ?]?' ''с' — блочно-перестаповочными с конъюнкцией относительно разбиения {а, Ь}, {с}, функции из класса ?{^.ь},{с} _ блочно_перестановочными с дизъюнкцией относительно разбиения {а,Ь},{с}. В диссертации получена следующая эквивалентная формулировка критерия шефферовости в Рз- Теорема 9. Функция f является неявно шефферовой в Рз тогда и только тогда, когда она не сохраняет констант, и удовлетворяет одному из условий: 1. f не сохраняет двухэлементных подмиоэ/сеств, нетривиальных разбиений и не является самодвойственной; 2. f сохраняет некоторое двухэлементное подмножество {а, Ь}, пе сохраняет чужих ему нетривиальных разбиений и не является {а, Ь} -самодвойственной; 3. f не сохраняет двухэлементных подмножеств, сохраняет некоторое нетривиальное разбиение {а, Ь}, {с} и относительно этого разбиения не является блочно-линейной, блочио-самодвойствен-ной, блочно-перестановочной с конъюнкцией или блочно-переста-нооочной с дизъюнкцией. Глава 2 состоит из трех разделов. В первом разделе даются необходимые определения и формулируются известные результаты, использующиеся при доказательстве критерия. Во втором разделе формулируются и доказываются необходимые условия неявной шефферовости. В третьем разделе формулируются и доказываются два приведенных выше эквивалентных критерия неявной шефферовости в Рз. В третьей главе сформулирован и доказан критерий неявной полноты в Р3. Распространенным подходом к решению задач о полноте в функциональных системах является описание соответствующей системы всех предполных классов. Как было отмечено выше, отношение неявной выразимости в Pk при к > 3 не транзитивпо. Поэтому в диссертации при поиске критерия неявной полноты в Рз был выбран другой подход, аналогичный принятому в теореме IV. Поскольку неявное расширение класса совпадает с неявным расширением его явного замыкания, рассмотрение произвольных систем функций можно свести к рассмотрению явно замкнутых классов. Установлено следующее. В Рз существует 27 конечных неявно полных систем функций, порождающих 27 различных явно замкнутых классов, каждый из которых неявно полон и не содержит другого явно замкнутого и неявно полного класса. При этом всякий явно замкнутый класс неявно полон тогда и только тогда, когда содержит один из указанных 27 классов. Список этих 27 систем функций приведен в таблице 2 (см. стр. 15). При этом используются следующие обозначения. Для задания функций одной и двух переменных и для оперирования с ними будем использовать таблицы значений. Приведем примеры. Таблица 1 а) задаёт функцию тах^,:^)) а таблица 1 б) — функцию Для удобства в таблице 2 и далее в тексте диссертации будем пользоваться упрощенной записью, иногда заменяя таблицами наименования функций в формулах: (х) Если наименования переменных неважны, то в этой записи они будут опускаться. Условимся в таблицах использовать знак «*» в тех случаях, когда значение функции па некотором наборе может быть произвольным. В таких случаях рассуждения будут строиться для всего класса функций рассматриваемого вида. Множество всех функций, двойственных функциям некоторого замкнутого по суперпозиции класса Е относительно фиксированной подстановки тг, также является замкнутым классом и называется двойственным классу Е относительно этой подстановки. Нетрудно видеть, что двойственные классы и двойственные функции обладают сходными свойствами. В частности, двойственные друг другу классы одновременно либо неявно полны, либо не полны. В дальнейшем, называя функции или классы функций двойственными, будем иметь в виду, что они двойственны относительно некоторой нетождественной подстановки. Приведем формулировку установленного в диссертации критерия неявной полноты в Рз- Теорема 21. Система функций W неявно полна в Рз тогда и только тогда, когда над ней явно выразима хотя бы одна из систем функций: 0 110 0 0 Как было указано выше, существует эквивалентная формулировка критерия неявной полноты в Рз- Теорема 22. Система функций W неявно полна в Рз тогда и только тогда, когда над W явно выразима хотя бы одна из 27 систем функций, приведенных в таблице 2. Из критерия неявной полноты в Рз вытекает несколько следствий. Теорема 23. Всякая неявно полная в Р3 система содержит конечную неявно полную подсистему. Теорема 24. Проблема распознавания неявной полноты конечных систем функций в Рз алгоритмически разрешима. Теорема 25. Система всех неявно предполных классов в Рз конечна. Всякая система функций трехзначной логики неявно полна в Рз тогда и только тогда, когда она целиком не содеро/сится ни в одном из неявно предполных классов. Глава 3 состоит из четырех разделов. Для нахождения всех минимальных неявно полных явно замкнутых классов в Рз по отдельности рассматриваются явно замкнутые классы, содержащие ни одной, одну, две или все три константы и входящие в различные явно предполные классы. В первом разделе главы 3 установлен критерий неявной полноты в трёхзначной логике для явно замкнутых классов, не содержащих констант. Во втором разделе рассмотрен важный класс функций трехзначной логики — неявно предполный класс Гб],, являющийся расширением клас- са 7?2, описанного автором в работе [1]. Непринадлежность этому классу дает необходимое условие неявной полноты в Рз, играющее важную роль при исследовании на неявную полноту систем функций, содержащих константы. В третьем разделе рассмотрен случай, когда исследуемый явно замкнутый класс содержит две константы. В четвертом разделе рассмотрен последний случай, когда исследуемый явно замкнутый класс содержит все три константы, и установлен критерий неявной полноты в Рз- Автор выражает глубокую благодарность своему научному руководителю, профессору Октаю Мурадовичу Касим-Заде, за постановку задачи, многочисленные обсуждения, постоянную поддержку и внимание к работе. Глава 1 Аналог критерия Слупецкого для неявной выразимости в 1.1 Критерий неявной полноты в /с-значной логике В настоящей главе все рассматриваемые объекты (наборы, функции и т.д.) связываются с fc-значнон логикой Р^, при некотором фиксированном к ^ 2. Введем ряд понятий и определений. Рассмотрим наборы из куба Е%. Определение 1. Четыре набора 01,02,0:3,0:4 составляют квадрат К, К = {0:1,0:2,0:3,0:4}, если: 1) наборы 01,02,0:3,0:4 попарно различны; 2) наборы 01,0:2,0:3,0:4 совпадают по всем компонентам, кроме двух (эти две компоненты мы будем называть непостоянными, а все остальные компоненты — постоянными); 3) каждая из двух непостоянных компонент принимает на наборах oi, 02,03,04 только два значения. Наборы, составляющие квадрат, будем называть вершинами этого квадрата. Поскольку из двух компонент, каждая из которых принимает только два значения, можно составить всего четыре различных набора, то каждое из своих значений непостоянная компонента вершин квадрата принимает на двух вершинах.

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

Цена, в рублях: (при оплате в другой валюте, пересчет по курсу центрального банка на день оплаты)	1425

Скачать бесплатно	23600.doc

Найти готовую работу

ЗАКАЗАТЬ

Обратная связь:

Связаться

Вход для партнеров

Регистрация

Восстановить доступ

Материал для курсовых и дипломных работ

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

15.04.24 Критерии качества преподавания

15.04.24 Категория нормы в обучающей деятельности

Архив материала для курсовых и дипломных работ

Ссылки:

Счетчики:

© 2006-2022. Все права защищены.
Выполнение уникальных качественных работ - от эссе и реферата до диссертации. Заказ готовых, сдававшихся ранее работ.