COMP2611 - Knowledge Representation

COMP2611 - Knowledge Representation

1. Propositional Logic

   • Propositional Symbol / Variables
     • Something that can either be T or F.
   • Wffs - well formed formuleas
   • Binary (Logical) Connectives
     • AND - (conjunction)
     • OR - (disjunction)
     • NOT - (negative)
     • IMPLIES [if __ then __] - (implication)
     • If and Only If [equivalence] - (bi-directional)
     • Operator Precedence
   • Interpretation - an assignment to each propositional variable of a value.
     • Either True (T) or False (F)
     • A formula is valid if it evaluaes to true in all interpretations.
   • Truth Table
   • Equivalence - Two wffs are equivalent if every interpretation gives them both the same value.
   • Satisfiability - A set of wffs is satisfiable if there is some interpretation making all the wffs in the set true simultaneously.
   • Resolution
     • Inference procedures based on resolution work by using the principle of proof by contradiction.
   • Literal is a wff which is an atomic sentence.
   • Clause - A set of literals
     • Writen using [ , ] notation
     • An empty claus, [ ] is equivilent to false.
     • Order of literals doesn't matter.
   • Conjuctive Normal Form (CNF)
     • Resolution applies only to clauses
       • Every wff can be converted to an equivalent conjunction of clauses.
     • Procedure for CNF
     • Propositional Resolution Refutation Procedure
       • Convert given set of wffs to CNF
       • Convert negation of clause to prove to CNF
       • Apply resolution to all present clauses
       • Continue till resolution is not possible or empty clause.
       • Empty clause means negation is false to proof is true.
   • Entailment - the idea that a sentence follows logically from another sentence.
   • Inference - How the definition of entailment can be used to derive conclusions
     • Modus Ponens Rule - Mode that affirms
     • Can be more efficient than enumerating models as it ignores irrelevant propositions.

2. First Order Logic

   • Expands on Propositional Logic by allowing properties of individuals.
   • How to describe the world (Method)
     • Identify
       • Constants
       • Predicates
       • Functions
       • Variables
     • Write
       • A formula that will be true only for desired cases
     • Check
       • Syntax
       • Correct in semantics
   • Deducing logical consequence
     • Conversion to CNF
       • 3) Skolemisation
         • Replace existential variable with new constant
         • Replace existential variable with Skolem function of universally quantified variables
       • 1) Eliminate Implies
       • 2) Move negation inwards
       • 4) Rename repeated variables
         • Avoids confusion when when quantifier are dropped
       • 5) Move Universal Quantifier(s) outwards
         • Then drop
       • 6) Distribute over AND & OR
     • Resolving Clauses / Resolution
       • Unification & Substitutions
         • Most General Unifier (MGU)
         • Cyclic
         • Clash
         • Successful
     • Factoring
       • The removal of redundant literals
         • Only applicable if they are unifiable
     • Refutation
       • Adding negation of query to KB and looking for a contradiction.
   • Language
     • Interpretation
       • A world and a meaning for all the elements of the language
       • A formula by itself has no truth value
         • Only in a given interpretation can we work out if T/F.
       • Often have an intended interpretation I, that is modelled through formulas
     • Sentences, S
       • Arity
         • Unary
         • Binary
         • Ternary
       • Atomic Sentences
         • Use of Equality Symbol (=)
         • Predicate Symbols, P
           • Represents relations
           • Use of Terms, T
             • Constant Symbols
               • A, B, C, John
             • A logical expression that refers to Objects / Fixed Individuals
             • Variables
               • x, y, z
             • Function Symbols, F
               • Defined as complex term(s).
           • True / False
       • Complex Sentences
         • Use of Logical Connectives
           • Quantifiers
             • All / Universal
             • There Exists / Existential
             • Allow generation of sentences
               • That then gives a truth value for each interpretation
           • All those present in Propositional Logic

Images and files in the map