Математическая логика и теория алгоритмов

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

очевидны Мы выбираем в качестве аксиом такие законы, которые очевидны исходя из природы рассматриваемых объектов. во множестве N существует элемент 1, который не следует ни за каким элементом. Например, рассматривая N множество натуральных чисел, мы говорим: во множестве N существует элемент 1, который не следует ни за каким элементом. При этом мы должны разъяснить, что означает понятие «следовать за». Необходимо выразить это понятие, через другие, ранее разъясненные понятия. просты и ясны А чтобы процесс не был бесконечным, мы должны выбрать некоторые основные понятия, которые остаются неопределяемыми. К основным понятиям, так же как и к аксиомам, предъявляется требование: они должны быть столь просты и ясны, что мы можем понимать их без точного определения. Остальные понятия, называемые производными понятиями, определяются в терминах основных.

Опишем кратко построение аксиоматической теории в общем случае. Если нам требуется доказать утверждение A, то в процессе доказательства мы ссылаемся на ранее полученные утверждения A 1, A 2,... Аналогично, для доказательства каждого из утверждений A 1, A 2... нужны ранее доказанные утверждения B 1, B 2,... Чтобы процесс не был бесконечным, мы должны выбрать некоторые начальные законы, называемые аксиомами, которые принимаются без доказательства. Остальные законы, называемые теоремами, доказываются, исходя из аксиом. На каком основании мы принимаем аксиомы? Вначале мы вводим некоторые основные понятия и аксиомы об этих понятиях. Далее переходим к определению производных понятий и доказываем теоремы об основных и производных понятиях. Система, состоящая из основных понятий, производных понятий, аксиом и теорем, называется аксиоматической теорией. Это может быть, например, аксиоматическим построением теории групп, планиметрии или теории натуральных чисел.

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

На рубеже 19–20 веков аксиоматический метод продемонстрировал значительные достижения: Р.Дедекиндом (1888 г.) и Дж.Пеано (1891 г.) разработана аксиоматическая теория натуральных чисел, Давидом Гильбертом (1899 г.) получено аксиоматическое построение евклидовой геометрии. Как основа большинства математических дисциплин в это время уже выступает теория множеств., парадокс Рассела (1903 г.) В это же время в теории множеств были обнаружены парадоксы, например, парадокс Рассела (1903 г.) Рассмотрим всевозможные множества и разделим их на два вида. 1) Множества, которые не являются элементом самого себя, т.е. M /M. 2) Множества, которые являются элементом самого себя, т.е. M M.

Ясно, что для любого множества M выполнено одно и только одно из условий 1) или 2). Рассмотрим множество X, элементами которого являются все множества вида 1). Значит, X состоит из всех множеств, не являющихся элементом самого себя X = {M | M /M}. (1) Множество X нельзя отнести к типу 2). Допустив, что X типа 2), мы получим: X является элементом самого себя, т.е. X ={A,B,...,X,...}. Это противоречит правилу (1) задания множества X. Поэтому множество X типа 1). И множество X не является элементом самого себя, X /X. Однако X состоит из всех множеств, не являющихся элементом самого себя и запись X /X по правилу задания множества X требует включения X X. Получили одновременно X /X и X X, это противоречие. В итоге, не выполнено ни 1), ни 2) парадокс в основаниях теории множеств.

Объяснение парадокса После ряда исследований этого парадокса выработано понимание, что здесь нет противоречия с интуитивным понятием множества. Действительно, для образования множества X мы собираем вместе некоторые объекты, которые в своей совокупности и составляют единственный объект, являющийся множеством X. Следовательно, перед тем, как множество X образовано, мы должны иметь в распоряжении все объекты, которые являются элементами из X. Отсюда следует, что множество X всегда не является элементом для X и парадокс Рассела исчезает. Хотя и данный парадокс получил разумное объяснение, среди математиков возникло убеждение о необходимости анализа логических средств, применяемых при построении аксиоматических теорий.

Задача о брадобрее (парадокс Рассела)

Формальная теория считается заданной, Формальная теория считается заданной, если известны следующие четыре составляющих: 1. Алфавит – конечное или счетное множество символов. 2. Формулы, которые по специальным правилам строятся из символов алфавита. Формулы, как правило, составляют счетное множество. Алфавит и формулы определяют язык или сигнатуру формальной теории. 3. Аксиомы – выделенное из множества формул специальное подмножество. Множество аксиом может быть конечным или бесконечным. Бесконечное множество аксиом задается с помощью конечного множества Схем аксиом и правил порождения конкретных аксиом из схемы аксиом. Различают два вида аксиом: Логические (общие для класса формальных теорий) и Собственные (определяющие содержание конкретной теории). 4. Правила вывода – множество отношений (как правило, конечное) на множестве формул, позволяющие из аксиом получать теоремы формальной теории. Обратите внимание, что здесь аксиомы – это необязательно утверждения, не требующие доказательства.

Выводом А 1, А 2 …А n Определение. Выводом формальной теории называется последовательность формул А 1, А 2 …А n, в которой все формулы – либо аксиомы, либо получаются из предыдущих по правилам вывода. формула A выводима из множества формул Г (обозначение: Г А), Говорят, что формула A выводима из множества формул Г (обозначение: Г А), существует вывод А 1, А 2 …А n, где А n =А если существует вывод А 1, А 2 …А n, где А n =А и есть три возможности: - аксиома - аксиома получаются из предыдущих формул по правилам вывода. получаются из предыдущих формул по правилам вывода. посылками гипотезами вывода. Формулы из множества Г называются посылками или гипотезами вывода. выводимой теоремой В частном случае, когда, имеет место обозначение: А, и формула называется выводимой в данной теории (или теоремой данной теории).

Строя аксиоматическую теорию, мы должны полностью описать те средства логики (правила вывода), которые применяются для получения теорем. Все теоремы должны выводится из аксиом, а аксиомы у нас просто строки символов. Поэтому данные правила должны описывать действия со строками и указывать, как из ранее полученных теорем получаются новые теоремы. Эти правила вывода будут иметь следующий вид A1,A2,...,An B(3) При этом A1,A2,...,An посылки, а B заключение правила вывода. если A1,A2,...An теоремы теории, то B также является теоремой. Правило вывода утверждает: если A1,A2,...An теоремы теории, то B также является теоремой. определение теоремы После этого определение теоремы можно сформулировать следующим образом. 1. Всякая аксиома является теоремой. 2. Если имеется некоторое правило вывода (3), и A1,A2,...An теоремы, то B также теорема. 3. То, что выражение является теоремой, устанавливается несколькими применениями правил 1) и 2).

Исчисление высказываний (теория L) Исчисление высказываний (теория L) определяется следующими компонентами. 1. Алфавит составляют: Пропозициональные буквы А, В, С… А 1, А 2 … Логические связки: Скобки: ( ) Иногда в исчислении высказываний допускаются формулы с другими логическими связками, но при этом учитывается, как они выражаются через инверсию и импликацию. 2. Формулы определяются 2. Формулы определяются т.о. :Определение. 1) Всякая пропозициональная буква есть формула. 2) Если А, В – формулы, то формулами являются также тогда и только тогда 3) Символ является формулой тогда и только тогда, когда это следует из 1) и 2).

3. 3. Аксиомы задаются тремя схемами аксиом: А1. А2. А3. Существуют исчисления высказываний с другим набором логических связок и другими схемами аксиом. 4. Modus ponens MPправило отделения 4. Правило вывода Modus ponens (сокращенно MP) – правило отделения (лат.) В где А, В– любые формулы. Множество аксиом исчисления высказываний, заданное тремя схемами аксиом, бесконечно. 1-ый способ записи 2-ой способ записи

Теорема.Все теоремы исчисления высказываний – тавтологии. Теорема. Все теоремы исчисления высказываний – тавтологии. Следствие. Исчисление высказываний непротиворечиво. Доказательство. Предположим противное, то есть в исчислении есть теоремы А и. По доказанной теореме они являются тавтологиями (тождественно истинными формулами), следовательно, формула А одновременно является тождественно истинной и тождественно ложной, что является противоречием. Теорема дедукции. Пусть Г – множество формул, А, В – формулы. Г, А В Г А В Теорема дедукции. Пусть Г – множество формул, А, В – формулы. Тогда Г, А В Г А В Справедлива и обратная теорема. Теорема. Пусть Г – множество формул, А, В – формулы. Г А В Г, А В Тогда Г А В Г, А В Теорема о полноте. Теорема о полноте. Всякая тавтология является теоремой исчисления высказываний. Следствие. Следствие. Множество всех теорем исчисления высказываний совпадает с множеством всех тавтологий.

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

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

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