Какво е доказателство

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

Смисълът на доказателствата

Доказателствата имат смисъл в математиката поради няколко причини. Основната причина е, че без помощта на доказателства не можем да потвърдим никоя идея или хипотеза, която ни хрумне. Бихме могли например да вярваме, че простите числа са краен брой, но ако нямаме доказателство, това си остава само безсмислено твърдение. От друга страна, и недоказаните твърдения имат смисъл в математиката (и другаде). Просто се казва, че ако е в сила предположението, че простите числа са краен брой, то е в сила… някаква друга теория.

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

Причината доказателствата да се учат в училище е, че който разбере доказателството, разбира и самия материал. Обикновено трудно можеш да разбираш добре даден материал, без да разбираш доказателствата. Думата „разбираш“ подчертах съвсем умишлено, защото ако научиш доказателствата наизуст един ден преди изпита, а на следващия ден само ги изсипеш на листа, това не означава, че си по-близо до разбирането на съответната тема.

Така при ученето на даден материал доказателствата отговарят на въпроса „защо е така?“ Ако разбереш защо нещо работи, по-лесно ще го запомниш и след време ще разбираш материала определено по-добре от човек, който го е учил на зубрене. Въпросът е дали това е твоята цел.

Какво е доказателство

Какво е доказателство, се определя формално в математическата логика например с помощта на синтактично следване, но ние ще се задоволим с далеч по-просто определение.

В началото на всяко доказателство трябва да имаме твърдение, което искаме да докажем. Това твърдение ще означим с магическия символ ϕ. Това е гръцка буква, която четем „фи“. Освен това ще ни трябва някакво множество от аксиоми и предположения, ще го означим Ax, с помощта на които ще докажем твърдението ϕ. Множеството от аксиоми е нещо, което вече знаем, което предполагаме, че е в сила. Могат да бъдат неща като например „всяко четно число се дели на две“. Освен това множеството може да съдържа например формули за преобразуване на изрази, които са доказани някъде настрани и вече предполагаме, че са в сила, например:

$$(a+b{)}^2=a^2+2ab+b^2;a,b\in \mathbb{R}$$

Сега последователно ще преобразуваме твърденията от множеството Ax, докато получим твърдението ϕ. Всички преобразувания трябва да са логически правилни, трябва да отговарят на основната съждителна логика. Например ако искаме да докажем предишната формула, ще действаме така: израза

$$(a+b{)}^2$$

преобразуваме с еквивалентни преобразувания, докато получим израза от дясната страна. Ще покажа:

$$(a+b{)}^2=(a+b)\cdot (a+b)=a\cdot a+a\cdot b+b\cdot a+b\cdot b=$$

$$=a\cdot a+2ab+b\cdot b=a^2+2ab+b^2$$

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

Важното е, че всяко преобразуване трябва да е валидно, трябва да изхожда от нещо, което вече познаваме. Математическото доказателство е нещо като еволюция – с последователни малки промени получаваме от един израз друг израз.

Тривиални доказателства

Тривиално доказателство (или още очевидно доказателство) е термин за доказателство, което не се побира на дъската, затова се прескача и ученикът го научава от учебника като домашно. :-) Сериозно сега – тривиалните доказателства са доказателства, които обикновено следват от някакво определение в една тривиална стъпка.

Ще го покажем на пример: нека имаме множеството на естествените числа, тоест множеството от числа ℕ = {1, 2, 3, …}. Сега можем да кажем, че всяка дроб от вида:

$$\frac{q}{p};q,p\in \mathbb{N}$$

е валидна дроб, тоест не съществува двойка числа q, p, за която зададената дроб да няма смисъл. Как бихме го доказали? Първо трябва да се сетим кога дробта няма смисъл. Дробта няма смисъл, когато в знаменателя има нула (не можем да делим на нула). Трябва следователно да докажем, че p ≠ 0 за всички възможни p. Ние обаче знаем, че p вземаме от естествените числа, които сме определили като ℕ = {1, 2, 3, …}. Множеството на естествените числа не съдържа нулата, така че числото p винаги ще е различно от нула.

$$\mathrm{\forall }p\in \mathbb{N}:p\ne 0$$

И доказателството е готово. Знаем, че ако числителят и знаменателят на дробта са от естествените числа, дробта е валидна.

Тривиалните доказателства обикновено наистина са тривиални, но само ако познаваш околния контекст. Например ако не разбираш понятието множество или не знаеш какво означава, че p е елемент на множеството ℕ, то дори това доказателство не е било тривиално за теб. Тривиалните доказателства се отличават не толкова с това, че са прости, колкото с това, че са кратки и следват просто от някакъв (произволно труден) контекст.

Контрапример

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

Пример: „всяко естествено число е по-голямо от десет“. По какъв начин ще докажем, че това не е вярно? Контрапример на нашето твърдение е например числото пет. Числото пет е естествено число и не е по-голямо от десет. Твърдението не можем да докажем, като изброим няколко естествени числа, които са по-големи от десет. Не можеш да кажеш „естествените числа 11, 12, 13, 123 и 5345 са по-големи от 10, така че даденото съждение е вярно“. Това не става. Само избрахме няколко примера, за които нашето твърдение е в сила, но това не казва нищо за останалите числа, които изобщо не споменахме.

Втори пример: всеки мъж, по-висок от два метра, има кафяви или сини очи. Предполагам, че малцина могат да намерят контрапример. Какво ни казва това за даденото съждение? Ами нищо. Ако не можем да намерим контрапример, това не означава непременно, че даденото съждение е вярно. Контрапример може някъде да съществува, просто в момента не можем да го намерим. Неспособността да се намери контрапример не доказва, че даденото твърдение е вярно.

Пряко доказателство

Основният вид доказателство е прякото доказателство. Сухо действаме по определението и преобразуваме първоначалното съждение, докато получим съждението, което искаме да получим. Обикновено искаме да докажем съждение, което има вид на импликация A ⇒ B, където A е някаква изходна точка, предположение, а B е съждението, което искаме да изведем, да докажем. Ако е в сила съждението A, то е в сила съждението B. Често е зададено само съждението B, тоест това, което искаме да докажем, а съждението A трябва да изберем сами по подходящ начин.

Следва верига, в която с помощта на импликации извеждаме други съждения и като последно съждение се оказва съждението B. Схематично това може да се запише така:

$$A\Rightarrow A_1\Rightarrow A_2\Rightarrow A_3\Rightarrow \dots \Rightarrow A_n\Rightarrow B$$

За пример ще докажем, че е в сила съждението

$$a>1\Rightarrow a^2>1$$

Сега по стъпки:

1. Тъй като a>1, със сигурност е в сила и a>0, както и a ≠ 0 (всъщност само отслабваме условието).
2. Тъй като a не е равно на нула и е положително, можем безгрижно да умножим цялото неравенство по променливата a. Ако a беше нула, строгото неравенство нямаше да се запази (щяхме да получим 0>0), ако беше отрицателно, щеше да се наложи да обърнем знака на неравенството. След умножение по променливата a получаваме израза a²>a.
3. В този момент знаем, че a>1 и същевременно знаем, че a²>a. Ако обединим тези две неравенства, получаваме: a²>a>1.
4. Оттук просто махаме средния израз и имаме израза a²>1. Това можехме да си позволим, защото a е по-голямо от едно и a² е по-голямо от a. Ако a² е по-голямо от a и a същевременно е по-голямо от едно, със сигурност a² е по-голямо от едно.

Символно можем да го запишем така:

$$a>1\Rightarrow a>0\Rightarrow a^2>a\Rightarrow a^2>a>1\Rightarrow a^2>1.$$

Непряко доказателство

Непрякото доказателство вече използва повече свойствата на импликацията. Ако трябва да докажем твърдение от вида A ⇒ B, можем да използваме контрапозицията на импликацията и да докажем

$$\mathrm{\neg }B\Rightarrow \mathrm{\neg }A.$$

Този начин понякога може да е по-удобен например от прякото доказателство. Подобен подход използва доказателството от противното, към което може да се преобразува всяко непряко доказателство. Ще опитаме непряко да докажем твърдението

$$a-b=0\Rightarrow a=b.$$

Сега извършваме контрапозиция на импликацията:

$$\begin{array}{rcl}\mathrm{\neg }(a=b)& \Rightarrow & \mathrm{\neg }(a-b=0)\\ a\ne b& \Rightarrow & a-b\ne 0\end{array}$$

Ако a ≠ b, можем да разложим b на сбор b = a + x, където x представлява разстоянието на числото b от числото a. Изразът се променя така:

$$a\ne (a+x)\Rightarrow a-(a+x)\ne 0;x\ne 0$$

Съкращаваме променливите a, които можем:

$$0\ne x\Rightarrow -x\ne 0;x\ne 0$$

Тъй като x ≠ 0, е и −x ≠ 0, така че импликацията е в сила. Твърдението е доказано, с което е в сила и първоначалното съждение

$$a-b=0\Rightarrow a=b.$$

Други техники за доказване са например вече споменатото доказателство от противното или доказателство по индукция.

Други източници

• Математическо доказателство в Уикипедия