Matematička logika

Matematička ili moderna logika je grana matematike i logike koja se bavi prikazom tradicionalne logike simbolima (pa se još naziva i simboličkom logikom), pri čemu je sve potpuno definirano te nema mogućnosti različitog shvaćanja kao što je to često u tradicionalnoj logici. Matematička je logika osnova modernih računala - na njoj se temelji cijeli logički dio procesora (CPU).

Povijest

Razvitku teorije matematičke logike su pridonijeli su George Boole (Booleova algebra), koji je otkrio zakonitosti ovog područja (začetke je postavio u jednom svom djelu iz 1847.), te hrvatski matematičar Vatroslav Bertić (čije je djelo doduše mnogo manje poznato, ali osnove ovome je postavio u svom djelu iz 1846., bez poznavanja Booleovog djela).

Iskazna logika

Iskazna je logika dio matematičke logike koji se bavi isključivo iskazima (jednostavnim i složenim), a ne jednostavnijim oblicima (prirocima). Osnova iskazne logike je iskaz. On se može usporediti s izjavom a dijeli se na jednostavne i složene iskaze:

Jednostavni iskaz

Jednostavni iskaz označava skup riječi kojima je nekom predmetu pridruženo neko svojstvo, odnosno prirok (vidi: Priročna logika). Lako se može usporediti s jednostavnom rečenicom u hrvatskome jeziku. Npr. rečenica "Hrvoje je pametan" može biti jednostavan iskaz. On će se u matematičkoj logici označavati velikim latiničnim slovom, npr. H (s tim da se uvijek mora navesti koje slovo označava koju rečenicu).

Primjeri:

• Mateja ide u Zagreb.
• Lihtenštajn je država.
• Egipatske su piramide najveličanstvenije građevine koje su ljudi ikad napravili.
• Sunčica će možda jednog dana obući onu prekrasnu zelenu haljinu s crvenim i žutim cvjetićima koju je kupila prije dvije ili tri godine kad je bila na nezaboravnom maturalnom putovanju u Madridu.

Istinosno vrednovanje
U matematičkoj logici svakom iskazu moramo dodijeliti moguća istinosna vrednovanja. Pogledajmo rečenicu "Hrvoje je pametan." Možemo li tvrditi da je ta rečenica apsolutno točna ili apsolutno netočna? Ne možemo. Zato moramo pretpostaviti i jednu i drugu mogućnost - da je ta rečenica istinita i da je neistinita. Istinosna tablica za taj iskaz izgleda ovako:

H
i
n

U ovoj tablici i označava istinu, a n neistinu. Umijesto tih znakova mogu se koristiti i parovi: "I - N", "T - N", "t - n", "T - ⊥", "T - F", "t - f", "1 - 0" i sl.
O istinosnim tablicama više u nastavku.

Složeni (sastavljeni) iskaz

Složeni ili sastavljeni iskaz je iskaz koji se sastoji od (obično) više jednostavnijih (jednostavnih ili složenih) iskaza. Ti se iskazi nazivaju podiskazima. Može se usporediti sa složenom rečenicom u hrvatskome jeziku, ali ne uvijek. Jednostavniji se iskazi spajaju različitim poveznicima.

Primjeri:

• Mateja ide u Zagreb, a Luka u Rijeku.
• Ako budeš dobar, dobit ćeš sladoled.
• Ili idem na bazen, ili se ostajem sunčati u dvorištu.
• Idemo na izlet samo ako ne bude padala kiša.
• Ivan nije ovdje. (Oprez: negacija spada u složene iskaze, iako je sastavljena od samo jednog iskaza!)
• Ako budem išao u Zagreb, Ivica će ići sa mnom ako i samo ako mu mačka ne bude bolesna ili bude petak.

Konjunkcija

Konjunkcija je vrsta poveznika u iskaznoj logici koja odgovara hrvatskom vezniku i, te se tako i čita. Označava se znakovima: "∧" ili "&", koji se postavljaju između dva jednostavnija iskaza (označenih velikim latiničnim slovom).

Dakle, imamo dva jednostavna iskaza: "Mama peče kolače." (koji označimo s npr, K) te "Tata kuha ručak." (koji označimo s R). Od njih sastavimo složeni iskaz: "Mama peče kolače i tata kuha ručak." Taj bi se iskaz jezikom (simbolima) iskazne logike napisao ovako: "K ∧ R" (umijesto znaka ∧, mogao je stajati i znak &).

Konjunkcija se ne prevodi samo veznikom i. Umijesto njega može stajati mnoštvo naših veznika, npr. a, ali, nego, već, premda, dok...

Istinosno vrednovanje
Kod istinosne tablice za jedan iskaz imali smo dvije mogućnosti: da je taj iskaz istinit i da je neistinit. Sada imamo dva iskaza i prema tome četiri mogućnosti:

1. oba su iskaza istinita
2. prvi iskaz je istinit, a drugi neistinit
3. prvi iskaz je neistinit, a drugi istinit
4. oba su iskaza neistinita.

Pa početna istinosna tablica za iskaz "K ∧ R" izgleda ovako:

K	∧	R
i		i
i		n
n		i
n		n

Sada se takva tablica treba popuniti tako da se u svaki redak, ispod veznika (∧) upisuje istinosna vrijednost za cijeli iskaz, ovisno o tome kakve istinosne vrijednosti imaju osnovni iskazi (K i R) u tome retku. Kod konjunkcije vrijedi pravilo: Konjunkcija je istinita samo kad su oba podiskaza istinita. Prema tome, rečenica "Mama peče kolače i tata kuha ručak." će biti istinita samo kad su i rečenica "Mama peče kolače." i rečenica "Tata kuha ručak." istinite.

K	∧	R
i	i	i
i	n	n
n	n	i
n	n	n

Redak u kojem je cijeli iskaz istinit obojen je plavo.

Disjunkcija

Disjunkcija odgovara hrvatskome vezniku ili. Označava se znakom v.

Ponovo imamo dva iskaza, "Mama peče kolače." (označen s K) i "Tata kuha ručak." (označen s R), ali sada ih sastavimo u složeniji iskaz na ovaj način: "Mama peče kolače ili tata kuha ručak." Simbolima iskazne logike ta rečenica glasi "K v R".

Istinosno vrednovanje
Ponovo imamo jednak broj mogućnosti, pa osnovna (nepotpuna) tablica izgleda jednako, osim promijenjenog poveznika:

K	v	R
i		i
i		n
n		i
n		n

Tablicu popunjavamo na isti način, ali se sad držimo ovog pravila: "Disjunkcija je istinita kad je bilo koji od podiskaza istinit." Odnosno, neistinita je samo u slučaju kad su oba podiskaza neistinita. Popunjena tablica izgleda ovako:

K	v	R
i	i	i
i	i	n
n	i	i
n	n	n

Retci u kojima je cijeli iskaz istinit obojeni su plavo.

Negacija

Negacija je najjednostavniji oblik poveznika iskazne logike, ali je namjerno stavljena poslije konjunkcije i disjunkcije da bi se u njima vidjelo spajanje dvaju iskaza. Negacija sadrži samo jedan iskaz, ispred kojega stoji znak negacije: "¬". Primjer negacije napisane iskaznom logikom: "¬K, što bi se prevelo s "Mama ne peče kolače.", odnosno "Nije istina da mama peče kolače.

Istinosno vrednovanje
Negacija jednostavno "obrne" istinosnu vrijednost iskaza: ako je iskaz istinit, njegova je negacija neistinita, a ako je neistinit, negacija mu je istinita. Negacija je unarna operacija, dok su ostale uglavnom binarne i zahtjevaju dva iskaza. Vrijednost cijelog iskaza piše se ispod znaka negacije. Evo i istinosne tablice:

¬	K
n	i
i	n

Napominjem da sad imamo samo jedan jednostavan iskaz i tako samo dvije mogućnosti (dva retka).

Pogodba (kondicional, implikacija)

Pogodba odgovara hrvatskom skupu riječi "ako ... onda ...". Označava se znakom "→" ili "⊃". Tako se rečenica "K → R" prevodi na hrvatski sa "Ako mama peče kolače, onda tata kuha ručak." (ali nipošto "Tata kuha ručak ako mama peče kolače."!).

Istinosno vrednovanje
Pravilo glasi: "Pogodba je neistinita samo kad je drugi podiskaz neistinit, a prvi istinit." Tablica izgleda ovako:

K	→	R
i	i	i
i	n	n
n	i	i
n	i	n

Ostali poveznici

Za neke od ostalih poveznika navest ćemo samo istinosne tablice i prijevod jer veća objašnjavanja nisu potrebna.

Dvopogodba (bikondicional, ekvivalencija)

"K ↔ R" : Mama peče kolače ako i samo ako tata kuha ručak.

K	↔	R
i	i	i
i	n	n
n	n	i
n	i	n

Binegacija

"K ↓ R" : Niti mama peče kolače, niti tata kuha ručak.

K	↓	R
i	n	i
i	n	n
n	n	i
n	i	n

Inkompatibilnost

"K | R"

K		R
i	n	i
i	i	n
n	i	i
n	i	n

Još složeniji iskazi

I složeni se iskazi mogu spajati u još složenije. Uzmimo npr. ova dva iskaza: "A v B" te "¬C" i spojimo ih veznikom "∧". Kad to radimo, svaki od manjih iskaza stavljamo u zagradu (osim ako je taj iskaz jednostavan ili je negacija): "(A v B) ∧ ¬C".

Kada radimo istinosnu tablicu, prvo napišemo vrijednosti najmanjih iskaza: A, B i C (dakle, sad će biti osam kombinacija, odnosno osam redaka: iii, iin, ini, inn, nii, nin, nni, nnn). Zatim rješavamo sljedeće iskaze po veličini: A v B i ¬C. Kad smo to napravili, idemo na cijeli iskaz (ili na još veće iskaze ako postoje): (A v B) ∧ ¬C. Rješenje cijelog iskaza bit će ispod glavnog poveznika - poveznika koji spaja dva najveća podiskaza (u našem slučaju, poveznik ∧).

(A	v	B)	∧	¬	C
i	i	i	n	n	i
i	i	i	i	i	n
i	i	n	n	n	i
i	i	n	i	i	n
n	i	i	n	n	i
n	i	i	i	i	n
n	n	n	n	n	i
n	n	n	n	i	n

Da su postojala četiri jednostavna iskaza (recimo A, B, C i D), bilo bi potrebno 16 redaka tablice. Uglavnom, vrijedi formula: "Za n jednostavnih iskaza, potrebno je 2ⁿ redaka."

Očuvanje istine

Istinosne tablice nam daju uvid u točnost iskazâ u svim mogućim slučajevima. Ovisno o istinosnim vrijednostima svih slučajeva razlikujemo zadovoljive i nezadovoljive, valjane i nevaljane te istovrijedne iskaze.

Zadovoljivost (ispunjivost)

Zadovoljiv je iskaz onaj iskaz čija je istinosna vrijednost u barem jednom slučaju istinita. Takav je, na primjer, gornji primjer: (A v B) ∧ ¬C.

Nezadovoljiv iskaz je onaj koji ni u jednom slučaju nije istinit, npr. iskaz P ∧ ¬P.

Valjanost (tautologija)

Valjan iskaz je onaj iskaz koji je u svakom slučaju istinit. Takav se iskaz naziva i tautologijom. Primjer takvog izraza je ¬(A v B) → (¬A ∧ ¬B).

Nevaljan iskaz je svaki iskaz koji je u barem jednom slučaju neistinit, npr. ¬(A ∧ B).

Istovrijednost (ekvivalentnost)

Istovrijedni iskazi su oni koji imaju potpuno jednake istinosne vrijednosti. Da bi to bilo moguće, oni moraju imati i iste varijable. Istovrijednost se označava znakom ≡ koji se stavlja između dva istovrijedna iskaza. Par istovrijednih iskaza je A ∧ (B v C) i (A ∧ B) v (A ∧ C).

Povezani članci

• Logički operatori u matematici

Vanjske poveznice

• FESB Osnove matematičke logike
• Katedra za matematiku Grafičkog fakulteta Uvod u matematičku logiku