Two-element Boolean algebra

The simplest Boolean algebra is the one having just two elements, 1 and 0, which are often called true and false. The symbol "+" is usually used for OR and "." or no symbol at all for for AND. The use of theese operators is an analogy with addition and multiplication that holds if you consider any nonzero value to be the same as 1. Conventionally A.B+C is interpreted as (A.B)+C not A.(B+C). This is again the same as with addition and multiplication in normal algebra. NOT is generally represented by overline.

Basic identities

The basic identites given below can all be trivially shown to be true by feeding in every possible set of inputs and checking the results match.

• $A.A=A$
• $A+A=A$
• $A+0=A$
• $A+1=1$
• $A.0=0$
• $A.1=A$
• ${\overline {\overline {A}}}=A$
• $A.B={\overline {{\overline {A}}+{\overline {B}}}}$
• $A+B={\overline {{\overline {A}}.{\overline {B}}}}$

The + and . operators are distributive that is A.(B+C) = A.B + B.B and A+B.C = (A+B).(A+C) . The first of theese is the same as with normal algebra but the second is not! Consequentyly the first is far more comfortable for most people to do than the second. For this and other reasons a sum of products (which leads to easy NAND synthsis) is more commonly used than a product of sums (which leads to easy NOR synthisys.

De morgans theorem

De-morgans theorem states that if you invert every varible in a function swap + and . operators and invert the result you get a function equivilent to the one you started with. Repeated application of De-morgans theorem to parts of a function can be used to move all inversions to the individual variables.