Авторефераты по всем темам >>
Авторефераты по разное
На правах рукописи
ПАНТЕЛЕЕВ Владимир Иннокентьевич
СУПЕРПОЗИЦИИ ФУНКЦИЙ k-ЗНАЧНОЙ ЛОГИКИ И ИХ ОБОБЩЕНИЙ
01.01.09 дискретная математика и математическая кибернетика
АВТОРЕФЕРАТ
диссертации на соискание ученой степени доктора физико-математических наук
Красноярск 2009
Работа выполнена на кафедре математической информатики Иркутского государственного педагогического университета
Научный консультант:
доктор физико-математических наук, профессор Перязев Николай Алексеевич
Официальные оппоненты:
доктор физико-математических наук, доцент Вороненко Андрей Анатольевич;
доктор физико-математических наук, профессор Егорычев Георгий Петрович;
доктор физико-математических наук, профессор Чагров Александр Васильевич
Ведущая организация:
Казанский государственный университет
Защита состоится 20 ноября 2009 г. в 15 часов на заседании диссертационного совета ДМ 212.099.18 в Сибирском федеральном университете по адресу: 660074, г. Красноярск, ул. Киренского, 26 корпус Ж, ауд. 1-15.
С диссертацией можно ознакомиться в библиотеке Сибирского федерального университета (г. Красноярск, ул. Киренского, 26).
Автореферат разослан октября 2009 г.
Ученый секретарь диссертационного совета Кириллов К.А.
Общая характеристика работы
Актуальность темы. Понятие функции в силу своей фундаментальности занимает одно из самых важных положений в математике.
Математические модели, описанные на языке функций, находят широкое применение в различных областях человеческой деятельности. В последнее время интенсивно развивающейся областью теории функций является класс дискретных функций, так как аппарат таких функций используется при проектировании вычислительных устройств, кодировании информации, передаче данных, в диагностике и контроле схем, в теории конечных автоматов, в теории игр, в языках программирования, при математическом моделировании природных процессов и др.
В рамках дискретных функций одним из важнейших понятий является понятие функциональной системы пары (P, Q), где P множество функций, Q множество операторов заданных на P. Изучение функциональных систем связано с именами целого ряда выдающихся математиков. Среди них Дж. Буль, Г. Фреге, А. Пирс, М. Шеффер, П.С. Порецкий, Е. Пост, К. Шеннон, И.И. Жегалкин, А.И. Мальцев, В.М. Глушков, А.В. Кузнецов, С.В. Яблонский, О.Б. Лупанов.
Одной из распространенных функциональных систем является система, в которой элементами первого множества являются функции, определенные на множестве {0, 1,..., k - 1} и принимающие значения из этого же множества, а в качестве оператора используется суперпозиция. Такие функции возникают как в самой теории функций, так и в многозначной логике (поэтому их часто называют функциями kзначной логики), в которой требуется для описания некоторых явлений употреблять высказывания, принимающие более двух значений.
Рассматривая функции k-значной логики можно выделить три направления исследований. Первое направление связано с логическими исчислениями, второе с подмножествами функций, а третье с суперпозициями, удовлетворяющими некоторым свойствам.
По первому направлению актуальны вопросы связанные с использованием функциональных систем в многозначных логиках. Исследуются различные семантики конечнозначных логик и строятся адекватные им логические исчисления. Одной из важных задач в этом направлении является построение многозначных логик при обобщенной интерпретации переменных языка первого порядка.
В рамках второго направления основным объектом исследований являются подмножества вместе с операцией суперпозиции и соответствующие им понятия:
- замыкания множества функций, представимых суперпозициями над заданным подмножеством;
- замкнутого класса множества функций, совпадающего со своим замыканием;
- клона замкнутого класса содержащего все проекции (селекторные функции);
- полного в замкнутом классе множества функций множества функций, замыкание которого совпадает с рассматриваемым замкнутым классом.
Наиболее важные достижения здесь относятся к построению и анализу порождающих множеств, проблеме эффективных критериев полноты и описанию решетки замкнутых классов1.
Среди всех работ в этом направлении выделим работы Э. Поста2 и И. Розенберга3.
В вышеперечисленных проблемах основным в паре подмножествосуперпозиция является второй элемент, но не менее интересной, а в последнее время и интенсивно развивающейся, является задача изучения некоторого специального подмножества функций k-значной логики. В этом случае приходится изменять операцию суперпозиции так, чтобы она не выводила за пределы рассматриваемого подмножества и относительно соответствующим образом измененной операции суперпозиции ставить те же вопросы замыкания, полноты и т.д.
Среди всех возможных подмножеств выделим подмножества функций 2m-значной логики, которые однозначно определяются по своим значениям на наборах, построенных из элементов множества {0, 1,..., m - 1}. Такие подмножества, с одной стороны, возникают при изучении многозначных логик, решении уравнений над функциями, в технических системах, где рассматриваются схемы с неисправностями из некоторого возможного множества, а с другой стороны, являются естеЯблонский С. В. Функциональные построения в k-значной логике // Труды матем. ин-та им. В. А. Стеклова. 1958. Т. 51. С. 2Ц142.
Post E. L. Two-valued iterative systems of mathematical logic. Annals of Math.
Studies. Princeton: Univ. Press. 1941. Vol. 5. 122 p.
Rosenberg I. G. ber die Verschiedenheit maximaler Klassen in Pk // Rev.
Roumaine Math. Pures Appl. 1969. 14. P. 431Ц438.
ственным развитием теории функций k-значной логики, в которой наряду со всюду определенными функциями рассматриваются и функции, определенные не на всех наборах и неопределенности могут быть различных видов. Один из путей исследований здесь связан с тем, что неопределенности понимаются как некоторые подмножества множества {0, 1,..., k - 1}. Естественно, что такие функции можно назвать обобщениями функций k-значной логики и, в зависимости от числа и вида неопределенностей, а также измененной суперпозиции, их называют частичными, недоопределенными, доопределяемыми, гипер-, мульти-, ультрафункциями4.
Для третьего направления исследований изучение суперпозиций специального вида можно выделить следующие фундаментальные проблемы:
- описание при фиксированном k класса функций представимых суперпозициями специального вида.
- указание тех значений k, при которых любую функцию k-значной логики можно представить суперпозициями заданного вида.
- разработка простых алгоритмов для нахождения представлений функций суперпозициями специального вида, существование которых определяется решением двух вышеприведенных проблем.
- оценка сложности представлений, исходя из определенных критериев сложности.
Одним из ответов на этот вопрос является возможность представления булевых функций дизъюнктивными и конъюнктивными нормальными формами и их аналоги для произвольного k > 2. Для k = 2 наиболее общая постановка задачи рассматривалась О. Б. Лупановым5.
Особый интерес при представлении функций специальными формами вызывают представления, использующие в качестве внешней функции суперпозиции многоместное сложение по модулю k, которые мы буЛо Джукай. Теория полноты для частичных функций многозначной логики // Кибернетический сборник. Новая серия. Вып. 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.
упанов О. Б. Об одном подходе к синтезу управляющих систем принципы локального кодирования // Проблемы кибернетики. 1965. № 4. С. 31Ц110.
дем называть полиномиальными формами. Многие известные полиномиальные представления булевых функций удалось описать с использованием операторного подхода6.
Естественной является задача распространения этих результатов на произвольные функций k-значной логики.
Цели работы:
Х описать логические системы, как область возникновения обобщений функций k-значной логики;
Х исследовать вопросы связанные с полными множествами и специальными представлениями частичных гиперфункций и ультрафункций;
Х перенести операторный подход, развитый для специальных представлений булевых функций на функции k-значной логики и в рамках этого подхода описать известные полиномиальные представления булевых функций с точки зрения полиномиальных представлений функций k-значной логики.
Основные результаты и научная новизна. Автору лично принадлежат следующие основные научные результаты (в том числе и из совместных работ):
- построены исчисления табличного типа для семантики языка предикатов с обобщенной интерпретацией переменных и доказаны теоремы полноты и корректности;
- найдены некоторые специальные представления частичных гиперфункций и полные множества, что позволило дать описание всех максимальных частичных гиперклонов на 2-х элементном множестве и доказать в терминах предполных классов критерий функциональной полноты. Тем самым решена проблема, являющаяся объединением известных задач С.В. Яблонского о полноте для частичных и недоопределенных булевых функций;
Избранные вопросы теории булевых функций: Монография / А. С. Балюк, С. Ф. Винокуров, А. И. Гайдуков и др. / под ред. С. Ф. Винокурова, Н. А. Перязева. М.: Физматлит, 2001. 192 с.
- как аналог частичных гиперфункций и обобщение функций k-значной логики определены ультрафункции и найдены для них некоторые полные множества, что позволило доказать критерий полноты для ультрафункций на 2-х элементном множестве;
- найдены необходимые и достаточные условия существования полиномиальных представлений частного вида;
- найдены общие условия существования полиномиальных представлений функций k-значной логики, в которых слагаемые являются операторными образами фиксированной функции (системы функций), и для некоторых таких представлений найдены формулы вычисления коэффициентов без использования операции нахождения обратной матрицы.
В диссертацию включены следующие совместные результаты:
- введена новая гиперзначная семантика при обобщенной интерпретации переменных языка предикатов (совместно с Н.А. Перязевым);
- предложен операторный подход к специальным представлениям функций k-значной логики, который позволил классифицировать известные операторы (совместно с Н.А. Перязевым);
- на основе операторного подхода найдены необходимые и достаточные условия существования полиномиальных представлений булевых функций в которых слагаемые являются бинарными термами (совместно с ученицей А.С. Зинченко);
- найдена нижняя оценка сложности для одного класса операторных полиномиальных представлений функций k-значной логики (совместно с А.С. Зинченко).
Основные результаты диссертации являются новыми. Конфликт интересов с соавторами отсутствует.
Теоретическая и практическая ценность. Полученные результаты имеют теоретическое значение и могут найти применение в исследованиях по теории функциональных систем. Результаты могут быть использованы при проектировании дискретных преобразователей информации и при работе с неполными и противоречивыми описаниями состояний.
Методы исследований. В диссертационой работе широко используются понятия и методы теории дискретных функций (в частности понятие сохранения предиката функцией), математической логики, универсальной алгебры, линейной алгебры.
Апробация работы. Результаты диссертации докладывались на:
школе-семинаре по дискретной математике и ее приложениям (Москва, 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 наименование, включая работы диссертанта.
Содержание работы Во введении дается обоснование актуальности темы исследований.
В первой главе делается обзор основных результатов диссертанта, а также исследований других авторов, касающихся вопросов, рассмотренных в диссертации.
В первом параграфе главы рассматривается функция истинностной оценки, которая приписывает каждому высказыванию (предикату) какой-нибудь (и только один) элемент некоторого множества истинностных значений. Если в качестве последнего взять двухэлементное множество {И, Л}, то получим классическую функцию истинности и классическую логику высказываний. В общем же случае речь идет о многозначной логике. Приводится пример 4-х значной логики высказываний, расматриваемой Дж. М. Данном7.
Во втором параграфе рассматриваются функции k-значной логики, частичные гиперфункции и приводятся известные результаты, связанные с проблематикой полноты, описанием решетки замкнутых классов.
В третьем параграфе приводятся известные результаты по полиномиальным представлениям функций k-значной логики, в частности, по полиномиальным операторным представлениям.
Результаты исследований, полученных дисcертантом, приведены во 2-й, 3-й и 4-й главах.
Вторая глава посвящена логическим системам с гиперзначной семантикой, основанной на обобщенной интерпретации переменных.
В первом параграфе главы вводится обобщенная интерпретация переменных и связанная с ней частичная гиперзначная семантика.
Пусть L - язык первого порядка с логическими символами &, , м, , , сигнатуры = {F, P }, где F - множество функциональных символов; P - множество предикатных символов. Определения терма, формулы сигнатуры , множества свободных переменных (F V ) терма и формулы даются стандартным образом.
Пусть A = A, - алгебраическая система с носителем A сигнатуры , где, как обычно функциональным символам соответствуDunn J.M. Intuitive semantics for first-degree entailment and coupled trees // Philosophial Studies. 1976. Vol 29. P. 149-168.
ют функции на A (нульместным функциональным символам элементы A), предикатным символам предикаты на A, при этом nместные предикаты на множестве A мы будем рассматривать как функции p : An B, (p P ), B некоторое конечное множество, которое называется основным истинностным множеством.
Пусть формула и F V () = {x1,..., xn} множество ее свободных переменных, на котором зафиксирован некоторый порядок. Обобщенной интерпретацией назовем отображение : F V () 2A.
Будем говорить, что интерпретация расширяет интерпретацию за счет переменной y F V () (обозначаем y ), если / : F V () {y} 2A, |(y)| = 1 и (x) = (x) для всех x F V ().
Определим значение терма t при обобщенной интерпретации (обозначаем [t]).
Если t = xi, то [t] = (xi).
Если t = f(t1,..., tn), то [t] = {a | a = f(a1,..., an), ai [ti]}.
Из этого определения сразу следует, что если для некоторого терма tj выполняется [tj] = , то тогда и [t] = .
Истинностное значение элементарной формулы P (t1,..., tn) при обобщенной интерпретации будем понимать следующим образом:
[P (t1,..., tn)] = {P (a1,..., an)}.
ai[ti] Если для некоторого ti выполняется [ti] = , то [P (t1,..., tn)] = .
Истинностные значения остальных формул при обобщенной интерпретации зависят от основного истинностного множества и могут определяться по разному в зависимости от решаемого класса задач. В общем случае истинностным значением таких формул являются элементы множества 2B.
Во втором параграфе второй главы рассматривается 4-х значная логика предикатов в качестве первого примера логической системы с обобщенной интерпретацией переменных, которой соответствует двухэлементное основное множество истинностных значений, т.е., говоря об алгебраической системе A сигнатуры с носителем A, nместные предикаты на множестве A мы будем рассматривать как функции p : An {И, Л}.
Для элементарных формул при обобщенной интерпретации переменных в соответствии со значением терма истинностным значением может быть любое подмножество основного множества истинностных значений {И}, {Л}, {И, Л}, . Обозначим эти подмножества как И, Л, Н, Б. Значение формулы при интерпретации (обозначаем []) в соответствии с этими обозначениями определяется следующим образом:
a) если P (t1,..., tn), то значение [] есть:
И, если P (a1,..., an) выполняется в A для всех ai [ti];
, если P (a1,..., an) не выполняется в A для всех ai [ti];
Н, если существуют a1,..., an, ai [ti] (i = 1,..., n) такие, что P (a1,..., an) выполняется в A и существуют b1,..., bn, bi [ti] (i = 1,..., n) такие, что P (b1,..., bn) не выполняется в A;
Б, если существует i {1,..., n} такое, что [ti] = .
б) если = 1 2( {&, , }), или = м, то значение [] определяется из следующих таблиц:
& И Л Н Б И Л Н Б И Л Н Б м И И Л Н Б И И И И Б И И Л Н Б И Л Л Л Л Л Б Л И Л Н Б Л И И И Б Л И Н Н Л Н Б Н И Н Н Б Н И Н Н Б Н Н Б Б Б Б Б Б Б Б Б Б Б Б Б Б Б Б Б в) если = x(x), то [] есть:
И, если [] =И, для любой интерпретации , такой что x ;
Л, если [] =Л, для некоторой интерпретации , такой что x , и не существует ( x ): [] =Б;
Н, если [] =Н, для некоторой интерпретации , такой что x , и не существует ( x ): [] =Б или [] =Л;
Б, если [] =Б, для некоторой интерпретации , такой что x .
г) если = x(x), то [] = [мxм(x)].
Отмеченными формулами сигнатуры будем называть выражения вида , {,,, } и формула сигнатуры ( назовем отметкой формулы ).
Конечное множество отмеченных формул будем называть секвенцией и обозначать .
Секвенцию назовем невыполнимой на алгебраической системе A сигнатуры , если для любой интерпретации существует отмеченная формула из ( = ), такая, что отметка не совпадает с [] при соответствии И Л Н Б, иначе секвенцию будем называть выполнимой на алгебраической системе A сигнатуры .
Секвенцию назовем семантически противоречивой, если она невыполнима на любой алгебраической системе сигнатуры .
В теореме 2.1 описаны некоторые условия, при которых секвенция противоречива.
Далее в параграфе построена система логического вывода табличного типа и доказана Теорема 2.2 (об адекватности). Секвенция семантически противоречива тогда и только тогда, когда выводима.
В третьем параграфе второй главы идеи, лежащие в основе построения исчисления для четырехзначной логики перенесены на случай, когда рассматривается 2k-значная логика, в которой основное множество истинностных значений состоит из k элементов.
Пусть основное множество истинностных значений это множество B = {1, 2,..., k}, на котором задан линейный порядок 1 2 ... k и соответствующая циклическая подстановка: = (123...k).
Рассматривая алгебраическую систему A с носителем A, под nместным предикатом мы понимаем отображение p : An B.
На элементах множества 2B определим операции &, и м.
Пусть B1 2B и B2 2B, тогда B1&B2 = {t | t = min(t1, t2), t1 B1, t2 B2};
B1 B2 = {t | t = max(t1, t2), t1 B1, t2 B2};
мB1 = {t | t = () для некоторого элемента из B1}.
Если = P (t1,..., tn), то значение [] = {P (a1,.., an)}.
ai[ti] Для формулы = 1 2 ( {&, }) значение [] = [1] [2], а [м] = м[].
Если = x(x), то [] есть множество D = {d1,..., dt}, причем dl D (l {1,..., t}) тогда и только тогда, когда найдется интерпре тация : x такая, что dl [] и для любой интерпретации : x найдется e [] такой, что dl e.
Если = x(x), то [] есть множество D = {d1,..., dt}, причем dl D (l {1,..., t}) тогда и только тогда, когда найдется интерпре тация : x такая, что dl [] и для любой интерпретации : x ) найдется e [] такой, что e dl.
Для рассматриваемой 2k-значной логики построено логическое исчисление табличного вида и доказана Теорема 2.3 Секвенция семантически противоречива в 2k-значной логике тогда и только тогда, когда выводима.
В третьей главе рассматриваются обобщения функций k-значной логики: частичные гиперфункции и ультрафункции.
Пусть A = {0, 1,..., k - 1} конечное множество. Тогда n-местной функцией на A называется отображение f : An A; n-местной частичной функцией на A f : An A ; n-местной гиперфункцией на A f : An 2A \ ; n-местной частичной гиперфункцией на A f : An 2A.
Суперпозиция f(f1(x1,...xn),..., fm(x1,...xn)) определяет (частичную, гипер-) функцию h(x1,..., xn) следующим образом:
для функций h(a1,...an) = f(f1(a1,...an),..., fm(a1,...an)), для частичных функций , если fi(a1,..., an) = для некоторого i {1,...n};
h(a1,..., an) =, f(f1(a1,...an),..., fm(a1,...an)) для гиперфункций h(a1,..., an) = f(b1,..., bn), (1) bifi(a1,...,an) для частичных гиперфункций , если fi(a1,..., an) = для некоторого i {1,...n};
h(a1,..., an) = f(b1,..., bn), иначе.
bifi(a1,...,an) (2) Функции-проекции это отображения en : (1,..., n) i.
i Функции-гиперпроекции это отображения en : (1,..., n) {i}.
i Клон (частичный клон) множество (частичных) функций, содержащее проекции и замкнутое относительно суперпозиции.
Гиперклон (частичный гиперклон) множество (частичных) гиперфункций, содержащее гиперпроекции и замкнутое относительно суперпозиции.
(Частичные) гиперфункции, заданные на множестве A, с определенной для них суперпозицией фактически определяют подмножество функций 2k-значной логики, заданных на множестве 2A (при этом мы отождествляем одноэлементное подмножество с элементом этого множества). Функцию 2k-значной логики, заданную на множестве 2A, будем называть гиперфункцией, если она однозначно строятся по своим значениям на наборах из множества A в соответствии с (1) и частичной гиперфункцией если в соответствии с (2).
Определим суперпозицию частичных гиперфункций, заданных на множестве A, следующим образом:
f(b1,..., bn), если f(b1,..., bn) = ;
bifi(a1,...,an) bifi(a1,...,an) h(a1,..., an) = f(b1,..., bn), иначе.
bifi(a1,...,an) (3) Функцию 2k-значной логики, заданную на множестве 2A, будем называть ультрафункцией, если она однозначно строятся по своим значениям на наборах из множества A в соответствии с (3).
Пусть Rs s-местный предикат, заданный на множестве F. Будем говорить, что функция f(x1,..., xn), определенная на множестве F, сохраняет предикат Rs, если для любых n наборов (11,..., s1),..., (1n,..., sn) принадлежащих предикату, набор (f(11,..., 1n),..., f(s1,..., sn)) принадлежит Rs.
Наборы, принадлежащие предикату, будем записывать в виде столбцов.
В первом параграфе основными вопросами являются вопросы полноты частичных гиперфункций на 2-х элементном множестве, которые мы рассматриваем как функции 4-х значной логики.
Определим 4-х значные функции как функции на множестве F = {, 0, 1, -} при соответствии , {0} 0, {1} 1, {0, 1} -.
Обозначим рассматриваемое подмножество через P2.
Для произвольной функции f P2 зададим всюду определенные 0 1 x функции: f 0-доопределение, f 1-доопределение, f (01)x доопределение, f (10)-доопределение следующим образом:
0, если f(1,..., n) {0, -, };
f(1,..., n) = 1, если f(1,..., n) {1}.
1, если f(1,..., n) {1, -, };
f(1,..., n) = 0, если f(1,..., n) {0}.
0, если f(1,..., n) {0, };
x f(1,..., n) = 1, если f(1,..., n) {1, -}.
0, если f(1,..., n) {0, -};
x f(1,..., n) = 1, если f(1,..., n) {1, }.
Функции x y и x y определяются естественным образом.
Теорема 3.1 Для любой f F справедливо разложение 0 x 1 x f(x1,..., xn) = (f f) (f f).
Теорема 3.2 Для любой f F справедливо разложение 0 x 1 x f(x1,..., xn) = (f f) (f f).
Из этих теорем получено несколько следствий, в которых описываются полные и предполные множества.
Для функций f(x1,..., xn), h1(x1,..., xm),..., hn(x1,..., xm) через h1,...,hn fx,...,xn обозначим суперпозицию f(h1,..., hn) и пусть как обычно x, если = 1;
x= x, если = 0.
Определим две функции i(x1,..., xn) = (0-) i(x1,..., xn) и i(x1,..., xn) = (-1) i(x1,..., xn), i, если i = 0;
где знак суперпозиции и пусть (i) = i, если i = 1.
Справедливы следующие представления частичных гиперфункций.
Теорема 3.3 (аналог скнф) Для любой функции f P2 справедливо разложение 1 n f(x1,..., xn) = & x ... x f( ),...,(n).
1 n x1,..., xn (,...,n )En Теорема 3.4 (аналог сднф) Для любой функции справедливо разложение 1 n f(x1,..., xn) = x &...&x &f( ),...,(n).
1 n x1,..., xn (,...,n )En Определим 15 множеств, содержащих селекторные функции.
I. K1 = {f(x1,..., xn) | f или f(0,..., 0) {0, -}}.
II. K2 = {f(x1,..., xn) | f или f(1,..., 1) {1, -}}.
III. K3 = {f(x1,..., xn) | f(0,..., 0) {0, }}.
IV. K4 = {f(x1,..., xn) | f(1,..., 1) {1, }}.
V. K5 = P2 {}.
VI. K6 = P2.
VII. K7 = {f| {f(0,..., 0), f(1,..., 1)} [e].
VIII. K8 класс функций, сохраняющих предикат 1 0 R8 =.
0 1 IX. K9 класс функций, сохраняющих предикат 0 0 1 0 - 1 - R9 =.
1 0 1 - 1 - - 0 1 - X. K10 класс функций, сохраняющих предикат 0 0 1 0 - - - 0 - 1 R10 =.
1 0 1 - 1 0 - XI. K11 класс функций, сохраняющих предикат 0 1 - 0 R11 =.
1 0 1 - 0 XII. K12 класс функций, сохраняющих предикат R12.
R12 содержит все наборы, кроме 0 0 0 1 1 1 - - - 0 1 1 - 1 0 - - 0 - - 0 1 - 0 1 - 0 1 - 0 1 0 - - - 1 0 1 0 - -.
1 0 0 0 0 0 0 0 0 1 1 XIII. K13 класс функций, сохраняющих предикат R13.
R13 содержит все наборы, кроме 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 0 - 1 - - - 0 0 1 0 - 1 - 1 - - 1.
1 0 1 0 - 0 - 1 - 0 - 1 0 0 1 - - 1 - 1 XIV. K14 класс функций, сохраняющих предикат R14.
R14 не содержит наборы (, , = ) 0 0 0 1 1 1 1 0 0 1 0 1 1 0 0 1 0 0 1 0 1 1 0 0 0 0 1 1 и не содержит наборы (1 2 3 4) такие, что i = (i {1, 2, 3, 4}) и среди 1, 2, 3, 4 встречается E и = -.
XV. Для набора (1,..., n) (F )n определим двойственный ему набор (1,..., n) следующим образом: если i = 0, то i = 1; если i = 1, то i = 0; в остальных случаях i = i (i {1,..., n}).
K15 класс функций, сохраняющих предикат R15, не содержащий следующие наборы и двойственные к ним (, , = , {1, -}, {0, 1, -}).
0 0 0 0 0 0 0 1 - 1 - - 1 0 .
1 - - 1 0 0 - Теорема 3.5 Система функций в P2 полна тогда и только тогда, когда она не содержится целиком ни в одном из классов K1 - K15.
Второй параграф посвящен ультрафункциям на 2-х элементном множестве и основным результатом является критерий полноты.
Пусть E = {0, 1}, F = {0, 1, -}. Как и выше функции f : En E назовем всюду определенными (P2 множество всех всюду опреде ленных булевых функций); f : En F ультрафункциями (Pмножество всех ультрафункций).
Введем в рассмотрение 11 замкнутых классов, содержащих селекторные функции.
I. P2 класс всюду определенных функций.
II. T0 класс функций, которые сохраняют нуль, т.е. на наборе из всех нулей равны 0.
III. T1 класс функций, которые сохраняют единицу, т.е. на наборе из всех единиц равны 1.
IV. S- класс функций, сохраняющих предикат 0 1 S- =.
1 0 V. L- класс функций, сохраняющих предикат 1 0 0 1 L- =.
1 0 1 0 VI. M- класс функций, сохраняющих предикат 1 0 0 - 0 M- =.
1 0 1 - - VII. K1 класс функций, сохраняющих предикат 0 1 1 - 1 K1 = 1 0 1 - - VIII. K2 класс функций, сохраняющих предикат 0 0 0 - - K2 = 0 1 - 0 - IX. K3 класс функций сохраняющих предикат 0 0 0 - 0 0 0 0 1 1 1 1 1 1 - - - 0 0 - K3 = 0 0 - - - 0 1 1 0 1 1 - - 1 1 1 - - 1 1 0 - 0 - - 1 0 1 1 0 1 - 1 - 1 - 1 1 - 0 X. K4 класс функций сохраняющих предикат - 0 0 0 0 0 0 - - - K4 = - - 0 1 0 - 0 0 0 - - 0 1 0 - - 0 0 - 0 XI. K5 класс, состоящий из всех функций существенно зависящих не более чем от одной переменной, а также из функций принимающих два значения, одно из которых есть Ф-Ф.
Теорема 3.6 Система функций F P2 полна тогда и только тогда, когда она целиком не содержится ни в одном из классов P2, T0, T1, S-, L-, M-, K1 - K5.
В третьем параграфе результаты, полученные выше обобщаются на частичные гипер- и ультрафункции, определенные на произвольном конечном множестве и в результате описываются некоторые полные множества и, как следствие, получаются решетки клонов частичных гипер- и ультрафункций (будем использовать также названия частичный гиперклон, гиперклон, ультраклон), содержащие клон всех функций.
Пусть A = {0, 1,..., k - 1} и пусть Pk множество всех функций определенных на множестве A, Pk множество всех частичных функций на множестве A, Pk множество всех гиперфункций на множестве A, Pk множество всех частичных гиперфункций на множестве A.
Pk множество всех ультрафункций на множестве A и Pk множество всех частичных ультрафункций на множестве A.
Определим на множестве A = {0, 1,..., k - 1} k-местную частичную гиперфункцию k(x1,..., xk):
k {0} {i}, если 1 = 1;
i=k(1,..., k) = k {i} \ {0}, если 1 = 1, i=k-местную гиперфункцию -(x1,..., xk):
k 0, если 1 =... = k = 0;
k {0} {i}, если 1 = 1;
-(1,..., k) = k i= k k {i} \ {0}, если 1 = 1 и {i} = 0, i=1 i=и k-местную частичную функцию (x1,..., xk):
k , если 1 = = k = 0;
...
, если 1 = = i-1 = i+1 = = k = 0,......
i (1,..., k) = k i = 0, i > 1;
0, иначе.
Теорема 3.7 Справедливы утверждения 1. Множество функций Pk {k} является полным в Pk.
2. Множество функций Pk {} является полным в Pk.
k 3. Множество функций Pk {-} является полным в Pk.
k В качестве следствий из этой теоремы получены некоторые полные множества и решетка частичных гиперклонов, содержащих клон всех функций, описанная R. Doroslovaki, J. Pantovi, G. Vojvodi8.
Для ультрафункций доказана Теорема 3.8 Частичными ультраклонами, содержащими Pk явля ются Pk, Pk , Pk, Pk , Pk, Pk и только.
Четвертая глава диссертации посвящена операторному подходу к полиномиальным представлениям функций k-значной логики, при этом везде, за исключением параграфа 4.3.2 предполагается, что k простое число.
Под операторами функций k-значной логики мы будем понимать любое отображение q : F F, где F множество всех функций kзначной логики В первом параграфе главы определяется класс операторов и его естественный подкласс , которые включают в себя все известные нам операторы.
Doroslovaki R., Pantovi J., Vojvodi G. One interval in the lattice of partial hyperclones // Chechoslovak Mathematical Journal. 2005. No. 55(130). P. 719Ц724.
Будем использовать следующие обозначения: x вектор перемен ных, h вектор функций. Пусть f функция k-значной логики, x и h это векторы переменных и функций одинаковой размерности s, h соответственно, тогда через fx обозначим функцию, полученную из f заменой переменных из x на функции из h, причем переменная xi за меняется на hi, i = 1,..., s.
Каждому натуральному n поставим в соответствие функцию hn(x, y1,..., ys) и наборы функций hn (x, z),...,hn (x, z).
1 s Класс это класс операторов q, определяемых следующим образом: для произвольной функции k-значной логики f ранга k имеем hk1 (xk,zk) hks q(f) = hk(xk, fx,..., fx (xk,zk)), k k причем среди переменных zk не встречаются переменные функции f, наборы xk и zk не содержат общих элементов.
Если в предыдущем определении каждому n поставим в соответствие одну и ту же функцию h, один и тот же набор функций h1(x, z),..., hs(x, z) и один и тот же набор переменных x, то полученный класс опе раторов назовем .
На классе определим произведение и операции k-значной логики.
Пусть d, q, d1,..., dn операторы, g(x1,..., xn) n-местная функция k-значной логики, тогда произведение операторов (d q) определяется следующим образом: (d q)(f) = d(q(f)), а операция k-значной логики g над операторами d1,..., dn дает оператор g(d1,..., dn):
g(d1,..., dn)(f) = g(d1(f),..., dn(f)).
Пусть q , h(y1,..., yn) n-местная функция k-значной логики. Оператор q называется h-стабильным, если для любых функций k-значной логики f1,..., fn выполняется:
q(h(f1,..., fn)) = h(q(f1),..., q(fn)).
В теоремах 4.1 и 4.2 показывается, что класс операторов замкнут относительно произведения и операций k-значной логики и получены необходимые и достаточные условия h-стабильности оператора.
Совместно c Н. А. Перязевым проведена классификация известных операторов булевых фцнкций.
В оставшихся параграфах главы рассматриваются полиномиальные представления функций k-значной логики с с использованием трех спеi i циальных операторов класса : разностного da, подстановки sa xi xi i и сдвига pa. При этом, говоря о полиномиальных представлениях, xi мы будем иметь в виду сложение по mod k, коэффициенты перед слагаемыми являются элементами Ek = {0, 1,..., k - 1}.
Пусть Ek и x() = k - 1 - x + . Заметим, что при k = 2 это x, если a = обозначение соответствует принятому xa = x, если a = 1.
Определим оператор подстановки (sa), разностный оператор (da) и оператор сдвига (pa) для функций k-значной логики, которые мы будем использовать далее в этой главе.
Пусть f(x1,..., xn) функция k-значной логики, тогда sa f(x1,..., xi,..., xn) = f(x1,..., xi-1, a, xi+1,..., xn) (0 a k - 1);
xi pa f(x1,..., xi,..., xn) = f(x1,..., xi-1, x(a), xi+1,..., xn) (0 a k-1);
xi i d0 f(x1,..., xi,..., xn) = f(x1,..., xi,..., xn);
xi da f(x1,..., xi,..., xn) = f(x1,..., xi,..., xn) + f(x1,..., xi - a,..., xn) xi (1 a k - 1).
1 n Оператор, являющийся произведением операторов ta, ta,..., ta 1 2 n (ti {s, p, d}, ai Ek), будем обозначать через t, члены произведения будем называть компонентами оператора, ti основанием компоненты оператора, ai ее показателем, а число n длиной оператора.
Для = (i,..., i ) и x = (xi,..., xi ) наборов констант и пе 1 r 1 r ременных, соответственно, оператор tx определяется как произведение i1 ir r операторов tx,..., t.
xir iВо втором параграфе четвертой главы рассматриваются полиномиальные представления функций k-значной логики с использованием разностного оператора и оператора сдвига.
Упорядоченное множество, состоящее из kn операторов длины n называется пучком операторов и обозначается T, число n называется размерностью этого пучка.
Назовем пучок операторов T размерности n базисным, если сущеn n ствует такая функция g Fk (Fk множество всех функций kn значной логики от n переменных), что любую функцию f Fk можно представить в виде линейной комбинации операторных образов функции g по операторам из T.
Функцию f(x1,..., xn) будем называть невырожденной, если f(1,..., n) = 0, i {0, 1,..., k - 1}, 1,...,n и вырожденной в противном случае. При k = 2 невырожденными будут те и только те функции, у которых вектор значений содержит нечетное число единиц. Невырожденные функции (и их аналоги) являются основой многих полиномиальных разложений.
1 n 1 n Пучок операторов O = (oi...in = oi... oi | (i1,..., in) Ek, 1 n oi {p, d}) называется однородным.
Среди однородных пучков выделим два:
n n 1 n 1 n P = (pi... pi |(i1,..., in) Ek ), D = (di... di |(i1,..., in) Ek ).
Для функции g(x1,..., xn) и однородного пучка операторов O определим матрицу G[O(g)] размерности kn kn.
G = (g) и g = oj g() ( = (i1,..., in), j = (j1,..., jn)).
j j x Теорема 4.3 Пусть пучок O является однородным, а n-местная функция g является невырожденной, тогда любую функцию k-значной логики можно представить в виде f(x1,..., xn) = a...no...n g(x1,..., xn) a...n Ek.
1 x1,...,xn 1...n Если O = P, то матрица коэффициентов A вычисляется по формуле - A = [G[O(g)]]k-1 F g(1,..., n), 1...n где F вектор-столбец значений функции f(x1,..., xn).
Невырожденность функции является необходимым условием существования полиномиальных представлений в которых слагаемые являются операторными образами данной функции.
Для однородных пучков это условие является и достаточным, а в общем случае, как показала А.С.Зинченко, требуется невырожденность специальным образом определенной матрицы пучка9.
Пусть Pt(f) полином, представляющий функцию f. Сложностью L(Pt(f)) полинома Pt(f) будем называть число слагаемых в нём. Число LK(f) = min L(Pt(f)) Pt(f)K назовём сложностью функции f в классе полиномов K. Сложностью класса функций S в классе полиномов K назовем число LK(S) = max LK(f).
fS G Можно выделить два класса полиномов: K = KT линейные комg бинации образов функций из базиса G по операторам из T и K = KT линейные комбинации образов невырожденной функции g по пучку из класса пучков T.
Среди всевозможных базисов рассмотрим два:
G1 = {x0 ... x0,..., xk-1 ... xk-1} и 1 n 1 n n 1 n G2 = {pi... pi g(x1,..., xn)|(i1,..., in) Ek }, где g невырожденная функция. Первый базис состоит из произведений степеней переменных, второй из сдвигов функции g.
Разложения по операторам из класса P и базису G1 позволяют получить представления, называемые поляризованными полиномами.
Н. А. Перязев нашел точное значение функции Шеннона для класса булевых функций и класса симметрических функций в поляризованных полиномах Жегалкина (форм Рида-Маллера), а С. Н. Селезнева получила оценки сложности функции Шеннона для поляризованных полиномов при k 3.
В следующей теореме содержится нижняя оценка класса D и базиса G1 (получена совместно с А. С. Зинченко).
Зинченко А. С., Пантелеев В. И. Полиномиальные операторные представления функций k-значной логики // Дискретный анализ и исследование операций.
Сер. 1. 2006. Т. 13. № 3. С. 13Ц26.
Теорема 4.4 При любом n 0 справедливо неравенство n k + GLKD (n) , k 3.
В третьем параграфе этой главы рассматриваются полиномиальные представления вида q-1 q 1 f(x1,..., xq)= 2...q g1(fx, g2(fx,..., gq-1(fx, fx )...)), 1 1 2 q-1 q 12...q (4) где g1(y1, y2),..., gq-1(y1, y2) бинарные функции.
Известно, что при разбиении множества переменных на две части любую булеву функцию можно представить суммой произведений собственных подфункций10.
Естественным является вопрос, а какие еще функции, сохраняющие возможность применения разложения к произвольной функции, могут быть использованы в построении слагаемых при разбиении множества переменных на k частей? В третьем параграфе четвертой главы дается ответ на этот вопрос.
Теорема 4.5 Для любой булевой функции f(x, ) существует разло жение f(x, ) = , (sf(x, ) s f(x, )).
x , Теорема 4.6 Для любой булевой функции f(x, ) имеют место раз ложения 1 f(x, ) = 2(s f(x, ) s f(x, )) 1 x 1 и 1 f(x, ) = 2(s f(x, ) s f(x, )).
1 x 1 В случае когда множество переменных разбивается на две части, можно сформулировать окончательный результат.
Винокуров С. Ф., Перязев Н. А. Разложение булевых функций на сумму произведений подфункций // Дискретная математика. 1993. Т. 5. № 3. С. 102Ц104.
Теорема 4.7 Разложение (4) при q = 2 имеет место для любой булевой функции тогда и только тогда, когда g1 {, , , }.
Теоремы 4.6 и 4.7 получены совместно с А. С. Зинченко.
Утверждение о том, что любую булеву функцию можно представить суммой произведений собственных подфункций, удалось распространить на функции k-значной логики не только при простом k, но и при произвольном k. Первым шагом в этом направлении оказался наш результат о том, что при простом k > 2 любую функцию k-значной логики можно представить суммой произведений собственных подфункций (теорема 4.8).
Теорема 4.9 Для любой функции k-значной логики f(, ) имеет место разложение f(, ) = sf s f, ( Ek) | | Ek|, Ek| тогда и только тогда, когда k = p1 p2 ... pm, где p1, p2,..., pm попарно различные простые числа (m 1).
Следующий результат (полученный совместно c Н. А. Перязевым) аналогичен соответствующему для булевых функций.
Теорема 4.10 Для любого k и любого t (t > 2) найдется функция f(x1,..., xn) и разбиение {x1,..., xn} = 1...t при котором f нельзя представить в виде 1 2 t f(1,..., t) = ...ts f s f ... s f 1 1 2 t | | 1Ek1|,...,tEkt| В оставшейся части параграфа приводятся примеры других полиномиальных представлений.
Теорема 4.11 Произвольную n-местную функцию f(x, ) можно пред ставить в полиномиальной форме следующего вида -1 f(x1,..., xn) = a, g(1,..., m) pg(x) sf(x, ), x x 1...m , где g(x), (m n) m-местная невырожденная функция, a эле мент, стоящий на (, ) месте в матрице (G[P(g(x1,..., xn))])k-1.
Если обозначить a = (a 0...a k-1),..., a = (a 0...a k-1), 1 1 1 i i i F (xi+1,..., xn) = (s0...0 f, s0...1 f..., sk-1...k-1f)t, x1...xi x1...xi x1...xi то справедлива Теорема 4.12 Для любой функции f(x1,..., xn) существует полиномиальное разложение вида 1 f = a ... a F (xi+1,..., xn) p g(x1) ... p g(xi), 1 i x1 xi 1...i где g(x) одноместная невырожденная функция, кронекерово произведение матриц.
Так как при простом k произвольную функцию можно представить полиномом по модулю k, то будем называть функцию полилинейной, если она линейна по любому своему аргументу. Другими словами, функция полилинейна, если каждая переменная в слагаемых встречается не более одного раза. Класс полилинейных функций является естественным обобщением класса булевых функций. Степень полилинейной функции определим как степень полинома, представляющего эту функцию.
Четвертый параграф этой главы посвящен полиномиальным представлениям полилинейных функций.
В теореме 4.13 устанавливается специальный базис, который используется при последующих разложениях. Полиномиальное разложение булевых функций по переменным обобщается в теореме 4.14.
Определим для функции g(x1,..., xn, y), зависящей от n + 1 переменной, матрицу G размерности 2n 2n, строки и столбцы которой занумеруем двоичными наборами и соответственно, следующим образом: G = (g), где g = h(), i, i {0, 1} и h(x1,..., xn) = (k - 1) g(x1,..., xn, 0) + g(x1,..., xn, 1).
Справедливо утверждение о разложении по системе функций, получаемых из одной функции с использованием собственных подфункций.
Теорема 4.15 Любая полилинейная функция f(x1,..., xn) имеет разложение вида n f(x1,..., xn) = g(x( ),..., x( ), (k - 1) f(1,..., m, xm+1,..., xn))() 1 n по полилинейной функции g(x1,..., xn, y), m n, i, i {0, 1} тогда и только тогда, когда функция g(x1,..., xn, y) имеет степень равную m + 1. Матрица коэффициентов A есть Gk-1, 1 m = (k - 1)1-m l-1 a...mg(x,..., x, 0) + 1, 1 1 m 1...m 1, если набор (1,..., m) содержит четное число 1;
a...m = k - 1, в противном случае.
Константа l зависит от выбора функции g(x1,..., xn, y).
Работы автора по теме диссертации 1. Пантелеев В.И. Полиномиальные канонические формы k-значных функций// Методы и системы технической диагностики/ Материалы 10 Международной конференции по проблемам теоретической кибернетики. Саратов, 1993. С. 134.
2. Пантелеев В. И. Полиномиальные разложения k-значных функций по невырожденным функциям // Математические заметки. 1994. Т. 55. № 1. С. 144Ц149.
3. Пантелеев В. И. Полиномиальные разложения полилинейных функций k-значной логики. Иркутск: Изд-во Иркут. ун-та, 1994. 23 с.
4. Пантелеев В. И. О полиномиальных разложениях полилинейных конечнозначных функций. 4-я межд. конф. по прикладной логике (Иркутск, 15-18 июня, 1995г.) Материалы. Иркутск, 1995. С. 59.
5. Пантелеев В. И., Перязев Н. А. Обобщенная интерпретация переменных и 8-значная логика //Природные ресурсы, экология и социальная среда Прибайкалья. Сб. науч. трудов. Т.III. Иркутск:
Изд-во Иркут. ун-та, 1995. C. 268Ц271.
6. Пантелеев В. И. Полиномиальные разложения k-значных функций по операторам дифференцирования и нормализации // Известия высших учебных заведений. Математика. 1998. № 1. С. 82Ц85.
7. Пантелеев В. И., Перязев Н. А. Об операторах булевых функций // Синтез и сложность управляющих систем: Материалы XI Межгосударственной школы-семинара (Нижний Новгород, 20Цнояб. 2000 г.). М.: Изд-во Центра прикладных исследований МГУ, 2001. Часть 2. С. 141Ц146.
8. Избранные вопросы теории булевых функций: Монография / А. С. Балюк, А. И. Гайдуков, В. И. Пантелеев и др. / под ред.
С. Ф. Винокурова, Н. А. Перязева. М.: Физматлит, 2001. 192 с.
9. Винокуров С. Ф., Пантелеев В. И. Полиномиальное представление булевых функций с использованием только остаточных функций // Труды XII Байкальской международной конференции. Иркутск:
Из-во Иркутского ун-та, 2001. Т. 5. С. 27Ц31.
10. Зинченко А. С., Пантелеев В. И. Специальные полиномиальные представления булевых функций // Компьютерные науки и информационные технологии: Материалы международной конференции (Саратов, 2002 г.). Саратов: Изд-во Сарат. ун-та, 2002. С. 28Ц29.
11. Пантелеев В. И. Представление булевых функций в виде суммы импликаций остаточных функций// Проблемы теоретической кибернети-ки. Тезисы докладов XIII Международной конференции. Ч II. М.: Изд-во центра прикладных исследований при механико-математическом ф-те МГУ, 2002. C. 140.
12. Пантелеев В. И. Пропозициональные логики при обобщенной интепретации переменных // Труды Второй Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в вузе. Иркутск: Изд-во Иркут. гос. пед. ун-та, 2003.
С. 82Ц83.
13. Зинченко А. С., Пантелеев В. И. О представлении функций конечнозначной логики пучками операторов // Алгебра, логика и кибернетика: Материалы Международной конференции, посвященной 75-летию со дня рождения профессора А. И. Кокорина (Иркутск, 25Ц28 авг. 2004 г.). Иркутск: Изд-во Иркут. гос. пед. ун-та, 2004. С. 139Ц142.
14. Зинченко А. С., Пантелеев В. И. Полиномиальные операторные представления функций k-значной логики // Дискретные модели в теории управляющих систем: Труды VI Международной конференции, посвященной 80-летию со дня рождения С. В. Яблонского (Москва, 7Ц11 дек. 2004 г.). М.: Издательский отдел Факультета ВМиК МГУ им. М. В. Ломоносова, 2004. С. 31Ц32.
15. Зинченко А. С., Пантелеев В. И. О нижней оценке сложности операторных полиномиальных форм для функций k-значной логики // Проблемы теоретической кибернетики: Материалы XIV Международной конференции, посвященной 80-летию со дня рождения С. В. Яблонского (Пенза, 23Ц28 мая 2005 г.) / под ред. О. Б.
упанова. М.: Изд-во механико-математического факультета МГУ, 2005. C. 51.
16. Пантелеев В. И., Перязев Н. А. Разложение функций k-значной логики в сумму произведений собственных подфункций // Проблемы теоретической кибернетики: Тезисы докладов XIV Международной конференции, посвященной 80-летию со дня рождения С. В. Яблонского (Пенза, 23Ц28 мая 2005 г.) / под редакцией О. Б.
упанова. М.: Изд-во механико-математического факультета МГУ, 2005. C. 114.
17. Пантелеев В. И., Перязев Н. А. Логика предикатов при обобщенной интерпретации переменных // Вестник Бурятского университета.
Серия 13: Математика и информатика. Вып. 2. Улан-Удэ: Изд-во Бурятского госуниверситета, 2005. С. 39Ц44.
18. Зинченко А. С., Пантелеев В. И. Полиномиальные операторные представления функций k-значной логики // Дискретный анализ и исследование операций. Сер. 1. 2006. Т. 13. № 3. С. 13Ц26.
19. Пантелеев В. И. О недоопределенных булевых функциях// Синтаксис и семантика логических систем: Материалы российской школысеминара. Иркутск: изд-во ГОУ ВПО ИГПУ, 2006. С. 78Ц79.
20. Пантелеев В. И., Перязев Н. А. Недоопределенные булевы функции и булевы уравнения // Дискретные модели в теории управляющих систем: Труды VII Международной конференции. М.: МАКС Пресс, 2006. С. 262Ц265.
21. Зинченко А. С., Пантелеев В. И. Бинарные термы в полиномиальных представлениях булевых функций // Математические заметки. 2007. Т. 81. Вып. 2. С. 217Ц225.
22. Пантелеев В. И., Перязев Н. А. О представлении функций kзначной логики суммой произведений остаточных подфункций // Дискретная математика. 2007. Т. 19. Вып. 2. С. 94Ц100.
23. Пантелеев В. И. О предполных классах недоопределенных функций алгебры логики // Алгебра и логика: Mатериалы международного российско-китайского семинара (Иркутск, 6Ц11 авг. 2007 г.).
Иркутск: Изд-во Иркут. гос.пед. ун-та, 2007. С. 81Ц82.
24. Пантелеев В. И., Перязев Н. А. Конечнозначная логика предикатов при обобщенной интерпретации переменных // Современная логика: проблемы теории, истории и применения в науке: Материалы X Общероссийской научной конференции (Санкт-Петербург, 26-июня 2008г). СПб., 2008. С. 299Ц301.
25. Пантелеев В. И. О предполных классах недоопределенных частичных булевых функций // Проблемы теоретической кибернетики:
Тезисы докладов XV международной конференции (Казань, 2Циюня 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.