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.
Author: Wolfgang Schreiner
Last Modification: October 4, 1999
