Exam Board:
OCR A-Level
Specification:
Computer Science H446
4.3 - Boolean Algebra
Watch on YouTube:
Boolean Logic (NOT, AND, OR, XOR)
Karnaugh maps
Boolean algebra rules
Logic gate diagrams
D-type flip flops
Half & full adders
This topic explores how the logical operations NOT, AND, OR and XOR are used to process binary data and control digital systems. It also looks at how to simplify and represent logic using Karnaugh maps, Boolean algebra rules, logic gate diagrams and truth tables.
Boolean Operators
Boolean logic is a form of algebra in which all values are either True (1) or False (0). There are four Boolean operators to know:
-
NOT (¬) reverses the input value - 1 becomes 0 and 0 becomes 1.
-
AND (∧) outputs 1 only if both inputs are 1 (e.g. 1 AND 1 = 1, otherwise 0).
-
OR (∨) outputs 1 if at least one input is 1 (e.g. 1 OR 0 = 1).
-
XOR (v) outputs 1 only if one input is 1 but not both (e.g. 1 XOR 1 = 0, 1 XOR 0 = 1).
A truth table is used to show all possible input combinations for a logic circuit or Boolean expression, along with the resulting output for each combination.
Karnaugh Maps
A Karnaugh map is a visual method used to simplify Boolean expressions and make logic circuits more efficient. It organises all possible input combinations into a grid, to more easily identify an expression's simplest form.
By grouping together 1s (representing True outputs) in powers of two (1, 2, 4 or 8 cells), you can identify and remove redundant terms in a Boolean expression. The simplified result reduces the number of logic gates needed in a circuit, making it faster and easier to build.
Boolean Algebra Rules
Boolean algebra rules are used to simplify Boolean expressions.
-
With Double Negation, two NOTs cancel each other out, returning the original value, e.g., ¬¬A = A.
-
Commutation means the order of terms doesn’t matter in Boolean operations, e.g., A AND B = B AND A.
-
Distribution allows expressions to be expanded or factored, e.g., A AND (B OR C) = (A AND B) OR (A AND C).
-
Association means the grouping of terms doesn’t affect the result. (A AND B) AND C = A AND (B AND C).
-
De Morgan’s Laws show how to distribute negation across AND and OR operations: ¬(A AND B) = (¬A OR ¬B) and ¬(A OR B) = (¬A AND ¬B).
Logic Gate Diagrams
Logic gate diagrams are visual representations of Boolean expressions or digital circuits, showing how data flows through logic gates to produce an output.
Each gate performs a basic logical operation (such as NOT, AND, OR or XOR) and is represented by a distinct symbol:
NOT
AND
OR
XOR
D-Type Flip Flops
A D-type flip-flop is a sequential logic circuit that stores a single bit of data (either 0 or 1). It has two inputs - D (data) and Clock - and two outputs - Q and ¬Q.
When a clock pulse occurs, the flip-flop copies the value of D to the Q output, and that value is held (stored) until the next clock pulse. This makes D-type flip-flops useful for memory storage, registers and data synchronisation.
Essentially, they act as a 1-bit memory cell, storing the last value of D whenever the clock signal triggers.
Half Adders & Full Adders
A half adder is a logic circuit with two inputs (A and B) that are added to produce two outputs - S (sum), the result of A XOR B - and C (carry), the result of A AND B. Half adders can only add two bits and cannot handle an input carry from a previous addition.
A full adder is an extension of a half adder with three inputs: A, B, and C in (a carry-in from a previous calculation). It produces two outputs: S (sum) (A XOR B XOR Cin) and C out (carry out) ((A AND B) OR (B AND Cin) OR (A AND Cin)). Full adders can be linked together to perform multi-bit binary addition in arithmetic circuits.
Questo's Key Terms
Boolean Logic: NOT, AND, OR, XOR, Karnaugh maps, logic gate diagrams, truth tables
Boolean Algebra Rules: De Morgan’s Laws, distribution, association, commutation, double negation
D-Type Flip Flops: data, clock, Q, NOT Q
Adders: half adder, full adder
Did You Know?
The word 'Boolean' is always spelt with a capital B because it is named after George Boole, a 19th-century English mathematician. His work has become the foundation of all modern digital electronics and computing.
