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

ФГБОУ ВО Московский государственный университет имени М. В. Ломоносова

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

Об условиях равномерности систем функций многозначной логики

Специальность 01.01.09 — дискретная математика и математическая кибернетика

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

Тарасов Павел Борисович

29 ЯНВ 2015

Москва — 2014

005558084

Работа выполнена на кафедре дискретной математики механико-математического факультета ФГБОУ ВО «Московский государственный университет имени М. В. Ломоносова»

Научный руководитель: Колпаков Роман Максимович

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

Коршунов Алексей Дмитриевич,

Официальные оппоненты: доктор физико-математических наук,

ведущий научный сотрудник, лабаратория дискретного анализа, ФГБУН «Институт математики им. С. JI. Соболева СО РАН»

Стеценко Владимир Алексеевич,

кандидат физико-математических наук, доцент, ФГБОУ «Московский педагогический государственный университет», математический факультет, кафедра теоретической информатики и дискретной математики

Ведущая организация: ■ ФГБУН «Институт прикладной математики им.

М. В. Келдыша РАН»

Защита диссертации состоится 13 февраля 2015 г. в 16 часов 45 минут на заседании диссертационного совета Д.501.001.84 на базе «ФГБОУ ВО Московский государственный университет имени М. В. Ломоносова» по адресу: Российская Федерация 119991, Москва, ГСП-1, Ленинские горы, д. 1, ФГБОУ ВО МГУ имени М. В. Ломоносова, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в Фундаментальной библиотеке ФГБОУ ВО "Московский государственный университет имени М. В. Ломоносова"по адресу: Москва, Ломоносовский проспект, д. 27, сектор А, 8 этаж и на сайте http ://mech.math.msu.su

Автореферат разослан 13 января 2015 года.

Ученый секретарь диссертационного совета Д.501.001.84, созданного на базе ФГБОУ ВО МГУ им. М. В. Ломоносова, доктор физико-математических наук, профессор

Иванов Александр Олегович

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

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

Синтез и сложность управляющих систем является одним из важнейших направлений исследований в математической кибернетике. Класс формул над конечными функциональными системами, реализующих функции ^-значной логики > 2), — один из основных модельных классов управляющих систем. Задача изучения сложности формул заключается в построении формулы, которая реализует заданную функцию и является оптимальной относительно некоторой меры сложности. Наиболее часто используемыми мерами сложности для формул являются число символов переменных, входящих в формулу, (называемое сложностью формулы) и глубина формулы. Сложность формулы можно интерпретировать как ее «стоимость», а глубину — как время ее вычисления, при условии, что все вычисления можно производить параллельно. Очевидным способом построения оптимальной формулы является перебор, но на практике такой метод не может быть использован в силу экспоненциального роста объема вычислений от числа переменных заданной функции. Поэтому важное значение имеет задача построения формул, близких к оптимальным, без использования перебора.

Большое число методов синтеза формул было разработано для конечных систем, состоящих из булевых функций. Для полных базисов асимптотически оптимальные методы синтеза как формул, так и некоторых других классов управляющих систем, были разработаны О. Б. Лупановым1. Оценки глубины формул в полных базисах были получены в работах С. Б. Гашкова2 и С. А.

х Лупанов О. Б. Об одном методе синтеза схем // Известия ВУЗов. Радиофизика. Т. 1, №1, 1958. С. 120-140.

Лупанов О. Б. Об асимптотических оценках сложности формул, реализующих функции алгебры логики // ДАН СССР. 128, 3. 1959. С. 464-467.

Лупанов О. Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики. Вып.

3. М.: Физматгиз, 1960. С. 61-80.

Лупанов О. Б. О реализации функции алгебры логики формулами из конечных классов (формулами ограниченной глубины) в базисе V, -1 // Проблемы кибернетики. Вып. 6. М.: Физмаггиз, 1961. С. 63-97.

Лупанов О. Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики. Вып. 10. М.: Физматгиз, 1963. С. 63-97.

Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принциие локального кодирования // Проблемы кибернетики. Вып. 14, М.: Физматгиз, 1965. С. 21-ПО.

Лупанов О. Б. О сложности реализации степеней булевой (п. п)-функшш // Вестник Моск. ун-та. Матем. Механ. 1993. №1. С. 59-67.

2Г:нш;ов С. Б. О глубине булевых функций // Проблемы кибернетики. Вып. 34. М.: Паука, 1978. С. 265-268.

Ложкина3. Сложность и глубина формул также изучалась для случая функционально неполных систем функций двузначной и Аг-значной логики при к > 3 (см., например, работы А. Б. Угольникова4 , А. Е. Андреева5 и А. А. Андреева6).

В последнее время все более актуальной становится проблема вычисления функций с помощью распараллеленных вычислений. Поскольку время распараллеленного вычисления формулы прямо пропорционально ее глубине, проблема минимизации таких вычислений сводится к задаче построения по заданной формуле эквивалентной формулы (то есть, формулы, реализующей ту же функцию), имеющей наименьшую возможную глубину. Если функцию / можно реализовать над конечной системой функций А формулой глубины не более I, то несложно получить верхнюю оценку Ь < п1 сложности Ь реализации функции / формулами над А, где тг — максимальное число переменных у функций из А. Таким образом, глубина реализации функции формулами над А не может быть меньше по порядку логарифма сложности этой реализации. В случае, если эта нижняя оценка достигается, говорят о равномерности системы А: конечная система функций А называется равномерной, если существуют такие константы си (I (зависящие только от А), что для любой функции /, реализуемой формулами над А, выполнено неравенство

Ш)<сЛоё2ЬА(/) + с1, (1)

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

Пусть к > 2. Обозначим через Еь множество {0,.... /с — 1}, а через Д. множество всех функций &-значной логики. Вопросы, связанные с равномерностью систем функций из Р^, изучались во многих работах. В работах В. М. Храп-

3Ложкин С. А. О связи между глубиной и сложность эквивалентных формул и о глубине монотонных функций алгебры логики // Проблемы кибернетики. Вып. 38. М.: Наука, 1981. С. 269-270.

4 Угольников А. Б. Синтез схем и формул в неполных базисах // Докл. АН. СССР. 1979. 249, 1. 60-62.

Угольников А. Б. Синтез схем и формул в неполных базисах // Препринт ИПМ АН СССР. 1980. Вып. 112.

Угольников А. Б. О глубине формул в неполных базисах // Математические вопросы кибернетики, вып. 1. М.:

Наука, 1988. С. 242-245.

Угольников А. Б. О сложности реализации формулами одной последовательности функций многозначной логики // Математические вопросы кибернетики, вып. 2. М.: Наука, 1989. С. 174-176.

5 Андреев А. Е. О сложности монотонных функций //Вестник Московского университета. Сер. 1. Математика. Механика. М.: Нзд-во МГУ, 1985. Выл 4. С. 83-87.

Андреев А. Е. О синтезе функциональных сетей // Докг. диссертация. М.: МГУ им М. В. Ломоносова, 1985.

6 Андреев А. А. Об одной последовательности функций многозначной логики // Вестник Московского университета. Сер. 1. Математика. Механика. 2011. №6. С. 3-7.

ченко7 и Ф. Спиры8 независимо была доказана равномерность всех конечных полных систем булевых функций. Методы, предложенные в работах В.М. Храп-ченко и Ф. Спиры, нетрудно перенести на полные системы функций многозначной логики, однако они существенно используют полноту систем. В работе И. Вегенера9 установлена равномерность всех конечных систем, порождающих класс M всех монотонных булевых функций. А. Б. Угольниковым10 установлена равномерность всех конечных систем булевых функций (см. также работу M. Е. Рагаза11). В данной работе также приведен пример систем функций из Р3, не являющихся полиномиально экивалентными.

Таким образом, вопрос о равномерности конечных систем функций из Ро решен полностью, поэтому приобретает актуальность задача исследования равномерности систем функций А-значной логики при к > 3. Задача о равномерности в P¡¡ является существенно более сложной в связи с тем, что для замкнутых классов булевых функций существует удобное описание, приведенное в работах Э. Поста12, в то время как для замкнутых классов функций из Рj. при к > 3 описание отсутствует, что связано с существованием принципиальных отличий многозначных логик от двухзначной, в частности, с континуальностью13 семейства всех замкнутых классов fc-значной логики при к > 3 и отсутствием описания всех конечно-порожденных классов fc-значной логики.

Ряд публикаций посвящен задаче о соотношении глубины и сложности формул над конечными системами функций, порождающими предполные классы Pk при к > 3. Полное предикатное описание таких предполных классов получено в работах И. Розенберга14. Согласно данному описанию, все предпол-

7 см. Яблонский С. В., Козырев В. П. Математические вопросы кибернетики // Информационные материалы Научного совета по комплексной проблеме "Кибернетика"АН СССР. Выл. 19а. М.: Издв-во МЭИ. 1997.

*Spira Р. М. On time-hardware complexity tradeoffs for Boolean functions // Proc. 4th Hawai Symposium on System Sciences, North Hollywood, 1971, Western Periodicals Company, P. 525-527.

9 Wegener I. Relating Monotone Formula Size and Monotone Depth of Boolean Functions // Information Processing Letters, 16. 1983. P. 41-42.

10Угольников А. Б. О полиномиальной эквивалентности формул для замкнутых классов двузначной логики // VII Всесоюзная конференция "Проблемы теоретической кибернетики": тезисы докладов. Часть 1. Иркутск: Изд-во Иркутского государственного университета. 1985. С. 194-195.

Угольников А. Б. О глубине и полиномиальное эквивалентности формул для замкнутых классов двухзначной логики. Математические заметки, том 42, выпуск 4, октябрь 1987. М.: Наука, 1987. С. 603-612.

1 !Ragaz M. Е. Paiallelizable algebras. Archiv fur mathematische Logik und Grundlagenforschung 26 (1986/7)) и приведены примеры неравномерных систем функций из Я). Р. 77-99.

12 PoslE. L. Introduction to a general theory of elementary propositions // Amer. J. Math. 1921. 43, N3. 163-185.

Post E. L. Two valued iterative systems of mathematical logic // Annals of Math. Studies. Princenton-London: London Univ. Press. 1941. 5. 122.

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

14 Rosenberg 1. La structure des fonctions de plusieurs variables sur un ensemble fini. C. R. Acad. Sei. Paris Ser A,

260 (1965), 3817-19.

ные классы функций Д. при к > 3 можно разделить на следующие семейства: классы линейных функций — классы типа классы функций, сохраняющих разбиения множества Еь — классы типа Е; классы функций, сохраняющих сильно гомоморфные прообразы элементарных /1-адических отношений, — классы типа В; классы функций, сохраняющих центральные отношения, — классы типа С; классы самодвойственных функций — классы типа Р; классы монотонных функций — классы типа О.

Пусть р — отношение частичного порядка на Ед., такое, что для любых двух элементов а и Ь из (Ец, р) существуют Ы1р(а, 6) и шДа, 6). Класс всех функций, сохраняющих отношение р, называется классом типа О*. Конечно-порожденные предполные классы функции, монотонных относительно частично упорядоченного множества ширины 2, называются классами типа <0>2. Классы типа С, сохраняющие унарные и бинарные центральные отношения, называются классами типа С1 и Сг соответственно.

Равномерность всех конечных систем, порождающих предполные классы Рз, анонсирована в работе Л. И. Ахметовой15. Равномерность любых конечных систем, порождающих предполные классы типов Ь, Е, В, Р, 0#, С1 и Сг в Р^, установлена в работе Р. Ф. Сафина16. Кроме того, в этой работе для любого к > 3 доказано существование равномерных порождающих систем для классов типа С. Для некоторых классов типа ©2 в работе О. С. Дудаковой17 показано существование в этих классах функции специального вида, поэтому применением метода из работ В.М. Храпченко и Ф. Спиры нетрудно установить равномерность всех конечных систем, порождающих эти классы. В работе Д. Ю. Дударова'8 анонсирована равномерность порождающих систем некоторых предполных классов монотонных функций в при к > 7.

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

Ш)<с]о&ЬА{Г) + <1.

**Ахметова Л. И. О глубине формул для предполных классов трехзначной логики // Методы и системы технической диагностики, выпуск 18. Саратов: Изд-во Саратовского университета.

Х(*Сафин Р.Ф. О соотношении между глубиной и сложностью формул для предполных.классов к-значной логики // Математические вопросы кибернетики. Вып 13. М. Физматлит. 2004. С. 223-278.

17 Дудакова О.С. О конечной порожденности предполных классов монотонных функций многозначной логики. // Математические вопросы кибернетики. Вып 17. М.: Физматлит, 2008. С. 13-104.

хгДудоров Д. Ю. Материалы X Межд. сем. "Дискр. матем. и ее прилож." М. 2010. 18-20.

С задачей нахождения достаточных условий равномерности систем функций связана задача о сравнении базисов. Конечные системы функций А и В, такие, что [.4] = [В], называются полиномиально эквивалентными, если существуют такие константы с'1 и со, что для любой функции / 6 [Л] выполнены неравенства

< -МЯ < ВД).

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

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

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

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

1. Любая конечная система А функций из Ри я, такая, что проекция системы А на множество Еа порождает мажоритарную функцию, равномерна, (через обозначается множество всех функций /с-значной логики принимающих значения из множества {0,...,« — 1})

2. При к < 7 все конечные системы функций из Р/;, порождающие предпол-ные классы, равномерны.

3. Все конечные системы функций, порождающие предполные классы Р^ типа С, равномерны при к > 3.

4. Доказана равномерность конечных систем функций Рк.2, проекция которых не лежит целиком ни в одном из множеств19 Ож, Iх, К, П, Ь.

''Обозначения для замкнутых классов булевых функций взяты из книги: Угольников А.Б. Классы Поста. Учебное пособие: М.: Изд-во ЦПИ при механико-матсматичсском факультете МГУ имени М.В. Ломоносова. 64 с.

7

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

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

Апробация работы. Основные результаты работы докладывались на:

1. Специальном семинаре «Функции многозначной логики и смежные вопросы» под руководством проф. А. Б. Угольникова, проф. Р. М. Колпакова и проф. С. Б. Гашкова (неоднократно в 2010 - 2013 гг.),

2. Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2012» (г. Москва, 9-13 апреля 2012 г.),

3. XI Международном семинаре «Дискретная математика и ее приложения» (г. Москва, 18 - 23 июня 2012 г.),

4. Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2013» (г. Москва, 8 -13 апреля 2013 г.),

5. CSEDays. Theory 2013. Algorithms and Complexity (г. Екатеринбург, 29 июня - 1 июля 2013 г.),

6. XVII Международной конференции «Проблемы теоретической кибернетики» (г. Казань, 6-20 июня 2014 г.) ,

7. Third Russian Finnish Symposium on Discrete Mathematics (г. Петрозаводск, 15-18 сентября 2014 г.).

Публикации. Основные результаты автора опубликованы в 7 работах автора [1-7], 3 из которых изданы в журналах, рекомендованных ВАК.

Объем н структура работы. Диссертация состоит из введения и пяти глав. Полный объем диссертации — 87 страниц. Список литературы содержит 68 наименований.

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

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

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

Пусть /(.ть ..., хп) - функция из Рк.я, а д(х ь ...,х„) — функция из Р3, такие, что для любого а 6 Е" выполнено равенство /(5) = д(о). Функцию д будем называть проекцией функции / и обозначать через рг9/. Пусть А С Рк я. Положим рг3/1 = {рг,/|/ 6 А}. Множество рг,Л будем называть проекцией системы А на Р3.

Функцию /(.Т[..... хп) € Рк будем называть мажоритарной, если для любых а, 0 € Еь выполнены равенства

/(а, а,..., а, 0) = /(а, а,..., а, /3, а) = /(/3, а,а,... ,а) = а.

Множество всех мажоритарных функций из Рк обозначим через 1Ч,4ь

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

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

Теорема 1. Произвольная конечная система функций из проекция на Р$ которой порождает мажоритарную функцию, равномерна.

В качестве следствия из данного утверждения с использованием результатов работ Р. Ф. Сафина и С. С. Марченкова20 получены следующие теоремы:

Теорема 2. Все конечные системы функций /с-значной логики, порождающие предполные классы типа С, равномерны при любом к > 3.

Теорема 3. При к < 7 все конечные системы функций, порождающие предполные классы Л-значной логики, равномерны.

Теорема 4. Все конечные системы функций из Р^ъ проекция на Рг которых не содержатся целиком ни в одном из множеств О00, Iх, К. О. Ь, равномерны.

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

20Марченнов. С С. Об разложениях класса Рк над предполными классами // Дискрет, матем., 5:2 (1993), 98-110.

Теорема 5. Пусть А — конечная система функций из /\2, такая, что [рг2.4] = М и функции из А зависят не более, чем от п переменных. Тогда система А равномерна. При этом для произвольной функции / 6 [А] коэффициенты с и с1 из соотношения 1 определяются по формулам

Ь2 2(п+1)2-1 ¿(Л)<2шах(Х.4(0)Х.4(1))(и+1)2

и д(х 1,... ,х7) — функция из [А], реализуемая формулой над А с наименьшей глубиной, такая, что рг2д = Х\Х2 V хухз V V х^хс, V х5хт),

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

Приведем необходимые определения. Пусть /(.Т],..., .г„) 6 Рк.ъ г 6 {1,..., п}, /3 е Ек- Положим

М? = {рг2/(аь • •., оц-\,х, а;,... ,ап_1)[ а € Е У* = {а в Е%~1\ рг2/(аь ..., оц-1,у, а,,..., а^) ф 0,1},

Лх, = 1(хъ . . . Р,ХМ, . . . ,Хп).

Для произвольных множества X = {х^,..., } С {,п,..., .г,,} и набора 5 е Е1к положим

м? = и Л/;, л?/ = и {А//},

х€Х х€Х

V? = {а е ЕГ*I рг2/|{х,.....Ф !}•

Будем говорить, что монотонная функция ... ,хп) £ Рк.2

обладает свойством # уровня г по множеству переменных X = {.г^,..., Хц} С {.ть ..., :сп} относительно замкнутого класса В С Рк2 и набора а 6 если существует функция д(х 1,..., хп-ч, у\,..., уг) 6 В,

такая, что:

1. для любого /3 е V* выполнено рг2<?(/3, у) 0 [{0,1}];

2."если {0, х} С Щ С {{0, а:}, {1,ш}, {0,1, ж}} и а в V*, то рг2.д(5,у) € Мш \ О00;

3. если {1, ж} С Л?/ С {{0, ж}, {1, ж}, {0,1, ж}} и 5 6 У/, то рг2<7(5, у) е Л/01 \

4. если М* = {{0,1,.т}} и а € V*, то рт2д(а,у) £ ГМ2-

Множество функций /(хь..., .т„), таких, что / обладает свойством # уровня г по множеству переменных X = {х!п..., С {х\,..., относительно замкнутого класса В и набора а 6 Е1^ 4, будем обозначать через г). Положим

#х(В,п,г)= П ШВ,п,г)-

5е4Х1

#(В,г)=У П #х(В,п,т)-

пеП ХС{х1.Х2,-.х„}

Будем говорить, что система Л монотонных функций из Г\,2 обладает свойством #, если А С #([/1], г) для некоторого г > 3.

Основным результатом параграфа является следующая теорема:

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

В третьей главе вводится следующее обозначение

#1(5, г) = и П #м(В,п,г). пеНге{1,....п}

Будем говорить, что система А монотонных функций из Р<..2 обладает свойством #ь если А С #1([Л]. г) для некоторого г > 3.

Основным результатом главы является следующая теорема:

Теорема 7. Произвольная конечная система монотонных функций из квази-равномерна тогда и только тогда, когда А обладает свойством #1.

Достаточность условия теоремы 7 доказана в параграфе 3.1, а необходимость этого условия — в параграфе 3.2. В параграфе 3.3 доказано, что за конечное время можно проверить, обладает ли система свойством #х. Тем самым предложена эффективная процедура проверки квази-равномерности конечных

СИСТеМ МОНОТОННЫХ фуНКЦИЙ ИЗ

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

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

В диссертации принята следующая нумерация утверждений: леммы, теоремы и утверждения нумеруются парами чисел — номер главы и номер утверждения, а следствия нумеруются по порядку для каждого утверждения.

Благодарности

Основная часть диссертации была выполнена под руководством доктора физико-математических наук, профессора

Александра Борисовича Угольникова , которому автор выражает благодарность за постановку задачи и научное руководство. Также за научное руководство, обсуждение результатов и внимание к работе автор благодарит научного руководителя, доктора физико-математических наук, профессора Р. М. Колпа-кова. Автор выражает благодарность кандидату физико-математических наук О. С. Дудаковой за обсуждение результатов работы.

Публикации автора по теме диссертации

1. Тарасов П. Б. О равномерности некоторых систем функций многозначной логики // Вестн. Моск. ун-та. Матем. Механ. 2013. № 2. 61-64.

2. Тарасов П. Б. О некоторых достаточных условиях равномерности систем функций многозначной логики // Вестн. Моск. ун-та. Матем. Механ. 2013. 5. 41-46.

3. Тарасов П. Б. Некоторые условия равномерности функций fc-значной логики принимающих значения 0 и 1 // Ученые записки Казанского университета. 2014. №3. 123-129.

4. Тарасов П. Б. Равномерность некоторых конечных систем функций многозначной логики // Тезисы XI Международного семинара "Дискретная Математика и ее приложения" (Москва, МГУ, 18 - 23 июня 2012 г.). Под редакцией О. М. Касим-Заде. М.: Изд-во механико-математического факультета МГУ, 2012. С. 213-215.

5. Тарасов П. Б. Several Sufficient Conditions For Uniformity of Finite Systems of Many-valued Logic // CSEDays. Theory 2013 (г. Екатеринбург, 29 июня - 1 июля 2013 г.). С. 47-49.

6. Тарасов П. Б. О некоторых необходимых условиях равномерности систем функций многозначной логики // Материалы XVII Международной конференции "Проблемы теоретической кибернетики" (Казань, 16-20 июня 2014 г.) Под редакцией Ю. И. Журавлева. Казань: Отечество, 2014. С. 232 -234.

7. Тарасов П. Б. Several Necessary Conditions For Uniformity of Finite Systems of Many-valued Logic // Третий Российско-Финский симпозиум по дискретной математике. Расширенные тезисы докладов, (г. Петрозаводск, 15 - 18 сентября 2014 г.) Под редакцией В. В. Мазалова. С. 129-132.

Подписано в печать 10.12.2014г. Бумага офсетная. Печать цифровая. Формат 60x90/16. Усл. печ. л. 1. Заказ № 177. Тираж 100 экз. Типография «КОПИЦЕНТР» 119234, г. Москва, Ломоносовский пр-т, д.20 Тел. 8 (495) 213-88-17