8.2 Boolean Functions and Truth Tables

A Boolean expression is a sequence of zeros, ones, and literals separated by Boolean operators. A Boolean literal is a primed (negated) or unprimed variable name , and all variable names will be a single alphabetic character. A Boolean function is a specific Boolean expression; we will generally give Boolean functions the name F with a possible subscript. For example, consider the following Boolean function:

 F  = AB + C

This function computes the logical AND of A and B and then logically ORs this result with C . If A = 1 , B = 0 , and C = 1 , then F returns the value one (1* 0 + 1 = 1).

You can also represent a Boolean function with a truth table . The truth tables for the logical AND and OR functions are shown in Table 8-1 and Table 8-2.

Table 8-1: AND truth table
AND		1

1		1

Table 8-2: OR truth table
OR		1
		1
1	1	1

For binary operators and two input variables , this form of a truth table is very natural and convenient . However, for functions involving more than two variables, these truth-table forms don't work well.

Table 8-3 shows another way to represent truth tables. This form has several advantages - it is easier to fill in the table, it supports three or more variables, and it provides a compact representation for two or more functions. The example in Table 8-3 demonstrates how to create a truth table for three different functions of three input variables.

Table 8-3: Truth Table Format for a Function of Three Variables
C	B	A	F = ABC	F = AB + C	F = A+BC

		1			1
	1
	1	1		1	1
1				1
1		1		1	1
1	1			1	1
1	1	1	1	1	1

Although you can create an infinite variety of Boolean functions, they are not all unique. For example, F = A and F = AA are two different functions. By theorem two, however, it is easy to show that these two functions produce exactly the same result no matter what input value you supply for A . As it turns out, if you fix the number of input variables you're going to allow, there are a finite number of unique Boolean functions possible. For example, there are only 16 unique Boolean functions with two input variables and there are only 256 possible Boolean functions with three input variables. Given n input variables, there are unique Boolean functions (two raised to two raised to the nth power). With two input variables there are or 16 different functions. With three input variables there are or 256 possible functions. Four input variables have or 2 ¹⁶ , or 65,536 unique Boolean functions.

When working with only 16 Boolean functions (two input variables), we can name each unique function. Table 8-4 lists common names for these functions.

Table 8-4: Common Names for Boolean Functions of Two Variables
Function Number ^[1]	Function Name	Description
	Zero (clear)	Always returns zero regardless of A and B input values
1	Logical NOR	(NOT (A OR B)) = (A + B) ²
2	Inhibition (AB ² )	Inhibition = AB ² (A AND not B). Also equivalent to A > B or B < A
3	NOT B	Ignores A and returns B ²
4	Inhibition (BA ² )	Inhibition = BA ² (B AND not A). Also equivalent to B > A or A < B
5	NOT A	Returns A ² and ignores B
6	Exclusive-or (XOR)	A • B. Also equivalent to A ‰ B
7	Logical NAND	(NOT (A AND B)) = (A * B) ²
8	Logical AND	A * B = (A AND B)
9	Equivalence (exclusive-NOR)	(A = B). Also known as exclusive-NOR (not exclusive-OR)
10	A	Copy A. Returns the value of A and ignores B's value
11	Implication, B implies A	A + B ² . (If B then A). Also equivalent to B ‰ A
12	B	Copy B. Returns the value of B and ignores A's value
13	Implication, A implies B	B + A ² . (If A then B). Also equivalent to A ‰ B
14	Logical OR	A + B. Returns A OR B
15	One (set)	Always returns one regardless of A and B input values
^[1] See the discussion of function numbers in the next section.