# Propositional Logic > The algebra of true and false: how AND, OR, and NOT combine statements, how truth tables prove what a compound claim really does, and the equivalences (like De Morgan's laws) that let you rewrite and negate conditions with confidence. --- # Propositional Logic You write `if (user.isActive && !user.isBanned)` without blinking. That `&&` and that `!` are *propositional logic* - the oldest, most useful corner of logic, and the one that maps most directly onto the code you write every day. It's the algebra of statements that are either true or false, and the rules for combining them. Most people pick this up by osmosis and end up with blind spots: an `or` that didn't mean what they thought, a negated condition that quietly inverted the wrong thing, an `if` that's impossible to satisfy. This guide closes those gaps. By the end you'll be able to take any tangle of `and`s, `or`s, and `not`s and say *exactly* what it's true for - and rewrite it into something simpler without changing its meaning. It builds directly on [What Logic Actually Is](/guides/what-logic-actually-is): there you learned what a statement is and what it means for reasoning to be valid. Here we make statements *combine*. ## How to read this - **Want the core fast?** [Phase 1](01-connectives-and-or-not.md) covers the three connectives that do most of the work. - **Want real fluency?** Read all three - Phase 2 gives you the tool (truth tables) that turns "I think this is right" into "I can prove this is right." ## The phases 1. **[Connectives: AND, OR, NOT](01-connectives-and-or-not.md)** - the three building blocks, what each one *precisely* means, and the inclusive-or trap. 2. **[Truth Tables](02-truth-tables.md)** - the machine for evaluating any compound statement, plus tautologies and contradictions. 3. **[Equivalences & De Morgan's Laws](03-equivalences-and-de-morgan.md)** - rewriting expressions without changing their meaning, and how to negate a condition correctly every time. > The next guide, [Implication & Conditionals](/guides/implication-and-conditionals), tackles the > trickiest connective of all - "if P then Q" - which deserves its own guide. --- # Connectives: AND, OR, NOT You already use these. Every `if (loggedIn && isAdmin)`, every `if (cached || fresh)`, every `if (!expired)` is propositional logic. You may never have called it that. You learned the rules by writing code that broke, then fixing it. This phase names what you already half-know and tightens it. Once the three connectives are precise in your head, you stop second-guessing conditions. You'll read a tangled `if` and know exactly when it fires - no running it three times to be sure. One at a time: AND, then OR, then NOT. Three operators. Every compound condition you'll ever write is built from these. ## 📝 Quick recap: propositions and connectives A **proposition** is a statement that is either true or false - nothing in between. "It is raining." "The user is logged in." "7 is even" (false, but still a proposition). If you can ask "is that true?" and expect a yes/no answer, it's a proposition. A **connective** combines propositions into a bigger one. "It is raining AND I have an umbrella" is one statement built from two. The whole thing is true or false, and *its* truth depends on the truth of its parts plus which connective you used. That's the entire game this phase: given the truth of the parts, what's the truth of the whole? (New to all this? Start at [/guides/what-logic-actually-is](/guides/what-logic-actually-is).) ## AND (conjunction, ∧) AND is the demanding one. "P AND Q" is true **only when both P and Q are true**. The moment either part is false, the whole thing is false. Think of a contract with two required conditions. "You get in if you have a ticket AND you're on the list." Miss either one and you're out. ```text true AND true → true true AND false → false false AND true → false false AND false → false ``` Three of the four rows are false. AND is hard to satisfy - it says yes only when everything lines up. The symbol is **∧** (a pointy "and"); in code it's `&&`. ## OR (disjunction, ∨) OR is the generous one. "P OR Q" is true when **at least one** of them is true. One part true is enough. Both true is also fine. ```text true OR true → true true OR false → true false OR true → true false OR false → false ``` Only one row is false - the row where *everything* is false. OR is easy to satisfy: it says no only when both parts fail. The symbol is **∨** (a pointy "or"); in code it's `||`. That top row catches people. `true OR true` is **true**, not false. That's the whole gotcha, so let's sit with it. ### ⚠️ The inclusive-or trap Read this: "You can have soup or salad." In a restaurant, that means *one or the other, not both*. Ask for both and the server raises an eyebrow. Everyday English "or" is often **exclusive** - it quietly means "but not both." Logical OR is **inclusive**. "P OR Q" is true even when both are true. No eyebrow. `true || true` is `true`, full stop. This isn't a quirk to memorize and resent - it's the more useful default. "Notify the user if they have unread messages OR pending invites" should fire when they have *both*. You almost never want it to go quiet because two things are true at once. The "exactly one, not both" meaning does exist in logic. It's a separate connective called **XOR** (exclusive or), with its own symbol (⊕) and its own rules. We'll meet it later. For now, burn in: > 💡 Logical OR is inclusive. "At least one is true" - including the case where both are. ## NOT (negation, ¬) NOT is the odd one out, usefully so: it takes **one** input, not two. It's **unary**. AND and OR each chew on two propositions; NOT works on a single one and flips it. "NOT P" is true exactly when P is false. It's the toggle. ```text NOT true → false NOT false → true ``` That's the whole table. Apply NOT twice and you're back where you started: `NOT (NOT P)` has the same truth as `P`. The symbol is **¬**; in code it's `!`. NOT is small but bugs love to hide there, because people misread *what* they're negating. `!loggedIn || isAdmin` negates only `loggedIn`, not the whole expression. Where the NOT reaches - its **scope** - matters as much as the NOT itself. Grouping and precedence is a rabbit hole of its own; for now, notice that NOT attaches to one thing, and be deliberate about which thing. ## The three, side by side Symbol, plain name, and code form together, so the translation becomes automatic: ```text ∧ AND (conjunction) && true only when both are true ∨ OR (disjunction) || true when at least one is true ¬ NOT (negation) ! flips true ↔ false (one input) ``` A logic paper shows ∧ ∨ ¬. A codebase shows `&&` `||` `!`. Same three ideas, different clothes. Being fluent both directions is most of what "knowing propositional logic" means at this stage. ## 🪖 For builders In your editor, the mapping is exact: - `&&` is AND - both sides must be truthy. - `||` is OR - at least one side truthy. (Inclusive. `true || true` is `true`.) - `!` is NOT - flips a boolean. One extra thing your code does that pure logic doesn't: **short-circuit evaluation**. With `a && b`, if `a` is false, your program never evaluates `b` - the answer is already false. With `a || b`, if `a` is true, it skips `b` for the same reason. The *result* matches the truth tables above; the difference is that the second operand might not run. That's why `user && user.name` is safe - if `user` is null, `user.name` is never touched. We're studying truth values here, not evaluation order. But the short-circuit is worth knowing, because it's the bridge between "AND is true only when both are true" and the defensive `if` checks you write every day. ## Recap - A **proposition** is true or false. A **connective** combines propositions into a bigger true-or-false statement. - **AND (∧, `&&`)** - true *only* when both parts are true. Hard to satisfy. - **OR (∨, `||`)** - true when *at least one* part is true, including when both are. **Inclusive.** Easy to satisfy. - **NOT (¬, `!`)** - unary; flips true and false. - Everyday "or" is often exclusive ("soup or salad"); logical OR is not. The exclusive version is **XOR**, a separate connective. You now have the three building blocks. Next, we lay them out properly - not as inline lists, but as full **truth tables**, the tool that lets you analyze *any* compound statement no matter how tangled. ## Open-ended exercise Take this real condition from a codebase: ```text if (!(user.isGuest || user.isBanned)) { allowAccess(); } ``` Rewrite it - without changing its meaning - into a condition that uses `&&` instead of `||`, by applying De Morgan's law. Then write, in one sentence, what the rewritten condition checks for. The goal is to make the guard so clear that a teammate can read it and immediately understand the rule. Here's a quick check before you move on. ```quiz [ { "q": "P is true and Q is false. What is \"P AND Q\"?", "choices": ["true", "false", "It depends on the order", "Undefined"], "answer": 1, "explain": "AND is true only when both parts are true. Q is false, so the whole conjunction is false." }, { "q": "Logical OR is inclusive. So when both P and Q are true, \"P OR Q\" is:", "choices": ["false, because that's the exclusive case", "true, because at least one is true", "true only if you use XOR", "false unless exactly one is true"], "answer": 1, "explain": "Inclusive OR is true whenever at least one part is true - and that includes the case where both are true. The 'exactly one, not both' meaning is XOR, a different connective." }, { "q": "P is false. What is \"NOT P\"?", "choices": ["false", "true", "still false", "It needs a second input"], "answer": 1, "explain": "NOT flips the value. P is false, so NOT P is true. NOT is unary - it takes a single input, no second operand needed." } ] ``` Watch it animated: [boolean operators](/explainers/BooleanOperators.dc.html) --- # Truth Tables In [Phase 1](01-connectives-and-or-not.md) you met the connectives: AND, OR, NOT. Each has a fixed meaning. But the moment you combine them, a new question shows up that the connectives alone can't answer. Look at this statement: ```text (A ∧ ¬B) ∨ C ``` For exactly which inputs is the whole thing true? You could squint and guess. You could talk yourself into an answer that *feels* right. But feeling right and being right are different things, and with logic the gap between them is where bugs live. There's a way to **know** - not guess, not estimate. You enumerate every possibility and check each one. That tool is the truth table, and it's the most reliable thing in logic: it can't bluff, skip a case, or change its mind under pressure. ## What a truth table is A truth table is a complete list of every combination of true/false values your input variables can take, plus a column showing the result for each. The word doing the work is **every**. That's the whole idea. You don't sample. You don't pick the "interesting" cases. You write down *all* of them, then evaluate the statement once per row. How many rows is "all of them"? Each variable is independent and can be true or false - two choices. Two variables give 2 × 2 = 4 combinations. Three give 2 × 2 × 2 = 8. The pattern: ```text n variables → 2^n rows ``` So one variable gives 2 rows, two gives 4, three gives 8, four gives 16, ten gives 1024. The count doubles with each new variable - worth remembering, because "exhaustive" gets expensive fast. We usually write `T` for true and `F` for false to keep the columns narrow. ## Build one step by step Let's build the table for `A ∧ ¬B` - "A is true and B is false." **Step 1 - list every input combination.** Two variables, so 2^2 = 4 rows. A reliable way to miss nothing: count in binary. Let the left column flip slowly and the right flip fast. ```text A B T T T F F T F F ``` That's all four cases, guaranteed, because we were mechanical rather than creative. **Step 2 - add a column for each intermediate piece.** Our statement uses `¬B`, so compute that first. `¬B` is B flipped: ```text A B ¬B T T F T F T F T F F F T ``` **Step 3 - combine.** Now `A ∧ ¬B` is true only when A is true *and* `¬B` is true. Read across each row and apply AND: ```text A B ¬B A ∧ ¬B T T F F T F T T F T F F F F T F ``` There's the complete answer. `A ∧ ¬B` is true in exactly one situation: A true, B false. Every other case is false. No guessing - the table told you. Building intermediate columns first is why this scales. You never evaluate the whole expression in your head at once; you compute small pieces and assemble them, one column at a time. A three-variable expression works identically, only taller. The opening statement, `(A ∧ ¬B) ∨ C`, has three variables, so it needs 2^3 = 8 rows - the four rows above repeated once with `C = T` and once with `C = F`, then an `(A ∧ ¬B)` column, then a final `∨ C` column. Same recipe, more rows. ## Tautology, contradiction, contingent Once you can read a result column, you can sort any statement into one of three buckets. A **tautology** is true in *every* row - true no matter what the inputs do. The classic example is `A ∨ ¬A` ("A, or not A"): ```text A ¬A A ∨ ¬A T F T F T T ``` Either A is true or its negation is - there's no third option, so the whole thing is always true. The result column is all `T`. That's a tautology. A **contradiction** is the mirror image: false in *every* row. Take `A ∧ ¬A` ("A and not A"): ```text A ¬A A ∧ ¬A T F F F T F ``` A can't be both true and false at once, so this is never satisfiable. The result column is all `F`. That's a contradiction. Everything else - statements whose truth *depends* on the inputs, like `A ∧ ¬B` from before - is **contingent**. Most useful statements are contingent. They carry information, because their answer changes with the situation. > 📐 A tautology is true because of its *form*, not because of any fact about the world. > `A ∨ ¬A` holds whether A means "it's raining" or "the server is up." That's what makes > tautologies the bedrock of valid reasoning - see [Why math isn't your enemy](/guides/why-math-isnt-your-enemy) > for more on why structure beats intuition. ## For builders If you write code, you already work with truth tables - under another name. - **A truth table is testing every input combination.** It's exhaustive case coverage: the table for a boolean function is the same as a test suite that checks all 2^n inputs. When you enumerate the cases, you can't miss one. - **A contradiction is dead code.** A condition that's always false is an `if` branch the program can never enter - `if (loggedIn && !loggedIn)`. The body is unreachable. - **A tautology is a redundant check.** A condition that's always true is an `if` that's pointless to write - `if (x > 0 || x <= 0)` is `if (true)`. The guard isn't guarding anything. Spotting these before you ship saves you from a feature flag that's secretly never on, or a validation check that secretly always passes. 💡 **Key point:** When you're unsure what a boolean expression does, build its truth table. Your intuition can talk itself into a wrong answer; a complete table lists every case and evaluates each one mechanically. It cannot lie, and it cannot skip the case that would have bitten you. ## Recap - A **truth table** lists every combination of true/false for the inputs, plus a result column. It's exhaustive on purpose - that's the whole point. - **n variables → 2^n rows.** The count doubles with each new variable. - **Build it in steps:** list all input combinations (count in binary so you miss none), add a column for each intermediate piece, then combine. - A **tautology** is true in every row (`A ∨ ¬A`). A **contradiction** is false in every row (`A ∧ ¬A`). Everything else is **contingent** - it depends on the inputs. - For builders: a truth table is full case coverage, a contradiction is dead code, a tautology is a redundant check. ## Open-ended exercise Build a truth table for the statement `(P ∧ Q) → R`. List all eight rows (three variables), compute the output for each, and then ask: is this statement a tautology, a contradiction, or neither? A tautology is true in every row; a contradiction is false in every row. If it's neither, point to the rows that make it true and the rows that make it false. Check yourself: ```quiz [ { "q": "A compound statement has 4 input variables. How many rows does its truth table have?", "choices": ["8", "16", "4", "32"], "answer": 1, "explain": "Each variable doubles the number of combinations: n variables give 2^n rows. With 4 variables that's 2^4 = 16." }, { "q": "What is a tautology?", "choices": ["A statement that is false in every row of its truth table", "A statement whose truth depends on its inputs", "A statement that is true in every row of its truth table", "A statement with no variables"], "answer": 2, "explain": "A tautology is true no matter what the inputs are - its result column is all true (e.g. A ∨ ¬A). The all-false version is a contradiction; the depends-on-inputs version is contingent." }, { "q": "What is a truth table actually used for?", "choices": ["To list every input combination and show the exact result for each one", "To pick the most likely value of a statement", "To shorten a statement so it has fewer variables", "To prove a statement is true without checking any cases"], "answer": 0, "explain": "A truth table enumerates every possible combination of inputs and evaluates the statement on each, so you know exactly when it's true or false - no guessing, no skipped cases." } ] ``` Watch it animated: [truth tables](/explainers/TruthTables.dc.html) --- # Equivalences & De Morgan's Laws In Phase 2 you learned to build truth tables - the row-by-row record of when a statement is true and when it's false. This phase puts that tool to work. Once you can write a statement's truth table, you can answer a deeper question: *are these two statements actually the same?* And from that comes the single most useful rule in everyday logic - De Morgan's laws - what you reach for every time you need to flip a condition around. ## When two statements are the same Look at these two sentences: "It is not the case that the door is unlocked" and "The door is locked." Different words, same meaning. In logic we want a way to say "same meaning" that doesn't depend on how clever you are with English. The answer is the truth table. Two statements are **logically equivalent** when they have the *same truth table* - the same true/false result in every single row, for every combination of inputs: ```text A ≡ B means A and B are true in exactly the same situations ``` Why it matters: equivalent statements are **interchangeable**. Swap one for the other anywhere, and nothing about when things come out true or false changes. That's what lets you take a tangled condition and replace it with a cleaner one that means the exact same thing. Note what equivalence is *not*: not "they're true right now," but "they agree in every possible row" - you check it by lining up the two truth tables and confirming the final columns match top to bottom. ## De Morgan's laws Here's the situation you'll hit constantly. You have a statement built with AND or OR, and you need its opposite - its negation. The tempting move is to stick a NOT in front and leave everything else alone. That move is a trap, and De Morgan's laws get it right: ```text ¬(A ∧ B) ≡ ¬A ∨ ¬B ¬(A ∨ B) ≡ ¬A ∧ ¬B ``` In plain English: - **not (both A and B)** is the same as **(not A) OR (not B)**. If it's not true that you have *both*, then at least one is missing. - **not (either A or B)** is the same as **(not A) AND (not B)**. If it's not true that you have *either one*, then you're missing *both*. A real example for the first law: say the rule is "you need both a ticket AND a passport." When is that rule violated? When you're missing the ticket, OR missing the passport, OR missing both. You don't need to be missing both to fail - missing *one* is enough. That's exactly `¬A ∨ ¬B`. ### Proving one of them Let's not take it on faith. Here's the truth table for `¬(A ∧ B)` and `¬A ∨ ¬B` side by side. If the last two columns match in every row, they're equivalent. ```text A B A∧B ¬(A∧B) | ¬A ¬B ¬A∨¬B ----- ----- ----- ------ | ----- ----- ------ T T T F | F F F T F F T | F T T F T F T | T F T F F F T | T T T ``` Compare the `¬(A∧B)` column with the `¬A∨¬B` column: `F, T, T, T` in both. They agree in all four rows - that's the proof, they're equivalent. The other law, `¬(A ∨ B) ≡ ¬A ∧ ¬B`, checks out the same way; building that table is a worthwhile exercise to convince yourself. ## The key insight: NOT flips the connective Look closely at what happened. We started with an AND inside the parentheses. After pushing the NOT inward, we ended up with an OR - the connective changed. This is the heart of De Morgan, and the part people get wrong: > When you push a NOT inside a group, **AND flips to OR, and OR flips to AND.** You can't sprinkle NOTs on the pieces and keep the same connective - the connective itself has to switch. Say it as a chant: *negate each part, and flip the operator.* That single habit prevents the most common logic bug there is. ## ⚠️ The classic bug: negating an AND wrong You have a condition `a && b` and you want its opposite. Your instinct is to negate each piece and keep the AND: ```text WRONG: not (a && b) → !a && !b RIGHT: not (a && b) → !a || !b ``` The wrong version says "*both* are false." But the opposite of "both true" isn't "both false" - it's "*not* both true," which means at least one is false. That's an OR, not an AND. Concrete check: suppose `a` is true and `b` is false. Then `a && b` is false, so its negation should be **true**. The wrong version `!a && !b` evaluates to `false && true` = `false` - wrong. The right version `!a || !b` evaluates to `false || true` = `true` - correct. ## A few more equivalences worth knowing De Morgan is the star, but a handful of others round out your toolkit: - **Double negation:** `¬¬A ≡ A` - two NOTs cancel out. "Not not raining" means "raining." - **Commutativity:** `A ∧ B ≡ B ∧ A` and `A ∨ B ≡ B ∨ A` - order doesn't matter for a plain AND or OR. - **Distribution:** `A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C)` - an AND spreads across an OR much like multiplication spreads across addition. You don't need to memorize these the way you need De Morgan, but recognizing them helps when you're simplifying a messy expression and want to know which rewrites are legal. ## Two equivalences that change how you read code **Implication as disjunction:** `P → Q ≡ ¬P ∨ Q`. An "if… then…" is logically the same as "either the if-part is false, or the then-part is true" - the bridge between propositional logic and the `if` statements you write. The whole statement `P → Q` is only false when `P` is true and `Q` is false. **Biconditional (if and only if):** `P ↔ Q ≡ (P → Q) ∧ (Q → P)`. "P if and only if Q" means both directions hold - in code, the "both or neither" pattern. It's `true` when P and Q agree (both true or both false) and `false` when they differ. The XOR gate you met in [boolean algebra](/guides/boolean-algebra-and-logic-gates) is the *negation* of the biconditional: `P ⊕ Q ≡ ¬(P ↔ Q)` - XOR fires on mismatch, biconditional fires on match. ## For builders De Morgan is how you read and write inverted guards. Suppose you let someone through only when they're logged in *and* verified: ```text if (loggedIn && verified) { allow() } ``` Now you want the "block them" branch. De Morgan tells you exactly how to write it: ```text if (!loggedIn || !verified) { block() } ``` NOT, applied to `loggedIn && verified`, becomes `!loggedIn || !verified` - the AND became an OR. Anyone missing *either* requirement gets blocked, which is what you want. The same rule rescues you when you flip a loop guard: `while (hasNext && !error)` stops when `!hasNext || error`. The biconditional shows up in validation: "the form is valid *if and only if* all required fields are filled" means filling all fields is *necessary* (without them, invalid) *and* sufficient (with them, valid) - both directions. [Implication & Conditionals](/guides/implication-and-conditionals) explores necessary and sufficient in depth. Two practical habits: - **When you invert a condition, apply De Morgan - don't eyeball it.** Negate each part and flip every `&&` to `||` and every `||` to `&&`. Mishandling this is a frequent source of "the check passes when it shouldn't" bugs. - **Use it to simplify.** `!(x > 0 && x < 10)` is often clearer rewritten as `x <= 0 || x >= 10` (note the comparisons flipped too - the negation of `>` is `<=`, and of `<` is `>=`). ## Logic you already use: regular expressions If you've written a regex, you've written propositional logic. `a && b` is `a.*b` (both, in order); `a || b` is `a|b` (either); `!a` is `[^a]` or `(?!a)`. De Morgan works there too: the opposite of "must contain a digit *and* a letter" is "missing a digit *or* missing a letter." Regex adds repetition (`*`, `+`, `?`) and capture, but the core - what counts as a match - is propositional logic in different clothes. ## A bridge to computer science: Boolean satisfiability One question propositional logic asks turns out to be deeply important in computer science: **"Is there any assignment of true/false that makes this whole expression true?"** That's **Boolean satisfiability**, or SAT - the engine behind constraint solvers (package managers, build systems), type checkers, model checkers, and SMT solvers, because many real problems can be *translated* into a boolean expression and then asked "does any solution exist?" The P vs NP question, one of the biggest open problems in math, is fundamentally about how hard that question is to answer for large expressions. You don't need to solve SAT instances today - but knowing "can this be true?" is a *named, studied problem* changes how you see the boolean expressions in your own code. ## Recap, and where this guide lands - **Logical equivalence** means two statements share an identical truth table, which makes them interchangeable. - **De Morgan's laws** let you correctly negate AND/OR: `¬(A ∧ B) ≡ ¬A ∨ ¬B` and `¬(A ∨ B) ≡ ¬A ∧ ¬B`. - **Pushing a NOT inward flips the connective** - AND becomes OR, OR becomes AND - and that flip is the part everyone forgets. Across this guide you went from "what is a proposition" to building truth tables to transforming statements while preserving their meaning - the whole core of propositional logic, and the machinery underneath every conditional you'll ever write. There's one connective we've been circling but never opened up: implication - "if A, then B." It surprises almost everyone the first time (an implication can be true even when its "if" part never happens), and it's the backbone of reasoning, proofs, and the conditionals in your code. That's the natural next step. A quick check before you go: ```quiz [ { "q": "Two statements are logically equivalent when:", "choices": [ "They use the same connectives", "They have identical truth tables - the same result in every row", "They are both true right now", "They contain the same variables" ], "answer": 1, "explain": "Equivalence is about agreeing in every possible situation, which is exactly what an identical truth table captures. Same words or same current truth value isn't enough." }, { "q": "By De Morgan's law, ¬(A ∧ B) is equivalent to:", "choices": [ "¬A ∧ ¬B", "A ∨ B", "¬A ∨ ¬B", "¬A ∧ B" ], "answer": 2, "explain": "Negate each part and flip the connective: the AND becomes an OR, giving ¬A ∨ ¬B. 'Not both' means 'at least one is missing.'" }, { "q": "What is the correct negation of the condition a && b?", "choices": [ "!a && !b", "!a || !b", "a || b", "!(a || b)" ], "answer": 1, "explain": "The opposite of 'both true' is 'not both true' - at least one is false - which is !a || !b. Keeping the AND (!a && !b) is the classic bug; that says 'both false.'" } ] ``` Watch it animated: [De Morgan's laws](/explainers/DeMorgansLaws.dc.html)