Математическа логика - увод

Увод


страницата се нуждае от дописване/преглеждане


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

Математиката е древна наука и човечеството се занимава с нея от хилядолетия (толкова отдавна, че не може да се каже от кога точно). Гърците в V в.пр.хр. въвеждат доказателството като основен (и единствен) приемлив метод за достигане до нови знания. До онова време се е използвал главно измервателния подход (измерват обема на 100 пирамиди и заключват, че той се намира по формулата $V = \frac{Bh}{3}$). Гърците развиват математиката не заради нейното приложение, а заради самата математика. Владеенето ѝ е било признак на висока култура и обществено положение. В началото математиката се е разивала главно във философски школи (еквивалент на съвременните университети) на известни по онова време философи (математици) - Питагор, Платон, Аристотел, Евклид и други. След отделянето на математиката от философията идва и ред на логиката, за основен виновник на което се счита Аристотел.
Логиката на Аристотел е известна в момента като Силогистка логика. Тя е вършила работа при воденето на научни диспути, но е била крайно недостатъчна за доказателството на математически теореми. Пример за логическо разсъждение в силогистката логика е следната логическа система:

Всички хора са смъртни
Сократ е човек

$\hline$
Сократ е смъртен

Хоризонталната черта се чете следователно. Аристотел класифицира твърденията на няколко основни групи и казва кой съждения (между твърдения от различни групи) са верни.

  • Евклид въвежда по-обобщена логика, която върши работа и на математиците.
  • Лайбниц пък успява да 'алгебризира' логиката - т.е. въвежда уравнения от логически твърдения; решаваш уравнението и получаваш дали дадено твърдение е вярно.
  • Джордж Бул се смята за родоначалник на Математическата Логика. Наричана още в негова чест Алгебра на Бул / Булева алгебра.

Към края на 19 век математиката била разделена на няколко части - алгебра, анализ, геометрия и т.н. Математиците започвали да си задават въпроса кое всъщност е общото между тези дялове. Кантор се заел с тази нелека задача и така поставил началото на теорията на множествата. За жалост началният вариант на теорията бил грешен - Кантор сам открил противоречие в кардиналните числа (отразяват безкрайности). Философът Ръсел също открил просто противоречие. Ще покажем тогавашната теория и противоречието:


Самият Ръсел предлага Patch към теорията, като предлага множествата да се разглеждат на нива, като елементи от едното ниво могат да участват в множества от по-горното ниво.
Предложен е по-добър Patch: в аксиома1 се добавя изискването множествата да се конструират от 'базово' множество и свойство. Т.е елементите на базовото множество се отсяват, и остават само тези, които притежават свойството.(3)
\begin{align} A = \{ x | x \in B \cap P(x) \} \end{align}

Хубавото на тази поправка е, че математиката винаги създава множества използвайки този подход. Т.е математиката автоматично 'стъпва' върху теорията на множествата без да се нуждае от преформулиране на дефиниции/теореми и т.н.

Хилберт поставя няколко проблеми на математическата общност. Един от тях е построяването на пълна и непротиворечива математическа теория. Една теория е пълна, ако всяко твърдение може да се докаже чрез нея, че е или вярно или невярно. Непротиворечива означава, че не може едно твърдение да се докаже, че е едновременно вярно и невярно (това което видяхме в парадокса на Ръсел). Непротиворечивостта на една теория може да се докаже, като се създаде неин модел в друга теория, за която е доказано, че е непротиворечива. В крайна сметка, всичко се свежда до теорията на естествените числа (аритметика - т.е събиране, умножение), затова ако нейната непротиворечивост бъде доказана всички могат да си отдъхнат (иначе може в един хубав момент да се окаже, че всичко в което вярваме и ползваме всекидневно е фундаментално грешно…което не е много добре). Логиката се развива доста в началото на 20век точно за да се опита да докаже непротиворечивостта (и евентуално пълнотата) на аритметиката. Гьодел се появява с 2 теореми, които разклащат цялата математическа (и не само) научни общности. Прочетете теоремите му (които са доказани от него) и ще се уверите.
Теорема на Гьодел #1: Всяка система, която съдържа естествените числа (т.е е базирана на нея - както казахме всички основни дялове са базирани на ест. числа) и е непротиворечива е непълна (т.е съществува твърдение, което не е нито вярно, нито невярно - т.е не може да бъде доказано нито едното нито другото).
Добавянето на едно такова свойство би разширило системата, но тя пак ще остане надграждане на естествените числа, т.е ще съществува ново недоказуемо твърдение. Т.е даже безкрайно да добавяме аксиоми в теорията и тя да остава непротиворечива, никога няма да стане пълна.
Теорема на Гьодел #2: За всяка система съдържаща естествените числа, не може (в нея) да бъде доказана нейната непротиворечивост.
За да се докаже непротиворечивост на дадена система, трябва да се използва нейно разширение, което както се сещате не се знае дали е (не)противоречиво.

Математиците скоро се поуспокоили и се примирили с факта, че не могат да докажат непротиворечивостта на математиката, за това ще внимават повче като правят системи и ще стискат палци :)

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

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

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License