Курсовая с практикой на тему Разрешимые и неразрешимые аксиоматические теории

Содержание:

ВВЕДЕНИЕ. 3

§ 1. Общее представление об
аксиоматических теориях. 5

§ 2. Проблема разрешимости
аксиоматических теорий. 13

§ 3. Практическая часть. 21

3.1 Разрешимые теории. 21

3.2 Неразрешимые теории. 22

ЗАКЛЮЧЕНИЕ. 30

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ.. 31

Введение:

Понятия алгоритма и
аксиоматической системы имеют давнюю историю. И то и другое известно ещё со
времён античности. Достаточно вспомнить постулаты геометрии Евклида и алгоритм нахождения наибольшего общего делителя того
же Евклида.

Несмотря на это, чёткого
математического определения исчисления и особенно алгоритма не существовало
очень долгое время. Особенность проблемы, связанной с формальным определением
неразрешимости состояла в том, что для того, чтобы показать, что некоторый
алгоритм существует, достаточно его просто найти и продемонстрировать. Если же
алгоритм не находится, возможно его не существует и это тогда требуется строго
доказать. А для этого нужно точно знать, что такое алгоритм[14, c. 52].

Большой прогресс в
формализации этих понятий был достигнут в начале XX века Гильбертом и его школой. Тогда, сначала,
сформировались понятия исчисления и формального вывода, а затем Гильбертом же,
в его знаменитой программе обоснования математики была
поставлена амбициозная цель формализации всей математики. Программа
предусматривала, в том числе, возможность автоматической проверки любой
математической формулы на предмет истинности. Тогда была поставлена проблема
разрешимости теорий, которая остается актуальной и по сей день[15, c. 108].

Целью данной курсовой
работы является рассмотрение разрешимых и неразрешимых аксиоматических теорий.

К задача данной курсовой
работы относятся:

— приведение общих
сведений об аксиоматических теориях;

— рассмотрение проблемы
разрешимости теорий;

— приведение примеров
разрешимых и неразрешимых аксиоматических теорий. Структура курсовой работы
состоит из введения, трех параграфов, заключения и списка используемой
литературы.

Во введение обоснована
актуальность рассматриваемой темы курсовой работы.

Сформулирована цель
курсовой работы и задачи, которые следует раскрыть при написании данной работы.

Первый параграф посвящен
определению и классификации аксиоматических теорий. В частности, в параграфе
дается определение аксиомы, теоремы и доказательства, как ключевых понятий при
рассмотрении аксиоматических теорий.

Также рассматривается
классификация аксиоматических теорий, которая условно делит их на две группы –
формальные и неформальные аксиоматические теории.

Второй параграф носит
аналитический характер. В нем рассматривается проблема разрешимости
аксиоматических теорий, как один их актуальных вопросов современной математики.

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

Третий параграф курсовой
работы имеет практическую направленность.

В нем приводятся примеры
разрешимых и неразрешимых

Заключение:

Аксиоматической теорией
называется  система, состоящая из двух
множеств высказываний (формул) R
и
L,
таких что  является подмножеством R.

К
основным свойствам аксиоматических теорий относят непротиворечивость и полноту.

Под
непротиворечивостью теории понимают отсутствие возможности вывода в данной
теории некоторой формулы или ее отрицания.

Под
полнотой теории понимают наличие возможности вывода для любой формулы или ее
отрицания.

Под алгоритмом в данной
курсовой работt
будем понимать некую программу, которая написала на некотором языке
программирования и выполняется на какой-то ЭВМ.

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

В
практической части были приведены примеры разрешимых и неразрешимых проблем в различных
аксиоматических теориях.

В
частности, можно отметить, что большое количество неразрешимых проблем
присутствует в теории машин Тьюринга, это связано с тем, что существует
множество способов задания алгоритмов работы машин Тьюринга.

Разрешимые
проблемы были рассмотрены на примеры теории формального языка, в частности, его
грамматик.

Таким
образом, цель курсовой работы достигнута, все задачи выполнены.

Фрагмент текста работы:

§ 1. Общее представление
об аксиоматических теориях История математики знает
два пути, по которым происходило становление известных аксиоматических теорий в
математике.

Первый
из этих путей заключается в том, что математическая теория, которая в определенный
момент времени, достигает достаточно высокого уровня, превращается в
аксиоматическую теорию, принимает ее характер.

На
основании данного подхода к аксиоматическим теориями стали относится следующие
теории:

—
арифметика Ж.Пиано;

—
Гильбертова геометрия, а также геометрии Г. Вейля, М. Пиери и т.д.;

—
теория вероятностей (А.Н. Колмогоров) и др.

Второй
путь становление математической теории как аксиоматической, заключался в том,
что среди нескольких математических теорий обнаруживались общие черты, что
приводило исследователей к мысли о создании аксиоматических теории, в основе
которых могли бы быть положены эти самые «общие» черты.

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

К
таким теориям относятся:

—
теория групп;

—
теория колец;

—
теория полей и других алгебраических систем;

—
общая (универсальная) алгебра и т.д.

Второй
подход предоставляет широчайшие возможности к метапредметным взаимодействиям
между математическими науками. Помимо этого, данный подход позволяет приводить
более общую интерпретацию основополагающих понятий, что отрывает еще более
широкие перспективы для развития и становления математики как науки.