Дедуктивная теория.html
 
| ca | de | en | es | fr | it | nl | no | pl | pt | ru | ro | fi | sv | tr | vo |


 

 Эту статью следует викифицировать.
Пожалуйста, оформите её согласно правилам оформления статей.

Содержание

править Определение и разновидности

Дедуктивная теория считается заданной, если:

  1. Задан алфавит и правила образования выражений (слов) в этом алфавите.
  2. Заданы правила образования формул (правильно построенных, корректных выражений).
  3. Из множества формул некоторым способом выделено подмножество T теорем (доказуемых формул).

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

  • В множестве формул выделяется подмножество аксиом, и задается конечное число правил вывода — таких правил, с помощью которых (и только с помощью их) из аксиом и ранее выведенных теорем можно образовать теоремы. Аксиомы иногда называют «скрытыми определениями».

Таким способом задается формальная теория (формальная аксиоматическая теория, формальное (логическое) исчисление).

  • Задаются только аксиомы, правила вывода считаются общеизвестными.

При таком задании теорем говорят, что задана полуформальная аксиоматическая теория.

  • Аксиом нет (множество аксиом пусто), задаются только правила вывода.

По сути, заданная таким образом теория — частный случай формальной, но имеет собственное название: теория естественного вывода.

править Свойства дедуктивных теорий

править Противоречивость

Теория, в которой множество теорем покрывает всё множество формул (все формулы являются теоремами, «истинными высказываниями»), называется противоречивой. В противном случае теория называется непротиворечивой. Выяснение противоречивости теории — одна из важнейших и иногда сложнейших задач формальной логики. После выяснения противоречивости теория, как правило, не имеет дальнейшего ни теоретического, ни практического применения.

править Полнота

Теория называется полной, если в ней для любой формулы F выводима либо сама F, либо ее отрицание \neg F. В противном случае, теория содержит недоказуемые утверждения (утверждения, которые нельзя ни доказать, ни опровергнуть средствами самой теории), и называется неполной.

править Независимость аксиом

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

править Разрешимость

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

править Примеры

править Важнейшие выводы

  • В 30-е гг. XX века Курт Гёдель показал, что есть целый класс теорий первого порядка, являющихся неполными. Более того, формула, утверждающая непротиворечивость теории, также невыводима средствами самой теории (см. Теоремы Гёделя о неполноте). Этот вывод имел огромное значение для математики, так как формальная арифметика (а на ней базируется теория действительных чисел, без которой нельзя представить современную математику) является как раз такой теорией первого порядка, а следовательно, формальная арифметика и все теории, содержащие ее, в том числе теория действительных чисел, являются неполными.
  • Проблема неразрешимости логики предикатов. Чёрчем доказано, что не существует алгоритма, который для любой формулы логики предикатов устанавливает, логически общезначима формула или нет.
  • Исчисление высказываний является непротиворечивой, полной, разрешимой теорией, причем все три утверждения доказуемы в рамках самой логики высказываний.

править Литература

  • Галиев Ш. И. Математическая логика и теория алгоритмов. — Казань: Издательство КГТУ им. А. Н. Туполева. 2002.

править Примечания

править См. также


Логика Это незавершённая статья по логике. Вы можете помочь проекту, исправив и дополнив её.
All Right Reserved © 2007, Designed by Stylish Blog.