Logic for Computer Scientists/Propositional Logic/Syntax

Syntax edit

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) edit

Assume a

  • countable set of atomic formulae  , where  ,
  • the junctors  , and  ,
  • the punctuation symbols   and  .

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

  • Atomic formulae are formula.
  • If   and   are formulae, then   and   are formulae.
  • If   is a formula, then   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) edit

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:

  instead of  

  instead of  

  instead of  

  instead of  

  instead of  

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

 

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

 

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: