PROPOSITIONAL CALCULUS IN CLASS EXERCISES

 

10/29/2017

Contents

1. Eight basic rules of inference

2. Derived rules of inference

3. Rules of replacement (equivalence)

4. Exercises using all three sets of rules

5. Hypothetical Rules (conditional and indirect proofs)

 

1. EIGHT BASIC RULES OF INFERENCE

 

What basic rule of inference is used here?

 

(1) Example

~R & S

˫ ~R

SIMP (&E)

 

(2)

~B

˫ ~B v A

       

 

(3)

~H

G

˫ ~H & G

        

 

(4)

~D → C

~D

˫ C

      

 

(5)

Z → ~X

~X → Z

˫ Z↔~X

 

 

(6)

~(B → A) & (~C v D)

˫ ~(B → A)

        

 

(7)

(G v ~H) → (J & ~I)

(G v ~H)

˫ J & ~I

        

 

(8)

(H & I) & (~F v G)

˫ H & I

          

 

(9)

(A v C) & (C → B)

B & D

˫ [(A v C) & (C → B)] & (B & D)

          

 

(10)

A → B

˫ (A → B) v (A → ~B)

       

 

(11)

A v (B & C)

A → (C → D)

(B & C) → (C → D)

˫ C → D

      

 

(12)

C → (A & B)

(A & B) → C

˫ C ↔ (A & B)

      

 

(13)

(A & B) ↔ (A v C)

˫ (A v C) → (A & B)

      

 

Supply the missing rules of inference in the lower premises and final conclusions.

 

(14) Example

1. A [assumption]

2. B → C [assumption]

3. A → B [assumption]

4. B [3, 1 MP (→E)]

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

 

(15)

1. A [assumption]

2. A v B [1, ADD (vI)]

3. A v C             

4. ˫ (A v B) & (A v C)                

 

(16)

1. A [assumption]

2. A → B [assumption]

3. B              

4. ˫ (C & D) v B             

 

(17)

1. A v B [assumption]

2. A → (C & D) [assumption]

3. B → (C & D)  [assumption]

4. C & D                  

5. ˫ D              

 

2. DERIVED RULES OF INFERENCE

 

What derived rule of inference is used below?

 

(1) Example

A → B

~B

˫ ~A

MT

 

(2)

~K → I

I → J

˫ ~K → J

 

 

(3)

B → ~A

˫ B → ( B & ~A)

  

 

(4)

(K → ~J)

(I → H)

K v I

˫ ~J v H

 

 

(5)

~Z v X

~X

˫ ~Z

 

 

(6)

X → ~(W & Y)

˫ X → [X & ~(W & Y)]

  

 

(7)

(K → ~J) → (I → H)

~(I → H)

˫ ~(K → ~J)

 

 

(8)

 (W & Y) → ~Z

X → (W v Y)

(W & Y) v X

˫ ~Z v (W v Y)

 

 

(9)

A → (B & D)

E → (B v F)

A v E

˫ (B & D) v (B v F)

 

 

(10)

(B ↔ A) → ~(A v ~B)

~(A v ~B) → (A → B)

˫ (B↔ A) → (A → B)

 

 

(11)

(A → B) → ~(C → ~D)

~~(C → ~D)

˫ ~(A → B)

 

 

(12)

(X & Z) → Y

˫ (X & Z) → [(X & Z) & Y]

  

 

(13)

[H & (F ↔ ~G)] v (I → D)

~[H & (F ↔ ~G)]

˫ I → D

 

 

(14)

(~A & B) → C

(A & ~B) → D

(~A & B) v (A & ~B)

˫ C v D

 

 

3. RULES OF REPLACEMENT (EQUIVALENCE)

 

What rule of replacement (equivalence) is used below? Hint: some apply to sub-wffs, others apply to the whole line.

 

(1) Example

A ↔ B

˫ (A & B) v (~A & ~B)

ME (↔I)

 

(2) Example

(A v C) → (B↔ C)

˫ (A v C) → [(B → C) & (C → B)]

ME (↔I)

 

(3)

X → Y

˫ ~ X v Y

 

 

(4)

(~W v X) & (Y v ~Z)

˫ (W → X) & (Y v ~Z)

 

 

(5)

X → Y

˫ ~Y → ~X

    

 

(6)

~(X v Y)

˫ ~X & ~Y

 

 

(7)

(~J & ~K) → (~J & ~K)

˫ ~(J v K) → (~J & ~K)

 

 

(8)

(W & X) v (Y → Z)

˫ (W & X) v (~Z → ~Y)

    

 

(9)

~~X

˫ X

 

 

 (10)

A v (~~B & C)

˫ A v (B & C)

 

 

(11)

X → (Y → Z)

˫ (X & Y) → Z

  

 

(12)

A v (B & C)

˫ (A v B) & (A v C)

   

 

(13)

[(C & D) → E] v (D & E)

˫ [C → (D → E)] v (D & E)

  

 

(14)

[(A → B) & ~A] v [(A → B) & ~B]

˫ (A → B) & (~A v ~B)

   

 

(15)

(W → ~X) & ~(Y & Z)

˫ (W → ~X) & (~Y v ~Z)

 

 

(16)

[(A & ~B) & C] & [(D v E) → F]

˫ [A & (~B & C)] & [(D v E) → F]

    

 

(17)

 [D → (~C → ~A)] v (A → B)

˫ [(D & ~C ) → ~A] v (A → B)

  

 

(18)

[W & (~X & ~Y)] & [W & (~X & ~Y)]

˫ [(W & ~X) & ~Y] & [W & (~X & ~Y)]

    

 

(19)

[A & (B → C)] v [A & (B → C)]

˫ A & (B → C)

   

 

(20)

(A → D) v (B → C)

˫ (~A v D) v (B → C)

 

 

(21)

 (~A → B) v [(D & ~C) → ~A]

˫ (~A → B) v [D → (~C → ~A)]

  

 

(22)

(~A → B) & (C → B)

˫ (~A → B) & (~B → ~C)

    

 

(23)

(~X → Y) & (~Z v W)

˫ [(~X → Y) & ~Z] v [(~X → Y) & W]

   

 

4. EXERCISES USING ALL THREE SETS OF RULES

 

State the inference or replacement rule for each line in the proofs below

 

(1) Example

1. (X v ~Y) → Z

2. ~Z / ˫ Y

3. ~(X v ~Y) [1, 2 MT]

4. ~X & ~~Y [3 DM]

5. ~~Y [4 SIMP (&E)]

6. ˫ Y [5 DN]

 

(2)

1. P ↔ (Q v R)

2. R / ˫ P

3. (Q v R) → P            

4. Q v R            

5. ˫ P               

 

(3)

1. (~Q & ~P) → R

2. ~R / ˫ ~P → (~P & Q)

3. ~(~Q & ~P)          

4. ~~Q v ~~P      

5. ~~P v ~~Q       

6. ~~P v Q      

7. ~P → Q      

8. ˫ ~P → (~P & Q)       

 

(4)

1. (A & ~B) → (C v D)

2. ~C

3. ~D / ˫ ~A v B

4. ~C & ~D                

5. ~(C v D)      

6. ~(A & ~B)         

7. ~A v ~~B      

8. ˫ ~A v B    

 

(5)

1. A

2. B / ˫ ~B → (~B & C)

3. A & B                

4. (A & B) v (A & C)            

5. A & (B v C)        

6. B v C             

7. ~B → C      

8. ˫ ~B → (~B & C)       

 

(6)

1. A / ˫ ~(B → C) → A

2. A v B            

3. A v C            

4. (A v B) & (A v C)                

5. A v (B & C)        

6. ~A → (B & C)      

7. ~(B & C) → ~~A         

8. ˫ ~(B & C) → A      

 

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

 

(7) Example

1. G → H

2. G & G / ˫ H

3. G [2 SIMP (&E)]

4. ˫ H [1, 3 MP (→E)]

 

(8)

1. (U v Y) & (U v Z) / ˫ ~~(U v Y)

2.                   

3. ˫                

 

(9)

1. ~B → ~A / ˫ ~A v B

2.               

3. ˫             

 

(10)

1. (A & B) v (C & D)

2. ~A v ~B / ˫ C & D

3.               

4. ˫               

 

(11)

1. X & Y

2. X → (Y → Z) / ˫ Z

3.                   

4. ˫                

 

(12)

1. J → (H v I)

2. ~H & ~I / ˫ ~J

3.               

4. ˫            

 

(13)

1. ~B → ~A

2. A / ˫ B

3.               

4. ˫                

 

(14)

1. ~G → H

2. I → J

3. G → I / ˫ H v J

4.             

5. ˫                  

 

(15)

1. (A → B)

2. (C → D)

3. A / ˫ B v D

4.                  

5. ˫                  

 

(16)

1. A v (B & A) / ˫ A v B

2.                          

3. ˫                   

 

(17)

1. X ↔ Y

2. ~(X & Y) / ˫ ~X & ~Y

3.                          

4. ˫                 

 

(18)

1. A → B

2. ~C → ~B / ˫ A → C

3.               

4. ˫               

 

(19) For this problem only, solve without using simplification.

1. X

2. X → Y / ˫ X & Y

3.                   

4. ˫                   

 

(20)

1. (J & K) → L

2. J / ˫ K → L

3.                   

4. ˫                      

 

(21)

1. A v (B v C)

2. ~C / ˫ A v B

3.                     

4. ˫               

 

(22)

1. (X & Y) → (Z v W)

2. ~(Z v W) / ˫ ~(Y & X)

3.                  

4. ˫                

 

(23)

1. A

2. B / ˫ (A & B) v C

3.                      

4. ˫                        

 

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.

 

(24) Example

1. B

2. C / ˫ (A v B) & (A v C)

3. B & C [1, 2 CONJ (&I)]

4. A v (B & C) [4 ADD (vI)]

5. ˫ (A v B) & (A v C) [5 DIST]

 

(25) For this problem only, solve without using absorption.

1. ~~J

2. J → K / ˫ K & J

3.                

4.                      

5. ˫              

 

(26)

1. Y → Z

2. ~X / ˫ X → Z

3.                   

4.            

5. ˫               

 

(27)

1. X → Y / ˫ ~X v (Y v Z)

2.             

3.                         

4. ˫                      

 

(28) Solve using theorem introduction (i.e., invent a tautology).

1. (X v X) v Z

2. ~X / ˫ Z

3.                

4.               

5. ˫           

 

(29)

1. ~W

2. ~X / ˫ W ↔ X

3.                        

4.                                

5. ˫                 

 

(30)

1. ~C / ˫ C → (C & D)

2.                   

3.            

4. ˫                   

 

(31)

1. ~A v B

2. ~B / ˫ ~(A v B)

3.            

4.                        

5. ˫               

 

(32)

1. ~(~D v E) / ˫ D

2.               

3.                 

4. ˫        

 

(33)

1. X → Y

2. ~Y ˫ ~(X v Y)

3.            

4.                        

5. ˫               

 

5. HYPOTHETICAL RULES: CONDITIONAL AND INDIRECT PROOFS

 

State the rules of inference and replacement used in the following conditional proofs (conditional introduction)

 

(1) Example

1. R → S / ˫ R → (S v T)

2. | R [Hypothesis for CP (→I)]

3. | S [1, 2 MP (→E)]

4. | S v T [3 ADD (vI)]

5. ˫ R → (S v T) [2-4 CP (→I)]

 

(2)

1. X → Y

2. X → Z / ˫ X → (Y& Z)

3. | X                        

4. | Y              

5. | Z         

6. | Y & Z                 

7. ˫ X → (Y & Z)             

 

(3)

1. A / ˫ (B → B) v C

2. | B                        

3. | B      

4. B → B             

5. ˫ (B → B) v C            

 

(4)

1. B → (C & D) /˫ A → (B → C)

2. | A & B                        

3. | B             

4. | C & D              

5. | C             

6. (A & B) → C             

7. ˫ A → (B → C)       

 

(5) For this problem only, prove without using HS.

1. A & B

2. B → (D → E)

3. A → (E →C) /˫ D → C

4. A           

5. B           

6. D → E              

7. E → C              

8.   | D                        

9.   | E              

10. | C              

11. ˫ D → C              

 

Adding three statements to the premises will produce a formal conditional proof (conditional introduction). Supply these statements and indicate the rules of inference and replacement used.

 

(6) Example

1. A & B / ˫ A → B

2. | A [Hypothesis for CP (→I)]

3. | B [1 SIMP (&E)]

4. ˫ A → B [2-3 CP (→I)]

 

(7)

1. A v B / ˫ ~A → B

2. |                           

3. |           

4. ˫                    

 

(8)

1. P → Q / ˫ (Q → R) → (P → R)

2. |                              

3. |               

4. ˫                               

 

(9)

1. A → B

2. C → D / ˫ (A v C ) → (B v D)

3. |                              

4. |                  

5. ˫                                

 

(10)

1. X / ˫ (X → Y) → Y

2. |                              

3. |                

4. ˫                         

 

(11)

1. X → Y / ˫ (Y → X) → (X ↔ Y)

2. |                              

3. |               

4. ˫                               

 

(12)

1. A / ˫ B → B

2. |                          

3. |         

4. ˫                   

 

(13)

1. (W & X) → Y

2. (X & Y) → Z / ˫ (W & X) → Z

3. |                              

4. |                

5. |               

6. | X & Y [4, 5 CONJ (&I)]

7. | Z [MP [2, 6 MP (→E)]

8. ˫ (W & X) → Z [3-7 CP (→I)]

 

State the rules of inference and replacement used in the following indirect proofs (negation introduction)

 

(1) Example

1. (S v T) → ~S /˫ ~S

2. | S [Hypothesis for IP (~I)]

3. | S v T [2 ADD (vI)]

4. | ~S [1, 3 MP (→E)]

5. | S & ~S [2, 4 CONJ (&I)]

6. ˫ ~S [2-5 IP (~I)]

 

(2) For this problem only, prove without using CD.

1. A v E

2. A ↔ E /˫ A & E

3. E → A      

4. | ~A                        

5. | ~E         

6. | E         

7. | E & ~E                

8. A             

9. A → E      

10. E              

11.˫ A & E                 

 

Adding two or three statements to the following will produce a formal indirect proof (negation introduction). Supply these statements and indicate the rules of inference and replacement used.

 

 

(3)

1. B v B / ˫ B

2. | ~B [Hypothesis for IP (~I)]

3. |           

4. |                       

5. ˫ B [2-4 IP (~I)]

 

(4)

1. ~(A & B)

2. A / ˫ ~B

3. | B [Hypothesis for IP (~I)]

4. |                      

5. |                                   

6. ˫ ~B [3-5 IP (~I)]

 

(5) For this problem only, prove without using Theorem Introduction (TI).

1. A / ˫ B v ~B

2. | ~(B v ~B) [Hypothesis for IP (~I)]

3. |               

4. |             

5. ˫ B v ~B [2-4 IP (~I)]

 

(6) For this problem only, prove without using DS (vE).

1. ~B v D

2. ~D / ˫ ~B

3. B → D [1 MI]

4. | B [Hypothesis for IP (~I)]

5. |                  

6. |                       

7. ˫ ~B [3-6 IP (~I)]

 

(7)

1. (A & B) v A / ˫ A

2. | ~A [Hypothesis for IP (~I)]

3. |               

4. |               

5. |                        

6. ˫ A [2-5 IP (~I)]

 

(8)

1. Y → ~(Y v Z) / ˫ ~Y

2. | Y [Hypothesis for IP (~I)]

3. | ~(Y v Z) [1, 2 MP (→E)

4. |               

5. |                

6. |                       

7. ˫ ~Y [2-6 IP (~I)]

 

(9)

1. ~B v A

2. ~(A v C) / ˫ ~B

3. | B [Hypothesis for IP (~I)]

4. |           

5. |              

6. |                 

7. | A & ~A [4, 6 CONJ (&I)]

8. ˫ ~B [3-8 IP (~I)]

 

 

(10)

1. B → (C & D)

2. ~D / ˫ ~B

3. | B [Hypothesis for IP (~I)]

4. |                    

5. |               

6. |                       

7. ˫ ~B [3-6 IP (~I)]