PREDICATE CALCULUS EXERCISES FOR HOMEWORK

****please print out this homework sheet and write answers directly onto it***

State the rules of inference and replacement used in the following proofs:

Example

1. x (Fx → Gx)

2. x (Fx → Hx) / ˫ x [Fx → Gx & Hx)]

3. Fx → Gx [1 E (UI)]

4. Fx → Hx [2 E (UI)]

5. ~Fx v Gx [3 MI]

6. ~Fx v Hx [4 MI]

7. (~Os v Gx) & (~Fx v Hx) [5, 6 CONJ]

8. ~ Fx v (Gx & Hx) [7 DIST]

9. Fx → (Gx & Hx) [8 MI]

10. ˫ x [Fx → Gx & Hx)] [9 I (UG)]

(1)

1. x (Fx → Gx)

2. x (Fx v ~Gx) / ˫ x (Fx ↔ Gx)

3. Fy → Gy

4. Fy v ~Gy

5. ~Gy v Fy

6. Gy → Fy

7. Fy ↔ Gy

8. ˫ x (Fx ↔ Gx)

(2)

1. Ǝx[Fx > (Gx & Hx)]

2. Ǝy(~Gx) / ˫ Ǝx (~Fz)

3. Fa > (Ga & Ha)

4. ~Ga

5. ~Ga v ~ Ha

6. ~(Ga & Ha)

7. ~Fa

8. ˫ Ǝx (~Fx)

Adding one or two statements to the premises will produce a formal proof of validity. Supply the statement and indicate the rule:

Example

1. Ǝx(Fx) / ˫ Fa

2. ˫ Fa [1 ƎE (EI)]

(3)

1. Fa / ˫ Ǝx(Fx)

2. ˫

(4)

1. x(Fx) / ˫ Ǝx(Fx)

2.

3. ˫

(5)

1. x(Fx) / ˫ Fy

2. ˫

Adding two or three statements to the premises will produce a formal proof of validity. Supply these statements and indicate the rules of inference and replacement used:

Example

1. x (Fx → Gx) / ˫  ~Ga → ~Fa

2. Fa → Ga [1 E (UI)]

3. ˫ ~Ga → ~Fa [2 TRANS]

(6)

1. x(Fx → Gx)

2. Fa / ˫ Ga

3.

4. ˫

(7)

1. x (Fx & Gx) / ˫ x(Fx)

2.

3.

4. ˫

(8)

1. x(Fx → Gx)

2. ~Gy / ˫ x(~Fx)

3.

4.

5. ˫

(9)

1. x~(Fx & Gx) / ˫ x(~Fx v ~Gx)

2. ~(Fy & Gy)

3.

4. ˫

(10)

1. x(Fx → Gx)

2. Fx / ˫ Ǝx(Gx v Hx)

3.

4.

5.

5. ˫ Ǝx(Gx v Hx) [5 ƎI (EG)]

(11)

1. Ǝx(Gx & Hx) / ˫ Ǝx[(Fx v Gx) & (Fx v Hx)]

2.

3.

4.

5. ˫ Ǝx[(Fx v Gx) & (Fx v Hx)] [4 ƎI (EG)]

(12)

1. Ǝx(~Hx)

2. Fa → (Ga → Ha) / ˫ Ǝx~(Fx & Gx)

3.

4.

5.

6. ˫ Ǝx~(Fx & Gx) [5 ƎI (EG)]

(13)

1. x(~Fx v Gx) / ˫ Ǝx(~Gx → ~Fx)

2.

3.

4.

5. ˫ Ǝx(~Gx → ~Fx) [4 ƎI (EG)]

(14)

1. Ǝx(Fx → Gx)

2. Ǝx(Fy → Gy)

3. Fa v Fb / ˫ Ǝx(Gx v Gy)

4.

5.

6.

7. ˫

(15)

1. Ǝx(Fx → Gx)

2. Ex(Fx & Hx) / ˫ Ǝx(Gx)

3.

4.

5.

6.

7. ˫ Ǝx(Gx) [6 ƎI (EG)]

The following examples involve relational and identity predicates. Adding three statements to the premises will produce a formal proof of validity. Supply these statements and indicate the rules of inference and replacement used.

Example

1. x y(Fxy → Fyx)

2. Fab / ˫ Fba

3. y (Fay → Fya) [1 E (UI)]

4. Fab → Fba [3 E (UI)]

5. ˫ Fba [4, 2 MP (→E)]

(16)

1. Ǝx Ǝy(~Fxy & ~Fyx) / ˫ ~(Fab v Fba)

2.

3.

4. ˫

(17)

1. Ǝx(Fx → Gx)

2. ~Ga

3. a=b / ˫ ~Fb

4.

5.

6. ˫