1Representation, Reasoning, andPropositional Logic2Representation and Reasoning•In order to determine appropriate actions to take to achievegoals, an intelligent system needs to compactly representinformation about the world and draw conclusions based ongeneral world knowledge and specific facts.•Knowledge is represented by sentences in a particularknowledge representation language stored in a knowledgebase (KB).•A system draws conclusions from the KB to answerquestions, solve problems, or suggest actions to perform toachieve goals.KBInference EngineFactsRulesUserquery conclusions3Knowledge Representation Languagesand Inference•A KR language is specified by-Syntax: The atomic symbols used in the language andhow they can be composed to formal legal sentences.-Semantics: What fact about the world is represented bya sentence in the language, which determines wether it istrue or false.•Logical inference (deduction) derives new sentences inthe language from existing ones.Socrates is a man.All men are mortal.--------------------------Socrates is mortal.•Proper inference should only derive sound conclusions(ones that are true assuming the premises are true)FollowsSentencesFactsSentenceFactEntailsSemanticsSemanticsRepresentationWorld4Propositional LogicSyntax•Logical constants: True, False•Propositional symbols: P, Q, etc. representing specific factsabout the world•If S is a sentence, then (S) is a sentence•If S and R are sentences then so are:-S ∧ R: conjunction, S and R are conjuncts-S ∨ R: disjunction, S and R are disjuncts-S ⇒ R: implication, S is a premise or antecedent, R is the conclusion or consequent, also known as a rule or if-then statement-S ⇔ R: equivalence (biconditional)-¬S: negation•Constants and symbols are atomic, other sentences arecomplex.•A literal is an atomic sentence or its negation (P, ¬S)•Precedence of operators:¬, ∧, ∨, ⇒, ⇔5Propositional LogicSemantics•True and False indicate truth and falsity in the world•A proposition denotes whatever fixed statement about theworld you want which could be true or false.•The semantics of complex sentences are derived from thesemantics of their parts according to the following truthtable.•Or is inclusive. Alternative is exclusive or: P ⊕ Q•Implication is material implication. If P is false P→ Q is trueby default. No causal connection implied.P Q:P P^Q P_Q P)Q P,QFalse False True False False True TrueFalse True True False True True FalseTrue False False False True False FalseTrue True False True True True True6Validity and Inference•An interpretation is an assignment of True or False to eachatomic propostion.•A sentence that is true under any interpretation is valid(also called a tautology or analytic sentence).•Validity can be checked by exhaustively exploring eachpossible interpretation in a truth table:•Inference can be performed by validity checking. If one hasa set of sentences {S1,...Sn} defining one’s backgroundknowledge, and one want to know wether a conclusion Clogically follows, construct the sentence:S1 ∧ S2 ∧... ∧ Sn ⇒ Cand check wether it is valid.How many rows do we need to check?P H P_H (P_H)^ :H ((P_H)^ :H))PFalse False False False TrueFalse True True False TrueTrue False True True TrueTrue True True False True7Models and Entailment•Any interpretation in which a setence is true is called amodel of the sentence.•A sentence A entails a sentence B (A |= B) if every modelof A is also a model of B. In this case, if A is true then Bmust be true.•Correct logical inference is characterized by entailment, wewant to be able to infer wether a statement S follows from aknowledge base:KB |= Sor(KB → S) is validP Q>=P QP QP QP QP Q>P Q>>=>=P Q8Rules of Inference•As an alternative to checking all rows of a truth table, onecan use rules of inference to draw conclusions.•A sequence of inference rule applications that leads to adesired conclusion is called a logical proof.•A |- B denotes that B can be derived by some inferenceprocedure from the set of sentences A.•Inference rules can be verified by the truth-table methodand then used to construct sound proofs.•Finding a proof is simply a search problem with theinference rules as operators and the conclusion as the goal.•Logical inference can be more efficient than truth tableconstruction.9Sample Rules of Inference•Modus Ponens: {α ⇒ β, α} |− β•And Elimination: {α ∧ β} |- α; {α ∧ β} |− β•And Introduction: {α, Β} |− α ∧ β•Or introduction: {α} |− α ∨ β•Double negation Elimination: {¬¬α} |− α•Implication Elimination: {α ⇒ β} |− ¬α ∨ β•Unit resolution: {α ∨ β, ¬β} |− α•Resolution: {α ∨ β, ¬β ∨ γ} |− α ∨ γ10Sample ProofIf John is not married he is a bachelor. (¬P ⇒ Q)John is not a bachelor. (¬Q)Therefore, he is married. (P)¬P ⇒ Q----------¬¬P ∨ Q Implication elimination-----------P ∨ Q, ¬Q Double negation elimination-------------------------P Unit resolutionCould also check validity of:((¬P ⇒ Q) ∧ ¬Q) ⇒ PForm of modus tollens reasoning11Satisfiability and Complexity of Inference•A sentence is satisfiable if it is true under someinterpretation (i.e. it has a model), otherwise the sentence isunsatisfiable.•A sentence is valid if and only if its negation is unsatisfiable.•Therefore, algorithms for either validity or satisfiabilitychecking are useful for logical inference.•If there are n propositional symbols in a sentence, thensimple validity checking must enumerate 2nrows (checkingeach row is only linear in length of the sentence to computetruth value).•However, propositional satisfiability is the first problem to beproven NP-complete, and therefore there is assumed to beno polynomial-time algorithm.•Therefore, sound and complete logical inference inpropositional logic is intractable in general.•But many problems can be solved very