Propositional calculus: symbols, connectives, well-formed formulas

A formal language for true/false claims

The propositional calculus is the simplest logic in the course: a formal language for stating and combining claims that are wholly true or wholly false. It has three kinds of symbol:

- Propositional symbols — P, Q, R, S, … each names *one* atomic claim, e.g. P = "it rained on Tuesday". - Truth symbols — the reserved constants true and false. - Logical connectives — ¬ (not), ∧ (and), ∨ (or), → (implies), ≡ (equivalent).

The defining limitation, the thing that later forces us into predicate calculus, is that a propositional symbol is *indivisible*: P is an opaque token. There is no way to look inside it and talk about *which day* it rained or to say something general about *all* rainy days. One symbol, one fixed claim.

Building well-formed formulas

A well-formed formula (WFF), also called a *legal sentence*, is any expression you can build by these rules:

1. Every propositional symbol and every truth symbol is a WFF.
2. If $s$ is a WFF, so is its negation $\neg s$.
3. If $s_1$ and $s_2$ are WFFs, so are $s_1 \wedge s_2$, $s_1 \vee s_2$, $s_1 \to s_2$, and $s_1 \equiv s_2$.

That is the *whole* grammar, and it is inductive — every legal sentence is a symbol, or a connective applied to smaller legal sentences. So ((P \wedge Q) \to \neg R) is a WFF, while P \wedge \to Q is not (the \to has no left operand).

Well-formedness is purely syntactic: it says the expression was *built correctly*, not that it is *true*. P \wedge \neg P is a perfectly legal WFF even though it can never be true. Keep that separation — *legal shape* now, *truth value* in the next lesson.

Worked example: parts of an implication

In the implication $P \to Q$:

- $P$ is the antecedent (also called the *premise*). - $Q$ is the consequent (also called the *conclusion*).

Take $P \to Q$ as raining → wet_ground. The antecedent is raining; the consequent is wet_ground. The crucial, exam-relevant fact about $\to$ is its truth definition: $P \to Q$ is false in exactly one case — when $P$ is true and $Q$ is false. In every other row it is true, *including* both rows where the antecedent $P$ is false (a false premise makes the whole implication vacuously true). We prove that with a truth table next lesson.

In $P \wedge Q$ the parts are the two conjuncts $P$ and $Q$; in $P \vee Q$ they are the two disjuncts. Those names matter the moment we apply inference rules: *And-Elimination* lets you pull either conjunct out of a true conjunction.