Propositional Logic

Propositional logic studies statements that are either true or false, and how the truth of a compound statement depends on the truth of its parts. It gives a precise language for conditions ("if the cache misses and the bus is free, then fetch"), for specifications, and for correctness arguments.

In computer science it is the logic of Boolean expressions and digital circuits, the base of first-order logic, the setting of the satisfiability problem (SAT, the first problem shown NP-complete), and the language of program assertions. The working skills are deciding whether a formula is a tautology, whether two formulas are equivalent, and whether an argument is valid.

A proposition is a declarative sentence that is either true (T, 1) or false (F, 0), but not both. "7 is prime" is a proposition; "$x > 3$" is not, because its truth depends on $x$ (it becomes a proposition once $x$ is fixed, or once it is quantified; see first-order logic). "Close the door" is not a proposition.

Propositional variables $p, q, r, \ldots$ stand for propositions. Compound formulas are built with connectives:

A formula with $n$ distinct variables has a truth table of $2^n$ rows. There are $2^{2^n}$ distinct truth functions of $n$ variables (16 for $n = 2$), because each of the $2^n$ rows can independently be T or F.

Precedence convention. $\neg$ binds tightest, then $\land$, then $\lor$, then $\to$, then $\leftrightarrow$. Implication is right-associative: $p \to q \to r$ means $p \to (q \to r)$. When in doubt, add parentheses.

$p \to q$ is false in exactly one row: $p$ true, $q$ false. When $p$ is false, the implication is vacuously true. The implication does not claim any causal link between $p$ and $q$.

Ways to read $p \to q$: "if $p$ then $q$", "$p$ only if $q$", "$q$ if $p$", "$p$ is sufficient for $q$", "$q$ is necessary for $p$", "$q$ unless $\neg p$".

From $p \to q$ we form three related implications:

Note the difference between the connective $\to$ (part of a formula) and the relation $\Rightarrow$ (a statement about two formulas).

All of the following hold for any formulas $p, q, r$ and can be checked by truth tables.

Equivalences involving implication and the biconditional:

Two traps: $(p \to q) \to r \not\equiv p \to (q \to r)$ (implication is not associative); and $(p \to r) \lor (q \to r) \equiv (p \land q) \to r$, not $(p \lor q) \to r$.

Conversion recipe: (1) eliminate $\leftrightarrow$ and $\to$ using the equivalences above; (2) push negations inward with De Morgan and double negation; (3) distribute $\lor$ over $\land$ (for CNF) or $\land$ over $\lor$ (for DNF).

A set of connectives is functionally complete if every truth function can be expressed with it. $\{\neg, \land, \lor\}$ is complete (by the full DNF), and so are $\{\neg, \land\}$, $\{\neg, \lor\}$, $\{\neg, \to\}$, $\{\text{NAND}\}$ and $\{\text{NOR}\}$. The sets $\{\land, \lor\}$, $\{\land, \lor, \to, \leftrightarrow\}$ and $\{\leftrightarrow, \oplus\}$ are not complete: the first two cannot express $\neg p$, because every formula built only from them is true when all variables are true; the last can express only affine (xor-linear) functions: it can express $\neg p$ as $p \oplus (p \leftrightarrow p)$, but never $p \land q$. The details of NAND and NOR gates belong to Boolean Algebra.

An argument with premises $P_1, \ldots, P_k$ and conclusion $C$ is valid if every row that makes all premises true also makes $C$ true; equivalently,

Validity concerns form, not truth: a valid argument with a false premise can have a false conclusion. An argument is sound if it is valid and its premises are true.

Two classic fallacies (invalid forms):

Proof by contradiction (refutation). To show premises $\Gamma$ entail $C$, show that $\Gamma \cup \{\neg C\}$ is unsatisfiable. Resolution theorem provers and SAT solvers work this way.

Is $((p \to q) \land (q \to r)) \to (p \to r)$ a tautology?

An implication is false only when its antecedent is true and its consequent is false. So suppose $p \to r$ is false: then $p = T$ and $r = F$. For $q \to r$ to be true with $r = F$ we need $q = F$; then $p \to q$ is $T \to F = F$. The antecedent is false, so no falsifying row exists. The formula is a tautology (it is hypothetical syllogism).

This "try to falsify" method is much faster than an 8-row truth table.

Show $(p \to q) \land (p \to \neg q) \equiv \neg p$.

using the distributive law in reverse, the negation law and identity.

Premises: "If it rains, the match is cancelled" ($r \to c$); "If the match is cancelled, we go home" ($c \to h$); "We did not go home" ($\neg h$). Conclusion: "It did not rain" ($\neg r$).

From $c \to h$ and $\neg h$, modus tollens gives $\neg c$. From $r \to c$ and $\neg c$, modus tollens gives $\neg r$. Valid.

Now change the conclusion to "It rained" ($r$). The row $r = F, c = F, h = F$ makes all three premises true and the conclusion false, so this argument is invalid.

How many of the 8 assignments to $p, q, r$ satisfy $(p \lor q) \land (\neg p \lor r)$?

Total 4. (Note that the resolvent $q \lor r$ is true in all 4, as resolution guarantees.)

Convert $\neg(p \to (q \land r))$ to CNF.

This is already a conjunction of two clauses, so it is in CNF (and also in DNF after distributing: $(p \land \neg q) \lor (p \land \neg r)$).