1. KOLOKVIJ MATEMATIČKA LOGIKA

20. STUDENOG 2007.

(1)

(a) Definirajte sljedeće pojmove: • konkatenacija

• formula logike sudova

• relacija logičke posljedice

• disjunktivna normalna forma

• konzistentan skup formula

(b) Iskažite sljedeće tvrdnje: • teorem o normalnim formama

• teorem o adekvatnosti sistema RS

• teorem dedukcije za RS

• jaki teorem potpunosti za RS

• o relaciji logičke posljedice koja je ekvivalentna s teoremom kompaktnosti

(2) Nađite (ako postoji) savršenu konjunktivnu normalnu formu za

formulu

(P ∨ Q) ↔ (Q → ¬P) .

(3) Pomoću glavnog testa ispitajte je li formula

((¬P → Q) ∧ (R ↔ Q)) → R

valjana.

(4) Za formulu F logike sudova kažemo da je pozitivna ako se u njoj od logičkih veznikâ javljaju jedino ∧ i ∨. Dokažite (indukcijom po složenosti) da je svaka pozitivna formula ispunjiva i oboriva.

(5) Neka je S skup formula logike sudova. Dokažite: S je oboriv skup ako i samo ako je svaki konačan podskup od S oboriv.