A propositional variable is a symbol (typically $p$, $q$, $r$, etc.) that represents a proposition. Each propositional variable can take exactly one of two truth values: true (denoted $T$ or $1$) or false (denoted $F$ or $0$).

The set of propositional formulas (or well-formed formulas) is defined recursively:

1. Every propositional variable is a formula
2. If $\phi$ is a formula, then $\neg \phi$ (negation) is a formula
3. If $\phi$ and $\psi$ are formulas, then $(\phi \land \psi)$ (conjunction), $(\phi \lor \psi)$ (disjunction), $(\phi \to \psi)$ (implication), and $(\phi \leftrightarrow \psi)$ (biconditional) are formulas
4. Nothing else is a formula

We often omit parentheses when the precedence is clear: $\neg$ binds strongest, then $\land$, $\lor$, $\to$, and $\leftrightarrow$.

The five fundamental logical connectives are defined by their truth tables:

• Negation $\neg p$: true when $p$ is false
• Conjunction $p \land q$: true when both $p$ and $q$ are true
• Disjunction $p \lor q$: true when at least one of $p$ or $q$ is true
• Implication $p \to q$: false only when $p$ is true and $q$ is false
• Biconditional $p \leftrightarrow q$: true when $p$ and $q$ have the same truth value

A truth assignment (or valuation) is a function $v$ that assigns a truth value to each propositional variable. Every truth assignment extends uniquely to all formulas by applying the truth tables of the connectives.