Logika prvog reda

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 uredi

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 uredi

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 →  
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 uredi

Koriste se ako se Iskaz odnosi na kolekciju objekata kako bi se izbeglo brojanje objekata

  • Univerzalni kvantifikatorr:  

Iskaz je istinit za sve vrednosti promenljive x.

  Svi psi su sisari
  • Egzistencijalni kvantifikator:  

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 uredi

  • 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 uredi

  • 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 uredi

  • 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 uredi

•Logička veza među univerzalnim i egzistencijalnim kvantifikatorom:

 
 

•Opšte važeći identiteti:

 
 
 
 
 
 

Jednakost uredi

  • 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 uredi

  • 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 uredi

  • Raymond M. Smullyan: First-order Logic, Courier Corporation, 1995
  • Leigh S. Cauman: First-order Logic: An Introduction, Walter de Gruyter, 1998

Eksterni linkovi uredi