Algebraic proof of De Morgan's Theorems

Could someone give me an algebraic proof of De Morgan's Theorems?

I already know the graphic proof with the truth table, but I need to understand the algebraic way.

EDIT

I try to explain better. Imagine to have the two theorems:

NOT(a * b) = NOT(a) + NOT(b) NOT(a + b) = NOT(a) * NOT(b) 

What do you answer to someone that tell you: "Show me why this two theorems are verified without using the truth tables"?

5 Answers

Following, e.g. Wikipedia, let us define a boolean algebra to be a set $A$, together with two binary operations $\land$ and $\lor$, a unary operation $'$, and two nullary operations $0$ and $1$, satisfying the following axioms: $$\begin{align*} a\lor(b\lor c) &= (a\lor b)\lor c, & a\land(b\land c) &= (a\land b)\land c, &&\text{(associativity)}\\ a\lor b &= b\lor a, & a\land b &= b\land a, &&\text{(commutativity)}\\ a\lor(a\land b) &= a, & a\land (a\lor b) &= a, &&\text{(absorption)}\\ a\lor(b\land c) &= (a\lor b)\land (a\lor c), & a\land(b\lor c) &= (a\land b)\lor (a\land c) &&\text{(distributivity)}\\ a\lor a' &= 1, & a\land a' &= 0. &&\text{(complements)} \end{align*}$$

You want to use these axioms to prove that $(a\land b)' = a'\lor b'$ and $(a\lor b)' = a'\land b'$.

Lemma 1. $a\land 1 = a$ and $a\lor 0 = a$ for all $a$.

Proof. $a \land 1 = a\land(a\lor a') = a$, by complements and absorption; likewise, $a\lor 0 = a\lor(a\land a') = a$ by complements and absorption. $\Box$

Lemma 2. $a\land 0 = 0$ and $a\lor 1 = 1$ for all $a$.

Proof. $a\land 0 = a\land (a\land a') = (a\land a)\land a' = a\land a' = 0$. And $a\lor 1 = a\lor(a\lor a') = (a\lor a)\lor a' = a\lor a' = 1$. $\Box$

Lemma 3. If $a\land b' = 0$ and $a\lor b'=1$, then $a=b$.

Proof. $$\begin{align*} b &= b\land 1\\ &= b\land(a\lor b')\\ &= (b\land a)\lor (b\land b')\\ &= (b\land a)\lor 0\\ &= (b\land a)\lor (a\land b')\\ &= (a\land b)\lor(a\land b')\\ &= a\land (b\lor b')\\ &= a\land 1\\ &= a.\ \Box \end{align*}$$

Lemma 4. For all $a$, $(a')' = a$.

Proof. By Lemma 3, it suffices to show that $(a')'\land a' = 0$ and $(a')'\lor a' = 1$. But this follows directly by complementation. $\Box$

Theorem. $(a\land b)' = a'\lor b'$.

By Lemmas 3 and 4, it suffices to show that $(a\land b)\land (a'\lor b') = 0$ and $(a\land b)\lor (a'\lor b') = 1$; for by Lemma 4, this is the same as proving $(a\land b)\land (a'\lor b')'' =0$ and $(a\land b)\lor (a'\lor b')'' = 1$; by Lemma 3, this gives $(a\land b) = (a'\lor b')'$, and applying Lemma 4 again we get $(a\land b)' = (a'\lor b')'' = a'\lor b'$, which is what we want.

We have: $$\begin{align*} (a\land b)\land(a'\lor b') &= \bigl((a\land b)\land a')\bigr) \lor \bigl((a\land b)\land b') &&\text{(by distributivity)}\\ &= \bigl( (a\land a')\land b\bigr) \lor \bigl( a\land (b\land b')\bigr) &&\text{(associativity and commutativity)}\\ &= ( 0\land b) \lor (a\land 0)\\ &= 0 \lor 0\\ &= 0. \end{align*}$$ And $$\begin{align*} (a\land b)\lor(a'\lor b') &= \bigl( (a\land b)\lor a'\bigr) \lor b'&&\text{(by associativity)}\\ &= \bigl( (a\lor a') \land (b\lor a')\bigr) \lor b'&&\text{(by distributivity)}\\ &= \bigl( 1\land (b\lor a')\bigr) \lor b'&&\text{(by complements)}\\ &= (b\lor a')\lor b'&&\text{(by Lemma 1)}\\ &= (b\lor b')\lor a'&&\text{(by commutativity and associativity)}\\ &= 1\lor a'&&\text{(by complements)}\\ &= 1 &&\text{(by Lemma 2)}. \end{align*}$$ Since $(a\land b)\land (a'\lor b') = 0$ and $(a\land b)\lor (a'\lor b') = 1$, the conclusion follows. $\Box$

Theorem. $(a\lor b)' = a'\land b'$.

Proof. Left as an exercise for the interested reader. $\Box$

Let ~ stand for the negation function "NOT", and -> for (material) implication. Then in a natural deduction system (with a rule of negation elimination going "from an assumption which is a negation which leads to a contradiction, we may infer the (sub) well-formed formula which the negation negates) the proofs might run as follows:

1 | ~(a*b) assumption 2 || ~(~a+~b) assumption 3 ||| ~a assumption 4 ||| (~a+~b) 3 + introduction 5 ||| ((~a+~b)*~(~a+~b)) 2, 4 * introduction 6 || a 3-5 ~ elimination 7 ||| ~b assumption 8 ||| (~a+~b) 7 + introduction 9 ||| ((~a+~b)*~(~a+~b)) 2, 8 * introduction 10 || b 7-9 ~ elimination 11 || (a*b) 6, 10 * introduction 12 || ((a*b)*~(a*b)) 1, 11 * introduction 13 | (~a+~b) 2-12 ~ elimination 14 (~(a*b)->(~a+~b)) 1-13 -> introduction 15 | (~a+~b) assumption 16 || (a*b) assumption 17 || a 16 * elimination 18 ||| ~a assumption 19 |||| b assumption 20 |||| (a*~a) 17, 18 * introduction 21 ||| ~b 19-20 ~ introduction 22 || (~a->~b) 18-21 -> introduction 23 ||| ~b assumption 24 || (~b->~b) 23-23 -> introduction 25 || ~b 15, 22, 24 + elimination 26 || b 16 * elimination 27 || (b*~b) 25, 26 * introduction 28 | ~(a*b) 16-27 ~ introduction 29 ((~a+~b)->~(a*b)) 15-28 -> introduction 30 (~(a*b)=(~a+~b)) 14, 29 = introduction 1 | ~(a+b) assumption 2 || a assumption 3 || (a+b) 2 + introduction 4 || ((a+b)*~(a+b)) 1, 3 * introduction 5 | ~a 2-4 ~ introduction 6 || b assumption 7 || (a+b) 6 + introduction 8 || ((a+b)*~(a+b)) 7, 1 * introduction 9 | ~b 6-8 ~ introduction 10 | (~a*~b) 5, 9 * introduction 11 (~(a+b)->(~a*~b)) 1-10 -> introduction 12 | (~a*~b) assumption 13 || (a+b) assumption 14 ||| a assumption 15 || (a->a) 14-14 -> introduction 16 ||| b assumption 17 |||| ~a assumption 18 |||| ~b 12 * elimination 19 |||| (b*~b) 16, 18 * introduction 20 ||| a 17-19 ~ elimination 21 || (b->a) 16-20 -> introduction 22 || a 13, 15, 21 + elimination 23 || ~a 12 * elimination 24 || (a*~a) 22, 23 * introduction 25 | ~(a+b) 13-24 ~ introduction 26 ((~a*~b)->~(a+b)) 12-25 -> introduction 27 (~(a+b)=(~a*~b)) 11, 26 = introduction 

A basic technique used there consists of not inferring a contradiction as soon as one might have the ability to do so, but rather introducing an assumption that one doesn't want to keep around, and then inferring a contradiction to get rid of it. Personally, I'd find this very tricky, if I didn't keep track of scope like I did above.

Note that there exists a metatheorem which states that if a theorem holds in classical propositional calculus, there will also exist a corresponding theorem in all Boolean Algebras. Since the above do consist of proofs in classical propositional calculus, by that metatheorem, they also hold for all Boolean Algebras.

The truth tables are a summary of the underlying algebra; without further specification of what you mean by "the algebraical way" I don't know what you would want other than truth tables. You could split it into cases ("if $A=0$ and $B=0$ then $(A+B)' = 0' = 1 = 1 \cdot 1 = A' \cdot B'$", and so on), but this is exactly what the truth table tells you.

What do you answer to someone who says: "Show me why this two theorems are verified without using the truth tables."?

The simplest possible example that I can think of for the de Morgan laws is:

If you ask:
"When does an $AND$ (or $\land$) statement is not $true$?",
then the answer is:
"If either of the two statements involved is $false$."

The above is described symbolically with: $$\lnot(a \land b) = \lnot a \lor \lnot b $$

Similarly, if you ask:
"When does an $OR$ (or $\lor$) statement is not $true$?",
then the answer is:
"When both of the involved statements are $false$."

Which symbolically is:

$$\lnot(a \lor b) = \lnot a \land \lnot b$$

Thus, the de Morgan laws could be thought of as a criteria for the result of the logical operators $OR$ and $AND$ to be $false$.

More convoluted answer:

Considering:

The statements $\lnot \forall x \in U(p(x))$ and $\exists x \in U(\lnot p(x))$ are equivalent.

The de Morgan laws could be thought of as a reduction of the relationship that negation, $\neg$, gives between "for all", $\forall$, and "there exists", $\exists$, statements, from a potentially infinite many statements about a infinite universe to finite number of statements.

Transferring the problem from the Boolean algebra $(\mathbb Z_2,\neg,\vee,\wedge)$ to the Boolean ring $(\mathbb Z_2,1,+,\cdot)$, where $1$ means TRUE, $+$ means EXCLUSSIVE OR and $\cdot$ means AND and using the equivalences

$\neg a \iff (1+a)$
$a\vee b \iff (a+b+ab)$
$a\wedge b \iff (a\cdot b)$

makes the task very algebraic and rather straightforward.

$\neg(a\wedge b)\iff (1+ab)$
$(\neg a \vee \neg b)\iff ((1+a)+(1+b)+(1+a)(1+b))=a+b+1+a+b+ab=1+ab$ (remember that $x+x=0$)

and

$\neg(a\vee b)\iff (1+(a+b+ab))$
$(\neg a)\wedge\neg b)(1+a)(1+b)=1+a+b+ab$