Logic for Computer Scientists/Propositional Logic/Semantics

Semantics edit

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



Definition 4 edit

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.  .

Theorem 1 edit

A formula   is valid, iff   is unsatisfiable.

Proof:   is a tautology

iff every assignment for   is a model for  

iff every assignment for   (which is of course, also an assignment for  ) is not a model for  

iff   has no model

iff   is unsatisfiable.

Definition 5 (Consequence) edit

A formula   is called a consequence of the formulae  , if for every assignment   for   and   holds: if   is a model for  , then   is a model for  . We write  .

The following theorem is a simple consequence from definitions:

Theorem 2 edit

  is called a consequence of the formulae  ,

iff   is a tautologie

iff   is unsatisfiable.

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  .

  false   false false  
  false   false true  
  true   true true  

When applying this procedure it might me helpful to introduce intermediate results for subformulae, as done in the following example.

        (  ))
false false true true true
false true true true true
true false false false true
true true false true true

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   micro-seconds.

Truth Tables edit

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 whether  .

Problem edit

Problem 1 (Propositional) edit

Compute truth tables for the following formulae. Decide for each formula whether it is valid (a tautology), satisfiable or unsatisfiable.


Problem 2 (Propositional) edit

"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"

  1. Formalize these rules with the help of propositional logic.
  2. Try to simplify the advice of the 100-year old man.

Problem 3 (Propositional) edit

Define the following functions recursively by induction over the construction of propositional formulae:

  1.  : Set of atomic formula in  
  2.  : Number of the binary junctors   and   in  

Note: For


  and   holds.

Problem 4 (Propositional) edit

Given the formulae  =    , in which   are atomic formulae ( ) where   denotes exclusive or. Prove for all  : A suitable assignment   for   is a model for   (i.e.  ) iff   halds for an odd number of   ( ).

Problem 5 (Propositional) edit

In the following we investigate formulae, in which only atoms   occur.

  1. How many of such formulae with different truth tables exist at most?
  2. Is there for every truth table a formula? If yes, please indicate a construction!

Problem 6 (Propositional) edit

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  .

Problem 7 (Propositional) edit

Formalize the following expressions and then simplify the corresponding formulae and the verbal propositions.

  1. It is not true that his mother is English and his father French.
  2. It is not true that he is studying physics but not mathematics.
  3. It is not true that the wages are going down and the prices are going up.
  4. It is not true that it is not cold or rainy.

Problem 8 (Propositional) edit

The professor proposes to make a new conception for the lunch in the University restaurant:

  1. There must be bread with every lunch if there is no dessert.
  2. If bread and dessert are served then is be no soup.
  3. If soup is served then there is no bread.

Help the management to fulfill the wishes of the professor. For this

  1. formalize the three propositions (as implications, disjunctions/conjunctions) and combine them into one logical formula.
  2. Give a truth table for this logical formula. Is there a model for the formula?
  3. Give a colloquial verbalization for the assignment.