程序代写代做代考 Boolean algebra and logic

Boolean algebra and logic

BOOLEAN

ALGEBRA AND LOGIC

Bernhard Kainz (with thanks to A. Gopalan, N. Dulay and E.

Edwards)

b.kainz@imperial.ac.uk

mailto:b.kainz@imperial.ac.uk

Learning Objectives

• At the end of this lecture you should:

• Understand how logic relates to computing problems

• Be able to represent Boolean logic problems as:

• Truth tables

• Logic circuits

• Boolean algebra

What is Logic?

• Dictionary definitions (dictionary.com – reduced!)

• reason or sound judgement

• a system of principles of reasoning

• the science that investigates the principles governing correct or

reliable inference

• Branch of philosophy

• Principles of inference

• You use logic all the time in your everyday life

Propositional Logic

• The Ancient Greek philosophers created a system to

formalise arguments called propositional logic

• A proposition is a statement that can be TRUE or FALSE

• Propositions can be compounded by means of the

operators AND, OR and NOT

Propositional Logic Example

• Propositions may be TRUE or FALSE, for example:

• It is raining

• The weather forecast is bad

• A combined proposition example is:

• It is raining OR the weather forecast is bad

Propositional Logic Example

• Can assign values to propositions, for example: I will take

an umbrella if it is raining OR the weather forecast is bad

• Means that the proposition “I will take an umbrella” is the result of

the Boolean combination (OR) between raining and weather

forecast being bad. In fact we could write:

• I will take an umbrella = it is raining OR the weather forecast is bad

Diagrammatic Representation

• Can think of the umbrella proposition as a result that we

calculate from the weather forecast and the fact that it is

raining by means of a logical OR

Truth Tables

• Since propositions can only take two values, we can

express all possible outcomes of the umbrella proposition

by a table

Complex Propositions

• Can make our propositions more complex, for example:

• (Take Umbrella ) = ( NOT (Take Car ) ) AND ( (Bad Forecast ) OR

(Raining ) )

• Diagrammatical representation

Boolean Logic

• To perform calculations quickly and

efficiently we need a more succinct

notation than propositional logic

• Need to have well-defined semantics

for all the “operators”, or connectives

that we intend to use

• Boolean Algebra satisfies the criterion

above

• Named after George Boole

• Provides a system of logical operations

• Rules for combining operations

• Describes their application to binary

numbers

George Boole: 1815-1864

Boolean Algebra – Fundamentals

• The truth values are replaced by 1 and 0

• 1 = TRUE 0 = FALSE

• Propositions are replaced by variables

• R = it is raining W = The weather forecast is bad

• Operators are replaced by symbols

• ‘ = NOT + = OR • = AND

Boolean Algebra – Simplify Propositions

• Recall:

• (Take Umbrella ) = ( NOT (Take Car ) ) AND ( (Bad Forecast ) OR

(Raining ) )

• Using notations notations, we get:

• U = (C’) • (W + R)

Boolean Algebra – Precedence

• Operator Precedence
• Highest precedence operator is evaluated first

• Note that: (C’) • (W + R) is not the same as C’ • W + R

• Logic operators in, e.g., C:

• Logical: AND: && OR: || NOT: !

• (Binary: AND: & OR: | NOT: ~)

(ᴧ)

(ᴠ)

(¬)

math (logic) symbol

Boolean Algebra – Truth Tables

• All possible outcomes of the operators can be written as

truth tables

Boolean Algebra – Truth Tables

• Given any Boolean expression e.g.: U = C’ • (W + R)

• We can calculate a truth table for every possible value of

the variables on the right hand side

• For n variables there are 2n possibilities

Boolean Algebra – Truth Tables

• Truth table for “Umbrella”

• U = C’ • (W + R)

Boolean Algebra – Rules

• Note: A and B can be any Boolean Expression

Negation:

(A’)’ = A

A • A’ = 0

A + A’ = 1

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 the precedence

Boolean Algebra – Rules

Single variables (Idempotent law):

A • A = A

A + A = A

Simplification rules with 1 and 0:

A • 0 = 0

A • 1 = A

A + 0 = A

A + 1 = 1

Boolean Algebra – de Morgan’s Rule

(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 • … • X)’ = A ‘ + B’ + C’ + D’ + … + X’

Boolean Functions – Schematic

Representation
• A standard set of easy-to-recognise symbols is used to

represent Boolean functions

• A circle is all that is required to indicate NOT. The triangle

is just to indicate Input/Output direction

Inverting Functions

• A circle can be added to the AND and OR symbol outputs

to create their inverted functions – NotAnd (NAND) and

NotOr (NOR) gates

Building Blocks for Circuits

• NAND/NOR are the commonly used building blocks for

most circuits

• NAND / NOR can easily be constructed from transistors

• NAND is complete

• A set of Boolean functions f1,f2,… is “complete” if and only if any

Boolean function can be generated by a combination these functions

• Also called “universal gate”

NAND Gate – NOT

• It is possible to build all other gates out of NAND gates

• Create a NOT gate using the Idempotent law:

• A • A = A therefore (A • A)’ = A’

NAND Gate – AND

• Create an AND gate using the Involution law:

• (A’)’ = A

(A • B)’

NAND Gate – OR / NOR

• To make an OR gate we need to apply de Morgan’s

theorem:

• A + B = (A’ • B’)’

• Just invert output to get a NOR gate ☺

NAND – Complex Circuits

• Consider two cascading NAND Gates

• What circuit have we created?

• Use Boolean Algebra to find out

• I = (B • C)’

• X = (A • I)’ = (A • (B • C)’)’

• Apply de Morgan’s law, we get

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

NAND – Complex Circuits

• Truth table for X = A’ + (B • C)

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

0 0 0 0 1

0 0 1 0 1

0 1 0 0 1

0 1 1 1 1

1 0 0 0 0

1 0 1 0 0

1 1 0 0 0

1 1 1 1 1

XOR and XNOR Gates

• Very useful gates

Behind the scenes

• Instantaneous on IC?

V-

V+

?

Behind the scenes

• Instantaneous on IC?

V-

V+

?

Behind the scenes

• Time delay and saturation limit state ‘switching’ speed of

real in-silico circuits

V-

V+

?

∆t

Behind the scenes

• Transistor-transistor logic TTL NAND gate

Behind the scenes

• CMOS NAND in silico

Behind the scenes