3. (a)
(b)
(c)
YOUR NAME and STUDENT NUMBER
(2 marks) Give a recursive definition of the set SP of propositional formulas that can formed using the ternary predicate P : {T, F}3 ¡ú {T, F} and the propositional variable X.
Solution:
(8 marks) Let M : {T, F}3 ¡ú {T, F} be the ternary predicate that is true when 0 or 1 of its arguments are true and is false when 2 or 3 of its arguments are true.
Use structural induction to prove that every formula in SM is logically equivalent to X or is logically equivalent to NOT(X).
Solution:
(8 marks) Let N : {T, F}3 ¡ú {T, F} be the ternary predicate that is true when 0 of its arguments are true and is false when at least 1 of its arguments is true.
Prove that every unary predicate U : {T, F} ¡ú {T, F} is logically equivalent to some formula in SN .
CSC240 Winter 2021 Midterm Assessment Question 3
Solution:
1