1. KOLOKVIJ MATEMATIČKA LOGIKA

20. STUDENOG 2007.

(1)

(a) Definirajte sljedeće pojmove: • podriječ

• logički ekvivalentne formule

• valjana formula

• savršena konjunktivna normalna forma

• potpun skup formula

(b) Iskažite sljedeće tvrdnje: • Craigova interpolaciona lema

• dva svojstva konzistentnih skupova

• generalizirani teorem potpunosti za logiku sudova • teorem kompaktnosti

• Lindenbaumova lema

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

formulu

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

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

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

ispunjiva.

(4) Ako je K interpretacija, sa S_{K} označimo skup svih formula F takvih da je K(F) = 1. Dokažite: ako su I i J interpretacije za koje je S_{I} ⊆ S_{J}, tada je I = J.

(5) Neka je S skup formula logike sudova, i F neka njegova logička posljedica. Dokažite da postoji konačan skup T ⊆ S takav da vrijedi T ⊧ F.