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. Fa / ˫ Ǝ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. ˫