Logika prvog reda ili predikativni račun prvog reda je formalni sistem koji se koristi u matematici, filozofiji, lingvistici i računarstvu. Ovde ćemo izložiti samo osnovni i najformalniji deo nužan kao potpora člancima teorije skupova.
Logika prvog reda
Logika prvog reda ili predikatska logika prvog reda se bazira na:
- objektima,
- svojstvima (unarnim predikatima nad objektima),
- relacijama (n-arnim predikatima nad objektima),
- funkcijama (preslikavanjima objekata na objekte).
Sintaksa logike prvog reda
Iskaz → ProstIskaz
|Iskaz Sveza Iskaz
|Kvantifikator Promenljiva Iskaz
|¬ Rečenica
|(Rečenica)
ProstIskaz → Predikat(Objekt, Objekt, ...)
| Objekt = Objekt
Objekt = Funkcija(Objekt, Objekt, ...)
| Konstanta
| Promenljiva
Sveza → ![{\displaystyle \lor |\land |\Rightarrow |\Leftrightarrow }](https://wikimedia.org/api/rest_v1/media/math/render/svg/18b1b66b7ff4e2b11cc3546c37805b42d923c970)
Kvantifikator →
Konstanta → <tekst> tj. "A" | "1" | "a"
Promenljiva → x | y | z |...
Predikat → otac| brat| poseduje| ...
Funkcija → saberi| predji|...
Objekti su:
konstante: <tekst>, tj. 0, 1, "a", "ababa"
imena funkcija:
tj.
Iskaz je predikat nad jednim ili više objekata. Predikat je neko svojstvo ili relacija među objektima koji može biti istinit ili lažan.
U gornjim primerima
znači da
imaju zajedničkog oca,
da su
braća.
ProstIskaz je predikat primenjen na objekte. Npr.
tj. Pero poseduje auto,
tj, Mujo i Suljo su braća.
Semantika Iskaza i ProstogIskaza je istina ili laž.
Sveze se koriste pri konstrukciji (složenih) Iskaza
tj. Mujo i Suljo su braća, Mujo ima auto a Suljo nema.
Kvantifikatori
Koriste se ako se Iskaz odnosi na kolekciju objekata kako bi se izbeglo brojanje objekata
- Univerzalni kvantifikatorr:
![{\displaystyle \forall x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1a3fa2fb002baecbc5038bd3dd42bab57448b315)
Iskaz je istinit za sve vrednosti promenljive x.
Svi psi su sisari
- Egzistencijalni kvantifikator:
![{\displaystyle \exists x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab833914405cde960b3b9af3feaa9e4fef96ffa9)
Iskaz je istinit za bar jednu vrednost promenljive x.
Marija ima (bar jednu) mačku crne boje
Na ovom svetu postoji bar jedna osoba koja voli pse i mrzi mačke
Upotreba kvantifikatora
- Univerzalni kvantifikator se koristi implikativno
Sve na ovom svetu je čovek i sisar
- Egzistencijalni kvantifikator se koristi vezivno:
Na ovom svetu ima nešto što Jovan ne poseduje ili postoji na ovom svetu pas
Ugneždeni kvantifikatori
- Poredak kvantifikatora istog tipa u iskazu je nevažan
- Poredak kvantifikatora različitog tipa u iskazu je nevažan
Svako voli nekoga, tj. svako ima nekog koga voli
Postoji na ovom svetu neko koga svako voli
Područje ili zona važenja promenljive
- Područje ili zona važenja promenljive je iskaz na koji je kvantifikator primenljiv.
- Promenljiva u logičkom izrazu se vezuje za najbliži kvantifivator unutar iskaza u kome se pojavljuje
Psi postoje i svi su žuti. x u zut(x) je univerzalno kvantificiran.
- U dobro napisanoj formuli sve promenljive moraju biti kvantifikovane:
Ova formula nije dobro napisana
Logička veza među kvantifikatorima
•Logička veza među univerzalnim i egzistencijalnim kvantifikatorom:
![{\displaystyle \forall x\neg \operatorname {voli} (x,bandit)\Leftrightarrow \neg \exists x\operatorname {voli} (x,bandit)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a01b4b9ac3a1822e2cfb8edd6fce1aab313a3583)
•Opšte važeći identiteti:
![{\displaystyle \forall x\neg P\Leftrightarrow \neg \exists xP}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc23a28aafea123aa6ccc391c6e18a6c7cb0e934)
![{\displaystyle \neg \forall xP\Leftrightarrow \exists x\neg P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/20b7bccb5d50285acc7430e95a6172c69cb58c3f)
![{\displaystyle \forall xP\Leftrightarrow \neg \exists x\neg P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71192344846f7b1b0b844993d54f472ac781d118)
![{\displaystyle \exists xP\Leftrightarrow \neg \forall x\neg P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ef59c43e7ad406016e20bd71f47f7dae10cb74d)
![{\displaystyle \forall xP(x)\land Q(x)\Leftrightarrow \forall xP(x)\land \forall xQ(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a2e2a9a0327e054cac5efa3b6574ee85c9a3699a)
Jednakost
- Jednakost se uključuje kao primitivni logički predikat.
- Primeri:
Jovan ima dva psa. Jednakost se koristi ovde da se obezbedi da su
i
različiti, tj. da se isključi interpretacija da
i
mogu biti isti pas
Svaki sin ima oca. Druga sveza
obezbeđuje da svaki sin ima jednog oca.
Logike višeg reda
- U logici prvog reda kvantifikatori su primenljivi samo na objekte.
- U logici drugog reda kvantifikatori su primenljivi samo na predikate i funkcije:
Dva objekta su jednaka ako i samo ako imaju ista svojstva.
Dve funkcije su jednake ako i samo ako imaju iste vrednosti za sve moguće argumente.
- Logika trećeg reda dopušta kvantifikaciju predikata, itd.
Na primer, predikat drugog reda
može biti
tj. binarni predikat
je relacija refleksivnosti.
Literatura
- Raymond M. Smullyan: First-order Logic, Courier Corporation, 1995
- Leigh S. Cauman: First-order Logic: An Introduction, Walter de Gruyter, 1998
Eksterni linkovi
- First order logic (Cornell)
- First order logic (Wolfram MathWorld)