Exercise 1.  

Why are the following not propositional formulae? There might be more than one reason

• P¬Q
• P ∧⊃ Q
• P¬∨ (Q ⊃)

Exercise 2.  

As seen in the course notes   false,f₁ ∨ f₂,f₁ ⊃ f₂ and f₁ ≡ f₂ 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 σ₀(P) = tt and σ₀(Q) = tt.

Give the semantics of P ≡ Q, i.e., calculate M⟦P ≡ Q⟧(σ₀).

Exercise 5.  

Show that for any state σ₀ and for propositional variables P and Q the following holds M⟦P ∨ Q⟧(σ₀) = (M⟦P⟧(σ₀) or M⟦Q⟧(σ₀)).

Exercise 6.  

Let P, Q, and R be propositional variables capturing the following propositions:

• P: You get a first on the final exam
• Q: You do every exercise of the course notes
• R: You get a first for this module

Write the following as formulae using P, Q, and R and logical connectives.

• You get a first for this module, but you do not do every exercise of the course notes.
• To get a first for this module, it is necessary for you to get a first on the final exam.
• Getting a first on the final exam and doing every exercise in the course notes is sufficient for getting a first in the module.

Exercise 7.  

Determine which of the following formula is satisfiable or valid. Explain why.

• false
• false ⊃true
• (P ∧ Q) ≡¬(¬P ∨¬Q)
• (P ∧ (P ∨ Q)) ≡ P