CH8 (PROPOSITIONAL LOGIC)

• Domain-independent algorithms


  INFERENCE ENGINE
• Domain-specific content


  KNOWLEDGE BASE
• set of sentences (assertions about the "world") in a formal language


  Knowledge base (KB)
• sentences taken as true without proof


  Axiom
• logically deducing new sentences from old sentences

  Inference
• use logic for representation, it learns quickly; adaptable to change

  Knowledge-Based Agents
• The agent must be able to:

  Represent states, actions, etc.

  Incorporate new percepts

  Update internal representations of the "world"

  Deduce hidden properties of the world

  Deduce appropriate actions

  SIMPLE KNOWLEDGE-BASED AGENT
• WHAT IS THE SENSORS IN WUMPUS WORLD?


  for Stench, Breeze, Glitter, Bump (walk into wall), Scream
• WHAT IS THE ACTUATORS IN WUMPUS WORLD:

  Left turn, Right turn, Forward, Grab, Release, Shoot, Die (if on live wumpus or in pit), Climb out (from 1,1 only)
• WUMPUS WORLD CHARACTERIZATION


  PHOTO

  
• is a formal system for manipulating facts so that true conclusions may be drawn

  LOGIC
• rules for constructing valid sentences


  Syntax
• Ex. x + 2 => y is a valid arithmetic sentence, =>x2y + is not

  TRUE
• sentences of correct syntax


  WELL-FORMED
• “meaning” of sentences, define truth sentences


  SEMANTICS
• Ex. x + 2 ≥ y is true in a world where x = 5 and y = 7

  Ex. x+2 ≥ y is false in a world where x = 0, y = 6

  IN SEMANTICS
• means that one sentence follows from another sentence or a knowledge base:

  KB ⊨α

  ENTAILMENT
• entails sentence α if and only if α is true in all worlds where KB is true

  Knowledge base KB
• is a relationship between sentencesthat is based on semantics


  Entailment
• Can α be true when KB is false?

  YES, but if KB is true then α is true also

  KB Alpha (TRUTH TABLE):

  F F

  F T

  T T

  T F (THIS IS FALSE)
• the process of determining what is entailed


  INFERENCE
• i is ______ if whenever KB ├i α, it is also true that KB⊨α.

  • INFERS ONLY WHAT IS ENTAILED
  • WHAT IS INFERRED IS ENTAILED

  SOUNDNESS
• i is ______ if whenever KB ⊨ α, it is also true that KB├iα.

  • INFERS ALL THAT IS ENTAILED
  • WHAT IS ENTAILED IS INFERRED

  COMPLETENESS
• A Logic is _____ as long as:

  • entailed sentences only increase as more information is added to the KB
  • entailed sentences are preserved as more knowledge is added
  • previously entailed sentences cannot be invalidated
  • new information do not contradict previous information
  • cannot change minds

  MONOTONIC / MONOTONICITY
• is an abstraction of a world

  MODEL
• Logicians evaluate the truth/falsity of sentences with respect to a model.

  TRUE
• We say m is a model of a sentence α if α is true in m

  TRUE
• M(α) is the set of all models of α

  TRUE
• A proposition symbol representing a true or false statement

  ATOMIC SENTENCE
• If P is a sentence, ¬P is a sentence

  NEGATION
• If P and Q are sentences, P ^ Q is a sentence

  CONJUNCTION
• If P and Q are sentences, P v Q is a sentence

  DISJUNCTION
• If P and Q are sentences, P → Q is a sentence

  IMPLICATION
• If P and Q are sentences, P ↔ Q is a sentence

  BICONDITIONAL
• ¬, ^, v, → , ↔ are called?

  LOGICAL CONNECTIVES
• • specifies the true/false status of each proposition symbol in the knowledge base
  • Ex. P is true, Q is true, R is false
  • With three symbols, there are 8 possible models (2^3), and they can be enumerated exhaustively

  MODEL
• Rules for evaluating truth with respect to a model:

  Rules for evaluating truth with respect to a model:

  
• specifies the truth value of a composite sentence for each model

  TRUTH TABLE
• an assignment of truth values to the proposition symbols

  each row is for a model
• TRUTH TABLE