Propositions and connectives

A concert venue has a door rule: “You can come in if you have a ticket and you’re on the guest list, or you’re with the band.” The bouncer applies it hundreds of times a night, and has to get every case right.

English is slippery. When a waiter says “soup or salad”, they mean one, not both. When a sign says “cash or card accepted”, paying with both is fine. Logic removes the guesswork: every word has one exact meaning, so a rule means the same thing to the bouncer, the manager and the computer that checks tickets.

You’ve already met these ideas as logic gates (F01) and if conditions (F02). Now you’ll see them as a language for thinking precisely, which is the foundation of every proof in this course.

The real words

• A proposition is a statement with a definite truth value: “Paris is in France” (true), "$2 + 2 = 5$" (false). "$x > 3$" isn’t one yet, because it depends on $x$ (that’s a predicate, lesson 6).
• The and, or, not ($\land, \lor, \lnot$) connectives:
  • $p \land q$ (”$p$ and $q$”): true only when both are true.
  • $p \lor q$ (”$p$ or $q$”): true when at least one is true. This is inclusive or.
  • $\lnot p$ (“not $p$”): the opposite of $p$.
  • $p \oplus q$ (”$p$ xor $q$”, exclusive or): true when exactly one is true.
• A truth table lists all combinations. Each new variable doubles the rows: 2 variables give 4 rows, 3 give 8, 10 give 1,024. (The same $2^n$ as light switches in F01!)
• Order of operations: not first, then and, then or. So p or q and r means p or (q and r). When in doubt, add parentheses. Python uses the same order for not, and and or.