Simplification, Conjunction and Addition (Simp, Conj, Add)

Three short rules handle $\land$ and $\lor$ directly. They look almost too simple, but proofs are full of them. They join the rules from Hypothetical and Disjunctive Syllogism (HS, DS).

Simplification, conjunction and addition.
Rule	From	Infer
Simp (simplification)	$p \land q$	$p$ (or $q$)
Conj (conjunction)	$p$ and $q$	$p \land q$
Add (addition)	$p$	$p \lor q$ (or $q \lor p$), for any $q$

Key idea

Simp takes one conjunct out of a conjunction. Conj joins two lines with $\land$. Add joins anything at all to a line with $\lor$. Simp and Add cite one line; Conj cites two.

Why it works

If $p \land q$ is true, both parts are true, so either one may be written alone (Simp). If $p$ and $q$ are each true, their conjunction is true (Conj). Addition is the surprising one: if $p$ is true, then $p \lor q$ is true whatever $q$ is, because a disjunction needs only one true part. Adding does lose information, but it never takes you from truth to falsehood, and that is all a rule needs.

All three rules in one proof.

Worked examples

Worked example: Simplification

From $(p \to q) \land \neg r$, what can Simp give?

The line is a conjunction.
Either conjunct may be written alone.

Answer: $p \to q$ or $\neg r$.

Worked example: Conjunction

From line 2, $\neg p$, and line 5, $q \lor r$, what does Conj give?

Join the two lines with $\land$, in the order you choose.

Answer: $\neg p \land (q \lor r)$ (justified "Conj 2, 5").

Worked example: Addition

You have $s$ and the conclusion is $s \lor (t \to u)$. How do you finish?

The conclusion is a disjunction whose first disjunct is $s$.
Add may attach any formula with $\lor$.

Answer: Write $s \lor (t \to u)$ by Add from the line $s$.

Common mistake

Applying Simp to a disjunction: from $p \lor q$ inferring $p$. A disjunction can be true with $p$ false, so nothing can be "simplified" out of it. Simp works only on a whole line whose main connective is $\land$. The opposite worry, that Add feels like cheating, is unfounded: Add is valid, since $p \lor q$ is true in every row where $p$ is.

Simp: whole line is $A \land B$ → write $A$ or $B$.
Conj: two lines $A$, $B$ → write $A \land B$.
Add: one line $A$ → write $A$ $\lor$ anything you like.

These rules are also how you take a conjunction apart and put a new one together. A premise like $p \land (q \to r)$ is two premises in one: Simp gives you $p$ and $q \to r$ as separate lines, and then the other rules can use them. At the end, Conj puts the pieces of a conjunctive conclusion back together.

Watch for Add whenever the conclusion contains a letter that appears in no premise: only Add can introduce something new.

Simplification, Conjunction and Addition (Simp, Conj, Add)

Worked examples

Practice

Builds on

Leads to

Sources and further reading