# Boolean Function and Expression

Download 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) |xiB, 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

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) |xiB, 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

## Categories

## You my also like

### Simplification And Minimization Of Boolean Functions

796.1 KB36.9K7.8K### Conversion between Logic and Algebraic Expressions of Boolean

385.1 KB2.8K558### CS61c: Representations of Combinational Logic Circuits

347.8 KB30.9K6.2K### Lattice And Boolean Algebra

1.2 MB4K767### Objectives Chapter 4: Control Structures I (Selection)

1.5 MB58.8K15.3K### Lecture 7 Logic Simplification

765.3 KB11.1K3.5K### Propositional Calculus: Boolean Algebra and Simplification

319.3 KB16K1.9K### Overview Write Equivalent Expressions Involving Rational Numbers

5.1 MB18K3.8K### QUESTION BANK – BOOLEAN ALGEBRA

526.5 KB18.1K8.7K