# proof of Generalized De Morgan's Laws by mathematical induction

Mathematical induction: Prove the following Generalized De Morgan's Laws. $\sim({p_1\land p_2 \land \cdots \land p_n}) \iff \sim{p_1}\lor\sim{p_2}\lor\cdots\lor\sim{p_n}$

My attempt: I'll use mathematical induction for the proof: If p(n) is a statement involving the natural number n such that p(1) is true, and p(k)⇒p(k+1) for any arbitrary natural number k, then p(n) is true for any natural number n.

(1) Let n=1, then the statement is obviously true because it becomes $\sim{p_1}\iff\sim{p_1}$. The first conditioin is satisfied

(2) Let n=k $\sim({p_1 \land p_2 \land \cdots \land p_k})$

I don't know how to further develop this proof from the second condition for the mathematical induction. I know how to prove 1+2+3+...+n= n(n+1)/2 is true for every natural numbers, but the connective $↔$ makes the problem more difficult.

FYI Theorem De Morgan's law of $\sim(p \land q) \equiv ~\sim p ~\lor \sim q$ can be proved, using truth table.

$$\begin{array}{c|c|c|c} \lnot({ p ∧ q }) &\iff&\ \lnot{p} ∨ \lnot{q} \\\hline FTTT& T& FFF\\ TTFF& T& FTT\\ TFFT& T& TTF\\ TFFF& T& TTT \end{array}$$

EDIT: Now I know how to complete the proof

back to (2) Suppose when n=k, p(k) is true. That is, $\sim({p_1\land p_2 \land \cdots \land p_k}) \iff \sim{p_1}\lor\sim{p_2}\lor\cdots\lor\sim{p_k}$

Let p1 ∧p2 ∧⋯∧pk=P, ∼p1 ∨∼p2 ∨⋯∨∼pk=~Q

The truth table for $\sim({P\land p_k+1}) \iff\ \sim Q\lor \sim {p_k+1}$

$$\begin{array}{c|c|c|c} \lnot({ P ∧ p_k+1 }) &\iff&\ \lnot{~Q} ∨ \lnot{pk+1} \\\hline FTTT& T& FFF\\ TTFF& T& FTT\\ TFFT& T& TTF\\ TFFF& T& TTT \end{array}$$

Therefore, $\sim({p_1\land p_2 \land \cdots \land p_n}) \iff \sim{p_1}\lor\sim{p_2}\lor\cdots\lor\sim{p_n}$ for any natural number n.

• @addy 2012 I don't see any "accepted" button. – buzzee Jan 2 '16 at 15:13
• it's a checkmark symbol next to the vote counter? – Adrian Jan 2 '16 at 15:14
• @addy2012 I checked the upwards point(↑)? – buzzee Jan 2 '16 at 15:19
• yes, that checkmark is sth extra. it's below the upvote button :) – Adrian Jan 2 '16 at 15:21
• @addy2012 I clicked the checkmark. – buzzee Jan 2 '16 at 16:39

First $n = 2$

$\lnot (p_1 \lor p_2) \Leftrightarrow (\lnot p_1 \land \lnot p_2)$

Can be easily proven with a truth table.

Assume $\lnot (p_1 \lor p_2 \lor \cdots \lor p_n) \Leftrightarrow (\lnot p_1 \land \lnot p_2 \land \cdots \land \lnot p_n)$ , $\forall n \in \mathbb{N}$

Now $n \rightarrow n+1$

$\lnot (p_1 \lor p_2 \lor \cdots \lor p_n \lor p_{n+1})$

$\Leftrightarrow \lnot ((p_1 \lor p_2 \lor \cdots \lor p_n) \lor p_{n+1})$

Use $n = 2$:

$\Leftrightarrow \lnot(p_1 \lor p_2 \lor \cdots \lor p_n) \land \lnot p_{n+1}$

Use assumption now:

$\Leftrightarrow (\lnot p_1 \land \lnot p_2 \land \cdots \land \lnot p_n) \land \lnot p_{n+1}$

$\Leftrightarrow \lnot p_1 \land \lnot p_2 \land \cdots \land \lnot p_n \land \lnot p_{n+1}$