Dokazi i dokazivanje, Logika

Indirektni deduktivni dokaz

Comments Off on Indirektni deduktivni dokaz 12 March 2015

U indirektnom deduktivnom dokazu tezu, odnosno, teoremu, dokazujemo tako što dokazujemo da negacija teze nije istinita. Ovaj isti postupak primenjivali smo kada smo metodom svođenja na protivrečnost dokazivali da je neka formula tautologija.

Sada taj postupak možemo primeniti na bilo koju tezu. Da je negacija teze netačna dokazujemo tako što pokažemo da iz nje logički slede dva protivrečna iskaza, odnosno, da iz nje sledi protivrečnost (kontradikcija).

Pošto u logici netačan iskaz može ispravno slediti samo iz netačnog iskaza, kontradikcija, koja je uvek netačna, ukazuje na to da ni antiteza iz koje ona sledi nije tačna, što opet dokazuje da je teza tačna.

Ovaj postupak koristili su još stari Grci. Sada ćemo pokazatui kako je Euklid koristeći ovaj postupak dokazao da ne postoji najveći prost broj.

Naime, mi možemo zamisliti da postoji najveći prost broj, odnosno, da posle nekog broja u nizu brojeva više nema nijednog novog prostog broja. Međutim, da bi tu pretpostavku direktno dokazali morali bi zaista da istražimo beskonačan skup brojeva, što je nemoguće. Isto bi važilo i da je naša teza da najveći prost broj ne postoji, odnosno da se posle svakog prostog broja koji smo pronašli, može pronaći još jedan prost broj veći od njega. Pošto ne možemo ništa dokazati na direktan način, primenjujemo postupak indirektnog dokaza.

Indirektni deduktivni dokaz ove teoreme izgleda ovako:

Teza:
Ne postoji najveći prost broj.

Antiteza:
Postoji najveći prost broj

(neka je to broj Pn)

Dokazivanje:

Ako postoji najveći prost broj Pn , onda možemo zamisliti niz svih prostih brojeva do broja Pn

1, 2, 3, 5, 7, 11. 13, 17, 19, 23, 29, ….., Pn

Ako je tako, onda možemo zamisliti i novi broj Pm koji je jednak proizvodu svih prostih brojeva do najvećeg Pn uvećanom za 1, dakle

Pm = (1∙ 3 ∙5 ∙ 7 ∙…….. ∙ Pn) + 1
Sada se postavlja pitanje: Da li je Pm, koji je sigurno veći od Pn , prost broj?

Pm je proizvod svih prostih brojeva do, po pretpostavci, najvećeg prostog broja Pn , uvećan za 1. Ako ovaj broj podelimo sa sa nekim od tih prostih brojeva manjim od Pk, vidimo da se Pk skrati sa samim sobom iz proizvoda svih prostih brojeva do Pm, ali uvek imamo i ostatak 1/Pk. što znači da Pm nije deljiv sa bilo kojim prostim brojem bez ostatka, što znači da je Pm prost broj.

I to prost broj koji je veći od pretpostavljenog najvećeg prostog broja Pn.

A to je protivrečnost, koja dokazuje da je naša antiteza netačna, a samim tim i da je naša teza tačna.

dakle,

Ne postoji najveći prost broj.

(u stvari je već pronađen prost broj sa 15 miliona cifara, a po ovoj teoremi uvek je moguće da se pronađe i veći prost broj od ovog)

Dokaz svođenjem na protivrečnost je veoma moćno dokazno sredstvo. U iskaznom računu, sve druge tautologije mogu se dokazati samo ako se pretpostavi da je pravilo reductio ad absurdum („svođenje na protivrečnost“ na latinskom) ispravno.

Na sličan način još su pitagorejci otkrili da je √2 iracionalan broj.

Dokaz ove teoreme:

Teza:
√2 je iracionalan broj

što znači da ne postoje celi brojevi m i n čiji razlomak m/n je jednak √2

Antiteza:
√2 je racionalan broj

odnosno, postoje celi brojevi m i n čiji razlomak je jednak √2, i koji nisu oba parni.

Uz uslov da m i n nisu oba parni brojevi, pošto, ukoliko jesu. mogu se napisati kao 2 m1 odnosno
2 n1 pa se broj 2 u njihovom razlomku uvek može skratiti, dok ne dođemo do dva broja koji nisu oba parni.

Ako je tako onda važi:

m/n = √2

ako to kvadriramo i i pomnožimo sa n2

dobijamo

m2 = 2 n2*

što znači da je m2 paran broj, a to onda znači i da je m paran broj (pošto je kvadrat parnog broja uvek paran, a kvadrat neparnog neparan, što nam je ovde pomoćna teorema)

ako je m paran važi da

m = 2 m1

ako sada m gore zamenimo sa 2 m1

dobijamo

(2 m1)2 = 2 n2

odnosno

4 m12 = 2 n2 ili 2 m12 = n2

što znači da je n2 parno, pa je onda po istoj logici, i n parno.

(*iz tehničkih razloga kvadrat je označen sa 2 koje je neposredno iza promenljive, a ne u eksponentu kao što bi trebalo)
Tako smo dobili da su i m i n parni, što je protivrečno sa početnom antitezom, što dokazuje da je ona netačna, što opet dokazuje da je teza tačna:

√2 je iracionalan broj
Indirektni ili apagoški dokaz česta je forma dokaza u matematici i logici.

SHARES
Share on FacebookShareTweet on TwitterTweet

Comments are closed.

© 2024 Kratka istorija filozofije. Powered by WordPress.

Daily Edition Theme by WooThemes - Premium WordPress Themes

%d bloggers like this: