---
title: Formal Languages and Well-Formed Formulas
module: Sentential Logic
moduleNumber: 2
lessonNumber: 1
order: 201
summary: >
  The language of sentential logic has an alphabet of sentence symbols, five
  connectives, and two parentheses, with formation rules that pick out the
  well-formed formulas. The wffs are the least set of expressions closed under
  the five formula-building operations, and every such generated set carries an
  induction principle.
topics: [Sentential Logic]
sources:
  - book: Enderton
    ref: "Ch. 1 — Sentential Logic; §1.0 Informal Remarks on Formal Languages, §1.1 The Language of Sentential Logic"
draft: false
---

To study deduction mathematically, one builds a formal language precise enough
that "follows logically" becomes a statement about strings of symbols rather than
about meaning. Sentential logic is the first and simplest such language. It fixes
a handful of connectives — _not_, _and_, _or_, _if–then_, _if-and-only-if_ — and
asks what can be said and deduced using only those, with the internal structure
of the sentences they join left opaque.

A natural language such as English carries meaning but tolerates ambiguity. A
formal language reverses the priorities: it is defined by exact formation rules,
and meaning is assigned only afterward, as a separate act. To describe a formal
language, Enderton gives three pieces of information.[^enderton-formal]

- **The alphabet.** The set of symbols out of which everything is built.
- **The formation rules.** Which finite strings of symbols count as
  grammatically correct. These strings are the **well-formed formulas**, or
  **wffs**.
- **The intended translations.** How wffs correspond to English sentences. Only
  this third part assigns any meaning; the first two are pure syntax.

A person who knew only the alphabet and the formation rules could carry out much
of what follows in complete ignorance of meaning, shuffling symbols by rule.
Syntax and semantics stay separate. Meaning enters with
[truth assignments](/logic/sentential-logic/truth-assignments-and-tautologies);
the syntax comes first.

## The alphabet

Fix an infinite sequence of distinct objects called **symbols**. We give them
names but stay neutral about what they are: sets, numbers, or marbles would all
serve. The one structural demand is that no symbol is a finite sequence of other
symbols, so that a string of symbols decomposes in exactly one way into its
constituent symbols.[^enderton-symbols]

The symbols fall into two groups.

| Group | Symbols | Role |
| --- | --- | --- |
| Logical | $($ , $)$ , $\neg$ , $\wedge$ , $\vee$ , $\to$ , $\leftrightarrow$ | fixed meaning, never reinterpreted |
| Parameters | $A_1, A_2, A_3, \dots$ | open to interpretation |

The two parentheses are punctuation. The five **sentential connective symbols**
have fixed intended readings.

| Symbol | Name | Reading |
| --- | --- | --- |
| $\neg$ | negation | "not …" |
| $\wedge$ | conjunction | "… and …" |
| $\vee$ | disjunction | "… or …" (inclusive) |
| $\to$ | conditional | "if …, then …" |
| $\leftrightarrow$ | biconditional | "… if and only if …" |

The connectives together with the parentheses are the **logical symbols**: their
translation to and from English never changes. The **sentence symbols**
$A_1, A_2, \dots$ are the **parameters**, or **nonlogical symbols**. Their
translation is not fixed. In one context $A_5$ might stand for "the evidence is
admissible"; in another, for "wishes are horses." Some authors call $A_n$ the
$n$th proposition symbol and speak of _propositional_ logic; the reading is the
same.

There are infinitely many sentence symbols. A more frugal alphabet would use a
single symbol $A$ and a prime, writing $A, A', A'', \dots$ for the sequence, which
brings the total number of distinct symbols down to nine. A less frugal choice
would allow an arbitrary set of sentence symbols, countable or not. Most of this
chapter survives either change; the exception is
[compactness](/logic/sentential-logic/compactness-and-effectiveness), where
countability of the symbol set is used.

$$
% caption: The alphabet splits into logical symbols (fixed meaning) and
% parameters (open to interpretation); the parameters are the only symbols a
% translation is free to reinterpret.
\begin{tikzpicture}[font=\footnotesize,
  grp/.style={draw, minimum width=34mm, minimum height=11mm, align=center},
  lab/.style={font=\footnotesize\itshape}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[grp] (par) at (0,1.4) {parentheses\\( \quad )};
  \node[grp] (con) at (0,0)   {connectives\\(5 symbols)};
  \node[grp, draw=acc, text=acc] (sen) at (6.2,0.7) {sentence symbols\\A, B, C, ...};
  % brackets grouping
  \draw[black] (2.1,-0.7) -- (2.6,-0.7) -- (2.6,2.1) -- (2.1,2.1);
  \node[lab, anchor=west] at (2.7,0.7) {logical symbols};
  \draw[black] (8.3,0.1) -- (8.8,0.1) -- (8.8,1.3) -- (8.3,1.3);
  \node[lab, anchor=west, text=acc] at (8.9,0.7) {parameters};
\end{tikzpicture}
$$

An **expression** is any finite sequence of symbols. We name an expression by
concatenating the names of its symbols: $(\neg A_1)$ names the four-symbol
sequence $(,\ \neg,\ A_1,\ )$. If $\alpha$ and $\beta$ are expressions, $\alpha\beta$
is their concatenation. So if $\alpha = (\neg A_1)$ and $\beta = A_2$, then
$(\alpha \to \beta)$ is the expression $((\neg A_1) \to A_2)$.

### Translating English

Let $A, B, \dots, Z$ abbreviate the first twenty-six sentence symbols. Then
compound English sentences translate by rendering "not" as $\neg$, "and" as
$\wedge$, "or" (inclusive) as $\vee$, "if–then" as $\to$, and "if and only if"
as $\leftrightarrow$.

- "The evidence is inadmissible" $\rightsquigarrow (\neg E)$.
- "The evidence is admissible, and the suspect need not be released"
  $\rightsquigarrow (E \wedge (\neg R))$.
- "Either the evidence is admissible or the suspect must be released, but not
  both" $\rightsquigarrow ((E \vee R) \wedge (\neg (E \wedge R)))$.

We always read $\vee$ inclusively, as "and/or." A caution: an English sentence
and its translation are different objects. "Roses are red" is presumably true or
false; the expression $R$ is just a string of symbols, true or false only once
interpreted, and interpretable differently in different contexts.

Some expressions translate no English sentence and are mere nonsense, such as
$(( \to A_3$. The formation rules exist to exclude exactly these.

## Well-formed formulas

We want the well-formed formulas to be the grammatical expressions. The
definition should have three consequences: every sentence symbol is a wff;
applying a connective to wffs yields a wff; and nothing is a wff except by force
of those two clauses. The third clause — the demand that wffs be _only_ what the
first two compel — is what needs care.

The five connectives correspond to five **formula-building operations** on
expressions:

$$
\begin{aligned}
\mathcal{E}_{\neg}(\alpha) &= (\neg\,\alpha), &
\mathcal{E}_{\wedge}(\alpha,\beta) &= (\alpha \wedge \beta), &
\mathcal{E}_{\vee}(\alpha,\beta) &= (\alpha \vee \beta), \\
\mathcal{E}_{\to}(\alpha,\beta) &= (\alpha \to \beta), &
\mathcal{E}_{\leftrightarrow}(\alpha,\beta) &= (\alpha \leftrightarrow \beta). &
\end{aligned}
$$

Each takes one or two expressions and returns a longer expression: it wraps its
inputs in parentheses and inserts a connective. Note that every operation inserts
exactly one matched pair of parentheses.

> **Definition (Well-formed formula).** An expression is a **well-formed
> formula** (wff) iff it can be built from sentence symbols by applying the five
> formula-building operations a finite number of times.

For example,
$((A_1 \wedge A_{10}) \to ((\neg A_3) \vee (A_8 \leftrightarrow A_3)))$ is a wff,
built from four sentence symbols by five applications of the operations. At the
other extreme, a lone sentence symbol $A_3$ is a wff, built by zero applications.
The empty sequence is not a wff; a wff has at least one symbol.

### Formation trees

The construction of a wff is displayed by its **formation tree** (Enderton's
"ancestral tree"): the wff sits at the root, each internal node is an application
of one operation, and the leaves are sentence symbols. Reading the tree from the
leaves up reconstructs the wff one operation at a time.

$$
% caption: Formation tree of the wff whose outermost operation is the
% conditional joining (A and B) to ((not C) or D); leaves are sentence symbols,
% internal nodes are the operations that built the formula.
\begin{tikzpicture}[font=\footnotesize, level distance=13mm,
  op/.style={draw, circle, minimum size=8mm, inner sep=0pt, font=\footnotesize},
  lf/.style={draw, minimum size=7mm, inner sep=1pt, font=\footnotesize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[op, draw=acc, text=acc] (r) at (0,0) {implies};
  \node[op] (and) at (-3,-1.5) {and};
  \node[op] (or)  at (3,-1.5)  {or};
  \node[lf] (A) at (-4,-3) {A};
  \node[lf] (B) at (-2,-3) {B};
  \node[op] (not) at (2,-3) {not};
  \node[lf] (D) at (4,-3) {D};
  \node[lf] (C) at (2,-4.4) {C};
  \draw[black] (r) -- (and);
  \draw[black] (r) -- (or);
  \draw[black] (and) -- (A);
  \draw[black] (and) -- (B);
  \draw[black] (or) -- (not);
  \draw[black] (or) -- (D);
  \draw[black] (not) -- (C);
\end{tikzpicture}
$$

An equivalent linear record of the same construction is a **construction
sequence**: a finite sequence $\varepsilon_1, \dots, \varepsilon_n$ of expressions
in which each $\varepsilon_i$ is either a sentence symbol or the result of
applying an operation to earlier entries. An expression $\alpha$ is a wff if and
only if some construction sequence ends with $\alpha$. A construction
sequence is a formation tree flattened into a list.

> **Worked example.** Give a construction sequence for
> $((A_1 \wedge A_{10}) \to ((\neg A_3) \vee (A_8 \leftrightarrow A_3)))$.
>
> Build the subformulas innermost first, each entry a sentence symbol or an
> operation applied to earlier entries:
>
> $$
> \begin{aligned}
> \varepsilon_1 &= A_1, \qquad \varepsilon_2 = A_{10}, \qquad \varepsilon_3 = (A_1 \wedge A_{10}),\\
> \varepsilon_4 &= A_3, \qquad \varepsilon_5 = (\neg A_3), \qquad \varepsilon_6 = A_8,\\
> \varepsilon_7 &= (A_8 \leftrightarrow A_3), \qquad \varepsilon_8 = ((\neg A_3) \vee (A_8 \leftrightarrow A_3)),\\
> \varepsilon_9 &= ((A_1 \wedge A_{10}) \to ((\neg A_3) \vee (A_8 \leftrightarrow A_3))).
> \end{aligned}
> $$
>
> Each compound entry names the operation that produced it:
> $\varepsilon_3 = \mathcal{E}_\wedge(\varepsilon_1, \varepsilon_2)$,
> $\varepsilon_5 = \mathcal{E}_\neg(\varepsilon_4)$,
> $\varepsilon_7 = \mathcal{E}_\leftrightarrow(\varepsilon_6, \varepsilon_4)$,
> $\varepsilon_8 = \mathcal{E}_\vee(\varepsilon_5, \varepsilon_7)$, and
> $\varepsilon_9 = \mathcal{E}_\to(\varepsilon_3, \varepsilon_8)$. Nine entries
> suffice, one per node of the formation tree. Any order in which each entry's
> constituents come earlier works, so the sequence is not unique, but its length
> is.

## The set of wffs as a least closed set

The definition says a wff is anything built "by applying the operations a finite
number of times." That phrase is made precise by the notion of a **least closed
set**, the pattern developed in full in
[induction and recursion](/logic/sentential-logic/induction-and-recursion).

Call a set $S$ of expressions **closed** under the formula-building operations
iff whenever $\alpha, \beta \in S$, every $\mathcal{E}_\square(\alpha, \beta)$ (and
$\mathcal{E}_{\neg}(\alpha)$) is again in $S$. Many sets are closed — the set of
_all_ expressions, for one. The set of wffs is the **smallest** set that both
contains the sentence symbols and is closed. Equivalently, it is the intersection
of every such set: an expression is a wff iff it belongs to _every_ set that
contains the sentence symbols and is closed under the operations.

$$
% caption: The wffs accumulate in stages: sentence symbols, then everything one
% operation reaches, then two, and so on; the union of all stages is the least
% closed set containing the symbols.
\begin{tikzpicture}[font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[black, fill=acc!5] (0,0) ellipse (4.6 and 3.0);
  \draw[black, fill=acc!8] (0,-0.15) ellipse (3.4 and 2.2);
  \draw[black, fill=acc!12] (0,-0.3) ellipse (2.1 and 1.35);
  \node[draw=acc, text=acc, fill=white, inner sep=2pt] at (0,-0.3) {sentence symbols};
  \node[font=\footnotesize] at (0,1.5) {one operation};
  \node[font=\footnotesize] at (0,2.5) {two operations};
  \node[font=\footnotesize, anchor=west] at (2.8,2.55) {all formulas};
  \draw[->, black] (2.7,2.5) -- (2.0,2.15);
\end{tikzpicture}
$$

## The induction principle

Every least-closed-set construction comes with a proof technique. To show a
property holds of _all_ wffs, it suffices to show it holds of the sentence
symbols and is preserved by each operation.

> **Theorem (Induction principle for wffs).** Let $S$ be a set of wffs. If $S$ contains
> every sentence symbol and is closed under all five formula-building operations,
> then $S$ is the set of all wffs.

The reason is immediate from the least-closed-set definition: such an $S$ is a
closed set containing the symbols, so it includes the smallest one, which is the
set of all wffs.[^enderton-induction] The argument reads two ways.

- **Up the tree.** An arbitrary wff $\alpha$ has a formation tree. Every leaf is
  a sentence symbol, hence in $S$. Working upward, each node's expression is
  built from children already in $S$ by an operation $S$ is closed under, so it
  too lies in $S$. The root $\alpha$ therefore lies in $S$.
- **Along the sequence.** $\alpha$ ends some construction sequence
  $\varepsilon_1, \dots, \varepsilon_n$. By strong induction on $i$, each
  $\varepsilon_i \in S$: it is either a sentence symbol or built from earlier
  entries, all in $S$ by hypothesis. So $\alpha = \varepsilon_n \in S$.

### A worked application

The induction principle is the standard tool for proving expressions ill-formed,
by exhibiting a property that all wffs share and the target expression lacks.

> **Theorem.** Every wff has equally many left and right parentheses. Hence any
> expression with more left than right parentheses is not a wff.

> **Proof.** Let $S$ be the set of **balanced** wffs — those with equal numbers of
> left and right parentheses. Every sentence symbol is balanced (it has zero of
> each), so $S$ contains the symbols. Each operation adds one left and one right
> parenthesis, so it preserves balance: if $\alpha, \beta \in S$ then
> $\mathcal{E}_\square(\alpha, \beta) \in S$. By the induction principle $S$ is the
> set of all wffs, so every wff is balanced. An unbalanced expression is therefore
> not a wff. $\blacksquare$

This is the shape of every ill-formedness proof: find an invariant the operations
preserve, check the target expression violates it.

$$
% caption: A grammatical wff (left) against a malformed string (right); the
% malformed string opens with unmatched right parentheses, an invariant no wff
% can satisfy.
\begin{tikzpicture}[font=\footnotesize,
  wff/.style={draw, minimum width=42mm, minimum height=11mm, align=center, font=\footnotesize},
  bad/.style={draw, minimum width=42mm, minimum height=11mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[wff, draw=acc] (ok) at (0,0) {( A and B )};
  \node[font=\footnotesize\itshape, text=acc] at (0,1.0) {well-formed};
  \node[bad] (no) at (6.5,0) {) ) implies A};
  \node[font=\footnotesize\itshape] at (6.5,1.0) {malformed};
  \draw[->, black] (5.0,-1.3) -- (5.35,-0.4);
  \node[font=\scriptsize, anchor=north, align=center] at (5.0,-1.3) {no matching\\left parenthesis};
\end{tikzpicture}
$$

> **Worked example.** Show that $((\neg A_3) \vee A_1$ is not a wff.
>
> Count parentheses: the expression has two left and one right. Every wff has
> equal numbers of each, so an expression with unequal counts is not a wff. The
> same test rejects $(({\to}A_3$ (two left, zero right) and $A_1)$ (zero left,
> one right) without any parse attempt.

## Formulas build upward

A structural feature of these particular operations will matter repeatedly:
they build up and never down. The expression $\mathcal{E}_\square(\alpha, \beta)$
contains all of $\alpha$ and all of $\beta$ as consecutive segments, plus a
connective and two parentheses, so it is strictly longer than either. Every
constituent of a wff appears verbatim inside it.

One consequence: if a wff $\varphi$ does not contain the symbol $A_4$, then
$\varphi$ can be built without ever using $A_4$. The symbol cannot appear in an
intermediate stage only to vanish, because nothing is ever deleted. This "no
material is thrown away" property makes the parentheses recoverable, and it
underlies the [parsing
algorithm](/logic/sentential-logic/unique-readability-and-parsing) and the
[unique readability theorem](/logic/sentential-logic/unique-readability-and-parsing).

[^enderton-formal]: Enderton, §1.0 — the three-part description of a formal language (alphabet, formation rules, translation) and the deliberate deferral of meaning to the third part.
[^enderton-symbols]: Enderton, §1.1 — the symbol table, the split into logical symbols and parameters, and the assumption that no symbol is a finite sequence of other symbols (unique decomposability, Chapter 0, Lemma 0A).
[^enderton-induction]: Enderton, §1.1 — the induction principle for wffs, with the two proofs (up the formation tree and along the construction sequence) and the parenthesis-counting example.