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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma^*} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma = \text{props} \cup \text{connectives}} is symbols and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle *} 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> )

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \wedge \vee B} does not parse Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \wedge B \implies C} parses, but could be interpreted in two ways:

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

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

Rules of precedence:

1. ¬
2. ∧
3. ∨, ⊕
4. →
5. ↔

Semantics

"Meaning" and relationships among sentences (e.g. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \neg (A \vee B)} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\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: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q \vee P \vee \neg P} is satisfied in all models because Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P \vee \neg P \equiv \mathbf{T}}

• Double negation elimination: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P \equiv \neg \neg P}
• Association: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (A \wedge B) \wedge C \equiv A \wedge (B \wedge C)}
• Distributivity: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \wedge (B \vee C) \equiv (A \wedge B) \vee (A \wedge C)}
• DeMorgan's Law: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \neg (A \wedge B) \equiv \neg A \vee \neg B}
• Implication elimination: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \implies B \equiv \neg A \vee B} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \iff B \equiv (A \implies B) \wedge (B \implies A)}

Entailment: Logical consequences

• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha \models \beta} iff all models that satisfy Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} also satisfy Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta}
• KB: {P, P → Q}, we say that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle KB \models Q} by modus ponens

Conversely, some are not satisfiable: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P \oplus P} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \wedge (A \implies B ) \wedge \neg B}