Definition:Language of Propositional Logic/Formal Grammar/Bottom-Up Specification

From ProofWiki
Jump to navigation Jump to search


Part of specifying the language of propositional logic is to provide its formal grammar.

The following rules of formation constitute a bottom-up grammar for the language of propositional logic $\mathcal L_0$.

  • Let $\mathcal P_0$ be the vocabulary of $\mathcal L_0$.
  • Let $Op = \left\{{\land, \lor, \implies, \iff}\right\}$.

The rules are:

$\mathbf W: TF$ $:$ $\top$ is a WFF, and $\bot$ is a WFF.
$\mathbf W: \mathcal P_0$ $:$ If $p \in \mathcal P_0$, then $p$ is a WFF.
$\mathbf W: \neg$ $:$ If $\mathbf A$ is a WFF, then $\neg \mathbf A$ is a WFF.
$\mathbf W: Op$ $:$ If $\mathbf A$ is a WFF and $\mathbf B$ is a WFF and $\circ \in Op$, then $\left({\mathbf A \circ \mathbf B}\right)$ is a WFF.

Any string which can not be created by means of the above rules is not a WFF.