Boolean Values, Operators & Truth Tables

Boolean Algebra & Digital Logic

Chapter 2 · Boolean Values, Operators & Truth Tables

A Boolean value is one of exactly two elements — 0 or 1 (equivalently False/True). A Boolean operator takes one or two Boolean values and produces another. This chapter defines the full working set — including two operators, XOR and NAND/NOR, that Discrete Mathematics Fundamentals' own propositional-logic chapter never needed but digital logic can't do without.

The Core Three: AND, OR, NOT

x	y	x · y (AND)	x + y (OR)
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	1

AND is 1 only when both inputs are 1. OR is 1 when at least one input is 1. NOT (x') simply flips: 0' = 1, 1' = 0.

XOR — Exclusive Or

XOR (⊕) is 1 exactly when its two inputs differ — true when exactly one input is 1, unlike plain OR which also accepts both.

x	y	x ⊕ y (XOR)
0	0	0
0	1	1
1	0	1
1	1	0

Why XOR gets its own chapter real estate

XOR isn't a minor variant of OR — it's the operator that makes binary addition without carry possible (1⊕1=0, exactly like adding two 1-bits and dropping the carry), which is precisely why Chapter 7's half adder is built directly from it.

NAND & NOR — Derived, and Surprisingly Powerful

NAND (NOT AND) and NOR (NOT OR) are simply AND/OR immediately followed by NOT:

x	y	NAND(x,y)	NOR(x,y)
0	0	1	1
0	1	1	0
1	0	1	0
1	1	0	0

A Remarkable Verified Fact: NAND Alone Builds Everything

NAND is functionally complete — every other operator in this chapter, including NOT, AND, and OR themselves, can be built using only NAND, wired to itself and to its own inputs.

Verified directly, for every input combination

NOT(x) = NAND(x, x) — verified for both x=0 and x=1. AND(x,y) = NAND(NAND(x,y), NAND(x,y)) — verified for all 4 input pairs, matching real AND exactly. OR(x,y) = NAND(NOT(x), NOT(y)) — verified for all 4 input pairs, matching real OR exactly.

Why this isn't just a curiosity

This is exactly why real chip manufacturing leans so heavily on NAND gates: building one reliable gate design and wiring it in different patterns is far more practical at scale than fabricating several different gate types. Chapter 6 picks this fact up directly when building real circuits.

Real Relevance: Logical vs. Bitwise Operators — a Genuine Trap

Most languages give you two separate operator families for what looks like the same idea: logical operators (and/or/not in Python) working on whole truthy/falsy expressions with short-circuit evaluation, and bitwise operators (&/|/^/~) working on individual bits — this chapter's own AND/OR/NOT/XOR, applied per-bit to an entire number at once.

A real, verified bug: operator precedence

& binds tighter than comparison operators in Python — so temperature > 10 & temperature < 30 silently parses as temperature > (10 & temperature) < 30, not the intended range check. Verified directly: with temperature = 50 (clearly not between 10 and 30), the un-parenthesized version wrongly returns True, while (temperature > 10) & (temperature < 30) correctly returns False. Always parenthesize each side when mixing comparisons with bitwise operators.

A real, verified gotcha: ~True is not False

~True evaluates to -2, not False — ~ is bitwise complement, not logical negation, and applying it to a boolean silently promotes it to an integer first. This is a genuinely recognized trap: recent Python versions emit a DeprecationWarning specifically for ~ on a bare bool, confirming this is a known real-world footgun, not an edge case invented for this lesson. Use not x for logical negation, ~ only when you deliberately mean bitwise complement.

Operators in Code

def NAND(x, y): return 1 - (x & y)

def NOT_from_nand(x): return NAND(x, x)
def AND_from_nand(x, y):
    n = NAND(x, y)
    return NAND(n, n)
def OR_from_nand(x, y):
    return NAND(NOT_from_nand(x), NOT_from_nand(y))

# verify every combination matches Python's own operators
for x in (0, 1):
    for y in (0, 1):
        assert AND_from_nand(x, y) == (x & y)
        assert OR_from_nand(x, y) == (x | y)
print("NAND builds AND and OR correctly for all inputs")

Hands-On Exercises

Exercise 1

Write out the full truth table for NOR(x,y) derived entirely from AND, OR, and NOT — that is, show (x + y)' matches the NOR truth table for all 4 input combinations.

📄 View solution

Exercise 2

Using this chapter's own NOT(x) = NAND(x,x) and OR(x,y) = NAND(NOT(x), NOT(y)) identities, trace through the computation of OR(0,1) step by step using only NAND operations, and confirm the final result is 1.

📄 View solution

Exercise 3

A piece of code checks if score > 90 & score < 100: in Python (using bitwise & instead of and). For score = 95, compute what this condition actually evaluates to (showing the precedence-driven parse), and explain why it happens to look correct here even though the operator choice is a real bug. Then show a specific score value where the bug produces a genuinely wrong result.

📄 View solution

Chapter 2 Quick Reference

AND (·): 1 only if both inputs are 1. OR (+): 1 if at least one input is 1. NOT ('): flips the value
XOR (⊕): 1 exactly when inputs differ — the basis of binary addition without carry (Chapter 7)
NAND/NOR: AND/OR immediately followed by NOT
NAND alone is functionally complete — verified to build NOT, AND, and OR for every input
Logical operators (and/or/not) and bitwise operators (&/|/^/~) are genuinely different — mixing them causes real, verified bugs (precedence, ~True)
Next chapter: The laws of Boolean algebra