Name: ______________________________

Section: _____________________________

The exam consists of 16 questions. Point values vary as indicated, but total 100. Show all work, either on this exam, or in a blue book, or both. This exam must be turned in with your blue book.

Part One: Definitions. (5 problems x 5 points each = 25 points)

Give a one sentence definition of the following terms.

1. Justification

 A justification is a citation at the end of a line of a proof which cites the rule and lines that were used to derive the line.

2. Tautology

 A tautology is a statement that is always true; it is also a statement that is provable from no premises.

3. Accessible line

 A line is accessible at a point in a proof if it is not within a subproof that has been closed at that point.

4. Main operator

 The operator that is responsible for the form of a statement, and builds that statement from the largest components in the statement.

5. Justified Step

A justified step is any line in a proof other than a premise. 

Part Two: Short Answer. (2 problems x 6 points each = 12 points)

6. Explain the difference(s) between a rule of inference and a replacement rule.

Rules of inference go from one or more given lines to a new line that is jointly implied by the given lines. Rules of replacement go from one statement to an equivalent statement. Because of this, inference rules can only be used on entire lines, while replacement rules can be used on components of lines. Also, inference rules work only on one direction (from the required statements to teh new statement), while replacement rules work in two directions (from statement form 1 to form 2, or from form 2 to 1). 

7. Explain the principle behind indirect proof.

The principle behind indirect proof is that if the negation of some statement is false, then that statement itself must be true. So, indirect proof works by showing that the negation of the desired statement must be false by demonstrating that one can derive a contradiction from it, and so it must be false.

Part Three: Proofs. (9 proofs x 7 points each = 63 points) 

8. (use any inference or replacement rules, but not CP or IP)

01. ~C -> ~B
02. A
03. A -> B / .: C

04. B 2, 3 MP
05. C 4, 1 MT

9. (use any inference or replacement rules, but not CP or IP)

1. Q
2. G -> ~Q
3. (~G v X) -> (~Q v H) / .: H

04. ~G 1, 2 MT
05. ~G v X 4 Add
06. ~Q v H 3, 5 MP
07. H 1, 6 DS

10. (use any inference or replacement rules, but not CP or IP)

1. ~(A v L)
2. P v Q
3. Q -> (R & A)
4. P -> (K v L) / .: K

05. ~A & ~L 1 DeM
06. ~A 5 simp
07. ~R v ~A 6 Add
08. ~(R & A) 7 DeM
09. ~Q 8, 3 MT
10. P 9, 2 DS
11. K v L 4, 10 MP
12. ~L 5 simp
13. K 11, 12 DS

11. (use any inference or replacement rules, and you must use IP)

1. (N v S) -> (L & ~M)
2. ~L v M / .: ~N

03. |-> N AIP
04. | N v S 3 add
05. | L & ~M 4, 1 MP
06. | L 5 simp
07. | ~M 5 simp
08. | M 2, 6 DS
09. |_ M & ~M 7, 8 conj
10. ~N 3-9 IP

12. (use any inference or replacement rules, and you must use CP)

1. ~E -> (F & G)
2. H -> ~G / .: H -> E

03. |-> H ACP
04. | ~G 2, 3 MP
05. | ~F v ~G 4 add
06. | ~(F & G) 5 DeM
07. |__ E 6, 1 MT
08. H -> E 3-7 CP

13. (use any rules or methods)

1. B -> (K & M)
2. (B & M) -> (P <-> ~P) / .: ~B

03. |-> B AIP
04. | K & M 3, 1 MP
05. | M 4 simp
06. | B & M 3, 5 conj
07. | P <-> ~P 6, 2 MP
08. | (P -> ~P) & (~P -> P) 7 BE
09. | (~P v ~P) & (P v P) 8 CE (x2)
10. |__ ~P & P 9 dupl (x2)
11. ~B

14. (use any rules or methods)

1. Z & ~Q
2. K -> {W -> (~Z & O)} / .: K -> (~W & ~Q)

03. |-> K ACP
04. | Z 1 simp
05. | Z v ~O 4 add
06. | ~(~Z & O) 5 DeM
07. | W -> (~Z & O) 2, 3 MP
08. | ~W 6, 7 MT
09. | ~Q 1 simp
10. |__ ~W & ~Q 8, 9 conj
11. K -> (~W & ~Q) 3-10 CP

15. (use any rules or methods)

/ .: {Z -> (X v Y)} -> {~X -> (~Y -> ~Z)}

01. |-> Z -> (X v Y) ACP
02. | ~(X v Y) -> ~Z 1 contrap
03. | (~X & ~Y) -> ~Z 2 DeM
04. |__ ~X -> (~Y -> ~Z) 3 exp
05. {Z -> (X v Y)} -> {~X -> (~Y -> ~Z)}

16. (use any rules or methods)

/ .: (P -> Q) v (Q -> P)

01. |-> ~{(P -> Q) v (Q -> P)} AIP
02. | ~(P -> Q) & ~(Q -> P) 1 DeM
03. | ~(~P v Q) & ~(~Q v P) 2 CE (x2)
04. | (P & ~Q) & (Q & ~P) 3 DeM (x2)
05. | P & ~Q 4 simp
06. | Q & ~P 4 simp
07. | Q 6 simp
08. | ~Q 5 simp
09. |__ Q & ~Q 7, 8 conj
10. (P -> Q) v (Q -> P) 1-9 IP