[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:
| Symbol | Name | Code | True when |
|---|---|---|---|
| negation | !p | is false | |
| conjunction | p && q | both | |
| disjunction | p || q | at least one (inclusive) | |
| implication | — | false, or true | |
| biconditional | p == q | same 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.
| T | T | T |
| T | F | F |
| F | T | T ← surprising |
| F | F | T ← 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 :
| Form | Equivalent to original? | |
|---|---|---|
| Converse | No | |
| Inverse | No | |
| Contrapositive | Yes |
“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:
| Name | From | Conclude |
|---|---|---|
| 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.
Related
- Proof Techniques — using this to establish things
- Sets, Relations and Functions — the objects logic talks about
- Complexity Classes — where SAT becomes central
- Discrete maths map
Software engineering
Infrastructure & security
Computer science
Hardware & engineering