# A-level Computing/OCR/Unit 1.4.3 Boolean Algebra
## Logic Gates

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

Truth Table:
| A | B | Q |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |

### OR Gate

Truth Table:
| C | D | R |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |

### NOT Gate

Truth Table:
| E | S |
| 0 | 1 |
| 1 | 0 |

### NAND Gate

Truth Table:
| F | G | T |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

### NOR Gate

Truth Table:
| H | I | U |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |

### XOR Gate

Truth Table:
| J | K | V |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

## Boolean Algebra
### Notation

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\land B$ | $A.B$ | $A\bot B$ |
| A OR B | $A\lor B$ | $A+B$ | $A\vdash B$ |
| NOT A | $\neg A$ | ${\overline {A}}$ | ${\overline {A}}$ |
| A XOR B | $A\veebar B$ | $A\oplus B$ | $A\oplus B$ |

### Laws of Boolean Algebra
#### Commutative Law

$A+B=B+A$
$A.B=B.A$

#### Associate Law

$(A+B)+C=A+(B+C)$
$C(A.B)=A(B.C)$

#### Distributive Law

$A.(B+C)=A.B+A.C$
$A+(B.C)=(A+B).(A+C)$

#### Identity Law

$A+A=A$
$A.A=A$

#### Negation Law

${\overline {A}}={\overline {A}}$
$A={\overline {\overline {A}}}$

#### Absorption Law

$A+(A.B)=A$
$A.(A+B)=A$

#### Redundancy Law

$A+A.B=A$
$A.(A+B)=A$

#### De Morgan's Laws

${\overline {A.B}}={\overline {A}}+{\overline {B}}$
${\overline {A+B}}={\overline {A}}.{\overline {B}}$

#### Other Laws

$A+0=A$
$A.0=0$
$A+1=1$
$A.1=A$
${\overline {A}}+1=1$
${\overline {A}}+A=1$
${\overline {A}}.A=0$
$A+{\overline {A}}.B=A+B$
$A({\overline {A}}+B)=A.B$

## Karnaugh Maps

These maps use pattern recognition to simplify boolean expressions. Tables of possible inputs are mapped against all possible outputs:
e.g.
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:
${\overline {C}}.{\overline {A}}$
In the Brown block (left hand rectangle) the values of A and B do not change, therefore this block is:
${\overline {A}}.{\overline {B}}$
In the red block (right hand square) the values of A and C do not change, therefore this block is:
$A.{\overline {C}}$
In the green block (right hand rectangle) the values of A and B do not change, therefore this block is:
$A.{\overline {B}}$
In the grey-blue block (middle centre) the values of B, C and D do not change, therefore this block is:
$B.C.D$
Finally in the bottom purple/blue block, the values of B, C and D do not change, therefore this block is:
$B.C.{\overline {D}}$
These values can then all be combined:
$({\overline {C}}.{\overline {A}})+({\overline {A}}.{\overline {B}})+(A.{\overline {C}})+(A.{\overline {B}})+(B.C.D)+(B.C.{\overline {D}})$
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
### Half Adder

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

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

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

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 ($D$) and the clock signal, along with two outputs, the stored data ($Q$) and the inverse (${\overline {Q}}$).
You may be asked to complete the output signal for a diagram, like the above, given the control input and the clock.