outline

Gates

• Electronic devices
  • built of transistors
• Implement truth tables
  • true = high voltage
  • false = low voltage

Computer Logic

• What is the smallest functional companent in a computer system?

Computer Logic 2

• Gone for the CSCI 230 lecture

Computer Logic 3

• Meet you at Kelly's pub

Mechanical realization of a switch

• When both pumps are ON, then there is no waterflow.

Mechanical realization of a switch 2

• When you turn the lower pumps off, water is allowed to passed.

Gate types

• Using water gates, we build the next level functional component in a digital system - the NOT, OR, & AND gates.

The NOT gate

• The logical operation of a NOT gate is:
  

  IN	OUT
  0	1
  1	0

The NOT gate 2

• Design a NOT gate using water pumps
• 

The OR gate

• The logical operation of an OR gate is:
  

  IN1	IN2	OUT
  0	0	0
  1	0	1
  0	1	1
  1	1	1

The OR gate 2

• Design the OR function using waterpumps
• 

The AND gate

• The logical operation of an AND gate is:
  

  IN1	IN2	OUT
  0	0	0
  0	1	0
  1	0	0
  1	1	1

The AND gate 2

• Design the AND function using water pumps
• 

A Logical Problem

• Ed will go to a certain party only id Dan or Carol goes.
• Dan will go if Ann goes and Bob does not
• Ann and Carol and Bob have decided not to go.
• Will Ed go to the party?

Logic Gate Symbols

• AND gate	OR gate	NOT gate

Ed's solution

• Does Ed go to the party?
• 

Ed's Solution 2

• A logic curcuit for the party problem:

  

BOOLEAN ALGEBRA

• Boolean algebra allows a symbolic & systematic approach to represent logical relationships.

BOOLEAN ALGEBRA 2

• In ordinary algebra, symbols (variables) represents quantities.
• Ex: x=$1.05 (price of a gollon of gas)

BOOLEAN ALGEBRA 3

• In Boolean algebra, symbols represents logical statements and the value can be only TRUE (=1) or FALSE (=0).

BOOLEAN ALGEBRA - Example

• Ex: It is sunny today.
• If r represents the above sentance, then
  

      r= TRUE   if it is sunny, and
      r=FALSE   if it is not sunny

BOOLEAN ALGEBRA - Example 2

• ~r is the opposite of r; ~~r = r.

• ~
  .
  +

Use of parentheses

• Ex:
  

       5 - 3 - 1 = ?
       5 - (3 - 1) = ?

• "()" tells which algerbra, the order is: (), NOT, AND, OR
  

  Ex:     ~~((p + ~p) . ~~q)
  

Boolean Logic

• George Boole, mid 1800s
• Algebra for logic
  • True/False values
  • Combinations of true/false with AND, OR, NOT
  • Truth tables

Typical Circuit

• Diagram of a typical circuit:

  

Circuit Diagram

• 

  There is a direct relationship between Boolean expressions and circuit diagrams of this type. Every Boolean expression can be represented pictorially as a circuit diagram, and every output value in a diagram can be written as a Boolean expression.

Circuit Diagram

• Above equals:

  c = (a OR b
  d = NOT ((a OR b)) AND (NOT b))

Diagram example

• In the previous example, if a = 1 and b, then the value on the c output line is 1, and the value on the d output line is 0. These values can be determined as follows:

  

Example

• Here is an example of the use of the NOT, OR , & AND:

  

One-bit compare-for-equality circuit

ADD Circuit

• Construct of a common ADDer diagram:

  

• Truth Table:
  

  Inputs			Outputs
  ai	bi	ci	si	ci+1