Неразрешимость логики первого порядка - Математика курсовая работа

Главная

Математика
Неразрешимость логики первого порядка

Понятие формальной системы. Основные понятия логики первого порядка. Доказательство неразрешимости проблемы остановки. Машина Тьюринга, ее структура. Вывод неразрешимости логики первого порядка из неразрешимости проблемы остановки и методом Геделя.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.


"Неразрешимость логики первого порядка"
формальный неразрешимость логика остановка
Философы сформулировали наиболее важные идеи искусственного интеллекта, но для преобразования его в формальную науку потребовалось достичь определенного уровня математической формализации в трех фундаментальных областях: логика, вычисления и вероятность.
Истоки идей формальной логики можно найти в работах философов древней Греции, но ее становление как математической дисциплины фактически началась с трудов Джорджа Буля (1815-1864), который детально разработал логику высказываний, или булеву логику. В 1879 году Готтлоб Фреге (1848-1925) расширил булеву логику для включения в нее объектов и отношений, создав логику первого порядка, которая в настоящее время используется как наиболее фундаментальная система представления знаний.
Одним из принципиально важных результатов математической логики является доказательство неразрешимости в логике первого порядка распознавания проблем как общезначимости, так и выполнимости ее предложений.
Цель исследования - изучить доказательства неразрешимости логики первого порядка. Для достижения данной цели необходимо выделить ряд задач:
1. Изучить основные понятия логики первого порядка.
2. Рассмотреть понятие машины Тьюринга и доказать неразрешимость проблемы остановки.
3. Вывести неразрешимость логики первого порядка из неразрешимости проблемы остановки.
4. Разобрать доказательство неразрешимости логики первого порядка методом Геделя.
Формальная система (или формальная теория) - результат строгой формализации теории, предполагающей полную абстракцию от смысла слов используемого языка, причем все условия, регулирующие употребление этих слов в теории, явно высказаны посредством аксиом и правил, позволяющих вывести одну фразу из других.
Формальная теория считается определенной , если:
- задано конечное или счётное множество произвольных символов (конечные последовательности символов называются выражениями теории);
- имеется подмножество выражений, называемых формулами;
- выделено подмножество формул, называемых аксиомами;
- имеется конечное множество отношений между формулами, называемых правилами вывода.
Обычно имеется эффективная процедура, позволяющая по данному выражению определить, является ли оно формулой. Часто множество формул задаётся индуктивным определением. Как правило, это множество бесконечно. Множество символов и множество формул в совокупности определяют язык или сигнатуру формальной теории.
Чаще всего имеется возможность эффективно выяснять, является ли данная формула аксиомой; в таком случае теория называется эффективно аксиоматизированной или аксиоматической. Множество аксиом может быть конечным или бесконечным. Если множество аксиом бесконечно, то, как правило, оно задаётся с помощью конечного числа схем аксиом и правил порождения конкретных аксиом из схемы аксиом. Обычно аксиомы делятся на два вида: логические аксиомы (общие для целого класса формальных теорий) и нелогические или собственные аксиомы (определяющие специфику и содержание конкретной теории).
Для каждого правила вывода R и для каждой формулы A эффективно решается вопрос о том, находится ли выбранный набор формул в отношенни R с формулой A, и если да, то A называется непосредственным следствием данных формул по правилу R.
Выводом называется всякая последовательность формул такая, что всякая формула последовательности есть либо аксиома, либо непосредственное следствие каких-либо предыдущих формул по одному из правил вывода.
Формула называется теоремой , если существует вывод, в котором эта формула является последней.
Теория, для которой существует эффективный алгоритм, позволяющий узнавать по данной формуле, существует ли ее вывод, называется разрешимой ; в противном случае теория называется неразрешимой.
Теория, в которой не все формулы являются теоремами, называется абсолютно непротиворечивой .
Дедуктивная теория считается заданной , если:
- задан алфавит (множество) и правила образования выражений (слов) в этом алфавите;
- заданы правила образования формул (правильно построенных, корректных выражений);
- из множества формул некоторым способом выделено подмножество T теорем (доказуемых формул).
1. Противоречивость . Теория, в которой множество теорем покрывает всё множество формул (все формулы являются теоремами, «истинными высказываниями»), называется противоречивой. В противном случае теория называется непротиворечивой. Выяснение противоречивости теории - одна из важнейших и иногда сложнейших задач формальной логики. После выяснения противоречивости теория, как правило, не имеет дальнейшего ни теоретического, ни практического применения.
2. Полнота . Теория называется полной, если в ней для любой формулы F выводима либо сама F, либо ее отрицание. В противном случае, теория содержит недоказуемые утверждения (утверждения, которые нельзя ни доказать, ни опровергнуть средствами самой теории), и называется неполной.
3. Независимость аксиом . Отдельная аксиома теории считается независимой, если эту аксиому нельзя вывести из остальных аксиом. Зависимая аксиома по сути избыточна, и ее удаление из системы аксиом никак не отразится на теории. Вся система аксиом теории называется независимой, если каждая аксиома в ней независима.
4. Разрешимость . Теория называется разрешимой, если в ней понятие теоремы эффективно, то есть существует эффективный процесс (алгоритм), позволяющий для любой формулы за конечное число шагов определить, является она теоремой или нет.
1) внешний алфавит A={ a 0 , a 1 , … , a n };
2) внутренний алфавит Q={ q 1 , q 2 ,…, q m } - множество состояний;
3) множество управляющих символов {П, Л, С}
4) бесконечная в обе стороны лента, разделённая на ячейки, в каждую из которых в любой дискретный момент времени может быть записан только один символ из алфавита А;
5) управляющее устройство, способное находиться в одном из множества состояний
Символом пустой ячейки является буква внешнего алфавита а 0 .
Среди состояний выделяются два - начальное q 1 , находясь в котором машина начинает работать, и заключительное (или состояние остановки) q 0 , попав в которое машина останавливается.
Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы алфавита A. Управляющее устройство работает согласно командам, которые имеют следующий вид
Запись означает следующее: если управляющее устройство находится в состоянии q i , а в обозреваемой ячейке записана буква a j , то (1) в ячейку вместо a j записывается a p , (2) машина переходит к обозрению следующей правой ячейки от той, которая обозревалась только что, если Х= П, или к обозрению следующей левой ячейки, если Х= Л, или же продолжает обозревать ту же ячейку ленты, если Х= С, (3) управляющее устройство переходит в состояние q k .
Поскольку работа машины, по условию, полностью определяется ее состоянием q , в данный момент и содержимым а обозреваемой в этот момент ячейки, то для каждой возможной конфигурации q i a j имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Поэтому программа машины Тьюринга с внешним алфавитом A={ a 0 , a 1 , … , a n} и внутренним Q={ q 1, q 2,…, q m} содержит не более m (n+ 1) команд.
Словом в алфавите А или в алфавите Q, или в алфавите A Q называется любая последовательность букв соответствующего алфавита. Под k-ой конфигурацией будем понимать изображение ленты машины с информацией, сложившейся на ней к началу k-того шага (или слово в алфавите А, записанное на ленту к началу k-того шага), с указанием того, какая ячейка обозревается в этот шаг и в каком состоянии находится машина. Имеют смысл лишь конечные конфигурации, т.е. такие, в которых все ячейки ленты, за исключением, быть может, конечного числа, пусты. Конфигурация называется заключительной , если состояние, в котором при этом находится машина, заключительное.
Если выбрать какую-либо незаключительную конфигурацию машины Тьюринга в качестве исходной, то работа машины будет состоять в том, чтобы последовательно (шаг за шагом) преобразовывать исходную конфигурацию в соответствии с программой машины до тех пор, пока не будет достигнута заключительная конфигурация. После этого работа машины Тьюринга считается закончившейся, а результатом работы считается достигнутая заключительная конфигурация.
Будем говорить, что непустое слово б в алфавите А\ { а 0 } = { a 1 , … , a n } воспринимается машиной в стандартном положении, если оно записано в последовательных ячейках ленты, все другие ячейки пусты, и машина обозревает крайнюю слева или крайнюю справа ячейку из тех, в которых записано слово б. Стандартное положение называется начальным (заключительным), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии q 1 (соответственно в состоянии остановки q 0 ).
Если обработка слова б переводит машину Тьюринга в заключительное состояние, то говорят, что она применима к б , в противном случае - не применима к б (машина работает бесконечно)
Дана машина Тьюринга с внешним алфавитом А = {0, 1} (здесь 0 - символ пустой ячейки), алфавитом внутренних состояний Q = { q 0 , q 1 , q 2 } и со следующей функциональной схемой (программой):
Данную программу можно записать с помощью таблицы
Посмотрим, в какое слово переработает эта машина слово 110, исходя из начального положения:
На первом шаге действует команда: q 1 0 > 1 Л q 2 (управляющее устройство находится в состоянии q 1, а в обозреваемой ячейке записана буква 0, в ячейку вместо 0 записывается 1, головка сдвигается влево, управляющее устройство переходит в состояние q 2), в результате на машине создается следующая конфигурация:
На втором шаге действует команда: q 2 1 > 1С q 1 и на машине создается конфигурация:
Третий шаг обусловлен командой: q 1 1 > 0 С q 2 . В результате нее создается конфигурация:
Наконец, после выполнения команды q 2 0 > 0 П q 0 создается конфигурация
Эта конфигурация является заключительной, потому что машина оказалась в состоянии остановки q 0 .
Таким образом, исходное слово 110 переработано машиной в слово 101.
Полученную последовательность конфигураций можно записать более коротким способом (содержимое обозреваемой ячейки записано справа от состояния, в котором находится в данный момент машина):
11 q 1 0 => 1 q 2 11 => 1 q 1 11 => 1 q 2 01 => 10 q 0 1
Машина Тьюринга - не что иное, как некоторое правило (алгоритм) для преобразования слов алфавита A Q, т.е. конфигураций. Таким образом, для определения машины Тьюринга нужно задать ее внешний и внутренний алфавиты, программу и указать, какие из символов обозначают пустую ячейку и заключительное состояние.
(1) x y t (( t Q i x t A j x ) > ( t ' Q k x t A p x ( y ? x > ( t A 0 y > t ' A 0 y … t A n y > t ' A n y ) )))
(«Если в момент времени t машина находится в состоянии q i , считывая при этом символ a j в клетке х , то в момент t + 1 машина перейдет в состояние q k , считывая при этом клетку х , в которой появится символ A p , а во всех клетках, отличных от х , в момент t + 1 останутся те же символы, что в момент t для всех t и х . »)
Также в множество Д для каждой строки программы вида q i a j > a j П q k мы включаем формулу
(2) x y t (( t Q i x t A j x ) > ( t ' Q k x ' ( t A 0 y > t ' A 0 y ) … ( t A n y > t ' A n y )))
(«Если в момент времени t машина находится в состоянии q i , считывая при этом символ a j в клетке х , то в момент t + 1 машина перейдет в состояние q k , считывая при этом клетку х + 1, и во всех клетках в момент t + 1 останутся те же символы, что в момент t для всех t и х. »)
Аналогично для строк вида q i a j > a j Л q k включаем в Д
(3) x y t (( t Q i x ' t A j x ') > ( t ' Q k x ( t A 0 y > t ' A 0 y ) … ( t A n y > t ' A n y )))
(«Если в момент времени t машина находится в состоянии q i , считывая при этом символ a j в клетке х + 1, то в момент t + 1 машина перейдет в состояние q k , считывая при этом клетку х , и во всех клетках в момент t + 1 останутся те же символы, что в момент t для всех t и х. »)
Одно из предложений множества Д утверждает, что в начальный момент машина находится в состоянии q 1 , считывая при этом самую левую единицу в сплошном массиве единиц на ленте с пустыми символами в остальных клетках:
(4) 0 Q i 0 0 A 1 0 0 A 1 0' … 0 A 1 0 (n-1) y (( y ? 0 y ? 0' … y ? 0 ( n -1) ) > 0 A 0 y )
Здесь 0 ( n -1) обозначает результат применения n символов следования к символу 0.
Еще одна из формула множества Д утверждает, что всякое целое число является следующим точно за одним целым:
(5) z x z = x ' z x y ( z = x ' z = y ' > x = y )
(6) x y z ( x < y y < z > x < z ) x y ( x ' = y > x < y ) x y ( x < y > x ? y ),
из которого следует, что если p и q - различные натуральные числа, то x x ( p ) ? x ( q ) .
Таким образом, Д состоит из формул (1), (2), (3), соответствующих всем командам машины, и трема дополнительными (4), (5), (6). Что касается предложения Н, то заметим, что всякая машина останавливается в момент времени t, если она в это время находится в состоянии q i , считывая при этом символ a j , причем в машинной таблице нет команды, соответствующей комбинации q i a j . Таким образом, за предложение Н мы принимаем дизъюнкцию всех предложений вида
для которых в машинной таблице нет команд, соответствующих комбинациям q i a j . Если же для всякой такой комбинации в таблице имеются команды, то машина никогда не остановится, и за Н в этом случае мы принимаем какую-либо формулу, ложную в интерпретации I, например 0 ? 0.
Мы показали, как по данной машине и входному значению n построить такие конечное множество предложений Д и отдельное предложение Н, что соотношение Д + Н имеет место тогда и только тогда, когда машина, получив n на входе, в конце концов, останавливается.
Рассмотрим факты, касающиеся отношения + в логике первого порядка. Все предложения из множества Д истинны в интерпретации I. Поэтому если Д + Н, то и Н истинно в I. Но Н истинно в I тогда и только тогда, когда машина, получив на входе n , в конце концов останавливается.
Введем теперь один специальный тип формул, называемых нами описаниями времени s. Так называется всякая формула, определяющая очевидным способом, в каком состоянии находится машина в момент s, какая клетка ею в это время считывается, а также в каких клетках ленты какие символы записаны, причем все это делается на языке множества формул Д {Н}. Точнее говоря, всякое описание времени s есть формула вида
(7) 0 (s) Q i 0 (p) 0 (s) … 0 (s) A j 0 (p) … 0 (s) y (( y … y 0 (p) … y ) > 0 (s) A 0 y )
Мы требуем при этом, чтобы последовательность целых чисел p 1 ,…, р,…, p v была возрастающей; р может совпадать с р 1 или с р v Заметим, что формула (4) является описанием времени 0.
Предположим теперь, что машина, получив на входе число n , в конце концов останавливается. Тогда для некоторых s, i, p и j машина в момент s окажется в состоянии q i , считывая при этом клетку с номером р, содержащую символ aj, причем в программе машинной нет команды для комбинации q i a j .
Предположим, далее, что из множества формул Д следует некоторое описание G времени s. Поскольку I - модель для Д, формула G должно быть истинным в I. Поэтому G должно содержать в качестве конъюнктивных членов формулы 0 ( s ) Qi0 ( p ) и 0 ( s ) Aj0 ( p ) а потому из G должна следовать формула
входящее одним из дизъюнктивных членов в 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 не остановилась, в ее программе должна присутствовать команда одного из видов
Если имеется команда типа (а), то одна из формул множества Д есть
x y t (( t Qi x t Aj x ) > ( t ' Qk x t Ap x ( y ? x > ( t A0 y > t ' A0 y … t An 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) A0 y ),
являющуюся описанием времени s + 1.
Еcли имеется команда типа (б), то одна из формул множества Д есть
x y t (( t Q i x t A j x ) > ( t ' Q k x ' ( t A 0 y > t ' A 0 y ) … ( t A n y > t ' A n y )))
Из этого предложения, объединенного с (5), (6) и (8), следует, что для некоторого символа ,
0 (s+1) Q i 0 (p+1) 0 (s+1) … 0 (s+1) A j 0 (p+1) … 0 (s+1) y (( y ? … y ? 0 ( p +1) … y ? ) > 0 ( s +1) A 0 y ),
а это предложение является описанием времени s + 1.
Если имеется стрелка типа (в), то одна из формул множества Д есть
x y t (( t Q i x ' t A j x ') > ( t ' Q k x ( t A 0 y > t ' A 0 y ) … ( t A n y > t ' A n y )))
Тогда существует такой символ a q, что из последней формулы, объединенной с (5), (6), (8), следует
0 (s+1) Q i 0 (p-1) 0 (s+1) … 0 (s+1) A j 0 (p-1) … 0 (s+1) y
(( y y 0 ( p -1) … y ) > 0 ( s +1) A 0 y )
а это предложение является описанием времени s + 1.
Во всех трех случаях множество Д имеет следствием некоторое описание времени s + 1, и тем самым неразрешимость логики первого порядка доказана.
Этапы развития логики. Имена ученых, внесших существенный вклад в развитие логики. Ключевые понятия монадической логики второго порядка. Язык логики предикатов. Автоматы Бучи: подход с точки зрения автоматов и полугрупп. Автоматы и бесконечные слова. курсовая работа [207,1 K], добавлен 26.03.2012
Основы формальной логики Аристотеля. Понятия инверсии, конъюнкции и дизъюнкции. Основные законы алгебры логики. Основные законы, позволяющие производить тождественные преобразования логических выражений. Равносильные преобразования логических формул. презентация [67,8 K], добавлен 23.12.2012
Практическое решение дифференциальных уравнений в системе MathCAD методами Рунге—Кутты четвертого порядка для решения уравнения первого порядка, Булирша — Штера - системы обыкновенных дифференциальных уравнений первого порядка и Odesolve и их графики. лабораторная работа [380,9 K], добавлен 23.07.2012
Дифференциальное уравнение первого порядка, разрешенное относительно производной. Применение рекуррентного соотношения. Техника применения метода Эйлера для численного решения уравнения первого порядка. Численные методы, пригодные для решения задачи Коши. реферат [183,1 K], добавлен 24.08.2015
Особенности выражения производной неизвестной функции. Общий вид дифференциального уравнения первого порядка, его решение. Сущность теоремы Коши (о существовании и единственности решения), её геометрический смысл. Общее и частное решение уравнения. презентация [77,7 K], добавлен 17.09.2013
Понятие и математическое описание элементов дифференциального уравнения как уравнения, связывающего искомую функцию одной или нескольких переменных. Состав неполного и линейного дифференциального уравнения первого порядка, их применение в экономике. реферат [286,2 K], добавлен 06.08.2013
В работе рассматриваются доказательства неразрешимости в рациональных ненулевых числах двух систем, которые легко касаются не только чисел, но и распространяются на рациональные функции, что, в конечном счёте, позволяет анализировать решение уравнения. творческая работа [123,8 K], добавлен 04.09.2010
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Неразрешимость логики первого порядка курсовая работа. Математика.
Реферат: Решения к Сборнику заданий по высшей математике Кузнецова Л.А. - 2. Дифференцирование. Зад.19
Реферат На Тему Олимпийские Чемпионы
Искусство И Религия Эссе
Дипломная работа по теме Уголовная ответсвенность за незаконное предпринимательство
Курсовая работа по теме Анализ комплексного грузопотока на направлении перевозок
Контрольная Работа Функции Их Свойства И Графики
Реферат: Одежда и украшения при Петре Первом. Скачать бесплатно и без регистрации
Сложное Сочинение Описание Комнаты
Контрольная работа по теме Роль интеллектуальной собственности в реформируемой экономике РФ
Реферат: История еврейства западной и восточной Европы в новое время
Реферат: Возникновение текстильной техники в первобытном общинном строе
Ответ на вопрос по теме Ландшафтоведение как наука. Свойства и характеристики природных компонентов ландшафта
Реферат: Педагогічні умови стимулювання активності студентів вищих педагогічних навчальних закладів до фізкультурної діяльності
Практическое задание по теме Учения Конфуция о государстве
Реферат На Тему Южная Америка
Реферат по теме Врождённые наследственные заболевания почек
Реферат На Тему Исторический Портрет Николая 1
Экологически Чистый Продукт Эссе
Теория Когнитивного Развития Ж Пиаже Реферат
Скачать Рефераты Асептика И Антисептика
Анализ эффективности применения соляно-кислотных обработок, проводимых в нефтегазодобывающем управлении "Ишимбайнефть" - Геология, гидрология и геодезия курсовая работа
Біорізноманіття. Причини та наслідки деградації біорізноманіття - Биология и естествознание презентация
Сравнительная характеристика методов определения показателей качества - Маркетинг, реклама и торговля реферат