TAUTOLOGIJE
Posebnu grupu iskaznih formula čine tautologije.
Definicija 1: Iskazne formule koje su tačne za sve vrednosti iskaznih slova nazivaju se
tautologijama.
Drugim rečima, ako u neku iskaznu formulu, umesto iskaznih slova zamenimo bilo
koje vrednosti iskaznih konstanti ( ,  ), dobijamo uvek tačno tvrđenje. Odnosno ma
koju kombinaciju iskaznih konstanti da dodelimo iskaznim slovima, iskazna formula će
uvek biti tačna.
Tautologije čine veoma važnu kategoriju u matematičkoj logici te je stoga veoma važno
utvrditi mehanizme pomoću kojih je moguće odrediti da li je neka formula tautologija ili
nije.
Iako postoji mnogo načina da se ta provera izvrši, ove godine ćemo se fokusirati na tri
osnovna i najjednostavnija načina: 1) metoda tablice
2) metoda diskusije po slovu
3) metoda svođenja na apsurd (reductio ad absurdum)
Metoda tablice: Sa ovom metodom smo se već sreli. Ona se sastoji u kreiranju tablice
istinitosti za formulu za koju želimo da pokažemo da li je tautologija (postupak kreiranja
istinitosne tablice demonstriran u prethodnom poglavlju, videti zadatak 4). Nakon
kreiranja tablice potrebno je pogledati poslednju kolonu. Ukoliko se u njoj na svim
mestima nalaze slova “T”, radi se o tautologiji, a ukoliko je na bar jednom mestu
konstanta  , nije u pitanju tautologija.
Primer 1: Metodom tablice ispitati da li je sledeća formula tautologija: ( p  q)  (q  p)
pq
q p
p
q
( p  q )  (q  p )
T
T
T
T
T
T
T
T


T
T
T


T
T
T


Posmatramo osenčenu kolonu. Obzirom da se u njoj nalaze samo iskazne konstante
„T“, zaključujemo da se radi o tautologiji. Ovo je najjednostavnija metoda ali i zahteva
najviše posla. U slučaju većeg broja iskaznih slova nema smisla koristiti ovu metodu.
Metoda diskusije po slovu: Ovo je najprimenjivija metoda. Uspešno se koristi i za
formule koje imaju više od dva iskazna slova.
Prvi korak je da izaberemo iskazno slovo koje je najfrekventnije u iskaznoj formuli (ono
koje se pojavljuje najveći broj puta). Nije neophodno početi baš od tog slova ali nam
dobar izbor skraćuje obim posla. Nakon što smo izabrali neko iskazno slovo dalji rad
nastavljamo posmatrajući dva slučaja (vršimo grananje) : prvi kada je istinitosna vrednost
tog slova jednaka „T“ i drugi kada je ta vrednost jednaka „  “.
Umesto izabranog slova ubacujemo iskazne konstante T ili  , u zavisnosti od grane koju
posmatramo, i uprošćujemo iskaznu formulu, radeći operacije za koje smo već sigurni
kakav im je rezultat. Kada smo to završili ako nismo dobili u obe grane neke identitete i
time utvrdili da je reč o tautologiji ili bar jednu kontradikciju i tako utvrdili da se ne radi
o tautologiji, ovaj postupak nastavljamo dalje, birajući neko drugo iskazno slovo i raditi
diskusiju po tom slovu (vršimo novo grananje). U jednom trenutku ćemo dobiti ili u
svim granama identitete(T=T) i tada je reč o tautologiji. Ako u bar jednoj grani dobijemo
kontradikciju(T=  ) onda tražena formula nije tautologija. Sledećim primerom ćemo
demonstrirati kako funkcioniše ova metoda i tada će sve biti mnogo jasnije:
Primer2: Metodom diskusije po slovu proveriti da li je sledeća formula tautologija:
( p  q)  [( p  (q  r ))  ( p  r )]
Utvrđujemo da je najfrekventnije iskazno slovo, slovo p, i po njemu radimo diskusiju.
1)  ( p)  T , sada u glavnu formulu gde god se nalazi slovo p umesto njega pišemo T:
(T  q)  [(T  (q  r ))  (T  r )] i počinjemo diskusiju. Posmatramo prvu zagradu
(T  q) . Ako iz nečega tačnog sledi q ta zagrada će biti tačna ako je q tačno, a ako je q
netačno i cela zagrada će biti netačna. Odatle zaključujemo da je istinitosna vrednost te
zagrade zapravo slovo q. Na isti način zaključujemo i u ostalim zagradama i tako
dobijamo novu formulu: q  [(q  r )  r ] . Ovde nastavljamo diskusiju tako što biramo
neko drugo slovo, na primer neka to bude q. Sada imamo dve nove grane-podgrane:
1.a)  (q)  T i 1.b)  (q)  . Nastavljamo diskusiju u ta dva podslučaja:
1.a)  (q)  T , menjamo u iskazu svuda umesto slova q stavljamo T i tako dobijamo:
T  [(T  r )  r ] , odakle dobijamo da je taj iskaz ekvivalentan iskazu: T  (r  r ) , a
to je dalje ekvivalentno sa T  T što je identitet T.
1.b)  (q)  , takođe menjamo u iskazu svuda umesto q pišemo znak  i tako dobijamo:
 [( r )  r ] , što je dalje ekvivalentno sa  (T  r ) , pa dalje imamo  r a to
je T.
Dakle dokazali smo da u slučaju da je  ( p)  T dobijamo identitet. Sada proveravamo i
drugu granu:
2)  ( p)  , sada u glavnu formulu umesto p pišemo  . Tada imamo:
( q)  [( (q  r ))  ( r )] što je dalje ekvivalentno sa T  (T  T ) pa
imamo da je to ekvivalentno sa T. Tako smo utvrdili da je i druga grana identitet, pa iz
činjenice da se u obe grane dobijaju identiteti sledi da je početna formula tautologija.
Sledeći šematski prikaz demonstrira kako smo raščlanili zadatak:
( p  q)  [( p  (q  r ))  ( p  r )]
 ( p) 
 ( p)  T
(T  q)  [(T  (q  r ))  (T  r )]
q  [(q  r )  r ]
 (q)  T
T  [(T  r )  r ]
T  (r  r )
T T
Т
 (q) 
 [( r )  r ]
 (T  r )
 r
Т
( q)  [( (q  r ))  ( r )]
T  (T  T )
Т
Metoda svođenja na apsurd (Reductio ad absurdum): Veliki broj matematičkih
problema, dokaza različitih teorema, zasniva se upravo na svođenju na apsurd tj.
kontradikciju.
Šta je suština ove metode? Suština je u tome da krenemo od suprotne pretpostavke i da
dokažemo da je ta pretpostavka pogrešna. Na primer, kada dokazujemo da iskaz jeste
tautologija, pretpostavimo da taj iskaz zapravo nije tautologija. Dalje ga razvijamo tako
sve dok ne dobijemo neki apsurd, neku kontradikciju. U ovom slučaju kontradikcije su
takve da u jednom trenutku rada dobijemo da je na primer  ( p)  T , a da u nekom
sledećem koraku dobijamo  ( p)  . Tada prekidamo rad i proglašavamo apsurd, jer je
jasno da istinitosna vrednost nekog iskaznog slova ne može istovremeno biti i T i  . Ova
metoda je korisna samo u slučajevima da je glavna operacija u iskaznoj formuli za koju
želimo da pokažemo da je tautologija, disjunkcija ili implikacija. Za ostale operacije
nema svrhe koristiti ovu metodu, već treba upotrebiti neko od dve prethodno navedene
metode. Zašto je baš pogodna samo za ova dva slučaja? Jedino disjunkcija i implikacija
dva iskaza nije tačna samo u jednom slučaju. Tačnije p  q nije tačno samo ako su i leva
i desna strana netačne, a p  q je netačna samo ako je leva strana tačna a desna nije.
Upravo od tih slučajeva krećemo kada dokazujemo da je nešto tautologija.
Primer 3: Metodom svođenja na apsurd dokazati da je sledeća formula tautologija:
( p  ( p  (q  r )))  (q  ( s  t )) .
Dakle, glavna operacija u ovoj iskaznoj formuli jeste implikacija. Sada pretpostavljamo
suprotno, da ova formula nije tautologija. U tom slučaju moralo bi da važi da je leva
strana implikacije tačna a desna netačna, pa imamo:
 (( p  ( p  (q  r ))))  T i  ((q  (s  t )))  tada nastavljamo da dalje
raščlanjujemo ove izraze pa dobijamo:
 ( p)  T ,  ( p  (q  r ))  T ,  (q)  T i  (s  t )  , ako dalje nastavimo sa ovim
postupkom imaćemo:  ( p)  T ,  (q  r )  T ,  (q)  T i  (s)  i  (t )  pa je
dalje:  ( p)  T ,  (q)  T ,  (r )  T ,  (q)  T i  (s)  i  (t )  a iz ovoga sledi
 ( p )  T ,  (q) ,  (r )  T ,  (q)  T i  ( s)  i  (t )  . Odavde jasno vidimo da
smo dobili da je iskazno slovo q istovremeno i tačno i netačno, što ja naravno
kontradikcija, pa sledi da naša pretpostavka nije bila tačna , tj. da je početna formula
zaista tautologija.
U matematičkoj logici postoji i pojam suprotan tautologiji.
Definicija 2: Iskazne formule koje nisu tačne ni za jednu vrednost iskaznih slova nazivaju
se kontradikcijama.
Najjednostavniji primer kontradikcije jeste formula:
( p  p)
Jasno je da ne može istovremeno biti tačno i tvrđenje p i njemu suprotno tvrđenje p .
Dokazivanje da je neka iskazna formula kontradikcija može se izvesti na potpuno isti
način kao i dokaz da je tautologija, s tim što je onda u tablici potrebno da u poslednjoj
koloni budu sve vrednosti  .
Postoji određen broj osnovnih tautologija koje se često primenjuju i koje bi bilo dobro
zapamtiti, kako ne bismo svaki put gubili vreme dokazujući ih.
Sada ćemo navesti nekoliko takvih tautologija:
1) p  p - zakon isključenja trećeg.
2) ( p  p) -zakon neprotivrečnosti.
3)
4)
5)
6)
( p  q )  p  q
- De Morganovi zakoni
( p  q )  p  q
pq  q p
- komutativnost konjunkcije i disjunkcije
pq  q p
( p  q )  r  p  (q  r )
- asocijativnost konjunckije i disjunkcije
( p  q )  r  p  (q  r )
p  (q  r )  ( p  q)  ( p  r )
- distributivnost konjunkcije i disjunkcije.
p  (q  r )  ( p  q)  ( p  r )
7) ( p  ( p  q))  q - modus ponens
8) ( p  q)  (q  r )  ( p  r ) - pravilo tranzitivnosti
9) ( p  q)  (q  p) - zakon kontrapozicije.
Ove formule, ako upamtimo, na
pismenom ne moramo da dokazujemo već
uzimamo bez provere da su tautologije.
ZADACI:
1. Metodom diskusije po slovu dokazati da su navedene tautologije zaista tautologije.
2. Sastaviti tablicu istinitosti za sledeće formule i odrediti koje od njih su tautologije:
a) ( p  q)  r; b) ( p  r )  q;
c) ( p  q)  (q  r )  ( p  r );
d ) (( p  q)  (r  p))  (q  r );
e) ( p  q)  (p  q);
f ) ( p  q)  (( p  q)  (q  p));
g ) ( p  p)  ((q  q)  (r  p))
Da li je neka od navedenih formula kontradikcija?
3. Ispitati da li su sledeće formule tautologije:
a) p  p; b) ( p  ( p  p ))  p;
c)[( p  q)  (r  p)]  ( p  q);
d )[[p  (q  r )]  (r  p )  (q  r )]  r ;
e) ( p  (q  r ))  q; f )( p  q )  [( p  (q  r ))  ( p  r ).
4. Polazeći od suprotne pretpostavke(svođenjem na apsurd) dokazati da su sledeće
formule tautologije:
a) (( p  q)  r )  (( s  t )  (r  p));
b) ( p  (q  r ))  ((q  s)  (t  p));
c) ((p  q)  (r  s))  ((r  t )  p);
d ) (q  p)  ( p  q).
5. Data je formula p  q . Naći njoj ekvivalentnu formulu, koja se sastoji samo od slova
p,q i veznika  .
6. Data je tablica
a)
p
q
T
T
T

T



b)

T

T
p
T
T


q
T

T

T

T

Naći bar jednu iskaznu formulu koja zadovoljava ovu tablicu.
7. Dokazati da je formula: ( p  q)  (q  r )  (r  p)  ( p  q)  (q  r )  (r  p)
tautologija.
8. Ispitujući da li za neke vrednosti svojih iskaznih slova data formula može imati
istinitosnu vrednost  , dokazati da je ta formula tautologija:
a) (( p  q)  r )  ((r  p)  (q  p));
b) ( p  q)  ((q  r )  ( p  r ));
c) ( p  q)  (( p  r )  (q  r ));
d ) ( p  q)  (( p  r )  (q  r )).
e) ( p  r )  ((q  r )  (( p  q)  r ))
f ) (( p1  p2 )  ( p2  p3 )  ...  ( pn 1  pn ))  ( p1  pn ), n  2, n   .
Download

TAUTOLOGIJE