Формално смятане Wikipedia

Формалната система(формална теория,аксиоматична теория,аксиоматика,дедуктивна система) е резултат от строга формализация на теорията, която предполага пълна абстракция от значението на думите на използвания език и всички условия, управляващи използването на тези думи в теорията, са изрично посочени с помощта на аксиоми и правила, които позволяват извличането на една фраза y от други [1] .

Формалната система е колекция от абстрактни обекти, които не са свързани с външния свят, в които правилата за работа с набор от символи са представени в строго синтактична интерпретация, без да се взема предвид семантичното съдържание, тоест семантиката. След поставянето на проблема Хилберт се появяват строго описани формални системи. Първата FS се появи след публикуването на книгите на Ръсел и Уайтхед „Формални системи“ [пояснете] . Тези FS бяха представени с определени изисквания.

Съдържание

Ключови точки

Формалната теория се счита за дефинирана, ако [2] :

  1. Даден е краен или изброим набор от произволни символи. Крайните последователности от знаци се наричат ​​изразина теорията.
  2. Има подгрупа от изрази, наречениформули.
  3. Отделено е подмножество от формули, наречениаксиоми.
  4. Има краен набор от връзки между формулите, наречениправила за извод.

Обикновено има ефективна процедура, която позволява на даден израз да определи дали е формула. Често набор от формули се дава чрез индуктивна дефиниция. По правило това множество е безкрайно. Наборът от символи и наборът от формули заедно определятезикаилиподписана формална теория.

За всяко правило за извод R иза всяка формулаAвъпросът дали избраният набор от формули е във връзка с R с формулатаAе ефективно решен и ако е така, тогаваAсе наричанепосредствено следствиеот тези формули съгласно правилото R.

Извежданее всяка последователност от формули, така че всяка формула от последователността е или аксиома, или пряко следствие от предишни формули съгласно някое от правилата за извод.

Формула се наричатеорема, ако има извод, в който тази формула е последната.

Теория, за която има ефективен алгоритъм, който ви позволява да разберете от дадена формула дали нейното извеждане съществува, се наричаразрешима; иначе теорията се наричанеразрешима.

Теория, в която не всички формули са теореми, се наричаабсолютно последователна.

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

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

  1. Дадена е азбука (набор) и правила за образуване на изрази (думи) в тази азбука.
  2. Дадени са правилата за образуване на формули (добре оформени, правилни изрази).
  3. От набора от формули по някакъв начин се избира подмножество отTтеореми (доказуеми формули).

Разновидности на дедуктивните теории

В зависимост от метода за конструиране на набор от теореми:

Посочване на аксиоми и правила за извод

В набора от формули се отделя подмножество от аксиоми и се посочва краен брой правила за извод - такива правила, с помощта на които (и само с помощта на тях) могат да се формират нови теореми от аксиоми и по-рано изведени теореми. Всички аксиоми също са включени в броя на теоремите. Понякога (например в аксиоматиката на Пеано) една теория съдържа безкраен брой аксиоми, които са определени с помощта на еднаили няколко схеми на аксиоми. Аксиомите понякога се наричат ​​"скрити определения". По този начин се дефинира формална теория (формална аксиоматична теория,формално (логическо) смятане).

Питам само аксиоми

Дадени са само аксиоми, правилата за извод се считат за добре известни.

Посочване само на правила за извод

Няма аксиоми (наборът от аксиоми е празен), дадени са само правила за извод.

Всъщност теорията, дадена по този начин, е частен случай на формалната, но има собствено име:теория на естествения извод.

Свойства на дедуктивните теории

Последователност

Теория, в която наборът от теореми обхваща целия набор от формули (всички формули са теореми, „верни твърдения“), се наричапротиворечива. В противен случай теорията се наричаконсистентна. Изясняването на непоследователността на една теория е една от най-важните и понякога най-трудните задачи на формалната логика. След изясняване на несъответствието теорията по правило няма по-нататъшно теоретично или практическо приложение.

Една теория епълна, ако за всяко изречение (затворена формула) F, или самото F, или неговото отрицание ¬ F може да бъде изведено в него. В противен случай теорията съдържа недоказуеми твърдения (твърдения, които не могат нито да бъдат доказани, нито опровергани чрез самата теория) и се наричанепълна.

Аксиома Независимост

Отделна аксиома на теория се счита занезависима, ако тази аксиома не може да бъде изведена от останалите аксиоми. Зависимата аксиома по същество е излишна и нейното премахване от системата от аксиоми няма да повлияе по никакъв начин на теорията. Цялата система от аксиоми на една теория се наричанезависима, ако всяка аксиома в нея е независима.

Разрешимост

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