   Go backward to 2.1 PreliminariesGo up to 2 The Language of LogicGo forward to 2.3 Predicate Logic ## 2.2 Propositional Logic

Propositional logic is that part of mathematical logic that deals with the composition of formulas. The composition starts with basic formulas that are considered as "black boxes": we are interested in their truth value ("true or false?") but not in what properties they actually describe. Various operations then allow to combine simpler formulas to more complex ones.

Definition 3 (Logical Connective) A (logical)  connective (Junktor) is a syntactic operator that combines formulas to a new formula.

In more detail, the formulas of propositional logic are constructed from the connectives `F', `T', `~', ` /\  ', ` \/ ', ` => ', ` <=> ' as follows:

Proposition 1 (Formulas of Propositional Logic)
• The following  logical constants (Logische Konstanten) are formulas2:
False
"false" ("falsch")
F
True
"true" ("wahr")
T
• If A is a formula, then the following is a formula:
Negation
"not A" ("nicht A")
~A
• If A and B are formulas, then the following are formulas
Conjunction
"A and B" ("A und B")
(A /\  B)
Disjunction
"A or B" ("A oder B")
(A \/ B)
Implication
"A implies B" ("A impliziert B")
(A => B)
Equivalence
"A is equivalent to B" ("A ist äquivalent zu B")
(A <=> B)
We omit the parentheses if A and B are unambiguous (usually x is free in A).

Above propositions provide the basis for a hierarchical construction of formulas.

Example  The syntactic structure of the formula
T /\  F => F
is ambiguous; it may be understood as (T /\  F) => F or as T /\  (F => F).

In the following sections, we will discuss the meanings of these formulas.

• 2.2.1 Logical Constants
• 2.2.2 Negations
• 2.2.3 Conjunctions
• 2.2.4 Disjunctions
• 2.2.5 Implications
• 2.2.6 Equivalences
• 2.2.7 Summary

• Author: Wolfgang Schreiner
Last Modification: October 4, 1999   