3
$\begingroup$

If $\overline X \equiv \text { not }X$,

De Morgan's Laws are stated as:

  1. $ \overline{(A + B)}= \overline A\cdot \overline B$

  2. $ \overline{(A\cdot B)} = \overline A + \overline B$

Verify the above laws algebraically.

I can prove this using truth tables and logic gates but algebraically, I don't know any intuitive way to prove it.

$$ \begin{array}{ |c|c| } \hline {\text{Axioms}}\\ \hline \text{Property of 0} & X + 0 = X \space ;\space X\cdot0 = 0 \\ \text{Property of 1} & X + 1 = 1 \space;\space X\cdot1 = X\\ \text{Idempotence Law} & X + X = X \space;\space X\cdot X = X\\ \text{Involution Law} & \overline{\overline X} = X\\ \text{Complementarity Law} & X + \overline X = 1 \space;\space X\cdot\overline X = 0\\ \text{Commutative Law} & X+Y = Y+X \space;\space X\cdot Y = Y\cdot X\\ \text{Associative Law} & (X+Y)+Z = X+(Y+Z) \space;\space (X\cdot Y)\cdot Z = X\cdot (Y\cdot Z)\\ \text{Distributive Law} & X(Y+Z) = XY + XZ \space;\space X + YZ = (X+Y)(X+Z)\\ \text{Absorption Law} & X + XY = X \space;\space X(X+Y) = X\\ \text{Other (3rd Distributive)} & X + \overline XY = X+Y\\ \hline \end{array} $$

$\endgroup$
6
  • 3
    $\begingroup$ What are the axioms? $\endgroup$
    – Git Gud
    Sep 23 '14 at 16:58
  • $\begingroup$ @GitGud: What do you mean? Like the law of ones, zeroes, Idompotence law etc? $\endgroup$
    – Nick
    Sep 23 '14 at 17:08
  • $\begingroup$ Yes. And don't forget the rules regarding $\neg$. $\endgroup$
    – Git Gud
    Sep 23 '14 at 17:10
  • $\begingroup$ @GitGud: Involution and the Complementarity Laws? How do I use that to prove this? $\endgroup$
    – Nick
    Sep 23 '14 at 17:13
  • 1
    $\begingroup$ Please list the axioms in the question and not just their names, but the actual syntactic formulation of them. $\endgroup$
    – Git Gud
    Sep 23 '14 at 20:38
6
$\begingroup$

By Complementarity Law, $$P + \overline P = 1 \space\text{ and }\space P \cdot \overline P = 0$$

(Note: I shall only be using $P + \overline P = 1$ as its dual is automatically true)


First Law:: DeMorgan's $1^{\text{st}}$ law states $\overline{X+Y} = \overline X \cdot \overline Y$

It is sufficient to prove that $(X + Y) + \overline X \cdot \overline Y = 1$ $$ \begin{align} \text{LHS} &= Y + (X + \overline X \cdot \overline Y)\\ &= Y + X + \overline Y\\ &= (Y+\overline Y) + X\\ &= 1 + X \\&= 1 = \text{RHS} \end{align} $$


Second Law:: DeMorgan's $2^{\text{nd}}$ Law states that $\overline{X\cdot Y} = \overline X + \overline Y$

It is sufficient to prove that $X\cdot Y + (\overline X + \overline Y) = 1$

$$ \begin{align} \text{LHS} &= \overline Y + (\overline X + \overline{\overline X}\cdot Y)\\ &= \overline Y + (\overline X + Y)\\ &= (Y + \overline Y) + \overline X\\ &= 1 + \overline X\\ &= 1 = \text{RHS} \end{align} $$


Hence, DeMorgan's Laws are verified algebraically.

$\endgroup$
4
  • $\begingroup$ This is not a complete proof, since proof must be made using both of the Complementarity Law, to ensure that the proofed law (DeMorgan's Laws) is equal. The current proof only shown like <=, thus not also >=, so == thus can't be inferred. See similarity in proof of De Morgan's laws for sets. $\endgroup$ Nov 20 '16 at 10:11
  • $\begingroup$ Both have to be satisfied. For example, given the boolean algebra $(P(X),\cup ,\cap )$, where $P(X)$ is the powerset of $X$. Take $A, B \in P(X)$, $A\cup B = 1$ doesn't imply $A\cap B = 0$. For example, $X = \{ 1,2,3,4,5 \}$, $A = \{ 1,2 \}$ and $B = \{ 4,5 \}$. $\endgroup$
    – Alberto
    Feb 21 '17 at 21:53
  • $\begingroup$ I am refering to both statements of the Complementarity Law. $\endgroup$
    – Alberto
    Feb 21 '17 at 21:59
  • $\begingroup$ I didn't explain myself correctly. $B=\bar{A}$ if and only if $A\cup B = 1$ and $A\cap B = 0$. Now, you can't use the duality principle for this last statement because these identities don't hold for any Boolean algebra, as the one I mentioned before. $\endgroup$
    – Alberto
    Feb 21 '17 at 22:37
2
$\begingroup$

Lemma: $ A + B = 1 \land AB = 0 \implies A = \overline B $

Proof:

Given $ A + B = 1 $, then:

$ (A + B) \overline B = 1 \cdot \overline B = \overline B $

$\implies A \overline B + B \overline B = A \overline B + 0 = A \overline B = \overline B $   (1)

Given $ AB = 0 $, we combine it with (1) to obtain:

$ A \overline B + AB = \overline B + 0 $

$\implies A (\overline B + B) = A \cdot 1 = A = \overline B$   QED

 

First law:

$ (X + Y) + \overline X \overline Y = Y + (X + \overline X \overline Y) = $

  $ = Y + (X + \overline Y) = (Y + \overline Y) + X = $

  $ = 1 + X = 1 $   (2)

$ (X + Y) \cdot \overline X \overline Y = X \cdot \overline X \overline Y + Y \cdot \overline X \overline Y = $

  $ = (X \overline X) \cdot \overline Y + (Y \overline Y) \cdot \overline X = 0 \cdot \overline Y + 0 \cdot \overline X = $

  $ = 0 + 0 = 0 $   (3)

By (2), (3), and the lemma, we have $ \overline { X + Y } = \overline X \overline Y $ -- QED

 

Second law:

$ \overline { X Y } = \overline { { \overline { \overline X } } \cdot { \overline { \overline Y } } } = $   (by First law)

  $ = \overline { \overline { \overline X + \overline Y } } = \overline X + \overline Y $   QED

 

Notes

  • Contrary to the approach in the first answer, it is necessary to prove both that $ A + B = 1 $ and $ AB = 0 $ in order to claim that $ A = \overline B $.
  • Absorption Law and 3rd Distributive are redundant as axioms, following from Property of 1, Complementarity Law, Idempotence Law, and Associative Law.
  • Idempotence Law is redundant as an axiom, following from Property of 1 and Distributive Law
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.