КУРСОВАЯ РАБОТА
«Неразрешимостьлогики первого порядка»
Введение
формальный неразрешимость логика остановка
Философысформулировали наиболее важные идеи искусственного интеллекта, но дляпреобразования его в формальную науку потребовалось достичь определенногоуровня математической формализации в трех фундаментальных областях: логика,вычисления и вероятность.
Истоки идейформальной логики можно найти в работах философов древней Греции, но еестановление как математической дисциплины фактически началась с трудов ДжорджаБуля (1815–1864), который детально разработал логику высказываний, или булевулогику. В 1879 году Готтлоб Фреге (1848–1925) расширил булеву логику длявключения в нее объектов и отношений, создав логику первого порядка, которая внастоящее время используется как наиболее фундаментальная система представлениязнаний.
Одним изпринципиально важных результатов математической логики является доказательствонеразрешимости в логике первого порядка распознавания проблем какобщезначимости, так и выполнимости ее предложений.
Цельисследования – изучить доказательства неразрешимости логики первого порядка.Для достижения данной цели необходимо выделить ряд задач:
1. Изучитьосновные понятия логики первого порядка.
2. Рассмотретьпонятие машины Тьюринга и доказать неразрешимость проблемы остановки.
3. Вывестинеразрешимость логики первого порядка из неразрешимости проблемы остановки.
4. Разобратьдоказательство неразрешимости логики первого порядка методом Геделя.
1. Понятие формальной системы
Формальнаясистема (или формальная теория) – результат строгой формализации теории,предполагающей полную абстракцию от смысла слов используемого языка, причем всеусловия, регулирующие употребление этих слов в теории, явно высказаныпосредством аксиом и правил, позволяющих вывести одну фразу из других.
Формальнаятеория считается определенной, если:
- заданоконечное или счётное множество произвольных символов (конечныепоследовательности символов называются выражениями теории);
- имеетсяподмножество выражений, называемых формулами;
- выделеноподмножество формул, называемых аксиомами;
- имеетсяконечное множество отношений между формулами, называемых правилами вывода.
Обычноимеется эффективная процедура, позволяющая по данному выражению определить,является ли оно формулой. Часто множество формул задаётся индуктивнымопределением. Как правило, это множество бесконечно. Множество символов имножество формул в совокупности определяют язык или сигнатуру формальнойтеории.
Чаще всегоимеется возможность эффективно выяснять, является ли данная формула аксиомой; втаком случае теория называется эффективно аксиоматизированной илиаксиоматической. Множество аксиом может быть конечным или бесконечным. Еслимножество аксиом бесконечно, то, как правило, оно задаётся с помощью конечногочисла схем аксиом и правил порождения конкретных аксиом из схемы аксиом. Обычноаксиомы делятся на два вида: логические аксиомы (общие для целого классаформальных теорий) и нелогические или собственные аксиомы (определяющиеспецифику и содержание конкретной теории).
Для каждогоправила вывода R и для каждой формулы A эффективно решается вопрос о том,находится ли выбранный набор формул в отношенни R с формулой A, и если да, то Aназывается непосредственным следствием данных формул по правилу R.
Выводом называется всякаяпоследовательность формул такая, что всякая формула последовательности естьлибо аксиома, либо непосредственное следствие каких-либо предыдущих формул поодному из правил вывода.
Формуланазывается теоремой, если существует вывод, в котором эта формулаявляется последней.
Теория, длякоторой существует эффективный алгоритм, позволяющий узнавать по даннойформуле, существует ли ее вывод, называется разрешимой; в противномслучае теория называется неразрешимой.
Теория, вкоторой не все формулы являются теоремами, называется абсолютнонепротиворечивой.
Дедуктивнаятеория считается заданной, если:
– заданалфавит (множество) и правила образования выражений (слов) в этом алфавите;
– заданыправила образования формул (правильно построенных, корректных выражений);
– измножества формул некоторым способом выделено подмножество T теорем (доказуемыхформул).
Свойствадедуктивных теорий:
1. Противоречивость. Теория, в котороймножество теорем покрывает всё множество формул (все формулы являютсятеоремами, «истинными высказываниями»), называется противоречивой. В противномслучае теория называется непротиворечивой. Выяснение противоречивости теории – однаиз важнейших и иногда сложнейших задач формальной логики. После выясненияпротиворечивости теория, как правило, не имеет дальнейшего ни теоретического,ни практического применения.
2. Полнота. Теория называетсяполной, если в ней для любой формулы F выводима либо сама F, либо ее отрицание.В противном случае, теория содержит недоказуемые утверждения (утверждения,которые нельзя ни доказать, ни опровергнуть средствами самой теории), иназывается неполной.
3. Независимостьаксиом.Отдельная аксиома теории считается независимой, если эту аксиому нельзя вывестииз остальных аксиом. Зависимая аксиома по сути избыточна, и ее удаление изсистемы аксиом никак не отразится на теории. Вся система аксиом теорииназывается независимой, если каждая аксиома в ней независима.
4. Разрешимость. Теория называетсяразрешимой, если в ней понятие теоремы эффективно, то есть существуетэффективный процесс (алгоритм), позволяющий для любой формулы за конечное числошагов определить, является она теоремой или нет.2. Основные понятия логики первого порядка
Логикапервого порядка (исчисление предикатов) – формальное исчисление, то есть этосовокупность абстрактных объектов, не связанных с внешним миром, в которомпредставлены правила оперирования множеством символов в строго синтаксическойтрактовке без учета смыслового содержания.
Язык логики первогопорядка строится на основе сигнатуры, состоящей из следующих символов:
1) логические
– символылогических операций ¬, />, />, ↔, →;
– символыкванторных операций ", $;
– служебныесимволы: скобки и запятая.
2)нелогические
– множествопредикатных символов, с которым связана арность, то есть число возможныхаргументов P(n), Q(m), …, P1(n), P2(n);
– символыпропозициональных переменных X, Y, Z, …, X1, X2, … (можно считать, что символы пропозициональных переменных – этонульместные предикатные символы);
– символыпредметных переменных x, y, z, …, x1, x2,…;
– символыпредметных констант a, b, c, …, a1, a2, …
n-местным предикатом P (x1, x2,…, xn) называется функция P: M1ЧM2Ч…ЧMn → {1,0},определенная на наборах длины n элементов некоторого множества M= M1ЧM2Ч…ЧMn и принимающая значения вобласти {1,0}. Множество М называется предметной областью предиката, егоэлементы – предметными константами.
ОтрицаниемпредикатаP(x1, x2,…, xn), определенного намножестве M1ЧM2Ч…ЧMn называется предикат ¬P(x1, x2,…, xn), определенный на том жемножестве, который на наборе (a1, a2,…, an) /> M1ЧM2Ч…ЧMn
/>
КонъюнкциейпредикатовP(x1, x2,…, xn), определенного намножестве M1ЧM2Ч…ЧMn, и Q(y1, y2,…, ym), определенного на множестве N1ЧN2Ч…ЧNm, называется предикат P /> Q(x1, x2,…, xn, y1, y2,…, ym) c пердметной областью M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn, который на наборе (a1, a2,…, an, b1, b2,…, bm) /> M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn
/>
ДизъюнкциейпредикатовP(x1, x2,…, xn), определенного намножестве M1ЧM2Ч…ЧMn, и Q(y1, y2,…, ym), определенного на множестве N1ЧN2Ч…ЧNm, называется предикат P /> Q(x1, x2,…, xn, y1, y2,…, yn) c пердметной областью M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn, который на наборе (a1, a2,…, an, b1, b2,…, bm) /> M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn
/>
Импликацией предикатов P(x1, x2,…, xn), определенного намножестве M1ЧM2Ч…ЧMn, и Q(y1, y2,…, ym), определенного на множестве N1ЧN2Ч…ЧNm, называется предикат P → Q(x1, x2,…, xn, y1, y2,…, yn) c пердметной областью M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn, который на наборе (a1, a2,…, an, b1, b2,…, bm) /> M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn
/>
Эквивалентностью предикатов P(x1, x2,…, xn), определенного намножестве M1ЧM2Ч…ЧMn, и Q(y1, y2,…, ym), определенного на множестве N1ЧN2Ч…ЧNm, называется предикат P(x1, x2,…, xn) ↔ Q (y1, y2,…, yn) c пердметной областью M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn, который на наборе (a1, a2,…, an, b1, b2,…, bm) /> M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn
/>
Операциейсвязыванияквантором общности переменной xi в n-местном предикате P(x1, x2,…, xn)), определенном намножестве M1ЧM2Ч…ЧMn, называется операция, в результате которой получается n-1-местный предикат " xi P(x1, x2,…, xi-1, xi+1,…, xn), который при значениях x1 = a1, …, xi-1 = ai-1, xi-1 = ai-1, …, xn= anистинен, если при любыхзначениях xi= ai высказывание P(a1, a2,…, an) истинно.
Операциейсвязывания квантором существования переменной xi в n-местном предикате P(x1, x2,…, xn) называется операция, врезультате которой получается n-1-местный предикат $ xi P(x1, x2,…, xi-1, xi+1,…, xn), который при значениях x1 = a1, …, xi-1 = ai-1, xi-1 = ai-1, …, xn= anистинен, если принекотором значении xi= ai высказывание P(a1, a2,…, an) истинно.
Вхождениекакой-либо переменной в формулу, называется свободным, если оно не входит вобласть действия никакого квантора по этой переменной.
Формулами логики предикатов являются:
– всякаянульместная предикатная переменная;
– P(n) (x1, x2,…, xn), где P(n) – n-местная предикатнаяпеременная, а x1, x2,…, xn – свободные переменные;
– />F, где F – формула;
– F1 /> F2, F1 /> F2, F1 ↔ F2, F1 → F2, где F1 и F2 – формулы, в которыхобщие переменные являются одновременно свободными или одновременно связанными;
– " xi P(x1, x2,…, xi-1, xi+1,…, xn) и $ xi P(x1, x2,…, xi-1, xi+1,…, xn), где P(x1, x2,…, xn) – формула, в которой xi – свободная переменная
Определениеистинности формул алгебры предикатов вводится с помощью интерпретации. Вклассическом случае интерпретация определяется следующими данными
1) предметнаяобласть;
2) всякойпредметной константе ставится в соответствие некоторый предмет, определенный вобласти;
3) каждомупропозициональному символу ставится в соответствие некоторое значение 1(истина) или 0 (ложь);
4) каждомупредикатному символу языка ставится в соответствие некоторая характеристическаяфункция.
Классификацияформул:
Формуланазывается
а) выполнимой(опровержимой) на множестве М, если существует ее истинная (ложная)интерпретация на этом множестве;
б) тождественно-истинной(тождественно-ложной) на множестве М, если любая ее интерпретации на этомна этом множестве истина (ложна);
в) выполнимой(опровержимой), если существует предметная область, на которой она выполнима(опровержима);
г) общезначимой(противоречием), если на любой предметной области она тождественно-истинная(тождественно-ложная).
Множествомистинностипредиката P(x1, x2,…, xn), заданного на множествеM1ЧM2Ч…ЧMn, называется совокупностьвсех упорядоченных систем (a1, a2,… an), в которых a1 е M1a2 е M2,…, an е Mn, таких, что данныйпредикат обращается в истинное высказывание Р(a1, a2,… an) при подстановке x1 = a1 x2 = a2,…, xn = an. Обозначается P+.
Два n-местных предиката Р(x1, x2,…, xn) и Q(x1, x2,…, xn), заданных на одном итом же множестве M1ЧM2Ч…ЧMn называются равносильными, если набор предметов a1 е M1a2 е M2,…, an е Mn превращает первыйпредикат в истинное высказывание Р(a1, a2,… an) тогда же, когда этотнабор предметов превращает второй предикат в истинное. Переход от предиката Р(x1, x2,…, xn) к равносильному емупредикату Q(x1, x2,…, xn) называется равносильнымпреобразованием первого.
Предикат Р(x1, x2,…, xn), заданный на множестве M1ЧM2Ч…ЧMn называется следствиемпредиката Q(x1, x2,…, xn), если он превращается вистинное высказывание на всех тех наборах значений предметных переменных изсоответствующих множеств, на которых в истинное высказывание превращаетсяпредикат Q(x1, x2,…, xn). 3. Понятиемашины Тьюринга
МашинаТьюринга есть математическая (воображаемая) машина, а не машина физическая. Онаесть такой же математический объект, как функция, производная, интеграл, группаи т.д. И так же как и другие математические понятия, понятие машины Тьюрингаотражает объективную реальность, моделирует некие реальные процессы.
МашиныТьюринга– это совокупность следующих объектов
1) внешнийалфавит A={a0, a1, …, an};
2) внутреннийалфавит Q={q1, q2,…, qm} – множество состояний;
3) множествоуправляющих символов {П, Л, С}
4) бесконечнаяв обе стороны лента, разделённая на ячейки, в каждую из которых в любойдискретный момент времени может быть записан только один символ из алфавита А;
5) управляющееустройство, способное находиться в одном из множества состояний
Символом пустой ячейки является буква внешнего алфавитаа0.
Среди состояний выделяются два – начальное q1,находясь в котором машина начинает работать, и заключительное (или состояниеостановки) q0, попав в которое машина останавливается.
Управляющееустройство может перемещаться влево и вправо по ленте, читать и записывать вячейки ленты символы алфавита A. Управляющее устройство работает согласно командам, которыеимеют следующий вид
qiaj →apXqk
Записьозначает следующее: если управляющее устройство находится в состоянии qi, а в обозреваемой ячейкезаписана буква aj, то (1) в ячейку вместо aj записывается ap, (2) машина переходит кобозрению следующей правой ячейки от той, которая обозревалась только что, еслиХ= П, или к обозрению следующей левой ячейки, если Х= Л, или же продолжаетобозревать ту же ячейку ленты, если Х= С, (3) управляющее устройство переходитв состояние qk.
Посколькуработа машины, по условию, полностью определяется ее состоянием q, в данный момент исодержимым а обозреваемой в этот момент ячейки, то для каждой возможнойконфигурации qiaj имеется ровно одноправило. Правил нет только для заключительного состояния, попав в котороемашина останавливается. Поэтому программа машины Тьюринга с внешним алфавитом A={a0, a1, …, an} и внутренним Q={q1, q2,…, qm} содержит не более m (n+ 1) команд.
Словом в алфавите А или валфавите Q, или в алфавите A /> Q называется любая последовательностьбукв соответствующего алфавита. Под k-ой конфигурацией будем понимать изображение лентымашины с информацией, сложившейся на ней к началу k-того шага (или слово валфавите А, записанное на ленту к началу k-того шага), с указаниемтого, какая ячейка обозревается в этот шаг и в каком состоянии находитсямашина. Имеют смысл лишь конечные конфигурации, т.е. такие, в которых всеячейки ленты, за исключением, быть может, конечного числа, пусты. Конфигурацияназывается заключительной, если состояние, в котором при этом находитсямашина, заключительное.
Если выбратькакую-либо незаключительную конфигурацию машины Тьюринга в качестве исходной,то работа машины будет состоять в том, чтобы последовательно (шаг за шагом) преобразовыватьисходную конфигурацию в соответствии с программой машины до тех пор, пока небудет достигнута заключительная конфигурация. После этого работа машиныТьюринга считается закончившейся, а результатом работы считается достигнутая заключительнаяконфигурация.
Будемговорить, что непустое слово б в алфавите А\ {а0} = {a1, …, an} воспринимается машинойв стандартном положении, если оно записано в последовательных ячейках ленты,все другие ячейки пусты, и машина обозревает крайнюю слева или крайнюю справаячейку из тех, в которых записано слово б. Стандартное положение называетсяначальным (заключительным), если машина, воспринимающая слово в стандартномположении, находится в начальном состоянии q1 (соответственно всостоянии остановки q0).
Еслиобработка слова б переводит машину Тьюринга в заключительное состояние, тоговорят, что она применима к б, в противном случае – неприменима к б (машина работает бесконечно)
Рассмотримпример:
Дана машинаТьюринга с внешним алфавитом А = {0, 1} (здесь 0 – символ пустой ячейки),алфавитом внутренних состояний Q = {q0, q1, q2} и со следующейфункциональной схемой (программой):
q1 0 → 1 Л q2;
q1 1 → 0 Сq2;
q2 0 → 0 П q0;
q2 1 → 1 Сq1;
Даннуюпрограмму можно записать с помощью таблицы 1
q1
1 Л q2
0 С q2
q2
0 П q0
1 С q1
Посмотрим, вкакое слово переработает эта машина слово 110, исходя из начального положения:
q1… 1 1 …
На первомшаге действует команда: q1 0 → 1 Л q2 (управляющее устройствонаходится в состоянии q1, а в обозреваемой ячейке записана буква 0, в ячейку вместо 0записывается 1, головка сдвигается влево, управляющее устройство переходит всостояние q2),в результате на машине создается следующая конфигурация:
q2… 1 1 1 …
На второмшаге действует команда: q2 1 → 1Сq1 и на машине создаетсяконфигурация:
q1… 1 1 1 …
Третий шагобусловлен командой: q1 1 → 0 Сq2. В результате неесоздается конфигурация:
q2… 1 1 …
Наконец,после выполнения команды q2 0 → 0 П q0создается конфигурация
q0… 1 1 …
Этаконфигурация является заключительной, потому что машина оказалась в состоянииостановки q0.
Такимобразом, исходное слово 110 переработано машиной в слово 101.
Полученнуюпоследовательность конфигураций можно записать более коротким способом(содержимое обозреваемой ячейки записано справа от состояния, в котором находитсяв данный момент машина):
11q10 => 1q211 => 1q111 => 1q201 => 10q01
МашинаТьюринга – не что иное, как некоторое правило (алгоритм) для преобразованияслов алфавита A /> Q, т.е. конфигураций.Таким образом, для определения машины Тьюринга нужно задать ее внешний и внутреннийалфавиты, программу и указать, какие из символов обозначают пустую ячейку изаключительное состояние. 4. Доказательствонеразрешимости проблемы остановки
Проблемаостановки машины Тьюринга – это проблема построения такого алгоритма, который мог быопределить закончится или нет вычисление по некоторой задаче. Оказывается, чтов общем случае такой алгоритм нельзя построить в принципе, то есть невозможно найтиалгоритм, позволяющий по произвольной машине Тьюринга Т и произвольной ееначальной конфигурации qiaj определить придет лимашина Т в заключительное состояние q0, если начнет работу в этойконфигурации.
Если машинаТ, запущенная в начальной конфигурации qiaj, останавливается (т.е.попадает в заключительное состояние) через конечное число шагов, то онаназывается самоприменимой, в противном случае – несамоприменимой.
Теорема.
Не существуетмашины Тьюринга М, решающей проблему самоприменимости, то есть проблемасамоприменимости алгоритмически неразрешима.
Доказательство.
Предположимпротивное, то есть. пусть существует машина Тьюринга Т, решающая проблему самоприместимостив указанном выше смысле. Построим новую машину Т0, добавив новоесостояние q0* и объявив его заключительным, а также добавивновые команды для состояния q0, которое было заключительным вТ:
q0a1→a1Сq0(1)
q0a2→a2Сq0(2)
…q0an→an С q0* (n)
Рассмотримтеперь работу машины T0.
Пусть M – произвольная машина.Если M –самоприменима, то начальная конфигурация q1ai перейдет с помощьюкоманд машины Tчерез конечное число шагов в конфигурацию q0a1, далее применяетсякоманда (1), и машина T0никогда не остановится. Если M – несамоприменима, тоначальная конфигурация q1ai перейдет с помощью командмашины Tчерез конечное число шагов в конфигурацию q0an, далее применяетсякоманда (n),и машина T0остановится.
Такимобразом, машина T0применима к кодам несамоприменимых машин Т и неприменима к кодамсамоприменимых машин Т.
Теперьприменим машину T0к начальной конфигурации q1ai. Сама машина T0является либосамоприменимой, либо несамоприменимой. Если T0самоприменима, то подоказанному она никогда не остановится, начав с q1ai, и потому онанесамоприменима. Если T0несамоприменима, то по доказанному, онаостанавливается через конечное число шагов, начав с q1aj, и потому она самоприменима.Получили противоречие, следовательно проблема самоприменимости алгоритмическинеразрешима, что и требовалось доказать.
Проблемаостановки алгоритмически неразрешима, т. к. если бы она была разрешимой,то мы получили бы разрешимость проблемы самоприменимости. 5. Неразрешимостилогики первого порядка
Вматематической логике и теории алгоритмов под разрешимостью подразумеваютсвойство формальной теории обладать алгоритмом, определяющим по данной формуле,выводима она из множества аксиом данной теории или нет. Теория называетсяразрешимой, если такой алгоритм существует, и неразрешимой, в противном случае.Вывод неразрешимости логики первого порядка изнеразрешимости проблемы остановки
Вообще,говорят, что проблема распознавания какого-либо свойства разрешима, еслисуществует допускающий механическое вычисление тест (вычислимая, илиэффективная, процедура), который, будучи применен к произвольному объектусоответствующего типа, по прошествии некоторого времени правильноклассифицирует этот объект с точки зрения наличия или отсутствия у него некоторогосвойства. (Слова «по прошествии некоторого времени» означают здесь «посленекоторого конечного числа шагов».) Позитивным тестом называется эффективнаяпроцедура, устанавливающая по прошествии некоторого времени все случаи наличиясоответствующего свойства и только их. Негативный тест – это эффективнаяпроцедура, обнаруживающая все случаи отсутствия свойства и только их. Проблемараспознавания произвольного свойства разрешима тогда и только тогда, когда длянего существует и позитивный, и негативный тесты; дело в том, что всякий объектможет или обладать рассматриваемым свойством, или нет, и потому, обладая обоимитестами, можно применить их оба к интересующему объекту, выполняя поочередношаги одного и другого, и после некоторого их количества обнаружить, обладает онэтим свойством или нет. (Верно и обратное: всякий тест, устанавливающий черезнекоторое конечное число шагов, обладает данный объект рассматриваемымсвойством или нет, реализует и позитивный, и негативный тесты для этогосвойства) Нас будут интересовать сейчас свойства общезначимости и выполнимости,а в роли объектов «соответствующего типа» выступают формулы языка логикипервого порядка.
Докажем, чтодля этих тестов не существует дополнительных – позитивного для выполнимости инегативного для общезначимости – и потому в логике первого порядка проблемыраспознавания как общезначимости, так и выполнимости неразрешимы.
Докажемнеразрешимость логики первого порядка от противного: покажем, что если бысоответствующий тест существовал, то проблема остановки оказалась бы разрешимой.Мы убедились, что проблема остановки неразрешима.
Нашедоказательство от противного будет строиться так: мы покажем, как, располагая программоймашины Тьюринга, а также натуральным числом n, можно эффективнопостроить такие конечное множество предложений Д и еще одно предложение Н, что Д├ Н тогда и только тогда, когда рассматриваемая машина, будучи запущеннойв состоянии n(т.е. когда она начинает работу в состоянии q1, считывая при этом самуюлевую единицу в сплошном массиве из n единиц на ленте спустыми символами в остальных клетках), в конце концов останавливается. Такимобразом, мы определяем некоторую интерпретацию машины Тьюринга I. Формула Н винтерпретации I говорит, что машина в конце концов остановится, а формула измножества Д описывают работу машины. Введем функцию следования ' (где i' = i + 1 для всякого i).Таким образом, если бы мы могли решить проблему распознавания общезначимостипредложений, мы смогли бы эффективно решать, остановится в конце концов или нетданная машина Тьюринга, поскольку логическое следование Д ├ Н имеет местотогда и только тогда, когда общезначима импликация F1/>F2/>…/>Fk→H, где Fi/> Д (i = 1,2,… k).
Будемсчитать, что клетки ленты машины Тьюринга занумерованы так:… -3 -2 -1 1 2 3 …
Будем такжепредполагать, что время разбито на бесконечную последовательность моментов t, вкаждый из которых машина выполняет точно одну свою операцию, и что машинаначинает работу в момент времени 0, считывая при этом содержимое клетки 0. Моментывремени предполагаются неограниченно продолжаемыми как в будущее, так и в прошлое,равно как и лента бесконечно простирается и вправо, и влево. Мы считаем, чтомашина «включается» в момент 0 и «выключается» в первый момент (если таковой наступит),который следует за моментом ее остановки; мы считаем, далее, что во всеотрицательные моменты времени и во все моменты, следующие за моментом остановкимашины, она не находится ни в каком состоянии, не считывает никакую изимеющихся клеток и никакой символ (даже пустой) не встречается нигде на ееленте.
Каждомусостоянию qi, в котором может пребывать машина, ставится всоответствие некоторый двуместный предикатный символ Qi, подобным жеобразом каждому символу aj, который машина можетсчитывать либо записывать, ставится в соответствие двуместный предикатныйсимвол Aj. Помимо символов Qi и Aj в формулах из множества Д/> {Н} могут встречатьсятолько следующие символы: имя 0, одноместный функциональный символ ' идвуместный предикатный символ
Впредполагаемой интерпретации I предложений из множества Д /> {Н} предметной областью являются целыечисла. Имени 0 интерпретация I приписывает значение нуль, а функциональному символу ' – функциюследования. Символы Qi, Aj и
I объявляет Qiистинным на паре t, x в точности тогда, когда машина в момент времени tнаходится в состоянии qi, считывая при этомклетку с номером х.
I объявляет aj истинным на паре t, x вточности тогда, когда вмомент t в клетке с номером х находится символ aj;
I объявляет
Выяснимтеперь, какие функции содержатся в множестве Д. (Будем использовать переменнуюt в тех случаях, когда имеется в виду время, и переменные х и у, когда речьидет о клетках на ленте.) Пусть ai, …, an – список символов, считываемыхи записываемых машиной. Для каждой строки программы вида qiaj →apCqk мы включаем в множество Дформулу
(1) "x "y "t ((t Qix /> t Ajx)→ (t' Qkx /> t Apx /> (y ≠ x→ (t A0y → t'A0y /> … /> tAny → t'Any))))
(«Если вмомент времени t машина находится в состоянии qi, считываяпри этом символ aj в клетке х, то в момент t + 1 машина перейдет всостояние qk, считывая при этом клетку х, в которой появитсясимвол Ap, а во всех клетках, отличных от х, в момент t+ 1 останутся те же символы, что в момент t для всех t и х.»)
Также в множествоД для каждой строки программы вида qiaj →aj Пqk мы включаем формулу
(2) "x "y "t ((t Qix /> t Ajx)→ (t' Qkx'/> (t A0y → t'A0y) /> … /> (tAny → t'Any)))
(«Если вмомент времени t машина находится в состоянии qi, считываяпри этом символ aj в клетке х, то в момент t + 1 машина перейдет всостояние qk, считывая при этом клетку х + 1, и вовсех клетках в момент t + 1 останутся те же символы, что в момент tдля всех t и х.»)
Аналогичнодля строк вида qiaj →ajЛqkвключаем в Д
(3) "x "y "t ((t Qix'/> t Ajx')→ (t' Qkx /> (t A0y → t'A0y) /> … /> (tAny → t'Any)))
(«Если вмомент времени t машина находится в состоянии qi, считываяпри этом символ aj в клетке х + 1, то в момент t + 1 машинаперейдет в состояние qk, считывая при этом клетку х, и во всехклетках в момент t + 1 останутся те же символы, что в момент tдля всех t и х.»)
Одно изпредложений множества Д утверждает, что в начальный момент машина находится всостоянии q1, считывая при этом самую левую единицу в сплошном массиве единицна ленте с пустыми символами в остальных клетках:
(4) 0 Qi 0 /> 0 A1 0 /> 0 A1 0' /> … /> 0 A1 0(n-1)/> "y ((y ≠0 /> y ≠0' /> … /> y ≠ 0(n-1)) → 0 A0y)
Здесь 0(n-1) обозначает результатприменения nсимволов следования к символу 0.
Еще одна из формуламножества Д утверждает, что всякое целое число является следующим точно заодним целым:
(5) "z $xz = x' /> "z"x"y(z = x' /> z = y' → x = y)
Введем в Деще одну формулу
(6) "x"y"z(x y /> y z → x z) /> "x"y(x'= y→ xy) /> "x"y(x y → x ≠ y),
из которого следует, что если p и q – различные натуральныечисла, то "xx(p) ≠ x(q).
Такимобразом, Д состоит из формул (1), (2), (3), соответствующих всем командаммашины, и трема дополнительными (4), (5), (6). Что касается предложения Н, тозаметим, что всякая машина останавливается в момент времени t, если она в это времянаходится в состоянии qi, считывая при этомсимвол aj, причем в машинной таблице нет команды,соответствующей комбинации qiaj. Таким образом, запредложение Н мы принимаем дизъюнкцию всех предложений вида
$t $x (t Qix/> t Aix),
для которых вмашинной таблице нет команд, соответствующих комбинациям qiaj. Если же для всякойтакой комбинации в таблице имеются команды, то машина никогда не остановится, иза Н в этом случае мы принимаем какую-либо формулу, ложную в интерпретации I, например 0 ≠ 0.
Мы показали,как по данной машине и входному значению n построить такие конечноемножество предложений Д и отдельное предложение Н, что соотношение Д ├ Нимеет место тогда и только тогда, когда машина, получив n на входе, в концеконцов, останавливается.
Рассмотримфакты, касающиеся отношения ├ в логике первого порядка. Все предложенияиз множества Д истинны в интерпретации I. Поэтому если Д ├Н, то и Н истинно в I. Но Н истинно в I тогда и только тогда, когда машина, получив на входе n, в конце концовостанавливается.
Введем теперьодин специальный тип формул, называемых нами описаниями времени s. Такназывается всякая формула, определяющая очевидным способом, в каком состояниинаходится машина в момент s, какая клетка ею в это время считывается, а также вкаких клетках ленты какие символы записаны, причем все это делается на языкемножества формул Д /> {Н}. Точнее говоря, всякое описаниевремени s есть формула вида
(7) 0(s)Qi0(p)/> 0(s)/>/> … /> 0(s)Aj0(p)/> … /> 0(s)/>/> "y ((y /> /> /> … /> y /> 0(p)/> … /> y /> />) → 0(s)A0y)
Мы требуемпри этом, чтобы последовательность целых чисел p1,…, р,…, pv была возрастающей; рможет совпадать с р1 или с рv Заметим, что формула (4)является описанием времени 0.
Предположимтеперь, что машина, получив на входе число n, в конце концовостанавливается. Тогда для некоторых s, i, p и j машина в момент s окажется всостоянии qi, считывая при этом клетку с номером р, содержащую символ aj, причем в программемашинной нет команды для комбинации qiaj.
Предположим,далее, что из множества формул Д следует некоторое описание G времени s. Поскольку I – модель для Д, формула G должно быть истинным в I. Поэтому G должно содержать вкачестве конъюнктивных членов формулы 0(s)Qi0(p) и 0(s)Aj0(p) а потому из G должна следовать формула
$t $x (t Qi x /> t Ai x),
входящееодним из дизъюнктивных членов в H. Поэтому Н будет следовать из Д.
Остается лишьпоказать, что для всякого неотрицательного s, если только машинане останавливается до момента s, из Д следует некоторое описание времени s. Докажем это индукциейпо s.
Основаниеиндукции. Пусть s = 0. Множество Д содержит, а потому и влечет за собой предложение(4), являющееся описанием времени 0.
Шаг индукции.Предположим, что выделенное курсивом предложение верно (для s). Предположим, далее,что наша машина не остановилась до момента s + 1. Это значит, что онане остановилась ни до момента s, ни в самый момент s. Тогда из Д следует некоторое описание (8)времени s.Нужно доказать, что из Д следует и некоторое описание времени s+1.
Поскольку I – модель для Д, формула(8) истинна в I.Поэтому в момент s машина находится в состоянии qi, считывая при этомнекоторую клетку (с номером р), в которой записан символ aj. Поскольку машина вмомент sне остановилась, в ее программе должна присутствовать команда одного из видов
(a)qiaj → ak С qm
(б)qiaj → aj П qm
(в)qiaj → aj Л qm
Если имеетсякоманда типа (а), то одна из формул множества Д есть
"x "y "t ((t Qix /> t Aj x) → (t'Qkx/> t Apx /> (y ≠x → (t A0 y → t'A0 y /> … /> tAn y → t'An y))))
Она вместе с(5), (6) и (8) влечет за собой формулу
0 (s+1)Qi0 (p) /> 0 (s+1) Aj10 (p1) /> … /> 0 (s+1) Aj0 (p) /> … /> 0 (s+1) Ajv0 (pv) /> "y ((y ≠0 (p1) /> … /> y ≠ 0 (p) /> … /> y ≠ 0 (pv)) → 0 (s+1)A0y),
являющуюся описанием времени s + 1.
Еcли имеется команда типа(б), то одна из формул множества Д есть
"x "y "t ((t Qix /> t Ajx)→ (t' Qkx'/> (t A0y → t'A0y) /> … /> (tAny → t'Any)))
Из этогопредложения, объединенного с (5), (6) и (8), следует, что для некоторогосимвола />,
0(s+1)Qi0(p+1)/> 0(s+1)/>/> … /> 0(s+1)Aj0(p+1)/> … /> 0(s+1) /> /> "y ((y ≠/> /> … /> y ≠ 0(p+1)/> … /> y ≠ />) → 0(s+1)A0y),
а этопредложение является описанием времени s + 1.
Если имеетсястрелка типа (в), то одна из формул множества Д есть
"x "y "t ((t Qix'/> t Ajx')→ (t' Qkx /> (t A0y → t'A0y) /> … /> (tAny → t'Any)))
Тогдасуществует такой символ aq, что из последней формулы, объединенной с (5), (6), (8),следует
0(s+1)Qi0(p-1)/> 0(s+1)/>/> … /> 0(s+1)Aj 0(p-1)/> … /> 0(s+1)/>/> "y
((y /> /> y /> 0(p-1)/> …/> y/>) → 0(s+1)A0 y)
а этопредложение является описанием времени s + 1.
Во всех трехслучаях множество Д имеет следствием некоторое описание времени s + 1, и темсамым неразрешимость логики первого порядка доказана.Доказательствонеразрешимости логики первого порядка методом Геделя
Длядоказательства неразрешимости логики первого порядка достаточнопродемонстрировать, как по данной машине Т с входным значением n (то есть когда машинанаходится на самой левой единице в сплошной последовательности из n единиц при пустыхсимволах в остальных клетках ленты) построить такие предложение I и конечное множествопредложений Г, что машина Т при входном значении /> останавливается тогда итолько тогда, когда Г ├ I.
Не существуетэффективной процедуры, позволяющей решать, останавливается ли произвольнаямашина Тьюринга Т при произвольном входном значении n и по данной машинеТьюринга Т можно построить примитивно рекурсивную функцию g, обладающую следующимсвойством: какое бы n мы не взяли, g(n, t) = 0 в точности тогда,когда t – номер шага, более позднего, чем тот, на котором машина T останавливается, если еезапустить при входном значении n. (по определению функции g, если шаг t не таков, то g(x, t) = a, b, c> = /> для некоторых a, b, c и потому g(x, t) > 0. Если же t – такой шаг, то g(x, t) = 0.
Такимобразом, если дана машина Т, то можно эффективно построить некоторую конечнуюпоследовательность q0, q1, …, qr примитивно рекурсивных функций, удовлетворяющую двумусловиям: 1) каждая функция gi либо является базиснойфункцией, либо получается из некоторых предыдущих функций с помощью композицииили примитивной рекурсии и 2) для всякого n машина T, запущенная на входномзначении n, в конце концов останавливается тогда и только тогда, когда gr(n, t) = 0 для некоторого t.
Построимтеперь по данной T последовательность примитивно рекурсивных функций,удовлетворяющую условиям 1) и 2). Каждой функции gi поставим в соответствиесвой функциональный символ gi с тем же числомаргументов, что иgi. Пусть g0= '. Используя этисимволы, выпишем для каждого gi одну или две очевидныеформулы, определяющие функцию gi Например,
если gi= z, то "xgi(x) = 0
еслиgi = s, то "xgi(x) = x'
если gi = />, то "x1 … "xm … "xngi(x1, …,xm, …,xn) = xm
Если gi получается изпредшествующих ей функций gjи gk c помощью примитивнойрекурсии, то "xgi(x, 0) =gj(x) и "x"y gi(x, y') =gk(x, y, gi(x, y))
Если же gi получается изпредшествующих ей функций gо и /> путем композиции, то "xgi(x) =gj/>(для краткости заменили здесь x1, x2, …, xn на x, a "x1, "x2, …, "xn на "x)
Запишем такжеформулы "xx' ≠ 0 и "x"y(x' = y' → x = y). Обозначим теперь черезГ множество всех этих формул, а через I – формулу />.
Утверждение.Машина Tпри входном значении /> останавливается тогда и только тогда,когда Г ├ I.
«Тогда».Пусть Г ├ I. Обозначим через /> модель, областью которой служит множествонатуральных чисел и которая интерпретирует символ 0 как 0, а функциональныесимволы gi – как />. Все предложения из Г истинны в />. Поскольку Г ├ I, предложение I истинно также.Следовательно, для некоторого /> справедливо />. Согласно 2), T останавливается на />.
«Толькотогда». Предположим, что Т останавливается при входном значении />. Для доказательства соотношения Г ├I предположим, что /> – произвольная модель, в которой всепредложения из Г истинны, и покажем, что из этого предположения следуетистинность /> в />. Пусть теперь /> – интерпретация символа 0 в модели />, a /> – при всяком /> – интерпретация в /> символа gi. Пусть, далее, />(так что /> – интерпретация в /> символа />), и пусть />. Так как формулы /> и /> истинны в />, функция />, для которой /> и />, является изоморфизмом множества {0, 1,2,…} натуральных чисел на множество N. Таким образом, можно считать, что N иявляется в действительности множеством натуральных чисел, />, ограничение функции /> на множество N есть />, а потому всякий нумерал е обозначаетчисло /> в />.
Индукцией по />легко доказывается, что для всех />р в N справедливо /> (а потому /> N). Рассмотрим в деталях наиболее трудныйслучай, когда функция /> получается примитивной рекурсией изфункций /> и /> причем/>. Итак, пусть для всех /> из N выполняются равенства />.Нам нужно доказать, что /> для всех /> и />. Но так как формулы /> и /> содержатся в Г, справедливы равенства /> и />. Но тогда /> и если />, то, полагая />, получим />. Таким образом, индукцией по /> заключаем, что /> для всех /> и />.
Поскольку /> при входном значении /> останавливается, можно утверждать, чтодля некоторого /> справедливо />, откуда />, а потому /> истинно в />, а значит, и I = /> истинно в />, и доказательство заканчивается.
Заключение
Логикапервого порядка обладает рядом полезных свойств, которые делают ее оченьпривлекательной в качестве основного инструмента формализации математики.Главными из них являются полнота (это означает, что для любой формулы выводималибо она сама, либо ее отрицание) и непротиворечивость (ни одна формула неможет быть выведена одновременно со своим отрицанием).
Логикапервого порядка обладает свойством компактности: если некоторое множествоформул невыполнимо, то невыполнимо также некоторое его конечное подмножество.
Являясь формализованныманалогом обычной логики, логика первого порядка дает возможность строгорассуждать об истинности и ложности утверждений и об их взаимосвязи, вчастности, о логическом следовании одного утверждения из другого, или,например, об их эквивалентности.
В ходеисследования были рассмотрены основные понятия логики первого порядка и изученыдоказательства неразрешимости логики первого порядка. Для этого было разобранопонятие машины Тьюринга, доказана неразрешимость проблемы ее остановки. Наоснове полученного выведена неразрешимость логики первого порядка. Так жеразобрано доказательство неразрешимости логики первого порядка методом Геделя.
Список использованных источников
1. Булос Дж., ДжеффриР. Вычислимость и логика – Москва «Мир»: 1994.-394 с.
2. Зюзюков В.М., Шелупанов А.А. Математическаялогика и теория алгоритмов – М: 2007.-176 с.
3. Игошин В.И. Математическаялогика и теория алгоритмов – М: 2008. -435 с.
4. Мендельсон Э. Введение вматематическую логику – М: 1971.-320 с.
5. Молчанов В.А. Математическаялогика – Оренбург: ИПК ГОУ ОГУ, 2009. -88 с.
6. ru.wikipedia.org/wiki/Логика_первого_порядка
7. ru.wikipedia.org/wiki/Машина_Тьюринга
8. ru.wikipedia.org/wiki/Формальное_исчисление