Propositional Logic: Propositions, Connectives, Truth Tables

Propositions

Two conditions: it must state something (declarative), and it must have a definite truth value, true (T, 1) or false (F, 0). We name propositions with lowercase letters $p, q, r, s, \dots$

Negation

Negate the whole statement, not a word in it. The negation of “the queue is empty” is “the queue is not empty”, and the negation of $3 > 5$ is $3 \le 5$ (not $3 < 5$).

Connectives

Connectives build compound propositions from simpler ones. Here are all of them in one table: memorize it, you will use it every week.

Truth tables

A truth table lists every combination of truth values of the variables and the resulting value of the formula. With $n$ variables there are $2^n$ rows, because each variable doubles the number of cases.

Build it column by column, from the inside out. For $(p \lor \neg q) \to (p \land q)$:

Now let the computer do it. Type any formula, including the one above as (p | ~q) -> (p & q):

The conditional, carefully

$p \to q$ is the connective students get wrong most often, and it is the one programmers rely on most. $p$ is the hypothesis (antecedent), $q$ the conclusion (consequent).

Think of it as a promise. “If you enter valid credentials, then you will be logged in.”

The promise only says something when the hypothesis holds. When $p$ is false, $p \to q$ is vacuously true. That is why $p \to q$ has the same truth table as $\neg p \lor q$, and why Python code often writes implications as not p or q.

Many ways to say $p \to q$

Converse, inverse, contrapositive

From $p \to q$ we can build three related conditionals:

“If today is Saturday, then tomorrow is Sunday.” Converse: “If tomorrow is Sunday, today is Saturday”, which happens to be true here, but only because of how the calendar works, not because of logic. Inverse: “If today is not Saturday, tomorrow is not Sunday.” Contrapositive: “If tomorrow is not Sunday, today is not Saturday”, which is always as true as the original. Check all of them in the playground: type (p -> q) <-> (~q -> ~p) and then (p -> q) <-> (q -> p).

The biconditional

$p \leftrightarrow q$ (“$p$ if and only if $q$”, often written “iff”) is true when $p$ and $q$ have the same truth value. It means $(p \to q) \land (q \to p)$: $p$ is both necessary and sufficient for $q$. Notice that $p \leftrightarrow q$ is exactly $\neg(p \oplus q)$. In code, it is p == q on booleans. We will go deeper next week.

Translating English into logic

1. Find the atomic propositions and name them.
2. Find the connectives, paying special attention to “only if”, “unless”, “but” (which means $\land$) and “neither … nor” ($\neg p \land \neg q$).
3. Add parentheses to match the intended meaning.

Logic on bits

Computers store truth values as bits, 1 and 0, and apply connectives to whole bit strings position by position. Python does this with integers:

a = 0b0110_1100
b = 0b1010_1010
print(f"{a & b:08b}")   # AND  → 00101000
print(f"{a | b:08b}")   # OR   → 11101110
print(f"{a ^ b:08b}")   # XOR  → 11000110

This is how file permissions (chmod 755), network masks and feature flags work. You will use it in the lab.

Summary

• A proposition is a declarative sentence with exactly one truth value.
• Six operators: $\neg, \land, \lor, \oplus, \to, \leftrightarrow$. Know their tables cold.
• $n$ variables → $2^n$ rows.
• $p \to q$ is false only when $p$ is true and $q$ is false; it equals $\neg p \lor q$.
• $p \to q \equiv \neg q \to \neg p$ (contrapositive). The converse is not equivalent.
• “$p$ only if $q$” is $p \to q$; necessary conditions are conclusions, sufficient conditions are hypotheses.

Tags:propositiontruth tablenegationconjunctiondisjunctionXORimplicationconditionalbiconditionalcontrapositiveconverse