Formal Logic Mathematical Structures for Computer Science Chapter 1 Copyright 2006 W H Freeman Co MSCS Slides Variables and Statements Variables A variable is a symbol that stands for an individual in a collection or set For example the variable x may stand for one of the days We may let x Monday or x Tuesday etc Use letters at the end of the alphabet as variables such as x y z A collection of objects is called the domain of a variable Incomplete Statements A sentence containing a variable is called an incomplete statement An incomplete statement is about the individuals in a definite domain or set When we replace the variable by the name of an individual in the set we obtain a statement about that individual For the above example the days in the week is the domain of variable x Example of an incomplete statement x has 30 days Here x can be any month and substituting that we will get a complete statement Section 1 3 Quantifiers Predicates and Validity 2 Quantifiers and Predicates Quantifiers Quantifiers are phrases that refer to given quantities such as for some or for all or for every indicating how many objects have a certain property Two kinds of quantifiers Universal and Existential Universal Quantifier represented by The symbol is translated as and means for all given any for each or for every and is known as the universal quantifier Existential Quantifier represented by The symbol is translated as and means variously for some there exists there is a or for at least one Section 1 3 Quantifiers Predicates and Validity 3 Quantifiers and Predicates Predicate It is the verbal statement that describes the property of a variable Usually represented by the letter P the notation P x is used to represent some unspecified property or predicate that x may have e g P x x has 30 days P April April has 30 days Combining the quantifier and the predicate we get a complete statement of the form x P x or x P x The collection of objects that satisfy the property P x is called the domain of interpretation Truth value of expressions formed using quantifiers and predicates Section 1 3 What is the truth value of x P x where x is all the months and P x x has less than 32 days Undoubtedly the above is true since no month has 32 days Quantifiers Predicates and Validity 4 Truth value of the following expressions Truth of expression x P x 1 2 1 2 P x is the property that x is yellow and the domain of not true interpretation is the collection of all flowers P x is the property that x is a plant and the domain of true interpretation is the collection of all flowers P x is the property that x is positive and the domain of not true interpretation consists of integers Can you find one interpretation in which both x P x is true and Not possible x P x is false Can you find one interpretation in which both x P x is true and Case 1 as mentioned above x P x is false Predicates involving properties of single variables unary predicates Binary ternary and n ary predicates are also possible 1 Section 1 3 x y Q x y is a binary predicate This expression reads as for every x there exists a y such that Q x y Quantifiers Predicates and Validity 5 Interpretation Formal definition An interpretation for an expression involving predicates consists of the following A collection of objects called the domain of interpretation which must include at least one object An assignment of a property of the objects in the domain to each predicate in the expression An assignment of a particular object in the domain to each constant symbol in the expression Predicate wffs can be built similar to propositional wffs using logical connectives with predicates and quantifiers Examples of predicate wffs Section 1 3 x P x Q x x y P x y V Q x y R x S x y R x y Quantifiers Predicates and Validity 6 Scope of a variable in an expression Brackets are used wisely to identify the scope of the variable x y P x y V Q x y R x Scope of y is P x y V Q x y while the scope of x is the entire expression x S x V y R y Scope of x is S x while the scope of y is R y x P x y y Q x y Scope of variable y is not defined for P x y hence y is called a free variable Such expressions might not have a truth value at all What is the truth of the expression x A x y B x y C y in the interpretation A x is x 0 B x y is x y and C y is y 0 where the domain of x is positive integers and the domain of y is all integers True x 1 is a positive integer and any integer less than x is 0 Section 1 3 Quantifiers Predicates and Validity 7 Translation Verbal statements to symbolic form Every person is nice can be rephrased as For any thing if it is a person then it is nice So if P x is x is a person and Q x be x is nice the statement can be symbolized as There is a nice person can be rewritten as There exists something that is both a person and nice x P x Q x All persons are nice or Each person is nice will also have the same symbolic form In symbolic form x P x Q x Variations Some persons are nice or There are nice persons What would the following form mean for the example above x P x Q x Section 1 3 This will only be true if there are no persons in the world but that is not the case Hence such a statement is false so almost always goes with conjunction and goes with implication Quantifiers Predicates and Validity 8 Translation Hint Avoid confusion by framing the statement in different forms as possible The word only can be tricky depending on its presence in the statement X loves only Y If X loves anything then that thing is Y Only X loves Y If anything loves Y then it is X X only loves Y If X does anything to Y then it is love Example for forming symbolic forms from predicate symbols D x is x is dog R x is x is a rabbit C x y is x chases y All dogs chase all rabbits For anything if it is a dog then for any other thing if it is a rabbit then the dog chases it x D x y R y C x y Some dogs chase all rabbits There is something that is a dog and for any other thing if that thing is a rabbit then …