1

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.

buzzee
  • 1,530

1 Answers1

4

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}$

adjan
  • 5,741