Jump to content

Unit 1.4.3 Boolean Algebra

From Wikibooks, open books for an open world


Logic Gates

[edit | edit source]

The letters above each column correspond to inputs and outputs; Usually the first two sequential letters in the alphabet are inputs, then the letters to the right of those are the outputs, for example in the AND Gate, A & B are inputs while Q is an output.

AND Gate

[edit | edit source]
AND Gate.

Truth Table:

A B Q
0 0 0
0 1 0
1 0 0
1 1 1

OR Gate

[edit | edit source]
OR Gate.

Truth Table:

C D R
0 0 0
0 1 1
1 0 1
1 1 1
NOT Gate.

NOT Gate

[edit | edit source]

Truth Table:

E S
0 1
1 0

NAND Gate

[edit | edit source]
NAND Gate.

Truth Table:

F G T
0 0 1
0 1 1
1 0 1
1 1 0

NOR Gate

[edit | edit source]

Truth Table:

NOR Gate.
H I U
0 0 1
0 1 0
1 0 0
1 1 0
XOR Gate.

XOR Gate

[edit | edit source]

Truth Table:

J K V
0 0 0
0 1 1
1 0 1
1 1 0

Boolean Algebra

[edit | edit source]

Notation

[edit | edit source]

OCR will be using the mathematicians style of syntax for questions in the exam, but conversion to the engineers syntax is simple and makes simplifying the algebra easier.

Statement Syntax (Mathematicians) Syntax (Engineers) Syntax (Engineers)
A AND B
A OR B
NOT A
A XOR B

Laws of Boolean Algebra

[edit | edit source]

Commutative Law

[edit | edit source]

Associate Law

[edit | edit source]

Distributive Law

[edit | edit source]

Identity Law

[edit | edit source]

Negation Law

[edit | edit source]

Absorption Law

[edit | edit source]

Redundancy Law

[edit | edit source]

De Morgan's Laws

[edit | edit source]

Other Laws

[edit | edit source]

Karnaugh Maps

[edit | edit source]

These maps use pattern recognition to simplify boolean expressions. Tables of possible inputs are mapped against all possible outputs:

e.g.

A Karnaugh map with 4 variables, A,B,C & D

To solve this map, initially the coloured squares must be created. Any binary values of 1 are grouped together into groups of 1, 2, 4, 8 etc. Then look at each coloured block and identify what components do not change:

In the Gold block (left hand square) the values of C & A do not change from 0, therefore this block is:

In the Brown block (left hand rectangle) the values of A and B do not change, therefore this block is:

In the red block (right hand square) the values of A and C do not change, therefore this block is:

In the green block (right hand rectangle) the values of A and B do not change, therefore this block is:

In the grey-blue block (middle centre) the values of B, C and D do not change, therefore this block is:

Finally in the bottom purple/blue block, the values of B, C and D do not change, therefore this block is:

These values can then all be combined:

There are certain rules for these Karnaugh maps:

  • The groups cannot contain 0s
  • The groups cannot be diagonal
  • The groups must be as large as possible
  • The groups must contain 1,2,4 or 8 in a block
  • The groups are allowed to overlap
  • The groups can wrap around either end of the map
  • Aim for the smallest number of groups

Adder & Flip-Flop Circuits

[edit | edit source]

Half Adder

[edit | edit source]

Truth Table:

A B S C
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

Where S is A XOR B and C is A AND B

Full Adder

[edit | edit source]

Truth table:

A B Cin S Cout
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

This is a combination of 2 half adders and an OR gate.

Flip Flops

[edit | edit source]

These circuits are capable of storing information.

Truth Table:

A B P Q
0 0 1 1
0 1 1 0
1 0 0 1
1 1 0 1
1 1 1 0

As shown above for the final two values, the circuit can exist in either state depending on the previously stored values.

D-Type Flip Flop

[edit | edit source]
D-type flip-flop
Logic circuit for a D-type flip-flop.

A D-Type flip-flop is a logic circuit that can store one bit of information, flipping between two states. The D, in D-type flip flop, stands for delay.

A change is triggered when the clock is at a positive (leading) edge, the state of the control input is stored for the clock cycle. An example can be seen below.

The D-type flip flop has two inputs, the control () and the clock signal, along with two outputs, the stored data () and the inverse ().

You may be asked to complete the output signal for a diagram, like the above, given the control input and the clock.