Logic and Boolean Algebra — Math for IT

TL;DR

A proposition is a statement that is either true or false; connectives such as not, and, or and if-then combine propositions into bigger ones.
The implication p \rightarrow q is false in exactly one case: p true and q false. It is equivalent to \lnot p \lor q.
An implication is equivalent to its contrapositive \lnot q \rightarrow \lnot p, but not to its converse q \rightarrow p.
Two formulas are equivalent when their truth tables agree on every row; with n variables that is 2^{n} rows, so a computer can prove it by checking them all.
The laws of Boolean algebra (identity, complement, distributive, absorption, De Morgan and others) let you simplify conditions step by step without changing what they mean.

This page is the mathematical side of a subject that Boolean Logic in Programming Concepts introduces from the programmer's side: the operators AND, OR, NOT and XOR, their truth tables, precedence, short-circuit evaluation and logic gates. Read that page first if those are new; here we go further, into implication, proofs and the laws you use to rewrite a condition safely.

Propositions

A proposition is a statement that is either true or false, with nothing in between. Some examples from an operations team:

"The link between Amsterdam and Groningen is up." (true or false)
"INC-20419 has priority 1." (true or false)
"2^{10} = 1000." (false, but still a proposition)

Not every sentence qualifies. "Is the link up?" is a question, and "Restart the router" is a command; neither is true or false. A sentence with an open variable, such as "x \gt 90", is not a proposition either until you fill in x: it is a predicate, a template that becomes a proposition for each value. "CPU load of server x is above 90%" is a predicate; "CPU load of portal-01 is above 90%" is a proposition. Every if condition in code is a predicate that the program turns into a proposition at run time by filling in the current values.

In logic, propositions are named with small letters p, q, r, and their truth values are written 1 and 0 (or T and F). That keeps the focus on structure: the rules on this page hold whatever the letters stand for.

Logical connectives

A logical connective is an operator that builds a new proposition out of one or more propositions, where the truth of the result depends only on the truth of the parts. The five that matter in practice:

Connective	Symbol	Read as	True when	Python
negation	\lnot p	not p	p is false	`not p`
conjunction	p \land q	p and q	both are true	`p and q`
disjunction	p \lor q	p or q	at least one is true	`p or q`
implication	p \rightarrow q	if p then q	not (p true and q false)	`(not p) or q`
biconditional	p \leftrightarrow q	p if and only if q	both have the same value	`p == q`

The truth tables of NOT, AND and OR, and of exclusive or (XOR, p \oplus q), are on Boolean Logic, together with the rule that NOT binds tighter than AND, and AND tighter than OR. Implication and the biconditional are new here. In formulas, \rightarrow and \leftrightarrow bind loosest of all, so p \land q \rightarrow r means (p \land q) \rightarrow r. As with code: when in doubt, write the parentheses.

Implication: if p, then q

An implication p \rightarrow q is the proposition "if p, then q". p is called the hypothesis (or antecedent) and q the conclusion (or consequent). Its truth table surprises most people at first:

p	q	p \rightarrow q	p \leftrightarrow q
0	0	1	1
0	1	1	0
1	0	0	0
1	1	1	1

Think of an implication as a promise, and ask in which case the promise is broken. The change manager promises: "If the change is approved, it is deployed on Tuesday."

Approved and deployed on Tuesday: promise kept (row 4).
Approved and not deployed on Tuesday: promise broken (row 3). This is the only 0.
Not approved: the promise says nothing about this case, so it cannot be broken, whether or not something happens on Tuesday (rows 1 and 2). In logic an unbroken promise counts as true. This is called vacuous truth: the rule holds because its condition never applies.

Because the only false row is "p true and q false", the implication is the same as "not p, or q":

p \rightarrow q \;\equiv\; \lnot p \lor q

Most programming languages have no implication operator, and this equivalence is how you write one. The program below prints the truth tables of both new connectives:

from itertools import product

print("p     q     p->q  p<->q")
for p, q in product([False, True], repeat=2):
    print(f"{p!s:<6}{q!s:<6}{(not p) or q!s:<6}{p == q}")

p     q     p->q  p<->q
False False True  True
False True  True  False
True  False False False
True  True  True  True

The shaded area is where each formula is true. For p \rightarrow q, only "inside p but outside q" is false: the same area as \lnot p \lor q.

Many ways to say "if p then q"

Policies, requirements and contracts express implications in many forms. All of these mean p \rightarrow q:

if p, then q
q if p
p only if q
p is sufficient for q
q is necessary for p

"A user may log in to the admin portal only if they use multifactor authentication" is login → MFA: logging in without MFA breaks the rule, while using MFA does not oblige anyone to log in.

Worked example: checking a policy

Kestrel Energy's security policy says: "If a server stores customer data, its disks must be encrypted." Sanne de Vries wants a list of servers that break the rule.

Let c = "stores customer data" and e = "disks encrypted". The rule is c \rightarrow e.
A server complies when \lnot c \lor e is true.
A server violates the rule in the one false row: c \land \lnot e. Note that a server without customer data complies whether or not it is encrypted.

servers = [
    # name,    stores customer data, disks encrypted
    ("web-01", True,  True),
    ("web-02", False, False),
    ("db-01",  True,  False),
    ("log-01", False, True),
]
for name, customer_data, encrypted in servers:
    complies = (not customer_data) or encrypted
    print(f"{name:<7} complies: {complies}")

web-01  complies: True
web-02  complies: True
db-01   complies: False
log-01  complies: True

Converse, inverse and contrapositive

From one implication p \rightarrow q you can make three related ones by swapping and negating the parts:

Name	Formula	Same meaning as the original?
original	p \rightarrow q	—
converse	q \rightarrow p	no
inverse	\lnot p \rightarrow \lnot q	no (it is the contrapositive of the converse)
contrapositive	\lnot q \rightarrow \lnot p	yes, always

The contrapositive of p \rightarrow q is \lnot q \rightarrow \lnot p: "if not q, then not p". It always has the same truth value as the original, which you prove below with a truth table. An IT example: the monitoring is configured so that "if the uplink is down, an alert is raised".

Contrapositive, valid: "if no alert is raised, the uplink is not down". (Assuming the rule itself holds, which is exactly what you test when you check that monitoring works.)
Converse, not valid: "if an alert is raised, the uplink is down". The alert can have other causes, or be a false alarm; Tomasz Nowak in the network operations center still has to check.

When both directions hold, p \rightarrow q and q \rightarrow p, you have the biconditional p \leftrightarrow q: "p if and only if q". Definitions are biconditionals: "a number is even if and only if it is divisible by 2".

Equivalence, tautologies and proofs with truth tables

Two formulas are in logical equivalence when they have the same truth value for every possible assignment of truth values to their variables. It is written with \equiv: p \rightarrow q \equiv \lnot p \lor q. Equivalent formulas are interchangeable: you can replace one by the other in any condition without changing what it does.

A tautology is a formula that is true for every assignment, such as p \lor \lnot p ("the link is up or it is not up"). Its opposite, a formula that is false for every assignment, is a contradiction, such as p \land \lnot p. Two formulas A and B are equivalent exactly when A \leftrightarrow B is a tautology. In code, a condition that is a tautology always fires and a contradiction never does: both are usually bugs.

Worked example: proving the contrapositive

A truth table lists every combination, so it is a complete proof. To show p \rightarrow q \equiv \lnot q \rightarrow \lnot p:

Write all four combinations of p and q.
Add the helper columns \lnot q and \lnot p.
Fill in p \rightarrow q (0 only when p = 1, q = 0) and \lnot q \rightarrow \lnot p (0 only when \lnot q = 1 and \lnot p = 0).
Compare the two result columns row by row.

p	q	\lnot q	\lnot p	p \rightarrow q	\lnot q \rightarrow \lnot p
0	0	1	1	1	1
0	1	0	1	1	1
1	0	1	0	0	0
1	1	0	0	1	1

The last two columns agree in all four rows, so the formulas are equivalent. With n variables a table has 2^{n} rows: 8 for three variables, 1024 for ten. A program can check them all, which turns "I think these conditions mean the same" into a proof:

from itertools import product


def equivalent(f, g, n):
    """True if f and g agree on all 2**n combinations of n truth values."""
    return all(f(*v) == g(*v) for v in product([False, True], repeat=n))


def tautology(f, n):
    return all(f(*v) for v in product([False, True], repeat=n))


def implies(a, b):
    return (not a) or b


# contrapositive: equivalent; converse: not equivalent
print(equivalent(lambda p, q: implies(p, q), lambda p, q: implies(not q, not p), 2))
print(equivalent(lambda p, q: implies(p, q), lambda p, q: implies(q, p), 2))

# modus ponens: (p and (p -> q)) -> q is a tautology
print(tautology(lambda p, q: implies(p and implies(p, q), q), 2))
print(tautology(lambda p: p or not p, 1), tautology(lambda p: p and not p, 1))

True
False
True
True False

The third line checks modus ponens, the basic rule of reasoning: if p holds and p \rightarrow q holds, then q holds. Checking every row is the same idea as generating truth tables in Boolean Logic; for many variables (hundreds, in chip design) specialized tools called SAT solvers do it far more cleverly.

The laws of Boolean algebra

Truth tables prove one equivalence at a time. The laws below are equivalences that have been proved once and for all, so you can use them to rewrite formulas step by step, the way you use a \cdot (b + c) = a \cdot b + a \cdot c in ordinary algebra. Here 1 stands for "always true" and 0 for "always false".

Law	AND form	OR form
identity	p \land 1 \equiv p	p \lor 0 \equiv p
domination (null)	p \land 0 \equiv 0	p \lor 1 \equiv 1
idempotent	p \land p \equiv p	p \lor p \equiv p
complement	p \land \lnot p \equiv 0	p \lor \lnot p \equiv 1
double negation	\lnot \lnot p \equiv p
commutative	p \land q \equiv q \land p	p \lor q \equiv q \lor p
associative	(p \land q) \land r \equiv p \land (q \land r)	(p \lor q) \lor r \equiv p \lor (q \lor r)
distributive	p \land (q \lor r) \equiv (p \land q) \lor (p \land r)	p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)
absorption	p \land (p \lor q) \equiv p	p \lor (p \land q) \equiv p
De Morgan	\lnot (p \land q) \equiv \lnot p \lor \lnot q	\lnot (p \lor q) \equiv \lnot p \land \lnot q

A few things to notice:

Duality. Every law comes in a pair: swap \land with \lor and 0 with 1, and you get the other half.
Two distributive laws. In ordinary algebra only multiplication distributes over addition. In Boolean algebra both directions work: AND over OR, and OR over AND. The second one has no counterpart in school arithmetic (2 + 3 \cdot 4 \ne (2 + 3) \cdot (2 + 4)), so it is the law people forget.
De Morgan's laws say how a negation moves into parentheses; they are explained with a worked example on Boolean Logic. The same laws hold for sets, with complement, intersection and union; see Sets and Relations.

Every law in the table can be checked by brute force, as in the previous section:

from itertools import product


def equivalent(f, g, n):
    return all(f(*v) == g(*v) for v in product([False, True], repeat=n))


laws = [
    ("absorption", lambda p, q: p and (p or q), lambda p, q: p, 2),
    ("distributive (or over and)",
     lambda p, q, r: p or (q and r), lambda p, q, r: (p or q) and (p or r), 3),
    ("De Morgan", lambda p, q: not (p and q), lambda p, q: (not p) or (not q), 2),
    ("complement", lambda p: p or not p, lambda p: True, 1),
    ("wrong: not (p and q) == not p and not q",
     lambda p, q: not (p and q), lambda p, q: (not p) and (not q), 2),
]
for name, f, g, n in laws:
    print(f"{name}: {equivalent(f, g, n)}")

absorption: True
distributive (or over and): True
De Morgan: True
complement: True
wrong: not (p and q) == not p and not q: False

Simplifying conditions

Conditions in alert rules, firewall policies and code grow by accretion: someone adds a case, someone else adds an exception. The laws let you rewrite such a condition into a shorter one that is guaranteed to behave the same.

Worked example: an alert rule

A monitoring rule at Kestrel Energy reads: alert when the CPU is high and the server is not in maintenance, or when the CPU is high, the server is in maintenance and it runs a critical service. Write c = "CPU high", m = "in maintenance" and k = "critical service":

(c \land \lnot m) \lor (c \land m \land k)

Distributive (AND over OR, read backwards): both parts start with c, so take it out: c \land \bigl(\lnot m \lor (m \land k)\bigr).
Distributive (OR over AND) on the inner part: \lnot m \lor (m \land k) \equiv (\lnot m \lor m) \land (\lnot m \lor k).
Complement: \lnot m \lor m \equiv 1, so the inner part is 1 \land (\lnot m \lor k).
Identity: 1 \land (\lnot m \lor k) \equiv \lnot m \lor k.

(c \land \lnot m) \lor (c \land m \land k) \;\equiv\; c \land (\lnot m \lor k) \;\equiv\; c \land (m \rightarrow k)

The last form uses the implication law from above and reads well: "CPU high, and if the server is in maintenance, then only for critical services". A program confirms that no row of the truth table changed:

from itertools import product

original = lambda c, m, k: (c and not m) or (c and m and k)
simplified = lambda c, m, k: c and ((not m) or k)

print(all(original(*v) == simplified(*v) for v in product([False, True], repeat=3)))

# Simplify: (on_call and not weekend) or (on_call and weekend)  ==  on_call
f = lambda on_call, weekend: (on_call and not weekend) or (on_call and weekend)
print(all(f(a, b) == a for a, b in product([False, True], repeat=2)))

True
True

The second check is a pattern worth recognizing: (a \land \lnot b) \lor (a \land b) \equiv a (distributive, complement, identity). If both branches of a condition do the same thing for b and for \lnot b, the test on b is dead weight.

Quantifiers: for all and there exists

Many IT statements are about a whole collection: "all servers are patched", "some backup failed last night". Logic writes them with two quantifiers:

\forall x \in S : P(x), "for all x in S, P(x)": true when the predicate holds for every element.
\exists x \in S : P(x), "there exists an x in S with P(x)": true when it holds for at least one.

For a finite set, "for all" is a long AND and "there exists" a long OR. De Morgan's laws therefore carry over, and they tell you how to negate such a statement:

\lnot \forall x : P(x) \;\equiv\; \exists x : \lnot P(x) \qquad \lnot \exists x : P(x) \;\equiv\; \forall x : \lnot P(x)

"Not all servers are patched" means "at least one server is not patched", not "no server is patched". Python's all() and any() are exactly these two quantifiers:

patched = {"web-01": True, "web-02": True, "db-01": False}

print(all(patched.values()))                       # for all: patched
print(any(not ok for ok in patched.values()))      # exists: not patched
print((not all(patched.values())) == any(not ok for ok in patched.values()))
print(sorted(name for name, ok in patched.items() if not ok))

print(all([]), any([]))                            # empty collection

False
True
True
['db-01']
True False

The last line is vacuous truth again. "All servers in an empty list are patched" is true, because there is no server that breaks it; "some server in an empty list is patched" is false. In monitoring this can bite: a check "all backups succeeded" that receives an empty list because the backup job never ran reports success. Test for an empty input separately.