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 $\land ,\lor$, and $\lnot$,
• 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\land G)$ and $(F\lor G)$ are formulae.
• If $F$ is a formula, then $\lnot 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 $(\lnot F_{1}\lor F_{2})$

$(F_{1}\leftrightarrow F_{2})$ instead of $((F_{1}\land F_{2})\lor (\lnot F_{1}\land \lnot F_{2}))$

$\bigvee _{i=1}^{n}~F_{i}$ instead of $(\cdots ((F_{1}\lor F_{2})\lor F_{3})\lor \cdots \lor F_{n})$

$\bigwedge _{i=1}^{n}~F_{i}$ instead of $(\cdots ((F_{1}\land F_{2})\land F_{3})\land \cdots \land 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

$\lnot (ab(or1))\to high(or1,o)\leftrightarrow (high(or1,i1)\lor high(or1,i2))$

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

$(\lnot (ab(or1))\to (high(or1,o)\leftrightarrow (high(or1,i1)\lor 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:
$(\lnot \lnot (ab(or1))\lor$

$(high(or1,o)\land ((high(or1,i1)\lor high(or1,i2))\lor$

$(\lnot high(or1,o)\lor \lnot (high(or1,i1)\lor high(or1,i2))))))$