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, 2014 at 16:58
  • $\begingroup$ @GitGud: What do you mean? Like the law of ones, zeroes, Idompotence law etc? $\endgroup$
    – Nick
    Sep 23, 2014 at 17:08
  • $\begingroup$ Yes. And don't forget the rules regarding $\neg$. $\endgroup$
    – Git Gud
    Sep 23, 2014 at 17:10
  • $\begingroup$ @GitGud: Involution and the Complementarity Laws? How do I use that to prove this? $\endgroup$
    – Nick
    Sep 23, 2014 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, 2014 at 20:38

2 Answers 2

7
$\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$
5
  • $\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, 2016 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$ Feb 21, 2017 at 21:53
  • $\begingroup$ I am refering to both statements of the Complementarity Law. $\endgroup$ Feb 21, 2017 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$ Feb 21, 2017 at 22:37
  • $\begingroup$ Why is it sufficient to show that $X+Y+\overline{X}\cdot \overline{Y} = 1$? In boolean algebra $a+b=1$ does not necessarily imply $b=\overline{a}$. $\endgroup$
    – Sam
    Nov 10, 2021 at 10:09
4
$\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$
1
  • $\begingroup$ Alternatively, if one has already shown basic properties of the component then $(3)$ follows easily from $(2)$. In particular, if one has shown that the complement of $X$ is unique and that $\overline{\overline{X}}=X$, then showing $(X+Y)+(\overline{X}\cdot \overline{Y})=1$ gives $(X\cdot Y)\cdot (\overline{X}+\overline{Y})=0$ by duality. Substituting $X$ by $\overline{X}$ and using the fact that $\overline{\overline{X}}=X$ we get $(\overline{X}\cdot \overline{Y})\cdot (X+Y)=0$. $\endgroup$
    – Sam
    Nov 10, 2021 at 10:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .