80-211                                                                                                             Spring 2003

Assignment #10

Due on Friday, April 4th

Note: This assignment is divided into two sections; the first section has some problems on material covered since the last assignment and the second section, which is a review meant to help you study for the exam.  The first section will be graded as usual, where as the second section you will receive all 4 points if you make a reasonable effort to do all the problems. You won?t be able to redo the second section.

Section 1 (6 pts):

Problem 1: Show that the sentences below are not semantically  equivalent.  Give a brief explanation why.

\$xFx & \$xGx, \$x(Fx & Gx)

Problem 2:  Establish that the following sequents are invalid by constructing an appropriate interpretation.  Give a brief explanation why as above.

(a) "x(Fx→Gx), "x(Hx→Gx) "xGx

(a)    "x(Bx→Cx), \$xBx "xCx

(b)    "x\$yRxy "x"yRxy

Problem 3:  Read in the text pages 159-167. Do problem 1(e) and 3(a) on page 168 of your text.

Section 2 (4 pts):

Problem 1: Define what it means to be semantically true and semantically false in predicate logic. Also state what it means for two sentences to be semantically equivalent.

Problem 2: Do problems (p), (o), (t), (w) on page 103 of your text.

Problem 3: Prove the following sequents using the four quantifier rules and primitive or derived rules of the propositional calculus.

(a)  "x(Fx ↔ Gx) ├ "xFx ↔ "xGx

(b)  "x(Fx→~Gx) ├ ~\$x(Fx & Gx)

(c)  "x(Fx v Hx→Gx & Kx), ~"x(Kx & Gx) ├ \$x~Hx

(d)  "x(~Gx v ~Hx), "x((Jx→Fx)→Hx) ├ ~\$x(Fx & Gx)

(e)  "x(\$yFyx→"zFxz) ├ "y"x(Fyx→Fxy)

Problem 4:  Prove the following sequents using the any primitive or derived rules for propositional/predicate logic.

(a) "x(Fx→Gx) ├ \$xFx→\$xGx

(b)  "xFx → "xGx ├ \$x(Fx → Gx)

(c)  ├ ~"x(Fx↔Gx) v (\$xFx ↔ \$xGx)