Boolean Functions

• Boolean Functions are an expression formed with binary variables, the two binary operators OR and AND, and unary operator NOT, parentheses, and an equal sign. For the given value of the variables, the function can be either 0 or 1.
• Boolean functions represented as an algebraic expression:

Consider Boolean function F1 = xyz'.
Function F1 is equal to 1 if x=1, y=1 and z=0; otherwise F1 =0.

Other examples are: F2 = x + y'z,

F3 = x'y'z + x'yz + xy',
F4 = xy' + x'z etc.

• The boolean function represented in a truth table:

The number of rows in the truth table is 2n, where n is the number of binary variables in the function, The 1's and 0's combinations for each row are easily obtained from the binary numbers by counting from 0 to 2n – 1.

 

x	y	z	F1	F2	F3	F4
0	0	0	0	0	0	0
0	0	1	0	1	1	1
0	1	0	0	0	0	0
0	1	1	0	0	1	1
1	0	0	0	1	1	1
1	0	1	1	1	0	0
1	1	0	0	1	0	0
1	1	1	0	1	0	0

Note:

Is it possible to find two algebraic expressions that specify the same
function?

Answer: Yes.

Being straightforward, the manipulation of Boolean algebra is applied mostly to the problem of finding simpler expressions for the same function.
Example: Did you or did you not notice that Functions F3 and F4 are the same although they have different combinations of binary variables within them.

Algebraic manipulation and simplification of Boolean function:

Simplify the following Boolean functions to a minimum number of literals(A literal is a primed or unprimed (i.e. complemented or un-complemented) variable.).

1. x + x 'y = (x + x ')(x + y) = 1.(x + y) = x + y

2. x(x' + y) = xx' + xy = 0 + xy = xy

3. From before example of F3 and F4

F3 = x'y'z + x'yz + xy' = x'z(y' + y) + xy' = x'z + xy' = F4

Complement of Function:

The complement of a function F is F' and is obtained from an interchange of 0's for 1's and 1's for 0's in the value of F. The complement of a function may be derived algebraically through DeMorgan's theorem. De-Morgan's theorems can be extended to three or more variables. The three-variable form of the first De-Morgan's theorem is derived below.

(A + B + C)' =  (A + X)'                 let B + C = X
= A'X'                       (DeMorgan)
= A' (B + C)'              substitute B + C = X
= A'(B'C')                  (DeMorgan)
= A'B'C'                    (associative)

DeMorgan's theorems for any number of variables resemble in form the two variable case and can be derived by successive substitutions
similar to the method used in the above derivation. These theorems can be generalized as follows:

(A + B + C + D + ... + F)' = A'B'C'D'... F'
(ABCD ... F)' = A' + B' + C' + D' + ... + F'

The generalized form of De Morgan's theorem states that the complement of a function is obtained by interchanging AND and OR and complementing each literal.