IAI Chapter 5 Knowledge Representation

1. World must be represented explicitly in a knowledge base (KB)

2. KB consits of sentences of a logic // Explicit knowledge

3. Interface ideally via ASK (if alpha holds) and TELL (that alpha holds) // Implicit knowledge

1. Correct if for every derivable alpha ASK(KB, alpha) holds

2. Complete if for every holding ASK(KB, alpha)) alpha is derivable

1. Knowledge // Interface on this level

2. Symbolic

3. Implementation

1. Declarative means that system believes P iff P is thought to be true

2. Which strings are sentences

3. What can be deduced by the sentence

1. One of many DL

2. Alphabet

3. Grammar

1. Logical symbols are delimiters ( (,) ), operators (\neg, \land, quantifiers) and variables

2. Nonlogical symbols are predicates (P⁰ are propositional variables) and functions (F⁰ constants)

3. Meaning is application dependent

1. Terms

2. Atomic formulae (wffs)

3. Formulas

1. Variables are terms

2. For terms t1,…,tn the n-function f(t1,…,tn) is a term

1. For terms t1 and t2 t1=t2 is Awffs

2. For terms t1,…,tn the n-predicate p(t1,…,tn) is a Awffs

1. Every Awffs is a wff

2. For wffs a b and var x \neg a, aOPb, \eXa, \fXa are wffs

1. Sublanguage of FOL

2. No terms, variables or quantifiers

3. Only P⁰ are atomic wffs

1. Abbreviations // a -> b for \neg a \lor b OR a == b for (a -> b) \land (b -> a)

2. Lexical binding for variable x if quantifier with x otherwise free

3. Sentences are wffs without free variables

4. Substitution a[x/t] with all free occurrences of x replaced by t

1. How to understand sentences

2. Logical interpretations

3. Denotation

4. Satisfaction

5. Logical consequence

1. I=<D,Phi> with domain D and interpretation function Phi

2. Predicates refer to objects

3. Functions refer to mappings

1. Assign rules of interpretation to terms

2. With v assigning objects of D to variables

Determine the truth value of given wffs

1. If S|=a all I which satisfy S also satisfy a

2. If S \land \neg a |= unsatisfiable then S|=a holds

1. Formulas (or terms) a conjunction of clauses ([p,~r],[~p,r])

2. Clauses a disjunction of literals [p,~r]

3. Literals atomic sentences or their negation p, ~r

4. The empty clause [] and formula () exist

CNF or DNF

1. Move \forall \exists global // Rename variables

2. Replace \exists with Skolem-constant and functions // Skolemization preservers satisfiability

1. Used for conversion of FOL theories into PL theories

2. Herbrand universe (HU) set of terms by function and terms of S

3. Herbrand base (HB) is t replacing variables by terms of HU

4. Herbrand theorem S is satisfiable if HB is satisfiable

5. HB are propositional but generally infinite

1. Remove if positive and negative literal are in two clauses and unite the remaining literals to resolvent

2.The interpretation always satisfies the resolvent

3. Exponential runtime in worst case

4. Not correct for if S→c then S|=c

5. Correct and complete for S→[] iff S|=false

1. Correct and complete

2. For unifiable l1 and ~l2 by unifier t we obtain resolvent with the most general unifier (MGU) // Rename variables of two clauses

3. Make use of the answer predicate A(x)

1. Forall t’ exists t~ t’=t*t~

2. Replace next disagreement

3. Make the occur check

1. With BFS (So-called semi-decidable)

2. With DFS infinite branch or resolvent possible

3. One clause might be needed multiple times

1. For \exists P(x) add (P(x) \land \neg A(x))

2. Answer is substitution of A(x)

3. Multiple answers possible and might contain variables

1. Eliminating clauses

2. Ordering

3. Set of support

4. Operators with sense of direction

1. Pure clauses if only l in clause but no ~l exists

2. Tautologies if l and ~l are in clause

3. Subsumed clause if superset of another clause

1. Many possibilities

2. Prefer unit clauses for resolution

One of the ancestors is from the query

1. Forward if for [~p,q] we try to find [p,…]

2. Backward if for [~p,q] we try to find [~q,…]