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 thumb|120x120px|AND Gate. Truth Table: ABQ000010100111 OR Gate thumb|120x120px|OR Gate. Truth Table: CDR000011101111 thumb|120x120px|NOT Gate. NOT Gate Truth Table: ES0110 NAND Gate thumb|120x120px|NAND Gate. Truth Table: FGT001011101110 NOR Gate Truth Table: thumb|120x120px|NOR Gate. HIU001010100110 thumb|120x120px|XOR Gate. XOR Gate Truth Table: JKV000011101110 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. StatementSyntax (Mathematicians)Syntax (Engineers)Syntax (Engineers)A AND BA OR BNOT AA XOR B Laws of Boolean Algebra Commutative Law Associate Law Distributive Law Identity Law Negation Law Absorption Law Redundancy Law De Morgan's Laws Other Laws Karnaugh Maps These maps use pattern recognition to simplify boolean expressions. Tables of possible inputs are mapped against all possible outputs: e.g. left|thumb|220x220px|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 Half Adder 180x180px Truth Table: ABSC0000011010101101 Where S is A XOR B and C is A AND B Full Adder 320x204px Truth table: ABCinSCout0000000110010100110110010101011100111111 This is a combination of 2 half adders and an OR gate. Flip Flops These circuits are capable of storing information. File:Flip flop circuit.png Truth Table: ABPQ00110110100111011110 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 thumb|D-type flip-flop thumb|375x200px|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. File: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.