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