How to use natural deduction to prove a statement.

Question

Prove the following statement using natural deduction rules (such as conjunction elimination, implication introduction, etc.)

[(p ∧ q) ∨ (p ∧ r)] ⊢ [p ∧ (q ∨ r)]

Answer 1

Without providing the answer itself, let me offer some general advice for natural deduction proofs. Then if you have additional questions, feel free to reach out to me.

With every natural deduction proof, you’ll have a set of (one or more) premises and a conclusion that you’re trying to derive from those premises. You’ll also have a set of rules you can use (like those you’ve mentioned in your original post). Each rule is typically written as a “schema”—in other words, it’s written in a general form that says anytime you’ve got a premise (or set of premises) with a certain form, you’re permitted to infer (or “derive”) a line with another kind of form. For example, the rule of conjunction elimination says that anytime you’ve got a line in your proof that has a conjunction as its main operator, you’re permitted to infer one of the conjuncts on a new line.

With all of this in mind, the best starting point is to review your rules and then look at the main operators of the premises in the proof you’re working on. In this case, it looks like the main operator is a disjunction, so you might start by looking at rules that deal with disjunctions.

Hope that helps! If you’ve already gotten this far and could use some additional help, feel free to reach out. I’m happy to discuss strategies for natural deduction proofs in more depth.