Logic for Computer Scientists/Propositional Logic/Syntax

Syntax

For the definition of the syntax we have to assume a set of atomic formulae, which we take as the start of an inductive definition. With the help of three junctors and brackets as punctuation symbols we inductively define more complex formulae.

Definition 1 (Syntax of propositional Logic)

Assume a

• countable set of atomic formulae $P_i$, where $i=1,2,3,\cdots$,
• the junctors $\wedge ,\vee$, and $\mathrm{\neg }$,
• the punctuation symbols $($ and $)$.

The set of propositional formulae is defined by the following induction:

• Atomic formulae are formula.
• If $F$ and $G$ are formulae, then $(F\wedge G)$ and $(F\vee G)$ are formulae.
• If $F$ is a formula, then $\mathrm{\neg }F$ is a formula

The different kinds of formulae are called conjunction, disjunction and negation. Note, that this is just a convention about wording, until now, we did not give any semantics to these junctors, which would justify these denotations.

This definition of the set of formulae also introduces a partial order in a very natural way, if we consider the concept of a subformula.

Definition 2 (Subformula)

A subformula of a formula is a substring, which is a formula.

Note that the relation "is subformula" is indeed a partial order.

The set of formulae together with the subformula-relation is a well-founded relation.

In order to facilitate notations We introduce the following abbreviations:

$A,B,C$ instead of $P_1,P_2,P_3$

$(F_1\to F_2)$ instead of $(\mathrm{\neg }{F}_1\vee F_2)$

$(F_1\leftrightarrow F_2)$ instead of $((F_1\wedge F_2)\vee (\mathrm{\neg }{F}_1\wedge \mathrm{\neg }{F}_2))$

$\underset{i=1}{\overset{n}{\bigvee }}{F}_i$ instead of $(\cdots ((F_1\vee F_2)\vee F_3)\vee \cdots \vee F_n)$

$\underset{i=1}{\overset{n}{\bigwedge }}{F}_i$ instead of $(\cdots ((F_1\wedge F_2)\wedge F_3)\wedge \cdots \wedge F_n)$

These notations (except the first one) are simple abbreviations; whenever those arrow-symbols or indexed junctors occur in a formulae, the corresponding subformula can be substituted according to this definition.

Coming back to our previous example you can see that

$\mathrm{\neg }(ab(or1))\to high(or1,o)\leftrightarrow (high(or1,i1)\vee high(or1,i2))$

can be written as a formula according to the above definition by introducing parenthesis:

$(\mathrm{\neg }(ab(or1))\to (high(or1,o)\leftrightarrow (high(or1,i1)\vee high(or1,i2))))$

The parenthesis are introduced in order to avoid any ambiguity. In order to increase readability, we will omit them whenever this is possible. If we additionally apply the above abbreviation rules we would result in the following formula:
$(\mathrm{\neg }\mathrm{\neg }(ab(or1))\vee$

$(high(or1,o)\wedge ((high(or1,i1)\vee high(or1,i2))\vee$

$(\mathrm{\neg }high(or1,o)\vee \mathrm{\neg }(high(or1,i1)\vee high(or1,i2))))))$