Sec 11.1 – Boolean Functions
Boolean Algebra provides the operations [complement, product, sum] and rules for working with the set {0, 1}.
Complement [denoted with bar]: 0 = 1 1 = 0
Product [denoted with or AND]:
1 1 = 1 1 0 = 0 0 1 = 00 0 = 0
Sum [denoted with + or OR]:
1 + 1 = 1 1 + 0 = 1 0 + 1 = 10 + 0 = 0
precedenceofoperators:
complement, product, sum
Example:
(1 + 0) (0 1) = 1 0 = 1 1 = 1
Let B = {0, 1}
Definition. A Booleanvariable, x, assumes values only from B.
Definition. A Booleanfunctionofdegreen is a function from Bn, the set {(x1, x2, …, xn) | xi B, 1 i n}, to B. Function values are often displayed in tables.
Boolean Expressions, which can represent Boolean functions, are made up from Boolean variables and operations. They are defined recursively as follows:
0, 1, x1, x2, ..., xn are Boolean expressions
if E1 and E2 are Boolean expressions, then so are: E1, (E1E2), and (E1+E2)
Each Boolean expression represents a Boolean function. To evaluate a function, we substitute 0’s and 1’s for the variables in the same way we did for Truth tables.
Table 1. F(x,y,z) = x + yzx / y / z / x / yz / F(x,y,z) = x + yz
1 / 1 / 1 / 0 / 1 / 1
1 / 1 / 0 / 0 / 0 / 0
1 / 0 / 1 / 0 / 0 / 0
1 / 0 / 0 / 0 / 0 / 0
0 / 1 / 1 / 1 / 1 / 1
0 / 1 / 0 / 1 / 0 / 1
0 / 0 / 1 / 1 / 0 / 1
0 / 0 / 0 / 1 / 0 / 1
Definition. Two Boolean functions, F and G, are equivalent IFF when they are evaluated on the variables b1, b2, ..., bn B:
F(b1, b2, ..., bn) = G(b1, b2, ..., bn)
Example. All the following functions are equivalent: xy xy + 0 xy1
Definition. The complement of the Boolean function F is the function F, where
F(x1, ..., xn) = F(x1, ..., xn)
Definition. The Booleansum F + G is defined by:
(F + G)(x1, ..., xn) = F(x1, ..., xn) + G(x1, ..., xn)
Definition. The Booleanproduct FG is defined by:
(FG)(x1, ..., xn) = F(x1, ..., xn)G(x1, ..., xn)
Definition. The degree of a Boolean function is the number of different variables upon which it depends. F(x1, ..., xn) has degree n.
Table 3. The Boolean Functions of Degree 2.x / y / F1 / F2 / F3 / F4 / F5 / F6 / F7 / F8 / F9 / F10 / F11 / F12 / F13 / F14 / F15 / F16
1 / 1 / 1 / 1 / 1 / 1 / 1 / 1 / 1 / 1 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0
1 / 0 / 1 / 1 / 1 / 1 / 0 / 0 / 0 / 0 / 1 / 1 / 1 / 1 / 0 / 0 / 0 / 0
0 / 1 / 1 / 1 / 0 / 0 / 1 / 1 / 0 / 0 / 1 / 1 / 0 / 0 / 1 / 1 / 0 / 0
0 / 0 / 1 / 0 / 1 / 0 / 1 / 0 / 1 / 0 / 1 / 0 / 1 / 0 / 1 / 0 / 1 / 0
Table 4. The Number of Boolean Functions of Degree n.
Degree / Number
1 / 4
2 / 16
3 / 256
4 / 65,536
5 / 4,294,967,296
6 / 18,446,744,073,709,551,616
How many different Boolean functions of degree n are there? There are 2n different n-tuples of 0s and 1s (representing all possible combinations of the variable values). Since each function is an assignment of 0s and 1s to each of these n-tuples, there are 2^2n different Boolean functions.
Identity / Name
x = x / Law of the Double Complement
x + x = x
x x = x / Idempotent laws
x + 0 = x
x 1 = x / Identity laws
x + 1 = 1
x 0 = 0 / Dominance laws
x + y = y + x
x y = y x / Commutative laws
x + (y + z) = (x + y) + z
x(yz) = (xy)z / Associative laws
x + yx = (x + y)(x + z)
x(y + z) = xy + xz / Distributive laws
(xy) = x + y
(x + y) = xy / De Morgan’s laws
We can use a table of Boolean values to verify the distributive law x(y + z) = xy + xz
Table 6. Verification of Distribution lawx / y / z / y + z / xy / xz / x(y+z) / xy + xz
1 / 1 / 1 / 1 / 1 / 1 / 1 / 1
1 / 1 / 0 / 1 / 1 / 0 / 1 / 1
1 / 0 / 1 / 1 / 0 / 1 / 1 / 1
1 / 0 / 0 / 0 / 0 / 0 / 0 / 0
0 / 1 / 1 / 1 / 0 / 0 / 0 / 0
0 / 1 / 0 / 1 / 0 / 0 / 0 / 0
0 / 0 / 1 / 1 / 0 / 0 / 0 / 0
0 / 0 / 0 / 0 / 0 / 0 / 0 / 0
We may also use the identities to prove other properties, such as the absorptionlaw:
x(x + y) = x
x(x + y) / = (x + 0)(x + y) / Identity law for Boolean sum= x + 0y / Distributive law of Boolean sum over Boolean product
= x + y0 / Commutative - Bool product
= x + 0 / Dominance law - Bool product
= x / Identity law for Boolean sum
Definition. The dual of a Boolean expression is obtained by interchanging Boolean sums and Boolean products, and interchanging 0s and 1s.
Booleanexpressiondual
x(y + 0) x + (y 1)
x 1 + (y + z)(x + 1) (yz)
Note: most of the identities come in pairs which are duals of each other.
Definition. The dualofaBooleanfunction F, represented by a Boolean expression, is the function represented by the dual of F’s expression. [denoted Fd]
Definition. The dualityprinciple states that the duals of equivalent functions are equivalent.
Example. Since x(x + y) = x, then x + (xy) = x also. [another absorption law]
Definition. A Booleanalgebra is a set B with two binary operations and , elements 0 and 1, and a unary operation such that the following properties hold for all x, y, and z in B:
x 0 = xx 1 = x / Identity laws
x x = 1
x x = 0 / Dominance laws
(x y) z = x (y z)
(x y) z = x (y z) / Associative laws
x y = y x
x y = y x / Commutative laws
x (y z) = (x y) (x z)
x (y z) = (x y) (x z) / Distributive laws
Collections which satisfy all these properties:
B = {0, 1} with the OR and AND operations and the complement operator
The set of propositions in n variables with the and operators, F and T, and the negation operator
The set of subsets of a universal set U with the union and intersection operations, the empty set and universal set, and the set complementation operator
Thus, to establish results about each of Booleanexpressions,propositions,and sets, we need only prove results about abstract Boolean algebras!
MAT 2345, Sec 9.1
Page 1 of 10