[Beginner] — Propositions, predicates, quantifiers, and the difference between an argument that’s valid and one that’s merely persuasive.

Propositional logic

A proposition is a statement that is either true or false. “It is raining.” "" is not a proposition until you know .

The connectives, and note that three of them behave exactly like operators you already use:

SymbolNameCodeTrue when
negation!p is false
conjunctionp && qboth
disjunctionp || qat least one (inclusive)
implication— false, or true
biconditionalp == qsame truth value

is inclusive or. English “or” is often exclusive (“tea or coffee”); mathematical or is not. XOR is written .

Implication is the strange one

— “if then ” — is where everyone stumbles, and it’s worth stopping on.

TTT
TFF
FTT ← surprising
FFT ← surprising

When is false, is true regardless of . This is vacuous truth.

“If the moon is made of cheese, then I am the king of France” is true.

Why it’s defined this way: an implication claims only that you can’t have true and false. It makes no claim about what happens when is false, and a claim that says nothing is not violated.

It’s less strange in code than it looks. Consider:

for (x in emptyList) { assert(f(x)) }

This passes. “All elements satisfy ” is true of an empty list — vacuously, because there’s no counterexample. Every all() on an empty collection returns true, in every language, for exactly this reason.

And the key identity:

Which is how you’d implement it: !p || q. Implication isn’t a mysterious new operation — it’s shorthand for a disjunction.

Converse, inverse, contrapositive

Given :

FormEquivalent to original?
ConverseNo
InverseNo
ContrapositiveYes

“If it’s raining, the ground is wet” does not mean “if the ground is wet, it’s raining” (the sprinkler). It does mean “if the ground isn’t wet, it isn’t raining.”

Two practical consequences:

Confusing a statement with its converse is the most common reasoning error there is — in code review, in debugging, in medical statistics, everywhere. “All bugs of this type show symptom X” does not mean “symptom X means this bug type”.

The contrapositive is a proof technique. If proving directly is awkward, prove instead — it’s the same statement and is often much easier. → Proof Techniques

Equivalences worth knowing

De Morgan’s laws — the ones you’ll use constantly:


Negating an AND gives an OR, and vice versa. This is why

if (!(a && b))     is      if (!a || !b)

and getting it wrong is a classic bug. When you invert a compound condition, the connective flips too.

The rest, briefly:



Tautology — true under every assignment. Contradiction — false under every assignment. Satisfiable — true under at least one.

That last word is doing a lot of work in practice. Determining whether a propositional formula is satisfiable is SAT, the original NP-complete problem — and modern SAT solvers, despite the worst case being exponential, routinely handle formulas with millions of variables. They’re what verify hardware designs, solve package-dependency resolution, and drive symbolic execution engines. → NP-completeness

Predicate logic

Propositional logic can’t express “every integer has a successor” — you’d need infinitely many propositions. Predicate logic adds variables and quantifiers.

A predicate is a proposition with a variable: ” is prime”. Not true or false until is fixed or quantified.

Universal: — “for all , ”

Existential: — “there exists an such that ”

“For every integer there’s a larger one.” True.

Order matters, enormously


Completely different claims. The second implies the first; the first does not imply the second.

This distinction shows up constantly in computing. “For every input there’s an algorithm that solves it quickly” (trivially true — hardcode the answer) versus “there’s an algorithm that solves every input quickly” (the actual question). Getting the quantifier order wrong turns a hard claim into a vacuous one.

It’s also exactly the difference between - definitions in analysis, and between “eventually consistent” and “always consistent” in distributed systems.

Negating quantifiers

The rule you’ll use most, and it’s De Morgan generalised:


“Not everything is ” means “something is not ”. To disprove a universal claim, produce one counterexample. To disprove an existential claim, you must show nothing works — much harder.

This asymmetry is why bugs are easy to demonstrate and correctness is hard to establish. A test is a search for a counterexample to “the code is always right”.

Mechanically: to negate, walk inward flipping every quantifier and negating the body.

Arguments and validity

An argument is premises plus a conclusion. It’s valid if the conclusion follows necessarily — whenever the premises are all true, the conclusion must be.

Validity is about form, not truth. A valid argument from false premises can reach a false conclusion. A sound argument is valid and has true premises — that’s what you actually want.

The rules of inference, which are just named valid patterns:

NameFromConclude
Modus ponens,
Modus tollens,
Hypothetical syllogism,
Disjunctive syllogism,

And the two invalid patterns that look valid — worth being able to name, because they’re the errors people actually make:

Affirming the consequent: from and , concluding . Invalid. “The tests pass, therefore the code is correct” — tests passing is a consequence of correctness, not evidence sufficient for it.

Denying the antecedent: from and , concluding . Invalid. “We didn’t deploy, so it can’t be our fault.”

Both are the converse/inverse confusion from earlier, in argument form. Recognising them is one of the more directly useful things in this note.

Where logic shows up in computing

Boolean expressions — directly, and De Morgan is how you simplify them.

Digital circuits — AND/OR/NOT gates are the connectives in silicon. Circuit minimisation is logical simplification. → Digital and Analog

Type systems — the Curry–Howard correspondence says propositions are types and proofs are programs. A function of type A → B is a proof that implies . This isn’t an analogy; it’s an isomorphism, and it’s the foundation of proof assistants like Coq, Lean and Agda. → Type Systems

SQL WHERE clauses — predicate logic, and NULL introduces a genuine third truth value, which is why NULL = NULL is neither true nor false and catches people out. → Databases

Formal verification — TLA+, model checkers, SMT solvers. Specifying “this can never happen” precisely enough to check exhaustively. → Testing Distributed Systems

Preconditions, postconditions, invariants — design by contract is applied predicate logic.


↑ Back to Discrete Mathematics