Tehnike dokazivanja

Question 1

Izgradnja aksiomatse teorije?

Answer 1

1. Jedan broj pojmova proglasavamo za osnovne pojmove - koji se ne definisu jer nije moguce sve definisati. Ovim pojmovima postoji snazna intuitivna predstava, npr. za skup.
2. Jedan broj tvrdjenja proglasavamo za aksiome - tvrdjenja koja se ne dokaziju - jer nije mogucde sve dokazati. Iz aksioma izvodimo nova tvrdjenja koja se nazivaju teoreme.
3. Navodimo pravila logickog zakljucivanja koja smemo da koristimo pri dokazivanu raznih tvrdjenja u toj teoriji.

Question 2

Sta je posledica?

Answer 2

Tvrdjenje koje neposredno sledi iz nekog drugog.

Question 3

Kako se definise dokaz neke teoreme?

Answer 3

Dokaz neke teoreme se moze definisati kao konacan niz tvrdjenja ciji je svaki clan ili aksioma ili tvrdjenje koje je ranije dokazano ili se dobija iz prethodnih clanova niza uz pomoc nekog pravila zakljucivanja. Poslednji clan niza je teorema koju dokazujemo.
(ne razumem ni ja)

Question 4

Direktan dokaz?

Answer 4

Da bi se izveo direktan dokaz implikacije p=>q uzima se da ako je p tacno i upotrebom razlicitih pravila zakljucivanja i teorema koje su ranije dokazane utvrdjuje da i q mora biti tacno.

Question 5

Indirektan dokaz?

Answer 5

Posto je implikacija p=>q jednaka svojoj kontrapoziciji -p=>-q, tacnost implikacije se moze dokazati tako sto se dokaze da vazi njena kontrapozicija. Dokaz ovog tipa se naziva indirektan dokaz. Tacnost kontrapozicije se obicno dokazuje direktno ali se moze koristiti i neka druga tehnika dokazivanja.

Question 6

Prazan dokaz?

Answer 6

Implikacija p=>q se moze dokazati tako sto se dokaze da je p netacno, jer je ona ili oblika 0=>1 ili 0=>0, a u oba slucaja je implikacija tacna. Dokaz ovog tipa se zove prazan dokaz.

Question 7

Trivijalan dokaz?

Answer 7

Implikacija p=>q se moze dokazati tako sto se dokaze da je p netacno, jer je ona ili oblika 0=>1 ili 0=>0 a u oba slucaja je implikacija tacna. Dokaz ovakvog tipa se zove trivijalan dokaz.

Question 8

Dokaz svodjenjem na kontradikciju?

Answer 8

Ako pronadjemo neku kontradikciju q, na primer r ^ -r, takvu da mozemo dokazati da je implikacija -p=>q tacna to onda znaci da tvrdjenje -p mora biti netacno, sto dalje znaci da je p tacno. Ovakva vrsta dokaza se naziva kontradikcija. Ovim postupkom se na pocetku dokaza pretpostavlja da je tvrdjenje koje zelimo dokazati netacno. Ako tokom dokazivanja toga dodjemo do kontradikcije onda znaci da je nasa pretpostavka pogresna i da je tvrdjenje koje smo dokazivali u stvari tacno i time je dokaz gotov.

Question 9

Produzena implikacija?

Answer 9

Dokaz koji se svodi na niz implikacija
p1 => p2, p2 => p3, … , pn-1 => pn, koji se koristi da bi se dokazala implikacija p1 => pn, tj. da prvi clan povlaci poslednji, se naziva produzena implikacija. Tacnost implikacije p1 => pn mozemo dokazati tako sto cemo dokazati tacnost svake implikacije u nizu. Ovaj metod se zasniva na svojstvu tranzitivnosti implikacije. Tj na tautologiji [(p1 => p2) ^ (p2 => p3 ) ^ .. ^ (pn-1 => pn)] => (p1 => pn).

Question 10

Ciklicna implikacija (produzena ekvivalencija)?

Answer 10

Da bi dokazali da su neka n tvrdjenja p1,..,pn medjusobno ekvivalentna, tj. da je pi<=>pj za svako i,j = 1,…, n, i nejednako j, mozemo dokazati da je tacan niz implikacija p1 => p2, p2 => p3, … , pn-1 => pn, pn => p1 - koji se naziva ciklicna implikcija jer je poslednjom implikacijom u nizu zatvoren krug. Implikacije se mogu dokazivati bilo kojim redom, jedino je dakle bitno da zatvorimo krug.
Iz tacnosti implikacija pi => pi+1, pi+1 => pi+2,.., pj+1 => pi dobijamo da je tacna implikacija pi=>pj na osnovu metode produzene implikacije. Iz tacnosti implikacija pj => pj+1,…, pi-1 => pi dobijamo da je tacna implikacija pj=>pi. Iz tacnosti implikacija pi+>pj i pj=>pi zakljucujemo da je tacna ekvivalencija pi <=> pj.

Question 11

Dokaz egzistencije?

Answer 11

Dokaz tvrdjenja koje je oblika (postoji x)P(x) gde je P(x) neki predikat, se naziva dokaz egzistencije zato sto takvo tvrdjenje tvrdi da postoji neki objekat sa odredjenim svojstvom. Konstruktivni dokaz egzistencije je kada eksplicitno navedemo za koji element a je takvo tvrdjenje tacno. Nekonstruktivni dokaz je ako dokazemo da je tvrdjenje (Postoji x)P(x) tacno i bez navodjenja nekog konkretnog a za koje je P(a) tacno, npr. putem svodjenja na kontradikciju.

Question 12

Dokaz jedinstvenosti?

Answer 12

Dokaz tvrdjenja koje je oblika (Postoji ne x?)P(x) se naziva dokaz jedinstvenosti zato sto ono tvrdi da postoji tacno jedan element x sa svojstvom P(x). Ovi dokazi se sastoje iz dve celine:
dokaz egzistencije - dokazuje da postoji element x sa datim svojstvom
dokaz jedinstvenosti - dokazuje da ako je y nejednako x da y nema to svostvo, tj da svako y ima to svojstvo da je onda y = x.