Lecture Notes for CS 388L Part 1 Propositional Formulas Syntax The alphabet of propositional logic includes the propositional connectives parentheses and other symbols called atoms We assume that atoms are different from the propositional connectives and parentheses and that there are finitely many of them In examples we will assume that p q r are atoms By a string we understand a finite string of symbols in this alphabet We define when a string is a propositional formula recursively as follows every atom is a formula and are formulas if F is a formula then F is a formula if F and G are formulas and is one of the binary connectives then F G is a formula Properties of formulas can often be proved by structural induction In such a proof we check that all atoms and the 0 place connectives have the property P that we would like to establish and that this property is preserved when a new formula is formed using a unary or binary connective More precisely we show that every atom has property P and have property P if a formula F has property P then so does F for any binary connective then so does F G if formulas F and G have property P Then we can conclude that property P holds for all formulas For instance we can use structural induction to prove that a binary connective never occurs at the very end of a formula as follows Atoms and don t contain binary connectives at all If the last character of F is not a binary connective then the last character of F is not a binary connective The last character F G is not a binary connective 1 Problem 1 A formula cannot contain two binary connectives next to each other True or false Problem 2 If a formula contains more than one character then its last character is not an atom True or false We will abbreviate formulas of the form F G by dropping the outermost parentheses in them For any formulas F1 F2 Fn n 2 F1 F2 Fn will stand for F1 F2 Fn The abbreviation F1 F2 Fn will be understood in a similar way The expression F G will be used as shorthand for F G G F Propositional Formulas Semantics The symbols f and t are called truth values A propositional interpretation or a truth assignment is a function that maps atoms to truth values For instance if the atoms are p q r then an interpretation I can be defined by the formulas I p f I q f I r t 1 An interpretation can be represented by the table of its values p q r f f t The semantics of propositional formulas introduced below defines which truth value is assigned to a formula F by an interpretation I As a preliminary step we need to associate functions with all unary and binary connectives a function from f t into f t with the unary connective and a function from f t f t into f t with each of the binary connectives These functions are denoted by the same symbols as the corresponding connectives and defined by the following tables x f t x t f 2 x f f t t y f t f t x y f f f t x y f t t t x y t t f t For any formula F and any interpretation I the truth value F I that is assigned to F by I is defined recursively as follows for any atom F F I I F I t I f F I F I F G I F I GI for every binary connective FI t then we say that the interpretation I satisfies F and write I F The truth table for a formula F shows the truth values assigned to F by all interpretations For instance here is the truth table for the formula p q If p f f t t q f t f t p q t t t f We assume that there are no atoms other than p and q Problem 3 For any formulas F1 Fn n 1 and any interpretation I F1 Fn I t iff F1I FnI t F1 Fn I f iff F1I FnI f Problem 4 a Assuming that the atoms are p q r find a formula F such that 1 is the only interpretation satisfying F b For any interpretation I there exists a formula F such that I is the only interpretation satisfying F Problem 5 a Assuming that the atoms are p q r find a formula F that is satisfied by two interpretations the interpretation defined by 1 and the interpretation defined by I p t I q t I r t b For any set S of interpretations there exists a formula F such that for all interpretations I I F iff I S 3 Tautologies and Equivalence A propositional formula F is a tautology if every interpretation satisfies F Problem 6 Determine which of the formulas p q q p p q p p p q r p q p r are tautologies A formula F is equivalent to a formula G symbolically F G if for every interpretation I F I GI Problem 7 a We know that conjunction and disjunction are associative F G H F G H F G H F G H Determine whether equivalence has a similar property F G H F G H b We know that implication distributes over conjunction F G H F G F H Find a similar transformation for F G H Problem 8 We know that conjunction distributes over disjunction and that disjunction distributes over conjunction F G H F G F H F G H F G F H Do these connectives distribute over equivalence Problem 9 a De Morgan s laws F G F G F G F G show how to transform a formula of the form F G when Find similar transformations for the cases when is or is or Problem 10 To simplify a formula means to find an equivalent formula that is shorter Simplify the formulas F F G F F G F F G 4