Boolean Logic

Logic is the "Science of Reasoning" (John Stuart Mill)

Example 1:

"If it is raining then I will take an umbrella"

• "It is raining" can be True or False

• "I will take an umbrella" can be True or False

The truth value of "take an umbrella" depends on the truth value of "raining"

In the form of a table:

raining umbrella False False True True

Called a TRUTH TABLE - can use it to make a DECISION:

• (take umbrella) = (raining)

"If it is raining or the weather forecast is bad then I will take an umbrella"

As a Truth Table:

raining bad forecast umbrella False False False False True True True False True True True True

• (take umbrella) = ((raining) or (bad forecast))

Example 3:

"If it is raining and I have no car then I will take an umbrella"

As a Truth Table:

raining no car umbrella False False False False True False True False False True True True

• (take umbrella) = ((raining) and (not(car))

Examples from Duncan Gillies

Digital Logic

Computers can make decisions using Logic

Basic Logical Operations are:

• Not
• And
• Or
• Exclusive Or (Xor)

Also:

• Not-And (Nand)
• Not-Or (Nor)

Computers operate electronically, using Logic Gates

• 1 or more Inputs
• 1 output

Inputs and outputs: 1 binary digit (0 or 1)

• 0 = False
• 1 = True

Electronic circuits, usually written as symbols, easily connected to perform more complex functions, form the basic "building blocks" of computers

Logic Gates

• NOT Gate

  a x  0   1   1   0

• AND Gate

  a b x  0   0   0   0   1   0   1   0   0   1   1   1

• OR Gate

  a b x  0   0   0   0   1   1   1   0   1   1   1   1

• XOR Gate

  a b x  0   0   0   0   1   1   1   0   1   1   1   0

More complex gates can be made by:

• Adding more inputs

3-input AND Gate



Applies to AND, OR, XOR - Any number of inputs

• Negating the output

NAND Gate



NOT-AND = NAND - Equivalent to AND followed by NOT

Similarly: NOT-OR = NOR

Logic Circuits

Combine gates into logic circuits to perform useful functions

"take umbrella" is True when "raining" is True AND "have car" is False (NOT TRUE)

Need NOT gate and AND gate

As a Truth Table:

raining NOT car umbrella 0 0 0 0 1 0 1 0 0 1 1 1

Practical Digital Circuits

Various physical forms. Most common is the dual in-line package.

Pin assignments for TTL type 7400 IC device

Also see: 7400 series TTL ICs at the Chip Directory

Boolean Algebra

From the graphical representation of circuit diagrams and the truth tables for the gates used, the output values of the circuit can be calculated for any given combination of input values. The same calculations can be done by a special algebraic method called Boolean algebra, first formalised by George Boole in 1847. Claude E. Shannon first extended this algebra in 1939 to binary gates, circuits and binary time-varying systems. Today, Boolean algebra is the formal foundation of digital circuit design.

Danger! Warning!

Infuriatingly, there is no single agreed representation for the logical operators in Boolean algebra:

A AND B	º	A • B	º	A Ù B	º	A & B	º	AB
A OR B	º	A + B	º	A Ú B	º	A | B
A XOR B	º	A Å B
NOT A	º	A¢	º	Ø A	º	A	(with a bar on top)

requires Symbol font installed to display properly

Algebraic Manipulation

The purpose of any algebra is to manipulate expressions without necessarily evaluating them.

Boolean Algebra has many manipulation rules, for example, concerning negation:

(A')' = A
A•A' = 0
A+A' = 1

These may be verified by a truth table.

The normal laws of algebra apply:

• Associative

  (A•B)•C = A•(B•C)
  (A+B)+C = A+(B+C)

• Commutative

  A•B = B•A
  A+B = B+A

• Distributive

  A•(B+C) = A•B + A•C
  A+(B•C) = (A+B) • (A+C) - note precedence of operators

Simplification Rules

Allow reducing the complexity of Boolean expressions.

Single variables:

A•A = A
A+A = A

Simplification rules with 1 and 0:

A•0 = 0
A•1 = A
A+0 = A
A+1 = 1

Note: in all these simplification rules A and B can be any Boolean expression. Thus

(P•(Q+R)+S)•0 = 0

de Morgan's Rules: (A + B)' = A' • B' (A • B)' = A' + B' as before, A and B can be any Boolean expression Can generalise to n Boolean variables: (A + B + C + D + ...)' = A' • B' • C' • D' • ... (A • B • C • D • ...)' = A ' + B' + C' + D' + ...

Also:

A Å B = A • B' + A' • B

Complement Law for XOR

(AÅB)' = AÅB' = A'ÅB

some content from Chris Hand

last updated: 19-Oct-05 Ian Harries <ih@doc.ic.ac.uk>