BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

MODULE - 01
1.1 Binary Logic
a)Definition of Binary Logic
 Binary logic consists of binary variables and a set of logical operations.
 The variables are Designated by letters of the alphabet, such as A, B, C, x, y, z, etc.,
with each variable having only two distinct possible values: 1 and 0.
 There are three basic logical operations: AND, OR, and NOT. Each operation
produces a binary result, denoted by z.
AND:
 This operation is represented by a dot or by the absence of an operator.
 For example,
x .y = z or xy=z is read “x AND y is equal to z.”
 The output z = 1 if and only if x = 1 and y = 1; otherwise z = 0.
 The truth table for AND operation is

OR:
 This operation is represented by a plus sign.
 For example,
x + y = z is read “x OR y is equal to z,”

 The output z = 1 if x = 1 or if y = 1 or if both x = 1 and y = 1. If both x = 0 and y

= 0, then z = 0.

NOT:

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 1

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

 This operation is represented by a prime (sometimes by an overbar).

 For example,
x = z‟ (or x= z)
is read “not x is equal to z,”
 The output z = 0 if x=1, and z = 1 if x=0.
 The NOT operation is also referred to as the complement operation.
 The truth table for NOT operation is

INPUT OUTPUT

X Z

0 1
1 0
b) Logic Gates

 Logic gates are electronic circuits that operate on one or more input
signals to produce an output signal. The symbolef for basic gates are
shown in figure 1.1.

FIGURE 1.1 Symbols for digital logic circuits

 Electrical signals such as voltages or currents exist as analog signals

having values over a given continuous range, say, 0 to 3 V, but in a
digital system these voltages are interpreted to be logic 1 or logic 0.
 The signal levels for binary logic values is shown in figure 1.2 below.

FIGURE 1.2 Signal levels for binary logic values

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 2

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

 The timing diagram for the basic gates illustrated in figure 1.3. It
contains input signals x and y together with the corresponding output
signal for each gate.

FIGURE 1.3 Input-output signals for gates

 An AND gate with three inputs and an OR gate with four inputs are
shown in Fig. 1.4.

FIGURE 1.4 Gates with multiple inputs

1.2 Basic theorem’s and properties of boolean algebra

a) Duality
 The important property of Boolean algebra is called the duality
principle and states that every algebraic expression deducible from
the postulates of Boolean algebra remains valid if the operators and
identity elements are interchanged.

b)Basic Theorems
 There are six theorems of Boolean algebra and four postulates.
 The postulates are basic axioms of the algebraic structure and need no proof.
The theorems must be proven from the postulates.

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 3

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

 Table 1.5 lists six theorems of Boolean algebra and four of its postulates.

FIGURE 1.5: Basic theorems and postulates of Boolean algebra

 Proofs of the theorems :

THEOREM 1:

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 4

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

THEOREM 2:

THEOREM 3: (x')' = x.
 From postulate 5, we have x + x' = 1 and x. x' = 0, which together define the
complement of x. The complement of x' is x. Therefore we have (x')' = x.

THEOREM 6: Absorption theorem

 The theorems of Boolean algebra can be proven by means of truth tables. The
following truth table verifies the first absorption theorem:

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 5

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

THEOREM 5: DeMorgan’s theorem

The truth table for the first DeMorgan‟s theorem, (x + y)' = x'y', is as follows:

Operator Precedence

 The operator precedence for evaluating Boolean expressions is

(1) Parentheses,
(2) NOT,
(3) AND
(4) OR.

1.3 BOOLEAN FUNCTIONS

 Boolean algebra is an algebra that deals with binary variables and logic operations.

 A Boolean function described by an algebraic expression consists of binary

variables, the constants 0 and 1, and the logic operation symbols.

 For a given value of the binary variables, the function can be equal to either 1 or 0.

 Example:

Consider ,

F1 = x + y’z

 The function F1 is equal to 1 if x is equal to 1 or if y‟z is equal to 1.

 F1 is a Boolean function can be represented as in the truth table 1.1.

 The number of rows in the truth table is 2n and it ranges from 0 through 2n - 1, where
n is the number of variables in the function.

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 6

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

Table 1.1: Truth table for F1

 A Boolean function can be transformed from an algebraic expression into a circuit
diagram composed of logic gates connected in a particular structure.
 The logic‐circuit diagram (also called a schematic) for F1 is shown in Fig.16.

FIGURE 1.6 Gate Implementation of F1= x+y’z

 In logic‐circuit diagrams, the variables of the function are taken as the inputs of the
circuit and the binary variable F1 is taken as the output of the circuit.
 Consider, for example, the following Boolean function:
F2 = x‟y‟z + x‟yz + xy‟

 The logic circuit diagram for F2 is shown in fig. 1.7 below.

FIGURE 1.7 Implementation of Boolean function F2 with gates

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 7

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

 The truth table for F2 is listed in Table 1.2

Table 1.2: Truth table for F2

 Now consider the possible simplification of the function by applying some of the
identities of Boolean algebra:

F2 = x‟y‟z + x‟yz + xy‟

= x‟z(y‟ + y) + xy‟
= x‟z + xy‟

 The logic circuit diagram for F2 is shown in fig. 1.8 below.

FIGURE 1.8 Implementation of Boolean function F2 with gates.

 The circuit in figure 1.8 is simpler than the one in figure 1.7, yet both implement the
same function. Both expressions produce the same truth table, they are equivalent.
 Therefore, the two circuits have the same outputs for all possible binary
combinations of inputs of the three variables.

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 8

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

Example 1.1: Simplify the following Boolean functions to a minimum number of

literal.

 Function 5 is not minimized directly, but can be derived from the dual of the
steps used to derive function 4. Functions 4 and 5 are together known as the
consensus theorem.
Complement of a Function

 The complement of a function F is F‟ and may be derived algebraically through

DeMorgan‟s theorems.
 DeMorgan‟s theorems for two variables have been already listed and proved and now
it can be extended to three or more variables.
 The three‐variable form of the first DeMorgan‟s theorem is derived as follows, from
postulates and theorems of Boolean algebra.

 This implies DeMorgan‟s theorems can be applicable for any number of variables.
 The generalized DeMorgan‟s theorem for any number of variable is

 The generalized form of DeMorgan‟s theorems states that the complement of a

function is obtained by interchanging AND and OR operators and complementing
each literal.

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 9

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

EXAMPLE1.2: Find the complement of the functions F1 = x’yz’+ x’y’z and F2 = x(y’z’
+ yz) by applying DeMorgan’s theorems.

EXAMPLE 1.3: Find the complement of the functions F1 and F2 of Example 1.2 by
taking their duals and complementing each literal.

Digital Logic Gates

 Since Boolean functions are expressed in terms of AND, OR, and NOT
operations, it is easier to implement a Boolean function with these type of gates.
 Still, the possibility of constructing gates for the other logic operations is of
practical interest.
 Factors to be weighed in considering the construction of other types of logic gates
are
1. The feasibility and economy of producing the gate with physical components,
2. The possibility of extending the gate to more than two inputs,
3. The basic properties of the binary operator, such as commutativity and
associativity.
4. The ability of the gate to implement Boolean functions alone or in conjunction
with other gates.

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 10

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

FIGURE 1.8 Digital logic gates

 Each gate has one or two binary input variables, designated by x and y, and one
binary output variable, designated by F.
 The inverter circuit inverts the logic sense of a binary variable, producing the
NOT, or complement, function. The small circle in the output of the graphic

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 11

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

symbol of an inverter (referred to as a bubble) designates the logic complement.

 The triangle symbol by itself designates a buffer circuit. A buffer produces the
transfer function and binary value of the output is equal to the binary value of the
[Link] circuit is used for power amplification of the signal and is equivalent to
two inverters connected in cascade.
 The NAND function is the complement of the AND function, as indicated by a
graphic symbol that consists of an AND graphic symbol followed by a small
circle.
 The NOR function is the complement of the OR function and uses an OR graphic
symbol followed by a small circle.
 NAND and NOR gates are called as universal gates.

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 Commutative
property and associative property.
 For the OR function, we have
x+y = y+x (Commutative)
(x+y)+z = x+(y+z) = x+y+z (Associative)

 For the AND function we have,

x.y = y.x (Commutative)
x.(y.z) = (x.y).z = x.y.z (Associative)
 Which indicates that And and OR function can be extended to multiple inputs.
 The NAND and NOR functions are commutative, and their gates can be extended to
have more than two inputs
 But NAND and NOR operators are not associative( (x↓y) ↓z ≠ x↓(y↓z) ) as shown in
as shown in Fig. 1.9 and the following equation.

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 12

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

 Hence it is proved that

FIGURE 1.9 Demonstrating the nonassociativity of the NOR operator:

 To overcome this difficulty,

a. we define the multiple NOR gate as a complemented OR gate. Thus, by
definition, we have

b. we define the multiple NAND gate as a complemented AND gate. Thus, by

definition, we have

 The graphic symbols for the three‐input gates are shown in Fig. 1.10

 The exclusive‐OR and equivalence gates are both commutative and associative and
can be extended to multiple inputs. The construction of a three‐input exclusive‐OR
function is shown in Fig. 1.11. This function can be implemented by cascading two‐
input gates, as shown in (a) and it can be represented with a single three‐input gate, as
shown in (b) and the truth table is shown in (c).

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 13

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

FIGURE 1.11 Three‐input exclusive‐OR gate

Positive and Negative Logic

 The binary signal at the inputs and outputs of any gate has one of two values, logic 1
and logic 0.
 The higher signal level is designated by H and the lower signal level by L.
 Choosing the high‐ level H to represent logic 1 defines a positive logic system as
shown in fig 1.12(a).
 Choosing the low‐level L to represent logic 1 defines a negative logic system
shown in fig 1.12(b).

FIGURE 1.12 Signal assignment and logic polarity

 Consider, for example, the electronic gate and the truth table as shown in fig below.

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 14

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

 Now, assume a positive logic assignment, with H = 1 and L = 0, then we will get
truth table which is same as the one for the AND operation as shown in Fig.1.13(a)
The graphic symbol for a positive logic AND gate is shown in Fig.1.13(b).

(a)Truth table for positive logic (b) Positive logic AND gate.

FIGURE 1.13 Demonstration of Positive logic

 Now, assume a negative logic assignment, with H = 0 and L = 1, then we will get
truth table which is same as the one for the OR operation as shown in Fig.1.14 (a).
The graphic symbol for a negative logic OR gate is shown in Fig.1.14(b).

(a)Truth table for negative logic (b) negative logic OR gate.

FIGURE 1.14 Demonstration of Negative logic

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 15

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

Gate-Level Minimization
 Gate-level minimization is the design task of finding an optimal gate-level
implementation of the Boolean functions describing a digital circuit.
 It is difficult to execute by manual methods when the logic has more than a few
inputs buy by using computer-based logic synthesis tools can minimize a large set of
Boolean equations efficiently and quickly.
The Map Method
 The complexity of the digital logic gates that implement a Boolean function is
directly related to the complexity of the algebraic expression from which the
function is implemented.
 These Boolean expressions can be simplified by using Algebraic techniques but
simplification by using this technique may become complex for larger expressions.
 The map method presented here provides a simple, straightforward procedure for
minimizing Boolean functions.
 This method may be regarded as a pictorial form of a truth table. The map method
is also known as the Karnaugh map or K-map.
 Karnaugh map/K map is a method simplifying and manipulating switching
functions. K map method is faster and easier to apply than other simplification
methods.
 A K-map is a diagram made up of squares, with each square representing one
minterm of the function that is to be minimized.

Two-Variable K-Map
The two-variable K-map is shown in Fig. 1.15 (a) and (b)
a) There are four minterms for two variables; hence, the map consists of four
squares, one for each minterm.
b) to show the relationship between the squares and the two variables x and y .
The 0 and 1 marked in each row and column designate the values of
variables. Variable x appears primed in row 0 and unprimed in row 1.
Similarly, y appears primed in column 0 and unprimed in column 1.

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 16

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

FIGURE 1.15 Two-variable K-map

EXAMPLE:1.4 Simplify the Boolean function F(x,y) = ∑(1,2,3)

Simplified expression F = x+y

Three-Variable K-Map
 A three-variable K-map is shown in Fig. 1.16 . There are eight minterms for three
binary variables; therefore, the map consists of eight squares.

 Note that the minterms are arranged, not in a binary sequence, but in a sequence
similar to the Gray code. The characteristic of this sequence is that only one bit
changes in value from one adjacent column to the next.

FIGURE 1.16 Three-variable K-map

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 17

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

EXAMPLE:1.4 Simplify the Boolean function F(x,y,z) = ∑(2,3,4,5)

The simplified Expression is F = x’y + xy’

EXAMPLE:1.5 Simplify the Boolean function F(x,y,z) = ∑(3,4,6,7)

The simplified Expression is F = xz’ + yz

EXAMPLE:1.6 Simplify the Boolean function F(x,y,z) = ∑(0,2,4,5,6)

The simplified Expression is F = z’ + x y’

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 18

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

EXAMPLE:1.7 For the Boolean function F = ac’ + a’b + ab’c + bc

a. Express this function as a sum of minterms.
b. Find the minimal sum-of-products expression.

a.

The function can be expressed in sum-of-minterms form as

b.

The minimal sum-of-products expression is F= c+a’b

FOUR-VARIABLE K-MAP

 A four variable K-map is shown in fig 1.17. There are eight minterms for three
binary variables; therefore, the map consists of eight squares.
 The rows and columns are numbered in a Gray code sequence, with only one digit
changing value between two adjacent rows or columns. The minterm corresponding
to each square can be obtained from the concatenation of the row number with the
column number.
 The map minimization of four-variable Boolean functions is similar to the method
used to minimize three-variable functions. Adjacent squares are defined to be
squares next to each other.
 The combination of adjacent squares that is useful during the simplification process
is easily determined from inspection of the four-variable map:

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 19

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

 One square represents one minterm, giving a term with four literals.
 Two adjacent squares represent a term with three literals.
 Four adjacent squares represent a term with two literals.
 Eight adjacent squares represent a term with one literal.
 Sixteen adjacent squares produce a function that is always equal to 1.

FIGURE 1.17 Four-variable map

EXAMPLE 1.8 :Simplify the Boolean function

The simplified Expression is F = y’ + w’z’ + xz’

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 20

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

EXAMPLE 1.9 : Simplify the Boolean function F = A’B’C’ + B’CD’ + A’BCD’ + AB’C’

The simplified Expression is F = B’D’ + B’C’ + A’CD’

Prime Implicants
 In choosing adjacent squares in a map, we must ensure that
o all the minterms of the function are covered when we combine the squares,
o the number of terms in the expression is minimized, and
o there are no redundant terms.

 Sometimes there may be two or more expressions that satisfy the simplification
criteria. The procedure for combining squares in the map may be made more
systematic if we understand the meaning of two special types of terms.
 A prime implicant is a product term obtained by combining the maximum
possible number of adjacent squares in the map. If a minterm in a square is
covered by only one prime implicant, that prime implicant is said to be essential.

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 21

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

 The prime implicants of a function can be obtained from the map by

combining all possible maximum numbers of squares. This means that a
single 1 on a map represents a prime implicant if it is not adjacent to any other
1‟s. Two adjacent 1‟s form a prime implicant, provided that they are not within a
group of four adjacent squares. Four adjacent 1‟s form a prime implicant if they
are not within a group of eight adjacent squares, and so on.
 The essential prime implicants are found by looking at each square marked with
a 1 and checking the number of prime implicants that cover it. The prime
implicant is essential if it is the only prime implicant that covers the minterm.
 Consider the following four-variable Boolean function:

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 22

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

 From this we can say that, there are four possible ways that the function can be
expressed with four product terms of two literals each:

 Therefore, from the above functions we can say that

Prime implicants : BD + B’D’ + CD + AD + AB’ + B’C
Essential Prime Implicants : BD + B’D’

Five-Variable Map
 Maps for more than four variables are not as simple to use as maps for four or
fewer variables.
 A five-variable map needs 32 squares and a six-variable map needs 64 squares.
 When the number of variables becomes large, the number of squares
becomes excessive and the geometry for combining adjacent squares
becomes more involved.
 Maps for more than four variables are difficult to use and will not be
considered here.

Don’t – care Conditions

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 23

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

 Functions that have unspecified outputs for some input combinations are called
incompletely specified functions.
 The unspecified minterms of a function are called as don’t-care conditions.
 A don’t-care minterm is a combination of variables whose logical value is not
specified.
 To distinguish the don‟t-care condition from 1‟s and 0‟s, an X is used.
 Thus, an X inside a square in the map indicates that we don‟t care whether the value is
„0‟ or „1‟.

EXAMPLE 1.10 : Simplify the Boolean function

which has the don‟t-care conditions

FIGURE 1.25 Example with don’t-care conditions

 In Fig. 1.25(a), don‟t-care minterms 0 and 2 are included with the 1‟s, resulting in
the simplified Function
F = yz + w’x’

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 24

 BCS302 | DIGITAL DESIGN & COMPUTER ORGANIZATION |

 In Fig. 1.25(b), don‟t-care minterm 5 is included with the 1‟s, and the simplified
function is now
F = yz + w’z

Prof. Divya A K, CS$E Dept. KVGCE, Sullia Page 25