final exam riview

Rebecca Horner  12 May 2015 

        Final Exam Review Questions: Spring 2016  

   

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 

       

   

Rebecca Horner  12 May 2015 

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  

Rebecca Horner  12 May 2015 

I(o) = Obi­Wan   

I(J): {Luke, Obi­Wan}  I(H): {<Luke, Leia>, <Leia, Luke>}   I(L): {<Luke, Leia>, <Han, Leia>}   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