Директен доказ

Од Википедија — слободната енциклопедија

Во математиката и логиката, директен доказ е начин на докажување дека дадено тврдење е вистинито, или пак дека е невистинито и тоа преку непосредно комбинирање на востановени факти, обично претходно докажани леми и теореми, или пак аксиоми, без какви било дополнителни претпоставки. За директно докажување на тврдење во форма на импликација "Ако p, тогаш q", неопходно е единствено да се претпостави дека е исполнет условот, односно претпоставката p. За да се стигне од претпоставката до заклучокот се користат формалните правила за изведување на заклучоци (расудување). Скоро секогаш се користи таканаречената логика од прв ред, односно предикатна логика, со вклучување на кванторите за секој и постои. Правилата за изведување на заклучоци се модус поненс и хипотетички силогизам.

Обратно, индиректен доказ може да почнува со различни погодни хипотетички сценарија и потоа продолжува со елиминирање на неодреденостите во секое од тие сценарија сè додека не се стигне до неизбежен заклучок дека тврдењето што се докажува мора да е вистинито. На пример, наместо да се докажува директно импликацијата p → q, може да се докаже контрапозицијата ~q → ~p (се претпоставува дека е исполнето ~q и се покажува дека тоа води до заклучок дека мора да е исполнето ~p). Бидејќи p → q и ~q → ~p се еквивалентни според принципот на транспонирање, всушност докажано е p → q. Методите на докажување кои не се директни вклучуваат доказ преку контрадикција. Директните методи на докажување вклучуваат доказ преку претресување на сите случаи, доказ преку бесконечно спуштање и доказ преку индукција.

Пример[уреди | уреди извор]

Следи едноставен, директен доказ дека збирот на два парни цели броеви е парен цел број.

Нека и се произволни парни цели броеви. Од нивната парност следува дека постојат цели броеви и , така што и . Тогаш, за збирот се добива: . Следува дека е делив со 2, па значи е парен. Од произволноста на и следува дека збирот на секои парни цели броеви е парен цел број.