Boolean Function

Consider a Boolean algebra of subsets generated by a set , which is the set of subsets of that can be obtained by means of a finite number of the set operations union, intersection, and complementation. Then each of the elements of is called a Boolean function generated by (Comtet 1974, p. 185). Each Boolean function has a unique representation (up to order) as a union of complete products. It follows that there are inequivalent Boolean functions for a set with cardinality (Comtet 1974, p. 187).

In 1938, Shannon proved that a two-valued Boolean algebra (whose members are most commonly denoted 0 and 1, or false and true) can describe the operation of two-valued electrical switching circuits. The following table gives the truth table for the possible Boolean functions of two binary variables.

0	0	0	0	0	0	0	0	0	0
0	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1

0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1

The names and symbols for these functions are given in the following table (Simpson 1987, p. 539).

operation	symbol	name
	0	FALSE
		AND
		AND NOT
		NOT AND
		XOR
		OR
		NOR
	XNOR	XNOR
		NOT
		OR NOT
		NOT
		NOT OR
		NAND
	1	TRUE

Determining the number of monotone Boolean functions of variables is known as Dedekind's problem and is equivalent to the number of antichains on the -set . Boolean functions can also be thought of as colorings of a Boolean -cube. The numbers of inequivalent monotone Boolean functions in , 2, ... variables are given by 2, 3, 5, 10, 30, ...(OEIS A003182).

Let denote the number of distinct monotone Boolean functions of variables with mincuts. Then

			(1)
			(2)
			(3)
			(4)

Wolfram Web Resources