II.9
Exercises
Exercises [Slide 42]
Exercise 1.
Why are the following not propositional formulae? There might be more
than one reason
Exercise 2.
As seen in the course notes false,f_{1} ∨ f_{2},f_{1} ⊃ f_{2} and f_{1} ≡ f_{2} are
derived propositional formulae.
Write out ((P ∨ Q) ∧ (Q ⊃ P)) using only ¬and ∧.
Exercise 3.
Give the truth table for the following propositional formulae:
false  (¬P) ∨ (Q ∧ R) 
(¬P) ≡ (Q ∨¬R) 
(¬P) ≡ (Q ⊃ R) 

Exercise 4.
Let σ_{0}(P) = tt and σ_{0}(Q) = tt.
Give the semantics of P ≡ Q, i.e., calculate M⟦P ≡ Q⟧(σ_{0}).
Exercise 5.
Show that for any state σ_{0} and for propositional variables P and Q the
following holds M⟦P ∨ Q⟧(σ_{0}) = (M⟦P⟧(σ_{0}) or M⟦Q⟧(σ_{0})).
Exercise 6.
Let P, Q, and R be propositional variables capturing the following
propositions:
 P: You get a ﬁrst on the ﬁnal exam
 Q: You do every exercise of the course notes
 R: You get a ﬁrst for this module
Write the following as formulae using P, Q, and R and logical connectives.
 You get a ﬁrst for this module, but you do not do every exercise
of the course notes.
 To get a ﬁrst for this module, it is necessary for you to get a ﬁrst
on the ﬁnal exam.
 Getting a ﬁrst on the ﬁnal exam and doing every exercise in the
course notes is suﬃcient for getting a ﬁrst in the module.
Exercise 7.
Determine which of the following formula is satisﬁable or valid. Explain
why.
 false
 false ⊃true
 (P ∧ Q) ≡¬(¬P ∨¬Q)
 (P ∧ (P ∨ Q)) ≡ P
