Answer all (five) questions .

1.

Below, x, y represent variable symbols, P represents a unary predicate symbol and Q represents a binary predicate symbol.

(a)  Consider the following strings in Lstring :

) Qxy ) ¬PxPy ) Px

))) Px¬¬QxyPyAxPx

For each of these strings, determine whether or not it is a formula in L. (b)  Convert the following formula of Lmath  to a formula in L:

((Qxy) , ((3y)(Py))) ) (Py) (20 marks)

2.

Below, ↵ , β , γ are taken to be distinct primitive propositions.

(a) For each of the following,  use the semantic tableaux method to determine whether or not the given semantic implication holds. If a semantic implication does not hold, describe every (type of) valuation for which it fails to hold.

(i)  {(↵ , β) ^ (¬γ)}  |= γ ) (↵ ) β)

(ii)  {γ ) (↵ ) β)}  |=  (↵ , β) ^ (¬γ)

(b) Determine, without constructing truth tables or further semantic tableaux, whether or not the following syntactic implication holds:

{(¬γ) ^ (↵ , β) , γ} ` ↵ ) β

Justify your answer; you may quote, without proof, any relevant results from our course. (20 marks)

3.

Below, ↵ , β , γ , 6 are taken to be propositions.

(a)  Give a direct proof of the following:

{↵ ) (β ) (¬γ)) , ↵ ) β} ` ↵ ) (¬γ)

(b) Use the Deduction Theorem for propositional logic to show the following: {↵ ) (¬ (β ) γ)) , (¬6) ) (β ) γ)} ` ↵ ) 6

(c) Determine whether or not the following set of propositions is consistent: {¬(γ ) β) , β} (20 marks)