0

I chanced upon a seemingly "too good to be true" proof of Demorgan's theorem for boolean algebra, however I'm not quite sure if it's valid.

The principle of duality states that for a boolean algebra, changing all OR signs to AND signs, all 1's to 0's, and vice versa for both statements, gives another boolean algebra.

So let us assume, $\overline A + \overline B = X$

Since all the boolean variables have values of either 1 or 0, complementing them is equivalent to applying the relevant part of the duality principle.

So, $\overline A +\overline B = X$

$\Rightarrow A \times B = \overline X$

$\Rightarrow \overline{AB} = \overline{(\overline X)}$

$\Rightarrow \overline{AB} = X$

And thus, $\overline A + \overline B = \overline {AB}$

Is the above proof valid?

buggy
  • 51
  • 1
    The 'principle of duality' is equivalent to De Morgan's law - you cannot use it to prove De Morgan's law. – Peter Foreman Jul 08 '19 at 14:36
  • @PeterForeman I see. And the bona fide proof for De Morgan's law would be one using truth tables? Or is algebra using other given properties sufficient? – buggy Jul 08 '19 at 14:39
  • See a formal proof here https://en.m.wikipedia.org/wiki/De_Morgan%27s_laws. It uses set theory. – Peter Foreman Jul 08 '19 at 14:41

0 Answers0