авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

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

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

На правах рукописи

Нагорный Александр Степанович О ПЕРЕСЕЧЕНИЯХ И ОБЪЕДИНЕНИЯХ ПРЕДПОЛНЫХ КЛАССОВ МНОГОЗНАЧНОЙ ЛОГИКИ 01.01.09 – дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва – 2013

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

Научные руководители: доктор физико-математических наук профессор Вороненко Андрей Анатольевич доктор физико-математических наук профессор Марченков Сергей Серафимович

Официальные оппоненты: доктор физико-математических наук профессор Дьяконов Александр Геннадьевич кандидат физико-математических наук доцент Дайняк Александр Борисович

Ведущая организация: Московский энергетический институт (Национальный исследовательский университет)

Защита диссертации состоится 7 июня 2013 г. в 11 часов на заседании диссертационного совета Д 501.001.44 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, Москва, ГСП-1, Ленинские горы, МГУ, 2-й учебный корпус, факультет вычислительной математики и кибернетики, ауд. 685. Желающие присутствовать на засе дании диссертационного совета должны сообщить об этом за два дня по тел. (495) 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М.В. Ломоносова. С текстом автореферата можно ознакомить ся на официальном сайте факультета ВМК МГУ http://cs.msu.ru.

Автореферат разослан мая 2013 г.

Ученый секретарь диссертационного совета В.А. Костенко к.т.н., ведущий научный сотрудник

Общая характеристика работы

Актуальность темы. Функции многозначной логики один из основ ных модельных объектов дискретной математики, широко используемых для описания разнообразных дискретных систем. Интерес к функциям многозначной логики обусловлен как достаточно широкими выразитель ными возможностями данных функций, так и возможностью применять к функциям комбинаторно-логические приемы и методы различного рода. В частности, эти методы позволяют получать многочисленные разложения и представления функций через „элементарные“ функции.

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

Среди различных подходов к классифицированию множества функций многозначной логики исторически первым явился подход, основанный на термальной (формульной) выразимости функций. Этот подход содержался в пионерских работах Э. Поста [21, 22], в которых была построена полная классификация множества булевых функций. Сейчас этот подход связыва ют с операторами замыкания на множестве функций многозначной логики (у Поста оператор суперпозиции) и классификациями, состоящими из замкнутых (относительно выбранного оператора замыкания) классов.

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

Пусть Lk обозначает решетку замкнутых классов в Pk.

Случай k = 3 вызывал и вызывает наибольший интерес у исследовате лей, поскольку это наименьшее значение k, при котором Lk имеет конти нуальную мощность. В качестве примера укажем, что для решетки L • все 18 максимальных элементов были найдены С.В. Яблонским [13], • все 169 субмаксимальных элементов были найдены Д. Лау [19], • все 84 минимальных элемента были построены Б. Чаканем [16], • все элементы решетки L3, содержащие множество всех трехзначных функций одной переменной, описаны Г.А. Бурле [4], • все 144 дискриминаторных класса в P3 были получены С.С. Марчен ковым [11], • все замкнутые классы линейных функций в Pk при любом простом k (и, в частности, в P3 ) были описаны Я. Деметровичем и Я. Бадь инским [17], однако в этом направлении имеется гораздо более общий результат: в P3 существует лишь конечное число замкнутых классов, содержащих существенную линейную функцию;

все эти классы фак тически описаны в работе С.С. Марченкова [10].

К строению решетки L3 также имеют отношение работы [2, 12, 6, 3, 5].

Особо отметим относительно недавно появившуюся монографию [20], в ко торой можно найти подробное изложение целого ряда новейших результа тов о строении решетки L3, а также некоторых фрагментов решетки Lk для произвольных значений k 3.



Самыми важными в вопросах классификации (а также в вопросах полно ты) представляются максимальные (предполные) классы. Согласно хорошо известной теореме А.В. Кузнецова [7], при любом k 2 число предполных классов в Pk конечно.

Как уже говорилось выше, все предполные классы в P2 были описаны Э. Постом, отдельные семейства предполных классов в Pk при k 3 были найдены С.В. Яблонским [13, 14], А.В. Кузнецовым [7], В.В. Мартыню ком [9], Ло Чжу-Каем [8] и другими исследователями. Полное описание предполных классов в Pk (в терминах сохранения некоторых предикатов) было получено И. Розенбергом [23, 24].

Нам понадобятся несколько определений.

n Множество всех функций из Pk от n переменных обозначим через Pk.

n Говорят, что функция f Pk сохраняет предикат (x1, x2,..., xm ), если для любых n наборов (a11,..., am1 ),..., (a1n,..., amn ), удовлетворяющих предикату, набор (f (a11,..., a1n ),..., f (am1,..., amn )) также удовлетворяет предикату.

Для любого предиката множество всех функций, сохраняющих преди кат, является замкнутым классом [1]. Отметим также, что из теоремы Розенберга [23, 24] следует, что при любом k 2 все предполные классы k -значной логики являются предикатно описуемыми. В настоящее время, следуя И. Розенбергу, принято разбивать все предполные классы (и соот ветствующие предикаты) на шесть семейств:

• классы функций, монотонных относительно частичных порядков с наименьшим и наибольшим элементами – классы семейства M, • классы функций, сохраняющих нетривиальные разбиения множества Ek = {0, 1,..., k 1} – классы семейства U, • классы функций, сохраняющих центральные предикаты – классы се мейства C, • классы функций, сохраняющих сильно гомоморфные прообразы h-адических элементарных отношений – классы семейства B.

• классы самодвойственных функций – классы семейства S, • и классы квазилинейных функций – классы семейства L.

Нам будет удобно выделить в семействе C подсемейство T классов функ ций, сохраняющих одноместные центральные предикаты.

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

Этот факт следует также из теории Галуа для алгебр Поста [1, 18], соглас но которой любой замкнутый класс можно задать подходящим множеством предикатов (может быть, бесконечным), среди которых обязательно при сутствует хотя бы один из предикатов, задающих предполный класс.

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

каковы все те замкнутые классы в Pk, которые определяются только пре дикатами, задающими предполные в Pk классы? Иными словами, каковы все те замкнутые классы в Pk, которые представляют собой пересечения предполных в Pk классов?





Данные замкнутые классы, которые мы будем назвать основными за мкнутыми классами, образуют „каркас“ решетки замкнутых классов в Pk, поскольку они определяются только „основными свойствами“ класса Pk свойствами, присутствующими во всех остальных замкнутых классах и от вечающими за решение проблемы полноты в классе Pk.

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

Очевидно, что количество основных замкнутых классов (при фиксиро ванном k ) конечно. При k = 2 (случай булевых функций) имеется ровно предполных классов и ровно 14 различных пересечений предполных клас сов. При k = 3 число предполных классов равно 18, а число различных пересечений предполных классов теоретически может быть близко к 218.

Понятно, что даже при небольших значениях k решение задачи построе ния всех основных замкнутых классов в Pk наталкивается на значительные трудности переборного характера. Вместе с тем анализ случаев k = 2, 3 по казывает, что одни и те же основные замкнутые классы могут получаться в результате пересечения предполных классов из довольно большого числа наборов таких классов. Возникает задача минимизирования перебора при перечислении основных замкнутых классов. В данной диссертации автором разработан путь решения этой задачи построение „аксиом вложения“, которые имеют вид Ki1 Ki2... Kis Kj1 Kj2... Kjt () и тем самым устанавливают связь (включение) пересечений некоторых предполных классов Kim и объединений некоторых (других) предполных классов Kjn.

Помимо классификации множеств функций, замкнутых относительно операции суперпозиции, определенный интерес представляет задача „ин дивидуальной классификации“ функций k -значной логики, т.е. задача по лучения множества F (k) всех возможных распределений таких функций по предполным в Pk классам (т.н. характеристических строк функций).

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

Наконец, для решения ряда задач (в частности, для ответа на вопрос, существует ли функция с заданным распределением по предполным клас сам) полезно иметь множество всех тупиковых (т.е. неупрощаемых) акси ом вложения, а еще лучше иметь его некоторое базисное подмножество (т.е. минимальное множество аксиом вложения, их которого логически вы водятся все остальные аксиомы вложения). В этом случае вместо того, чтобы вести поиск нужной строки в множестве F (k), мы можем просто проверить, удовлетворяет ли данное распределение по предполным клас сам всем аксиомам из базисного множества аксиом.

Цель работы. Диссертационная работа преследует следующие цели:

• изучить структуру замкнутых (относительно операции суперпозиции) классов функций многозначной логики на предмет получения некото рых универсальных (справедливых для всех k 2) свойств вида () для пересечений и объединений предполных в Pk классов;

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

а в четырехзначной логике построить фрагменты решетки ос новных замкнутых классов.

Основные результаты работы и научная новизна. Все основные результаты диссертации являются новыми. Укажем наиболее существен ные из них.

1. Доказаны 48 утверждений и следствий из них, представляю щих собой универсальные (справедливые для всех k 2) свойства пересечений и объединений предполных клас сов k -значной логики (первая глава);

2. В трехзначной логике:

найдены все 1505 основных замкнутых (относительно опе рации суперпозиции) классов и описан алгоритм постро ения решетки по вложению, которую они образуют (тео рема 2.2 и приложение B);

получены все 406 вариантов распределения функций по предполным классам (теорема 2.3);

найдены все 3602 тупиковые аксиомы вложения, среди которых выделены все 58 ядровых и все 319 регулярных аксиом. Указана также одна из базисных систем аксиом (теоремы 2.4 и 2.5 и приложение D);

3. В четырехзначной логике построены фрагменты решетки всех основных замкнутых классов для пересечений предпол ных классов из семейств M и U (теоремы третьей главы и при ложение E).

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

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

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

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

Научные конференции “Тихоновские чтения” (Москва, 2010–2012);

Научные конференции “Ломоносовские чтения” (Москва, Севастополь, 2011–2013);

XI, XIII и XV Международные научно-практические семинары “Ком бинаторные конфигурации и их применения” (Кировоград, 2011–2013);

XVI Международная конференция “Проблемы теоретической кибер нетики” (Нижний Новгород, 20–25 июня 2011 г.);

XI Международный семинар “Дискретная математика и ее приложе ния” (Москва, 18–23 июня 2012 г.);

Международный научный семинар “Дискретная математика и ее при менение в экономико-математическом моделировании и информаци онных технологиях” (Запорожье, 11–13 октября 2012 г.).

Кроме того, результаты обсуждались на научных семинарах кафедры математической кибернетики факультета ВМК МГУ.

Публикации. По теме диссертации опубликовано 11 работ [25]–[35], в том числе две работы [29, 32] в рецензируемых изданиях, включенных в перечень ВАК РФ. Все работы опубликованы без соавторов.

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

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

Первая глава диссертации посвящена исследованию пересечений и объ единений предполных классов k -значной логики для произвольного k и является самой объемной. В первом параграфе приводятся основные определения и обозначения, используемые в диссертационной работе. В частности, в нем приводится предикатное описание всех шести семейств предполных классов k -значной логики.

Аксиому вложения вида () назовем тупиковой, если после удаления любого Kim из левой части или Kjn из правой части она перестает быть аксиомой (т.е. соответствующее вложение становится ложным). Из конеч ности числа предполных в Pk классов (при любом заданном k 2) следует конечность множества всех тупиковых аксиом вложения в Pk. Две аксиомы вложения вида () назовем двойственными, если найдется такая переста новка на Ek, которая переводит одну аксиому вложения в другую.

Подмножество A множества всех тупиковых аксиом вложения назовем полной системой аксиом, если все остальные аксиомы вложения логически следуют из аксиом этого подмножества, и неприводимой системой аксиом, если никакая аксиома из A логически не следует из всех остальных аксиом из A. Неприводимую полную систему аксиом вложения будем называть базисной системой аксиом.

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

Если, наоборот, ни одна базисная система аксиом не содержит некоторую тупиковую аксиому вложения, то такую аксиому назовем регулярной.

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

Пусть Im(f ) есть множество значений функции f Pk на множестве Ek, K = Pk \ K для любого K Pk и C есть минимальный по числу наборов двухместный центральный предикат с центром.

Следующая лемма играет важную роль.

Лемма 1.9. Пусть k 3, s 2 и для каждого i = 1, 2,..., s подмно жество i множества Ek удовлетворяет условию 1 |i | k 2.

s Для того чтобы для любой функции f C i выполнялось Im(f ) = Ek, i= необходимо и достаточно, чтобы нашлось подмножество {i1, i2,..., it } {1, 2,..., s } множества такое, что t (Ek \ ij ) = Ek и при всех j = 1, 2,..., t справедливо |ij | = k 2.

j= В третьем параграфе для произвольного k 2 мы формулируем и доказываем, опираясь на факты и леммы из предыдущего параграфа, ряд универсальных свойств предполных классов k -значной логики (28 утвер ждений и восемь следствий из них). Бльшая часть этих свойств представ о ляет собой некоторые аксиомы вида ().

Для произвольного = E Ek обозначим через TE множество функ ций из Pk, сохраняющих множество E.

Утверждение 1.16. Пусть k 3. Для любых непустых множеств и E, удовлетворяющих условиям E = и E Ek, справедливо вложение C TE TE.

Для произвольного нетривиального разбиения D = {E1, E2,..., Es } мно жества Ek обозначим через UE1,E2,...,Es класс всех k -значных функций, со храняющих разбиение D.

Утверждение 1.18. Пусть k 3. Тогда для любого нетривиального разбиения D = {,, E} множества Ek выполнено M,,E C TE U,E U,E.

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

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

Утверждение 1.26. Пусть k 3, t 2 и пусть множества t 1, 2,..., t Ek таковы, что (Ek \i ) = Ek и при всех i = 1, 2,..., t i= справедливо |i | = k 2. Тогда t C1,2,...,k2 B T0,k1.

Ci i= Отдельный, четвертый параграф первой главы посвящен исследова нию некоторых предполных классов монотонных k -значных функций, а именно классов функций, монотонных относительно линейных порядков на Ek (подсемейство M k ), и классов функций, монотонных относительно ча стичных порядков на Ek, имеющих наименьший и наибольший элементы, и таких, что остальные элементы в них попарно несравнимы (подсемейство M k ). Здесь формулируются и доказываются восемь теорем о том, в каких случаях пересечение таких классов минимально (т.е. содержит лишь кон станты из Ek и селекторные функции) и в каких случаях все функции в этом пересечении монотонны относительно некоторого линейного порядка на множестве Ek.

Приведем формулировки двух утверждений из этого параграфа:

Утверждение 1.34. При всех k k для любых классов K1, K2,..., Kp M k верно a) при 2 p p Kj K;

j=1 KM k k найдутся классы K1, K2,..., Kp M k такие, что b) при p p Kj K.

j=1 KM k Утверждение 1.35. При всех k k a) в случае 2 p существуют p попарно различных классов p K1, K2,..., Kp M k таких, что Kj K;

j=1 KM k k1 k b) в случае +1 p для любых p попарно различных классов 2 p k K1, K2,..., Kp M выполняется Kj K.

j=1 KM k Данные результаты могут быть использованы для оптимизации алго ритмов поиска указанных выше пересечений классов k -значных функций для фиксированных значений k, а также для получения нижних и верхних оценок для числа попарно различных пересечений (такого вида) классов k -значных функций при растущем k.

Также отметим, что утверждения 1.34 и 1.35 являются примерами „по роговых“ свойств предполных классов k -значной логики при увеличении количества p пересекаемых классов всего на единицу свойства результата резко изменяются.

В пятом параграфе речь идет о решетке основных замкнутых классов в k -значной логике и об одном из методов ее построения.

Наконец, в шестом параграфе первой главы для произвольного k подробно описаны три алгоритма:

алгоритм построения множества F (k) всех попарно различных харак теристических строк для k -значных функций;

алгоритм поиска всех тупиковых аксиом вложения в k -значной логике;

алгоритм поиска всех (в том числе минимальных) базисных систем аксиом вложения в k -значной логике.

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

Его основные результаты помещены в формулировку теоремы 2.1 и в приложение A и фактически являются следствиями известных резуль татов Э. Поста [21, 22].

Второй параграф начинается с предикатного описания всех 18 пред полных классов трехзначной логики. Далее доказывается утвержде ние 2.2, содержащее 30 свойств аксиом вложения пересечений предпол ных классов трехзначной логики в некоторый другой предполный класс.

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

Остальные свойства являются специфическими для предполных классов именно трехзначной логики, поэтому доказываются отдельно. Отметим, что при доказательстве активно используется распределение одноместных функций из P3 по предполным классам, полученное С.В. Яблонским [14].

Опираясь на доказанные в утверждении 2.2 свойства, с помощью ком пьютерной программы мы получили множество всех основных замкнутых классов трехзначной логики (теорема 2.2 и приложение B).

В третьем параграфе доказывается утверждение 2.3, состоящее из 11 аксиом вложения некоторых предполных классов трехзначной логики или их пересечений в объединение двух или более (других) предполных классов. Эти аксиомы, вместе с аксиомами из утверждения 2.2, позволяют найти все варианты распределения трехзначных функций по предполным классам (теорема 2.3), а также решить некоторые задачи, связанные с базисами в P3 (замечание 2.1).

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

В этой таблице таблице также выделены все ядровые и все регулярные аксиомы.

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

Данная базисная система аксиом позволяет ответить на вопрос, суще ствует ли трехзначная функция с заданным распределением по предпол ным классам, проверив справедливость всех аксиом системы, что значи тельно проще, чем вести поиск характеристического вектора данной функ ции в множестве F (3), состоящем из 406 строк длины 18.

Третья глава посвящена исследованию пересечений и объединений предполных в P4 классов и изучению связей между ними.

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

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

Еще большее число аксиом вложения получено автором с помощью ком пьютерных программ. В частности, найдены все пересечения предполных классов, содержащих все константы из Ek, в некоторый класс из семей ства M или из семейства U. Некоторые из них перечислены во втором и в третьем параграфе, соответственно.

Данные результаты позволили построить некоторые обозримые фраг менты решетки L основных замкнутых классов в P4 (теоремы 3.3 и 3. из второго параграфа и теоремы 3.6–3.8 из третьего параграфа), которая в этом случае содержит конечное, но очень большое число вершин.

Второй и третий параграфы третьей главы имеют также по одному техническому утверждению, посвященному перечислению всех неприводи мых (т.е. неупрощаемых) пересечений предполных классов из семейства M (теорема 3.2) и из семейства U (теорема 3.5), содержащих только все константы из E4 и все селекторные функции (такие пересечения мы на зываем тривиальными). Список неприводимых тривиальных пересечений крайне полезен при поиске (в частности, при компьютерном поиске) тупи ковых аксиом, поскольку он позволяет существенно уменьшить количество логических слагаемых при раскрытии скобок в КНФ функции покрытия.

В последнем, четвертом параграфе третьей главы указаны точные значения количеств неприводимых тривиальных пересечений, состоящих из n классов (n = 2, 3,..., 8), для всех предполных в P4 классов, содер жащих все константы (таблица 7).

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

Диссертационная работа содержит пять приложений. Приложение A содержит диаграмму Хассе решетки основных замкнутых классов алгебры логики. В приложении B перечислены элементы полурешетки пересече ний в P3, вместе с примерами множеств функций, задающих эти элементы.

Приложение C содержит примеры функций для строк множества F (3) (теорема 2.3). В приложении D перечислены все тупиковые попарно не двойственные аксиомы вложения в P3. В соответствующей таблице для каждой такой аксиомы указано количество двойственных аксиом, а также выделено множество ядровых и регулярных аксиом вложения. Наконец, приложение E содержит 6 диаграмм Хассе для различных фрагментов решетки L основных замкнутых классов в P4 (теоремы 3.3, 3.4, 3.6–3.8).

СПИСОК ЛИТЕРАТУРЫ 1. Боднарчук В. Г., Калужнин В. А., Котов В. Н., Ромов Б. А. Теория Га луа для алгебр Поста I-II// Кибернетика. 1969. № 3. С. 1–10, № 5. С. 1–9.

2. Булатов А. А. Конечные подрешетки в решетке клонов // Алгебра и логика. 1994. Т. 33, № 5. С. 514–549.

3. Булатов А. А. Подрешетки решетки клонов функций на трехэлемент ном множестве, I // Алгебра и логика. 1999. Т. 38, № 1. С. 3–23;

II, там же. 1999. Т. 38, № 3. С. 269–295.

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

5. Жук Д. Н. Решетка замкнутых классов самодвойственных функций трехзначной логики // М.: Издательство Московского университета.

2011. 109 с.

6. Крохин А. А. Моноидальные интервалы в решетках клонов // Алгебра и логика. 1995. Т. 34, № 5. С. 288–310.

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

Т. 2. М.: Изд-во АН СССР. 1956. С. 145–146.

8. Ло Чжу-Кай Предполные классы, определяемые k -арными отношени ями в k -значной логике - Asta Sci. natur. Univ. Jilinesis, N 3. 1964.

9. Мартынюк В. В. Исследование некоторых классов функций в много значных логиках // Проблемы кибернетики. 1960. 3. С. 49–60.

10. Марченков С. С. О замкнутых классах в Pk, содержащих однородные функции // Препринт ИПМ АН СССР. 1984. № 35. С. 1–28.

11. Марченков С. С. Дискриминаторные классы трехзначной логики // Матем. вопросы кибернетики. Вып. 12. M.: Наука. 2003. С. 15–26.

12. Сафин К. Л. Идеалы итеративных алгебр // Сибир. матем. журнал.

1995. Т. 36, № 6. С. 1384–1391.

13. Яблонский С. В. О функциональной полноте в трехзначном исчисле нии // ДАН СССР. 1954. 95. № 6. С. 1153–1156.

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

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

С. 44–46.

16. Cs k ny B. All minimal clones on three-element set // Acta Cybernet.

aa 1983. V. 6, N. 3. P. 227–238.

17. Demetrovics J., Bagynski J. The lattice of linear classes in prime-valued logics // Discrete Mathematics. Banach Center Publications. Warsaw, 1982. V. 7. P. 105–123.

18. Geiger D. Closed systems of functions and predicates // Pacic journal of mathematics. 1968. V. 27. N. 1. P. 95—100.

19. Lau D. Submaximalle Klassen von P3 // Electron. Informationsverarb.

und Kybernet. 1982. B. 18, N. 4-5. S. 227–243.

20. Lau D. Function Algebras on Finite Sets. A Basic Course on Many Valued Logic and Clone Theory // Springer-Verlag Berlin Heidelberg.

2006. 670 p.

21. Post E. L. Introduction to a general theory of elementary propositions // Amer. J. Math. 1921. 43. N. 4. P. 163–185.

22. Post E. L. Two-valued iterative systems of mathematical logic. N. J.:

Princeton Univ. Press, 1941.

23. Rosenberg I. G. La structure des fonctions de plusieurs variables sur un ensemble ni // C.R. Acad. Sci. Paris. Ser. A.B. 1965. 260. P. 3817– 3819.

24. Rosenberg I. G. Uber die funktionale Vollst ndigkeit in den mehrwer a tigen Logiken // Rozpravy Ceskoslovenske Akad. V d. N. 80. Praha:

e Rada Math. Pir. V d., 1970. P. 3–93.

r e Публикации автора по теме диссертации 25. Нагорный А. С. О мощности базисов трехзначной логики // Научная конференция „Тихоновские чтения 2010“, тезисы докладов (Москва, 25 29 октября 2010 г.). М.: Изд-во МАКС Пресс, 2010, С. 9.

26. Нагорный А. С. О свойствах предполных классов в трехзначной ло гике // XI Межвузовский научно-практический семинар „Комбинатор ные конфигурации и их применения“ (Кировоград, 15-16 апреля г.), Материалы. Кировоград: Изд-во Кировоградского национального технического университета, 2011, С. 117-122.

27. Нагорный А. С. О свойствах теоретико-множественных операций над предполными классами трехзначной логики // Проблемы теорети ческой кибернетики. Материалы XVI Международной конференции (Нижний Новгород, 20-25 июня 2011 г.). Нижний Новгород: Изд-во Ни жегородского госуниверситета, 2011. C. 336-340.

28. Нагорный А. С. О критериальной таблице в P3 // Научная конферен ция „Ломоносовские чтения“, тезисы докладов (Москва, 14-23 ноября 2011 г.). М.: Изд-во МАКС Пресс, 2011, С. 27-29.

29. Нагорный А. С. О свойствах предполных классов в P3 // Известия высших учебных заведений. Поволжский регион. Физ.-мат. науки. Пен за: Изд-во Пензенского государственного университета, 2012, №2 (22), C. 16-24.

30. Нагорный А. С. О функциях четырехзначной логики, монотонных от носительно линейных порядков // Материалы XIII Межвузовского научно-практического семинара „Комбинаторные конфигурации и их применения“, (Кировоград, 13-14 апреля 2012 г.). Кировоград: Изд во Кировоградского национального технического университета, C. 107 109.

31. Нагорный А. С. О пересечениях классов монотонных функций мно гозначной логики // XI международный семинар „Дискретная мате матика и ее приложения“, (Москва, 18-23 июня 2012 г.). М.: Изд-во механико-математического ф-та МГУ, С. 207-209.

32. Нагорный А. С. О распределении трехзначных функций по предпол ным классам // Вестник Московского университета. Серия 15. Вычис лительная математика и кибернетика. 2012. № 3, С. 45-52.

33. Нагорный А. С. О некоторых пересечениях предполных классов мно гозначной логики, вложенных в классы C0 и C0,1,...,k3 // Материалы Международного научного семинара „Дискретная математика и ее при менение в экономико-математическом моделировании и информацион ных технологиях“ (Запорожье, 11-13 октября 2012 г.). С. 51-52;

34. Нагорный А. С. О некоторых пересечениях предполных классов много значной логики // Научная конференция „Тихоновские чтения“, тези сы докладов (Москва, 29-31 октября 2012 г.). М.: Изд-во МАКС Пресс, С. 46-47.

35. Нагорный А. С. О линейной монотонности некоторых пересечений предполных классов многозначной логики // Материалы XV Междуна родного научно-практического семинара „Комбинаторные конфигура ции и их применения“, (Кировоград, 12-13 апреля 2013 г.). Кировоград:

ПП „Ексклюзив-Систем“, C. 75-78.



 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.