C, PHP, VB, .NET

Нека имаме едно твърдение. Дадена ни е задача да определим дали това твърдение е вярно или грешно. За удобство ще приемем, че трябва да докажем, че твърдението е вярно – ако трябва да докажем обратното, то можем просто да обърнем задачата с отрицание на условието й. Вече знаем, че за да можем да кажем, че едно твърдение е вярно, то ние трябва да стъпим на вече преди това приети за вярни твърдения. С други думи искаме да докажем, че има следствие от приетото за вярно твърдение p към новото твърдение q. За целта се използват дедуктивни, индуктивни или умозаключения с аналогия с изоморфни множества.

Ето един прост пример:

Твърдение: „Ако триъгълник има страни 3, 4 и 5см, то той е правоъгълен„.

Тук е лесно да използваме вече приетото за вярно твърдение „Питагорова теорема“ и нейните следствия, за да докажем, че твърдението от примера е вярно. Така използваме едно твърдение за следствие на друго и имаме именно дедуктивно умозаключение „Питагоровата теорема е вярна и страните на този триъгълник я удовлетворяват, следователно горното твърдение е вярно„.

Когато имаме задача с отворен отговор, то нещата стават по-сложни. Те отново се свеждат до правене на умозаключения, но вече имаме две стъпки в решението на задачата:

1. Търсене на решения – т.е. съставяме поредица от едно или повече твърдения;
2. Доказателство, че намерените решения са вярни, т.е. правене на умозаключение, че съставените твърдения са вярни.

Често втората стъпка е съвсем тривиална и се пропуска. Например когато решаваме задача по схемата на Пап или синтез, то ние винаги знаем, че достигнатото твърдение е вярно. Да, но дори това само по себе си е умозаключение! Затова втората стъпка съществува, дори когато не я изказваме явно. При решаване на задачи по схемата на Евклид ние винаги правим втората стъпка – тя е именно проверката дали намереното решение удовлетворява условието на задачата.

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

Зад. Нека x+1 = 2. Намерете x.

Решение: Изваждаме 1 от двете страни на равенството, с което то не се променя
⇒ x+1-1 = 2-1
⇒ x = 1

Използвали сме решение по схемата на синтез (от условието към решението) като сме стъпили върху три приети за вярни твърдения:

1. Ако извадим число от двете страни на едно равенство, то не се променя;
2. 2-1 = 1
3. 1-1 = 0

Именно на базата на тези три твърдения сме формирали нашето умозаключение, а именно „трите твърдения са вярни, следователно x = 1 е вярно„. Струва ни се съвсем логично да не правим проверка, т.е. доказателство, че твърдението ни е вярно. В такива задачи обаче се казва, че ние всъщност просто сме пропуснали доказателството, т.е. не сме решили задачата докрай. Това е така, понеже знаем, че доказването е прекалено тривиално и се опитваме да спестим време. Ще се убедите обаче, че при по-сложни задачи нуждата от доказателство става все по-нужна. Затова аз лично съм привърженик на това да караме учениците колкото се може по-често да правят проверка на намерените резултати.

Доста удобни за показване на нуждата от тази двустъпкова система на решение на задачи са оптимизационните задачи. В тях има много решения, от които ние търсим само екстремалните. Така например ако имаме един граф, в който всяко ребро има дадена „тежест“, то бихме направили т.нар. транспортна задача – търсим такъв маршрут, че да минем през всички върхове на графа, но да сме натрупали минимална сума от тежестите на ребрата. Ясно е, че в зависимост от графа можем да имаме огромно множество от пътища, които обхождат всички върхове. Ако позволим да минаваме повече от веднъж по дадено ребро, то може да се получат „цикли“ и всъщност решенията да станат безкрайно много. Само едно или няколко от тях обаче водят наистина до минимална тежест, т.е. те са т.нар. екстремални решения. Е в такава задача много ясно се вижда как трябва да процедираме:

1. Обхождаме графа и намираме всички възможни пътища, които не са резултат от цикъл. След това изваждаме от множеството пътища тези с най-малка натрупана тежест и твърдим, че са решения;
2. Доказваме, че намерените решения са вярни и доказваме, че пътищата, които са резултат от цикъл са винаги с по-голяма тежест по-големи от тах.

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

Рядко, но се появяват и задачи с обратен подход. Те следват принципа:

1. Доказателство, че задачата има поне едно конкретно решение;
2. Намиране на едно такова конкретно решение.

Този случай е изключително рядък и обикновено пак се използва за екстремални задачи. Обикновено с индуктивни методи първо правим теоретична оценка на задачата и успяваме да докажем твърдението, че всички възможни решения са в дадени граници. После търсим поне едно такова гранично решение, което даваме като отговор. В такива задачи обикновено не се търси пълно изчерпване на решенията. Използват се, за да се спестят операции и да можем да извършваме изчисленията по-бързо.

В заключение ще кажа, че както се вижда от по-горе задачите с условия „докажете…“ са частен случай на задачите с условия „намерете…“. При първите ни е дадено готово твърдение, което трябва да докажем, че е вярно. При вторите се търси съставяне на такова твърдение, което също трябва да докажем, че е вярно. Не винаги обаче е възможно да преобразуваме и усложним задача от тип „докажете…“ в „намерете…“. Често ни се налага да насочваме учениците към конкретното решение на задачата. Силен пример за това са теоремите, за които ще пиша по-късно.