Logic for Computer Scientists/Propositional Logic/Syntax

< Logic for Computer Scientists‎ | Propositional Logic


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

 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^n_{i=1} ~F_i   instead of  (\cdots ((F_1 \lor F_2) \lor F_3)   \lor \cdots \lor F_n)

  \bigwedge^n_{i=1} ~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)) ) )))