Major results: (wrt propositional logic)• How to reason correctly.• How to reason efficiently.• How to determine if a statement is true or false.Fuzzy logic deal with statements that are somewhat vague, such as: this paint isgrey.Probability deals with statements that are possibly true, such as whether I will winthe lottery next week.Propositional logic deals with concrete statements that are either true true or false.Predicate Logic (first order logic) allows statements to contain variables, such as ifX is married to Y then Y is married to X.1We need formal definitions for:• legal sentences or propositions (syntax)• inference rules, for generated new sentence. (entailment)• truth or validity. (semantics)ExampleSyntax: (x > y)&(y > z) → (x > z)Interpretation: x = John’s agey= Mary’s agez= Tom’s ageIf John is older than Mary and Mary is older than Tom, then we can conclude Johnis older than Tom. (semantics)Conclusion is not approximately true or probably true, but absolutely true.21 Propositional LogicSyntax:logical constants True and False are sentences.propositional symbols P,Q, R, etc are sentencesThese will either be true (t) or false (f)Balanced Parenthesis if S is a sentence, so is (S).logical operators or connectives : ∨, ∧, ∼, , , , ⇒, ...Actually NAND (Shaeffer stroke) is the only connective that is needed.Sentences legal combinations of connectives and variables, i.e. propositional let-ters are sentences and if s1 and s2 are sentences so are ∼ s1, (s1), s1 ⇒ s2,Note: Instead of ⇒ one can use ∨ and ∧ since p ⇒ q ⇔∼ p ∨ qSemantics:• Each propositional variable can be either True or False.• The truth or falsity of a sentence is defined compositionally.• Truth tables define the semantics of the logical operations.• A sentence is true if any assignment of the propositional variables yields true.This means that a formula with k variables will have 2kinterpretations.3Rules of InferenceThese define derivability or provability, not truth.All of these rules are sound.Modus Ponensα⇒β,ββAnd-Eliminationα1∧...∧αnαiAnd-Introductionα1,α2,...αnα1∧...∧αnOr-Introductionαiα1∨...∨αnDouble-Negation Elimination∼∼ααUnit Resolutionα∨β,∼βαResolutionα∨β,∼β∨γα∨γNote: Many possible sets of axioms and inference rules exist, and this is just one ofthem.How do we know if these axioms are sound or complete?Are these easy to use? Not for most people.42 Important Concepts• A formula is satisfiable if it is true for some assignment of the propositionalvariables.E.G. (p∨ ∼ q) ∧ (∼ p ∨ q) is true if p=t and q=t.• The assignment of either t or f to the variables is called an interpretation.An interpretation is also called a worldSatifiable = true in some interpretation.• A formula is true or valid if it is true in all interpretations.E.G. p∨ ∼ p is always true.• A formula is unsatisfiable if there is no interpretation in which it is true.E.G. p∧ ∼ p is unsatisfiable.• A formula is provable if it follows from the axioms and rules of inference.The axioms and rules of inference define a logic.• A logic is sound if every provable statement is true.• A logic is complete if every true statement can be proven.• A logic is decidable if an effective procedure exists to determine if any state-ment is true or false.• Proposition logic is monotonic, i.e. if we add more sentences, then the oldinferences are still valid.• A Horn sentence has the form P1∧... ∧Pn⇒ Q where each Piand Q is a non-negated atom. Horn sentences allow for computationally tractable inferences.53 Drawing ConclusionsInference Rules: rules for producing new conclusions.Modus Ponens:p, p ⇒ q ` qAbduction (one version):q, p ⇒ q ` pModus Ponens is sound while abduction is not.Resolution: (sound)p ∨ q, ∼ p ∨ r ` q ∨ r4 TheoremsTheorems are sentences that are derived from the axioms and the rules of inference.If the rules of inferences are sound, then any theorem will be true.If the rules of inferences are complete, then any true statement can be proven.65 Translating into Propositional LogicBuilding good computational models is difficult.We did this for the state-space paradigm, and we will do if for propositional andpredicate logic.Example:If it rains, then the game will be cancelled.If the game is cancelled, then we will clean the house.If it rains, then we will clean the house.Is this a valid conclusion?Let p= it rains, q= game canceled, r= we clean house.Then the abstract reasoning schema is:If p then qIf q then rIf p then rIs this valid form of argument? How can we tell?Formally:p ⇒ q, q ⇒ r ` p ⇒ r76 Establishing Truth by ModelsA model is case. If a formula is true for every case, it is true.Example: Use models to prove that:p ⇒ q, q ⇒ r ` p ⇒ rp q r ∼ p ∼ q ∼ r ∼ p ∨ q ∼ q ∨ r ∼ p ∨ rt t t f f f t t t√t t f f f t t f f ×t f t f t f f t t ×t f f f t t f t f ×f t t t f f t t t√f t f t f t t f t ×f f t t t f t t t√f f f t t t t t t√7 SummaryPropositional logic is sound (easy) and complete (difficult).Proposition logic is decidable, i.e. we can determine if any statement is either trueor false. How? Use a truth table.Computationally, to determine a set of clauses is satisfiable is NP-hard, i.e. withour current knowledge this computation takes exponential time in the number ofpropositional variables. How much work is involved in setting up a truth table?88 Limitations of Propositional Logic• Can’t deal with uncertain information, e.g.• There is an 80% chance of rain tomorrow.This will be covered in section on Expert Systems• Can’t combine evidence, e.g.How would you represent the information and reasoning that allowed you todecide on a particular career, car, or school?• Can’t express quantification, e.g.– Every person has a father.– Some students deserve better grades then others.• Doesn’t deal with relations,e.g. If X is contained in Y, and Y is contained in Zthen X is contained in Z orIf X is married to Y, then Y is married to X.• Can’t talk about itself, e.g.The relation “taller than” is transitiveGoal: To write down in a precise way what we
View Full Document
Unlocking...