SI242: Homework 6

Print this problem set out (there are X problems!) and answer the problems on the given sheet.

Identify the predicates, constants and functions in the following formula: $$\exists x[W(x,foo) \Rightarrow \neg R(foo) \wedge S(g(x))]$$
Let $F_2$ be the formula: $$\forall x,y[ x \neq y \Rightarrow P(f(x,y))]$$ Given the interpretation below, show that this interpretation is a model for formula $F_2$.
- domain: {a,b,c}
- P: P(a) = false, P(b) = true, P(c) = true
- f: The table below defines f(u,v) where u is the row heading and v is the column heading
  
  a b c
  
  a a c b
  
  b c a b
  
  c b c a
Finish the in-class activity and submit as per instructions. Note: you do not have to do #4 of Part 3 (which is the second programming problem). If you did this with a partner, please write down here the name of the partner that submitted the solution. If you did it alone, please write a note to that effect here.

	a	b	c
a	a	c	b
b	c	a	b
c	b	c	a

The following two formulas define the "before" predicate's beahvior: ∀x[~before(x,x)] and ∀x,y,z[before(x,y) & before(y,z) => before(x,z)] Given these, prove before(a,b) => ~before(b,a).

1: ∀x,y,z[before(x,y) & before(y,z) => before(x,z)]       Given

2: ∀x[~before(x,x)]                                       Given

3: ______________________________________________________ specialize x=a, y=b, z=a in 1

4: ______________________________________________________ contrapositive of 3

5: ______________________________________________________ specialize x=a in 2

6: ______________________________________________________ Modus Ponens on 4 and 5

7: ______________________________________________________ De Morgan on 6

8:______________________________________________________ (a=>b) <=> (~a|b) on 7

Give a conversational english version of the first-order logic formula ∀x[∃y[y = father(x)]].
Note: if you write something like "for all x there exists a y such that y equals father of x", you will get no points.
Given ∀x[∃y[y = father(x)]] and vader = father(luke), the following purports to prove vader = father(father(vader)), i.e. that Darth Vader is his own grandfather! Clearly there is a flaw in this proof! For each line that is a valid deduction given the lines above it (even if they may be flawed), label the line with the justification for the proof step. For the one line (yes, there can be only one) that is an invalid deduction step given the lines above it, clearly explain what deduction rule has been missapplied, and how that rule was incorrectly used!
```
	  
1: ∀x[Ey[y = father(x)]]          _______________________________________________________________________



2: vader = father(luke)           _______________________________________________________________________   



3: Ey[y = father(vader)]          _______________________________________________________________________



4: luke = father(vader)           _______________________________________________________________________



5: vader = father(father(vader))  _______________________________________________________________________
	
```
Given ∀x[ innocent(x) => ~∃y[ victimOf(y,x) ] ] and victimOf(bob,alice), prove ~innocent(alice).