What is KRR (Knowledge representation and reasoning)

Symbolic encoding of propositions believed by some agent andtheir manipulation to produce representations of propositions thatare believed by the agent but not explicitly represented.

Why KRR

• KR hypothesis: any artificial intelligent system isknowledge-based
• Knowledge-based system: system with structures that
  • can be interpreted propositionally and
  • determine the system behavior such structures are called its knowledge base (KB)
• Knowledge-based system most suitable for open-ended tasks

• Hallmark of knowledge-based system: cognitive penetrability,i.e., actions depend on beliefs, including implicitly representedbeliefs

• KR假设：任何人工智能系统都是基于知识的。
• 基于知识的系统：具有以下结构的系统。
  • 可以通过命题和
  • 确定系统行为 这样的结构称为其知识库(KB)。
• 基于知识的系统最适合开放式任务
• 基于知识的系统的Hallmark：认知渗透性，即行动依赖于信念，包括隐含表示的信念

KRR and logic

Logic is the main tool for KRR, because logic studies

• How to formally represent agent’s beliefs
• Given the explicitly represented beliefs, what are the implicitlyrepresented beliefs.

There are many kinds of logics. In this course, we will usefirst-order logic (FOL) as the tool for KRR

An example (cont’d)

• Intelligence is needed to answer the question
• Can we make machines answer the question?
• A possible approach
  • First, translate the sentences and question into FOL formulas
    • Of course, this is hard, and we do not have a good way toautomate this step
  • Second, check if the formula of the question is logicallyentailed by the formulas of the sentences
    • We will show that there are ways to automate this step

Alphabet

• Logical symbols (fixed meaning and use):
  • Punctuation: (,),,,.
  • Connectives and quantifiers:=,¬,∧,∨,∀,∃
  • Variables:x,x1,x2,…,x′,x′′,…,y,…,z,…
• Non-logical symbols (domain-dependent meaning and use):
  • Predicate symbols
    • arity: number of arguments
    • arity 0 predicates: propositional symbols -Function symbols
    • arity 0 functions: constant symbols

Terms

• Every variable is a term
• If t1,…,tn are terms andfis a function symbol of arityn,then f(t1,…,tn)is a term

Formulas

• If t1,…,tn are terms andPis a predicate symbol of arityn,thenP(t1,…,tn)is an atomic formula
• Ift1andt2are terms, then(t1=t2)is an atomic formula
• Ifαandβare formulas, andvis a variable, then¬α,(α∧β),(α∨β),∃v.α,∀v.αare formulas

Notation

• Occasionally add or omit (,)
• Use [,] and {,}
• Abbreviation:(α→β)for(¬α∨β)
• Abbreviation:(α↔β)for(α→β)∧(β→α)
• Predicates: mixed case capitalized,e.g., Person, OlderThan
• Functions (and constants): mixed case uncapitalized,e.g.,john, father,

Variable scope

• Free and bound occurrences of variables
• e.g.,P(x)∧∃x[P(x)∨Q(x)]
• A sentence: formula with no free variables
• Substitution:α[v/t]meansαwith all free occurrences of thevreplaced by termt
• In general,α[v1/t1,…,vn/tn]

Interpretations

An interpretation is a pair = <D,I>

• D,Ii D is the domain, can be any non-empty set
• I is a mapping from the set of predicate and function symbols
• If P is a predicate symbol of arity n, I(P) is an n-ary relation over D, i.e., I(P) ⊆ Dn
  • If p is a 0-ary predicate symbol, i.e., a propositional symbol, I(p) ∈{true,false}
• If f is a function symbol of arity n, I(f) is an n-ary function over D, i.e., I(f) : Dn → D
  • If c is a 0-ary function symbol, i.e., a constant symbol, I(c) ∈ D

wrt: with pespect to