← mapLogic & Proof

Propositions & Connectives

⚗ Dr. Möbius, from the lab

You spent five lessons building numbers from nothing. Now we build something even more fundamental: the machinery of truth itself. Logic is the operating system everything else runs on, and I will not let you write a single damn proof until you can say, with a straight face and zero vibes, exactly what makes a sentence true. Strap in, you beautiful disaster.

THE BIG IDEA

A proposition is a sentence that is definitely true or definitely false, and the connectives AND, OR, NOT combine propositions in ways completely specified by their truth tables.

What counts as a proposition

A proposition is a declarative sentence that is either true or false — exactly one of the two, no third option, no "depends on your mood." That's the entire entry requirement, and most sentences flunk it.

" $7$ is prime." True. Proposition. " $2 + 2 = 5$ ." False. Still a proposition — being false is allowed, being undecided is not. "Is it raining?" Not a proposition; it's a question. "This sentence is a banger." Not a proposition; it's an opinion, and opinions don't have truth values, they have fans. " $x > 3$ ." Not yet a proposition — until I tell you what $x$ is, it's neither true nor false. We call that an open sentence or predicate, and we'll cage those beasts two lessons from now.

The Federation of Boring Textbook Authors loves to blur this line, and I find it personally offensive. A proposition has a definite truth value, full stop. We label propositions with letters — $P$ , $Q$ , $R$ — and the truth value is either $T$ (true) or $F$ (false).

The three connectives, defined by their behavior

Single propositions are boring. The action starts when you combine them. There are exactly three primitive connectives, and here's the beautiful part — each one is completely defined by its truth table. The table isn't a study aid; it is the definition. Nothing hidden, nothing left to interpretation.

Negation $\neg P$ ("not $P$ ") flips the truth value:

$P$	$\neg P$
T	F
F	T

Conjunction $P \land Q$ (" $P$ and $Q$ ") is true only when both are true:

$P$	$Q$	$P \land Q$
T	T	T
T	F	F
F	T	F
F	F	F

Disjunction $P \lor Q$ (" $P$ or $Q$ ") is true when at least one is true:

$P$	$Q$	$P \lor Q$
T	T	T
T	F	T
F	T	T
F	F	F

Memorize these by understanding them, not by chanting. AND is a demanding bastard — needs everything or it gives you nothing. OR is generous — it'll take anything, the easygoing slob.

Inclusive or: the one that trips up your meat-brain

Look at the very first row of the OR table. $P$ true, $Q$ true, and $P \lor Q$ is true. That offends your everyday instincts, because in a restaurant "soup or salad" means pick one, not both, you greedy animal. That's exclusive or.

Mathematical $\lor$ is inclusive: " $P$ or $Q$ " means " $P$ , or $Q$ , or both." When a mathematician says " $x > 0$ or $x < 5$ ," they are blissfully fine with $x = 3$ satisfying both — no waiter required. If we ever want the restaurant's pick-exactly-one version, we build it explicitly — and you'll do exactly that in the gauntlet. Burn this in: default or is inclusive. Confuse it once and I will know.

Building compound statements and computing their tables

Connectives stack. Feed outputs back in as inputs and you get arbitrarily complex statements — $\neg(P \land Q)$ , $(\neg P) \lor Q$ , $(P \lor Q) \land \neg R$ . To find the truth table of a compound statement, you list every possible combination of the inputs ( $2^n$ rows for $n$ variables) and evaluate from the inside out, exactly like nested functions.

Let's compute $\neg P \lor Q$ step by step:

$P$	$Q$	$\neg P$	$\neg P \lor Q$
T	T	F	T
T	F	F	F
F	T	T	T
F	F	T	T

You build the helper column $\neg P$ first, then OR it against $Q$ . Mechanical. No fucking genius required — that's the point of logic. It turns reasoning into bookkeeping. This is the beaker, not the inspiration.

Play with one. Toggle the rows, change the expressions, and watch the columns light up — get a feel for how a compound statement's table is just its parts, stacked:

truth table — tap a row to spotlight it

P	Q	¬P ∨ Q	P ∧ ¬Q
T	T	T	F
T	F	F	T
F	T	T	F
F	F	T	F

Logical equivalence and the first De Morgan sighting

Here's where it gets gorgeous. Two compound statements are logically equivalent (written $\equiv$ ) when they have identical truth tables — same output in every row. They're the same statement wearing different costumes. Remember the master refrain from the very first lesson: the squiggle is not the thing. Two different squiggles can name the same logical thing. This is not a philosophy seminar; it's a lab, and the table is the damn proof.

Watch this. Compute $\neg(P \land Q)$ and $\neg P \lor \neg Q$ :

$P$	$Q$	$P \land Q$	$\neg(P \land Q)$	$\neg P$	$\neg Q$	$\neg P \lor \neg Q$
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

Columns four and seven are identical. So

$\neg(P \land Q) \equiv \neg P \lor \neg Q.$

That's De Morgan's law, and its twin (proved the same way) is $\neg(P \lor Q) \equiv \neg P \land \neg Q$ . In words: the negation of an AND is the OR of the negations, and vice versa. Negation pushes through a connective and flips it. "It's not the case that the soup AND the salad are good" means "the soup is bad OR the salad is bad." You already knew this in your bones; now you can prove it.

File De Morgan away somewhere safe — tattooed on your reactor wall if necessary. It comes back to negate quantifiers, it comes back to flip set operations into each other, and it never, goddamn ever stops being useful. Now go do the gauntlet, you magnificent idiot.

🔬 SPECIMENS (worked examples)

Worked example 1 — proposition or garbage?▸

For each sentence, decide whether it's a proposition, and if so give its truth value: (a) " $11$ is even." (b) "Close the lab door." (c) " $n$ is a multiple of $3$ ."

A proposition needs a definite truth value.

(a) " $11$ is even." This is a declarative sentence with a determinate answer: $11$ is odd, so the sentence is false. It IS a proposition (a false one — perfectly legal).

(b) "Close the lab door." This is a command, not a declaration. It can't be true or false. Not a proposition.

(c) " $n$ is a multiple of $3$ ." Until someone fixes $n$ , this is neither true nor false — it's true for $n = 6$ and false for $n = 7$ . Not a proposition; it's an open sentence (a predicate). Pin down $n$ and it becomes one.

Worked example 2 — building a compound table▸

Compute the full truth table of $(P \lor Q) \land \neg P$ .

Two variables, so $2^2 = 4$ rows. Build helper columns inside-out: first $P \lor Q$ , then $\neg P$ , then AND them.

$P$	$Q$	$P \lor Q$	$\neg P$	$(P \lor Q) \land \neg P$
T	T	T	F	F
T	F	T	F	F
F	T	T	T	T
F	F	F	T	F

Read it off: the whole thing is true in exactly one row — when $P$ is false and $Q$ is true. That makes sense: you need the OR satisfied (so something's true) and $P$ false, which forces $Q$ to carry the OR alone. This compound is secretly equivalent to " $\neg P \land Q$ " — check the tables and see.

Worked example 3 — the trap: no vibes, just the table▸

Is $\neg(P \lor Q)$ logically equivalent to $\neg P \land \neg Q$ ? Prove your answer with a truth table.

This is the other De Morgan law, and the only honest way to settle it is to compute both tables and compare every row.

$P$	$Q$	$P \lor Q$	$\neg(P \lor Q)$	$\neg P$	$\neg Q$	$\neg P \land \neg Q$
T	T	T	F	F	F	F
T	F	T	F	F	T	F
F	T	T	F	T	F	F
F	F	F	T	T	T	T

Compare column four, $\neg(P \lor Q)$ , with column seven, $\neg P \land \neg Q$ : identical in all four rows. So yes,

$\neg(P \lor Q) \equiv \neg P \land \neg Q.$

The trap people fall into is "proving" it with a sentence and a vibe. No. Equivalence is a claim about every row, so you check every row. The negation of " $P$ or $Q$ " is "neither $P$ nor $Q$ " — which is exactly "not $P$ and not $Q$ ."

☠ KNOWN HAZARDS

Reading $\lor$ as exclusive. Mathematical "or" includes the both-true case. If you secretly mean exclusive-or, you must say so and build it; the default never excludes.
Treating opinions or questions as propositions. "Is $7$ prime?" and "math is beautiful" have no truth value. Only definitely-true-or-false declaratives qualify.
Botching De Morgan by forgetting to flip the connective. $\neg(P \land Q)$ is not $\neg P \land \neg Q$ . Negation pushes in AND flips $\land \leftrightarrow \lor$ . Drop the flip and your table won't match — and you'll have proven something false, which is worse than proving nothing.
Thinking $\neg P$ is "the opposite extreme." The negation of " $x > 5$ " is " $x \le 5$ ", not " $x < 5$ ". $\neg$ is the exact complement, nothing more, nothing less.

TL;DR

▸
A proposition is a sentence with a definite truth value — true or false, no questions, no opinions, no undecided $x$ 's.
▸
The three connectives are defined entirely by their truth tables: $\neg$ flips, $\land$ needs both true, $\lor$ needs at least one true.
▸
Mathematical "or" ( $\lor$ ) is inclusive — true even when both parts are true, unlike restaurant "soup or salad".
▸
To find a compound statement's table, list all $2^n$ input rows and evaluate inside-out with helper columns.
▸
Two statements are logically equivalent ( $\equiv$ ) when their tables match in every row; first example: De Morgan's laws, $\neg(P \land Q) \equiv \neg P \lor \neg Q$ .

unlocks

Implication →