Section Eight: Boolean algebra Flashcards
Chapter 40 – Logic gates and truth tables
Binary logic
At the most elementary level, an electronic device can only recognise the presence or absence of current or voltage. Either electricity is present or it isn’t. This is a switch – on or off, true or false, 1 or 0. With a computer’s semiconductor, the voltage at the input and output terminals is measured and is either high or low; 1 or 0. Computers comprise billions of these switches and manipulating these sequences of ONs and OFFs can change individual bits. Electronic logic gates can take one or more inputs and produce a single output. This output can become the input to another gate and a complicated cascaded sequence of logic gates can be implemented to form a circuit in, for example, the CPU.
Chapter 40 – Logic gates and truth tables
Simple logic gates and truth tables
There are a number of different logic gates that are each designed to perform a different operation in terms of output. We will look at NOT, AND, OR and XOR gates.
Each of these gates may be represented by a truth table showing the output for each possible input or combination of inputs. The four gates are shown below. Inputs are usually given algebraic letters such as A, B and C and output is usually represented by P or Q.
Chapter 40 – Logic gates and truth tables
NOT gate (negation)
The NOT gate inverts the input. The small circle denotes an inverted input.
Chapter 40 – Logic gates and truth tables
AND gate (conjunction)
The AND gate needs both inputs to be 1 to get a 1 else you would get a 0
Chapter 40 – Logic gates and truth tables
OR gate (disjunction)
The OR gate only needs one 1 in order to get a 1 and you can only get a 0 if there are two 0
Chapter 40 – Logic gates and truth tables
XOR gate (exclusive disjunction)
The XOR (pronounced ex-or) gate stands for exclusive OR, meaning that the output will be true if one or other input is true, but not both. Compare this to the OR gate, which will accept two true inputs as true also.
Chapter 41 – Simplifying Boolean expressions
de Morgan’s laws
Augustus de Morgan (1806-1871) was a Cambridge Mathematics professor who formulated two theorems or laws relating to logic. These laws can be used to manipulate and simplify Boolean expressions. Although his theoretical work had little practical application in his lifetime, it became of major significance in the next century in the field of digital electronics, in which TRUE and FALSE can be replaced by ON and OFF or the binary numbers 0 and 1.
Using de Morgan’s laws, any Boolean function can be converted to one which uses only NAND functions or only NOR functions, and these can be further converted to an expression using all NAND functions or all NOR functions.
Thus, any integrated circuit can be built from just one type of logic gate. This is an advantage in manufacturing where costs can be kept down by using only one type of gate.
Chapter 41 – Simplifying Boolean expressions
General rules
- X ^ 0 = 0
- X ^ 1 = X
- X ^ X = X
- X ^ ¬X = 0
- X ^ 0 = X
- X ^ 1 = 1
- X ^ X = X
- X ^ ¬X = 1
Chapter 41 – Simplifying Boolean expressions
Commutative rule
- X ^ Y = Y ^ X
- X ^ Y = Y ^ X
Chapter 41 – Simplifying Boolean expressions
Associative rules
- X ^ (Y ^ Z) = (X ^ Y) ^ Z
- X ^ (Y ^ Z) = (X ^ Y) ^ Z
Chapter 41 – Simplifying Boolean expressions
Distributive rules
- X ^ (Y ^ Z) = (X ^ Y) ^ (X ^ Z)
- (X ^ Y) ^ (W ^ Z) = (X ^ W) ^ (X ^ Z) ^ (Y ^ W) ^ (Y ^ Z)
Chapter 41 – Simplifying Boolean expressions
Absorption rules
- X ^ (X ^ Y) = X
- X ^ (X ^ Y) = X
Chapter 41 – Simplifying Boolean expressions
Double negation
- X = ¬ ¬X
Chapter 42 – Karnaugh maps
