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 AND. The use of these 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 these is the same as with normal algebra but the second is not. Consequently 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 synthesis) is more commonly used than a product of sums (which leads to easy NOR synthesis).

De morgans theorem

De-morgans theorem states that if you invert every variable in a function, swap + and . operators (taking care to add brackets to ensure the order of operations remains the same) and invert the result, you get a function equivalent 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.