Boolean Function and Expression

Preview text

DISCRETE STRUCTURES
Boolean Algebra

Boolean Algebra
•Boolean algebra provides the operations and the rules for working with the set {0, 1}. •These are the rules that underlie electronic circuits, and the methods we will discuss are fundamental to VLSI design. •We are going to focus on three operations: • Boolean complementation, • Boolean sum, and • Boolean product

Spring 2003

CPCS - Discrete Structures

2

Boolean Operations
•The complement is denoted by a bar (on the slides, we will use a minus sign). It is defined by •-0 = 1 and -1 = 0.
•The Boolean sum, denoted by + or by OR, has the following values: •1 + 1 = 1, 1 + 0 = 1, 0 + 1 = 1, 0 + 0 = 0
•The Boolean product, denoted by  or by AND, has the following values: •1  1 = 1, 1  0 = 0, 0  1 = 0, 0  0 = 0

Spring 2003

CPCS - Discrete Structures

3

Boolean Functions and Expressions
•Definition: Let B = {0, 1}. The variable x is called a Boolean variable if it assumes values only from B. •A function from Bn, the set {(x1, x2, …, xn) |xiB, 1  i  n}, to B is called a Boolean function of degree n.
•Boolean functions can be represented using expressions made up from the variables and Boolean operations.

Spring 2003

CPCS - Discrete Structures

4

Boolean Functions and Expressions
•The Boolean expressions in the variables x1, x2, …, xn are defined recursively as follows: • 0, 1, x1, x2, …, xn are Boolean expressions. • If E1 and E2 are Boolean expressions, then (-E1),
(E1E2), and (E1 + E2) are Boolean expressions.
•Each Boolean expression represents a Boolean function. The values of this function are obtained by substituting 0 and 1 for the variables in the expression.

Spring 2003

CPCS - Discrete Structures

5

Boolean Functions and Expressions
•For example, we can create Boolean expression in the variables x, y, and z using the “building blocks” 0, 1, x, y, and z, and the construction rules: •Since x and y are Boolean expressions, so is xy. •Since z is a Boolean expression, so is (-z). •Since xy and (-z) are expressions, so is xy + (-z). •… and so on…

Spring 2003

CPCS - Discrete Structures

6

Boolean Functions and Expressions
•Example: Give a Boolean expression for the Boolean function F(x, y) as defined by the following table:

x

y

F(x, y)

0

0

0

0

1

1

1

0

0

1

1

0

Possible solution: F(x, y) = (-x)y

Spring 2003

CPCS - Discrete Structures

7

Boolean Functions and Expressions

•Another Example:

x y z F(x, y, z)

000

1

001

1

010

0

011

0

1 00

1

101

0

1 10

0

111

0

Possible solution I: F(x, y, z) = -(xz + y)
Possible solution II: F(x, y, z) = (-(xz))(-y)

Spring 2003

CPCS - Discrete Structures

8

Boolean Functions and Expressions
•There is a simple method for deriving a Boolean expression for a function that is defined by a table. This method is based on minterms.
•Definition: A literal is a Boolean variable or its complement. A minterm of the Boolean variables x1, x2, …, xn is a Boolean product y1y2…yn, where yi = xi or yi = -xi. •Hence, a minterm is a product of n literals, with one literal for each variable.

Spring 2003

CPCS - Discrete Structures

9

Boolean Functions and Expressions

•Consider F(x,y,z) again:

x y z F(x, y, z)

000

1

F(x, y, z) = 1 if and only if:
x = y = z = 0 or

001

1

010

0

011

0

1 00

1

101

0

1 10

0

111

0

x = y = 0, z = 1 or
x = 1, y = z = 0
Therefore,
F(x, y, z) = (-x)(-y)(-z) + (-x)(-y)z + x(-y)(-z)

Spring 2003

CPCS - Discrete Structures

10

Preparing to load PDF file. please wait...

0 of 0
100%