knowledge, entailment, inference, and models

Question 1

Knowledge base

Answer 1

a set of sentences in a formal language

Question 2

knowledge-based agent

Answer 2

able to:

• represent states, actions, etc.
• incorporate new percepts
• Update internal representations of the world
• Deduce hidden properties of the world
• Deduce appropriate actions

Question 3

model

Answer 3

m is a model of a sentence alpha if alpha is in m

• formally structured worlds with respect to which truths can be evaluated
• M(alpha) is the set of all models of alpha

so KB |- alpha iff M(KB) <= M(alpha)

Question 4

entailment KB |- A

Answer 4

KB entails sentence A iff A is true in all worlds where KB is true

Question 5

wumpus world KB

Answer 5

KB = wumpus-world rules + observations

Question 6

inference ( KB |-i alpha )

Answer 6

KB |-i alpha = sentence alpha can be derived from KB by procedure i

• Inference is best used in first order logic which is expressive enough to say almost anything of interest, and for which there exists a sound and complete inference procedure
• the procedure will any question whose answer follows from what is known by the KB

Question 7

inference soundness

Answer 7

i is sound if whenever KB |-i alpha, it is also true that KB |- alpha

Question 8

inference completeness

Answer 8

i is complete if whenever KB |- alpha, it is also true that KB |-i alpha

Question 9

validity

Answer 9

a sentence is valid if it is true in all models

KB |- alpha iff KB ==> alpha is valid

Question 10

satisfiability

Answer 10

a sentence is satisfiable if it is true in some model

A sentence is unsatisfiable if it is true in no models

connected to inference via the following:

KB |- alpha iff (KB ^ not alpha) is unsatisfiable

Question 11

proof methods

Answer 11

application of inference rules

model checking

Question 12

application of inference rules

Answer 12

-Legitimate (sound) generation of new sentences from old

-proof = a sequence of inference rule applications.
can use inference rules as operators in a standard search algorithm

-typically require transformation of sentences into a normal form

Question 13

model checking

Answer 13

• truth table enumeration (always exponential in n)
• improved backtracking, e.g., Davis–Putnam-Logemann-Loveland (DPLL)
• heuristic search in model space (sound but incomplete)
• -e.g., min-conflicts like hill-climbing algorithms

Question 14

complementary literals

Answer 14

one is the negation of the other