 Welcome guest
You're not logged in.
318 users online, thereof 0 logged in

## Definition: Syntax of PL0 - Propositions as Boolean Terms

The variables and functions defined in signature of propositional logic $PL0$ are called Boolean, named after the English mathematician George Boole.

First, we agree that the formal language $$L\subseteq \Sigma^*$$ of $PL0$ is defined over an alphabet $$\Sigma$$ containing the following letters:

• space character “ “,
• Boolean constants: the characters “$1$” and “$0$”,
• Boolean variables: small Latin letters $$“a”,“b”,“c”,\ldots,“x”,“y”,“z”$$, and letters indexed with natural numbers, e.g. $$“a_0”,“a_1”,“a_2”,\ldots,“b_0”,“b_1”,“b_2”,\ldots,$$,
• the parentheses “$($” and “$)$”, and
• the following additional letters “$$\neg$$”, “$$\wedge$$”, “$$\vee$$”, “$$\Rightarrow$$”, “$$\Leftrightarrow$$”.

We will now specify the syntax of $PL0$:

• A Boolean constant is a proposition (we also will use the notion Boolean term synonymously for “proposition”).
• Boolean variables are propositions.
• If “$\phi$” and “$\psi$” are propositions, then “$\neg \phi$,” “$\phi\wedge\psi$”, “$\phi\vee\psi$”, “$\phi\Rightarrow\psi$”, “$\phi\Leftrightarrow\psi$” are propositions.
• If “$\phi$” is a proposition, then the concatenation “$(\phi)$” is a proposition.

### Examples

This syntax enables us to construct propositions (Boolean terms):

• $x$,
• $(x)$,
• $\neg a$,
• $$(\neg(\neg y))$$,
• $$((x\Rightarrow(y\vee(1\wedge(\neg w))))\wedge 0)$$,
• $$((a\Leftrightarrow b)\vee(0\Rightarrow y))$$.

Please note that we did not yet define any meaning (semantics) of propositions. We will catch up on this now.