PROPOSITIONAL CALCULUS EXERCISES FOR HOMEWORK

10/29/2015

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

Contents

1. Ten basic rules of inference

2. Derived rules of inference

3. Rules of replacement (equivalence)

4. Exercises using all three sets of rules

5. Conditional proofs (conditional introduction)

6. Indirect proofs (negation introduction)

1. TEN BASIC RULES OF INFERENCE

What basic rule of inference is used here?

(1) Example

~Q

˫ ~Q v P

(2)

~C & D

˫ ~C

(3)

~S → R

~S

˫ R

(4)

~X

W

˫ ~X & W

(5)

~(Q → P) & (~R v S)

˫ ~(Q → P)

(6)

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

(W v ~X)

˫ Z & ~Y

(7)

Z → ~H

~H → Z

˫ Z↔~H

(8)

(P v R) & (R → Q)

Q & S

˫ [(P v R) & (R → Q)] & (Q & S)

(9)

P → Q

˫ (P → Q) v (P → ~Q)

(10)

(X &I) & (~U v W)

˫ X &I

(11)

P v (Q & R)

P → (R → S)

(Q & R) → (R → S)

˫ R → S

(12)

(P & Q) ↔ (P v R)

(P v R) → (P & Q)

(13)

R → (P & Q)

(P & Q) → R

R ↔ (P & Q)

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

(1) Example

1. P [assumption]

2. P → Q [assumption]

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

4. ˫ (R & S) v Q [3, ADD (vI)]

(2)

1. P [assumption]

2. Q → R [assumption]

3. P → Q [assumption]

4. Q

5. ˫ R

(3)

1. P [assumption]

2. P v Q [1, ADD (vI)]

3. P v R

4. ˫ (P v Q) & (P v R)

(4)

1. P v Q [assumption]

2. P → (R & S) [assumption]

3. Q → (R & S)  [assumption]

4. R & S

5. ˫ S

2. DERIVED RULES OF INFERENCE

What derived rule of inference is used below?

(1) Example

~M → Y

Y → Z

˫ ~M → Z

HS

(2)

P → Q

~Q

˫ ~P

(3)

(M → ~Z)

(Y → X)

M v Y

˫ ~Z v X

(4)

Q → ~P

˫ Q → ( Q & ~P)

(5)

H → ~(G & I)

˫ H → [H & ~(G & I)]

(6)

~Z v H

~H

˫ ~Z

(7)

(G & I) → ~Z

H → (G v I)

(G & I) v H

˫ ~Z v (G v I)

(8)

(M → ~Z) → (Y → X)

~(Y → X)

˫ ~(M → ~Z)

(9)

(Q ↔ P) → ~(P v ~Q)

~(P v ~Q) → (P → Q)

˫ (Q↔ P) → (P → Q)

(10)

(~P & Q) → R

(P & ~Q) → S

(~P & Q) v (P & ~Q)

˫ R v S

(11)

(P → Q) → ~(R → ~S)

~~(R → ~S)

˫ ~(P → Q)

(12)

(H & Z) → I

˫ (H & Z) → [(H & Z) & I]

(13)

P → (Q & S)

T → (Q v U)

P v T

˫ (Q & S) v (Q v U)

(14)

[X & (U ↔ ~W)] v (Y → S)

~[X & (U ↔ ~W)]

˫ Y → S

3. RULES OF REPLACEMENT (EQUIVALENCE)

What rule of replacement (equivalence) is used below?

(1) Example

X ↔ Y

˫ (X & Y) v (~X & ~Y)

ME (↔I)

(2) Example

(P v R) → (Q↔ R)

˫ (P v R) → [(Q → R) & (R → Q)]

ME (↔I)

(3)

A → B

˫ ~ A v B

(4)

A → B

˫ ~B → ~A

(5)

~(A v B)

˫ ~A & ~B

(6)

A → (B → C)

˫ (A & B) → C

(7)

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

˫ (G → H) & (I v ~Z)

(8)

X v (Y & Z)

˫ (X v Y) & (X v Z)

(9)

(~Z & ~M) → (~Z & ~M)

˫ ~(Z v M) → (~Z & ~M)

(10)

(G & H) v (I → Z)

˫ (G & H) v (~Z → ~I)

(11)

~~A

˫ A

(12)

P v (~~Q & R)

˫ P v (Q & R)

(13)

[(P → Q) & ~P] v [(P → Q) & ~Q]

˫ (P → Q) & (~P v ~Q)

(14)

(G → ~H) & ~(I & Z)

˫ (G → ~H) & (~I v ~Z)

(15)

(~P → Q) & (R → Q)

˫ (~P → Q) & (~Q → ~R)

(16)

[(R & S) →E] v (S &E)

˫ [R → (S →E)] v (S &E)

(17)

[S → (~R → ~P)] v (P → Q)

˫ [(S & ~R ) → ~P] v (P → Q)

(18)

[P & (Q → R)] v [P & (Q → R)]

˫ P & (Q → R)

(19)

[(P & ~Q) & R] & [(S v T) → U]

˫ [P & (~Q & R)] & [(S v T) → U]

(20)

(P → S) v (Q → R)

˫ (~P v S) v (Q → R)

(21)

[G & (~H & ~I)] & [G & (~H & ~I)]

˫ [(G & ~H) & ~I] & [G & (~H & ~I)]

(22)

(~P → Q) v [(S & ~R) → ~P]

˫ (~P → Q) v [S → (~R → ~P)]

(23)

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

˫ [(~H → I) & ~Z] v [(~H → I) & G]

4. EXERCISES USING ALL THREE SETS OF RULES

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

(1) Example

1. (P & ~Q) → (R v S)

2. ~R

3. ~S / ˫ ~P v Q

4. ~R & ~S [2, 3 CONJ (&I)]

5. ~(R v S) [4 DM]

6. ~(P & ~Q) [1, 5 MT]

7. ~P v ~~Q [6 DM]

8. ˫ ~P v Q [7 DN]

(2)

1. A ↔ (B v C)

2. B / ˫ A

3. (B v C) → A

4. B v C

5. ˫ A

(3)

1. (H v ~I) → Z

2. ~Z / ˫ I

3. ~(H v ~I)

4. ~H & ~~I

5. ~~I

6. ˫ I

(4)

1. (~B & ~A) → C

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

3. ~(~B & ~A)

4. ~~B v ~~A

5. ~~A v ~~B

6. ~~A v B

7. ~A → B

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

(5)

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

2. P v Q

3. P v R

4. (P v Q) & (P v R)

5. P v (Q & R)

6. ~~P v (Q & R)

7. ~P → (Q & R)

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

9. ˫ ~(Q & R) → P

(6)

1. P

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

3. P & Q

4. (P & Q) v (P & R)

5. P & (Q v R)

6. Q v R

7. ~Q → R

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

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.

(1) Example

1. (P & Q) v (R & S)

2. ~P v ~Q / ˫ R & S

3. ~(P & Q) [2 DM]

4. ˫ R & S [1, 3 DS]

(2)

1. (F v I) & (F v Z) / ˫ ~~(F v I)

2.

3. ˫

(3)

1. W → X

2. W & W / ˫ X

3.

4. ˫

(4)

1. ~Q → ~P / ˫ ~P v Q

2.

3. ˫

(5)

1. Z → (X v Y)

2. ~X & ~Y / ˫ ~Z

3.

4. ˫

(6)

1. P → Q

2. ~R → ~Q / ˫ P → R

3.

4. ˫

(7)

1. ~Q → ~P

2. P / ˫ Q

3.

4. ˫

(8)

1. (P → Q)

2. (R → S)

3. P / ˫ Q v S

4.

5. ˫

(9)

1. H & I

2. H → (I → Z) / ˫ Z

3.

4. ˫

(10)

1. P v (Q & P) / ˫ P v Q

2.

3. ˫

(11)

1. H ↔ I

2. ~(H & I) / ˫ ~H & ~I

3.

4. ˫

(12)

1. (Z & M) → N

2. Z / ˫ (M → N)

3.

4. ˫

(13)

1. (H & I) → (Z v G)

2. ~(Z v G) / ˫ ~(I & H)

3.

4. ˫

(14)

1. P v (Q v R)

2. ~R / ˫ P v Q

3.

4. ˫

(15)

1. P

2. Q / ˫ (P & Q) v R

3.

4. ˫

(16) Solve without using simplification.

1. A

2. A → B / ˫ A & B

3.

4. ˫

(17)

1. ~G → H

2. I → J

3. G → I / ˫ H v J

4.

5. ˫

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.

(1) Example

1. Z

2. Z → M / ˫ M & Z

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

4. Z & M [1, 3 CONJ (&I)]

5. ˫ M & Z [4 COM]

(2)

1. I → Z

2. ~H / ˫ H → Z

3.

4.

5. ˫

(3)

1. Q

2. R / ˫ (P v Q) & (P v R)

3.

4.

5. ˫

(4)

1. H → I / ˫ ~H v (I v Z)

2.

3.

4. ˫

(5)

1. (H v H) v Z

2. ~H / ˫ Z

3.

4.

5. ˫

(6)

1. ~G

2. ~H / ˫ G ↔ H

3.

4.

5. ˫

(7)

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

2.

3.

4. ˫

(8)

1. ~P v Q

2. ~Q / ˫ ~(P v Q)

3.

4.

5. ˫

(9)

1. H → I

2. ~I / ˫ ~(H v I)

3.

4.

5. ˫

(10)

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

2.

3.

4. ˫

5. CONDITIONAL PROOFS (CONDITIONAL INTRODUCTION)

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

(1) Example

1. H → I

2. H → Z / ˫ H → (I& Z)

3. | H [Hypothesis for CP (→I)]

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

5. | Z [2, 3 MP]

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

7. ˫ H → (I & Z) [3-6 CP (→I)]

(2)

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

2. | Q

3. | Q

4. Q → Q

5. ˫ (Q → Q) v R

(3)

1. C → D / ˫ C → (D v E)

2. | C

3. | D

4. | D v E

5. ˫ C → (D v E)

(4)

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

2. | P & Q

3. | Q

4. | R & S

5. | R

6. (P & Q) → R

7. ˫ P → (Q → R)

(5) prove without using HS

1. P & Q

2. Q → (S →T)

3. P → (T →R) /˫ S → R

4. P

5. Q

6. S →T

7. T → R

8.   | S

9.   | T

10. | R

11.˫ S → R

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.

(1) Example

1. H / ˫ (H → I) → I

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

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

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

(2)

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

2. |

3. |

4. ˫

(3)

1. P & Q / ˫ P → Q

2. |

3. |

4. ˫

(4)

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

2. |

3. |

4. ˫

(5)

1. X / ˫ Y → Y

2. |

3. |

4. ˫

(6)

1. X v Y / ˫ ~X → Y

2. |

3. |

4. ˫

(7)

1. P → Q

2. R → S / ˫ (P v R ) → (Q v S)

3. |

4. |

5. ˫

(8)

1. (G & H) → I

2. (H & I) → Z / (G & H) → Z

3. |

4. |

5. |

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

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

8. ˫ (G & H) → Z [3-7 CP (→I)]

6. INDIRECT PROOFS (NEGATION INTRODUCTION)

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

(1) Example

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

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

3. | D v E [2 ADD (vI)]

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

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

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

(2) Prove without using CD.

1. P v T

2. P ↔ T /˫ P & T

3. T → P

4. | ~P

5. | ~T

6. | T

7. | T & ~T

8. P

9. P →T

10. T

11.˫ P & T

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.

(1)

1. ~(P & Q)

2. P / ˫ ~Q

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

4. |

5. |

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

(2)

1. Q v Q /˫ Q

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

3. |

4. |

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

(3) Prove without using DS (vE).

1. ~Q v S

2. ~S / ˫ ~Q

3. Q → S [1 MI]

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

5. |

6. |

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

(4) Prove without using Theorem Introduction (TI)

1. P / ˫ Q v ~Q

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

3. |

4. |

5. ˫ Q v ~Q [3-4 IP (~I)]

(5)

1. (P & Q) v P / ˫ P

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

3. |

4. |

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

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

(6)

1. W → (Y & Z)

2. ~Z / ˫ ~W

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

4. |

5. |

6. |

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

(7)

1. ~T v S

2. ~(S v U) / ˫ ~T

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

4. |

5. |

6. |

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

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

(8)

1. A → ~(A v B) / ˫ ~Y

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

3. | ~(A v B) [1, 2 MP (→E)

4. |

5. |

6. |

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