Algebra of statements

Every simplification in this chapter, from here on, is really just a chain of substitutions drawn from one fixed list of standard equivalences — the 'algebra of statements'. Each law in the list can itself be confirmed with a truth table exactly the way the results of §1.4.1 were, so none of it is new magic; it is simply given a name so that a long simplification can be written as a sequence of small, checkable, and citable steps instead of one big table. A handful of these names are already familiar from ordinary algebra — Idempotent, Commutative, Associative, Distributive — because logic's $∧$ and $∨$ behave, in many respects, like multiplication and addition; the remaining names (De Morgan's, Identity, Complement, Absorption, Conditional, Biconditional) are specific to statements and were mostly proved earlier in this chapter.

A quick word on the less obvious rows: the Identity law says $t$ and $c$ act like the '1' and '0' of this algebra — anding with $t$ or oring with $c$ changes nothing, while anding with $c$ collapses everything to $c$ and oring with $t$ inflates everything to $t$. The Complement law says a statement and its own negation can never both hold ($p ∧ ~p ≡ c$) and can never both fail ($p ∨ ~p ≡ t$) — this is what makes $c$ and $t$ reachable at all. The Absorption law says that $∨$-ing or $∧$-ing a statement with a larger expression that already contains it changes nothing. The Conditional and Biconditional rows are simply the results proved in §1.4.1, restated here so the whole toolkit is in one place.

The next three worked examples show how a chain of these laws — never a truth table — can negate a statement, remove an 'if…then', or prove an equivalence outright, naming the exact law used at each step. The rule for reading such a chain is strict: a line is valid only if it is obtained from the line above it by applying exactly the named law (or an earlier proved result) to some part of that line, nothing more.

Ex.1 — negate each statement, naming the law used at every step.

i) $~[(p ∨ q) ∧ (q ∨ ~r)]$. The outer connective is $∧$, so the outer De Morgan's law applies first, then it is applied again to break open each of the two resulting negated brackets:

≡ $~(p ∨ q) ∨ ~(q ∨ ~r)$ [De Morgan's law, outer]

≡ $(~p ∧ ~q) ∨ (~q ∧ r)$ [De Morgan's law, applied inside each bracket; note $~(~r) = r$]

≡ $(~q ∧ ~p) ∨ (~q ∧ r)$ [Commutative law, to bring the shared term $~q$ to the front of both conjuncts]

≡ $~q ∧ (~p ∨ r)$ [Distributive law, factoring $~q$ back out of both conjuncts]

So the negation is $~q ∧ (~p ∨ r)$.

ii) $~[(p → q) ∨ r]$. Here the outer connective is again $∨$, so De Morgan's law applies once outside, and the leftover $~(p → q)$ is then rewritten using the negation-of-implication result already established in §1.3.3, not a fresh law:

≡ $~(p → q) ∧ ~r$ [De Morgan's law]

≡ $(p ∧ ~q) ∧ ~r$ [negation of implication, §1.3.3: $~(p→q) ≡ p ∧ ~q$]

So the negation is $(p ∧ ~q) ∧ ~r$.

iii) $~[p ∧ (q ∨ r)]$. The outer connective is $∧$, so De Morgan's law applies outside, and then again to the inner $~(q ∨ r)$:

≡ $~p ∨ ~(q ∨ r)$ [De Morgan's law]

≡ $~p ∨ (~q ∧ ~r)$ [De Morgan's law]

So the negation is $~p ∨ (~q ∧ ~r)$.

iv) $~[(~p ∧ q) ∨ (p ∧ ~q)]$. Once more the outer connective is $∨$, so De Morgan's law splits it, and then De Morgan's law is applied to each of the two resulting negated conjunctions, cancelling the double negations $~(~p)=p$ and $~(~q)=q$ along the way:

≡ $~(~p ∧ q) ∧ ~(p ∧ ~q)$ [De Morgan's law]

≡ $(p ∨ ~q) ∧ (~p ∨ q)$ [De Morgan's law, using $~(~p)=p$ and $~(~q)=q$]

So the negation is $(p ∨ ~q) ∧ (~p ∨ q)$.

v) $~[(p ∧ q) → (~p ∨ r)]$. This is an implication being negated, so the negation-of-implication result applies first (turning $~(A → B)$ into $A ∧ ~B$), then De Morgan's law breaks open the remaining negated bracket, then the four resulting conjuncts are reordered and finally collapsed:

≡ $(p ∧ q) ∧ ~(~p ∨ r)$ [negation of implication]

≡ $(p ∧ q) ∧ (p ∧ ~r)$ [De Morgan's law, using $~(~p)=p$]

≡ $q ∧ p ∧ p ∧ ~r$ [Commutative and Associative laws together — commuting the first bracket's two letters and dropping all the brackets — to line up the repeated $p$]

≡ $q ∧ p ∧ ~r$ [Idempotent law, collapsing $p ∧ p$ to $p$]

So the negation is $q ∧ p ∧ ~r$.

Ex.2 — rewrite without using 'if…then', by the Conditional law $p → q ≡ ~p ∨ q$. Since the Conditional law says an implication is nothing but 'not the front, or the back', every 'if…then' sentence converts directly:

i) 'If prices increase then the wages rise' is $p → q$ with p: 'prices increase', q: 'the wages rise'; by the Conditional law this becomes 'prices do not increase or the wages rise'.

ii) 'If it is cold then we wear woollen clothes' is $p → q$ with p: 'it is cold', q: 'we wear woollen clothes'; by the Conditional law this becomes 'it is not cold or we wear woollen clothes'.

Ex.3 — prove each equivalence without a truth table, by a law chain.

i) $p ↔ q ≡ ~(p ∧ ~q) ∧ ~(q ∧ ~p)$. Starting from the Biconditional law's definition and rewriting each implication by the Conditional law, then pushing the negation back in by De Morgan's law, reaches the right-hand side directly:

$p ↔ q ≡ (p → q) ∧ (q → p)$ [Biconditional law]

≡ $(~p ∨ q) ∧ (~q ∨ p)$ [Conditional law, applied to each implication]

≡ $~(p ∧ ~q) ∧ ~(q ∧ ~p)$ [De Morgan's law, applied to each disjunction; note $~p ∨ q ≡ ~(p ∧ ~q)$ and $~q ∨ p ≡ ~(q ∧ ~p)$] …