Transcript PPT
Propositional Logic School of Athens Fresco by Raphael Wikimedia Commons Discrete Structures (CS 173) Madhusudan Parthasarathy, University of Illinois Mathematical logic (symbolic logic) Study of inference using abstract rules that does not assume any particular knowledge of things or of properties. E.g.: All men are mortal Socrates is a man Inference: Socrates is mortal. E.g. All pigs are boisterous Alfred is a pig. Inference: Alfred is boisterous All snarks are frabjous Yeti is a snark. Inference: Yeti is frabjous Key idea: Inference is independent of the subjects (men, pigs, snarks) and properties (mortality, boisterousness, frabjousness). Inference follows simply from language! All pβs are q. h is a p. Inference: h is q. βπ₯. π π₯ β π π₯ π β Inference: q(h) But inference rules neednβt hold in natural language! β¦ quirks of English Sam and Sally are programmers. Inference: Sam is a programmer Sam and Sally are together. Inference: Sam is together! So we need a formal languageβ¦. logic! Propositional logic A proposition is a statement that is either true or false. Examples: β’ Socrates is a man β’ This car is purple β’ 43 is prime Non-examples: β’ Trucks β’ Hello β’ Trkjkjugirtu Propositional logic Propositional logic talks about Boolean combinations of propositions and inferences we can make about them. E.g., If it is raining, then it is cloudy. It is not cloudy. Inference: It is not raining. Abstraction: p: it is raining q: it is cloudy (π β π) βΌ π Inference: ~ π Propositional logic Propositions: p, q, r, s, β¦. Constants: T, F Operators (boolean): β§βΆ and β¨: ππ ¬, ~ βΆ πππ‘ β: πππππππ βΊβΆ bi-implication; iff Syntax: Any formula that combines propositions and constants using these operators Propositional logic: Semantics A formula f, in general, doesnβt have a βtruthβ value associated to it. Model: M - Assigns truth/falsehood to each proposition Any formula f evaluates to true/false in such a model. Implication can be non-intuitive πβπ says βif p is true then q is trueβ If the model sets p to true, and q to true, then π β π evaluates to true. If the model sets p to true, and q to false, then π β π evaluates to false. If the model sets p to false and q to true, then π β π evaluates to true. If the model sets p to false and q to false, then π β π evaluates to true! (vacuosly) Implication So π β π is really the same as ~π βπ βIf p then qβ is same as βeither p is false or q is trueβ Tautology A formula is a tautology if it evaluates to true in every model. E.g. π β¨ ~π If model sets p to true, then formula is true. If model sets p to false, then formula is true. E.g., ( π β π β§ π β π ) β (π β π) Why? βDo you like this or not?β --- βYesβ Non-example: π, π β¨π Equivalence Formulas f and g are equivalent (π β‘ π) if in every model M, either both f and g evaluate to true in M or both evaluate to false in M. E.g., ~π β π β‘ π β π Some important equivalences β’ ~~π β‘ π β’ π β π β‘ ~π β π β’ π β π β‘ ~π β π β‘ ~~π β ~π β‘ ~π β ~π ~π β ~π ππ π‘βπ ππππ‘πππππ ππ‘ππ£π ππ π β π β’ ~ π β§ π β‘ ~π β¨ ~π β’ ~ π β¨ π β‘ ~π β§ ~π β’ ~ π β π β‘ π β§ ~π De Morganβs laws Some important equivalences Distributive laws: β’ ββ§ πβ¨π β‘ ββ§π β¨ ββ§π β’ ββ¨ πβ§π β‘ ββ¨π β§ ββ¨π Commutativity β’ πβ§πβ‘πβ§π β’ πβ¨πβ‘πβ¨π Associativity β’ πβ§ πβ§β β‘ πβ§π β§β β’ πβ¨ πβ¨β β‘ πβ¨π β¨β Contrapositive, converse, negation Proposition: βIf the sky is green, then Iβm a monkeyβs uncle.β β’ Converse β If Iβm a monkeyβs uncle, then the sky is green. β’ Contrapositive β If Iβm not a monkeyβs uncle, then the sky is not green. β’ Negation β The sky is green, but I am not a monkeyβs uncle. Contrapositive, converse, negation Proposition: βIf the sky is green, then Iβm a monkeyβs uncle.β β’ Converse β If Iβm a monkeyβs uncle, then the sky is green. β’ Contrapositive β If Iβm not a monkeyβs uncle, then the sky is not green. β’ Negation β The sky is green, but I am not a monkeyβs uncle. More manipulation examples Show that these are tautologies: ~π β§ π β π β ~π π β¨ π β§ ~π β π Logistics β’ If youβre not registered yet and β Sign sheet at end of class (again) β Sign up for moodle and piazza β Keep on top of homeworks β’ only mini-homework for next week β’ will be released by Friday β’ No discussion sections this week See you next week! β’ Tuesday β More logic β’ Predicate logic β’ Quantifiers β’ Binding and scope β Direct proofs β’ Thursday β More proof practice and strategies