Knowledge Representation

Knowledge Representation

اسلاید 1: Knowledge Representation- Logic1Knowledge Representation

اسلاید 2: Knowledge Representation- Logic2After knowledge is acquired, it has to be organized and formalized.It can then be put into the knowledge base.There are two types of knowledge representations: 1. Analysis Representation used for analysis and is usually graphical 2. Coding Representation for coding the knowledge Knowledge acquisitionAnalysis RepresentationCoding RepresentationInference

اسلاید 3: Knowledge Representation- Logic3We will talk about coding representation methods and those that we cover are:LogicSemantic NetworksProductionsFramesLogicLogic in general is a subfield of philosophy and its development is credited to ancient Greeks.Symbolic or mathematical logic is used in AI. In symbolic logic rules and procedures are used to draw conclusions using various logicaltechniques.

اسلاید 4: Knowledge Representation- Logic4The general form of a logical processLogicalProcess(using logic toReason)PremisesOrFactsInferencesORConclusionsInference is a process that is used to derive new facts from the ones that are known.

اسلاید 5: Knowledge Representation- Logic5LogicPropositional LogicA^B <-> CFirst Order Logic (Predicate Logic or Predicate Calculus)A system of computingNot differential orintegral calculus/ x (ODD(x)→EVEN(add(x,1)))Higher order Logics / P (P(x)) / f (P(f(x)))

اسلاید 6: Knowledge Representation- Logic6Propositional Logic and Automated ReasoningA: Today is Monday.B: It is raining now.Not A: Today is not Monday.Not B: It is not raining now.A proposition is a declaration:New Zealand is beautiful.The sun is made of chocolate.Symbols like A,B,C,… are used to denote propositions. These are called atoms.A proposition can either be true or false but not both. This is called its truth value and it is assigned not inherent to the proposition.

اسلاید 7: Knowledge Representation- Logic7A FormulaA formula is built with atoms, parantheses and the following five logical operators:Negation ~notConjunction /andDisjunction /orImplication ->if…thenDouble implication<->if and only ifExample formulaeA(~A)(( B / C) / ~D )((( A -> B) / C) / D)Order of precedence ~ / /-><->(((~A)/B) -> (C/D))≡ ~A / B -> C / D

اسلاید 8: Knowledge Representation- Logic8A Recursive Definition of Formulae in Propositional LogicAn atom is a formula.If F is a formula then ~F is a formula.If F and G are formlae thenF / GF / GF -> GF <-> GAre formulae.There are no formulae other than these just defined

اسلاید 9: Knowledge Representation- Logic9Formulae have truth values. Truth value of a formula can be obtained from its atoms and logical operators. B C D (B/C) (~C) ((B/C)/~C) (((B/C)/~C)/D) true true true true false false truetrue true false true false false falsetrue false true true true true truetrue false false true true true truefalse true true true false false truefalse true false true false false falsefalse false true false true false truefalse false false false true false falseInterpretation of FormulaeAn interpretation of a formula F is an assignment of truth values toevery atom. A formula having n atoms has 2^n interpretations (a table with 2^n rows).

اسلاید 10: Knowledge Representation- Logic10A formula is a tautology (or a valid formula) if and only if it is true under all interpretations.B / ~BA formula is an inconsistency if and only if it is false under all interpretations.A formula is a tautology if and only if its negation is an inconsistency (or unsatisfiable formula).(~B / B)A formula is consistent (or satisfiable) if it is not inconsistent.In other words, a formula is consistent if it is true under at least one interpretation.If a formula is a tautology it is consistent but the converse may not hold.A formula F is equivalent to formula G if and only if the truth value of F is equivalent to the truth value of G under all interpretations.

اسلاید 11: Knowledge Representation- Logic11A ProofFormula G is said to be the logical consequence of formulae F1, F2,…, Fnif and only if every interpretation that satisfies (F1/F2/…/Fn)also satisfies G. We may also say, F1, F2,…,Fn imply G.G is called the Goal and the Fi are called the premisses.T demonstrate that G is a logical consequence of the Fs is to prove that((F1/F2/…/Fn) -> G) is a theorem.The demonstartion is the proof.The formulae we will work on will be the ones that are consistent.

اسلاید 12: Knowledge Representation- Logic12A proof may bea direct proofa refutation proofDirect method: ((F1/F2/…/Fn) -> G) is a tautology.Refutation method: ~((F1/F2/…/Fn) -> G) is an inconsistency.Since the negation of a tautology is an inconsistency these are equivalent.~((F1/F2/…/Fn) -> G) ≡ ~(~(F1/F2/…/Fn) / G ) ≡ ((F1/F2/…/Fn) / ~G)

اسلاید 13: Knowledge Representation- Logic13 F G ~G F->G F/(F->G) (F/(F -> G)) ->G (F/(F -> G)) / ~G true true false true true true falsetrue false true false false true falsefalse true false true false true falsefalse false true true false true falseExampleProve by both methods that G is a logical consequence ofF and F-> GWe need 4 rows because we have 2 atoms.This shows that there exists a finite procedure in propositional logic to decide whether a given goal is a theorem or not. Propositional logic is thus decidable. This is known as modus ponens.

اسلاید 14: Knowledge Representation- Logic14As the number of atoms (n) increases the number of rows in the tableIncreases exponentially which makes the use of truth table for proving theorems impractical. There are other methods that may be used.Rules of inferenceWhat we proved using the table (modus ponens) is called a rule of inference and is written as,if F and (F-> G) then GA rule of inference applied to a set of premisses produces a formula.In the case of modus ponens above we can say that G is deduced from F and F-> G by modus ponens. There are other rules of inference and these rules are used in a theoremProving method called the natural deduction.

اسلاید 15: Knowledge Representation- Logic15Natural DeductionA rule of inference is applied to a set of given premisses to deduce theLogical consequence formula which is added to the set of premisses. New formulae is deduced and added to a set by applying various rules of inference until we deduce a formula that is identical to the goal or we can no longer deduce new formulae. One of these cases occurs in finite time. Natural deduction is a direct method. Using this method ofProof we may produce formulae that are not useful in reaching the goal.This is not a computationally desirable methodThere is a refutation proof method called the resolution principle whichUses one rule of inference called the resolution which is effective Enough to make other rules secondary. We will look at this rule and its theorem proving procedure.

اسلاید 16: Knowledge Representation- Logic16ABA/C -> DB->CCmodus ponens on 2 and 4A/Cintroducing conjunction on 1 and 5Dmodus ponens on 3 and 6The goal has been deduce as a logical consequence of the premisses.The goal has been proved to be a theorem.ExampleProving D Given

اسلاید 17: Knowledge Representation- Logic17Proving Theorems by ResolutionLiterals and ClausesThe resolution method is applicable to a formula that is a conjunction of clauses.A clause is a disjunction of n literals for any finite integer n>=0.A literal is an atom or the negation of an atom (Examples: A, B, ~A)An atom and its negation are referred to as complementary literals.(Examples: B and ~B, H and ~H, etc.)Clauses are constructed from literals.Example Clauses:A / B / ~ D~A / BDNIL

اسلاید 18: Knowledge Representation- Logic18Converting a Formula to Clause Form