Unit 3: Logic Gates and Recurrence Relations

MTH136 — Discrete Structures 6 min read

Digital logic and recurrence relations are the two computational cores of discrete structures: the first turns Boolean algebra into physical circuitry, the second turns self-reference into closed-form counting. Both rest on a small set of primitive rules applied repeatedly.

Boolean domain: every variable takes one of two values, written 0/1, F/T, or LOW/HIGH; there are no intermediate states.
Three basic operations: AND (·), OR (+) and NOT (' or overbar) generate all Boolean functions and hence all gates.
Functional completeness: the set {AND, OR, NOT} is complete; so is {NAND} alone and {NOR} alone, which is why real hardware is built mostly from NAND/NOR.
Recursive definition: a rule that defines an object in terms of smaller instances of itself, plus base case(s) that terminate the descent.
Sequence convention: aₙ denotes the nth term; n ≥ 0 unless stated, and initial conditions fix the sequence uniquely.

II. Logic Gates — Boolean Functions Realised as Hardware

A logic gate is a physical device implementing one Boolean operation, mapping one or more binary inputs to a single binary output defined by a truth table.

A. Introduction to Logic Gates

The seven standard gates cover every one- and two-input Boolean primitive.

AND: output 1 only when all inputs are 1: Y = A·B. Truth table row 11→1, else 0.
OR: output 1 when any input is 1: Y = A + B. Only 00→0.
NOT (inverter): single input, Y = A'; 0→1, 1→0.
NAND: AND followed by NOT, Y = (A·B)'; output 0 only for 11. Universal gate.
NOR: OR followed by NOT, Y = (A+B)'; output 1 only for 00. Universal gate.
XOR (exclusive-OR): Y = A⊕B = A'B + AB'; output 1 when inputs differ.
XNOR (equivalence): Y = (A⊕B)' = AB + A'B'; output 1 when inputs match.

Standard two-input truth table:

TEXT

A B | AND OR NAND NOR XOR XNOR
0 0 |  0   0    1   1   0    1
0 1 |  0   1    1   0   1    0
1 0 |  0   1    1   0   1    0
1 1 |  1   1    0   0   0    1

B. Combination of Gates

Complex Boolean functions are built by cascading gates so that outputs feed subsequent inputs.

Expression-to-circuit mapping: each operator becomes a gate; nesting order follows operator precedence NOT > AND > OR.
Worked build of Y = A·B + C': invert C with a NOT gate, feed A,B to an AND gate, feed both results to an OR gate. Two levels of logic, three gates.
Universality demonstrated with NAND:
- NOT from NAND: tie both inputs together, (A·A)' = A'.
- AND from NAND: NAND then invert, ((A·B)')' = A·B.
- OR from NAND: invert both inputs then NAND, (A'·B')' = A + B (De Morgan).
XOR as a combination: A⊕B = (A·(A·B)')·((A·B)'·B) implemented with four NAND gates — shows a "derived" gate is just a fixed cluster of primitives.
Boolean simplification first: apply laws such as A + A'B = A + B or A·A' = 0 before wiring, since fewer literals mean fewer gates and shorter propagation delay.

C. Implementation of Logic Gates to the Switching Circuits

Logic gates are the algebraic abstraction of switching networks, where a switch is a Boolean variable — closed (1) conducts, open (0) blocks.

Series connection = AND: current flows only if switch A and switch B are both closed, so conduction = A·B. Two switches in a single line.
Parallel connection = OR: current flows if switch A or switch B is closed, so conduction = A + B. Two switches on separate branches.

Complementary switch: a normally-closed switch conducts when its variable is 0, realising A'.
Series–parallel translation: any Boolean expression in sum-of-products form maps to parallel branches (the +) of series switches (the ·).
- Example: Y = A·B + C → one branch with A in series with B, wired in parallel with a lone switch C.
Bridge/relay circuits: electromechanical relays historically implemented these networks; Shannon's 1938 thesis established the exact equivalence between switching circuits and Boolean algebra.
Design goal: minimise switches by algebraic reduction, e.g. A·B + A·B' = A·(B + B') = A collapses two series pairs into a single switch.

III. Recurrence Relations — Sequences Defined by Their Own Past

A recurrence relation defines each term of a sequence as a function of one or more preceding terms, together with base cases that anchor the definition.

A. Introduction to Recursion

Recursion expresses a problem's solution in terms of smaller instances of the same problem.

Two mandatory parts: a base case that halts the descent, and a recursive case that reduces the problem toward the base.
Factorial: n! = n·(n−1)! with base 0! = 1; computing 4! unwinds 4·3·2·1·1.
Fibonacci definition: F(n) = F(n−1) + F(n−2), base F(0)=0, F(1)=1.
Recursion vs iteration: recursion mirrors the mathematical definition and uses the call stack; iteration reuses variables and avoids stack growth but obscures the structure.
Failure mode: omitting or never reaching the base case causes infinite recursion (stack overflow).

B. Recurrence Relation

A recurrence relation is the formal equation stating the dependence of aₙ on earlier terms.

General form: aₙ = f(aₙ₋₁, aₙ₋₂, …, aₙ₋ₖ) for n ≥ k, with k initial conditions supplied.
Order: the difference between the highest and lowest indices; aₙ = aₙ₋₁ + aₙ₋₂ is order 2.
Degree: the highest power of any term; aₙ = aₙ₋₁² has degree 2 (non-linear).
Linear: each aₙ₋ᵢ appears to the first power and is not multiplied by another term.
Homogeneous: every term contains some aₙ₋ᵢ; no standalone function of n. If a term like 2ⁿ appears alone, the relation is non-homogeneous.
Modelling example: compound interest Pₙ = 1.05·Pₙ₋₁ (order 1, linear, homogeneous); Tower of Hanoi moves Hₙ = 2Hₙ₋₁ + 1 (order 1, linear, non-homogeneous).

C. Solving Recurrence Relation

Solving means finding a closed-form (explicit) expression for aₙ that removes all self-reference.

Iteration / substitution (back-substitution): repeatedly expand the recurrence until a pattern emerges, then generalise.
- Worked example aₙ = aₙ₋₁ + 3, a₀ = 2:
  TEXT
```
    a₁ = a₀ + 3
    a₂ = a₀ + 3·2
    aₙ = a₀ + 3n = 2 + 3n
```
- Verified: a₃ = 2 + 9 = 11, matching direct computation 5,8,11.
Forward substitution: start from base and build upward when the pattern is easier to spot ascending.
Characteristic-root method: the systematic technique for linear homogeneous relations, developed in the next subsection.
Generating functions: encode the sequence as coefficients of a power series and solve algebraically — a general but heavier tool.

D. Linear Homogeneous Recurrence Relation with Constant Coefficients and Their Solution

This class admits a complete, mechanical solution via the characteristic equation.

Standard form: aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + … + cₖaₙ₋ₖ, where each cᵢ is a constant and cₖ ≠ 0; order k.
Characteristic equation: substitute the trial solution aₙ = rⁿ to obtain
TEXT
```
  rᵏ − c₁rᵏ⁻¹ − c₂rᵏ⁻² − … − cₖ = 0
```
General solution by root type:
1. Distinct roots r₁,…,rₖ: aₙ = α₁r₁ⁿ + α₂r₂ⁿ + … + αₖrₖⁿ, constants αᵢ fixed by initial conditions.
2. Repeated root r of multiplicity m: that root contributes (α₀ + α₁n + … + α_{m−1}n^{m−1})rⁿ, an extra factor of n per repetition.
Worked example (Fibonacci): aₙ = aₙ₋₁ + aₙ₋₂, a₀=0, a₁=1.
- Characteristic equation r² − r − 1 = 0, roots r = (1 ± √5)/2.
- General solution aₙ = α₁((1+√5)/2)ⁿ + α₂((1−√5)/2)ⁿ.
- Applying a₀=0, a₁=1 gives α₁ = 1/√5, α₂ = −1/√5, yielding Binet's formula
  TEXT
```
    aₙ = (1/√5)[((1+√5)/2)ⁿ − ((1−√5)/2)ⁿ]
```
Repeated-root example: aₙ = 4aₙ₋₁ − 4aₙ₋₂ gives r² − 4r + 4 = 0, root r = 2 twice, so aₙ = (α₀ + α₁n)2ⁿ.
Symbols defined: rⁿ is the geometric trial term; αᵢ are arbitrary constants; multiplicity m counts how often a root repeats; k initial conditions are always exactly enough to determine the k constants.