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

  • 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
    @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$