Zoran Skoda logika predikata

Uz ovu stranicu pročitajte i stranicu zaključivanje.

Sud (iskaz) je izjava koja ima točno određenu i nepromjenjivu vrijednost istinitosti, istina ili laž. Istinu označavamo s $\top$ ili $1$, a laž s $\perp$ ili $0$. Koristimo uobičajenu matematičku pokratu akko za sintagmu ‘ako i samo ako’.

Od jednostavnih sudova možemo sastavljati složene sudove, npr. ako je $P$ sud “3 je neparan broj” i Q sud “4 je paran broj” tada možemo sastaviti složeni sud $P\wedge Q$, “3 je neparan broj i 4 je paran broj”. Operator konjunkcije $\wedge$ čitamo “i” jer odgovara (do neke mjere) uporabi veznika i u prirodnom jeziku. Konjunkcija dvaju sudova je istinita akko je svaki od ta dva suda istinit.

Slično, konstruiramo disjunkciju sudova $P\vee Q$ i čitamo $P$ ili $Q$. Disjunkcija sudova je istinit sud onda i samo onda kad je barem jedan od sastavnih sudova istinit.

Implikacija sudova $P\implies Q$ je lažna onda i samo onda ako je $P$ istinit, a $Q$ lažan sud. Dakle čak iz laži možemo dobiti zaključak koji je istinit, ali iz istine nikako ne možemo ispravnim zaključivanjem dobiti laž. Jedino što je nemoguće je da istina implicira laž. $P\implies Q$ čitamo “iz $P$ slijedi $Q$” ili “$P$ implicira $Q$” ili “$Q$ ako $P$”.

Ekvivalencija sudova $P\Leftrightarrow Q$ je istinita ako oba sastavna suda $P$ i $Q$ imaju istu istinitosnu vrijednost, tj. ako su oba istina ili oba laž. $P\Leftrightarrow Q$ čitamo $P$ ako i samo ako $Q$ ili čitamo $P$ onda i samo onda kada $Q$ ili čitamo $P$ je ekvivalentno $Q$.

Konačno negacija suda $P$ je sud $\neg P$ koji je istinit ako je $P$ lažan i lažan ako je $P$ istinit.

Logika sudova ili račun sudova se bavi računanjem istinitosnih vrijednosti izraza koji se od jednostavnih sudova dobiju pomoću gornjih operacija negacije, disjunkcije, konjunkcije, implikacije i ekvivalencije. Pri tome smatramo da se negacija uže veže uz ime suda, a druge su operacije jednako vrijedne pa redoslijed moramo diktirati zagradama.

Dakle, imamo slijedeća gramatička pravila produkcija kako formiramo složene sudove

$$\array{ JEDNOSTAVNISUD \to \top \\ JEDNOSTAVNISUD \to \perp \\ SUD \to JEDNOSTAVNISUD \\ SUD \to (SUD \wedge SUD) \\ SUD \to (SUD \vee SUD) \\ SUD \to \neg SUD \\ SUD \to (SUD \implies SUD) \\ SUD \to (SUD \Leftrightarrow SUD) }$$

i naravno $JEDNOSTAVNISUD$ možemo zamijeniti imenom nekog jednostavnog suda.

Npr. pogledajmo slijedeće primjere složenih sudova

$(\top \implies \perp)\implies (\perp\implies\perp)$ je sud čija vrijednost je $\top$

$(P \implies R) \wedge (R\vee Q)$ gdje su $P,Q,R$ imena jednostavnih sudova. Istinitosna vrijednost tog suda zavisi od istinitosnih vrijednosti sudova $P,Q,R$, dakle o $2\times 2\times 2 = 8$ kombinacija njihovih istinitosnih vrijednosti.

Složeni sud čija vrijednost je istina za ma koju kombinaciju istinitosnih vrijednosti jednostavnih sudova u njegovoj strukturi zovemo tautologijom logike sudova.

Predikat (prirok) je izjava čija istinitosna vrijednost zavisi samo od vrijednosti nekog parametra. Dakle, za svaku vrijednost parametra dobijemo sud, pa je prirok kao familija sudova koja je parametrizirana tim parametrom. Ako je $x$ parametar (kažemo i argument priroka) tada predikat zovemo $P(x)$. Sam izraz $P(x)$ nema istinitosnu vrijednost, nema značenja, sam po sebi je besmislen. Parametar/argument $x$ mora biti iz neke kolekcije mogućih parametara, no ako ipak nismo odredili za koju vrijednost testiramo izraz tada kažemo da je $x$ slobodni ili nevezani parametar. Ako je $P$ predikat “biti paran broj” na skupu prirodnih brojeva tada je $P(1)$ laž, a $P(2)$ istina. Ako smo fiksirali koliko je $x$ tada znamo vrijednost $P(x)$. Zanima nas slučaj kad je $P(x)$ točan za svaku vrijednost od $x$, što izražavamo rečenicom: za svaki $x$ vrijedi $P(x)$ i pišemo $(\forall x) P(x)$. Taj izraz je istinit ako je za svaki broj stavljen umjesto $x$ izraz $P(x)$ istinit. Ovdje smo pretpostavili da je skup parametara koje gledamo skup (prirodnih) brojeva, no općenito to nije jasno. Zato bismo točnije trebali reći $(\forall x\in N) P(x)$ gdje je $N$ skup prirodnih brojeva. Ekvivalentno možemo reći da je $x$ varijabla općeg tipa i da naknadno specificiramo u kvantificiranoj formuli da je $x\in N$, tj. $(\forall x) (x\in N \wedge P(x))$. Simbol $\forall$ zovemo univerzalnim kvantifikatorom. U izrazu $(\forall x\in N)P(x)$ jasno je za koje vrijednosti testiramo $P(x)$ i kako je definirana istinitosna vrijednost cijelog izraza jer nema parametara koji lete slobodni u zraku i ne znamo na koje vrijednosti ih testiramo. Kažemo da je $x$ vezana varijabla (tj. nije slobodna). Ako gledamo samo izraz $P(x)$ onda nije jasno gdje leži $x$ i unutar tog izraza $x$ nije vezana nego slobodna varijabla. Pitamo se na primjer da li su svi prirodni brojevi parni ? $(\forall x\in N)(paran(x))$. Nisu, jer $1$ nije paran pa je cijeli izraz laž.

Izraz $(\exists x) P(x)$ (“postoji $x$ takav da je $P(x)$”) je drugi način određivanja kako testirati $P(x)$. Taj izraz ima vrijednost istina akko postoji vrijednost parametra $x$ za koju je $P(x)$ istina. Simbol $\exists$ označava egzistencijalni kvantifikator. Predikat ima određenu vrijednost samo ako su svi argumenti vezani.

Jednostavne predikate možemo kombinirati u složene predikate. Npr. ako su $P(x), Q, R(y,z)$ tri predikata (prvi ima jedan argument, drugi nema argumenata, a treći ima dva argumenta) tada slijedeći predikat

$$(\forall x) ((P(x) \cap Q) \implies ((\exists x')P(x') \vee (\forall y)(\forall z)R(y,z)))$$

ima neku istinitosnu vrijednost koja zavisi naravno o izboru predikata jer su svi argumenti vezani.

Primjetimo da uvijek ako vrijedi $(\forall x)P(x)$ tada vrijedi i $(\exists x)P(x)$ (pri čemu u računu predikata podrazumijevamo da univerzalni skup nije prazan, inače $P(x)$ ne bi imao niti jednu definiranu istinitosnu vrijednost pa ne bi bio predikat).

Jednakost $=$ i kratice $\neq$ i $\exists! x$

Posebno zanimljiv predikat je jednakost $=$, posebno značajan predikat koji zavisi od dva argumenta.

Taj predikat tipično ima drukčiju sintaksu, umjesto $=(x,y)$ pišemo $x = y$.

U logici predikata možemo neke objekte smatrati jednakima. Kažem da je predikat jednakosti $=$ s dva argumenta istinit za one parove za koje su oba argumenta jednaka ili identična u nekom smislu. Npr. interpretiramo da su nazivi argumenata samo različiti nazivi za isti objekt u interpretaciji. Sintaktički, prije nego možemo osmisliti interpretaciju preko objekata, tražimo samo da jednakost zadovoljava svojstva

• tranzitivnost $(\forall x)(\forall y)(\forall z)((x = y)\wedge(y=z))\implies (x = z)$ (ako je neki $x$ jednak nekom $y$ i taj $y$ jednak nekom $z$ tada je i taj $x$ jednak tomu $z$)

• simetričnost $(\forall x)(\forall y) (x = y)\implies (y = x)$ (ako je neki $x$ jednak nekom $y$ tada je taj $y$ jednak tome $x$)

• refleksivnost $(\forall x)(x = x)$ (svaki $x$ je jednak sebi samom)

• jednakost čuva vrijednost predikata: ako za ma koji predikat $P$ vrijedi $P(x)$ i vrijedi $x = y$ tada vrijedi i $P(y)$. Postupak zamjene $x$ na $y$ je supstitucija, stoga kažemo da supstitucija argumenta čuva vrijednost predikata (invarijantnost predikata na supstituciju argumenta).

Npr. pogledajmo slijedeći izraz:

$$(\forall x)(\forall y)(x = y \implies P(x) = P(y))$$

Taj izraz je uvijek istinit, za ma koji predikat $P$ s jednim argumentom: ako u $P$ supstituiramo nešto ili nešto drukčije nazvano ali koje je “jednako” prvom argumentu dobit ćemo istu istinitosnu vrijednost. Govorimo o računu predikata s jednakošću.

Izraz $x \neq y$ je kratica za izraz $\neg(x = y)$.

Izraz $(\exists! x)P(x)$ (postoji točno jedan $x$ takav da je $P(x)$) je kratica za izraz

$$(\exists x)P(x) \wedge (\forall y)(\forall z)((P(y)\wedge P(z))\implies (y = z))$$

To je “logično”, naime u običnom jeziku ovaj izraz kaže: postoji $x$ takav da vrijedi $P(x)$ i ako vidimo bilo koja dva takva onda su oni jednaki. Dakle sve zajedno to znači da postoji točno jedan $x$ takav da vrijedi $P(x)$.

Kvantifikator s tipom

Ponekad kvantifikatori vrijede za varijable nekog tipa. U teoriji skupova možemo tip smatrati kao pripadnost nekom skupu. Npr. ako je $x$ tipa $A$ to je kao da $x\in AA$ gdje je AA skup svih $y$ tipa $A$. Možemo to promatrati i kao imati neko svojstvo $AAA$, tj. da vrijedi $AAA(x)$. Dakle, $AAA(x)$ je vrijednost predikata $AAA$ na varijabli $x$. No, moguće je direktno u kvantifikatoru napisati na koji tip se odnosi. Možda je dobro izbjeći pitanje postojanje skupa svih $z$ tako da vrijedi $AA(z)$ pa jednostavno reći da je $x$ tipa $A$ kao neki posebni sintaktički odnos, recimo $x:A$ ($x$ je tipa $A$). Dakle, neki pišu $\forall_A x$ umjesto $\forall x:A$ ili umjesto $\forall x, AAA(x)$ ili umjesto $\forall x, x\in AA$. Slično pišemo i $\exists_A x$ za $\exists x:A$ (postoji $x$ tipa $A$).

category: zadarmat1