Definition 3 (Semantics of propositional logic)Edit
For the semantics of our formal language of propositions we do not refer to a
specific intended interpretation. Moreover we only are interested in truth
values. We assume an initial assignment of truth values to atomic formulae and
based on this, we define the truth value of more complex formulae.
The set of truth values is the set .
An assignment for a set of atomic formulae is a function
Let be the set of formulae containing , i.e and
exactly those formulae which can be constructed from according
to the definition of the syntax. Then
the extension of on , , is given as:
In the following we will omit the index to indicate the
extension of an assignment .
Note that this is the right place to name formulae of type as conjunctions, formulae of type as disjunctions and formulae of
type as negations.
The following is an example evaluation by means of the definition of
Assume as given and , then
Let be an assignment and a formula. is called
assignment for , if is defined for every subformula of .
If is an assignment for and we call
a model for and we write
If is an assignment for and , we write .
A formula is called satisfiable, iff there is
a model for , otherwise is called unsatisfiable. is called valid (or a
tautology) iff every assignment for is a
model. We write rsp. .
Obviously the validity of a formula depends only of the assignments
for its atomic subformulae: If and are assignments for
and if they yield the same value for every occurring atomic
subformulae, then holds. As a consequence we can
state, that it suffices for a test of the validity of a formula
to check the infinitely many assignments of its atomic subformulae.
Such a check can be depicted easily in a tableau of the following
form, where is an arbritrary formula, containing distinct
atomic formulae .
When applying this procedure it might me helpful to introduce
intermediate results for subformulae, as done in the following
Note that we just have depicted an algorithm to check the validity of
a formula. Assume the Formula contains atomic subformulae, then
our just constructed tableaux contain lines. To estimate the
costs for such an exponential algorithm, assume that the computation
of one line takes 1 micro-second. Is contains only 100 atomic
subformulae the computation of the tableau would take
The problem whether a propositional formula is satisfiable is called
SAT and the corresponding tautology problem is called TAUT.
SAT is an NP-complete problem, and hence it is not known whether SAT
is tractable or not. Whether TAUT is in NP is still an open problem.
For TAUT we know, that it is in NP iff NP is closed under
complementation. SAT and TAUT, both, play a prominent role in the
study of complexity theory, in particular with respect to the question
"What is the secret of your long life?" a 100-year old man was asked. He answered: "I apply the following diet rules very strictly:
If I drink no wine at dinner then I have always fish. Whenever I take fish and wine for dinner, it is without garlic. If I have garlic or wine I avoid fish"
Formalize these rules with the help of propositional logic.
Try to simplify the advice of the 100-year old man.
If the colonel was not in the room during the murder then
he cannot know the weapon of the murderer. The butler
lies or he knows the murderer. If Lady Barntree is the
murderer then the colonel was in the room during the murder
or the butler lies. The butler knows the murderer or the
colonel was not in the room during the murder.
The policeman concludes that Lady Barntree is the murderer.
Give propositional variables for every statement
of the argumentation. Write the argumentation as a set
of propositional formulae of the prerequisites and the
conclusion as a propositional formula .