Ch 6 Logical Agents

Question 1

What is the definition of entailment?

Answer 1

one thing follows from another.

KB |= alpha iff
alpha is true in all worlds where KB is true

Question 2

What is the definition of a model?

Answer 2

A formally structured world with respect to which truth can be evaluated

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

M(alpha) is the set of all models of alpha

KB |= alpha iff
M(KB) is subset of M(alpha)

Question 3

What is inference?

What is the definition of soundness and completemeness? Officially and in own words?

Answer 3

Soundness means it doesn’t make any mistakes. It finds truth and only truths…

whenever KB|–i alpha, it is also true that KB |= alpha

Completeness means if there is an answer there, it will find it..

Whenever KB|= alpha, KB |–i alpha.

Question 4

What is the definition of syntax and semantics?

Answer 4

Syntax, the structure of a sentence says wheter a sentence even exists in the language.

Semantics, the meaning is the truths that are the case in particular worlds (??)

Question 5

When is a sentence valid?

Answer 5

It is true in ALL models….

True, A OR !A
A => A
(A AND (A => B)) => B

Question 6

What is the deduction theorem?

Answer 6

KB |= alpha IFF

KB => alpha is valid

Question 7

When is a sentence satisfiable?

When is a sentence unsatisfiable?

Answer 7

It is true in some model.

It is true in no models.

Question 8

How is satisfiability connected to inference?

Answer 8

KB |= alpha

IFF

KB AND !alpha is unsatisfiable.

There is no world where my knowledge base is true and alpha is not true.

(prove alpha by reductio ad absurdum)

Question 9

What is the definition of logically equivalent?

Answer 9

Two sentences are logically equivalent iff they are true in the same models.

a _= b IFF

alpha |= Beta,
AND
Beta |= alpha

Question 10

When is an inference false?

Answer 10

When there are states in my Knowledge Base that are outside of what I’m trying to infer.

Question 11

What is the analogy with multiplication and zero that relates to entailment?

Answer 11

alpha |= Beta

IFF

M(alpha) is a subset of M(Beta)….

alpha is a stronger assertion than Beta, it rules out more possible worlds.

think x = 0. That’s a stronger statement since any model where x is zero will make xy = 0 regardless of what y is.

Question 12

What is Horn form

Answer 12

KB = a conjunction of Horn clauses.

Proposition symbol (diamond) or conjunction of symbols with the => symbol

Question 13

What’s the definition of a proof

Answer 13

chain of conclusions that leads to the desired goal.

Question 14

When would you want to use a forward chaining very a backward chaining algorithm to to proofs in Propositional logic?

Answer 14

FC is data-driven (I know alot of propositions). for ex unconscious processing, object recognition, routine decisions…..

I may do lots of work that is irrelevant to the goal.

BC is goal-driven, appropriate for problem solving.

Complexity of BC is often MUCH LESS than linear in size of KB.

Question 15

What’s the biggest issue to avoid with backward chaining? Why is it a factor? How do you avoid it.

Answer 15

Avoid looping. Because it’s recursive. You can avoid it by storing subgoals and see if the goal you’re about to work is already on the stack.

It’s also key to avoid repeated work: check if a new subgoal

1. has already been proved true or
2. has already failed.

Question 16

Why is backward chaining fast? What is forward chaining potentially wasteful?

Answer 16

Because I only look at rules that are potentially useful in BC.

In FC, …all for the want of a nail. checking everything for one little change. But if things are data driven and there are alot of quick changes, this is the way to go.

Question 17

What are 3 reasons why KB’s containing only definite clauses are interesting?

Answer 17

1. every definite clause can be written as an implication whose premise is a conjunction of positive literals and whose conclusion is a single positive literal.
2. Inference with Horn clauses can be done through forward and backward chaining.
3. Deciding entailment with Horn clauses can be done in time that is linear in the size of the KB.

Question 18

What is a definite clause?
What is a Horn clause?
What is a goal clause?

What is the relationship between them?

Answer 18

a disjunciton of literals of which EXACTLY ONE is positive. = definite clause

a disjunction of literals of which AT MOST ONE is positive. = Horn clause.

clauses with no positive literals.

All definite clauses are Horn clauses.

Question 19

What is the definition of monotonicity?

Answer 19

the set of entailed sentences can only INCREASE as information is added to the knowledge base.

IF KB |= alpha, then KB AND Beta |= alpha.

new knowledge can bring new conclusions, but it can’t invalidate what I already know and the conclusion of rules follow regardless of what else is in the data base.

Question 20

How does the resolution rule lead to a complete inference procedure for all propositional logic?

Answer 20

Because all propositional logic sentences can be put into CNF which what resolution needs.