Practical Electronics/Logic/Boolean Identities

From Wikibooks, open books for an open world
< Practical Electronics‎ | Logic
Jump to: navigation, search


There are several laws that can be used to simplify or modify Boolean expressions. This page will explain them, this page will list them for easy reference.

Axioms[edit]

Axioms are propositions that are deemed obvious and therefore are not required to be proved - in fact they cannot be proved because they are defined to be true by the structure of the algebra. They form the foundation of the rest of boolean algebra by defining the two values, 1 and 0 and the three operators, AND, OR and NOT.

  Axiom Axiom Dual
1 \mbox{If }X\ne1, \,X=0 \mbox{If }X\ne0, \,X=1
2 \mbox{If }X=0, \, \overline{X} =1 \mbox{If }X = 1, \, \overline{X}=0
3 0 \cdot 0 = 0 1 + 1 = 1 \,
4 1 \cdot 1 = 1 0 + 0 = 0 \,
5 1 \cdot 0 = 0 \cdot 0 = 0 1 + 0 = 0+1= 1 \,

DeMorgan's Law[edit]

DeMorgan's Law Venn Diagram 2.svg

DeMorgan's Law is a very powerful tool for grouping or ungrouping logical statements. It basically states that either logical function AND or OR may be replaced by the other, given certain changes to the equation. It is usually expressed as two distinct identities. First is the following:


\overline{A+B}=\overline A \cdot \overline B

At first, it may not be clear how this result is found, but if you look at the first Venn Diagram to the left, it is clear. Imagine a variable called X, which is defined by:

X=\overline{A+B}

This means that X is NOT in group A OR B, so it must be in the blue region. Now, this is the same as saying that X is NOT in A AND also NOT in B. This means that we can also define X as:

X=\overline A \cdot \overline B

This can also be seen by drawing up a truth table: working in from each end of the table, we can see that the two give identical results:

A B A+B ¬(A+B)   ¬A•¬B ¬B ¬A
0 0 0 1   1 1 1
0 1 1 0   0 0 1
1 0 1 0   0 1 0
1 1 1 0   0 0 0
DeMorgan's Law Venn Diagram 1.svg

The second expression is basically the same but with exchanged symbols

\overline{A \cdot B}=\overline A + \overline B

If we do the same trick with X again, we see that it must NOT be in both A AND B. Therefore it must be in the light blue, dark blue or red regions, and not in the centre. We can now say that X is either not in A, not in B or not in either. This is the the same as saying that X is NOT in A OR NOT in B (using the logical kind of "or"). Therefore,

X=\overline A + \overline B

Again, this can be shown by a truth table:

A B A•B ¬(A•B)   ¬A+¬B ¬B ¬A
0 0 0 1   1 1 1
0 1 0 1   1 0 1
1 0 0 1   1 1 0
1 1 1 0   0 0 0

An easy way to remember the laws given above is: "Split the line, change the sign." With these two rules, it can be shown that any logical statement can be changed using the following method:

  1. Compliment all terms in the expression
  2. Change all ANDs to ORs and all ORs to ANDs
  3. Invert the result

See Also[edit]