Logic Gates and Boolean Algebra

Even if the truth tables of two expressions are identical, implementing them as gate circuits may still produce different glitches; an output labeled "high" does not guarantee reliable recognition by another chip. Digital logic must simultaneously handle Boolean functionality, propagation timing, and analog voltage levels. This article first clarifies the algebra, then uses Karnaugh maps and path delays to explain these three layers of relationships.

Operation and Negation Scope

Boolean variables take only values 0 and 1. This article uses A·B for AND, A+B for OR, ¬A for NOT, and A⊕B for XOR; the plus sign here is not standard integer addition, so 1+1 remains 1. Parentheses explicitly define the scope of negation; ¬(A·B) must not be mistakenly written as A·¬B.

NOT flips 0 to 1 and 1 to 0. A two-input XOR outputs 1 when inputs differ; XNOR is its inverse. For multiple inputs, continuous XOR outputs 1 if the number of 1s is odd; it should not be misunderstood as "all inputs are pairwise different."

Simplification Relies on Identities, Not Intuitive Algebra

For example, AB+A¬B=A(B+¬B)=A. Similarly, Y=¬(AB)+C becomes ¬A+¬B+C via De Morgan's law; negating only B would already change the function.

NAND is functionally complete: A NAND A yields NOT; negating the result of NAND yields AND; (A NAND A) NAND (B NAND B) yields OR. Therefore, at the level of stateless Boolean functions, any combinational logic can be constructed using only NAND gates; the same applies to NOR. This does not prove that using a single gate type always yields the smallest area or fastest speed; nor does it explain why memory technologies are named NAND/NOR, which is not derived from the fact that "gates can implement all functions."

From Truth Table to Covering

For n inputs, a complete truth table has 2ⁿ rows. If each row where the output is 1 is written as a minterm, and these terms are ORed together, a Sum-of-Products (SOP) expression is obtained. For example, with three variables encoded from high to low as ABC, binary 001 corresponds to ¬A¬BC.

Karnaugh maps arrange rows and columns in Gray code order, ensuring that adjacent cells differ by only one bit. Adjacent 1s can be grouped into rectangles with sizes that are powers of two (1, 2, 4, 8, etc.); variables that change within a group are eliminated, while those that remain constant are retained. Each group yields an implicant covering multiple minterms, not "larger circles yielding more minterms." MIT: Combinational Logic and Karnaugh Maps

Given Y=Σm(1,3,6,7), with BC arranged as 00, 01, 11, 10. In the top row, B changes while A=0 and C=1, yielding ¬AC; in the bottom row, C changes while A=1 and B=1, yielding AB. Thus, Y=¬AC+AB.

Edges are also adjacent; corners can form cross-boundary groups in appropriately sized maps. Groups may overlap but must not include cells definitively set to 0. "Don't care" conditions can only arise from task requirements that guarantee certain inputs will not occur or outputs are unspecified; one cannot arbitrarily mark inputs as X simply because they are difficult to handle. If uninitialized or fault states are possible, corresponding behaviors should be considered.

Gate count, input count, logic depth, fan-out, and target process technology all affect implementation cost; the expression with the fewest literals does not necessarily correspond to the fastest or smallest circuit. Complex logic is usually handled by synthesis tools, but truth tables and covering remain the foundation for understanding results.

Logical Equivalence Does Not Equal Timing Equivalence

Continuing with Y=AB+¬AC, let B=C=1. In steady state, regardless of whether A is 0 or 1, Y is always 1; however, when A switches from 1 to 0, the AB path may go to 0 first, while the ¬AC path (through an inverter) goes to 1 slightly later, creating a gap where both product terms are 0. This is called a static-1 hazard.

Adding the redundant term BC yields Y=AB+¬AC+BC, which does not change the truth table but provides a path that remains 1 when B=C=1 and A switches. On the Karnaugh map, this corresponds to adding a common group covering the two BC=11 cells in both rows. MIT: Combinational Logic Hazards and Covering

This conclusion applies to the corresponding two-level implementation and the condition where only A changes; it does not guarantee glitch-free operation for arbitrary multi-level mappings or simultaneous changes in multiple inputs. If synthesis tools remove redundant terms again to save area, the target constraints after implementation must be verified. Dynamic hazards and multi-input functional hazards are not fully resolved by this single term.

Synchronous systems can sample combinational logic via registers after it has stabilized, but setup/hold times must be met, and glitches may still increase dynamic power consumption. Signals driven by clocks, asynchronous resets, or directly to external actions are particularly sensitive to glitches. One cannot arbitrarily place a capacitor on a standard gate output as a universal fix: it increases load, slows edges, and may violate input transition time requirements; if filtering is needed, a defined RC circuit and appropriate input structure should be designed.

Same truth table, why a glitch?

Directly separate arrival times to reveal the gap. Reverse their order and it becomes overlap, removing this static-1 hazard in the model. BC keeps either order high, only for the stated single-input transition.

0/1 Are Voltage Ranges

V_IL(max) is the maximum input voltage guaranteed to be recognized as low; V_IH(min) is the minimum input voltage guaranteed to be recognized as high; input values between these limits do not guarantee logical results and do not imply the device has a third stable Boolean value. The actual switching point of a standard input also varies with device, supply voltage, and temperature.

When connecting a driver to a receiver, use the driver's V_OH(min) and V_OL(max) under specified current conditions, and compare them with the receiver's V_IH(min) and V_IL(max): High-level static noise margin NM_H = V_OH(min) − V_IH(min), and Low-level static noise margin NM_L = V_IL(max) − V_OL(max).

Assume the driver's high output is at least 2.9 V and low output is at most 0.2 V; the receiver requires high at least 2.0 V and low at most 0.8 V. Then the margins are 0.9 V and 0.6 V, respectively. This only checks static levels; one must also verify absolute maximum input voltage, undervoltage tolerance, ground offset, and edge rate conditions.

TTL/CMOS are not sufficiently precise level specifications. Even within CMOS implementations, input thresholds can differ between series such as HC and HCT; identical power supplies do not guarantee interface compatibility, nor can one deduce that "CMOS" always offers better noise margins than all TTL families. Nexperia: 74HC00 / 74HCT00

Floating Inputs, Slow Edges, and Schmitt Triggers

When a CMOS input floats, leakage and coupling may drive the voltage into the transition region, causing uncertain outputs and increased internal current. Slow edges or noise crossing the switching point multiple times may also cause repeated switching. Schmitt trigger inputs have different rising and falling thresholds, providing hysteresis, but one must still adhere to their voltage and operating conditions. TI: Slow Edges and Floating CMOS Inputs

Unused inputs should be tied to a valid state according to device requirements, either directly or via appropriate resistors; output pins cannot be arbitrarily tied to power rails as inputs. Push-pull outputs generally cannot be directly paralleled to "enhance drive"; open-drain structures require pull-ups and wired-AND logic according to specific rules.

Ideal Gates vs. Real Chips

A CMOS inverter uses a pull-up PMOS and a pull-down NMOS. When the input is near the low rail, the PMOS conducts and the NMOS turns off, pulling the output high; when the input is near the high rail, the opposite occurs. During the transition, both transistors may be partially on simultaneously, and the output load capacitance must charge and discharge; therefore, real circuits exhibit not only static leakage but also short-circuit current and dynamic power consumption.

The common estimate is P_dyn ≈ αC_LV_DD²f, where α is defined in this article as the average number of 0→1 charging events at the output per reference cycle. Different sources may define the activity factor with different counting conventions; this condition must not be overlooked. Even when the output does not switch, leakage, input bias, and other internal activities may still occur; one cannot write "power is consumed only during switching moments."

Fan-out is not merely about how many inputs can be connected: static input current, capacitance, trace characteristics, and required timing collectively determine the driving burden. Propagation delay t_pLH/t_pHL depends on supply voltage, temperature, load, and input transition conditions; truth tables do not contain this information.

The number is merely a lookup entry; the full part number prefix/suffix, logic family, and package determine actual specifications. The next article Combinational Logic Circuits uses these gates to build adders, decoders, and multiplexers.

from itertools import product

def nand(a,b): return not (a and b)
for a,b,c in product([False,True], repeat=3):
    original = (a and b) or ((not a) and c)
    covered = original or (b and c)
    assert original == covered
    index = 4*int(a)+2*int(b)+int(c)
    assert original == (index in {1,3,6,7})
    assert (not (a and b)) == ((not a) or (not b))
    assert nand(nand(a,a),nand(b,b)) == (a or b)
assert (False or False) is False
assert (False or False or True) is True
print("8 input combinations: Karnaugh map, redundant covering, De Morgan, and NAND construction are all consistent")

This exhaustive verification checks Boolean functionality only; it does not verify gate delays, actual glitches, or interface levels; physical implementation still requires corresponding timing and electrical checks.