De Morgan's Theorum
Augustus De Morgan was a 19th century mathematician working in the field of propositional logic, he established a series of rules concerned with conversion between different operators using inversion. The fundamental basis of his theory is that NOT ( P AND Q) = (NOT P) OR (NOT Q), and similarly NOT (P OR Q) = (NOT P) AND (NOT Q), this is often known as De Morgan Duality.
Expanding upon this idea, we can say that it is possible for any expression to be shown in two fundamental t ways, either as a series of variables AND'd together (known as a minterm) or a series of variables OR'd together (known as a maxterm).
A full equation may then be shown either as a series of minterms OR'd together (the sum of products form), or a series of maxterms AND'd together (the product of sums form).
The Product of Sums form (POS), a series of maxterms are AND'd together
The Sum of Products form (SOP), a series of minterms are OR'd together
We can use truth tables to prove that De Morgan's theory is correct, as shown in the tables below:
Now we have established the basis of De Morgan's theory, we can use it in practice to help simplify boolean equations, in a production environment this could simplify the overall circuit being created and thus lower the cost of manufacturing the circuit. It is possible to reduce the entire circuit to a series of only AND gates and NOT gates, or OR gates and NOT gates, potentially significantly reducing costs.
Or, using a more complicated example:
De Morgan's theorem is not just important in Computer Systems though, it also pops up in the Formal Aspects of Computer Science module, since its foundation is in propositional logic. When applied to logic, De Morgan's theory is used to expand the negation of a conjunction or disjunction, such that
¬ ( A V B ) = ¬ ( A ) Λ ¬ ( B ) and ¬ ( A Λ B ) = ¬ ( A ) V ¬ ( B )
The same principle is true in Set Theory, where
References:
- Janet Lavery - Durham University Computer Systems, Machine Architecture Lecture 1, 2007
- Janet Lavery - Durham University Computer Systems, Machine Architecture Lecture 2, 2007
- DeMorgan's Theorems - from http://www.mtsu.edu/~phys2020/Lectures/L19-L25/L3/DeMorgan/body_demorgan.html