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

Индукцией по легко доказывается, что для всех р в N справедливо (а потому N). Рассмотрим в деталях наиболее трудный случай, когда функция width=17 height=22 src="images/referats/658/image028.gif">получается примитивной рекурсией из функций и причем. Итак, пусть для всех из 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/Формальное_исчисление

Размещено на Allbest.ru

 Скачать реферат