Суперпозиции функций k-значной логики и их обобщений тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

сР-Г

ПАНТЕЛЕЕВ Владимир Иннокентьевич

СУПЕРПОЗИЦИИ ФУНКЦИЙ к-ЗНАЧНОЙ ЛОГИКИ И ИХ ОБОБЩЕНИЙ

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

2 2 ОКТ ?с«9

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

Красноярск — 2009

003480296

Работа выполнена на кафедре математической информатики Иркутского государственного педагогического университета

Научный консультант:

доктор физико-математических наук, профессор Перязев Николай Алексеевич

Официальные оппоненты:

доктор физико-математических наук, доцент Вороненко Андрей Анатольевич; доктор физико-математических наук, профессор Егорычев Георгий Петрович; доктор физико-математических наук, профессор Чагров Александр Васильевич

Ведущая организация:

Казанский государственный университет

Защита состоится 20 ноября 2009 г. в 15 часов на заседании диссертационного совета ДМ 212.099.18 в Сибирском федеральном университете по адресу: 660074, г. Красноярск, ул. Киренского, 26 корпус Ж, ауд. 1-15.

С диссертацией можно ознакомиться в библиотеке Сибирского федерального университета (г. Красноярск, ул. Киренского, 26).

Автореферат разослан 13 октября 2009 г.

Ученый секретарь диссертационного совета

Кириллов К.А.

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

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

В рамках дискретных функций одним из важнейших понятий является понятие функциональной системы — пары (Р, Q), где Р — множество функций, Q — множество операторов заданных на Р. Изучение функциональных систем связано с именами целого ряда выдающихся математиков. Среди них Дж. Буль, Г. Фреге, А. Пирс, М. Шеффер, П.С. Порецкий, Е. Пост, К. Шеннон, И.И. Жегалкин, А.И. Мальцев, В.М. Глушков, A.B. Кузнецов, C.B. Яблонский, О.Б. Лупанов.

Одной из распространенных функциональных систем является система, в которой элементами первого множества являются функции, определенные на множестве {0,1,..., к — 1} и принимающие значения из этого же множества, а в качестве оператора используется суперпозиция. Такие функции возникают как в самой теории функций, так и в многозначной логике (поэтому их часто называют функциями к-значной логики), в которой требуется для описания некоторых явлений употреблять высказывания, принимающие более двух значений.

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

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

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

— замыкания множества функций, представимых суперпозициями над заданным подмножеством;

— замкнутого класса — множества функций, совпадающего со своим замыканием;

— клона — замкнутого класса содержащего все проекции (селекторные функции);

— полного в замкнутом классе множества функций — множества функций, замыкание которого совпадает с рассматриваемым замкнутым классом.

Наиболее важные достижения здесь относятся к построению и анализу порождающих множеств, проблеме эффективных критериев полноты и описанию решетки замкнутых классов1.

Среди всех работ в этом направлении выделим работы Э. Поста2 и И. Розенберга3.

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

Среди всех возможных подмножеств выделим подмножества функций 2ш-значной логики, которые однозначно определяются по своим значениям на наборах, построенных из элементов множества {0,1,..., т — 1}. Такие подмножества, с одной стороны, возникают при изучении многозначных логик, решении уравнений над функциями, в технических системах, где рассматриваются схемы с неисправностями из некоторого возможного множества, а с другой стороны, являются есте-

1 Яблонский С. В. Функциональные построения в /с-значной логике // Труды матем. ин-та им. В. А. Стеклова. 1958. Т. 51. С. 2-142.

2Post Е. L. Two-valued iterative systems of mathematical logic. Annais of Math. Studies. Princeton: Univ. Press. 1941. Vol. 5. 122 p.

3Rosenberg 1. G. Uber die Verschiedenheit maximaler Klassen in Pt ;! Rev. Roumaine Math. Pures Appl. 1969. 14. P. 431-438.

ственньш развитием тео])1ш функций ¿-значной логики, в которой наряду со всюду определенными функциями рассматриваются и функции, определенные не на всех наборах и неопределенности могут быть различных видов. Один пз путей исследований здесь связан с тем, что неопределенности понимаются как некоторые подмножества множества {0,1,..., fc — 1}. Естественно, что такие функции можно назвать обобщениями функций fc-значной логики и, в зависимости от числа и вида неопределенностей, а также измененной суперпозиции, их называют частичными, недоопределенными, доопределяемыми, гипер-, мульти-, ультрафункциями4.

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

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

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

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

— оценка сложности представлений, исходя из определенных критериев сложности.

Одним из ответов на этот вопрос является возможность представления булевых функций дизъюнктивными и конъюнктивными нормальными формами и их аналоги для произвольного к > 2. Для к = 2 наиболее общая постановка задачи рассматривалась О. Б. Лупановым5.

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

4JIo Джукай. Теория полноты для частичных функций многозначной логики // Кибернетический сборник. Новая серия. Вып. 25. М.: Мир, 1988. С. 142-157. Тарасов В. В. Критерий полноты для не всюду определенных функций алгебры логики // Проблемы кибернетики. Вып. 30. М.: Наука, 1975. С. 319-325. Алексеев В. Б., Вороненко А. А. О некоторых замкнутых классах в частичной двузначной логике // Дискретная математика. 1994. Т. 6. Вып. 4. С. 58-79. Rosenberg I. G. Multiple-valued hyperstructures // Proceedings of 28th ISMVL (May 27-29 1998). IEEE, 1998. P. 326-333.

5Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципы локального кодирования // Проблемы кибернетики. 1965. № 4. С. 31-110.

дем называть полиномиальными формами. Многие известные полиномиальные представления булевых функции удалось описать с использованием операторного подхода0.

Естественной является задача распространения этих результатов на произвольные функций fc-значной логики.

Цели работы:

• описать логические системы, как область возникновения обобщений функций fc-значной логики;

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

• перенести операторный подход, развитый для специальных представлений булевых функций на функции fc-значной логики и в рамках этого подхода описать известные полиномиальные представления булевых функций с точки зрения полиномиальных представлений функций fc-значной логики.

Основные результаты и научная новизна. Автору лично принадлежат следующие основные научные результаты (в том числе и из совместных работ):

- построены исчисления табличного типа для семантики языка предикатов с обобщенной интерпретацией переменных и доказаны теоремы полноты и корректности;

- найдены некоторые специальные представления частичных гиперфункций и полные множества, что позволило дать описание всех максимальных частичных гиперклонов на 2-х элементном множестве и доказать в терминах предполных классов критерий функциональной полноты. Тем самым решена проблема, являющаяся объединением известных задач C.B. Яблонского о полноте для частичных и недоопре-деленных булевых функций;

6Избранные вопросы теории булевых функций: Монография / А. С. Валюк, С. Ф. Винокуров, А. И. Гайдуков и др. / под ред. С. Ф. Винокурова, Н. А. Пе-рязева. M : Физматлит, 2001. 192 с.

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

найдены необходимые и достаточные условия существования полиномиальных представлений частного вида;

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

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

- введена новая гиперзначная семантика при обобщенной интерпретации переменных языка предикатов (совместно с H.A. Перязевым);

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

- на основе операторного подхода найдены необходимые и достаточные условия существования полиномиальных представлений булевых функций в которых слагаемые являются бинарными термами (совместно с ученицей A.C. Зинченко);

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

Основные результаты диссертации являются новыми. Конфликт интересов с соавторами отсутствует.

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

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

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

Апробация работы. Результаты диссертации докладывались на: школе-семинаре по дискретной математике и ее приложениям (Москва, 1993); 4-й Международной конференции по прикладной логике (Иркутск, 1995); Международной конференции «Логика и приложения» (Новосибирск, 2000); 12-й Байкальской международной конференции «Методы оптимизации и их приложения» (Иркутск, 2001); Международной конференции «Компьютерные науки и информационные технологии» (Саратов, 2002); X, XIII, XIV и XV Международной конференции «Проблемы теоретической кибернетики» (Саратов, 1993; Казань, 2002; Пенза, 2005; Казань, 2008); Второй Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в вузе (Иркутск, 2003); Международной конференции «Алгебра, логика и кибернетика» (Иркутск, 2004); VI и VIII Международной конференции «Дискретные модели в теории управляющих систем» (Москва, 2004; 2009); Российской школе-семинаре «Синтаксис и семантика логических систем» (Иркутск, 2006; Владивосток, 2008); Международном российско-китайском семинаре «Алгебра и логика» (Иркутск, 2007); Шестых Смирновских чтениях по логике (Москва, 2009).

Исследования по теме диссертации выполнялись в рамках грантов РФФИ (00-01-00556 «Вопросы существования, нахождения и сложности представления булевых функций полиномиальными формами», 007-01-00240 «Недоопределенные частичные булевы функции»).

Публикации. По теме диссертации опубликовано 30 научных работ, отражающих основное содержание диссертации, в том числе семь работ в журналах, рекомендованных ВАК РФ [2, 6, 17, 18, 21, 22, 27] и одна коллективная монография [8].

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

Содержание работы

Во введении дается обоснование актуальности темы исследований.

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

В первом параграфе главы рассматривается функция истинностной оценки, которая приписывает каждому высказыванию (предикату) какой-нибудь (и только один) элемент некоторого множества истинностных значений. Если в качестве последнего взять двухэлементное множество {И, JI}, то получим классическую функцию истинности и классическую логику высказываний. В общем же случае речь идет о многозначной логике. Приводится пример 4-х значной логики высказываний, расматриваемой Дж. М. Данном7.

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

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

Результаты исследований, полученных диссертантом, приведены во 2-й, 3-й и 4-й главах.

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

В первом параграфе главы вводится обобщенная интерпретация переменных и связанная с ней частичная гиперзначная семантика. Пусть L — язык первого порядка с логическими символами V,-i, —>,V, 3 сигнатуры Е = {F,/5}, где F — множество функциональных символов; Р — множество предикатных символов. Определения терма, формулы сигнатуры Е, множества свободных переменных (FV) терма и формулы даются стандартным образом.

Пусть 21 = (А, Е) — алгебраическая система с носителем А сигнатуры Е, где, как обычно функциональным символам соответству-

7Dunn J.M. Intuitive semantics for first-degree entailment and coupled trees // Philosophial Studies. 1976. Vol 29. P. 149-168.

ют функции на Л (нульместным функциональным символам элементы Л), предикатным символам предикаты на А, при этом п-местные предикаты на множестве А мы будем рассматривать как функции р : А" —» В, (р £ Р), В — некоторое конечное множество, которое называется основным истинностным множеством.

Пусть Ф — формула и РУ(Ф) = {гп,..., хп} — множество ее свободных переменных, на котором зафиксирован некоторый порядок. Обобщенной интерпретацией назовем отображение

7 : РУ(Ф) -» 2а.

Будем говорить, что интерпретация 7' расширяет интерпретацию 7 за счет переменной у ф РУ(Ф) (обозначаем 7 <у 7'), если

7' : РУ(Ф) и {у} 2Л, ¡7'(у)| = 1 и У(х) = у(х) для всех х & РК(Ф).

Определим значение терма £ при обобщенной интерпретации 7 (обозначаем Щ-у).

ЕСЛИ Ь — Х{, то [£]7 = 7(Хг).

Если Ь = /(¿ь ...,£„), то [£]7 = {а | а = /(аь ...,ап),сч в [£*]7}.

Из этого определения сразу следует, что если для некоторого терма Ь] выполняется = 0, то тогда и [£]7 = 0.

Истинностное значение элементарной формулы ,..., 1п) при обобщенной интерпретации 7 будем понимать следующим образом:

*„)]7= и {Р(аь...,а„)}.

Если для некоторого и выполняется = 0, то [Р(£ 1, ...,£п)]7 = 0.

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

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

говоря об алгебраической системе сигнатуры Е с носителем Л, п-месгные предикаты на множестве А мы будем рассматривать как функции р : Ап —» {И, Л}.

Для элементарных формул при обобщенной интерпретации переменных в соответствии со значением терма истинностным значением может быть любое подмножество основного множества истинностных значений — {И}, {Л}, {И, Л}, 0. Обозначим эти подмножества как И, Л, Н, Б. Значение формулы Ф при интерпретации 7 (обозначаем [Ф]7) в соответствии с этими обозначениями определяется следующим образом:

а) если Ф = Р(Ь],..., ¿п), то значение [Ф]7 есть: И, если Р(а 1,...,ап) выполняется в 21 для всех щ € [¿г]-,; Л, если Р(а\,...,а„) не выполняется в 21 для всех сц € [¿¿]7; Н, если существуют ах,..., а„, щ € [¿¿]7 (г = 1, •••, п) такие, что Р{а\,..., ап) выполняется в 21 и существуют 61,..., Ъп, Ьг 6 [¿¿]7 (г = 1,...,п) такие, что Р(&1, ...,6„) не выполняется в 21; Б, если существует г {1, ...,п} такое, что [¿¿]7 = 0.

б) если Ф = Фа * Ф2(* е {&,->, V}), или Ф = ->Ф, то значение [Ф]7 определяется из следующих таблиц:

к И Л Н Б V И Л Н Б И Л Н Б Ф -.Ф

и И Л Н Б И И и И Б И и Л Н Б И Л

л Л л Л Б Л и Л Н Б Л и и И Б Л И

н н л н Б н и н Н Б н и н Н Б н н

Б Б Б Б Б Б Б Б Б Б Б Б Б Б Б Б Б

в) если Ф = \/жФ(х), то [Ф]7 есть:

И, если [Ф]у =И, для любой интерпретации 7', такой что 7 <х 7'; Л, если [Ф]у =Л, для некоторой интерпретации 7', такой что 7 <х 7', и не существует 7" (7 <х 7"): [Ф]у =Б;

Н, если [Ф]у =Н, для некоторой интерпретации 7', такой что 7 <х 7',

и не существует 7" (7 7"): [Ф]7" =Б или [Ф]7" =Л;

Б, если [Ф]у =Б, для некоторой интерпретации 7', такой что 7 <х 7'.

г) если Ф = ЭхФ(х), то [Ф]7 = [--1\/х-1Ф(а;)]7.

Отмеченными формулами сигнатуры £ будем называть выражения вида аФ, а 6 {И , =1, "тт, _и_} и Ф — формула сигнатуры £ (а назовем отметкой формулы Ф).

Коночное множество отмеченных формул будем называть секвенцией и обозначать Г.

С'оквенцшо Г назовем невыполнимой на алгебраической системе 51 сигнатуры Е, если для любой интерпретации у существует отмеченная формула в из Г (в = а-Ф), такая, что отметка о не совпадает с [Ф]7 при соответствии

И Л Н Б N Ц "тг л '

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

Секвенцию Г назовем семантически противоречивой, если она невыполнима на любой алгебраической системе сигнатуры Е.

В теореме 2.1 описаны некоторые условия, при которых секвенция противоречива.

Далее в параграфе построена система логического вывода табличного типа и доказана

Теорема 2.2 (об адекватности). СеквенцияТ семантически противоречива тогда и только тогда, когда Г выводима.

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

Пусть основное множество истинностных значений — это множество В = {1,2,..., к}, на котором задан линейный порядок 1 < 2 < ... < к и соответствующая циклическая подстановка: а — (123...к).

Рассматривая алгебраическую систему 21 с носителем А, под п-местным предикатом мы понимаем отображение р : Ап —> В.

На элементах множества 2В определим операции V и -п.

Пусть Вг € 2В и В2£ 2В, тогда

В1кВ2 = | Ь = тт{Ье ВХ,Ь2 е В2>;

В1 V В2 = {£ | £ = тах^иЬ)^! € Въ12 6 В2}\

—>£?1 = для некоторого элемента а из Вг}.

Если Ф = Р{1 ь то значение

[Ф]7 = и {Р(а,1,.., а„)}.

Для формулы Ф = 11'| *Ф_. (* е {&, V}) значение (Ф)-, = [Ф^-, *[ФзЬ,-аЬФ],= -[Ф]7.

Если Ф = \/:гФ(.г), то [Ф]^ есть множество И = {г/1,....сЦ}, причем (11 6 Б (I е {1,...,£}) тог,та н только тогда, когда найдется интерпретация -)■' : 7 <х 7' такая, что <7/ € [Ф]у и для любой интерпретации 7" : 7 <х 7" найдется е 6 [Ф]7" такой, что ¿1 < е.

Если Ф = ЗхФ(.-с), то [Ф]7 есть множество И = {(¿ь причем

¿1 <Е И (I € {1, ...,£}) тогда и только тогда, когда найдется интерпретация У : 7 <х У такая, что ф 6 [Ф]7' и для любой интерпретации 7" : 7 <х 7") найдется е е [Ф]7" такой, что е < с?;.

Для рассматриваемой 2д"-значной логики построено логическое исчисление табличного вида и доказана

Теорема 2.3 Секвенция Г семантически противоречива в 2к -значной логике тогда и только тогда, когда Г выводима.

В третьей главе рассматриваются обобщения функций ¿-значной логики: частичные гиперфункции и ультрафункции.

Пусть А — {0,1,..., к — 1} — конечное множество. Тогда га-местной функцией на А называется отображение / : Ап — > А\ п-местной частичной функцией на А — / : Ап —> А и 0; п-местной гиперфункцией на Л — / : Ап —> 2а \ 0; п-местной частичной гиперфункцией на Л — / : Ап —> 2а.

Суперпозиция /(/х(хь.. (хь ...£„)) определяет (частичную,

гипер-) функцию /г(жь..., а;п) следующим образом: для функций

/г(«1, ...ап) = ¡{}\{ах, ...а„),...,/т(аь ...а„)), для частичных функций

^ ^ , _ Г 0, если /Да), ...,а„) = 0 для некоторого г € {1, ...п};

для гиперфункций

Л(а1,...,а„)= У (1)

b,ьf,(al,■■■,a„)

для частичных гиперфункций

И (а 1.....«,,)

0. если /¿(а 1, ...,ап) = 0 для некоторого I 6 {1. ...//.}; У /(¿>ь - А), иначе .

.....а„)

(2)

Функции-проекции — это отображения е" : (а1,...,а„) а,.

Функцмп-гпперпроекции — это отображения е" : (а\, ...,ап) —> {а¿}.

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

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

(Частичные) гиперфункции, заданные на множестве А, с определенной для них суперпозицией фактически определяют подмножество функций 2/с-значной логики, заданных на множестве 2Л (при этом мы отождествляем одноэлементное подмножество с элементом этого множества). Функцию 2*:-значной логики, заданную на множестве 2Л, будем называть гиперфункцией, если она однозначно строятся по своим значениям на наборах из множества А в соответствии с (1) и частичной гиперфункцией — если в соответствии с (2).

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

Функцию 2л-значной логики, заданную на множестве 2А, будем называть ультрафункцией, если она однозначно строятся по своим значениям на наборах из множества А в соответствии с (3).

Пусть — я-местный предикат, заданный на множестве Р'. Будем говорить, что функция /(х-1, ...,£„), определенная на множестве Р', сохраняет предикат Л5, если для любых п наборов (ац,...,^]), ..., (а:1П, ...,аьп) принадлежащих предикату, набор

П /(&!,...,б„), если п /(&!,•••,Ы Ф 0;

(3)

принадлежит /?

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

В первом параграфе основными вопросами являются вопросы полноты частичных гиперфункций на 2-х элементном множестве, которые мы рассматриваем как функции 4-х значной логики.

Определим 4-х значные функции как функции на множестве Г' = {*, 0,1, —} при соответствии 0 <-» *, {0} <-> 0, {1} <-> 1, {0,1} <-> —.

Обозначим рассматриваемое подмножество через ■

Для произвольной функции / € Р2*~ зададим всюду определенные функции: /д — О-доопределение, /д — 1-доопределение, /д — (01)-доопределение, /д — (Ю)-доопределение следующим образом:

[О, если /(аи ...,а„) е {0,-,*};

РА{аъ...,ап) = Г

[1, если /(аь...,«п) € {1|.

Г1, если /(«!,...,а„) е {1,-,*};

[0, если/(аь ...,а„) 6 {0}. ч (О, если /(аь ...,а„) 6 {0, *};

1^1, если /(аь ...,а„) € {1, -}. . (О, если /(ах,..., ап) е {0, —};

если/(аь ...,ап) е {1,*}.

Функции х П у и х и у определяются естественным образом.

Теорема 3.1 Для любой f ё -Р*- справедливо разложение Теорема 3.2 Для любой / € справедливо разложение

/(*!,...,*•„) = (/>/£) п(/АиЯ).

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

Для функций /(хь...,£„), /гДжь ...,а;т), ..., М^ь..., ,тт) через /х/обозначим суперпозицию /(/гь ...,/г„) и пусть как обычно

а ] а;, если а = 1;

I .г, если а = 0.

Определим две функции

......'•») = (0-) о K¡(.rt......г„) и A¿(xi.....хп) = (-1) о тгД.ть ...,.т„),

f S.¡, если о = 0; где о — знак суперпозиции п пусть р{оц) = <

I A¿, если а, = 1.

Справедливы следующие представления частичных гиперфункций.

Теорема 3.3 (аналог скнф) Для любой функции / £ справедливо разложение

/(*!,...,хп) = & (xf V... VV.

(ai,...,а„)ЕЕ" \ >

Теорема 3.4 (аналог еднф) Для любой функции справедливо разложение

f{x},...,xn) = V •

(«1 ,...,а„)е£" V /

Определим 15 множеств, содержащих селекторные функции. I. Кг = {/(ц, ...,х„) | / = * или /(0, ...,0) е {0, -}}. И. К2 = {f{xi,...,xn) | / = * или /(1,1) е {1,-}}.

III. К3 = {f(xu...,xn) | /(0.....0) е {0,*}}.

IV. К4 - {¡(хъ...,хп) | /(1,...,1) € {1,*}}.

V. Кь = Р2 и {*}•

VI. К6 = Ро-

VII. К7 = {/I* € {/(0,...,0),/(1,...,1)}и [е].

VIII. К$ — класс функций, сохраняющих предикат

IX. Кд — класс функций, сохраняющих предикат 0010-1-****

Кд '101-1--01-*

X. К ¡о — класс функций, сохраняющих предикат

/0010---0-1*

1О\101-10-****

XI. Л Ii класс функции, 'охраняющих предикат

^ i (I ;....•• 0 ¡

11 V 1 0 1 -0* * * *

XII. К i2 — класс функций, сохраняющих предикат R\2. R12 содержит все наборы, кроме

/0 0 0111---0 1 1 - 1 0--0 ---0 \

01-01-0 1-010---1 010-- .

\ ***** * * * ^1000000001 1 1/

XIII. Ki 3 — класс функций, сохраняющих предикат R13. Л13 содержит все наборы, кроме

(***** * * * * 1 1 1111 1 1 о о о о \

10010 -1---0010-1 -1 ---lj.

1010-0-1-0-1001---1 — 1 — /

XIV. К\4 — класс функций, сохраняющих предикат R¡ 4. R14 не содержит наборы (а,/3,7 ф *)

/*00011110\ а 0 0 1 0 1 1 0 1 /301001011 V 7 1 О О О 0 1 1 1 /

и не содержит наборы ((^¿г^з^) такие, что í¡ ^ * (i € {1,2,3,4}) и среди ¿i, 5i, <5з,54 встречается а € Е и ß = — .

XV. Для набора (ai,...,an) € (F')n определим двойственный ему набор (ßi,--,ßn) следующим образом: если a¿ = 0, то ßz = 1; если оц = 1, то ßi = 0; в остальных случаях a¿ = ß¿ (i £ {1, ...,n}).

Ä'15 — класс функций, сохраняющих предикат ñis, не содержащий следующие наборы и двойственные к ним (a,ß,S ф *, v £ {1,—}, ах е {0,1,-}).

а ß

\5j

/0\ 1 1

W

\fj

ÍQ\ 1

w

1

о

V ^ /

п

о

w

о

и

/04

0

1

W

Теорема 3.5 Систем,а фующий а Р* • полна, тогда и только' тогда.. когда 01т не содержится целиком ни в одном </.•; клиссоа Кi — К[гу.

Второй параграф посвящен ультрафункциям на 2-х элементном множестве и основным результатом является критерий полноты.

Пусть Е = {0,1}, F = {0,1, -}. Как и выше функции / : Еп -> Е назовем всюду определенными (Po ~ множество всех всюду определенных булевых функций); / : Еп —> F — ультрафункциями (Р^ — множество всех ультрафункций).

Введем в рассмотрение 11 замкнутых классов, содержащих селекторные функции.

I. -Рз — класс всюду определенных функций.

II. Tq — класс функций, которые сохраняют нуль, т.е. на наборе из всех нулей равны 0.

III. Т{~ — класс функций, которые сохраняют единицу, т.е. на наборе из всех единиц равны 1.

IV. — класс функций, сохраняющих предикат

V. L — класс функций, сохраняющих предикат

VI. М —- класс функций, сохраняющих предикат

VII. К\ — класс функций, сохраняющих предикат

VIII. Ко — класс функций, сохраняющих предикат

IX. А"я класс функций сохраняющих предикат

( (I и О - О О О О 1 1 1 1 1 1---0 0---

Кл = | О 0---О 1 1 О 1 1 - - 1 1 1--1 1 о

(о-0--101101-1-1-1 1-01]

X. К4 - к.пясс функций сохраняющих предикат

/-0000 00 ----1\

К 4, -= I--010—00 0 — 11

\—010--00-01/

XI. Л~5 — класс, состоящий из всех функций существенно зависящих не более чем от одной переменной, а также из функций принимающих два значения, одно из которых есть "—".

Теорема 3.6 Система функций Р С Р2~ полна тогда и только тогда, когда она целиком не содержится пи в одном из классов Р2, То, Т\, Ь~, М~, К г -Къ.

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

Пусть А = {0,1,...,к - 1} и пусть Рк — множество всех функций определенных на множестве А, Р£ — множество всех частичных функций на множестве А, Р^ — множество всех гиперфункций на множестве А, — множество всех частичных гиперфункций на множестве А. Р£ — множество всех ультрафункций на множестве А и Р£~ — множество всех частичных ультрафункций на множестве А.

Определим на множестве А = {0,1,..., к — 1} к-местную частичную гиперфункцию 0к(хх, ...,хк):

!{0} и у если = 1;

к 1=2

и{°г}\{0}, если о>1

г=2

/.■-местную гнперфупкпмк

(I.

если ai = ... = щ. = 0;

I,

0A-(Q1, ...,а,) = U .U {<*}. если аг = 1;

к

и ы \ {0}, если сц ф 1 и U / 0,

и к-местную частичную функцию 0£(жь

Ofc(o;i,...,afc) = <

0, если ot\ = ... = afc = 0;

Qi, если ai = ... = «¿_i = ai+i = ... = — 0,

щ ф 0,г > 1; 0, иначе.

Теорема 3.7 Справедливы утверждения

1. Множество функций Pk U {Ofc} является полным в Pjl~ ■

2. Множество функций Pk U {0£} является полным в Р£.

3. Множество функций Pk U {ф^Г} является полным в Р^.

В качестве следствий из этой теоремы получены некоторые полные множества и решетка частичных гиперклонов, содержащих клон всех функций, описанная R. Doroslovacki, J. Pantovic, G. Vojvodic8.

Для ультрафункций доказана

Теорема 3.8 Частичными ультраклонами, содержащими Pk являются Рк, Рк U *, Pf, U *, Р£, и только.

Четвертая глава диссертации посвящена операторному подходу к полиномиальным представлениям функций fc-значной логики, при этом везде, за исключением параграфа 4.3.2 предполагается, что к — простое число.

Под операторами функций fc-значной логики мы будем понимать любое отображение q : F —> F, где F — мЕЮжество всех функций fc-значной логики

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

Doroslovacki R., Pantovic J.. Vojvodic G. One interval in the lattice of partial hyperclones // Czechoslovak Mathematical Journal. 2005. No. 55(130). P. 719-724.

Бч-дем [[( пользовать следующие обозначения: г вектор переменных. Ь вектор функции. Пусть / - функция к-¡ннчпоп логики, х и /1 что векторы переменных п функции одинаковой размерности а, соответственно, тогда через обозначим функцию, полученную из / заменой переменных из х па функции из Л, причем переменная а:, заменяется на г = 1,..., д.

Каждому натуральному п поставим в соответствие функцию

и наборы функций /гП1 (х, (х, г).

Класс — это класс операторов q, определяемых следующим образом: для произвольной функции /с-значной логики / ранга к имеем

причем среди переменных ¿^ не встречаются переменные функции /, наборы и ¿а не содержат общих элементов.

Если в предыдущем определении каждому п поставим в соответствие одну и ту же функцию /г., один и тот же набор функций Н\ (ж, г),..., ^.¡(а:, 5) и один и тот же набор переменных х, то полученный класс операторов назовем Е.

На классе Е определим произведение и операции /с-значной логики. Пусть в., д, ¿1,...,йп — операторы, д{х^,...,хп) — п-местная функция /г-значной логики, тогда произведение операторов (й о д) определяется следующим образом: (с/°д)(/) = а операция /с-значной логики

д над операторами й\,...,с1п дает оператор д(с1г,..., с1п):

Пусть д £ Е, к(у\, ...,уп) — п-местная функция /с-значной логики. Оператор называется /г-стабильным, если для любых функций /с-значной логики выполняется:

<?(Ч/ъ...,/п)) = Л(9(/1), -.,«(/„)).

В теоремах 4.1 и 4.2 показывается, что класс операторов Е замкнут относительно произведения и операций А--значной логики и получены необходимые и достаточные условия Л.-стабальностн оператора.

Совместное: Н. А. Перязевым про ведена классификация известных операторов булевых фцнкций.

В оставшихся параграфах главы рассматриваются полиномиальные представления функций fc-значной логики с с использованием трех специальных операторов класса Е: разностного - , подстановки — s"; п сдвига — р";. При этом, говоря о полиномиальных представлениях, мы будем иметь в виду сложение по mod к, коэффициенты перед слагаемыми являются элементами £'i. = {0,l,...,fc-l}.

Пусть а 6 Е^ и х^ = к — 1 — х + а. Заметим, что при к = 2 это

Определим оператор подстановки (б0), разностный оператор (с1а) и оператор сдвига (ра) для функций А:-значной логики, которые мы будем использовать далее в этой главе.

Пусть /(ад,... ,хп) — функция /с-значной логики, тогда

= /(£1,...,£¿-1,а,хт,...,£„) (О <а < к- 1); и-;Хг,--,Хп) - /(х1у...,х^1,х1а),хг+1,...,хгг) (0 < а < к-1); 1 > ""> •"*' ^тг) ~ /(^11 .--, ^г, х„),

(1 < а < к- 1).

Оператор, являющийся произведением операторов ...,

€ {з,р,(1}, сц е будем обозначать через 1:, члены произведения будем называть компонентами оператора, ti — основанием компоненты оператора, аг — ее показателем, а число п — длиной оператора.

Для ст = (сг^ ,..., <Х{Г) и х = {хгг,..., х— наборов констант и переменных, соответственно, оператор определяется как произведение г операторов ,..., Ьх]гг ■

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

Упорядоченное множество, состоящее из /с" операторов длины п называется пучком операторов и обозначается Т, число п называется размерностью этого пучка.

Назовем пучок операторов Т размерности п базисным, если существует такая функция д £ — множество всех функций позначной логики от п переменных), что любую функцию / £ Р" можно

обозначение соответствует принятому ха =

.а _

х, если а — О х, если а = 1.

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

Функцию /(.).1.... ,.тп) будем называть невырожденной, если

Л /С/?1,...,А») /Л е {о, 1,...,к - 1},

/31,..., А,

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

Пучок операторов О = (о'1 = о^1 ... о^* | (¿1,...,гп) £ О; € {р, ¿}) называется однородным.

Среди однородных пучков выделим два:

Р = (р" .. .р^Кгь . -. ,г„) е и = (с!'1 ... а'-'Кп,..., гп) € Е%).

Для функции д(х\,..., хп) и однородного пучка операторов О определим матрицу С[0(<7)] размерности кп х кп.

С = (д%) и д.- = о|з(г) (г = (гь ..., гп),^ = (¿ь...,./„)).

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

/{хи ..., хп) = ■ - -,хп) а01.._0п е

01-13«

Если О = Р, то матрица коэффициентов А вычисляется по формуле

где Р — вектор-столбец значений функции /(^ь... ,хп).

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

Для однородных пучков что условие является и достаточным, а в общем случае, как показала А.С.Зинченко. требуется невырожденность специальным образом определенной матрицы пучка9.

Пусть P\{f) — полином, представляющий функцию /. Сложностью L{P\{f)} полинома Pt{f) будем называть число слагаемых в нём. Число

LKU)= min L(Pt(/)) Л(/)ел

назовём сложностью функции / в классе полиномов К. Слолшостью класса функций S в классе полиномов К назовем число

LK{S) = maxLK(f).

Можно выделить два класса полиномов: К = К^ — линейные комбинации образов функций из базиса G по операторам из Т и К -= Kj — линейные комбинации образов невырожденной функции д по пучку из класса пучков Т.

Среди всевозможных базисов рассмотрим два:

Gi = {х? • ... • ... -а^-1} и

G2 = {ph .. ... ,xn)\{ii,... ,гп) е ££},

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

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

Н. А. Перязев нашел точное значение функции Шеннона для класса булевых функций и класса симметрических функций в поляризованных полиномах Жегалкина (форм Рида-Маллера), а С. Н. Селезнева получила оценки сложности функции Шеннона для поляризованных полиномов при к > 3.

В следующей теореме содержится нижняя оценка класса D и базиса G\ (получена совместно с А. С. Зинченко).

9Зпнченко А. С., Пантелеев В. И. Полиномиальные операторные представления функций А'-значной логики // Дискретный анализ и исследование операций. Сер. 1. 2000. Т. 13. № 3. С. 13-26.

Теорема 4.4 При. любим п I) справедливо неравенство

(к 4- 1 \"

LK^('i) > {-i-) .

В третьем параграфе этой главы рассматриваются полиномиальные представления вида

f(xu...,xg)= ^^...^[gH/i; lflr2(/|=,.. ■ /!;)• - -))],

à 1 à 2 • --CTq

(4)

где gi(yi,y2),.. • ,gq-i(yi, ij2) — бинарные функции.

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

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

В третьем параграфе четвертой главы дается ответ на этот вопрос.

Теорема 4.5 Для любой булевой функции fix,у) существует разложение

f(x,y) = Y^aà,î(4f{x,y) Vs£/(z,y)).

Теорема 4.6 Для любой булевой функции fix,у) имеют место разложения

f(x, у) = £ аа^ЛФту) - spfix,y))

(7i ¡J 2

U

fix,у) = <*w{sïf(ï,v) s£2/(i,y))-

сг 1 <72

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

'"Винокуров С. Ф., Перязев II. А. Разложение булевых функций на сумму произведений подфункций /,/ Дискретная математика. 1993. Т. 5. № 3. С. 102-104.

Теорема 4.7 Ра.ш»жтш (4) при q = 2 имеет место для любой палевой функции то-/да и тол.ъко тогда, когда сд € {V, •,<—, —>}.

Теоремы 4.6 и 4.7 получены совместно с А. С. Зпнченко. Утверждение о том. что любую булеву функцию можно представить суммой произведений собственных подфункций, удалось распространить на функции А:-зна.чной логики не только при простом к, но и при произвольном к. Первым шагом в этом направлении оказался наш результат о том, что при простом к > 2 любую функцию к-значной логики можно представить суммой произведений собственных подфункций (теорема 4.8).

Теорема 4.9 Для любой функции k-значиой логики f(ü, v) имеет место разложение

f(ü,v)= aaíslf-slf, (añreEk)

íe^'.fee^1

тогда и только тогда, когда к = р\ ■ Рг ' — ' рт> где Pi,P2, •■•■>Рт ~~ попарно различные простые числа (т > 1).

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

Теорема 4.10 Для любого к и любого t (t > 2) найдется функция f(xi,...,xn) иразбиение {rcj,... ,хп} =üiU...Uüí при котором f нельзя представить в виде

aieí;^'.....^^1

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

Теорема 4.11 Произвольную п-местную функцию f(x, у) можно представить в полиномиальной форме следующего вида

f(x !,...,£„) = • ( Y^ f^i, •••.т-т))"1 -Pi9(x) -4/(£>У)>

a,0 Ti...T„,

где g{x), (m < n) — rn-местная невырожденная, функция, aáp — элемент. стоящий на (á,(3) месте в матрице (G[P(g(x\,..., хп))})к~1.

Если обозначить

ат, = («Т1о...с/7-1д. -1). ...ат, = (аГ|о...«т,А-1), .....*„) =

то справедлива

Теорема 4.12 Для любой функции . •. ,хп) существует полиномиальное разложение вида

/= ® •■•®ат. ■ Р(Хг+ъ-,хп) ^Тх\д{хх) ■ ... -р£<7(а;;),

Т1... т,

где — одноместная невырожденная функция, ® — кропекерово произведение матриц.

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

Четвертый параграф этой главы посвящен полиномиальным представлениям полилинейных функций.

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

Определим для функции д(х\, ...,хп,у), зависящей от п + 1 переменной, матрицу размерности 2п х 2™, строки и столбцы которой занумеруем двоичными наборами т и а соответственно, следующим образом: С = (дт-а), гДе <7™ = Цт"), тг,с^ е {0,1} и

/г(жь ...,ж„) = (к - 1) ■ д(хг, ...,хп,0) + д(хг,...,хп, 1).

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

Теорема 4.15 Любая полчшшейтья функция }'{х\, лож-еп.и.е вида.

х.п) -имеет '¡юз-

/(■П.....*„) = ^^^......~ 1)

та

по полилинейной функции д(х!.....хп,-у). т. < € {0,1} тогда,

и только тогда, когда функция д[ху, ...,хп,у) имеет, степень равную т + 1. Матрица коэффициентов А есть С?*-1,

7 = (Л-1)1-т-Г1- £ аТ1...Т,пд{х\\...,хТ-, 0) + 1,

Т1...Т,,,

(1, если набор {т1,...,тт) содержит четное число 1]

к — 1, в противном случае. Константа I зависит от выбора функции д(х\,..., хп,у).

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

1. Пантелеев В.И. Полиномиальные канонические формы /г-зпачных функций// Методы и системы технической диагностики/ Материалы 10 Международной конференции по проблемам теоретической кибернетики. Саратов, 1993. С. 134.

2. Пантелеев В. И. Полиномиальные разложения /с-значшлх функций по невырожденным функциям // Математические заметки. 1994. Т. 55. № 1. С. 144-149.

3. Пантелеев В. И. Полиномиальные разложения полилинейных функций к-значной логики. Иркутск: Изд-во Иркут. ун-та, 1994. 23 с.

4. Пантелеев В. И. О полиномиальных разложениях полилинейных конечнозначных функций. 4-я межд. конф. по прикладной логике (Иркутск, 15-18 июня, 1995г.) Материалы. Иркутск, 1995. С. 59.

5. Пантелеев В. И., Перязев Н. А. Обобщенная интерпретация переменных и 8-значная логика //Природные ресурсы, экология и социальная среда Прибайкалья. Сб. науч. трудов. Т.Ш. Иркутск: Изд-во Иркут. ун-та, 1995. С. 268-271.

6. Пантелеев В. И. Полиномиальные разложения /с-значных функций по операторам дифференцирования и нормализации // Известия высших учебных заведений. Математика. 1998. № 1. С. 82-85.

7. Пантелеев В. И., Перязев Н. А. Об операторах булевых функций < Синтез н сложность управляющих систем: Материалы XI Межгосударственной школы-семинара (Нижний Новгород, '20-25 нояб. 2000 г.). М.: Изд-во Центра прикладных исследований МГУ, 2001. Часть 2. С. 141-146.

8. Избранные вопросы теории булевых функций: Монография / А. С. Балюк, А. И. Гайдуков, В. И. Пантелеев и др. / под ред. С. Ф. Винокурова, Н. А. Перязева. М.: Физматлит, 2001. 192 с.

9. Винокуров С. Ф., Пантелеев В. И. Полиномиальное представление булевых функций с использованием только остаточных функций // Труды XII Байкальской международной конференции. Иркутск: Из-во Иркутского ун-та, 2001. Т. 5. С. 27-31.

10. Зинченко А. С., Пантелеев В. И. Специальные полиномиальные представления булевых функций // Компьютерные науки и информационные технологии: Материалы международной конференции (Саратов, 2002 г.). Саратов: Изд-во Сарат. ун-та, 2002. С. 28-29.

11. Пантелеев В. И. Представление булевых функций в виде суммы импликаций остаточных функций// Проблемы теоретической кибернети-ки. Тезисы докладов XIII Международной конференции. Ч II. М.: Изд-во центра прикладных исследований при механико-математическом ф-те МГУ, 2002. С. 140.

12. Пантелеев В. И. Пропозициональные логики при обобщенной ин-тепретации переменных // Труды Второй Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в вузе. Иркутск: Изд-во Иркут. гос. пед. ун-та, 2003. С. 82-83.

13. Зинченко А. С., Пантелеев В. И. О представлении функций конеч-нозначной логики пучками операторов // Алгебра, логика и кибернетика: Материалы Международной конференции, посвященной 75-летию со дня рождения профессора А. И. Кокорина (Иркутск, 25-28 авг. 2004 г.). Иркутск: Изд-во Иркут. гос. пед. ун-та, 2004. С. 139-142.

14. Зинченко А. С., Пантелеев В. И. Полиномиальные операторные представления функций /с-значной логики // Дискретные модели в теории управляющих систем: Труды VI Международной конференции, посвященной 80-летию со дня рождения C.B. Яблонского

(Москва, 711 дек. 2004 г.). М.: Издательский отдел Факультета ВМпК МГУ им. М. В. Ломоносова. 2004. С. 31 32.

15. Зпнченко А. С., Пантелеев В. И. О нижней оценке сложности операторных полиномиальных форм для функций /с-значноп логики /'/ Проблемы теоретической кибернетики: Материалы XIV Международной конференции, посвященной 80-летию со дня рождения С. В. Яблонского (Пенза, 23-28 мая 2005 г.) / под ред. О. Б. Лупанова. М.: Изд-во механико-математического факультета МГУ, 2005. С. 51.

16. Пантелеев В. И., Перязев Н. А. Разложение функций /с-значной логики в сумму произведений собственных подфункций // Проблемы теоретической кибернетики: Тезисы докладов XIV Международной конференции, посвященной 80-летию со дня рождения С. В. Яблонского (Пенза, 23-28 мая 2005 г.) / под редакцией О. Б. Лупанова. М.: Изд-во механико-математического факультета МГУ, 2005. С. 114.

17. Пантелеев В. И., Перязев Н. А. Логика предикатов при обобщенной интерпретации переменных // Вестник Бурятского университета. Серия 13: Математика и информатика. Вып. 2. Улан-Удэ: Изд-во Бурятского госуниверситета, 2005. С. 39-44.

18. Зинченко А. С., Пантелеев В. И. Полиномиальные операторные представления функций /с-значной логики // Дискретный анализ и исследование операций. Сер. 1. 2006. Т. 13. № 3. С. 13-26.

19. Пантелеев В. И. О недоопределенных булевых функциях// Синтаксис и семантика логических систем: Материалы российской школы-семинара. Иркутск: изд-во ГОУ ВПО ИГПУ, 2006. С. 78-79.

20. Пантелеев В. И., Перязев Н. А. Недоопределенные булевы функции и булевы уравнения // Дискретные модели в теории управляющих систем: Труды VII Международной конференции. М.: МАКС Пресс, 2006. С. 262-265.

21. Зинченко А. С., Пантелеев В. И. Бинарные термы в полиномиальных представлениях булевых функций / / Математические заметки. 2007. Т. 81. Вып. 2. С. 217-225.

22. Пантелеев В. И., Перязев Н. А. О представлении функций /,-значной логики суммой произведений остаточных подфункций // Дискретная математика. 2007. Т. 19. Вып. 2. С. 94-100.

23. Пантелеев В. И. О предполных классах недоопределенных функций алгебры логики // Алгебра и логика: Материалы международного российско-китайского семинара (Иркутск, 6-11 авг. 2007 г.). Иркутск: Изд-во Иркут. гос.пед. ун-та, 2007. С. 81-82.

24. Пантелеев В. И., Перязев Н. А. Конечнозначная логика предикатов при обобщенной интерпретации переменных // Современная логика: проблемы теории, истории и применения в науке: Материалы X Общероссийской научной конференции (Санкт-Петербург, 26-28 июня 2008г). СПб., 2008. С. 299-301.

25. Пантелеев В. И. О предполных классах недоопределенных частичных булевых функций // Проблемы теоретической кибернетики: Тезисы докладов XV международной конференции (Казань, 2-7 июня 2008 г.). Казань: Отечество, 2008. С. 91.

26. Пантелеев В. И. Клоны недоопределенных частичных булевых функций // Синтаксис и семантика логических систем: Материалы Российской школы-семинара, посвященной 60-летию со дня рождения профессора Ю. И. Шишмарева (Владивосток, 25-29 авг. 2008 г.). Владивосток: изд-во Дальнаука, 2008. С. 42-43.

27. Пантелеев В.И. Критерий полноты для доопределяемых булевых функций // Вестник Самарского государственного университета. Естественнонаучная серия. № 2 (68). 2009. С.60-79.

28. Пантелеев В. И., Перязев Н. А. Логика предикатов при обобщенной интерпретации переменных. Шестые Смирновские чтения: Материалы Междунар. науч. конф. (Москва, 17-19 июня 2009). М.: Современные тетради, 2009. С. 32-34.

29. Пантелеев В.И. Частичные гиперфункции на двухэлементном множестве// Дискретная математика и информатика. Вып. 20. Иркутск: Изд-во Ирк. гос. пед. ун-та., 2009. 28 с.

30. Пантелеев В.И. Максимальные клоны недоопределенных частичных булевых функций. Дискретные модели в теории управляющих систем: Труды VIII Международной конференции. М.: МАКС Пресс, 2009. С. 230-233.

Пантелеев Владимир Иннокентьевич Суперпозиции функций к-значной логики и их обобщений

Автореф. дисс. на соискание ученой степени доктора физ.-мат. наук Подписано в печать 10.10.2009. Заказ № 103 Формат 60x84 1/16. Усл. печ. л. 1,8. Тираж 100 экз. Отпечатано в изд-ве Иркутского государственного университета 664003, Иркутск, б. Гагарина, 36 тел. (3952)24-14-36

Введение

1 Основные понятия и результаты

§ 1.1 Истинностные значения и многозначные логики.

§ 1.2 Функции А;-значной логики и их обобщения.

§ 1.3 Полиномиальные представления функций fc-значной логики

2 Логика с обобщенной интерпретацией переменных

§ 2.1 Обобщенная интерпретация переменных и частичная гиперзначная семантика.

§ 2.2 Обобщенная интерпретация переменных и 4-х значная логика

§ 2.3 2/с-значная логика и обобщенная интерпертация переменных

3 Гипер- и ультрафункции

§ 3.1 Частичные гиперфункции на двухэлементом множестве

3.1.1 Примеры полных множеств.

3.1.2 Замкнутые классы.

3.1.3 Вспомогательные леммы.

3.1.4 Критерий полноты.

§ 3.2 Ультрафункции на двухэлементном множестве.

3.2.1 Замкнутые классы.

3.2.2 Вспомогательные результаты.

3.2.3 Критерий полноты.

§ 3.3 Полные множества частичных гипер- и ультрафункций на произвольном множестве.

4 Операторные представления функций fc-значной логики

§ 4.1 Об операторах функций /с-значной логики

4.1.1 Основные понятия и определения

4.1.2 Операторы булевых функций.

4.1.3 Некоторые операторы функций /с-значной логики

§ 4.2 Разностный оператор и оператор сдвига в полиномиальных представлениях функций /с-значной логики.

4.2.1 Существование полиномиальных представлений

4.2.2 Некоторые оценки сложности.

§ 4.3 Оператор подстановки в полиномиальных представлениях

4.3.1 Разложения, применимые к произвольным булевым функциям.

4.3.2 Разложения функций fc-значной логики.

4.3.3 Разложения с оператором сдвига.

§ 4.4 Операторы подстановки и сдвига в разложениях полилинейных функций.

Понятие функции в силу своей фундаментальности занимает одно из самых важных положений в математике. Математические модели, описанные на языке функций, находят широкое применение в различных областях человеческой деятельности. В последнее время интенсивно развивающейся областью теории функций является класс дискретных функций, так как аппарат таких функций используется при проектировании вычислительных устройств [4, 12, 14], кодировании информации [53], передаче данных [17], в диагностике и контроле схем, в теории конечных автоматов, в теории игр, в языках программирования, при математическом моделировании природных процессов и др.

В рамках дискретных функций одним из важнейших понятий является понятие функциональной системы — пары (Р, Q), где Р — множество функций, Q — множество операторов, заданных на Р. Изучение функциональных систем связано с именами целого ряда выдающихся математиков. Среди них Дж. Буль, Г. Фреге, А. Пирс, М. Шеффер, П.С. Порецкий, Е. Пост, К. Шеннон, И.И. Жегалкин, А.И. Мальцев, В.М. Глушков, А.В. Кузнецов, С.В. Яблонский, О.Б. Лупанов.

Одной из распространенных функциональных систем является система, в которой рассматриваются функции, определенные на множестве {0,1,., к — 1} и принимающие значения из этого же множества, а в качестве оператора используется суперпозиция. Такие функции возникают как в самой теории функций, так и в многозначной логике (поэтому их часто называют функциями &-значной логики), в которой требуется для описания некоторых явлений употреблять высказывания, принимающие более двух значений, в частности для описания широко известной проблемы «будущей случайности». В девятой главе трактата «Об истолковании» Аристотель ставит следующую проблему: верно ли, что относительно единичного и вместе с тем будущего события всякое утверждение или отрицание истинно или ложно? Данная проблема оказалась продуктивной для развития логики: распространенным является мнение, что именно многочисленные попытки логической реконструкции подхода Аристотеля к решению проблемы будущей случайности привели к появлению многозначных логик, которые связываются, прежде всего, с именем Я. Лукасевича [45].

Функциональным системам с операцией суперпозиции посвящена книга [57].

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

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

В рамках второго направления основным объектом исследований являются подмножества вместе с операцией суперпозиции и соответствующие им понятия: замыкание — множество функций, представимых суперпозициями над заданным подмножеством; замкнутого класса — множества функций, совпадающего со своим замыканием; клона — замкнутого класса содержащего все проекции (селекторные функции); полного в замкнутом классе множества — множества функций, замыкание которого совпадает с рассматриваемым замкнутым классом.

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

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

Среди всех возможных подмножеств выделим подмножества функций 2т-значной логики, которые однозначно определяются по своим значениям на наборах, построенных из элементов множества {0,1,., m— 1}. Такие подмножества, с одной стороны, возникают при изучении многозначных логик, решении уравнений над функциями, в технических системах, где рассматриваются схемы с неисправностями из некоторого возможного множества, а с другой стороны, являются естественным развитием теории функций £;-значной логики, в которой наряду со всюду определенными функциями рассматриваются и функции, определенные не на всех наборах и неопределенности могут быть различных видов. Один из путей исследований здесь связан с тем, что неопределенности понимаются как некоторые подмножества множества {0,1, — 1}. Естественно, что такие функции можно назвать обобщениями функций fc-значной логики и, в зависимости от числа и вида неопределенностей, а также измененной суперпозиции, их называют частичными, недоопре-деленными, доопределяемыми, гипер-, мульти-, ультрафункциями.

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

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

В диссертации исследуются перечисленные выше проблемы для рас- -смотренных направлений исследований:

• в направлении, связанном с логическими исчислениями: логические системы как область возникновения обобщений функций &-значной логики;

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

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

Автору лично принадлежат следующие основные научные результаты для перечисленных направлений по четырем из отмеченных выше проблем (в том числе и из совместных работ):

- построены исчисления табличного типа для семантики языка предикатов с обобщенной интерпретацией переменных и доказаны теоремы полноты и корректности;

- найдены некоторые специальные представления частичных гиперфункций и полные множества, что позволило дать описание всех максимальных частичных гиперклонов на 2-х элементном множестве и доказать в терминах предполных классов критерий функциональной полноты. Тем самым решена проблема, являющаяся объединением известных задач С.В. Яблонского о полноте для частичных и неопределенных булевых функций;

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

- найдены необходимые и достаточные условия существования полиномиальных представлений частного вида;

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

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

- введена новая гиперзиачная семантика при обобщенной интерпретации переменных языка предикатов (совместно с Н.А. Перязевым);

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

- на основе операторного подхода найдены необходимые и достаточные условия существования полиномиальных представлений булевых функций в которых слагаемые являются бинарными термами (совместно с ученицей А.С. Зинченко);

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

Конфликт интересов с соавторами отсутствует.

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

Параграфы разбиваются на пункты.

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

Вторая глава посвящена описанию логических систем с обобщенной интерпретацией переменных. Как примеры таких систем, приводятся 4-х значная и 2fc-3Ha4Han логики, для которых построены исчисления табличного вида и доказаны теоремы адекватности.

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

Четвертая глава посвящена специальным полиномиальным представлениям функций /с-значной логики.

Результаты диссертации докладывались на школе-семинаре по дискретной математике и ее приложениям (Москва, 1993); 4-й Международной конференции по прикладной логике (Иркутск, 1995); Международной конференции «Логика и приложения» (Новосибирск, 2000); 12-й Байкальской международной конференции «Методы оптимизации и их приложения» (Иркутск, 2001); Международной конференции «Компьютерные науки и информационные технологии» (Саратов, 2002); X, XIII, XIV и XV Международной конференции «Проблемы теоретической кибернетики» (Саратов, 1993; Казань, 2002; Пенза, 2005; Казань, 2008); Второй Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в вузе (Иркутск, 2003); Международной конференции «Алгебра, логика и кибернетика» (Иркутск, 2004); VI и VIII Международной конференции «Дискретные модели в теории управляющих систем» (Москва, 2004; 2009); Российской школе-семинаре «Синтаксис и семантика логических систем» (Иркутск, 2006; Владивосток,

2008); Международном российско-китайском семинаре «Алгебра и логика» (Иркутск, 2007); Шестых Смирновских чтениях по логике (Москва,

2009).

Исследования по теме диссертации выполнялись в рамках грантов РФФИ (00-01-00556 «Вопросы существования, нахождения и сложности представления булевых функций полиномиальными формами», 007-0100240 «Недоопределенные частичные булевы функции»).

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

По теме диссертации опубликовано 30 работ, в том числе 1 коллективная монография [159] и 7 работ из списка ВАК [153, 157, 168, 169, 172, 173, 178].

1. Авгуль Л. Б., Супрун В. П. Обобщенные полиномиальные разложения симметрических булевых функций // Кибернетика. 1991. № 1. С. 122-125.

2. Алексеев В. В., Вороненко А. А. О некоторых замкнутых классах в частичной двузначной логике // Дискретная математика. 1994. Т. 6. Вып. 4. С. 58-79.

3. Алексеев В. Б. О некоторых замкнутых классах частичных многозначных самодвойственных функций // Проблемы теоретической кибернетики: тезисы докладов XV международной конференции (Казань, 2-7 июня 2008 г.). Казань: Отечество, 2008. С. 5.

4. Артюхов В. Л., Копейкин В. Л., Шалыто А. А. Настраиваемые модули для управляющих логических устройств. Ленинград: Энергоиз-дат, 1981. 166 с.

5. Авсаркисян Г. С. Представление булевых функций суммой по модулю 2 импликацией аргументов // Автоматика и вычислительная техника. 1977. № 1. С. 8-11.

6. Авсаркисян Г. С. Обобщенные полиномиальные формы булевых функций и синтез многовыходных логических схем // Автоматика и Телемеханика. 1983. № 11. С. 111-119.

7. Авсаркисян Г. С. Полиномиальные формы частичных функций к-значной логики // Кибернетика. 1985. № 4. С. 32-36.

8. Авсаркисян Г. С. Квазиполиномиальные формы функций fc-значной логики // Кибернетика. 1988. № 3. С. 104-105.

9. Айзенберг Н. Н., Рабинович 3. JL Некоторые классы функционально полных систем операций и канонические формы представления функций многозначной логики // Кибернетика. 1965. № 2. С. 37-45.

10. Айзенберг Н. Н., Семйон И. В., Циткин А. И. Мощность класса функций fc-значной логики от п переменных, представимых полиномами по модулю к // Многоустойчивые элементы и их применение. М.: Сов.радио, 1971. С. 78-83.

11. Айзенберг Н. Н., Семйон И. В. Некоторые критерии представимости функций fc-значной логики полиномами по модулю к // Многоустойчивые элементы и их применение. М.: Сов.радио, 1971. С. 84-88.

12. Ачасова С. М. Алгоритмы синтеза автоматов на программируемых матрицах. М.: Радио и связь, 1987. 135 с.

13. Балюк А. С., Винокуров С. Ф. Функция Шеннона для некоторых классов операторных полиномиальных форм // Оптимизация, управление, интеллект. 2000. Вып 5. С. 167-180.

14. Баранова С. И., Скляров В. А. Цифровые устройства на программируемых СБИС с матричной структурой. М.: Радио и связь, 1986. 270 с.

15. Белнап Н., Стил Т. Логика вопросов и ответов: Пер. с англ. М.: Прогресс, 1981. 288 с.

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

17. Бохманн Д., Постхоф X. Двоичные динамические системы. М.: Энергоатомиздат, 1986. 401 с.

18. Бочвар Д. А. Об одном трехзначном исчислении и его применении к анализу парадоксов классического расширенного функционального исчисления // Матем. сб. 1934. Вып. 4. С. 281-308.

19. Винокуров С. Ф. Смешанные операторы в булевых функциях и их свойства // Иркутский Университет. Серия: Дискретная математика и информатика. Вып. 12. Иркутск: Из-во Иркутского ун-та, 2000. 36 с.

20. Винокуров С. Ф., Перязев Н. А. Полиномиальные разложения булевых функций по невырожденным функциям // Алгебра и логика. 1991. Т. 30. № 6. С. 631-637.

21. Винокуров С. Ф. Полиномиальные операторные разложения и канонические формы булевых функций. Иркутск: Из-во Иркутского унта, 1992. 26 с.

22. Винокуров С. Ф., Перязев Н. А. Представление булевых функций полиномиальными формами // Кибернетика и системный анализ. 1992. № 3. С. 175-179.

23. Винокуров С. Ф., Перязев Н. А. Разложение булевых функций на сумму произведений подфункций // Дискретная математика. 1993. Т. 5. № 3. С. 102-104.

24. Винокуров С. Ф., Перязев Н. А. Полиномиальные разложения булевых функций // Кибернетика и системный анализ. 1993. № 6. С. 3447.

25. Винокуров С. Ф., Перязев Н. А. Полиномиальная декомпозиция булевых функций // Математические заметки. 1993. Т. 52, № 2. С. 2529.

26. Винокуров С. Ф., Перязев Н. А. Полиномиальная декомпозиция булевых функций по образам однородных операторов от невырожденных функций // Изв. вузов. Матем. 1996. № 1. С. 17-21.

27. Винокуров С. Ф., Перязев Н. А. Полиномиальные разложения булевых функций по образам неоднородных операторов // Кибернетика и системный анализ. 2000. № 4. С. 40-55.

28. Винокуров С. Ф. Разложения булевых функций по собственным операторным образам и термам над бинарными функциями // Оптимизация, управление, интеллект. 2000. Вып. 4. С. 167-180.

29. Гаврилов Г. П. О надструктуре класса полиномов в многозначных логиках // Дискретная математика. 1996. Т. 8. Вып. 3. С. 90-97.

30. Гаврилов Г. П. О замкнутых классах .многозначной логики, содержащих класс полиномов // Дискретная математика. 1997. Т. 9. Вып. 2. С. 12-23.

31. Гельфонд А. О. Исчисление конечных разностей. М: Физматлит, 1959. 400 с.

32. Дюбуа Д., Град А. Теория возможностей. Приложения к представлению знаний в информатике. М.: Радио и связь, 1990. 287 с.

33. Жегалкин И. И. Арифметизация символической логики // Мат. сборник. 1928. Т. 35. С. 311-373.

34. Жегалкин И. И. Арифметизация символической логики // Мат. сборник. 1929. Т. 36. С. 305-338.

35. Зинченко А. С. О базисных пучках операторов булевых функций // Вестник Иркутского университета. Специальный выпуск: Материалы научно-теоретической конференции молодых ученых, посвященной 85-летию ИГУ. Иркутск: Иркут. ун-т, 2003. С. 76-77.

36. Зинченко А. С. Полиномиальные представления булевых функций по коимпликации // Вестник БГУ. Серия 13: Математика и информатика. 2006. Вып. 3. С. 23-28.

37. Зинченко А. С. Полиномиальные операторные представления ко-нечнозначных функций: дис. . канд. физ.-мат. наук. Красноярск, 2006. 97 с.

38. Карпенко А. С. Многозначные логики. В сер. «Логика и компьютер». Вып. 4. М.: Наука, 1997.

39. Кириченко К. Д. Верхняя оценка сложности полиномиальных нормальных форм булевых функций // Дискретная математика. 2005. Т. 17. № 3. С. 80-88.

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

41. Кузнецов А. В. Алгебра логики и ее обобщения // Яновская С. А. Математическая логика и основания математики. Математика в СССР за сорок лет. Т. 1. М.: Физматгиз, 1959. - С. 13-120.

42. Лукасевич Я. Аристотелевская силлогистика с точки зрения современной формальной логики. Биробиджан: ИП «ТРИВИУМ», 2000. 312 с.

43. Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципы локального кодирования // Проблемы кибернетики. 1965. № 4. С. 31-110.

44. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во Моск. ун-та, 1984. 137 с.

45. Ло Джукай. Максимальные замкнутые классы в множестве частичных функций многозначной логики // Кибернетический сборник. Новая серия. Вып. 25. М.: Мир, 1988. С. 131-141.

46. Ло Джукай. Теория полноты для частичных функций многозначной логики // Кибернетический сборник. Новая серия. Вып. 25. М.: Мир, 1988. С. 142-157.

47. Мальцев А. И. Итеративные алгебры и многообразия Поста // Алгебра и логика. 1966. Т. 5. № 2. С. 5-24.

48. Мальцев А. И. Итеративные алгебры Поста. Новосибирск: Изд-во НГУ, 1976. 100 с.

49. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Связь, 1979. 477 с.

50. Мартынюк. Исследование некоторых классов в многозначных логиках// Проблемы кибернетики. М.: Наука, 1960 ТЗ. С.49-60

51. Марченков С. С. Замкнутые классы булевых функций. М.: Физмат-лит, 2000. 128 с.

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

53. Марченков С. С. Функциональные системы с операцией суперпозиции. М.: Физматлит, 2004. 104 с.

54. Мещанинов Д. Г. Некоторые условия представления функций из Рк полиномами по модулю к // ДАН СССР. 1988. Т. 299. № 1. С. 50-53.

55. Мещанинов Д. Г. Перестановочные представления функций к-значной логики / / Вестн. МГУ / Вычисл. мат. и ки-берн. 1988. № 3. С. 61-66.

56. Мещанинов Д. Г. О вторых р-разностях функций £>а-значной логики // Дискретная математика. 1992. Т. 4. № 4. С. 131-140.

57. Мещанинов Д. Г. Метод построение полиномов для функций к-значной логики // Дискретная математика. 1995. Т. 7. № 3. С. 48-60.

58. Мещанинов Д. Г. О замкнутых классах к-значных функций, сохраняющих первые d-разности // Математические вопросы кибернетики. Вып. 8. М.: Наука, 1999. С. 219-229.

59. Многозначные логики и их применения/ сост. О.М. Аншаков, Д.В. Виноградов, В.К. Финн.- М.: ЛКИ, 2008.- T.l, Т2.

60. Нечаев А. А. Критерий полноты систем функций р^-значной логики, содержащих операции сложения и умножения по модулю рп // Методы дискретного анализа и решения комбинаторных задач. 1999. Т. 34. С. 74-89.

61. Пантелеев В. И. Полиномиальные разложения конечнозначных функций : автореф. дис. канд. физ.-мат. наук : 01.01.06. Омск, 1984. 14 с.

62. Пантелеев В. И., Перязев Н. А. Обобщенная интерпретация переменных: семантическое следование и логический вывод // Пятая школа молодых математиков Сибири и Дальнего Востока. Новосибирск, 1990. С. 87-89.

63. Перязев Н. А. Сложность булевых функций в классе полиномиальных поляризованных форм // Алгебра и логика. 1995. Т. 34. Ж 3. С. 323-326.

64. Перязев Н.А. Алгебра не всюду определенных функций // Алгебра и ее приложения: Труды международной конференции. Красноярск, 2007. С. 104.

65. Перязев Н.А. Функциональные системы недоопределенных частичных функций // Дискретная математика и ее приложения: Материалы Международного семинара. М.: Изд-во ММФ МГУ, 2007. С. 173174.

66. Перязев Н. А. Недоопределенные частичные булевы функции // Проблемы теоретической кибернетики: Материалы XV международной конференции. Казань, 2008. С. 92.

67. Поспелов Д. А. Логические методы анализа и синтеза схем.М.: Энергия, 1974. 368 с.

68. Селезнева С. Н. О сложности представления функций многозначных логик поляризованными полиномами // Дискретная математика. 2002. Т. 14. № 2. С. 48-53.

69. Селезнева С. Н. О сложности поляризованных полиномов функций многозначных логик, зависящих от одной переменной // Дискретная математика. 2004. Т. 16. № 2. С. 117-120.

70. Скорняков JI. А. Дедекиндовы структуры с дополнениями и регулярные кольца. М.: Физматгиз, 1961. 199 с.

71. Супрун В. П. Преобразования булевых функций на основе симметрической разности // Изв. АН СССР. Техническая кибернетика. 1983. № 5. С. 199-202.

72. Супрун В. П. Табличный метод полиномиального разложения булевых функций // Кибернетика. 1987. № 1. С. 116-117.

73. Супрун В. П. Декомпозиция булевых функций на основе полиномиального разложения // Известия АН СССР. Техническая кибернетика. 1989. № 3. С. 187-191.

74. Супрун В. П. Об одном методе полиномиального разложения булевых функций // Кибернетика. 1989. № 5. С. 122-124.

75. Тарасов В. В. Критерий полноты для не всюду определенных функций алгебры логики // Проблемы кибернетики. Вып. 30. М.: Наука, 1975. С. 319-325.

76. Тошич Ж. Полиномиальные представления в одном классе трехзначных логик // Известия АН СССР. Техническая кибернетика. 1967. № 2.

77. Тошич Ж. Полиномиальные представления булевых функций и их минимизация // Известия АН СССР. Техническая кибернетика. 1967. № 3. С. 141-143.

78. Угольников А. Б. О замкнутых классах Поста // Известия вузов. Математика. 1988 № 7 С. 79-88.

79. Угольников А. Б. Класс Поста: учеб. пособие. М.: Издательство ЦПИ при ММФ МГУ, 2008. 64 с.

80. Черепов А. Н. Описание структуры замкнутых классов в содержащих класс полиномов // Проблемы кибернетики. 1983. № 40. С. 518.

81. Черепов А. Н. О надструктуре класса полиномов // Труды семинара по дискретной математике и ее приложениям. М.: Изд-во Моск. унта, 1989. С. 117-120.

82. Шабунин A. JI. Об а-суперпозиции функций fc-значной логики // Сибирский математический журнал. 2007. Т. 48. № 2. С. 441-457.

83. Шеннон К. Э. Работы по теории информации и кибернетике. М: ИЛ., 1963. 829 с.

84. Шрамко Я. В. Обобщенные истинностные значения: решетки и муль-тирешетки // Логические исследования. Вып. 9. М.: Наука, 2002. С. 264-291.

85. Фрейвалд Р. В. О полноте частичных функций алгебры логики // ДАН СССР. 1966. Т. 167. № 6. С. 1249-1250.

86. Фреге Г. Логика и логическая семантика.— М.: Аспект Пресс, 2000.512 с.

87. Яблонский С. В. О суперпозициях функций алгебры логики // Мат. сборник. 1952. Т. 30. № 2. С. 329-345.

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

89. Яблонский С. В. Функциональные построения в fc-значной логике // Труды матем. ин-та им. В. А. Стеклова. 1958. Т. 51. С. 2-142.

90. Яблонский С. В. О суперпозициях функций в Рк / / Проблемы кибернетики. 1963. № 9. С. 337-340.

91. Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. М.: Наука, 1966. 120 с.

92. Яблонский С. В., Гаврилов Г. П., Набебин А. А. Предполные классы в многозначных логиках. М.: Из-во МЭИ, 1997. 144 с.

93. Яблонский С. В. Введение в дискретную математику: учеб. пособие для вузов. / под ред. В. А. Садовничего. — 3-е изд., стер. М.: Высш. шк., 2001. 384 с.

94. Balyuk A., Vinokurov S. Classes of Operator Forms // 5th International Workshop on Boolean Problems. Freiberg, Germany, 2002. P. 217-224.

95. Borner, F.; Haddad, L. Maximal partial clones with no finite basis // Algebra Univers. 40. 1998. No. 4. P. 453—476.

96. Bulatov A., Krokhin A., Safin K., Sukhanov, E. On the structure of clone lattices // General Algebra and Discrete Mathematics. Berlin: Heldermann Verlag, 1995. P. 27—34.

97. Bulatov A., Lau D., Strauch B. The cardinalities of sublattices of depth 2 in the lattices of clones on a 3-elementary set. Preprint Uni-versitat Rostock, 1996.

98. Bulatov A. A. Sublattices of a lattice of clones of functions on a 3-element set. I. (Russian, English) Algebra Logika 38, No. 1, 3-23 (1999); translation in Algebra Logic 38, No. 1, 1-11 (1999)

99. Bulatov A. A.: Sublattices of the lattice of clones of functions on a 3- element set. II. (Russian, English) Algebra Logika 38, No. 3, 269-295 (1999); translation in Algebra Logic 38, No. 3, 144-158 (1999) References 641

100. Bulatov A. A., Krokhin A. A., Jeavons P. Constraint satisfaction problems and finite algebras. // Montanari, Ugo (ed.) et al., Automata, languages and programming. 27th international colloquium,

101. ALP 2000, Geneva, Switzerland, July 9-15, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci 1853. P. 272—282.

102. Bulatov A., Krokhin A., Safin K., Semigrodskikh A., Sukhanov E. On the structure of clone lattices II. // Multi-Valued Log. 7. 2001. No. 5-6. P. 379-389.

103. Bulatov A. A.: Conditions satisfied by clone lattices // Algebra Univcrs. 2001. 45, No. 1-2. P. 237-241.

104. Chagrov A., Zakharjaschev M. Modal Logic. Oxford, 1998.

105. Csakany B. All minimal clones on the three-element set // Acta Cybernet. 1983. 6. P. 227-238.

106. Gaidukov A. I., Vinokurov S. F. Operator polynomial expansions of Boolean functions // 4th International Workshop on Boolean Problems. Freiberg, Germany, 2000. P. 63-68.

107. Goodearl K. R. Von Neuman regular rings. London e.a.: Pitman, 1979. 412 p.

108. Doroslovacki R., Pantovic J., Vojvodic G. One interval in the lattice of partial hyperclones // Chechoslovak Mathematical Journal. 2005. No. 55(130). P. 719-724.

109. Dunn J.M. The algebraof intensional Logics. Doctoral Dissertation. University of Pittsburg, Ann Arbor, 1966 (University Microvilms).

110. Dunn J.M. Intuitive semantics for first-degree entailment and coupled trees // Philosophial Studies. 1976. Vol 29. P. 149-168.

111. Drescher Th., Poschel R. Multiclones and relations // Multi-Val. Logic. 2001. No. 7. P.313-337.

112. Haddad L., Rosenberg I. G., Schweigert D. A maximal partial clone and a Slupecki- type criterion. // Acta Sci. Math. 1990. No. 54. P. 89-98.

113. Krasner M. Une generalisation de la notion de corps. J. Math, pure et appl., 1938. N 19. P. 367-383.

114. Lau D. Function algebras on finite sets. A basic course on many-valued logic and clone theory. Berlin: Springer-Verlag. 2006. 668 p.

115. Lehtonen E. Subfunction relation defined by the clones containing all unary operations.

116. Lo Czu Kai. Precompleteness of a set and rings of linear functions/ Acta sc/ natur Univ. Jilinensis, N 2, 1963.

117. Machida H. Hyperclones on a two-element set // Multiple-Valued Logic. An International Journal. 2002. No. 8(4). P. 495-501.

118. Machida H., Pantovic J. Maximal Hyperclones on E2 as Hypercores.

119. Machida H., Pantovic J. On maximal hyperclones on {0,1} a new approach // Proceedings of 38th IEEE International Symposium on Multiple- Valued Logic (ISMVL 2008). 2008. P. 32-37.

120. Muller D. E. Application of Boolean algebra to switching circuit design and error detection // IRE Trans. Electron. Comput. 1954. Vol. 3. No. 3. P. 6-12.

121. Pantovic J., Vojvodic G. Minimal partial hyperclones on a twoelement set // Proceedings of 34th IEEE International Symposium on Multiple-Valued Logic (ISMVL 2004). 2004. P. 115-119.

122. Pantovic J., Vojvodic G. On the partial hyperclone lattice // Proceedings of 35th IEEE International Symposium on Multiple-Valued Logic (ISMVL 2005). 2005. P. 96—100.

123. Post E. L. Determination of all closed systems of truth tables // Bull. Amer. Math. Soc. 1920. Vol. 26. P. 427.

124. Post E. L. Introduction to a general theory of elementary propositions // Amer. J. Math. 1921. Vol. 43. No. 4. P. 163-185.

125. Post E. L. Two-valued iterative systems of mathematical logic. Annals of Math. Studies. Princeton: Univ. Press. 1941. Vol. 5. 122 p.

126. Poschel R., Kaluznin L. A. Funktionen und Relationenalgebren // Ein Kapitel der diskreten Mathematik. Berlin: Deutscher Verlag der Wiss, 1979. (in German); Birkh Birkh hauser Verlag, Basel u. Stuttgart (Math. Reihe Bd. 67).

127. Pouzet M., Rosenberg I. G. Small clones and the projection property. 2008.

128. Reed I. S. A class of multiply-error-correcting codes and decoding scheme // IRE Trans. Inform. Theory. 1954. Vol. 4. No. 9. P. 38-49.

129. Romov B. A. Hyperclones on a finite set. // Multiple-Valued Logic. An International Journal. 1998. Vol.3(2). P. 285-300.

130. Romov B. A. Partial hyperclones on a finite set // Proceedings of 32nd IEEE International Symposium on Multiple-Valued Logic (IS-MVL 2002). 2002. P. 17-22.

131. Romov B. A.: Maximal subalgebras of algebras of partial multivalued logic functions. (Russian, English) //Cybernetics. 1980. 16. P. 31-41; translation from Kibernetica. 1980. No. 1. P. 28-36.

132. Romov B. A.: The algebras of partial functions and their invariants. (Russian, English) // Cybernetics 1981. 17. P. 157-167; translation from Kibernetica. 1981. No. 2. P. 1-11.

133. Romov B. A. The completeness problem in the algebra of partial functions of finite-valued logic. (Russian, English) // Cybernetics 1990. 26. No. 1. P. 133-138; translation from Kibernetica. 1990. No. 1. P. 102-106.

134. Rosenberg I. G. La structure des fonctions de plusieeurs variables sur un ensemble fini // C. R. Acad. Sci. Paris. 1965. Ser. A-B. 260. P. 3817-3819.

135. Rosenberg I. G. Zu einigen Fragen der Superpositionen von Funk-tionen mehrerer Veranderlicher // Bui. Inst. Politehn. Iasi. 1966. 12(16). P. 7-15.

136. Rosenberg I. G. Uher die Verschiedenheit maximaler Klassen in Pk // Rev. Roumaine Math. Pures Appl. 1969. 14. P. 431-438.

137. Rosenberg I. G. Minimal clones I: the five types // Lectures in universal algebra (Szeged, 1983), Colloq. Math. Soc. Janos Bolyai, 43, North-Holland, Amsterdam, 1986, pp. 405-427.

138. Rosenberg I. G. An algebraic aproach to hyperalgebras // Proceedings of 26th ISMVL, (Santiago de Compostela, May 28-31 1996). IEEE, 1996, P. 203-207.

139. Rosenberg I. G. Multiple-valued hyperstructures // Proceedings of 28th ISMVL (May 27-29 1998). IEEE, 1998. P. 326-333.

140. Logic synthesis and optimization / ed. T. Sasao. Kluwer Academic Publishers, 1993. 320 p.

141. Shramko Y., Dunn J.M., Takenaka T. The trilattike of constructive truth values // Journal of logic and computation. 2001. Vol. 11. P. 761-788.

142. Slupecki J. Kriterium pelnosci wielovar tosciowych systemov logiki zdan. - Comptes Rendus des Seaces de la Societe des Sciences et des Lettres de Varsovie? CI III 1939, 32 P.102-109

143. Szendrei A. Clones in universal algebra. Montreal: Les presses de l'universite de Montreal, 1986. 166 p.

144. Wang Xianghao. Structure theory of total and partial functions defined in a finite set. Acta Sci. Natur. Univ. Jiliensis, 1963. V. 2. P. 295-316.

145. Пантелеев В.И. Полиномиальные канонические формы Анзначных функций// Методы и системы технической диагностики/ Материалы 10 Международной конференции по проблемам теоретической кибернетики. Саратов, 1993. С. 134.

146. Пантелеев В. И. Полиномиальные разложения к-значных функций по невырожденным функциям // Математические заметки. 1994. Т. 55. № 1. С. 144-149.

147. Пантелеев В. И. Полиномиальные разложения полилинейных функций fc-значной логики. Иркутск: Изд-во Иркут. ун-та, 1994. 23 с.

148. Пантелеев В. И., Перязев Н. А. Обобщенная интерпретация переменных и 8-значная логика //Природные ресурсы, экология и социальная среда Прибайкалья. Сб. науч. трудов. T.III. Иркутск: Изд-во Иркут. ун-та, 1995. С. 268-271.

149. Пантелеев В. И. О полиномиальных разложениях полилинейных ко-нечнозначных функций. 4-я межд. конф. по прикладной логике (Иркутск, 15-18 июня, 1995г.) Материалы. Иркутск, 1995. С. 59.

150. Пантелеев В. И. Полиномиальные разложения /с-значных функций по операторам дифференцирования и нормализации // Известия Высших Учебных Заведений. Математика. 1998. № 1. С. 82-85.

151. Избранные вопросы теории булевых функций: Монография / А. С. Балюк, С. Ф. Винокуров, А. И. Гайдуков и др. / под ред. С. Ф. Винокурова, Н. А. Перязева. М.: Физматлит, 2001. 192 с.

152. Винокуров С. Ф., Пантелеев В. И. Полиномиальное представление булевых функций с использованием только остаточных функций //Труды XII Байкальской международной конференции. Иркутск: Из-во Иркутского ун-та, 2001. Т. 5. С. 27-31.

153. Зинченко А. С., Пантелеев В. И. Специальные полиномиальные представления булевых функций // Компьютерные науки и информационные технологии: Материалы международной конференции (Саратов, 2002 г.). Саратов: Изд-во Сарат. ун-та, 2002. С. 28-29.

154. Пантелеев В. И., Перязев Н. А. Логика предикатов при обобщенной интерпретации переменных // Вестник Бурятского университета. Серия 13: Математика и информатика. Вып. 2. Улан-Удэ: Изд-во Бурятского госуниверситета, 2005. С. 39-44.

155. Зинченко А. С., Пантелеев В. И. Полиномиальные операторные представления функций fc-значной логики // Дискретный анализ и исследование операций. Сер. 1. 2006. Т. 13. № 3. С. 13-26.

156. Пантелеев В. И. О недоопределенных булевых функци-ях//Синтаксис и семантика логических систем: Материалы российской шко-лы-семинара. Иркутск: изд-во ГОУ ВПО ИГПУ, 2006. С. 78-79.

157. Пантелеев В. И., Перязев Н. А. Недоопределенные булевы функции и булевы уравнения // Дискретные модели в теории управляющих систем: Труды VII Международной конференции. М.: МАКС Пресс,2006. С. 262-265.

158. Зинченко А. С., Пантелеев В. И. Бинарные термы в полиномиальных представлениях булевых функций // Математические заметки. 2007. Т. 81. Вып. 2. С. 217-225.

159. Пантелеев В. И., Перязев Н. А. О представлении функций к-значной логики суммой произведений остаточных подфункций // Дискретная математика. 2007. Т. 19. Вып. 2. С. 94-100.

160. Пантелеев В. И. О предполных классах недоопределенных функций алгебры логики // Алгебра и логика: Материалы международного российско-китайского семинара (Иркутск, 6-11 авг. 2007 г.). Иркутск: Изд-во Иркут. гос.пед. ун-та, 2007. С. 81-82.

161. Пантелеев В. И. О предполных классах недоопределенных частичных булевых функций // Проблемы теоретической кибернетики: Тезисы докладов XV международной конференции (Казань, 2-7 июня 2008 г.). Казань: Отечество, 2008. С. 91.

162. Пантелеев В.И. Критерий полноты для доопределяемых булевых функций // Вестник Самарского государственного университета. Естественнонаучная серия. № 2 (68).- 2009.- С.60-79.

163. Пантелеев В. И., Перязев П. А. Логика предикатов при обобщенной интерпретации переменных. Шестые Смирновские чтения: Материалы Междунар. науч. конф. (Москва, 17-19 июня 2009). М.: Современные тетради, 2009. С. 32-34.

164. Пантелеев В.И. Частичные гиперфункции на двухэлементном множестве/ / Дискретная математика и информатика. Вып. 20. — Иркутск: Изд-во Ирк. гос. пед. ун-та., 2009. — 28 с.

165. Пантелеев В.И. Максимальные клоны недоопределенных частичных булевых функций. Дискретные модели в теории управляющих систем: Труды VIII Международной конференции. М.: МАКС Пресс, 2009. С. 230-233.