Logic for Computer Scientists/Propositional Logic/Semantics

Semantics Definition 3 (Semantics of propositional logic) 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 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 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) 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 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 falsefalse falsefalsetrue truetruetrue When applying this procedure it might me helpful to introduce intermediate results for subformulae, as done in the following example. ( ))falsefalsetruetruetruefalsetruetruetruetruetruefalsefalsefalsetruetruetruefalsetruetrue 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 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 Problem 1 (Propositional) Compute truth tables for the following formulae. Decide for each formula whether it is valid (a tautology), satisfiable or unsatisfiable. Problem 2 (Propositional) "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. Problem 3 (Propositional) Define the following functions recursively by induction over the construction of propositional formulae: : Set of atomic formula in : Number of the binary junctors and in Note: For = and holds. Problem 4 (Propositional) 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) In the following we investigate formulae, in which only atoms occur. How many of such formulae with different truth tables exist at most? Is there for every truth table a formula? If yes, please indicate a construction! Problem 6 (Propositional) 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) Formalize the following expressions and then simplify the corresponding formulae and the verbal propositions. It is not true that his mother is English and his father French. It is not true that he is studying physics but not mathematics. It is not true that the wages are going down and the prices are going up. It is not true that it is not cold or rainy. Problem 8 (Propositional) The professor proposes to make a new conception for the lunch in the University restaurant: There must be bread with every lunch if there is no dessert. If bread and dessert are served then is be no soup. If soup is served then there is no bread. Help the management to fulfill the wishes of the professor. For this formalize the three propositions (as implications, disjunctions/conjunctions) and combine them into one logical formula. Give a truth table for this logical formula. Is there a model for the formula? Give a colloquial verbalization for the assignment.