1

Prove that $P \to Q, \neg Q ⊢ \neg P$ . We know that this is complete as $P \to Q, \neg Q ⊨ \neg P$ .

1. 2. 3. P \to Q \neg Q P \to \neg Q data data subcomputation 3.1 3.2 P \neg Q data from (2.) \underline{P} 4. \neg P from (1.), (3.), and (\neg I)

2

Prove that $P \to Q ⊢ \neg (P \land \neg Q)$ .

1. 2. P \to Q (P \land \neg Q) \to Q data ? 2.2 2.3 P Q from (2.1) and (\land E) from (2.2) and (\to E) \underline{Q} 2.1 P \land \neg Q data 3. 4. (P \land \neg Q) \to \neg Q \neg (P \land \neg Q) ? from (2.), (3.), (\neg I)

Sound and complete:

P \to Q P \to Q \neg (P \land \neg Q) \equiv \neg (P \land \neg Q) ⊨ \neg (P \land \neg Q) ⊨ P \to Q

Prove that $P \to Q, R \to Q, P \lor R, Q \to S ⊢ S$ .

1. 2. 3. 4. 5. 6. P \to Q R \to Q P \lor R Q \to S Q S data data data data from (1.), (2.), (3.), and (\lor E) from (4.), (5.), and (\to E)

Prove that $P \to Q, \neg (Q \land \neg R), P ⊢ R$ .

1. 2. 3. 4. P \to Q \nrg (Q \land \neg R) \neg R \to \neg (Q \land \neg R) \neg R \to Q \land \neg R data data from (2.) and (\to I 2) subcomputation 5.1 5.2 \neg R Q data from (1.), (2.), and \underline{Q \land \neg R}

Prove that $⊢ P \lor \neg P$ .

Prove that $(P \to Q) \to Q, Q \to P ⊢ P$ .

Prove that $A \to B ⊢ \neg A \lor B$ .