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

From ProofWiki
Jump to navigation Jump to search

Definition

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 $\LL_0$.


  • Let $\PP_0$ be the vocabulary of $\LL_0$.
  • Let $Op = \set {\land, \lor, \implies, \iff}$.


The rules are:

$\mathbf W: TF$ $:$ $\top$ is a WFF, and $\bot$ is a WFF.
$\mathbf W: \PP_0$ $:$ If $p \in \PP_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 $\paren {\mathbf A \circ \mathbf B}$ is a WFF.


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


Sources