Propositional Logic and Truth Tables

Hook #

An AI just generated a conditional with three negations and an unless. You read it. You think it's right. You ship it.

Six months later, a customer hits the one branch nobody traced through, and a refund goes to the wrong account. The AI didn't make that mistake. You did — when you read the conditional and didn't actually evaluate it.

You won't write more conditionals after this. You'll be reading more of them, written by something that doesn't care if it's right. The math you'll learn from MIT — they teach it cleanly, freely. What we set up is why it matters, the engineer's-lens you can carry into the chapter, and the check on whether it actually landed when you come back.

What you'll be able to do by the end of this lesson #

• Recognise when two boolean expressions are logically equivalent — without testing every case.
• Translate an English sentence with "if," "and," "or," and "unless" into a formal expression you can verify.
• Simplify a tangled conditional using De Morgan's laws — turn three nested negations into one readable statement.
• Look at two conditionals that do the same thing and explain which one is easier to read, and what makes it easier — beyond personal preference.

Why this matters here #

This is the path's first lesson, and it earns that position because everything downstream depends on it. The next lesson adds variables to propositions and gives you predicate logic. The lesson after that uses the equivalences you'll learn here as the engine of every proof. Beyond this course: every database WHERE clause, every type system, every access-control rule, every static analyser is built on what you're about to learn.

When you come back from MIT chapter 1, our AI tutor — Bodhi — will check your understanding by asking you to explain things in your own words and work problems. Not a quiz. A conversation that tells us (and you) whether the chapter actually landed.

A quick try before we start #

Suppose your team has this rule:

"If your code passes all our tests, then you can deploy."

The CI configuration has been broken for a week. The test suite isn't running at all. Can you deploy?

Sit with the question for a minute. Notice if you feel pulled toward two different answers. We'll come back to this.

The engineer's lens #

Vacuous truth — the failure mode no engineer learns to look for #

Vacuous truth is the failure mode no engineer learns to look for. The rule says "if some condition is met, then a guarantee holds" — and when the condition never happens, the rule is technically satisfied without the guarantee ever being checked. The system is doing what it promised. The engineer is doing what they promised. And something is still wrong. The deploy rule from the start of this lesson is one shape of it: yes, technically you can deploy, because no test failed, because no test ran. The rule held. The system shipped broken anyway. The math isn't broken — implication is doing exactly what it's defined to do. The trap is the engineer who reads the rule and doesn't ask "is the condition meaningfully met, or am I just safe by accident?" That question is what discrete math gives you. Without the formalism, you have an instinct that something feels off. With it, you have a name for the shape, and a habit of looking for it.

Equivalence — the only binary answer in your codebase #

Logical equivalence is the only formal claim in this lesson with a binary answer. Two expressions are either equivalent or they're not — every row of the truth table either matches or it doesn't, and there's no "it depends." That's rare in software. Most of what an engineer reasons about — readability, design, performance — is matter of judgement. Equivalence isn't. And because it isn't, it's the foundation under everything that needs to be right. Refactoring a conditional is substituting one expression for an equivalent one. A compiler optimising your code is doing the same thing. A static analyser proving your code safe is doing the same thing. Every time you trust that the rewritten version of a function "does the same thing," you're trusting an equivalence claim. You're working with zeros and ones; getting this right is the contract under everything else.

IFF — the connective for definitions #

IFF is the connective for definitions. Most things engineers reason about formally are biconditional — they hold in both directions. A number is even if and only if it divides cleanly by 2. A transaction commits if and only if every write succeeded. A user has admin access if and only if the role table records it. Without IFF, you'd write each of these definitions twice — once forward (if even, then divisible by 2) and once backward (if divisible by 2, then even) — and you'd have to remember they're paired. IFF compresses that. It's also the connective that catches the mistake learners make most often when reading or writing rules: confusing implication for biconditional. All admins are users doesn't mean all users are admins — and the day you assume otherwise is the day a permission check ships wrong.

What to focus on in MIT 6.042J Chapter 1 #

Now go read the chapter. The full PDF is in the Resources panel. ~25 pages. Take notes; you'll need them.

A specific guide so the chapter doesn't waste your time:

• Sections 1.1 and 1.2 (Propositions, Logical Connectives). Essential. Read carefully. Don't skim the (tt/tf/ft/ff) row-label notation MIT uses for IMPLIES — they reuse those labels throughout the textbook for the rest of the course.
• The IMPLIES truth table specifically. Sit with it until vacuous truth stops surprising you. The Quick-try at the start of this lesson was an instance of it; if you still feel pulled toward "no, you can't deploy," the chapter is the place to resolve it.
• De Morgan's laws (in the Logical Equivalence section). Trace the truth-table proof yourself once. Don't just read it. The willingness to do the bookkeeping is what makes this stuff stick.
• Section 1.4 (Validity) — skim. Useful concept, light on engineering payoff for our path. Come back if a later lesson needs it.
• Section 1.5 (Satisfiability and SAT, P-vs-NP teaser) — optional. Beautiful but tangential. The Algorithms course revisits SAT properly later.

You don't need to do MIT's exercises in the chapter — we'll have you do ours when you come back. Read for understanding; we'll handle the practice.

When you come back #

After you've read MIT chapter 1, come back here. Two things to do — one short, one longer. Both are how we check (and how Bodhi checks, when you're working with the AI tutor) whether the chapter actually landed. If something here doesn't come easily, that's a signal to revisit, not a failure.

Explain it back to me #

Pick a colleague in your head — someone who writes code daily but has never sat with formal logic. Explain to them, in your own words: why is the statement "if pigs can fly, then 1+1 = 3" technically true? Don't appeal to "the textbook says so" or "the truth table says so." Give the actual reason — the one that lets a sensible person agree with you, not just trust you.

If you can do that in two or three sentences, you understand vacuous truth. If you can't, the chapter hasn't landed yet — go back to MIT section 1.2 (the IMPLIES discussion) and read it again, slowly. The willingness to notice you don't actually understand something is more useful than the willingness to keep moving.

A small exercise #

Here is a real-world authorisation rule someone might ship:

rubydef can_view_invoice?(user, invoice)
  return false if user.nil?
  return true if user.admin?
  !user.banned? && (invoice.owner_id == user.id || invoice.shared_with?(user))
end

The third return statement is doing a lot. Your task: rewrite the third statement using De Morgan's laws so the negation is at the outermost level, not buried inside. Then look at both versions and decide which one you'd rather review at 2am — and write one sentence explaining why.

Where this connects #

This is the path's first lesson, so there is no backward connection — only forward ones. The next lesson, Predicate Logic and Quantifiers, takes the propositions you've just learned to manipulate and adds variables and quantifiers — "for all users in the table, P holds" and "there exists a record where Q is true." Every database WHERE clause is a quantifier. Every loop invariant is a universal claim. Every type predicate is a domain restriction.

After that, Proof Techniques and Mathematical Induction uses the equivalences from this lesson as the engine of every proof. The contrapositive trick from this lesson becomes a proof method. Vacuous truth becomes a recognised pattern. De Morgan's becomes the move that makes proofs readable.

Beyond this course, propositional logic shows up everywhere there's structured reasoning under the hood: SQL query optimisation, type checking, static analysis, compiler proofs, access-control systems, the verification of distributed protocols. You'll meet it again, at depth, in places you didn't expect. The investment you made in this lesson compounds.