Transcript Boolean Functions

Fall 2012: FCM 708
Foundation I
Lecture 2
Prof. Shamik Sengupta
Email: [email protected]
Quick Recap…

Intro to Computer Architecture:
– Number system
– Decimal, Binary, Hexadecimal
– Unsigned and signed representations
– Hardware architecture
– A simplified model of the microprocessor structure
– Central Processing Unit (CPU)
– Arithmetic & Logic Unit (ALU)
– Control Unit (CU)
– Register Array
– System Bus
– Memory
– Overview of Instruction Execution Cycle
FCM 708: Sengupta
A quick look at a microprocessor architecture

Let us have some hand-on experience of what we have learnt so far

We will use a simple microprocessor simulator
– Motorola 68HC11
FCM 708: Sengupta
Boolean algebra and Logic gates
Objectives
 Understand the relationship between Boolean logic
and digital computer circuits
 Learn how to design simple logic circuits.
 Understand how digital circuits work together to form
complex computer systems.
FCM 708: Sengupta
Introduction
 In the latter part of the nineteenth century, George Boole
showed that logical thought could be represented through
mathematical equations
 Computers, as we know them today, are implementations of
Boole’s Laws of Thought
– John Atanasoff and Claude Shannon were among the first to see
this connection
FCM 708: Sengupta
What is Boolean algebra

Boolean algebra is an algebra for the manipulation of objects that
can take on only two values, typically true and false

Why Boolean algebra is so useful in computers?
– Because computers are built as collections of gates that are either “on”
or “off,” Boolean algebra is a very natural way to represent digital
information or compute information

Boolean functions are implemented in digital computer circuits called
gates (logic gates)
– A gate is an electronic device that produces a result based on two or
more input values
– All the microprocessor components are combinations of such logic gates
FCM 708: Sengupta
Boolean Operators

Most common Boolean operators are AND,
OR and NOT

A Boolean operator can be completely
described using a truth table

The truth table for the Boolean operators
AND, OR and NOT are shown here
FCM 708: Sengupta
Logic Gates

The three simplest gates are the AND, OR, and NOT gates.

They correspond directly to their respective Boolean operations, as
you can see by their truth tables

And these representations map exactly into the electric circuits of a
digital system
FCM 708: Sengupta
Detailed implementation picture of a
Logic Gate
Voltage inverted
from input
This is the logic for an
AND gate
74LS08
Quad 2-input AND
Voltage from
input
FCM 708: Sengupta
Logic Gates


Three other logic gates:
The output of the XOR
operation is true only when
the values of the inputs differ.
Note the special symbol 
for the XOR operation.
• Symbols for NAND and NOR, and
truth tables are shown at the right.
FCM 708: Sengupta
Logic Gates

NAND is known as universal gate
because they are inexpensive to
manufacture and any Boolean
function can be constructed using
only NAND gates.
FCM 708: Sengupta
Boolean Functions
 Boolean functions are composed of Boolean
variables and multiple logic operators
 NOT has the precedence over AND
 AND has the precedence over OR
FCM 708: Sengupta
Boolean Functions
 Digital computers contain circuits that implement
Boolean functions.
 The simpler that we can make a Boolean function, the
smaller the circuit that will result.
– Simpler circuits are cheaper to build, consume less power,
and run faster than complex circuits.
 With this in mind, we always want to reduce our
Boolean functions to their simplest form.
– Boolean identities
FCM 708: Sengupta
Boolean identities


Most Boolean identities have an AND (product) form as well as an
OR (sum) form.
We show our identities using both forms. Our first group is rather
intuitive:
FCM 708: Sengupta
Boolean identities
 Our second group of Boolean identities should be
familiar to you from your study of algebra:
FCM 708: Sengupta
Boolean identities
 Our last group of Boolean identities are perhaps
the most useful.
FCM 708: Sengupta
Simplification of Boolean Functions
 Let’s try some of these identities to simplify Boolean
Functions:
 F = AB + BBC + BCC
 F = A + B(A+C) + AC
FCM 708: Sengupta
Simplification of Boolean Functions
 Simplify the function:
FCM 708: Sengupta
Hand-on Practice

Multimedia Logic Simulator

Can be downloaded from http://www.softronix.com/logic.html

We will implement some of the simplest logic circuits
FCM 708: Sengupta
Digital Circuits and Boolean Algebra
 Using Boolean algebra to design various important
digital circuits implementation
– Designing a Burglar alarm
– Designing an adder
FCM 708: Sengupta
Reading Assignment
1. Boolean Algebra (In Blackboard)
FCM 708: Sengupta