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.

  • $\begingroup$ @addy 2012 I don't see any "accepted" button. $\endgroup$ – buzzee Jan 2 '16 at 15:13
  • $\begingroup$ it's a checkmark symbol next to the vote counter? $\endgroup$ – Adrian Jan 2 '16 at 15:14
  • $\begingroup$ @addy2012 I checked the upwards point(↑)? $\endgroup$ – buzzee Jan 2 '16 at 15:19
  • $\begingroup$ yes, that checkmark is sth extra. it's below the upvote button :) $\endgroup$ – Adrian Jan 2 '16 at 15:21
  • $\begingroup$ @addy2012 I clicked the checkmark. $\endgroup$ – 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}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.