Рекурсивные функции
Сущность и значение кодирования программ. Характеристика и отличительные черты теоремы о параметризации, описание и специфика универсальных функций. Применение теоремы Клини о нормальной форме. Синтаксис и семантика, теорема Райса и математическая логика.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 30.12.2015 |
| Размер файла | 47,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Иногда (как в предыдущем случае с конечно определенными группами) удобно строить модель в терминах равенства, отождествляя некоторые выражения как “имеющее одно и то же значение”.
Теория непротиворечива, если в ней доказуемы только истинные высказывания и полна, если все истинные высказывания доказуемы.
Таким образом, для любой “нормальной” встречающейся на практике формальной теории множество L перечислимо и, на деле, даже разрешимо ( в программировании алгоритм проверки синтаксической корректности, как мы знаем, реализуются в программах синтаксического анализа), а множество T перечислимо - для любой такой теории несложно построить генератор теорем, перебирающий всевозможные конечные цепочки доказательств.
Суть принципа неполноты Геделя заключается в том, что, если некоторая непротиворечивая формальная теория “не слабее арифметики” - т.е. достаточно гибка, чтобы сформулировать в ней (быть может, с использованием некоторого эффективного кодирования) некоторое определение вычислимости, - то можно воспроизвести в ней диагональные рассуждения, подобные сделанные нами выше и показать, что множество недоказуемых формул L\T продуктивно. Следовательно, множество T всех теорем креативно и, следовательно, неразрешимо.
Далее, пусть F - множество формул, отрицание которых доказуемо в нашей теории. F перечислимо (поскольку перечислимо T) и F L\T. В силу продуктивности L\T можно эффективно предъявить пример формулы f, f L\(T F). Либо f, либо ее отрицание обязано быть истинным (при любом понимании того, что такое истинная формула!), но ни одно из них недоказуемо в нашей теории. Следовательно, наша теория либо противоречива, либо неполна.
Таким образом, для сколь-нибудь сложной математической теории (не говоря уже о математике в целом) мы не только не можем надеется на существование универсального алгоритма, определяющего за нас истинность (или доказуемость) утверждений этой теории. Более того, при любой попытке расширить понятие доказуемости (например, добавлением в теорию все новых аксиом) мы можем получить явный пример того, почему этого такое расширение было недостаточно. Теперь становиться понятным, почему Э.Пост выбрал для креативных множеств столь интригующее название - такие результаты подчеркивают существенно творческий, т.е. неформальный характер математического знания.
Размещено на Allbest.ru
Подобные документы
История создания теоремы. Краткая биографическая справка из жизни Пифагора Самосского. Основные формулировки теоремы. Доказательство Евклида, Хоукинса. Доказательство через: подобные треугольники, равнодополняемость. Практическое применение теоремы.
презентация [3,6 M], добавлен 21.10.2011Основные понятия алгебры логики. Дизъюнктивные и конъюнктивные нормальные формы. Сущность теоремы Шеннона. Булевы функции двух переменных. Последовательное и параллельное соединение двух выключателей. Свойства элементарных функций алгебры логики.
контрольная работа [345,3 K], добавлен 29.11.2010Теорема о представлении дзета-функции Дедекинда произведением L-рядов Дирихле, ее доказательство в виде произведения L-функций в разветвленном и неразветвленном случаях. Приложение теоремы: выведение функционального уравнения дзета-функции Дедекинда.
курсовая работа [65,6 K], добавлен 15.06.2011Доказательство первой, второй и третей теоремы Силова. Описание групп порядка pq. Смежные классы по подгруппе и теорема Лагранжа. Классы сопряженных элементов. Нормализатор множества в группе. Теоремы о гомоморфизмах. Примеры силовских подгрупп.
курсовая работа [246,9 K], добавлен 21.04.2011Краткий биографический очерк жизненного пути Пифагора. История появления теоремы Пифагора, ее дальнейшее распространение в мире. Формулировка и доказательство теоремы с помощью различных методов. Возможности применения теоремы Пифагора к вычислениям.
презентация [309,4 K], добавлен 17.11.2011Теорема Ролля и ее доказательство, структура и геометрический смысл. Сущность теоремы о среднем, принадлежащей Лагранжу, использование в ней результатов теоремы Ролля. Отражение и обобщение работы Лагранжа в теореме Коши, методика ее доказательства.
реферат [208,2 K], добавлен 15.08.2009Биография Менелая Александрийского - древнегреческого астронома и математика. Формулировка и доказательство теоремы Менелая для плоского случая, при переносе центральным проектированием на сферу. Применение теоремы для решения прикладных задач.
презентация [1,8 M], добавлен 17.11.2013Путь Пифагора к знаниям, источники его учения и научная деятельность. Формулировка теоремы Пифагора, ее простейшее доказательство на примере равнобедренного прямоугольного треугольника. Применение изучаемой теоремы для решения геометрических задач.
презентация [174,3 K], добавлен 18.12.2012Общая характеристика сходимости последовательностей случайных величин и вероятностных распределений. Значение метода характеристических функций в теории вероятностей. Методика решения задач о типах сходимости. Анализ теоремы Ляпунова и Линдеберга.
курсовая работа [2,6 M], добавлен 22.07.2011Доказательство теоремы Ферма методами теоремы арифметики, элементарной алгебры с использованием методов решения параметрических уравнений для четных и нечетных показателей степени. Теорема о разложении на простые множители целых составных чисел.
научная работа [22,6 K], добавлен 12.06.2009
