Logički deo jezika prvog reda (sintakse, zapisivanja) čine:
- prebrojiv skup promenljivih (isto kao u iskaznoj logici, p,q,r,s,...)
- veznici (isto kao u iskaznoj logici): ne, i, ili, sledi, ekvivalentno ¬, ∧, ∨, ⇒, ⇔
- kvantifikatori: svi, neki ∀, ∃
- logičke konstante: tačno, netačno T, ⊥
- pomoćni simboli: { } ( )
Opštije gledano, imamo sledeće:
- simboli konstanti
- funkcijski simboli
- relacijski (predikatski) simboli
Svaki simbol ima pridruženu arnost – broj argumenata na koje se simbol primenjuje. f(x) ima arnost 1, jer se primenjuje na jedan argument. zbir(x,y) ima arnost 2.
Simboli konstanti mogu da se tretiraju kao funkcijski simboli arnosti 0. Npr. konstantu 2 možemo da tretiramo i kao funkciju 2() koja uvek kao rezultat vraća vrednost 2.
Atomični iskazi (iskazna slova) se mogu shvatiti kao relacijski simboli arnosti 0. Npr. iskazno slovo p možemo da tretiramo kao funkciju p() koja vraća vrednost tog iskaznog slova – zamislite to kao vrednost promenljive, ili getter metod.
Neki funkcijski ili relacijski simboli arnosti 2 obično se pišu infiksno, npr. umesto +(3,2) pišemo 3+2
Programski jezici u kojima ne postoje promenljive
Tretiranje simbola konstanti i iskaznih slova kao funkcija arnosti 0 je jako interesantan koncept jer nam omogućava kreiranje programskih jezika u kojima ne postoje promenljive. Ovo je jedna od osnova funkcionalnih programskih jezika i videćemo kasnije kako Haskell to koristi i kakve zgodne prednosti to može da ima.
Sintaksu logike prvog reda definišemo u nekoliko faza:
- termovi
- atomičke formule
- formule
Termovi
Termovi označavaju objekte nekog domena, dok formule imaju istinitosne vrednosti (tačno,netačno).
Promenljive i konstante su termovi.
Ako su t1,…,tk termovi a f funkcijski simbol, onda je i f(t1,…,tk) takođe term.
Atomičke formule
Atomičke formule se grade primenom relacijskih simbola na termove.
Logičke konstante T i ⊥ su atomičke formule.
Iskazno slovo je atomička formula
Ako je p relacijski simbol jezika a t1,…,tk termovi onda je p(t1,…,tk) atomička formula.
Primeri atomičkih formula
0<1 2+x x=3
paran(3) 4|f(x)
izmedju(A,B,C) podudarno(A,B,A1,B1)
p(x*0, 0)
Formule
Formule se grade od atomičkih formula primenom logičkih veznika i kvantifikatora.
Atomičke formule su formule (trivijalan slučaj)
Ako je A formula onda je i ¬(A) formula
Ako su A i B formule onda su i (A)∧(B), (A)∨(B), (A) ⇒ (B), (A) ⇔ (B) formule
Ako je A formula, x promenljiva, onda su i ∀x.(A), ∃x.(A) formule