3
$\begingroup$

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

  • 0
    Have you tried writing down truth tables?2012-01-02
  • 0
    @Neal: Yes, I write it.2012-01-02
  • 5
    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.2012-01-02
  • 1
    @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.2012-01-02
  • 0
    @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.2012-01-03
  • 0
    @ArturoMagidin: Understood. I had not consider that was necessary to provide axioms or hypotheses to prove something, sorry. I was not following the mathematical way to do things, and this is a serious error I know. This because these things are part of the exam _Foundations of Computer Science_ in which aren't used strict rules to describe mathematical concepts (and this is a great lack in my opinion) so, when is necessary to prove a Theorem, some people (like me in this case) don't know what to do. Expecially when the handouts, given by professor, are not clear :/.2012-01-03
  • 0
    @unNaturhal: Fair enough; it takes some experience to even become aware that there may be different ways of defining something like a boolean algebra. But, for a simple example, I did not assume that $0$ and $1$ were neutral elements in my answer (I *deduced it* in Lemma 1), but you had them as axioms. I did not assume complements were unique, but you may have; the fact that double negation is the identity is often assumed, I didn't, etc. Given your assumptions, the argument that shows that, for instance, `not(A) OR not(B)` is the complement of `A AND B` might be enough.2012-01-03
  • 0
    If you show one of the two, then the other follows by the duality principle.2012-01-06

5 Answers 5

20

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$

  • 3
    You are too impressive Arturo...2012-01-02
  • 1
    @ArturoMagidin: I made the exercise following your demonstration. This is what I made: [image](http://img806.imageshack.us/img806/6494/img014o.jpg). The comments are in italian, but I think that is clear enough. There's something wrong?2012-01-08
  • 0
    @ArturoMagidin: Another question: the five assiomatic property, don't need a demostration right? Otherwise they would not called axioms.2012-01-08
  • 1
    @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.2012-01-08
  • 0
    @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.2012-01-08
  • 0
    @ArturoMagidin: Sorry for my handwriting :P. However, what I meant about the axioms is: what I have to answer to the professor if he ask me, for instance: "Prove me the Distributivity property."?2012-01-09
  • 0
    @unNaturhal: It wasn't the handwriting, so much as (i) the display I was using; (ii) my own rather poor eyesight; and (iii) the contrast was too low. As to the question: in a boolean algebra, there are **two** distributivity properties, so the first question would be "*Which* distributivity property?" The second question would be "Under what assumptions?" The distributivity properties are part of the *axioms* a boolean algebra. One can be asked to show that a particular *interpretation* satisfies distributivity, but then you need to be told what $\land$ and $\lor$ actually *are*.2012-01-09
  • 0
    @ArturoMagidin: I think to have to thank you, Arturo. Yesterday I gave the exam for which I studied these things, and I got 30/30, thanks also to your explanation about the Boolean Algebra :)2012-01-11
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.

1

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.

  • 0
    I edited my first post. I hope that now is clear than before :)2012-01-02
  • 0
    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?2012-01-02
  • 0
    Because I thought, just like you, that the truth tables were enough to explain the Theorems, but my teacher was not convinced of this...2012-01-02
  • 0
    @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.2012-01-06
0

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.

0

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$