BOOLEAN FUNCTIONS

CS 25

BOOLEAN FUNCTIONS
A binary variable can take the value of 0 or 1. A Boolean function is an expression formed w/ binary variables, the two binary operators OR and AND, the unary operator NOT, parentheses, and equal sign. For a given value of the variables, the function can be either 0 or 1. Consider, for example, the Boolean function: F1 = xyz mariaramilaisidrojimenez XUCC

BOOLEAN FUNCTIONS
The function F1 is equal to 1 if x = 1 and y = 1 and z = 0; otherwise F1 = 0. A Boolean function may also be represented in a truth table, we need a list of the 2n combinations of 1s and 0s of the n binary variables, and a column showing the combinations for w/c the function is equal to 1 or 0. Consider the following functions: mariaramilaisidrojimenez XUCC F2 = x + yz

BOOLEAN FUNCTIONS
F3 = x y z + x y z + x y F4 = x y + x z
x y z F1 0 0 0 0 0 0 1 0 F2 0 1 0 0 1 1 1 1 F3 0 1 0 1 1 1 0 0 F4 0 1 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 mariaramilaisidrojimenez 1 1 1

XUCC

BOOLEAN FUNCTIONS
Is an algebraic expression of a given Boolean function unique? In other words, is it possible to find two algebraic expressions that specify the same function? The answer is yes. As a matter of fact, the manipulation of Boolean algebra is applied mostly to the problem of finding simpler expressions for the same function. Consider, for example, F4. From the table we find that F4 is the same as F3, since both have identical 1s
mariaramilaisidrojimenez XUCC

BOOLEAN FUNCTIONS
the three binary variables. In general, two functions of n binary variables are said to be equal if they have the same value for all possible 2n combinations of the n variables. A Boolean function may be transformed from an algebraic expression into a logic diagram composed of AND, OR, and NOT gates. The implementation of the four functions are shown in the next slide.
mariaramilaisidrojimenez XUCC

BOOLEAN FUNCTIONS

mariaramilaisidrojimenez

XUCC

BOOLEAN FUNCTIONS

mariaramilaisidrojimenez

XUCC

BOOLEAN FUNCTIONS
Algebraic Manipulation A literal is a primed or unprimed variable. When a Boolean function is implemented w/ logic gates, each literal in the function designates an input to a gate, and each term is implemented w/ a gate. The minimization of the number of literals and the number of terms results in a circuit w/ less equipment. At the moment, we mariaramilaisidrojimenez XUCC shall narrow the minimization criterion to

BOOLEAN FUNCTIONS
in a Boolean function can be minimized by algebraic manipulations. Unfortunately, there are no specific rules to follow that will guarantee the final answer. The only method available is a cut-and-try procedure employing the postulates, the basic theorems, and any other manipulation method w/c becomes familiar w/ use.
mariaramilaisidrojimenez XUCC

BOOLEAN FUNCTIONS
Complement of a Function The complement of a function F is F and is obtained from an interchange of 01 for 1s and 1s for 0s in the value of F. The complement of a function may be derived algebraically through De Morgans theorem. De Morgans theorems can be extended to three or more variables. De Morgans theorems for any number of variables resemble in form the two-variable case and can be derived mariaramilaisidrojimenez XUCC by successive substitutions similar to the

BOOLEAN FUNCTIONS
method used in the derivation below. (A + B + C) = (A + X) let B + C = X =AX by Theorem5a = A (B + C) substitute B+C = X = A (B C) by Theorem5a = A B C by Theorem4b

mariaramilaisidrojimenez

XUCC

BOOLEAN FUNCTIONS
The generalized form of De Morgans theorem states that the complement of a function is obtained by interchanging AND and OR operators and complementing each literal.

mariaramilaisidrojimenez

XUCC

BOOLEAN FUNCTIONS
CANONICAL AND STANDARD FORMS Minterms and Maxterms A binary variable may appear either in its normal form (x) or in its complement form (x). Now consider two binary variables x and y combined w/ an AND operation. Since each variable may appear in either form, there are four possible combinations: x y, xy, xy, and xy. Each of these four AND terms is called a minterm or a standard mariaramilaisidrojimenez XUCC product.

BOOLEAN FUNCTIONS
In a similar fashion, n variables forming an OR term, w/ each variable being primed or unprimed, provide 2n possible combinations, called maxterms or standard sums. A Boolean function may be expressed algebraically from a given truth table by forming a minterm for each combination of the variables w/c produces a 1 in the function, and then taking the OR of all those terms.
mariaramilaisidrojimenez XUCC

BOOLEAN FUNCTIONS
x 0 0 0 0 1 1 1
mariaramilaisidrojimenez

y 0 0 1 1 0 0 1

z 0 1 0 1 0 1 0

Minterms Term Designation xyz m0 xyz xyz xyz xyz xyz xyz
XUCC

m1 m2 m3 m4 m5 m6

BOOLEAN FUNCTIONS
x 0 0 0 0 1 1 1
mariaramilaisidrojimenez

y 0 0 1 1 0 0 1

z 0 1 0 1 0 1 0

Maxterms Term Designation x+y+z M0 x+y+z x+y+z x+y+z x+y+z x+y+z x+y+z
XUCC

M1 M2 M3 M4 M5 M6

BOOLEAN FUNCTIONS
x 0 0 0 0 1 1 1 1
mariaramilaisidrojimenez

y 0 0 1 1 0 0 1 1

z 0 1 0 1 0 1 0 1

Function f1 0 1 0 0 1 0 0 1
XUCC

Function f2 0 0 0 1 0 1 1 1

BOOLEAN FUNCTIONS
These examples demonstrate an important property of Boolean algebra: Any Boolean function can be expressed as a sum of minterms ( by sum is meant the Oring of terms). These examples demonstrate a second important property of Boolean algebra: Any Boolean function can be expressed as a product of maxterms (by product is meant the ANDing of terms).
mariaramilaisidrojimenez XUCC

BOOLEAN FUNCTIONS
The procedure for obtaining the sum of minterms directly from the truth table is as follows. Form a minterm for each combination of the variables w/c produces a 1 in the function, and then form the OR of all those minterms.

mariaramilaisidrojimenez

XUCC

BOOLEAN FUNCTIONS
The procedure for obtaining the product of maxterms directly from the truth table is as follows. Form a maxterm for each combination of the variables w/c produces a 0 in the function, and then form the AND of all those maxterms. Boolean functions expressed as a sum of minterms or product of maxterms are said to be in canonical form.
mariaramilaisidrojimenez XUCC

BOOLEAN FUNCTIONS
Standard Forms The two canonical forms of Boolean algebra are basic forms that one obtains from reading a function from the truth table. These forms are very seldom the ones w/ the least number of literals, because each minterm/maxterm must contain, by definition, all the variables either complemented or uncomplemented.
mariaramilaisidrojimenez XUCC

BOOLEAN FUNCTIONS
Standard Forms Another way to express Boolean functions is in standard form. In this configuration, the terms that form the function may contain one, two or any number of literals. There are two types of standard forms: the sum of products and the product of sums. The sum of products is a Boolean expression containing AND terms, called mariaramilaisidrojimenez XUCC

BOOLEAN FUNCTIONS
Standard Forms product terms, of one or more literals each. The sum denotes the ORing of these terms. Ex. F1 = y + xy + x y z A product of sums is a Boolean expression containing OR terms, called sum terms. Each term may have any number of literals. Ex. F2 = x(y + z)(x + y + z + w)
mariaramilaisidrojimenez XUCC

BOOLEAN FUNCTIONS
Standard Forms The use the words product and sum stems from the similarity of the AND operation to the arithmetic product(multiplication) and the similarity of the OR operation to the arithmetic sum(addition). A Boolean function may be expressed in a nonstandard form. Ex. F3 = (AB + CD)(A BXUCC D) is neither in +C mariaramilaisidrojimenez

BOOLEAN FUNCTIONS
OTHER LOGIC OPERATIONS When the binary operators AND and OR are placed between two variables x and y, they form two Boolean functions x y and x + y, respectively. It was stated previously that there are 2n functions for n binary variables. For two variables, n=2 and the number of possible Boolean functions is 16. Therefore, the AND and OR functions are only two of a total of 16 possible functions formed w/ mariaramilaisidrojimenez XUCC two binary variables. It would be

BOOLEAN FUNCTIONS
OTHER LOGIC OPERATIONS the other 14 functions and investigate their properties. The 16 functions listed in truth table form can be expressed algebraically by means of Boolean expressions. The Boolean expressions are already simplified. The 16 functions listed can be subdivided into three categories:
mariaramilaisidrojimenez XUCC

BOOLEAN FUNCTIONS
1. Two functions that produce a constant 0 or 1. 2. Four functions w/ unary operations complement and transfer. 3. Ten functions w/ binary operators that define eight diff. operations AND, OR, NAND, NOR, exclusive-OR, equivalence, inhibition, and implication. Any function can be equal to a constant, but a binary function can be equal to only 1 or 0. mariaramilaisidrojimenez XUCC

BOOLEAN FUNCTIONS
A function w/c is equal to an input variable has been given the name transfer, because the variable x or y is transferred through the gate that forms the function w/o changing its value. Inhibition and implication are used by logicians but are seldom used in computer logic. AND and OR operators have been mentioned in conjunction w/ Boolean algebra.
XUCC

mariaramilaisidrojimenez

BOOLEAN FUNCTIONS
NAND, NOR, exclusive-OR, and equivalence are extensively used in the design of digital systems. Exclusive-OR(XOR or EOR) is similar to OR but excludes the combination of both x and y being equal to 1. Equivalence is a function that is 1 when the two binary variables are equal, I.e., when both are 0 or both are 1. Equivalence and exclusive-OR functions are complements of each other. mariaramilaisidrojimenez XUCC

BOOLEAN FUNCTIONS
Truth tables for the 16 functions of two binary variables

x 0 0 1 1

y 0 1 0 1

F0 0 0 0 0

F1 0 0 0 1

F2 0 0 1 0

F3 0 0 1 1

F4 0 1 0 0

F5 F6 F7 F8 F9 0 1 0 1 0 1 1 0
+

0 1 1 1
+

1 0 0 0

1 0 0 1

Operator Symbol
mariaramilaisidrojimenez

XUCC

BOOLEAN FUNCTIONS
Truth tables for the 16 functions of two binary variables

x 0 0 1 1

y 0 1 0 1

F10 F11 F12 F13 F14 F15 1 0 1 0 1 0 1 1 1 1 0 0

1 1 0 1

1 1 1 0

1 1 1 1

Operator Symbol
mariaramilaisidrojimenez

Boolean functions F0= 0 F1= xy F2= xy F3= x F4= xy F5= y F6= xy+xy F7= x+y

BOOLEAN FUNCTIONS
Operator Symbol xy x y y x x y x+y
+

Name

Comments

Null AND Inhibition Transfer Inhibition Transfer OR

Binary constant 0 x and y x but not y x y but not x y x or y

Exclusive-OR x or y but not both

mariaramilaisidrojimenez XUCC F8=(x+y) x y for the 16 functions of two variables NOR NOT-OR Boolean expressions

Boolean functions F10= y F11= x+y F12= x F13= x+y F14= (xy) F15= 1

BOOLEAN FUNCTIONS
Operator Symbol xy y xy x xy x y Name

Comments

F9 = xy+xy

Equivalence* x equals y Complement Not y Implication Implication NAND Identity If y then x If x then y NOT-AND Binary constant 1 Complement NOT x

*Equivalence is also known as equality, coincidence, and exclusive-NOR. mariaramilaisidrojimenez XUCC

BOOLEAN FUNCTIONS

mariaramilaisidrojimenez

XUCC

BOOLEAN FUNCTIONS
Extension to multiple inputs A gate can be extended to have multiple inputs if the binary operation it represents is commutative and associative. The AND and OR operations, defined in Boolean algebra, possess these two properties. The NAND and NOR functions are commutative but not associative. To overcome this difficulty, we define the multiple mariaramilaisidrojimenez NOR(or NAND) gate as a XUCC

BOOLEAN FUNCTIONS
Extension to multiple inputs Complemented OR(or AND) gate. Thus by definition, we have: x y z = (x + y + z) x y z = (xyz) The exclusive-OR and equivalence gates are both commutative and associative and can be extended to more than two inputs. However, multiple-input exclusive-OR gates mariaramilaisidrojimenez XUCC

BOOLEAN FUNCTIONS
are uncommon from the hardware standpoint. The exclusive-OR is an odd function, i.e., it is equal to 1 if the input variables have an odd number of 1s. The equivalence function is an even function, i.e.,it is equal to 1 if the input variables have an even number of 0s.

mariaramilaisidrojimenez

XUCC

BOOLEAN FUNCTIONS

mariaramilaisidrojimenez

XUCC

BOOLEAN FUNCTIONS

mariaramilaisidrojimenez

XUCC

BOOLEAN FUNCTIONS

mariaramilaisidrojimenez

XUCC