A n-digit boolean function is f: {0,1} x ... x {0,1} → {0,1}

** 1-digit boolean functions **

There are exactly four different boolean functions, with one variable:

constant zero: f(x) = 0

constant one: f(x) = 1

identity: f(x) = x

not: f(x) = !x

** 2-digit boolean functions **

Most of the well known boolean functions, like AND or OR, are 2-digit. This means they are:

f: {0,1} x {0,1} → {0,1}

Obviously there are 16 different 2-digit boolean functions. Why? I'll explain it: As there are two boolean variables, there are 4 different combinations:

x1, x2 ∈ {0,1}

1: x1=0 x2=0

2: x1=0 x2=1

3: x1=1 x2=0

4: x1=1 x2=1

This means there are 4 combinations for which each function has to have a result(0000,0001,...,1111). This is equivalent to 4 Bits, so you have 16 different functions.

Here are the 16 2-digit boolean functions:

1. constant zero:

x1 x2 f(x1,x2)

0 0 0

0 1 0

1 0 0

1 1 0

2. NOR ↓

x1 x2 f(x1,x2)

0 0 1

0 1 0

1 0 0

1 1 0

3. has no name (I guess)

x1 x2 f(x1,x2)

0 0 0

0 1 1

1 0 0

1 1 0

4. !x1

x1 x2 f(x1,x2)

0 0 1

0 1 1

1 0 0

1 1 0

5. has no name

x1 x2 f(x1,x2)

0 0 0

0 1 0

1 0 1

1 1 0

6. !x2

x1 x2 f(x1,x2)

0 0 1

0 1 0

1 0 1

1 1 0

7. XOR ⊕ (anti-valence)

x1 x2 f(x1,x2)

0 0 0

0 1 1

1 0 1

1 1 0

8. NAND |

x1 x2 f(x1,x2)

0 0 1

0 1 1

1 0 1

1 1 0

9. AND (conjunction)

x1 x2 f(x1,x2)

0 0 0

0 1 0

1 0 0

1 1 1

10. XNOR (equivalance

x1 x2 f(x1,x2)

0 0 1

0 1 0

1 0 0

1 1 1

11. x2

x1 x2 f(x1,x2)

0 0 0

0 1 1

1 0 0

1 1 1

12. implication →

x1 x2 f(x1,x2)

0 0 1

0 1 1

1 0 0

1 1 1

13. x1

x1 x2 f(x1,x2)

0 0 0

0 1 0

1 0 1

1 1 1

14. ←

x1 x2 f(x1,x2)

0 0 1

0 1 0

1 0 1

1 1 1

15. OR v (disjunction)

x1 x2 f(x1,x2)

0 0 0

0 1 1

1 0 1

1 1 1

16. constant one

x1 x2 f(x1,x2)

0 0 1

0 1 1

1 0 1

1 1 1

** Boolean functions with more than two binary variables:**

1. extend 2-digit funtions
This is sometimes in wiring diagrams used to simplify them. For example, if you see the symbol for AND with three inputs:

A -|--\ B -| |--- AND(A,B,C) C -|--/

AND(A,B,C) = AND(A,AND(B,C)) = A AND B AND C:

A-------|--\ B -|\___| | C -|/ |--/

2. combine 1-digit and 2-digit boolean functions This is what ist used in every wiring plan. You combine severeal of the above functions, to more complex functions:

f(x1,x2,x3,x4) = (x1 AND x2) ⊕ (x3 v (x4 AND (!x1)))

Some of the parenthesises can be omissed: AND binds stronger than all other 2-digit functions. 1-digit funtions bind stronger than 2-digit functions: f(x1,x2,x3,x4) = x1 AND x2 ⊕ (x3 v x4 AND !x1)

** rules for boolean functions **

!(!x)) = x

x1 AND (x2 AND x3) = (x1 AND x2) AND x3

x1 v (x2 v x3) = (x1 v x2) v x3

x1 ⊕ (x2 ⊕ x3) = (x1 ⊕ x2) ⊕ x3

x1 AND (x2 v x3) = x1 AND x2 v x1 AND x3

x1 v x2 AND x3 = (x1 v x2) AND (x1 v x3)

x1 AND (x2 ⊕ x3) = x1 AND x2 ⊕ x1 AND x3

x1 AND x2 = x2 AND x1

x1 v x2 = x2 v x1

x1 &oplus x2 = x2 ⊕ x1

!(x1 AND x2 AND ... AND xn) = !x1 v !x2 v ... v !xn

!(x1 v x2 v ... v xn) = !x1 AND !x2 AND ... AND !xn

x v x = x

x AND x = x

x v 0 = x

x AND 0 = 0

x v 1 = 1

x AND 1 = x

x v !x = 1

x AND ! x1 = 0

x ⊕ x = 0

x ⊕ !x = 1

x ⊕ 0 = x

x ⊕ 1 = !x

x1 v x2 = x1 ⊕ x2 ⊕ x1 AND x2

x1 ⊕ x2 = x1 AND !x2 v !x1 AND x2

!x = x | x

x1 AND x2 = (x1|x2)|(x1|x2)

x1 v x2 = (x1|x1)|(x2|x2)

!x = x ↓ x

x1 v x2 = (x1 ↓ x2) ↓ (x1 ↓ x2)

x1 AND x2 = (x1 ↓ x1) ↓ (x2 ↓ x2)

These last 6 rules are very important, as they show, that AND and OR, which are pretty complex to realize, can be substituted by NAND and NOR.

** How to tell if two functions are equal **

If both functions are simple, one can just calculate both and look at their results. If the results are equal, the functions are, too (works in the other direction, too: different results → different functions). Another possibility is to use the rules above and try to form one function into the other.

Both methods are easy for small functions, but if you have bigger functions, there are better ways: For each boolean function exist three diffenent forms, in which each function is unique. This means if these forms are equal (and only then!) the functions are equal. These are the complete disjunctive normal form, the complete conjunctive normal form and the antivalent normal form. If you want to know more about these (especially the two first ones) I suggest you read my write ups about boolean cube, Karnaugh maps and Quine-McClusky. Both are methods to reach one of these forms.