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

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

004Ы<м»

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

Федорова Валентина Сергеевна

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

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

Автореферат

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

1 1 НОЯ 2010

Москва — 2010

004612381

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

Научный руководитель: доктор физико-математических наук,

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

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

профессор механико-математического факультета МГУ Буевич Вячеслав Александрович;

кандидат физико-математических наук, доцент Московского энергетического института (технического университета) Мещанинов Дмитрий Германович.

Ведущая организация: Вычислительный центр РАН.

Защита дисертации состоится 12 ноября 2010 г. в 11:00 на заседании диссертационного совета Д 501.001.44 в Московском государственном университете имени М. В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМК МГУ. С текстом автореферата можно ознакомиться на официальном сайте ВМК МГУ имени М. В. Ломоносова http://www.cmc.msu.ru в разделе ,Даука" — „Работа диссертационных советов" — „Д 501.001.44".

Автореферат разослан 8 О ктЛ5р& 2010 г.

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

Н. П. Трифонов

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

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

Одно из простейших функциональных уравнений — это уравнение Коши f(x + у) = /(х) + f{y). Его непрерывные решения имеют вид f(x) = С ■ х, где С — произвольная константа.

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

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

aob = boa, (о о Ь) о с = а о {Ь о с),

где о — символ некоторой бинарной операции. Но если представить эту операцию в эквивалентном виде а о 6 = f(a,b), то получится как раз то, что обычно называют функциональным уравнением:

/М) = /(М), /(/(а,Ь),с) =/(а,/М).

Этот пример показывает, что функциональные уравнения можно также рассматривать как выражение некоторого свойства, характеризующего то или иное множество функций. Так, для периодических с периодом 7Г функций — это /(х + п) = f(x), а для четных функций — f(x) = f{—x).

В теории аналитических функций функциональные уравнения часто применяются для введения новых классов функций. Например, автоморфные функции описываются функциональными уравнениями вида f(saz) = f(z),

где ва есть элемент некоторой счетной подгруппы группы дробно-линейных преобразований комплексной плоскости, двоякопериодические функции — парой функциональных уравнений /(г + а) = f(z) и f{z + Ь) = /(2).

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

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

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

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

Ф Уи ■ • ■, хп ® уп) © р(0,..., 0) = 1,..., х„) ® <р(уи ...,уп),

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

у(хь..., хп) V <р(х 1 V ух,..., хп V уп) = <р(х 1 V г/ь..., хп V Уп),

1К лини С. К. Введение в метаматематику. М.: ИЛ, 1957.

2Бардзинь Я. М., Трахтенброт Б. А. Конечные автоматы (поведение и синтез). М.: Наука, 1970.

'Кобринский Н. Е., Трахтенброт Б. А. Введение в теорию конечных автоматов. М.: Физматгиз, 1962.

4Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М.: Наука, 1986.

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

<p(xi, ...,жп) = ..., хп).

Также подобные примеры можно найти в различных работах, касающихся, в частности, замкнутых классов булевых функций5,6,7,8,9,10,11.

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

Цели диссертации:

• исследовать множества решений систем функциональных уравнений;

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

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

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

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

5Избранные вопросы теории булевых функций. Под редакцией Винокурова С. Ф. и Перязева H. А. М.: Физматлит, 2001.

6Гаврилов Г. П. Индуктивные представления булевых функций и конечная порождаемостъ классов Поста. Алгебра и логика. 1984. Т. 23, вып. 1. С. 88-99.

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

8Марченков С. С. Конечная порождаемостъ замкнутых классов булевых функций. Дискретный анализ и исследование операций. Серия 1. 2005. Т. 12, № 1. С. 101-118.

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

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

uKuntzman J. Algèbre de Boole. Paris: Dunod, 1965.

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

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

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

Публикации и апробирование. Результаты диссертации были представлены на VI Молодежной научной школе по дискретной математике и ее приложениям (Москва, 16 - 20 апреля 2007 г.), XVII Международной школе-семинаре „Синтез и сложность управляющих систем" имени академика О. Б. Лупанова (Новосибирск, 27 октября - 1 ноября 2008 г.), Восьмой Международной научной конференции „Дискретные модели в теории управляющих систем" (Москва, 6-9 апреля 2009 г.), XVIII Международной школе-семинаре „Синтез и сложность управляющих систем" имени академика О. Б. Лупанова (Пенза, 28 сентября - 3 октября 2009 г.), а также докладывались на семинаре кафедры математической кибернетики факультета вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова „Дискретные функции и сложность алгоритмов".

Результаты диссертации опубликованы в 8 работах, пять из которых в соавторстве с научным руководителем профессором С. С. Марченковым. Три работы опубликованы в журналах, рекомендованных ВАК РФ.

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

Краткое содержание диссертации

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

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

В параграфе 1.1 определяются основные понятия и терминология, принятые при изложении результатов.

Пусть к > 2, Ек = {0,1,..., к-1}, Е? = Ек х Ек X ... х Ек — п-ая декар-

4 V /

П

това степень множества Ек- Отображение / : Е% Ек назовем п-местной функцией к-значной логики (в случае к = 2 — булевой функцией). Рк — множество всех функций й-значной логики (соответственно, Р% — множество всех булевых функций). Если <2 С Рк и п ^ 1, то через С^") обозначим множество всех п-местных функций из <2-

Определим язык функциональных уравнений многозначной логики. Предполагаем, что каждая функция из Рк имеет индивидуальное обозначение. Для обозначения п-местных функций из Рк используем символы которые называем функциональными константами. Наряду с функциональными константами рассматриваем функциональные переменные, для которых используем символы (р[п>, с областью значений В случае, когда это не приводит к недоразумению, верхние индексы у функциональных переменных будем опускать. Кроме функциональных переменных используем обычные индивидные переменные х\, ... с областью значений

Пусть Я С. Р^ Определим понятие терма над ф: всякая индивидная переменная есть терм над <2; если ..., Ьп — термы над <3, — функциональная константа, служащая обозначением функции из <5, ср^ — функциональная переменная, то выражения

суть термы над ф.

Равенством над <2 называем любое выражение вида ¿1 = ¿2> где ~ термы над С^. Равенства над <3 считаем также функциональными уравнение ями над

Пусть ■ ■ •, — все функциональные переменные, входящие в уравнение = ¿2- Тогда решением уравнения = ¿2 называем систему {/-711',..., &т)} функций из Рк, которая после замены каждой переменной

соответствующей функциональной константой превращает уравнение = ¿2 в тождество относительно всех входящих в уравнение индивидных переменных. Отметим, что решением уравнения над <2 могут быть функции, не входящие в множество С}.

Если 5 — конечная система уравнений, то решением системы уравнений 5 называем систему функций из Р*, которая является решением каждого уравнения, входящего в систему 5.

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

Пусть — главная функциональная переменная системы уравнений а и Р С Говорим, что множество функций Р определяется системой уравнений 5, если Р является множеством всех тех п-местных функций, которые входят в решения системы Е в качестве компоненты по переменной <р . Наконец, говорим, что множество функций Р определимо системой уравнений над если существует система уравнений над С}, которая определяет множество Р.

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

Теорема 1. Пусть к ^ 2, С} — замкнутый класс функций из Р* и для любого п ^ 1, любого набора ..., ап) £ Щ найдутся такие функции д\,...,дп из <2^ и {х} и такой элемент Ъ в Ей, что

(аь...,ап) = (д1(Ь),...,дп(Ь)).

Тогда для любой функции д{х\,...,хгп) 6 <3 существует система функциональных уравнений над С^1' с одной функциональной переменной, единственным решением которой служит д.

В дальнейшем нам понадобится тернарный дискриминатор р, который определяется следующими соотношениями:

Р(х,у,г) = |

2, если х = у, х в противном случае.

Если а, Ь £ Ек и а < Ь, то пусть

тгхаь{х,у) = I если е М-

4 ' [ ж в остальных случаях.

Пусть 7г — перестановка на множестве Ек и / 6 Рк- Функция /*(х1,..., хп) = 7г-1(/(я"(х1),..., 7г(а;п))) называется двойственной к функции / относительно перестановки 7г. Функция, двойственная самой себе относительно перестановки 7Г, называется самодвойственной относительно перестановки 7Г.

Теорема 2. Пусть к ^ 2, п > 1, Р С Р^"' и Р ф %. Тогда существует система функциональных уравнений с функциональными константами р,тахо1, тахо2> ■ • •, тах^^-ь которая определяет множество К

Теорема 3. Пусть к 2, п ^ 1 и Р — непустое множество функций из которое для любой перестановки п на множестве Ек наряду с любой функцией / содержит двойственную ей функцию Тогда существует система функциональных уравнений с единственной функциональной константой р, которая определяет множество Р.

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

Функция сохраняет 0 (сохраняет 1), если на наборе, состоящем из всех нулей, она принимает значение 0 (соответственно, на наборе, состоящем из всех единиц, она принимает значение 1). Функция }{х\,..., хп) называется самодвойственной, если справедливо следующее равенство:

¡(ХЪ...,ХП) = /(Ж1,...,®„).

Пусть Тр, «У суть соответственно классы всех функций, сохраняющих О, всех функций, сохраняющих 1, и всех самодвойственных функций. Положим

Т01 — ТоП 21, 5о1 = 5 П Тог.

Теорема 4. Для каждого из классов /*>2) То, Т1!, То1, £01 тьустиь символ ф обозначает соответственно множество функций

{0,1}, {0}, {1}, {¿с}, 0.

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

Теорема 5. Пусть п ^ 1, Р С Р^ и Р ф Тогда существует система функциональных булевых уравнений с функциональными константами V, & и двумя функциональными переменными, которая определяет множество Р.

Теорема 6. Пусть п ^ 1 и F — непустое подмножество множества которое наряду с любой функцией содержит двойственную ей функцию. Тогда существует система функциональных булевых уравнений с двумя функциональными переменными и без функциональных констант, которая определяет множество F.

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

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

Определим оператор SFE-замыкания. Пусть Q С Pk. Замыканием множества Q относительно систем функциональных уравнений (коротко SFE-замыканием) назовем множество всех тех функций из Pk, которые могут быть получены как единственное решение некоторой системы функциональных уравнений над Q. SFE-замыкание множества Q обозначим через SFE[Q], Множество Q назовем SFE-замкнутым, если Q — SFE[Q]. Понятия SFE-полпоты, SFE-предполноты и SFE-порождающей системы вводятся по аналогии с соответствующими понятиями для операции суперпозиции.

Пусть для i G Ек

j./x\ = J если * = *>

| 0 в остальных случаях. Теорема 7. Справедливы следующие равенства:

1. SFE[0,1,... ,k — 1] — Pk 2).

2. Для любого s е Ек имеет место SFE[0,1,..., s — 1, s-f 1, • ■ •, к — 1] = Pk (fc> 3).

8. SFB[?o, .......Jfc-i] = A

4. Для любого se Ек имеет место SFEjjo, j\,..., js-i, ja+i, ■ • •, jk-i] = Рк

Отметим, что вместо функций ¿о(х),...,Зк-\{х) в четвертом пункте теоремы 7 можно использовать функции

где j, г — различны, г, j, г £ Ек.

Пусть р(хI,..., хт) — предикат на множестве Ек, то есть отображение р : Е™ —{Г, F}, где Т, F — истинностные значения „истина" и „ложь". Набор (а 1,..., ат) из .E^1 удовлетворяет предикату р, если р{а\,..., ат) = Т.

Говорят, что функция /(xi,.. .,хп) £ Рк сохраняет предикат р, если для любых тг наборов (an, 021,..., ami),..., (ai„, а2п,..., атп), удовлетворяющих предикату р, набор (/(ац, ап,..., ai„),..., /(am 1, am2,..., amn)) также удовлетворяет предикату /5.

Обозначим через Ро1(р) множество всех функций из Pk, сохраняющих предикат р.

Напомним12, что каждый предполный в Pk класс определяется (в смысле функтора Pol) предикатом одного из шести семейств Р, О, L, Е, С, В. При этом семейство Р состоит из предикатов, которые являются графиками перестановок на Ек, разлагающихся в произведение циклов одной и той же простой длины, а все одноместные предикаты семейства С имеют вид х £ D, где 0 ф D С Ек ■

Теорема 8. Пусть Q — предполный в Рк класс, который определяется предикатом одного из семейств О, L, Е, С, В. Тогда SFE[<2] = Рк-

Множество всех функций из Рк, самодвойственных относительно перестановки тг, обозначим через S„. Если G — непустое множество перестановок на Ек, то пусть So есть пересечение всех множеств Sn, где 7г £ G. Справедливо следующее утверждение:

для любой группы G перестановок на множестве Ек класс Sq является SFE-замкнутым.

Теорема 9. При любом к > 2 любой SFE-замкнутый класс функций из Рк SFE-порождается множеством всех своих функций, зависящих не более чем от к переменных.

"Rosenberg I. G. Über die funktionale Vollständigkeit in den mehrwertigen Logiken. Rozpravy Geskoslovenske Akad. V6d. Rada Math. Prir. VSd. Praia. 1970. V. 80. S. 3-93.

j, если x — i, г в остальных случаях,

Следствие. При любом к ^ 2 число ЭРЕ-замкнутых классов в Р* конечно.

Теорема 10. В Р2 выполняется равенство БРЕ[0] = 5.

Следствие. В Р2 существует всего два БЕЕ-замкнутых класса — это класс самодвойственных функций Б и класс всех булевых функций Р2.

В параграфе 2.2 на множестве функций трехзначной логики строится полная решетка ЭРЕ-замкнутых классов с указанием порождающих функций для каждого класса.

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

Теорема 11. Имеет место равенство БЕЕ[0] = Яз.

Определим следующие предикаты:

еа(х) = (х = а), еаь(х) е(х£ {а, Ь}),

а(х, у) = (х + 1 = у), ааъ(х, у) = (х е {о, 6}) & <т(х, у),

а°(х, у) = (2х = у), а°аЬ(х, у) = (х € {а, Ь» к сй{х, у),

а1(х,у) = {2х + 2 = у), о^х,у) = (х € {а, Ъ}) & ^(х,у),

а2(х,у) = (2х + 1 = у), а2аЬ{х,у) = (® € {а,Ъ}) ка\х,у),

где а € {0,1,2}, аЪ € {01,02,12}, а сложение и умножение выполняются по модулю 3.

Теорема 12. Следующие классы функций являются БЕЕ-предполными в Р3:

= Ро1(ст), 32х = Ро1(<7°), 52х+2 = РоКа1), 521+1 = Ро1(<т2).

Теорема 13. Следующие классы функций БЕЕ-полны в Р3:

= Ро1(сг01), = Ро1(а02), - Ро1(<т12), ^ = Ро1«)( = Ро1Ю, = Ро1(стр2), ^ = 52°2+2 = Ро1К2), Й^^РоК^).

Теорема 14. &+1 = 8РЕ[х + 1], = 8РЕ[2ж], Б2х+2 = БЕЕрх + 2} и 52г+1 = 8РЕ[2а; +1].

Теорема 15. Пусть

В, = Ро1(ео, еь е2, е0х, еог, е12, сг01, сг02, <т12, одц сг°2, сг^, сг^, а]2, сг{2, <7щ, о"12). Тогда БРЕ[Д] = Р3.

Следствие. В существует ровно четыре БРЕ-предполных класса:

Теорема 16. Класс Щ Б¥Е-предполон в классах Зх+\, ¿2х, ¿21+2) ¿гх+ь Следствие. В Рз существует ровно шесть ЭРЕ-замкнутых классов: Рз> ¿1+1, ¿>2х, 32х+2, 521+1, Я3.

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

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

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

В параграфе 3.1 приводится верхняя оценка временной сложности решения этой проблемы. Если I — длина кода системы функциональных булевых

уравнений, то существует недетерминированная процедура, которая по коду системы проверяет ее выполнимость за время

(LI)'.

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

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

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

Ы(Л) = (J Ree(Мт).

т>1

Теорема 17. Существует алгоритм временной сложности 0(т • log т), который для любого недетерминированного автомата А сводит проблему принадлежности конфигурации множеству R(-A) к проблеме выполнимости некоторой системы функциональных булевых уравнений.

Следствие. Нижняя оценка временной сложности недетерминированного распознавания выполнимости системы функциональных булевых уравнений на одноленточной машине Тьюринга, работающей с линейной зоной, по порядку не меньше d^1, где I — длина входа, d > 1.

13Кудрявцев В. В., Подколзин А. С., Болотов А. А. Основы теории однородных структур. M.: Наука, 1990.

Основные результаты диссертации

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

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

3. Введен оператор ЭРЕ-замыкания, определяемый на основе систем функциональных уравнений, выявлены его основные свойства, построена полная решетка БРЕ-замкнутых классов функций трехзначной логики.

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

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

1. Марченков С. С., Федорова В. С. О решениях систем функциональных булевых уравнений // Дискретный анализ и исследование операций. 2008. Т. 15. № 6. С. 48-57.

2. Марченков С. С., Федорова В. С. О решениях систем функциональных булевых уравнений // Материалы XVII Международной школы-семинара „Синтез и сложность управляющих систем" имени академика О. Б. Лупанова (Новосибирск, 27 октября - 1 ноября 2008 г.), изд-во Института математики, Новосибирск 2008. С. 108-113.

3. Марченков С. С., Федорова В. С. О решениях систем функциональных уравнений многозначной логики // Доклады РАН. 2009. Т. 426, № 4. С. 448-449.

4. Марченков С. С., Федорова В. С. О свойствах решений систем функциональных уравнений многозначной логики // Труды VIII Международной конференции „Дискретные модели в теории управляющих систем" (Москва, 6-9 апреля 2009 г.), издательский отдел факультета Вычислительной математики и кибернетики МГУ имени М. В. Ломоносова, МАКС Пресс, Москва, 2009. С. 210-213.

5. Марченков С. С., Федорова В. С. Решения систем функциональных уравнений многозначной логики // Вестник МГУ. Серия 15. Вычислительная математика и кибернетика. 2009. № 4. С. 29-33.

6. Федорова В. С. О сложности выполнимости системы функциональных булевых уравнений // Материалы XVIII Международной школы-семинара „Синтез и сложность управляющих систем" имени академика О. В. Лупанова (Пенза, 28 сентября - 3 октября 2009 г.), изд-во механико-математического факультета МГУ, Москва, 2009. С. 84-88.

7. Федорова В. С. Сложность проблемы выполнимости для одного языка с функциональными булевыми переменными // Материалы VI молодежной научной школы по дискретной математике и ее приложениям (Москва, 16-21 апреля 2007 г.), часть 3. Изд-во ИПМ РАН, Москва, 2007. С. 17-23.

8. Федорова В. С. SFE-замкнутые классы трехзначной логики // Сборник статей молодых ученых факультета ВМК МГУ, 2010, вып. 7. Москва, издательский отдел факультета Вычислительной математики и кибернетики МГУ имени М. В. Ломоносова. С. 23-33.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от01.12.99 г. Подписано к печати 29.09.2010 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 70 экз. Заказ 424. Тел. 939-3890. Тел./факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

Введение

Глава 1. Решения систем функциональных уравнений многозначной логики

1.1 Основные понятия и терминология.

1.2 Общие свойства решений систем функциональных уравнений

1.3 Системы функциональных булевых уравнений.

Глава 2. Оператор SFE-замыкания

2.1 Некоторые свойства SFE-замыкания.

2.2 SFE-замкнутые классы трехзначной логики.

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

3.1 Верхняя оценка сложности проблемы выполнимости.

3.2 Нижняя оценка сложности проблемы выполнимости.

В математике функциональным уравнением называется уравнение, выражающее связь между значением функции в одной точке с ее значениями в других точках. Это весьма общий класс уравнений, в которых искомой является некоторая функция, а не переменная. Функциональными уравнениями, по существу, являются дифференциальные уравнения, интегральные уравнения, уравнения в конечных разностях, однако само название „функциональные уравнения" обычно не относят к уравнениям этих типов. Под функциональными уравнениями в узком смысле слова понимают уравнения, в которых искомые функции связаны с известными функциями одного или нескольких переменных при помощи операции образования сложной функции. Решения •функционального уравнения могут быть как конкретными функциями, так и классами функций, зависящими от произвольных параметров или произвольных функций.

Одно из простейших функциональных уравнений — это уравнение Коши f(x + у) — f(x) + f(y). Его непрерывные решения имеют вид f(x) — С • х, где С — произвольная константа.

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

Даже свойства коммутативности и ассоциативности суть не что иное как функциональные уравнения. В привычной всем записи эти законы выглядят следующим образом: а о b —boa, (а о Ь) о с = а о (Ь о с), где о — символ некоторой бинарной операции. Но если представить эту операцию в эквивалентном виде а о b — /(а, 6), то получится как раз то, что обычно называют функциональным уравнением: а, 6) - /(6, а), /(/(а, 6), с) = /(а,/(Ь,с)).

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

В теории аналитических функций функциональные уравнения часто применяются для введения новых классов функций. Например, автоморфные функции описываются функциональными уравнениями вида f(saz) = f(z), где sa есть элемент некоторой счетной подгруппы группы дробно-линейных преобразований комплексной плоскости, двоякопериодические функции — парой функциональных уравнений f(z + а) — f(z) и f{z + Ъ) = f(z).

Если функция известна в некоторой области, то знание для нее функционального уравнения позволяет расширить область определения этой функции. Этот прием часто применяют для аналитического продолжения функций комплексного переменного. Например, используя функциональное уравнение T(z -+- 1) = zT{z) и имея значения Гамма-функции Г(^) в полосе О < Re z < 1, можно продолжить ее на всю плоскость z.

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

Также подобные примеры можно найти в различных работах, касающихся, в частности, замкнутых классов булевых функций (см., например, [2, 5, 20, 23, 41, 46, 53]).

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

• Что представляют собой множества решений систем функциональных уравнений?

• Как зависят решения систем функциональных уравнений от функциональных констант, используемых в уравнениях?

• Насколько сложным может быть поиск решений систем функциональных уравнений?

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

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

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

Если же обратиться к дискретной математике, то можно увидеть, что целые теории строятся и развиваются на базе? подходящих языков функциональных уравнений: Так, одним из первых определений; рекурсивных функций/ в теории алгоритмов стало эрбран-геделевское определение, основанное на решениях систем функциональных уравнений специального? вида [9]. Системы канонических уравнений в теории автоматов представляют собой основной инструмент как для задания и изучения: собственно конечно-автоматных функций, так и для исследования разнообразных их обобщений [3, 10, 12].

В теории булевых функций и теории, функций многозначной, логики функциональные. уравнения представлены; также достаточно; широко. Укажем» лишь три хрестоматийных" примера. Все линейные булевы функции; зависящие от п переменных, могут быть определены как решения функционального уравнения . фЫ е ух,., хп ® уп) е v?(o,., о) ■;= ., хп) ф <р(уъ . • ,уп)у где О и ® суть г заданные функциональные константы ноль и сложение по модулю два; Все монотонные булевы функции от n переменных определяются функциональным уравнением cp(xi,. ,хп) V (р(х 1 V 2/1,. ,хп V yn) =<p{xi V уи . ,хп V уп),

Ряд результатов о функциональных уравнениях был получен зарубежными учеными за последнее десятилетие. О. Ekin, S. Foldes, P. L. Hammer, L. Hellerstein в работе [49] вывели уравнения; задающие множества рефлексивных, полярных, супермодулярных, субмодулярных, билинейных, квадратичных и принадлежащих классам Хорна булевых функций. Также в работе [49] доказан критерий задания класса булевых функций функциональным уравнением: класс булевых функций, замкнутый относительно операции добавления или изъятия несущественных переменных, может быть описан функциональным уравнением тогда и только тогда, когда этот класс замкнут относительно операции отождествления переменных.

S. Foldes в [50] усилил этот критерий, убрав предварительное условие замкнутости'класса относительно операции добавления или изъятия несущественных переменных, и* доказал его, используя методы общей алгебры, а N. Pippenger в [54]' расширил область его применения до классов функций вида / : {0,., к — 1}п —> {0,., I — 1}, к, I ^ 2, частным случаем которых являются функции многозначной логики.

L. Hellerstein в статье [52] доказала существование классов, определяемых системой с бесконечным числом функциональных уравнений (например, таков класс линейных пороговых функций).

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

В теории функций многозначной логики одними из важнейших являются вопросы классификационного характера. Чаще всего классификации строятся на основе каких-либо операторов замыкания. Самая известная классификация этого типа — это классификация на основе операции суперпозиции. Для булевых функций она приводит к счетной решетке замкнутых классов [55, 56, 46, 20], но уже для функций трехзначной логики подобная классификация оказывается континуальной [47]. Естественным образом возникает вопрос о построении конечной (или хотя бы счетной) классификации для функций многозначной логики на основе более сильного, чем оператор суперпозиции, оператора замыкания. Например, в работах [17, 18, 35-37] изучается операция 5-замыкания, в работах [7, 14, 48] — операция параметрического замыкания, в работах [6, 26, 38, 39] — операции замыкания программного типа.

Идея операции й'-замыкания, где наряду с операцией суперпозиции разрешается применять операцию перехода к двойственным функциям относительно фиксированной группы подстановок, высказывалась несколькими авторами. В настоящее время существуют две версии построения 5-классификации множества функций &-значной логики при к ^ 3, представленные в работах С. С. Марченкова [17, 18] и Нгуена Ван Хоа [35-37] , где, в частности, установлено, что множество классов в данной классификации конечно, хотя и зависит от к сверхэкспоненциальным образом.

Понятия параметрической выразимости и параметрического замыкания введены А. В. Кузнецовым в работе [14]. В этой же работе получены критерий параметрической выразимости в к-значной логике для всех к ^ 2 и конечное описание параметрически замкнутых классов булевых функций. Конечность множества параметрически замкнутых классов при к = 3 показана в работе А. Ф. Данильченко [7], а при к > 3 — в работе S. Burris, R. Willard [48]. Кроме того, в [7] построены все предполные классы в Р3.

В работах Ю. В. Голункова [6] и С. С. Марченкова [26] изучаются вопросы полноты функционально-предикатных систем с операциями замыкания программного типа. В работах В. А. Тайманова [39],и В:. Д. Соловьева-[38] исследуется семейство функциональных систем многозначной логики с операциями программного типа, каждая из которых определяется своим множеством предикатов. В работе [39] показано, что в зависимости от свойств указанных множеств предикатов мощность множества замкнутых классов может быть конечной, счетной или континуальной. В [38] рассматриваются примеры конечных описаний множества замкнутых классов для некоторых операций программного типа.

С. С. Марченков в работе [28] вводит в рассмотрение на основе идеи исчисления равенств операцию эквационального замыкания, порождающую конечную классификацию классов функций- многозначной логики, а в работе [24], новые операторы замыкания, определяются* на основе логико-функциональных языков различных типов.

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

В диссертации вводится новый оператор замыкания, основывающийся, на системах функциональных уравнений, — оператор SFE-замыкания (system of functional equations), который существенно отличается от известных сильных операторов замыкания как по способу задания, так и по порождаемым классификациям функций многозначных логик. По-видимому, оператор SFE-замыкания является наиболее сильным из известных операторов замыкания. В частности, в классе Р2 булевых функций образуется лишь два SFE-замкнутых класса: сам класс и класс S самодвойственных функций. л

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

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

Заключение

На защиту выносятся следующие результаты:

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

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

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

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

1. Ахо А. В., Сети Р., Ульман Д. Д. Компиляторы: принципы, технологии и инструменты. М.: Вильяме, 2003.

2. Балюк А. С., Винокуров С. Ф., Гайдуков А. И., Зубков О. В., Кириченко К. Д., Пантелеев В. И., Перязев Н. А., Перязева Ю. Н. Избранные вопросы теории булевых функций. М.: Физматлит, 2001.

3. Бардзинь Я. М., Трахтенброт Б. А. Конечные автоматы (поведение и синтез). М.: Наука, 1970.

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

5. Гаврилов Г. П. Индуктивные представления булевых функций и конечная порождаемостъ классов Поста j j Алгебра и логика. 1984. Т. 23, вып. 1. С. 88-99.

6. Голунков Ю. В. Полнота систем функций в операторных алгоритмах, реализующих функции k-значной логики // Вероятностные методы и кибернетика. 1980. К9- 17. С. 23-34.

7. Данильченко А. Ф. О параметрической выразимости функций трехзначной логики // Алгебра и логика. 1977. Т. 16, № 4. С. 397-416.

8. Катериночкина Н. Н. Об эквивалентности некоторых вычислительных устройств // Кибернетика. 1970. № 5. С. 27-31.

9. Клини С. К. Введение в метаматематику. М.: ИЛ, 1957.

10. Кобринский Н. Е., Трахтенброт Б. А. Введение в теорию конечных автоматов. М.: Физматгиз, 1962.

11. Кон П. Универсальная алгебра. М.: Мир, 1968.

12. Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М.: Наука, 1986.

13. Кудрявцев В. Б., Подколзин А. С., Болотов А. А. Основы теории однородных структур. М.: Наука, 1990.

14. Кузнецов А. В. О средствах для обнаружения невыводимости и невыразимости. В книге „Логический вывод". М.: Наука, 1979. С. 5-33.

15. Курода С. И. Классы языков и линейно ограниченные автоматы // Кибернетический сборник, вып. 9. М.: Мир, 1972. С. 36-51.

16. Ложкин С. А. Лекции по основам кибернетики. М.: Изд-во факультета Вычислительной математики и кибернетики МГУ, 2004.

17. Марченков С. С. S-классификация функций многозначной логики j j Дискретная математика. 1997. Т. 9, № 3. С. 125-152.

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

19. Марченков С. С. Дискриминаторные классы трехзначной логики j j Математические вопросы кибернетики. Вып. 12. 2003. С. 15-26.

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

21. Марченков С. С. Итерация булевых (п, п)—операторов // Вестник МГУ. Серия 15. Вычислительная математика и кибернетика. 2006. № 4. С. 3641.

22. Марченков С. С. Клоповая классификация дуально дискриминаторных алгебр с конечным носителем J/ Математические заметки. 1997. Т. 61, № 3. С. 359-366.

23. Марченков С. С. Конечная порождаемость замкнутых классов булевых функций // Дискретный анализ и исследование операций. Серия 1. 2005. Т. 12, № 1. С. 101-118.

24. Марченков С. С. О выразимости функций многозначной логики в некоторых логико-функциональных языках // Дискретная математика. 1999. Т. 11, № 4. С. 110-126.

25. Марченков С. С. Однородные алгебры // Проблемы кибернетики. Вып. 39. М.: Наука, 1982. С. 85-106.

26. Марченков С. С. Операторы замыкания с разветвлением по предикату // Вестник МГУ. Серия 1. Математика. Механика. 2003. № 6. С. 37-39.

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

28. Марченков С. С. Эквациональное замыкание // Дискретная математика. 2005. Т. 17, вып. 2. С. 117-126.

29. Марченков С. С., Федорова В. С. О решениях систем функциональных булевых уравнений // Дискретный анализ и исследование операций. 2008. Т. 15. № 6. С. 48-57.

30. Марченков С. С., Федорова В. С. О решениях систем функциональных уравнений многозначной логики // Доклады РАН; 2009: Т. 426, № 4. С. 448-449. •

31. Марченков С1 С., Федорова В. С. Решения систем функциональных уравнений многозначной логики // Вестник МГУ: Серия 15. Вычислительная математика и кибернетика: 2009. № 4; С. 29^33.

32. Мучник А. А. Добавление переводчика к статьям „Об альтернировании, I- II" // Кибернетический сборник (новая серия) ■ вып. 20. М.: Мир, 1983. С. 141-158.

33. Нгуен Ван Хоа О замкнутых классах k-значной логики, самодвойственных относительно транзитивных групп // Дискретная математика. 1996. Т. 8,.№ 1. С. 129-156.

34. Нгуен Ван Хоа О семействах замкнутых классов k-значной логики, сохраняемых всеми автоморфизмами // Дискретная математика. 1993. Т. 5, № 4. С. 87-108.

35. Нгуен Ван Хоа О структуре самодвойственных замкнутых классов трехзначной логики Рз / / Дискретная математика. 1992. Т. 4, № 4. С. 8295.

36. Соловьев В. Д. Замкнутые классы в k-значной логике с операцией разветвления по предикатам // Дискретная математика. 1990. Т. 2, № 4. С. 19-25.

37. Тайманов В. А. О функциональных системах k-значной логики с операциями программного типа // Доклады АН СССР. 1983. Т. 268, № 6. С. 1307-1310.

38. Тарасова О. С. Классы k-значной логики, замкнутые относительно расширенной операции суперпозиции // Вестник МГУ. Серия 1. Математика. Механика. 2001. № 6. С. 54-57.

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

40. Федорова В. С. Сложность проблемы выполнимости для одного языка с функциональными булевыми переменными J/ Материалы VI молодежной научной школы по дискретной математике и ее приложениям

41. Москва, 16-21 апреля 2007 г.), часть 3. Изд-во ИПМ РАН, Москва, 2007. С. 17-23. . • ' •, ■ ■■ ' ' ,

42. Федорова В. С. SFE-замкнутые классы трехзначной логики // Сборник статей молодых ученых факультета ВМК МГУ, 2010, вып. 7. Москва, издательский отдел факультета Вычислительной математики и кибернетики МГУ имени М. В. Ломоносова.

43. Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986.

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

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

46. Foldes S. Equational classes of Boolean functions via the HSP Theorem // Algebra Universalis. 2000. V. 44. P. 309 324.

47. Ganter В., Plonka J., Werner H. Homogeneous algebras are simple // Fundi Math. 1973. V. 79. № 3. P. 217-220.

48. Hellerstein L. Ongeneralized constraints and certificates / / Rutcor Reserch Report 26 98. Rutcor, Rutgers University, 1998.53.? Kuntzman J. Algebre de Boole. Paris: Dunod, 1965.

49. Pippenger N. Galois theory for minors of finite functions // Discrete Mathematics. 2002. V. 254. P. 405-419.

50. Post E. L. Introduction to a general theory of elementary propositions j j Amer. J. Math. 1921. V. 43. P. 163-185.

51. Post E. L. The two-valued iterative systems of mathematical logic. Princeton Univ. Press, Princeton, NJ. 1941.

52. Rosenberg I. G. U&er die funktionale Vollsf&ndigkeit in den mehrwertigen Logiken // Rozpravy Ceskoslovenske Akad. Ved. Rada Math. Prir. Ved.

53. Praha. 1970. V. 80. S. 3 93.