Условия выразимости и полноты пропозициональных исчислений

• Автор: Боков, Григорий Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 91 с.

Оглавление
Введение
Основные понятия диссертации
1 Проблема базиса
1.1 Критерий конечно-порожденности
1.2 Мощность базисов
2 Структура решетки замкнутых классов тавтологий
2.1 Глубина и ширина решетки
2.2 Предполные классы
2.3 Дуально-предиолные классы
2.4 Критериальные системы
3 Проблема полноты и выразимости
3.1 Алгоритмическая неразрешимость проблемы выразимости .
3.2 Алгоритмическая неразрешимость проблемы полноты
Заключение
Литература

Введение
Общая характеристика работы
Актуальность темы
Диссертация является исследованием в области дискретной математики и математической кибернетики и посвящена изучению функциональных свойств пропозициональных исчислений.
Исчисление в общем смысле представляет собой множество формул С, некоторым набором операций, применимых к этим формулам и приводящих к получению других формул. Первоначально, конструкции такого рода служили только моделями для изучения рассуждений человеке, но с появлением электронных вычислительных машин и развитием математической кибернетики область их применимости значительно возросла, начиная с изучения реальных вычислительных систем как схем из функциональных элементов [24] и заканчивая моделированием логических процессов и искусственного интелекта [16].
При рассмотрении логических систем, частным случаем которых являются пропозициональные исчисления, можно выделить два направления: функциональный, когда на первый план выходит изучение функциональных свойств системы и где рассматриваются такие понятия, как замкнутые классы, полнота, нредполнота, базисы и т.п; и логический, в котором происходит изучение системы как объекта в виде системы аксиом и правил вывода. В работе будет рассмотрен первый подход.
В функциональном подходе в качестве логической системы рассматривается пара вида (М, П), где М является множеством объектов системы, а

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

Доказательство. Утверждение леммы будем доказывать индукцией по числу вхождений пДа) символов / Є Т,а, где а Є {/3,7,5}, в формулу 21. Если пи(сг) < 1 для все а Є {/3,7,5}, то в качестве формулы 23 можно взять 21.
Пусть утверждение леммы верно для па(гг), такого что 1 < п%(а) < Ау. Покажем, что оно верно и для пДа) = ка.
Согласно лемме 8 можно считать, что 21 не содержит одноместных символов из Еа и содержит не более одного символа из 5ф По аналогии с леммой 9 можно считать, что 21 не содержит одноместных символов из Ей и Е содержит только одну 0-местную /3-функцию и одну 0-местную 7-функцию, которые также обозначим через 1 и 0, соответственно.
Поскольку кпг > 1, то найдутся вхождения символов /, д Є Е„ в формулу 21. Тогда по лемме 7 и следствию 1 найдется такая формула 23, что 21 23 и 23 = /д23і...23п, где п = х(/) + х( 1. Поскольку
не имеет одноместных связок, то последовательным применением операций Г1Р из 23 можно вывести формулу £ вида
где {хц, ...,.тД все значащие переменные формулы 21, щ £ М, щ £ М+, г =
2,..., Н2иЭ это формула вида где т — арность К и
{X,;, если П,_1 = Мя(х,;_1) И 0 < Щ < /^(х,),
1, если щ = мя(х^) и 0 < пк+х < ма(1),
О, если пк+1 = г^а(1)-
Причем, для каждого г € А; + 2, если щ = 0, то п1+ = 0, а также, если п1+1 ^ 0, то щ = ма(х.().
Если щ 0 и п^+1 = 0, где г < к + 1, тогда по лемме 4 щ = ма(х;;) = 2ш^-, j = 1,...,г — 1. Так как f,g £ Е„ и и Е {/3,7,5}, то п = 2/ + 1, поэтому

пк пк+
2тх 2 ті 2т,