PROPOSITIONAL CALCULUS EXERCISES
10/29/2011
Contents
1. Ten basic rules of inference
2. Derived rules of inference
3. Rules of replacement (equivalence)
4. Conditional proofs (conditional introduction)
5. Indirect proofs (negation introduction)
6. Refutation trees for validity
1. TEN 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)
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)]
ABS
(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?
(1) Example
(A v C) → (B↔ C)
˫ (A v C) → [(B → C) & (C → B)]
ME (↔I)
(2)
(~W v X) & (Y v ~Z)
˫ (W → X) & (Y v ~Z)
(3)
(~J & ~K) → (~J & ~K)
˫ ~(J v K) → (~J & ~K)
(4)
(W & X) v (Y → Z)
˫ (W & X) v (~Z → ~Y)
(5)
A v (~~B & C)
˫ A v (B & C)
(6)
[(C & D) → E] v (D & E)
˫ [C → (D → E)] v (D & E)
(7)
[(A → B) & ~A] v [(A → B) & ~B]
˫ (A → B) & (~A v ~B)
(8)
(W → ~X) & ~(Y & Z)
˫ (W → ~X) & (~Y v ~Z)
(9)
[(A & ~B) & C] & [(D v E) → F]
˫ [A & (~B & C)] & [(D v E) → F]
(10)
[D → (~C → ~A)] v (A → B)
˫ [(D & ~C ) → ~A] v (A → B)
(11)
[W & (~X & ~Y)] & (W & (~X & ~Y)]
˫ [(W & ~X) & ~Y] & [W & (~X & ~Y)]
(12)
[A & (B → C)] v [A & (B → C)]
˫ A & (B → C)
(13)
(A → D) v (B → C)
˫ (~A v D) v (B → C)
(14)
(~A → B) v [(D & ~C) → ~A]
˫ (~A → B) v [D → (~C → ~A)]
(15)
(~A → B) & (C → B)
˫ (~A → B) & (~B → ~C)
(16)
(~X → Y) & (~Z v W)
˫ [(~X → Y) & ~Z] v [(~X → Y) & W]
DIST
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. (~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)
(3)
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
(4)
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)
(5)
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 v (B & C)
7. ~A → (B & C)
8. ~(B → C) → ~~A
9. ˫ ~(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.
(1) Example
1. G → H
2. G & G / ˫ H
3. G [2 SIMP (&E)]
4. ˫ H [1, 3 MP (→E)]
(2)
1. (U v Y) & (U v Z) / ˫ ~~U v Y
(3)
1. ~B → ~A / ˫ ~A v B
(4)
1. (A & B) v (C & D)
2. ~A v ~B / ˫ C & D
(5)
1. X & Y
2. X → (Y → Z) / ˫ Z
(6)
1. J → (H v I)
2. ~H & ~I / ˫ ~J
(7)
1. ~B → ~A
2. A / ˫ B
(8)
1. (A → B) & (C → D)
2. A / ˫ B v D
(9)
1. A v (B & A) / ˫ A v B
(10)
1. X ↔ Y
2. ~(X & Y) / ˫ ~X & ~Y
(11)
1. A → B
2. ~C → ~B / ˫ A → C
(12)
1. (J & K) → L
2. J / ˫ (K → L)
(13)
1. A v (B v C)
2. ~C / ˫ ~(A v B)
(14)
1. (X & Y) → (Z v W)
2. ~(Z v W) / ˫ ~(Y & X)
(15)
1. A
2. B / ˫ (A & B) v C
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. 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]
(2)
1. J
2. J → K / ˫ K & J
(3)
1. Y → Z
2. ~X / ˫ X → Z
(4)
1. X → Y / ˫ ~X v (Y v Z)
(5)
1. (X v X) v Z
2. ~X / ˫ Z
(6)
1. ~G → H
2. I → J
3. G → I / ˫ H v J
(7)
1. ~W
2. ~X / ˫ W ↔ X
(8)
1. ~A v B
2. ~B / ˫ ~(A v B)
(9)
1. ~(~D v E) / ˫ D
(10)
1. X → Y
2. ~Y ˫ ~(X v Y)
4. CONDITIONAL PROOFS (CONDITIONAL INTRODUCTION)
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 [H 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) Example
1. A / ˫ (B → B) v C
2. | B [H for CP (→I)]
3. B → B [2-2 CP (→I)]
4. ˫ (B → B) v C [3 ADD (vI)]
(3)
1. X → Y
2. X → Z / ˫ X → (Y& Z)
3. | X
4. | Y
5. | Z
6. | Y & Z
7. ˫ X → (Y & Z)
(4)
1. B → (C & D) /˫ A → (B → C)
2. | A & B
3. | A
4. | B
5. | C & D
6. | C
7. (A & B) → C
8. ˫ A → (B → C)
(5) 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.
(1) Example
1. A & B / ˫ A → B
2. | A [H for CP (→I)]
3. | B [1 SIMP (&E)]
4. ˫ A → B [2-3 CP (→I)]
(2)
1. X / ˫ (X → Y) → Y
(3)
1. A / ˫ (B → B) v C
(4)
1. A → B
2. C → D / ˫ (A v C ) → (B v D)
5. INDIRECT PROOFS (NEGATION INTRODUCTION)
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 [H for IP (~I)]
3. | S v T [2 ADD (vI)]
4. | ~S [1, 3 MP (→E)]
5. | S & ~S [1, 4 CONJ (&I)]
6. ˫ ~S [2-5 IP (~I)]
(2) 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.
(1)
1. ~(A & B)
2. A / ˫ ~B
3. | B [H for IP (~I)]
6. ˫ ~B [3-5 IP (~I)]
(2)
1. B v B /˫ B
2. | ~B [H for IP (~I)]
5. ˫ B [2-4 IP (~I)]
(3)
1. (~B v D)
2. ~D / ˫ ~B
3. | B [H for IP (~I)]
7. ˫ ~B [3-6 IP (~I)]
6. REFUTATION TREES FOR VALIDITY
Complete the refutation trees below for conjunction. At the end of each path, indicate that the path is closed with an X or open with an !,. Write “valid” or “invalid” in the final line. In brackets, explain your work for each step.
(1) Example
1. A & B / ˫ A
2. ~A [negated conclusion]
Path 1
3. A [from 1]
4. B [from 1]
x [2, 3 conflict]
Valid [path closed]
(2) Construct 1 path.
1. A & B
2. ~A / ˫ B
3. ~ B [negated conclusion]
Path 1
(3) Construct 1 path.
1. A & B
2. A / ˫ ~B
3. B [negated conclusion]
Path 1
Complete the refutation trees below for disjunction.
(1) Example
1. A v B
2. ~A / ˫ B
3. ~B [negated conclusion]
Path 1
4. A [from 1]
x [2, 4 conflict]
Path 2
5. B [from 1]
x [3, 5 conflict]
Valid [paths 1 and 2 closed]
(2) Construct two paths.
1. A v B
2. A / ˫ ~B
3. B [negated conclusion]
Path 1
Complete the refutation trees below for conditional.
(1) Example
1. A → B
2. A / ˫ B
3. ~B [negated conclusion]
4. ~A v B [1, MI]
Path 1
(2) Construct two paths.
1. A → B
2. ~B / ˫ ~A
3. ~A [negated conclusion]
4. ~A v B [1, MI]
Path 1
(3) Construct three paths.
1. A → B
2. B → C
3. A / ˫ C
3. ~C [negated conclusion]
4. ~A v B [1, MI]
5. ~B v C [2, MI]
Path 1
(4) Construct three paths.
1. H → I
2. I → J
3. ~H / ˫ J