Introduction to Derivation Rules

(Fill in the blanks) The symbol called the ________ is used in derivations to explicitly indicate that a ________ has been derived.

1. (Pick one) How many lines should be cited for an application of⊥I?

a. one

b. two

c. three

2. How many lines should be cited for an application of¬I?

a. one

b. two

c. three

3. Can negation introduction (¬I) be used to derive any type of formula other than a negation?

a. yes

b. no

4. Can negation elimination (¬E) be used to derive a negation?

a. yes

b. no

Complete each of the following derivations by filling in the missing justification for each line.

(Choose from ⊥I, &I, vIL, vIR, —>I, ¬I, &EL, &ER, vE, —>E, ⊥E, ¬E)

1. J —> (N & M))     Premise

2. (K —> ¬N)            Premise

3. K                            Premise

4. J                             Assumption

5. ¬N                         Goal

6. (N & M)                Goal

7. N                           Goal

8. ⊥                           Goal

9. ¬J                         Goal

5. Justification for Line 5

_____: ______, _______

6. Justification for Line 6

_____: ______, _______

7. Justification for Line 7

_____: ______

8. Justification for Line 8

_____: ______, _______

9. Justification for Line 9

_____: ______

Complete the justification for the given lines.

1. (G —> ¬F)                      Premise
2. (H —>F)                         Premise
3. (¬A —>(G & H))              Premise
4. ¬A                                      Assumption
5. (G & H)                             Goal
6. G                                       Goal
7. H                                       Goal
8. ¬F                                      Goal
9. F                                        Goal
10. ⊥Goal
11. ¬¬A                                  Goal

10. Justification for Line 5

______: ______, _______

11. Justification for Line 6

______: ______

12. Justification for Line 7

______: ______

13. Justification for Line 8

______: ______, _______

14. Justification for Line 9

______: ______, _______

15. Justification for line 10

______: ______, _______

16. Justification for Line 11

______: ______

What are the contradictions that will be candidates for any application of an indirect rule in each of the following derivations? I.e., what candidate contradictions are supplied by the premises?

1. (A v B)                          Premise
2. (C v D)                          Premise
3. (A —>(¬C & ¬D))       Premise

N.B                                     Goal

Which ones are they?

1. A and ¬A
2. B and ¬B
3. C and ¬C
4. D and ¬D
5. (¬C & ¬D) and ¬(¬C & ¬D)

1. (P —> T)                   Premise
2. (¬T —> ¬R)             Premise
3. (¬P —> R)                Premise

n.T                                  Goal

Which ones are they?

1. P and ¬P
2. R and ¬R
3. T and ¬T

Solve The Derivations and include the justifications: (P=Premise, G=Goal)

Problem 1: (14 lines)

1. (P v Q)        P
2. (R v Q)       P
3. ¬Q             P

N. (P & R)         G

Problem 2: (10 lines)

N. ((K —> J) v (J —> K))                  G

Problem 3: (6 lines)

1. ¬¬P                       P
2. (P —> Q)              P

N. Q                            G

Problem 4: (12 lines)

1. (P —> T)               P
2.   (¬T —> ¬R)          P
3.   (¬P —> R)             P

n.T                              G

Problem 5: (8 lines)

N.¬((R —> F) & (R & ¬F))         P

Problem 6: (7 lines)

1. ((P & Q) & ¬R)                        P
2. (¬P & (Q & R))                        P

n.¬Q                                              G

Problem 7: (9 lines)

1. (¬Q & P)                                P
2. (R —> (P —> Q))                 P

n.¬R                                            G

Problem 8: (15 lines)

1. (K v (A & B))                       P
2. (K —> (C v D))                    P
3. ¬C                                           P
4. (D —> B)                               P

n.B                                             G

Problem 9: (20 or 18 lines)

1. ((P & (Q —> R)) —> S)      P

n.(¬P v (Q v S))                         G

Problem 10: (13 lines)

1. ¬¬(Q & R)                           P
2. A                                          P

n.(Q & ¬¬A)                              G