# De Morgan's Theorems

Could someone give me an algebraical demonstration of the De Morgan's Theorems?

I already know the graphic demonstration with the truth table, but I need to understand the algebraical 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"?

-
Have you tried writing down truth tables? –  Neal Jan 2 '12 at 18:07
@Neal: Yes, I write it. –  Overflowh Jan 2 '12 at 18:29
What axioms do you have? It's possible to deduce De Morgan's Laws for a boolean algebra given certain sets of axioms, but you have to specify what axioms you do have and which ones you do not. –  Arturo Magidin Jan 2 '12 at 18:59
@ArturoMagidin: I'm sorry, I don't know this rule. These are the axioms: 1. commutative property. 2.associative property. 3. absorption. 4. distributive property. 5. complements. 6. Existence of neutral elements (I really don't know what this mean :/). 7. Idempotency. 8. Minimum and maximum. If you need, I can write the mathematical formulas that I have on the notes. –  Overflowh Jan 2 '12 at 20:46
@unNaturhal: What "rule" is it you don't know? Simply put: you can't get something out of nothing. In order to deduce things (i.e., in order to prove things) you need *premises*/hypotheses/axioms. Since there are many different ways of describing a boolean algebra, in order to be able to "prove algebraically" a given property, one needs to know what the assumptions/axioms that you are taking for granted are. In some axiomatizations, De Morgan's Laws are included, which would mean that a "proof" would just be "because they are axioms". That's what my comment meant. –  Arturo Magidin Jan 3 '12 at 1:41

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$

-
You are too impressive Arturo... –  Samuel Reid Jan 2 '12 at 19:48
@ArturoMagidin: I made the exercise following your demonstration. This is what I made: image. The comments are in italian, but I think that is clear enough. There's something wrong? –  Overflowh Jan 8 '12 at 16:05
@ArturoMagidin: Another question: the five assiomatic property, don't need a demostration right? Otherwise they would not called axioms. –  Overflowh Jan 8 '12 at 16:31
@unNaturhal: An axiom, in this context, is an assumption. Given a particular set and a particular interpretation of the operations $\land$ and $\lor$, $'$, $0$ and $1$, you would need to prove that the set with those interpretations satisfy the axioms; if you do that, then all the theorems for boolean algebras would automatically hold for the set. –  Arturo Magidin Jan 8 '12 at 22:01
@unNaturhal: I can't really read the image very well, but it looks okay. The argument should be very, very similar to the one I did above. –  Arturo Magidin Jan 8 '12 at 23:41

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.

-
I edited my first post. I hope that now is clear than before :) –  Overflowh Jan 2 '12 at 18:40
Re: your edit - if someone were to ask you to prove the theorem without the use of truth tables, then there's no real way of getting around having to write out the four separate cases $(A,B)=(T,T),(T,F),(F,T),(F,F)$ and show that each equation holds in each case. But this is exactly what a truth table is for! Out of interest, why do you want a proof that doesn't involve truth tables? –  Clive Newstead Jan 2 '12 at 18:57
Because I thought, just like you, that the truth tables were enough to explain the Theorems, but my teacher was not convinced of this... –  Overflowh Jan 2 '12 at 20:38
@CliveNewstead No. In classical propositional calculus, you can prove the theorems without any reference to truth tables, or truth values (or the separate cases). Since there exists a metatheorem which tells us that if a formula (wff) qualifies as a theorem in classical propositional calculus, it will also hold as a theorem in Boolean Algebra, you can prove that such a formula holds in both settings "in one stroke" without any reference to truth values or truth tables. –  Doug Spoonwood Jan 6 '12 at 3:34

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.

-