Valjanost
Valjana formula donekle odgovara pojmu tautologije u iskaznoj logici – formula je valjana ako je tačna u svakoj valuaciji, pri svakoj interpretaciji.
Rečenica je valjana ako je tačna pri svakoj interpretaciji.
Formula koja ima slobodne promenljive je valjana isključivo ako je tačna za svaku valuaciju tih slobodnih promenljivih, odnosno možemo da smatramo da su slobodne promenljive vezane univerzalnim kvantifikatorom ∀.
Rečenica ∀x. x = 0 ∨ ¬(x = 0) je valjana.
Rečenica ¬(∀x. x = 0) ⇔ (∃x. ¬(x = 0)) je valjana.
Primer – paradoks pijanca
Rečenica ∃x.P(x) ⇒ ∀y.P(y) je valjana, za x i y iz istog domena.
Time je interpretacija “postoji čovek takav da ako on pije onda svi piju” tačna. Ako postoji čovek koji ne pije, onda je to taj za kog premisa P(x) nije tačna, pa ni ∀y.P(y) nije tačno jer postoji taj jedan koji ne pije. Sa druge strane, ako svi piju koji god x da uzmemo P(x), levi deo, je tačan a iz tačnog sledi tačno i to je tačno.
Zadovoljivost
Rečenica je zadovoljiva ako postoji interpretacija u kojoj je tačna.
Formula je zadovoljiva ako postoji interpretacija u kojoj je tačna.
Rečenica F je valjana ako je ¬F nezadovoljiva.
Logička ekvivalentnost
Formule F i G su logički ekvivalentne ako svaka interpretacija koja zadovoljava F zadovoljava i G, i obrnuto.
Formule F i G su ekvivalentne ako se razlikuju u
- imenu varijable pod kvantifikatorom
- ∀x.P(x) ≡ ∀y.P(y)
- redosledu kvantifikatora iste vrste
- ∀x∀y.P(x,y) ≡ ∀y∀x.P(x,y) ≡ ∀x,y.P(x,y)
- postojanju ili nepostojanju kvantifikatora varijable koja se ne pojavljuje u domenu formule
- ∀x.P(y) ≡P(y)