1. Short answer
(a) Explain what syntax and semantics mean in this class, and then explain how they differ. (8 marks)
(b) How did we define the syntax for Boolean logic (or propositional logic)? What about semantics? (Explain all of the important points in those definitions) (8 marks)
(c) Would you say that Hilbert proofs are syntactical or semantical? Explain why. (4 marks)
Q2 (20 points)
Suppose vv is a state and pp is a propositional variable with v(p)=tv(p)=t. Show by induction on formulas that for any wff AA, we have v(A)=v(A[p:=⊤])v(A)=v(A[p:=⊤]).
Q3 (15 points)
Let Γ={(p→(q∨r)),((¬q)→s),((s∧p)→r)}Γ={(p→(q∨r)),((¬q)→s),((s∧p)→r)} and A=(r→q)A=(r→q).
Does Γ⊨tautAΓ⊨tautA? Explain why or why not.
Q4 (15 points)
Give a Hilbert proof to show that ((p≡q)≡r)⊢(q≡(r≡p))((p≡q)≡r)⊢(q≡(r≡p)).
*Your proof must be a Hilbert proof according to the definition, you cannot use any shortcuts that we learned in class.
Q5 (15 points)
For each of the following wffs, determine whether or not it is a logical axiom in the Hilbert proof system. Explain why or why not.
1) ⊤⊤ (5 marks)
2) ¬(p→q)≡((p→q)≡⊥)¬(p→q)≡((p→q)≡⊥) (5 marks)
3) ¬(p→q)≡((¬p∨q)≡q)¬(p→q)≡((¬p∨q)≡q) (5 marks)
Let us define a concept of BFWFFBFWFF (bracket-free well-formed formula) as follows. The symbols are the same as in propositional logic (propositional variables, logical connectives), except that there are no brackets and no constants (⊤⊤ and ⊥⊥).
BFWFFBFWFF is the smallest set of strings in these symbols so that:
(i) Every propositional variable is in BFWFFBFWFF;
(ii) If AA is in BFWFFBFWFF, so is ¬A¬A;
(iii) If A,BA,B are in BFWFFBFWFF, so is ∘AB∘AB, where ∘∘ is one of the following symbols: ∨,∧,→,≡∨,∧,→,≡.
Write a string in BFWFFBFWFF which uses 10-15 symbols. Explain why it is in BFWFFBFWFF.
