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

• Пантелеев, Владимир Иннокентьевич
• доктор физико-математических наук
• 2009

Оглавление диссертации доктор физико-математических наук Пантелеев, Владимир Иннокентьевич

Введение

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 Операторы подстановки и сдвига в разложениях полилинейных функций.

Введение диссертации (часть автореферата) на тему «Суперпозиции функций k-значной логики и их обобщений»

Понятие функции в силу своей фундаментальности занимает одно из самых важных положений в математике. Математические модели, описанные на языке функций, находят широкое применение в различных областях человеческой деятельности. В последнее время интенсивно развивающейся областью теории функций является класс дискретных функций, так как аппарат таких функций используется при проектировании вычислительных устройств [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].

Список литературы диссертационного исследования доктор физико-математических наук Пантелеев, Владимир Иннокентьевич, 2009 год

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.