Electrical Engineering › Section R · Digital concepts, number systems, and codes › Topic R.2
Basic logic, combinational, and sequential functions
Three simple operations, NOT, AND and OR, are the raw material of every digital system. This topic defines them, then surveys the larger functions built from them, from adders and decoders to counters and memories, and the key split between circuits that remember and circuits that do not.
Logic from true-or-false statements
Many everyday rules are logic statements: "the fan runs if the switch is on and the cover is closed". Each condition is either true or false, and so is the result, which suits circuits with two states. In positive logic, true is HIGH (1) and false is LOW (0). George Boole published an algebra of such statements in 1854, and in the late 1930s Claude Shannon showed that it describes switching circuits. That algebra, Boolean algebra, gets its own topic, "Boolean operations, laws, and DeMorgan's theorems"; here we meet its three basic operations as circuits called logic gates.
NOT: the inverter
The NOT function has one input and gives the opposite level at its output: a 1 becomes 0 and a 0 becomes 1. The circuit is called an inverter. In Boolean notation the output for input \(A\) is written with a bar, \(\overline{A}\), read "A bar" or "not A"; plain text, such as a flashcard, writes it A'. Its truth table, which lists the output for every input, has just two rows:
Applying NOT twice gives back the original signal, \(\overline{\overline{A}} = A\).
AND and OR
The AND function gives a 1 only when all its inputs are 1; any 0 input forces the output to 0. The OR function gives a 1 when at least one input is 1, and 0 only when all inputs are 0. AND is written like multiplication, \(AB\) or \(A \cdot B\), and OR like addition, \(A + B\), where the plus means OR, not arithmetic sum. For two inputs:
Both gates can have more inputs; the same rules apply to all of them.
Worked example: a garage-door rule
A garage-door motor M should run when the button B is pressed, but never while the safety beam is blocked, S = 1. Write M in Boolean form and build its truth table. 1. Translate the words: M is 1 when B is 1 and S is not 1, so \(M = B\overline{S}\), an AND of B with an inverted S. 2. List all four input pairs and evaluate:
3. Check the meaning: the only row with M = 1 is button pressed and beam clear, exactly as required. Two inputs give \(2^2 = 4\) rows.
Combinational and sequential logic
Every digital circuit falls into one of two families. In combinational logic the outputs depend only on the inputs at that moment: give the same inputs and you always get the same outputs, as in the garage-door rule. In sequential logic the outputs also depend on what happened before, because the circuit stores information. A counter is sequential: one more input pulse moves it from 7 to 8 only because it remembered the 7. Sequential circuits need a storage element, usually the flip-flop, and usually a clock. "Combinational circuits and universal NAND and NOR gates" and "Latches and flip-flops" take each family further.
Comparison and arithmetic
A comparator takes two binary numbers A and B and raises one of three outputs, \(A < B\), \(A = B\) or \(A > B\). An adder takes A, B and a carry input and produces a sum and a carry output. A 4-bit adder holds sums up to 15, so \(9 + 12 = 21\) appears as sum 5 with carry out 1, because \(21 = 16 + 5\). A subtracter gives a difference and a borrow output, though "Complements and signed numbers" shows that an adder can subtract too. Multiplication is shifts and additions: \(6 \times 5\) is 6 plus 6 shifted two places, \(6 + 24 = 30\). Division is repeated subtraction: 7 goes into 30 four times, remainder 2.
Encoding, decoding and code conversion
A code is a pattern of bits that stands for specific information. An encoder turns an uncoded input, such as one key pressed on a numeric keypad, into a code, here the binary number for that digit. A decoder does the reverse: it takes a code and activates the matching output, for example the segments of a 7-segment display that show the digit. A code converter changes one code into another, such as plain binary into binary-coded decimal (BCD) or Gray code, codes introduced in "Hexadecimal, octal, BCD, and error codes". All three are combinational.
Data selection: multiplexers
A multiplexer (mux) connects one of several input lines to a single output, chosen by select inputs; a demultiplexer (demux) does the reverse, routing one input to one of several outputs. Together they let several sources share one line. If a mux and a distant demux step through their positions together, source 1 reaches destination 1 in the first time slot, source 2 reaches destination 2 in the second, and so on. Sharing a line's time this way is time-division multiplexing (TDM).
Storage and counting
A flip-flop is a bistable circuit: it rests in either of two stable states, so it stores one bit until told to change. A register is a row of flip-flops holding a group of bits; an 8-bit register uses eight. A shift register can move its bits along: loaded serially, bits enter one per clock pulse; loaded in parallel, all enter at once. Large amounts of data go in semiconductor memories (RAM for working data, ROM or flash for data that must survive power-off) and in magnetic and optical drives. A counter steps through a sequence of binary codes, one per input pulse, so it is a sequential circuit built from flip-flops.
Worked example: a car-park sign
A 120-space car park shows free spaces and lights FULL when no spaces remain. Name the function blocks. 1. Sensors at the entrance and exit give one pulse per car. 2. A counter counts entrance pulses up and exit pulses down, so it holds the number of cars, sequential logic. 3. A register stores the capacity, 120, entered once from a keypad through an encoder. 4. A subtracter forms 120 minus the count, and a decoder turns the result into display segments. 5. A comparator checks count against capacity; its A = B output lights FULL. Check: with 120 cars, the display shows 0 and FULL is lit together.
Common mistakes to avoid
First, reading the OR plus sign as arithmetic: in logic \(1 + 1 = 1\), not 2. Second, thinking AND needs only one HIGH input; it needs all of them. Third, missing rows in a truth table: n inputs always need \(2^n\) rows, so three inputs need eight. Fourth, calling a circuit combinational because it contains only gates; gates wired in a feedback loop can store a bit, and then the circuit is sequential. Fifth, confusing encoders and decoders: an encoder produces a code, a decoder reads one.
Key takeaways
NOT inverts, written \(\overline{A}\). AND gives 1 only when all inputs are 1, written AB; OR gives 1 when any input is 1, written A + B. A truth table lists the output for all 2ⁿ input combinations. Combinational outputs depend only on present inputs; sequential outputs also depend on stored history. Larger functions are built from gates: comparators, adders and subtracters, encoders, decoders, code converters, multiplexers and demultiplexers (combinational), and flip-flops, registers, memories and counters (sequential).
Flashcards
Flashcard
Output is the opposite of the input
Test your understanding
Question 1 of 5
A 3-input AND gate has inputs A = 1, B = 1 and C = 0. What is its output, and why?
Question 2 of 5
Which of these is a sequential circuit?
Question 3 of 5
In Boolean logic, what is the value of 1 + 1?
Question 4 of 5
A truth table for a logic circuit with 4 inputs needs how many rows?
Question 5 of 5
Which block turns a key pressed on a numeric keypad into a binary code?
