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

• Боков, Григорий Владимирович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Боков, Григорий Владимирович

Оглавление

Введение

Основные понятия диссертации

1 Проблема базиса

1.1 Критерий конечно-порожденности

1.2 Мощность базисов

2 Структура решетки замкнутых классов тавтологий

2.1 Глубина и ширина решетки

2.2 Предполные классы

2.3 Дуально-предиолные классы

2.4 Критериальные системы

3 Проблема полноты и выразимости

3.1 Алгоритмическая неразрешимость проблемы выразимости

3.2 Алгоритмическая неразрешимость проблемы полноты

Заключение

Литература

Введение диссертации (часть автореферата) на тему «Условия выразимости и полноты пропозициональных исчислений»

Введение

Общая характеристика работы Актуальность темы

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

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

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

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

в качестве П берется множество допустимых операций над объектами системы. Примерами таких систем являются множества функций с операцией суперпозиции [24], множество автоматных функций с операциями композиции и обратной связи [7], исчисления высказываний [15], интуиционистская логика [34], модальные логики [21], логика доказуемости [40, 11] и другие, где в качестве объектов выступают формулы, а в качестве операций, как правило, выступают операция подстановки и операция тоЛ/,5 ропет1. С таким понятием логической системы (М, О) связан целый ряд задач функционального характера. К ним относятся такие важные проблемы, как задача о выразимости и вариант последней — задача о полноте, которые, как правило, раскрывают содержательную суть рассматриваемой системы. Выразимость между объектами в логической системе означает возможность получения одних из них через другие посредством заранее определенного набора правил, в частности, посредством суперпозиций. Проблема выразимости состоит в описании всех таких пар конечных множеств объектов логической системы, для которых все элементы одного множества можно выразить через элементы другого множества. Зачастую не всегда для рассматриваемой логической системы удается решить проблему выразимости для произвольных объектов. Для таких систем принято рассматривать частный случай проблемы выразимости, а именно, проблему полноты. Проблема полноты состоит в описании таких множеств объектов рассматриваемой системы, отправляясь от которых можно получить посредством заранее определенного набора правил все объекты данной системы.

Основополагающую роль в решении проблемы выразимости для двузначной логики играет результат Э. Поста 1921 года [37]. Он изучил отношение выразимости для случая классической логики и полностью описал структуру всех замкнутых (относительно суперпозиций) классов булевых функций, названных впоследствии классами Поста [27]. На основе данного описания замкнутых классов уже нетрудно построить алгоритм распозна,-вания выразимости в классической логике высказываний, позволяющий по любой булевой функции, заданной формулой или таблицей, и любой

хТо есть, если выводимо а и а влечет в, то в выводимо.

конечной системе таких функций распознавать, выразима ли эта функция через эту систему посредством суперпозиции. При переходе от двузначных логик к многозначным обнаружились принципиальные отличия в выразимости одних объектов через другие. Попытка обозрения замкнутых классов функций для многозначной логики натолкнулась на принципиальные трудности, связанные с континуальным обилием замкнутых классов, обнаруженных Ю.И.Яновым и А.А.Мучником [28]. Аналогичные трудности были обнаружены М.Ф.Раца [17] даже в простейшей неклассической логике первой матрицы Яськовского [35]. В этой связи, хотя для любой конеч-нозначной логики существует алгоритм для распознавания выразимости, основанный на переборе всех функций от данных переменных, выразимых через данную систему, однако такой перебор в большинстве случаев является громоздким и поэтому соответствующий алгоритм практически не реализуем.

Для двузначного случая проблема полноты относительно операции суперпозиции была полностью решена Э. Постом [37]. Им же были предприняты первые шаги по решению данной проблемы для многозначных логик. В качестве одного из основных подходов к решению проблемы полноты выступает подход, впервые осуществленный в работах А.В.Кузнецова и С.В.Яблонского [25, 26] и состоящий в получении критериев полноты в терминах так называемых предполных классов. Принцип определения критериев зависит от свойств структуры замкнутых подмножеств рассматриваемого множества. Основным понятием в данном подходе служит понятие критериальной системы [6]. Основываясь на нем, в 1954 году С.В.Яблонским [25[ была решена проблема полноты для 3-значной логики. Решение было сведено к описанию всех предполных классов в ней, при этом было показано, что множество предполных классов образует критериальную систему. Сами предполные классы при этом были явно описаны. Из этого описания вытекал алгоритм распознавания полноты для конечных систем. Идея решения задачи о полноте в терминах предполных классов впоследствии стала одной из самой главной для /с-значных логик. Так, в 1964 году А.И.Мальцев на этом пути решил задачу о полноте для четырех-

значной логики, а затем рядом авторов С.В.Яблонским, А.В.Кузнецовым, Л о Чжу-каем, Розенбергом и др. были последовательно построены в явном виде все предполные классы для k-значных логик [26, 12, 3, 38]. Завершающее построение при этом провел Розенберг в 1970 году.

Впервые проблема выразимости для пропозициональных исчислений была поставлена Тарским в 1946 году на конференции по проблемам математики, посвященной двухсотлетию Принстонского университета [41]. Уже в 1949 году Линиал и Пост [36] опубликовали короткую заметку, в которой без доказательства сформулировали гипотезу об алгоритмической неразрешимости проблемы полноты для классического исчисления высказываний. Доказательство данного результата постепенно было восстановлено последующими авторами. Первым в этом направлении был Дэвис [29], который в 1958 году опубликовал первый вариант доказательства, далее в 1963 году Синглетари [39] и в 1964 — Интема [42] завершили доказательство. Независимо от них в 1958 году Харроп [32] построил конечную систему аксиом над двумя бинарными связки и конечное множество правил вывода, для которых проблема выразимости алгоритмически неразрешима. Следующим продвижением в этом направлении был отказ от фиксирования логических связок. Так, в 1963 году Глэдстоун [30] обобщил результат Линиала и Поста на случай произвольной конечной системы связок, из которых выразима импликация. При этом он заменил операцию m.odus ponens на ее синтаксический аналог. Независимо от Линиала и Поста в 1963 году Кузнецов [9] доказал алгоритмическую неразрешимость целого класса задач для пропозициональных исчислений с операцией modus ponens, куда входит проблема эквивалентности, проблема полноты и выразимости.

Впоследствии задача решения проблемы выразимости стала возникать в разнообразных логиках, задаваемых исчислениями, которые необязательно обладают адекватными конечными моделями. К таким логикам относятся интуиционистская логика [34], модальные логики [21], логика доказуемости [40, 11] и др. В этом направлении А.В.Кузнецов [8, 10] попытался перенести отношения выразимости на случай языка формул той или иной логики путем явного использования правила замены эквивалентным в рас-

сматриваемой логике. Общая проблема выразимости в данной логике ставится следующим образом. Требуется указать алгоритм, который по любой формуле и любой конечной системе формул языка этой логики позволял бы распознавать, выразима ли эта формула через эту систему, используя лишь правило замены эквивалентным в этой логике и ослабленное правило подстановки. М.Ф.Раца [18, 19] рассмотрел модальные логики с точки зрения отношения выразимости и доказал, что для многих из них, в том числе для наиболее известных, какими являются логика 54 Люиса [21] и логика Гржегорчика [31], не существует алгоритма, решающего проблему выразимости в них. Ему же удалось доказать, что для пропозициональной логики доказуемости Геделя-Леба, а также для многих ее расширений алгоритма распознавания выразимости не существует [20].

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

Особое внимание в изучении логических систем уделяется выделению систем образующих или базисов рассматриваемых систем. Системы образующих двузначных логик уже давно изучаются многими авторами. Так, Э. Пост [37] доказал, что, если ограничиться только рассмотрением операции суперпозиции, то каждая двузначная логика конечно порождена. Л.Хенкин [33] показал, что каждая двузначная логика, содержащая классическую импликацию, конечно порождена относительной операции modus ponens. При переходе от двузначных логик к к-значным для к > 3 обнаружились принципиальные отличия этих объектов относительно выводимости или порождения из одних формул других. Так, для случая выво-

димости относительно суперпозиции [28] Мучник показал, что не каждая /с-значная логика конечно порождена, а Янов для каждого к > 3 доказал, что существует /с-значная логика, не имеющая базиса.

Отдельным самостоятельным направлением в решении общей проблемы выразимости является описание структуры решетки замкнутых классов. Для двузначной логики с операцией суперпозиции решетка имеет счетное число замкнутых классов и ее структура полностью восстанавливается из результата Поста [27]. Для /с-значной логики это не верно, уже при к > 3 решетка континуальная [6]. Подобные результаты были получены и для неклассических логик, в частности, континуальную надрешетку имеют интуиционистская логика, модальные логики, логика доказуемости [2].

Цель и задачи диссертационного исследования

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

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

- найти минимально-достаточные условия, которые нужно наложить па правила вывода, чтобы образованное ими исчисление было конечно порождено;

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

- исследовать размер и структуру решетки замкнутых классов;

- охарактеризовать предполные и дуально-предполные классы этой решетки.

Методы исследования

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

Научная новизна

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

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

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

3. Исследованы размеры решетки замкнутых классов тавтологий, существование и мощность системы предполных и дуально-предполных классов, наличие и виды критериальных систем. Для пропозициональных исчислений с произвольными модусными операциями вывода доказаны достаточные условия континуальности решетки замкнутых классов тавтологий.

Теоретическое и прикладное значение

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

Апробация работы

Результаты диссертации неоднократно докладывались на семинарах механико-математического факультета МГУ им. М. В. Ломоносова: на семинаре "Кибернетика и информатика" под руководством профессора В. Б. Кудрявцева (2008 - 2013 гг.), на семинаре "Теория автоматов" под руководством профессора В. Б. Кудрявцева (2008 - 2013 гг.).

Результаты докладывались на следующих конференциях:

1. Международная научная конференция студентов, аспирантов и молодых ученых "Ломоносов-2010", Москва, МГУ им. М.В.Ломоносова, 12 — 15 апреля 2010 года.

2. Международная научная конференция студентов, аспирантов и молодых ученых "Ломоносов-2011", Москва, МГУ им. М.В.Ломоносова, 11 — 15 апреля 2011 года.

3. Международная научная конференция студентов, аспирантов и молодых ученых "Ломоносов-2012", Москва, МГУ им. М.В.Ломоносова. 9 — 13 апреля 2012 года.

4. Международная научная конференция студентов, аспирантов и молодых ученых "Ломоносов-2013", Москва, МГУ им. М.В.Ломоносова, 8 — 13 апреля 2013 года.

5. Научная конференция "Ломоносовские чтения", Москва, МГУ им. М.В.Ломоносова, 14 — 23 ноября 2011 года.

6. Научная конференция "Ломоносовские чтения", Москва, МГУ им. М.В.Ломоносова, 16 — 24 апреля 2012 года.

7. Научная конференция "Ломоносовские чтения", Москва, МГУ им. М.В.Ломоносова, 15 — 24 апреля 2013 года.

8. X международный семинар "Дискретная математика и ее приложения", Москва, МГУ им. М.В.Ломоносова, 1 — 6 февраля 2010 года.

9. X международная конференция "Интеллектуальные системы и компьютерные науки", Москва, МГУ им. М.В.Ломоносова, 5 — 10 декабря 2011 года.

Публикации

Основные результаты диссертации опубликованы в 9 работах автора [43]-[51|.

Структура и объем диссертации

Диссертация состоит из "Введения", "Основных понятий диссертации", трёх глав, в которых раскрыты основные результаты, заключения и списка литературы. Объем диссертации 91 страница. Список литературы содержит 51 наименование.

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

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

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

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

Во второй главе рассматриваются общие вопросы структуры решетки замкнутых классов тавтологий: глубина и ширина решетки, предполные и дуально-предполные замкнутые классы, критериальные системы. Основные результаты второй главы представлены теоремами 3-7. Первый раздел главы посвящен размеру решетки, в нем формулируется и доказывается теорема 3 о достаточных условиях континуальности решетки замкнутых классов и теорема 4 о размерах решетки. Во втором разделе представлена с доказательством теорема 5 о числе предполных классов тавтологий. Третий раздел содержит доказательство теоремы 6 об отсутствии дуалыю-

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

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

Основные понятия диссертации

Множество натуральных чисел {1, 2, 3,...} обозначим через N, а множество натуральных чисел с нулем N U {0} — через

Пусть Е2 = {0,1}. Через Р2 обозначим множество всех булевских функций [24]. Элементы множества Р2 будем обозначать прописными латинскими буквами f,g,h,..., возможно, с индексами. Число существенных переменных функции / G Р2 обозначим через >c{f). На множестве Р2 определим оператор замыкания [•], порожденный операцией суперпозиции [24]. Множество Q С Р2 — замкнуто, если [Q] = Q.

Будем считать, что имеется некоторый счетный универсум переменных U, элементы которого будем обозначать прописными латинскими буквами х, у, z,возможно, с индексами. Если множество переменных И интерпретировать, как переменные высказывания, принимающие только значения истина и ложь, то функции из Р2 можно рассматривать как логические связки над данными переменными. Определим понятие формулы. Пусть £ С Р2 — конечное множество функций и X С IX — некоторое множество переменных, тогда формулой над логическими связками из Е и множеством переменных X назовем слово (конечную последовательность) в алфавите EUX, которое определяется следующим образом. Слово х G X является формулой. Если слова 2li, ...,2ln — формулы и / G Е — логическая связка арности п. тогда слово /2li...2ln является формулой. Обозначим через Фе(Х) множество всех формул над логическими связками из Е и множеством переменных X. Когда X = 11 множество будем для

краткости обозначать через Фе. Элементы множества Фе будем обозначать строчными готическими буквами 21,03, ..., возможно, с индексами. Под равенством формул из будем понимать равенство соответствующих

слов в алфавите Е U X. Равенство формул 21,03 G Фе будем обозначать через 21 = 03.

Формула 21 G Фе(Х) является подформулой формулы 03 G Фе(Х), если найдутся такие слова ai,o>2 G (EuX)*, что 03 = Собственными будем называть такие подформулы 21 формулы 03, для которых 21 не совпадает с 03. Определим понятие глубины подформулы 21 G формулы 03 G Фъ(Х). Если 21 совпадает с 03, то глубина 21 равна нулю. Пусть 21 собственная подформула в 03 и £ — минимальная подформула в 03, для которой 21 является собственной подформулой, тогда, если глубина С равна п G N, то глубина 21 равна п + 1. Глубину подформулы 21 формулы 03 будем обозначать через ¿<в(21).

Будем говорить, что формула 21 G Фе зависит от переменного х G И, если х является подформулой в 21. Зависимость формулы 21 от переменной х обозначим через 21(.х), зависимость от переменных х\,....хп — через Щхъ

Каждой формуле $ G Фе однозначно сопоставим функцию из [Е U {.т}] [24], где ж 6 ?2 ~ тождественная функция. Поскольку каждую логическую связку из Е можно интерпретировать как соответствующую ей функцию, то по аналогии с определением формулы можно определить понятие интерпретации формулы. Каждая переменная задает тождественную функцию из Р^, которую будем обозначать тем же символом: если формулам 2li, ...,21 т уже сопоставлены функции /i,..., fm, то формуле /211 ...2lm сопоставим функцию д равную функции /(/i,..., /,„). Итак, каждой формуле $ из Фе можно сопоставить функцию из Р2, которую будем обозначать через /дг. В этом случае будем говорить, что формула $ выражает функцию

h-

Формулу $ из Фе будем называть тавтологией или тождественно истинной, если /^(¿i,..., гт) = 1, при любых значениях i\..... гт из Е2, где т — это арность функции /5. Обозначим через Th множество всех тавтологий

В ФЕ:

Th = б Фе | = 1}

На множестве формул Фе определим понятие модусной операции [22]. Пусть различные формулы из Фе({^1, •••, хп}), тогда набор

(т?ь Ът] задает операцию lü : Ф™ —>■ Фе, определенную следующим образом:

/ то

= ^о ^ 32lb...,2ln е ФЕ ( Д& =

\г=0

ГДе ---Лт. — переменные, пробегающие множество формул Фе- Обо-

значим правую часть условия через £ь •■■, тогда операцию со

можно записать в виде Л-функции [23]:

= Ас......<„, (б> I -,£m))

Следуя [1, 22], такие операции будем обозначать в виде схемы:

..., •••> Зт^'Ъ •••■) Хп)

Классическим примером модусной операци является операция modus ponens:

Xi,Xi —>• х2 Х2

Множество всех модусных операций на Фе обозначим через Элементы множества будем обозначать прописной греческой буквой и, а множества элементом из Л4% — строчной греческой буквой О, возможно, с индексами.

Нас будут интересовать не все модусные операции, а лишь те w Е ЛЛт,-, которые тавтологии переводят в тавтологии. Такие операции назовем допустимыми [14] на Th. Множество всех допустимых на Th операций обозначим через Оть-

Кроме того, определим на множестве Th операцию подстановки. Пусть 21 — тавтология, содержащая переменное высказывание х, а — произвольная формула из Фе- Тогда, если заменить в 21 все вхождения х на то

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

31(з)

щ

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

Расширим понятие операции подстановки для общего случая. Подстановкой будем называть всякое отображение а: 11 -—> Ф^. Результатом применения подстановки о к формуле 21 £ Фе является формула <721, которая определяется по правилу. Если 21 = х € И, то ст21 = о~(х), если же 21 = /031-..03п, то ст21 = /сг®1...сг03п. Отличие подстановки, как отображения сг: IX ■—>■ Фе, от операции подстановки заключается в том, что о позволяет одновременно подставлять формулы вместо нескольких переменных. Множество всех подстановок а: X —> Ф^, где I С И, обозначим через Я^,{Х), а множество подстановок через Я^. Ясно, что для любой

подстановки а Е Я£ и каждой формулы 21 £ Ф^ формула а21 есть результат последовательного применения операции подстановки к формуле 21.

Множество тавтологий ТЪ и множество допустимых операций О. образуют алгебраическую систему (ТЬ, О,), которую будем называть пропозициональным исчислением. Пусть С Оть — произвольное множество допустимых на ТЪ модусных операций, тогда на ТЬ можно определить оператор замыкания, порожденный операциями из Г> [5]. Этот оператор будем обозначать через или просто через [•], когда множество О фиксировано 2.

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

2Во избежание увеличения количества обозначений, операторы замыкания для множеств различной природы имеют одно и тоже обозначение [•].

П С тИе оператор является алгебраическим оператором замыкания [5].

Множество тавтологий М С ТЬ называется замкнутым относительно множества операций П, если [М]ц — М и полным, если [М]^ = ТЬ. Для произвольного М С ТЬ и 21 £ ТЬ формулу 21 £ [М]^ назовем выводимой из множества формул М и будем обозначать это через М Ь^ 21 или просто через М К 21, если множество О, фиксировано. Множество тавтологий ТЪ будем называть конечно-порожденным относительно множества операций О, если существует такое конечное множество М С ТЬ, что [М]п = ТЬ. Исчисление высказываний (ТЬ, П) конечно-порождено, если множество ТЬ конечно-порождено относительно множества операций ГI.

Для произвольного множества тавтологий М С ТЬ и произвольного множества допустимых модусных операций О С Оть обозначим через (М)п множество состоящее из тавтологий множества М, из тавтологий 21, для которых существует такая операция си £ П и такие формулы 05т,..., 03,?1 Е М, что иДФх, ...,03т) = 21, а также из тавтологий 21, для которых существуют такая формула 05 € М и подстановка о £ что 21 = а\8. Если множество операций О фиксировано, то будем писать (М) вместо (М)^. Положим (М)п — Ми (М)1^1 = ((МУп)п, тогда не сложно убедиться, что

[М]п = и (М)Ь

/> о

Параметр I при этом играет роль длины вывода.

Пусть ...,9)т £ ..., жп}). Будем говорить, что уравнение

З^жъ •■••, хп) = 65(жх,..., хп) имеет решение в области истинности формул 5Э1, ...,53т и записывать это в виде:

если существует такая подстановка <т: {х'1,...,хп} —> Фе, что = сг<5 и (т5Эг ^ ТЬ, г = 1,.... т.

Список литературы диссертационного исследования кандидат наук Боков, Григорий Владимирович, 2013 год

Литература

4

Гильберт Д., Бернайс П. Логические исчисления и формализация арифметики. — М.: Наука, 1979.

21 Горбунов И.А., Рыбаков М.Н. Континуальные семейства логик // Логические исследования, т. 14, 2007, с. 131-151.

Захарова Е.Ю. Критерий полноты для системы функций из Рк. // Проблемы кибернетики., №18, 1967, с. 5-10.

Колмогоров А.Н., Драгалин А.Г. Введение в математическую логику. — М.: Изд-во Моск. ун-та, 1982.

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

61 Кудрявцев В.Б. Функциональные системы. — A4.: Изд-во Моск. ун-та, 1982.

Кудрявцев В.Б., Алешин C.B., Подколзип A.C., Введение в теорию автоматов. — М.: Наука, 1985.

Кузнецов А. В. Аналоги "штриха Шеффера"в конструктивной логике. // ДАН СССР, т. 160, №2, 1965, с. 274-277.

Кузнецов A.B. Неразрешимость общих проблем полноты, разрешимости и эквивалентности для исчислений высказываний. // Алгебра и логика, том 2, №4, с. 47-66, 1963.

[10] Кузнецов А. В. О функциональной выразимости в суперинтуиционистских логиках. // Матем. исследования, т.6, №4, 1971, с. 75-122.

[11] Кузнецов А. В., Муравицкий А. Ю. Доказуемость как модальность. // Актуальные проблемы логики и методологии науки, Киев, 1980, с. 193-230.

[12] Ло Чжу-Кай, Лю Сюй Хуа. Предполные классы, определяемые бинарными отношениями в многозначной логике. Acta Sei. Natm. Univ. Jilinensis, №4, 1963.

[13 [14

[15 [16

[17

[18

[19

[20

[21 [22

Мальцев А.И. Алгоритмы и рекурсивные функции. — М.: Наука, 1965.

Минц Г. Е. Допустимые и производные правила. // Записки научных семинаров ЛОМИ АН СССР, т. 8, 1968, с. 189-191.

Новиков П. С. Элементы математической логики. — М.: Наука, 1973.

Подколзин A.C. Компьютерное моделирование логических процессов. Архитектура и языки решателя задач. — М: ФИЗМАТЛИТ, 2008.

Раца М. Ф. О функциональной полноте в интуиционистской логике высказываний. // Пробл. киберн., т. 39, 1982, с. 107-150.

Раца М.Ф. Неразрешимость проблемы функциональной выразимости в модальной логике SA. // ДАН СССР, т. 268, №4, 1983, с. 814-817.

Раца М.Ф. Алгоритмическая неразрешимость проблемы выразимости в модальных логиках. // Матем. пробл. киберн., т. 2, 1989, с 71-99.

Раца М. Ф. Формальное сведение общей проблемы выразимости формул в логике доказуемости Гёделя-Лёба. // Дискретная математика, т. 14, вып. 2, 2002, с. 95-106.

Фейс Р. Модальная логика. — М.: Наука, 1974.

Циткин А. И. О допустимых правилах интуиционистской логики высказываний. // Матем. сб., т. 102(144):2, 1977.

[23] Шенфилд Д., Математическая логика. — М.: Наука, 1975, с. 314-32-3.

[24] Яблонский C.B. Введение в дискретную математику. — М., Наука, 1986.

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

[26] Яблонский С. В. Функциональное построение в /с-значной логике. // Труды матем. ин-та им В.А.Стеклова, Из-во АН СССР, т. 51, 1958, с. 5-142.

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

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

[29] Davis М., Computability and unsolvability. // McGraw-Hill, New York, 1958, p. 137-142.

[30] Gladstone M.D. Some Ways of Constructing a Prepositional Calculus of Any Required Degree of Unsolvability. // Transactions of the American Mathematical Society, vol. 118, 1965, p. 192-210.

[31] Grzegorezyc A. Some relational systems and the associated topological spaces. // Fund. Math., №60, 1967, p. 223-231.

[32] Harrop R. On the existence of finite models and decision procedures. // Proceedings of the Cambridge Philosophical Society, vol. 54, 1958, p. 1-16.

[ 33] Henkin L. Fragments of the prepositional calculus. //J. Symb.Logic, vol. 14, 1949, p. 42-82.

[34] Heytmg A. Die Formalen Regeln der Intuitionistischen Logik. // Sitzungsberichtc der Prcussischen (Berlin) Acadcmic der Wissen-schaften zu Berlin, Phys.-Math. Klasse, 1930, p. 42-56.

[35] Jaskowski R. Recherches sur le systeme de la logique intuitioniste. // Actes du Congres Intern, de Philosophie Scientifique. Paris, part VI, 1936, p. 5861.

[36] Limai S., Post E.L., Recursive unsolvability of the deducibility, Tarski's comleteness, and independence of axioms problems of the propositional calculus (abstract). // Bulletin of the American Mathematical Society, vol. 55, 1949, p. 50.

[37] Post E.L. Two-valued iterative systems of mathematical logic. // Princeton Univ. Press, Princeton, 1941.

[38] Rosenberg J. La structure des fonctions de plusiers variables sur un ensemble fini. // Comptes Rendus Acad. Sci. Paris, №260, 1965, p. 38173819.

[39] Singletary W.E., A complex of problems proposed by Post. // Bulletin of the American Mathematical Society, vol. 70, num. 1, 1964, p. 105-109.

140] Solovay R. M. Provability interpretations of modal logic. / / Israel J. Math., vol. 25, №3-4, 1975, p. 287-304.

[41] Address at the princeton university bicentennial conference on problems of mathematics (December 17-19, 1946), by Alfred Tarski. // The Bulletin of Symbolic Logic, vol. 6, num. 1, 2000.

[42] Yntema M.K., A detailed argument for the Post-Linial theorems. // Notre Dame Journal of Formal Logic, vol. 5, num. 1, 1964, p. 37-50.

[43] Боков Г. В. Проблема полноты в исчислении высказываний. // Интеллектуальные системы, т. 13, вып. 1-4, 2009, с. 165-181.

[44] Боков Г. В. Критерий конечной порожденное™ пропозициональных исчислений. // Дискрет. Матем., т. 25, вып. 3, 2013, с. 63-81.

(45] Боков Г. В. Об алгоритмической неразрешимости проблемы выразимости пропозициональных исчислений. // Интеллектуальные системы, т. 17, вып. 1-4, 2013, с. 271-292.

(46] Боков Г. В. О конечной порожденности исчисления высказываний с произвольными операциями вывода // Интеллектуальные системы, т. 17, вып. 1-4, 2013, с. 267-270.

|47] Боков Г. В. О проблеме полноты в исчислении высказываний. // Материалы X Международного семинара «Дискретная математика и ее приложения» (Москва, МГУ, 1-6 февраля 2010 г.) / Отв. Ред.: В. В. Кочергин; под общ. ред.:0. М. Касим-Заде. М.: Механико-математический факультет МГУ, 2010, с. 345-348.

[48] Боков Г. В. Об алгебраических свойствах исчисления высказываний. / / Материалы Международного молодежного научного форума «JTOMOHOCOB-2010» / Отв. ред. И.А. Алешковский, П.Н. Костылев, А.И. Андреев, A.B. Андриянов. [Электронный ресурс] — М.: МАКС Пресс, 2010. - URL: http://www.lomonosov-msu.ru/archive/Lomonosov_2010/index.htm

|49] Боков Г. В. Обобщение теоремы Хенкина на случай k-значных логик. // Материалы Международного молодежного научного форума «ЛОМОНОСОВ-2011» / Отв. ред. А.И. Андреев, A.B. Андриянов, Е.А. Антипов, М.В. Чистякова. [Электронный ресурс] — М.: МАКС Пресс, 2011. - URL: http://www.lomonosov-msu. ru / archi ve/Lomonosov_2011 /1257/5161 _ 7cbd. pdf

[50] Боков Г. В. Об алгоритмически разрешимых случаях проблемы выразимости в пропозициональных исчислениях. / / Материалы Международного молодежного научного форума «ЛОМОНОСОВ-2012» / Отв. ред. А.И. Андреев, A.B. Андриянов, Е.А. Антипов, К.К. Андреев, М.В. Чистякова. [Электронный ресурс] — М.: МАКС Пресс, 2012. - URL: http://www.lomonosov-msu.ru/archive/Lomonosov_2012/1793/5161_a567.pdf

|51| Боков Г. В. Алгоритмическая разрешимость проблемы выразимости автоматно-отделимых подалгебр термов. // Материалы Международного молодежного научного форума «ЛОМОНОСОВ-2013» / Отв. ред. А.И. Андреев, A.B. Андриянов, Е.А. Ан-типов, К.К. Андреев, М.В. Чистякова. [Электронный ресурс| — М.: МАКС Пресс, 2013. - URL: http://www.lomonosov-msu.ru/archive/Lomonosov_2013/2193/5161_30ee.pdf

1/