Q1)

a) Explain what it means for a relation to be symmetric.

b) Explain what it means for a proof system to be complete.

c) Explain what it means for a set of sentences, S, to semantically entail a sentence A.

Q2) Use natural deduction to prove the following arguments:

a) P∧Q, P→R ?Q∧R
b) P∨Q ?(P∨R)∨(Q∨S)
c) P→Q, Q→R, R→S ?P→S
d) ?P→(¬P→P)

Q3) Use tableaux to test whether the following arguments of QL are valid. If they are invalid, give a counter­example.

a) ∃xFx→∀xFx, ∃x¬Fx ?¬∃xFx
b) a=b, Fa↔Gb, ∃xFx ?∃xGx
c) ∀x∃y(Hxy∧Hyx) ?∃xHxx

Q4) Using the translation keys provided, translate the following collections of sentences of English into sentences of QL, then use tableaux to test whether the sentences are jointly consistent. If they are consistent, provide a model that shows this.

a) C(x,y): x causes y
(i) Everything has a cause
(ii) Nothing causes itself

b) Mx: x is a musician
Wx: x is a woman
m: Marshall Mathers
b: Beyonce
e: Eminem

(i) Eminem is Marshall Mathers
(ii) Beyonce is not Eminem
(iii) If Beyonce is not Marshall Mathers then every musician is a woman
(iv) Marshall Mathers is a musician
(v) Eminem is not a woman

c)

Dx: x is a dog
Hx: x is a human
Lxy: x loves y
(i) All dogs are loved
(ii) All humans love something
(iii) Some humans do not love any dogs

Q5) Consider the following model, M:

D: {Luke, Leia, Han, Obi­Wan}
I(s) = Luke
I(l) = Leia
I(h) = Han
I(b) = Obi­Wan

I(o) = Obi­Wan
I(J): {Luke, Obi­Wan}
I(H): {, }
I(L): {, }
I(S): {}

And the following translation scheme:
s: Luke Skywalker
l: Leia Organa
h: Han Solo
b: Ben Kenobi
o: Obi­Wan Kenobi
Jx: x is a Jedi
Hxy: x and y are siblings
Lxy: x loves y
Sx: x is a Sith

Translate the following sentences of English into QL and say whether they are true or false on M. Explain your answer.

a) Ben Kenobi is Obi­Wan Kenobi

b) If Luke and Leia are siblings, then Leia and Luke are siblings

c) Someone is both a Jedi and a Sith

d) Somebody loves someone who is their sibling

e) Han Solo loves only Leia