AIMA: Logical Agents
Flashcards
Knowledge bases and sentences
How do knowledge-based agents represent their knowledge?
Using a knowledge base.
How are sentences represented in a knowledge base?
In a knowledge representation language.
Entailment, models and validity
What does it mean for a sentence to be valid?
Given true premises, the sentence is always true.
What does it mean for a sentence to be satisfiable?
There exists a model that makes the formula true.
How can you define entailment in terms of validity?
$\alpha \models \beta$ if the sentence $\alpha \implies \beta$ is valid.
How can you define entailment in terms of satisfiability?
if $(\alpha \land \neg\beta)$ is unsatisfiable.
Connectives: conjunction and disjunction
Implication and biconditional
How can you interpret $P \implies Q$?
If $P$ is true, then I am claiming that $Q$ is true; otherwise I am making no such claim.
Why is “5 is even implies Sam is smart” true in logic?
Because the premise of the implication is false, then the overall sentence is true.
Why is “5 is odd implies Tokyo is the capital of Japan” true in logic?
Because logic doesn’t require causation or relevance between premises and conclusions.
How can you write $P \iff Q$ in terms of implication?
Models, soundness and completeness
What is $M(\alpha)$ for some sentence $\alpha$?
The set of all models for $\alpha$.
What is a sound inference algorithm?
One that only derives entailed sentences (never makes things up).
What is a complete inference algorithm?
One that derives all sentences that are entailed.
What’s the brute-force solution for entailment?
Model-checking, trying all the models possible.
Literals, CNF and chaining
What is conjunctive normal form?
Logical sentences consisting only of conjunctions of clauses of literals.
When do forward chaining and backward chaining algorithms work?
When a knowledge base is expressed in Horn form.
What is forward chaining?
Making inferences to try and arrive at a conclusion.
What is backward chaining?
Making inferences backward from a conclusion to try match it to initial knowledge.
How can you do route finding using SAT solvers?
Formulate a sentence that contains assertions about the initial state, transitions and the goals and see if it can find a valid solution.