80-211 Spring 2003

Assignment #10

Due on Friday, April
4^{th}

^{ }

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)