Digital Fundamentals and Boolean Algebra Explained: Gates, Laws and Simplification

Digital logic begins with only 0 and 1, yet a gate diagram, a truth table and a Boolean expression can make the same function look like three separate topics. The real task is learning to move confidently between these representations: read a gate, write its expression, build the truth table, simplify the result and verify that the function did not change.

Related reading: Boolean algebra MCQs and K-map minimization.

Digital fundamentals: what 0 and 1 mean

A bit is a variable with two possible logical values, 0 and 1. They can represent false and true, or low and high, but they are abstract states rather than universal fixed voltages. Each hardware family defines the electrical ranges that represent them.

An analogue sensor signal may vary continuously. A one-bit comparator output records only whether that signal is below (0) or above (1) a chosen threshold. This distinction is a useful starting point in the wider CS Fundamentals route.

An n-bit word has 2^n possible patterns. For three bits, they are 000, 001, 010, 011, 100, 101, 110, 111. These eight patterns are why a three-variable truth table has eight rows.

Logic gates and Boolean notation

Let A and B be input bits and F be the output. AND is written by adjacency, so F=AB; OR uses +, so F=A+B; and NOT uses an apostrophe, so F=A'. NAND is (AB)', NOR is (A+B)', XOR is A ⊕ B, and XNOR is (A ⊕ B)'. XOR is 1 when the inputs differ, while OR is 1 when at least one input is 1.

For A=1 and B=0, AB=0, A+B=1, A'=0, B'=1, and A ⊕ B=1. NAND is 1, NOR is 0, and XNOR is 0. Unless parentheses say otherwise, evaluate complement first, AND second, and OR last.

Boolean laws worth learning as tools

Let X, Y and Z be Boolean variables. These laws are tools for controlled rewriting, not formulas to recite without recognising their purpose.

Commutative laws allow X+Y=Y+X and XY=YX. Associative laws allow regrouping, such as (X+Y)+Z=X+(Y+Z). Distribution works in both forms: X(Y+Z)=XY+XZ and X+YZ=(X+Y)(X+Z). The second is valid Boolean distribution, even though it does not resemble ordinary arithmetic.

Absorption gives X+XY=X and X(X+Y)=X. De Morgan's laws are (X+Y)'=X'Y' and (XY)'=X'+Y'. For example, (A+BC)'=A'(BC)'=A'(B'+C'). Duality swaps OR with AND and 0 with 1 to produce a dual identity. It does not mean complementing every variable. The majority-function reduction below uses only idempotence, complement and identity. Advanced Boolean Algebra Laws and Logic Optimization develops consensus-law reduction, gate-cost accounting and the static-hazard trade-off.

Worked example: simplify a three-input majority function

Define F(A,B,C)=A'BC+AB'C+ABC'+ABC. Each product identifies a row where the output is 1: 011, 101, 110, and 111. Since these are exactly the inputs containing at least two 1 bits, F is a three-input majority function. With A as the most significant bit and m denoting a minterm row number, F=Σ m(3,5,6,7).

Use idempotence in reverse to make two extra copies of the existing ABC term. OR-ing a term with copies of itself changes nothing:

1. F=A'BC+ABC+AB'C+ABC+ABC'+ABC

2. F=BC(A'+A)+AC(B'+B)+AB(C'+C)

3. F=BC.1+AC.1+AB.1

4. F=AB+AC+BC

Each pair uses X'+X=1, followed by the identity law. Now verify the original and reduced expressions on every input.

Under a simple two-level sum-of-products convention, the original form uses four 3-literal product terms. The reduced form uses three 2-literal product terms. This is a structural comparison, not a universal transistor-count or timing claim. The Boolean Algebra and K-map Minimization Guide shows how to see the same grouping spatially.

Boolean algebra traps and counterexamples

Boolean OR is not arithmetic addition: 1+1=1 and A+A=A, not 2A. Keep XOR separate too. At A=B=1, OR gives 1, while XOR gives 0.

De Morgan changes both literals and the operator. The wrong rule (A+B)'=A'+B' fails at A=0, B=1: its left side is 0, while the wrong right side is 1. The correct A'B' is 0.

Do not cancel a common factor. AB+AC=A(B+C), not B+C. At A=0, B=1, C=0, the original is 0, but B+C is 1. Similarly, A+AB=A is legal absorption, while A+AB=A+B is invalid.

Complement scope matters: (AB)'=A'+B', but AB' complements only B. Preserve parentheses whenever a NOT bubble covers a whole gate output. One counterexample can reject an alleged identity, but establishing equivalence needs a valid algebraic derivation or a complete truth table.

How exams test digital fundamentals

Exam-style questions may ask you to evaluate an output, translate a gate diagram, match an expression with a truth table, simplify using named laws, apply De Morgan's laws, distinguish OR from XOR, or compare equivalent two-level realisations. Try this rapid check before reading the answers:

1. G=(A+B')C at (A,B,C)=(1,0,1) gives 1; at (0,1,1) it gives 0.

2. (A+BC)' becomes A'(B'+C').

3. AB+AB'=A(B+B')=A.

4. The majority function gives F=0 at 100, but F=1 at 101.

Use targeted practice to test gate outputs, laws and simplification, then sort each mistake by notation, law choice or verification. Next, Combinational Circuits: MUX, Decoders, Adders carries Boolean expressions into functional circuit blocks.

Digital fundamentals and Boolean algebra: the short version

Keep this five-line revision card:

1. Define the notation before evaluating an expression.

2. Translate a diagram one gate at a time.

3. Use a named Boolean law for every rewrite.

4. Test a suspicious identity with a counterexample.

5. For a small input set, verify the final expression across every row.

The worked result is A'BC+AB'C+ABC'+ABC=AB+AC+BC, with output sequence 0,0,0,1,0,1,1,1. Use Zero to Hero, Complete CS Course when your wider CS foundation needs structured rebuilding. Before moving to K-maps or circuit blocks, rebuild the eight-row table from memory.