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 formation of well-formed formulas (WFFs) of the language of propositional logic $\LL_0$.


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


The rules are:

$\mathbf W: \text {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: \text {Op}$ $:$ If $\mathbf A$ is a WFF and $\mathbf B$ is a WFF and $\circ \in \mathrm {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.


Examples

Example 1

The following is a WFF of propositional logic:

$\paren {\paren {p \land q} \implies \paren {\lnot \paren {q \lor r} } }$


Sources