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.

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.

| | | | | created: 2015-06-07 09:39:47 | modified: 2020-05-04 18:49:39 | by: *bookofproofs* | references: [656], [711]

[656] **Hoffmann, Dirk W.**: “Grenzen der Mathematik – Eine Reise durch die Kerngebiete der mathematischen Logik”, Spektrum Akademischer Verlag, 2011

[711] **Mendelson Elliott**: “Theory and Problems of Boolean Algebra and Switching Circuits”, McGraw-Hill Book Company, 1982