Unit 1.4.3 Boolean Algebra

From Wikibooks, open books for an open world
Jump to navigation Jump to search


Logic Gates[edit]

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]

AND Gate.

Truth Table:

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

OR Gate[edit]

OR Gate.

Truth Table:

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

NOT Gate[edit]

Truth Table:

E S
0 1
1 0

NAND Gate[edit]

NAND Gate.

Truth Table:

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

NOR Gate[edit]

Truth Table:

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

XOR Gate[edit]

Truth Table:

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

Boolean Algebra[edit]

Notation[edit]

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]

Commutative Law[edit]

Associate Law[edit]

Distributive Law[edit]

Identity Law[edit]

Negation Law[edit]

Absorption Law[edit]

Redundancy Law[edit]

De Morgan's Laws[edit]

Other Laws[edit]

Karnaugh Maps[edit]

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]

Half Adder[edit]

Half Adder.svg

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]

Full-adder.svg

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]

These circuits are capable of storing information.

Flip flop circuit.png

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]

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.

D-type flip-flop impulse diagram.png

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.