Generalized De Morgan and distributive laws

Laws for any number of terms

The lesson on semantic consequence and equivalence established the laws of equivalence for two terms: among them, the commutativity and associativity of $\wedge$ and of $\vee$, De Morgan's laws and the two distributivities. Now, a formula in disjunctive normal form is a disjunction of conjunctions, each with as many terms as needed, and transforming a formula into that form requires negating, regrouping and distributing conjunctions and disjunctions of any length. If this is so, the binary laws do not suffice as they stand: they must be extended to $n$ terms, and this must be done once and for all $n$.

For each fixed $n$, the De Morgan law of $n$ terms could be verified with a truth table of $2^n$ rows, written with $n$ variables, and the uniform substitution of the previous lesson, applied to the biconditional between both sides, would extend it to arbitrary formulas. But there are infinitely many values of $n$, and no number of tables exhausts them. It follows that the claim “for every $n$” is not an equivalence between two formulas but a statement about infinitely many equivalences, formulated in the metalanguage; its proof is, like those of the lesson on induction on the natural numbers and on formulas, an external proof, and its instrument is induction on the number of terms. The notation $\bigwedge_{i=1}^{n} \varphi_i$ also belongs to the metalanguage: it is not a new symbol of the language but a name for a string of circles and disks, just as $(\varphi \wedge \psi)$ is.

Three relations that must not be confused should be fixed from the outset. The equality $\alpha = \beta$ says that $\alpha$ and $\beta$ are the same string; definitions, which are written with $:=$, introduce names for strings, and what is obtained by unfolding a definition is equal, not merely equivalent. Semantic equivalence $\alpha \eqsem \beta$ says that $v(\alpha) = v(\beta)$ for every valuation $v$. The provable equivalence $\alpha \dashv\vdash \beta$ of the unit on deduction says that each formula is deducible from the other. This lesson works with the first two; the third appears only in a remark.

What is used

From the lesson on the semantics of propositional logic we take valuations, functions from the variables $v_1, v_2, \ldots$ to $\{0, 1\}$, and their extension to all formulas, which is written with the same letter $v$; the value of the defined connectives, computed from the official abbreviations: $v(\neg\varphi) = 1 - v(\varphi)$, $v((\varphi \wedge \psi)) = v(\varphi)\,v(\psi)$, so that the conjunction has value $1$ if and only if its two components have value $1$, and $v((\varphi \vee \psi)) = 1$ if and only if $v(\varphi) = 1$ or $v(\psi) = 1$; the coincidence lemma (if two valuations agree on the variables of a formula, they agree on the formula); and the formulas $\top$ and $\bot$, a fixed tautology and a fixed contradiction. From the lesson on semantic consequence and equivalence we take that $\eqsem$ is reflexive, symmetric and transitive, the semantic replacement theorem and the catalogue of laws with their names: commutativity, $(\varphi \wedge \psi) \eqsem (\psi \wedge \varphi)$ and $(\varphi \vee \psi) \eqsem (\psi \vee \varphi)$; associativity, $(\varphi \wedge (\psi \wedge \chi)) \eqsem ((\varphi \wedge \psi) \wedge \chi)$ and its analogue for $\vee$; De Morgan, $\neg(\varphi \wedge \psi) \eqsem (\neg\varphi \vee \neg\psi)$ and $\neg(\varphi \vee \psi) \eqsem (\neg\varphi \wedge \neg\psi)$; distributivity, $(\varphi \wedge (\psi \vee \chi)) \eqsem ((\varphi \wedge \psi) \vee (\varphi \wedge \chi))$ and $(\varphi \vee (\psi \wedge \chi)) \eqsem ((\varphi \vee \psi) \wedge (\varphi \vee \chi))$; double negation, $\neg\neg\varphi \eqsem \varphi$; idempotence, $(\varphi \vee \varphi) \eqsem \varphi$; identity, $(\varphi \wedge \top) \eqsem \varphi$; and excluded middle, $\models (\varphi \vee \neg\varphi)$. The laws hold for arbitrary formulas $\varphi$, $\psi$, $\chi$, which are metavariables.

At each step of the proofs that follow, a part of a formula is replaced by an equivalent one. The semantic replacement theorem licenses this for one occurrence at a time; the following lemma, which is a particular case of it, gives it at once for the parts of a negation, a conjunction or a disjunction. It should be noted that this is not a syntactic triviality: $\neg\alpha$ is the string $(\alpha \downarrow \alpha)$, in which $\alpha$ occurs twice, and $(\alpha \wedge \beta)$ therefore contains eight occurrences of $\alpha$ and eight of $\beta$.