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

Вообще, говорят, что проблема распознавания какого-либо свойства разрешима, если существует допускающий механическое вычисление тест (вычислимая, или эффективная, процедура), который, будучи

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

Курсовой проект

Математика и статистика

Другие курсовые по предмету

Математика и статистика

Сдать работу со 100% гаранией
ется, если ее запустить при входном значении 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, то x gi(x) = 0

если gi = s, то x gi(x) = x'

если gi = , то x1 … xm … xn gi(x1, …, xm, …, xn) = xm

Если gi получается из предшествующих ей функций gj и gk c помощью примитивной рекурсии, то x gi(x, 0) =gj(x) и x y gi(x, y') =gk(x, y, gi(x, y))

Если же gi получается из предшествующих ей функций gо и путем композиции, то x gi(x) =gj (для краткости заменили здесь x1, x2, …, xn на x, a x1, x2, …, xn на x)

Запишем также формулы x x ' ≠ 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. http://ru.wikipedia.org/wiki/Логика_первого_порядка
  7. http://ru.wikipedia.org/wiki/Машина_Тьюринга
  8. http://ru.wikipedia.org/wiki/Формальное_исчисление

 

Похожие работы

<< < 1 2 3 4 5