3.13.5.1 - Combinational Logic

Binary signals and six logic gates

A digital signal represents one of two logic levels, low (0) or high (1). These are voltage ranges defined by the circuit, not a claim that every logic 1 is the same voltage. A combinational circuit determines its output from the present input combination: it does not store an earlier count or wait for a clock edge. Allow a short propagation time for real gates to respond.

A logic gate applies a fixed input–output rule. A truth table lists that rule for every possible input combination. Two independent binary inputs give four rows: 00, 01, 10 and 11.

AND, OR and NOT

An AND gate is high only when both inputs are high. An OR gate is high when at least one input is high, including when both are high.

[DIAGRAM: asset_name: E.5.1 - Combinational Logic - Diagram 1; asset_slug: E.5.1 - Combinational Logic - Diagram 1; caption: AND: both inputs must be high; description: AND: both inputs must be high]

[DIAGRAM: asset_name: E.5.1 - Combinational Logic - Diagram 2; asset_slug: E.5.1 - Combinational Logic - Diagram 2; caption: OR: at least one input must be high; description: OR: at least one input must be high]

A NOT gate has one input and reverses its logic level: input 0 gives output 1 and input 1 gives output 0. Its small output circle, called an inversion bubble, means NOT.

[DIAGRAM: asset_name: E.5.1 - Combinational Logic - Diagram 3; asset_slug: E.5.1 - Combinational Logic - Diagram 3; caption: NOT: the output bubble marks inversion; description: NOT: the output bubble marks inversion]

NAND, NOR and EOR

NAND means NOT AND: first apply AND, then invert its output. NOR means NOT OR. Keep the bubble in a circuit symbol: omitting it changes the truth function.

EOR (also called XOR or exclusive OR) is high when its two inputs differ. Unlike OR, it is low when both inputs are high.

[DIAGRAM: asset_name: E.5.1 - Combinational Logic - Diagram 7; asset_slug: E.5.1 - Combinational Logic - Diagram 7; caption: NAND and NOR invert the AND and OR results; description: NAND and NOR invert the AND and OR results]

[DIAGRAM: asset_name: E.5.1 - Combinational Logic - Diagram 4; asset_slug: E.5.1 - Combinational Logic - Diagram 4; caption: EOR: the extra input-side curve distinguishes exclusive OR; description: EOR: the extra input-side curve distinguishes exclusive OR]

Treat the gates as building blocks with these rules. Their internal transistor circuits are not required. For example, a two-input AND can enable a sensor signal: with the enable input 1, the output follows the sensor; with enable 0, the output stays 0.

Writing Boolean expressions

Boolean algebra expresses the same gate rules using variables that can be only 0 or 1. The operation symbols have logical meanings.

For example, Boolean $1+1=1$, because OR is high when either or both inputs are high. This is not ordinary addition.

The extent of a bar matters: $\overline{A+B}$ is NOR, whereas $\overline A+B$ means invert A and then OR the result with B. With A = B = 1, these give 0 and 1 respectively. Similarly, NAND is $\overline{AB}$, not $\overline A B$.

Write one expression per gate

If A and B enter an OR gate whose output D is ANDed with C, write $D=A+B$, then $Z=DC=(A+B)C$. Brackets preserve the wiring order. In $A+BC$, B and C enter AND before its output enters OR with A; this is a different circuit.

Two useful equivalences are De Morgan's laws:

The second says that “neither input is high” is the same as “A is low AND B is low”. A truth table verifies either law for all four input pairs. Inverting each input without also exchanging AND and OR does not give the inverted original result.

Simplifying without changing the logic

A simpler Boolean expression is useful only if it gives the same output for every input combination. Start with gate rules, apply valid identities, and use a truth table to check an uncertain step.