Algebraic proof of De Morgan's Theorems

Question

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"?

Answer 1

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$

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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$