Мат. логика

Каждую фигур можно заполнить 4х4 = 16 вариантами. Учитывая, что фигур 4, получим 16х4 = 64 различных пар категорических суждений, связывающих крайние термины со средним. Однако не любая из этих пар порождает заключение, отличное от посылок, а лишь некоторые. Их оказывается 19, и именно они, вместе с вытекающими из них заключениями, называются силлогизмами.

Анализ отношений между тремя терминами M, S, P удобно проводить, рассматривая изображенную фигуру:

Из рисунка видно, что заключение A (S, P) – все S суть P – следует в тех случаях, когда оказываются пустыми области a и d.

Но это возможно лишь в одном случае: когда справедливы суждения

A (M, P) и A (S, M).

Когда возможно заключение E (S, P) – ни одно S не есть P. Пустыми должны быть области f и g.

Каковы условия вывода I (S, P)? Ответ: некоторые S суть P. Надо доказать непустоту областей f и g.

Особый случай:

A(M,P)

A(S,M)

¯¯¯¯¯¯¯

I(S,P) (1,A,A)->I

У нас есть (1,A,A)->A Поглощает

O(M,P)

A(M,S)

¯¯¯¯¯¯¯

O(S,P) (3,O,A)->O

33.Аксиоматическое исчисление предикатов. Теоремы о корректности и полноте исчисления предикатов.

Замечание об аксиоматическом исчислении предикатов

Аксиоматическая теория предикатов может быть построена аналогично тому, как была построена аксиоматическая теория высказывания. При этом, необходимо заметить:

1)Алфавит и определение формулы исчисления высказывания то же, что и в алгебре предикатов.

2)В качестве системы аксиом может быть взята система, в которую включены 11 аксиом ИВ, и добавить две дополнительные аксиомы.

12.

13. , где А(С) не содержит переменной х.

3) К правилам вывода, которые используется в ИВ, добавляются еще два правила. А) Правило обобщения:

Б) Правило конкретизации:

, где А(х) и В – это произвольные формулы ЛП, В не содержит

свободных вхождений х.

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

5)Для исчисления предикатов первого порядка справедлива теорема Геделя.

├Е  ╞Е

Отсюда вытекает:

А) ИП не противоречиво.

Б) ИП полно относительно общезначимости.

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

конечное число шагов. По-видимому, это основная причина, по которой ИП неразрешимо.

Если быть более строгим, то ИП полуразрешимо. Это означает, что если формула Е общезначима, то существует алгоритм, доказывающий формулу Е.

Теорема корректности (|-E => |=E). Если существует вывод замкнутой формулы F из множества формул G, тогда G влечёт F.

Теорема полноты (|=E => |-E). Для любой замкнутой формулы F и любого множества предложений G, если G влечёт F, то существует вывод F из некоторого подмножества G.

Аксиома №18 – аксиома индукции, точнее, аксиомная схема, так как в её формулировке имеется метознак «Р», обозначающий произвольную формулу арифметики.

Интерпретация аксиом:

14 – «два объекта, порознь равные третьему, равны между собой» 15 – «каждое натуральное число непосрдственно следует не более чем за одним натуральным

числом» 16 – «0 непосредственно не следует ни за каким натуральным числом»

17 – «за каждым натуральным числом непосредственно следует точно одно натуральное число» 18 – «если 0 обладает некоторым свойством Р и для любого натурального числа х из того, что х

обладает свойством Р, вытекает, что и непосредственно следующее за ним число х обладает этим свойством, то всякое натуральное число обладает свойством Р»

19, 20 – рекурсивно определяют сложение 21,22 – рекурсивно определяют умножение

Правила вывода

В систему правил вывода включаются правила вывода теории PL, а также используется специальное правило вывода – правило индукции (I), основанное на аксиоме индукции №18.

Формальное доказательство в теории Ar.

Определение. Доказательство формулы В в теории Ar называется конечная последовательность формул В1,В2,…,Вк (В) этой теории, такая, что каждая формула этой последовательности есть либо

аксиома, либо получена из предшествующих по одному из правил вывода. Обозначение:

Заключение Аксиомы (15)-(18) составляют содержательную аксиоматику Пеано для арифметики натуральных

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

Джузеппе Пеано (1858-1932) – итальянский математик. Более всего известен как автор стандартной аксиоматизации натуральной арифметики – арифметики Пеано.

35. Гёделевская нумерация.

Гёдель показал, что каждому элементарному символу, каждой формуле (т.е. цепочке элементарных символов) и каждому доказательству (конечной последовательности формул) можно однозначным образом приписать определенный номер (натуральное число).

Гёделевский номер символа.

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

Гёделевский номер формулы.

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

Введем в рассмотрение функцию γ, аргументом которой является формула, а значением – гёдельский номер этой формулы. Тогда можно записать:

Очевидно, что .

Заметим, что не каждому натуральному числу, большему 16, соответствуют определенная формула системы.

Для m = 100, получим:

– тарабарщина

Гёделевский номер доказательства. Пусть последовательность формул Ф1, Ф2,…,Фк образует доказательство своей последней формулы Фк.

Обозначим через Г функцию, аргументом которой является последовательность символов, составленная из формул доказательства, а значением – гёделевский номер этого доказательства. Тогда Г определим так:

где Рk – k-тое простое число.

Нетрудно видеть, что по номеру m однозначно определяются формулы Ф1, Ф2,…,Фк доказательства,

то есть

Г-1(m) = Ф1, Ф2,…,Фк.

Таким образом, если нам дано какое-нибудь выражение (символ алфавита, формула или доказательство), мы без труда напишем его гёделевский номер. Это, однако, лишь полдела.

Важно то, что когда нам дано какое-либо натуральное число, то мы можем установить, является ли это число гёделевским номером, а если да – то можем точно «восстановить» обозначаемое этим номером выражение.

Действительно, если данное число не превосходит 16, то это просто номер некоторого символа алфавита арифметики.

Если же данное число больше 16, то его можно разложить, причем единственным образом (в этом состоит так называемая основная теорема арифметики), на простые сомножители:

Если при этом , то речь дальше должна идти о доказательстве длины n, у которого

– гёделевские номера соответствующих формул

36. Теорема Гёделя о неполноте.

Нетрудно видеть, что ранее рассмотренные определения формулы и доказательства позволяют построить алгоритмы для ответа на следующие вопросы:

1.Является ли данная цепочка символов формулой или нет?

2.Является ли данная последовательность формул доказательством или нет?

Отсюда вытекает возможность построения алгоритма, позволяющего определить: является ли данное натуральное число гёделевским номером определенного выражения, а если да – то восстановить это выражение (символ, формулу или доказательство).

Пусть, например, нам дано число 9.474.609.375. Разложим его (оно, очевидно, составное) на простые сомножители:

9.474.609.375 = 20*32*59*72*111

Поскольку γ1 = 2 < 16, то по-видимому это формула. Восстанавливаем цепочку символов, которая является формулой:

(неполноты) системы аксиом и ее можно устранить дополнением этой системы формулой G(n0), выражающий истинное предложение, в качестве новой аксиомы.

В этом случае мы получим расширенную систему A`r. Гёдель показал, что и в этой системе A`r найдется некоторое истинное, но недоказуемое высказывание, т.е. и A`r оказывается неполной.

Аналогичен можно построить системы A``r, A```r, … , для которых также будет верна теорема Гёделя. Неполнота Ar обусловлена принципиальной невозможностью полной формализации такой

содержательной части математики, как арифметика натуральных чисел.

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

Теорема Гёделя о неполноте известна также под названием «Первая теорема Гёделя», которая в расширенной формулировке звучит так:

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

1.В Т имеются содержательно истинные недоказуемые формулы, т.е. такие формулы А, что ни А, ни недоказуемы;

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

Вторая теорема Гёделя касается доказательства непротиворечивости формальной системы Ar. В частности, доказана возможность выражения с помощью формулы Ar непротиворечивости этой же системы. Однако эта формула недоказуема в Ar, откуда и следует Вторая теорема Гёделя: непротиворечивость системы Ar недоказуема в Ar.

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

Со времен доказательства Гёделем своей теоремы математики искали примеры таких истинных теорем, которые было бы невозможно доказать, используя аксиоматику Пеано.

Только в 1977 году удалось обнаружить такую теорему в комбинаторике, так называемую бесконечную теорему Рамсея.

В 1982 году Л. Кирби и Дж. Парис показали, что теорема Гудстейна эквивалентна утверждению о непротиворечивости арифметике Пеано, а поэтому, в силу второй теоремы Гёделя, она недоказуема (но может быть доказана, например, в арифметике второго порядка).

37.Интуитивное определение алгоритма. Эквивалентность различных теорий алгоритмов. Тезис Чёрча.

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

Характерные черты для алгоритмического процесса имеют вид:

1.Элементарность шагов алгоритма: решение задачи распадается на ряд шагов, каждый из которых является достаточно простым.

2.Детерминированность: после выполнения очередного шага однозначно определено, что делать на следующем шаге.

3.Массовость: алгоритм пригоден для решения всех задач из заданного класса.

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

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

в) нормальные алгоритмы Маркова г) канонические системы Поста и др.

Впоследствии было установлено, что эти модели эквивалентны в том смысле, что классы решаемых ими задач совпадают.

Впервые эта гипотеза была высказана (в несколько ином виде) А. Чёрчем и носит название тезиса Чёрча: класс задач, решаемых в любой из формальных моделей алгоритма, и есть класс всех задач, которые могут быть решены «интуитивно алгоритмическими» методами.

Сейчас этот тезис является общепризнанным. Формальное определение понятия алгоритма создало предпосылки для разработки теории алгоритмов.

Эквивалентность различных теорий алгоритмов

Справедлива теорема:

Следующие классы функций (заданных на натуральных числах и принимающих натуральные значения) совпадают:

a) класс всех функций, вычислимых по Тьюрингу; б) класс всех частично-рекурсивных функций; в) класс всех нормально вычислимых функций.

Отсюда следует, что любые утверждения о существовании или несуществовании алгоритмов, сделанные в одной из трех формализаций, верны и в других. Поэтому возможна общая теория алгоритмов, независящая (инвариантная) от способа формализации понятия «алгоритм». Основные её понятия – алгоритм и вычислимая функция.

38.Машина Тьюринга. Вычисление функций на машинах Тьюринга. Тезис Тьюринга.

Машина Тьюринга состоит из бесконечной в обе стороны ленты, разбитой на ячейки, и рабочей головки.

Машина работает в дискретные моменты времени t = 0,1,2,…

В ячейках ленты может быть записана любая буква алфавита А = {а0, а1,…,ак-1} (А – внешний алфавит машины). a0 – пустой символ; обозначим его λ.

Головка может находиться в одном из конечного числа внутренних состояний

Q = {q0,q1,…,qr-1}.

Если головка в состоянии qi читает символ ai, то в следующий момент времени она записывает в эту ячейку вместо аi символ аi1, переходит в состояние qi1 и, в зависимости от того, совпадает ли S с П, Л или Н, головка сдвигается на одну ячейку вправо, влево или остается на месте.

То есть работа машины задается системой команд вида:

qiai → qi1ai1S

Пусть q0 – заключительное состояние. Попав в это состояние, машина останавливается.

Для каждой пары qiai (qi ϵ Q \ {q0}, ai ϵ A) имеется ровно одна команда с левой частью qiai. Всего команд – (r-1)k.

Совокупность этих команд определяет программу машины.

Работа машины состоит в изменении её конфигурации. Под конфигурацией в момент времени t понимается распределение букв по ячейкам ленты, состояние головки и обозреваемая ячейка в момент t.

Если конфигурация Кt не является заключительной, она в соответствии с очередной командой переходит в конфигурацию Кt+1. Всякая начальная конфигурация К0 порождает последовательность конфигураций К0, К1,…,Кt,…

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

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

Вычисление функций на машинах Тьюринга

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

Если активная зона имеет длину р и в ней записано слово а(1)…а(р), а головка обозревает букву а(i) этого слова в состоянии q, то такую конфигурацию будем представлять словом длины р+1:

а(1)…а(i-1)q а(i)…а(р), в котором состояние q указывается перед обозреваемым символом.

Пример.

q2 λλλλ11 λλ0

1q20λλ0

Введем обозначения:

q1 – начальное состояние

P – слово, записанное на ленте, перед началом работы машины. q1P – начальная конфигурация.

f – словарная функция, отображающая слова в слова. f(P) – значение функции f на слове Р

q0f(P) – заключительная конфигурация, если f(P) определена.