PREDICATE CALCULUS IN-CLASS EXERCISES

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

Example

1. ∀x(Fx → Gx)

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

3. Fa & Ha [2 ƎE]

4. Fa → Ga [1 ∀E]

5. Fa [3 &E SIMP]

6. Ga [4, 5 →E MP]

7. Ha & Fa [3 COM]

8. Ha [7 &E SIMP]

9. Ha & Ga [8 &I CONJ]

10. ˫ Ǝx (Hx & Gx) [9 ƎI]

(1)

1. ∀x(Fx →  Gx) / ˫ Ǝx[~Fx v (Gx v Hx)]

2. Fa →  Ga       

3. ~Fa v Ga       

4. (~Fa v Ga) v Ha             

5.  ~Fa v (Ga v Ha)          

6. ˫ Ǝx[~Fx v (Gx v Hx)]       

(2)

1. Ǝx(~Fx)

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

3. ~Fa       

4. ~Ga       

5. ~Fa & ~Ga                 

6. (Fa & Ga) v (~Fa & ~Ga)             

7. Fa ↔ Ga            

8. ˫ Ǝx(Fx ↔ Gx)       

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

Example

1. Fy / ˫ ∀x(Fx)

2. ˫ ∀x(Fx) [1 ∀I (UG)]

(3)

1. ∀x(Fx) / ˫ Fy

2. ˫               

(4)

1. Ǝx(Fx) / ˫ Fa

2. ˫               

(5)

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

2.               

3. ˫                   

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)

2. Fa / ˫ Ga

3. Fa → Ga [1 ∀E]

4. ˫ Ga [3, 2 MP (→E)]

(6)

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

2.                    

3. ˫                    

(7)

1. ∀x (Fx → Gx) / ˫ ∀x(~Gx → ~Fx)

2.                    

3.                    

4. ˫                           

(8)

1. ∀x(Fx → Gx)

2. Fy / ˫ ∀x(Gx)

3.                    

4.                  

5. ˫                    

(9)

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

2.                    

3.                

4. ˫                        

(10)

1. ∀x(Fx → Gx)

2. ∀x(Gx → Hx) / ˫ ∀x(Fx → Hx)

3. Fy → Gy [1 ∀E]

4.               

5.                    

6. ˫                   

(11)

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

2.                 

3.                  

4.              

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

(12)

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

2.                 

3.                  

4. ˫                         

(13)

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

2.           

3.                       

4.                  

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

(14)

1. Ǝx (Fx & Gx)

2. Fa → (Ga → Ha) / ˫ Ǝx (Hx)

3.               

4.                       

5.                  

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

(15)

1. ∀x(~Gx → ~Fx)

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

3. ~Ga → ~Fa [1 ∀E]

4.                  

5.          

6.                  

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

The following examples involve relational 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) / ˫ Fba

2. Ǝy(Fay & Fya) [1 ƎE (EI)]

3. Fab & Fba [2 ƎE (EI)]

4. Fba [3 SIMP (&E)]

(16)

1. ∀x ∀y(Fxy → Fyx)

2. Fab / ˫ Fba

3.                           

4.                      

5. ˫                  

(17)

1. ∀x ∀y (Rxy → Sxy) 

2. ∀x ∀y (Sxy → Txy) / ˫ ∀x ∀y (Rxy → Txy)

3. ∀y (Ruy → Suy) [1 ∀E]

4. Ruz → Suz [3 ∀E]

5.

6.

7.

8. ∀y (Ruy → Tuy) [7 ∀I]

9. ˫ ∀x ∀y (Rxy → Txy)

The following problems involve 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(Fx → Hx)

2. a=b

3. Fa / ˫ Hb

4. Fa → Ha [1 ∀E (UI)]

5. Ha [3, 4 MP (→E)]

6. ˫ Hb [2, 5 ID]

(18)

1. ∀x(Fx → Gx)

2. a=b

3. ~Gb / ˫ ~Fa

4. Fa → Ga [1 ∀E (UI)]

5.

6.

7. ˫

(19)

1. Ǝx(Fx & Gx)

2. a=b / ˫ Ǝx(Gx)

3. Fa & Ga [1 ƎE]

4.

5.

6. ˫

The following problems involve quantifier equivalence rules. 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(Fx → Gx)

2. ∀x(Fx) / ˫ Ǝx(Gx)

3. Fy → Gy [1 ∀E variable form]

4. Fy [2 ∀E variable form]

5. Gy [3, 4 MP (→E)]

6. ∀x(Gx) [5 ∀I variable form]

7. ˫ Ǝx(Gx) [6 QE1]

(20)

1. ∀x(Fx → Hx)

2. ∀x~(Hx) / ˫ ~Ǝx(Fx)

3. Fy → Hy [1 ∀E variable form]

4. ~Hy [2 ∀E variable form]

5. ~Hy → ~Fy [3 TRANS]

6.

7.

8. ˫

(21)

1. ∀x(Fx → Gx)

2. ~∀x~(Fx) / ˫ Ǝx(Gx)

3.

4. Fa [3 ƎE constant form]

5.

6.

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