CSCE 420 Lecture 12

« previous | Thursday, February 21, 2013 | next »

Knowledge Representation

FOL = first-order logic
Propositional logic

Used for making knowledge-based programs to enhance performance. Logic is one of the ways to represent knowledge

Declarative programming: Describing "what" to do; Concepts, relationships; Infer stuff for useful decision-making ("observe" unobservable properties and make actions); Unobservable properties of the world
Procedural programming: telling the computer "how" to do something

function KB-Agent(KB) returns updated KB
  percepts := sensors()
  KB-Tell(KB, make_sentence(percepts, t)) // assert
  action := KB-Ask(KB, make_action_sentence(goals)) // query
  do action
  return KB

KB = KB-Create()
loop do
  KB = KB-Agent(KB)

Natural Language as capture language for knowledge? (highly ambiguous, context-dependent metaphor, analogy)

Ontological engineering: defining vocabulary to clearly and unambiguously define states and actions

Propositional Logic

What is logic?

Inference/Proof Procedures: algorithmic aspect of knowledge representation (what makes the engine chug)

Syntax

Description of well-formed formulas/theorems/sentences (WFF's)

Formally defined with a grammar (BNF)

WFFs are a subset of $\Sigma ^{*}$ , where $\Sigma ={\text{props}}\cup {\text{connectives}}$ is symbols and $*$ is the Kleene operator.

<sentence> ::= <atomic sentence> | <complex sentence>
<atomic sentence> ::= Prog Sym = {P, Q, R, ..., T, F, ..., field_slippery, light_on_in_113_HRBB, raining_in_BCS}
<complex sentence> ::= ¬ <sentence>
                     | <sentence> ∧ <sentence>
                     | <sentence> ∨ <sentence>
                     | <sentence> → <sentence>
                     | <sentence> ↔ <sentence>
                     | <sentence> ⊕ <sentence>
                     | ( <sentence> )

$A\wedge \vee B$ does not parse $A\wedge B\implies C$ parses, but could be interpreted in two ways:

→
|-- ∧
|   |-- A
|   `-- B
`-- C

∧
|-- A
`-- →
    |-- B
    `-- C

Rules of precedence:

¬
∧
∨, ⊕
→
↔

Semantics

"Meaning" and relationships among sentences (e.g. $\neg (A\vee B)$ and $(\neg A\wedge \neg B)$ are syntactically different, but semantically the same.

Given by correspondence to states of affairs in a real world ("interpretation")

Truth-functional semantics:

each proposition maps to TRUE or FALSE in a particular world (no alternatives)
All worlds fall into equivalence classes: Truth assignments for propositional symbols
Model: truth assignment
Compositional semantics: Meaning of any sentence can be derived from the meaning of its components

Tautology: $Q\vee P\vee \neg P$ is satisfied in all models because $P\vee \neg P\equiv \mathbf {T}$

Double negation elimination: $P\equiv \neg \neg P$
Association: $(A\wedge B)\wedge C\equiv A\wedge (B\wedge C)$
Distributivity: $A\wedge (B\vee C)\equiv (A\wedge B)\vee (A\wedge C)$
DeMorgan's Law: $\neg (A\wedge B)\equiv \neg A\vee \neg B$
Implication elimination: $A\implies B\equiv \neg A\vee B$ and $A\iff B\equiv (A\implies B)\wedge (B\implies A)$