Artificial Intelligence Knowledge, Reasoning, and Logic Syllabus

Knowledge, Reasoning, and Logic syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Knowledge, Reasoning, and Logic in Artificial Intelligence, not a summary of it.

1. 1

   Logical Agents

   4 topics

   • Knowledge-Based Agents
   • Propositional Logic
   • Theorem Proving
   • Model Checking and SAT Solvers
2. 2

   First-Order Logic

   3 topics

   • Syntax and Semantics of FOL
   • Using First-Order Logic
   • Knowledge Engineering in FOL
3. 3

   Inference in First-Order Logic

   4 topics

   • Unification and Lifting
   • Forward and Backward Chaining
   • Resolution in FOL
   • Logic Programming
4. 4

   Knowledge Representation

   4 topics

   • Ontological Engineering
   • Categories and Objects
   • Semantic Networks and Description Logics
   • Reasoning with Default Information
5. 5

   Automated Planning

   5 topics

   • Classical Planning
   • Planning as State-Space Search
   • Planning Graphs and GraphPlan
   • Hierarchical and Partial-Order Planning
   • Planning and Acting in the Real World

Knowledge, Reasoning, and Logic flashcards for Artificial Intelligence

21 of 60 cards from the Knowledge, Reasoning, and Logic deck — real questions with worked answers.

1. What is a knowledge-based agent, and what are the two core components of its knowledge base?

   An agent that decides actions by reasoning over an internal representation of the world. Its knowledge base (KB) is a set of sentences in a formal knowledge representation language, and it uses two operations: TELL (add a sentence to the KB) and ASK (query what follows from the KB).

2. Distinguish syntax, semantics, and a model in a logical knowledge representation.

   Syntax specifies which sentences are well-formed. Semantics defines the truth of each sentence with respect to each possible world. A model is a possible world (an assignment) in which a sentence is true; we write $m$ is a model of $\alpha$ as $m \in M(\alpha)$.

3. Define logical entailment and give its semantic definition.

   $\alpha \models \beta$ ("$\alpha$ entails $\beta$") means $\beta$ is true in every model in which $\alpha$ is true. Formally, $\alpha \models \beta$ if and only if $M(\alpha) \subseteq M(\beta)$.

4. What do soundness and completeness mean for an inference procedure?

   An inference procedure is sound (truth-preserving) if it derives only entailed sentences: if $KB \vdash_i \alpha$ then $KB \models \alpha$. It is complete if it can derive every entailed sentence: if $KB \models \alpha$ then $KB \vdash_i \alpha$.

5. List the five logical connectives of propositional logic in order of precedence (highest to lowest).

   $\lnot$ (not), $\land$ (and), $\lor$ (or), $\Rightarrow$ (implies), $\Leftrightarrow$ (biconditional).

6. State the truth table for implication $P \Rightarrow Q$.

   $P \Rightarrow Q$ is false only when $P$ is true and $Q$ is false; it is true in all three other cases (including whenever $P$ is false, i.e. vacuously true).

7. Define a valid sentence and a satisfiable sentence in propositional logic.

   A sentence is valid (a tautology) if it is true in all models, e.g. $P \lor \lnot P$. A sentence is satisfiable if it is true in at least one model. A sentence is unsatisfiable if true in no model.

8. State the Deduction Theorem linking entailment and validity.

   $\alpha \models \beta$ if and only if the sentence $(\alpha \Rightarrow \beta)$ is valid.

9. State the relationship between entailment and unsatisfiability (proof by refutation).

   $\alpha \models \beta$ if and only if $(\alpha \land \lnot \beta)$ is unsatisfiable. This is the basis of proof by contradiction / refutation.

10. State De Morgan's laws and the distributivity of $\lor$ over $\land$.

    De Morgan: $\lnot(\alpha \land \beta) \equiv (\lnot\alpha \lor \lnot\beta)$ and $\lnot(\alpha \lor \beta) \equiv (\lnot\alpha \land \lnot\beta)$. Distributivity: $(\alpha \lor (\beta \land \gamma)) \equiv ((\alpha \lor \beta) \land (\alpha \lor \gamma))$.

11. State the inference rules Modus Ponens and And-Elimination.

    Modus Ponens: from $\alpha \Rightarrow \beta$ and $\alpha$, infer $\beta$. And-Elimination: from $\alpha \land \beta$, infer $\alpha$ (or $\beta$).

12. What is Conjunctive Normal Form (CNF)?

    A conjunction of clauses, where each clause is a disjunction of literals (a literal is an atom or its negation). Every propositional sentence can be converted to an equivalent sentence in CNF.

13. State the unit resolution and full resolution inference rules for propositional logic.

    Full resolution: from $(\ell_1 \lor \cdots \lor \ell_k)$ and $(m_1 \lor \cdots \lor m_n)$ where $\ell_i$ and $m_j$ are complementary, infer the clause with both removed. Unit resolution is the special case where one clause is a single literal.

14. Why is resolution refutation-complete for propositional logic, and how is it used to prove $KB \models \alpha$?

    Resolution alone cannot generate all entailed sentences, but it can always derive the empty clause (a contradiction) from any unsatisfiable set. To prove $KB \models \alpha$, convert $(KB \land \lnot\alpha)$ to CNF and apply resolution; deriving the empty clause proves the entailment.

15. Define a definite clause, a Horn clause, and a goal clause.

    A definite clause is a disjunction of literals with exactly one positive literal. A Horn clause has at most one positive literal. A goal clause has no positive literals. Definite clauses can be written as implications: body (conjunction of positives) $\Rightarrow$ head.

16. Why are Horn clauses important for efficient inference?

    Inference with Horn clauses can be done via forward chaining or backward chaining, in time linear in the size of the KB, and these proofs are easy for humans to follow. Deciding entailment with Horn clauses is tractable, unlike general propositional inference.

17. Describe the forward-chaining algorithm for propositional definite clauses.

    Start from known facts; whenever all premises of an implication are satisfied, add its conclusion to the known facts. Repeat until the query is added or no new facts can be inferred. It is a data-driven, sound and complete procedure for definite-clause KBs.

18. Contrast forward chaining and backward chaining.

    Forward chaining is data-driven: it starts from known facts and derives all consequences (can do irrelevant work). Backward chaining is goal-directed: it starts from the query and works backward through implications, touching only relevant facts—useful for problem-solving.

19. What is the DPLL algorithm and its three key enhancements over truth-table enumeration?

    DPLL is a complete backtracking search for satisfiability of CNF. Its three improvements are: early termination (a clause is true if any literal is true), pure symbol heuristic (assign pure symbols to make their literals true), and unit clause propagation (assign the forced literal in any unit clause).

20. How do local-search SAT solvers like WalkSAT work, and what is their key limitation?

    WalkSAT starts from a random complete assignment and repeatedly flips one symbol in an unsatisfied clause—either the flip that minimizes unsatisfied clauses (greedy) or a random one (to escape local minima). It is fast on satisfiable problems but cannot prove unsatisfiability (may run forever).

21. What is the phase transition / satisfiability threshold in random 3-SAT?

    The hardness of random 3-SAT problems peaks near a critical clause/symbol ratio $\frac{m}{n} \approx 4.3$. Below it problems are almost always satisfiable, above it almost always unsatisfiable, and the hardest instances cluster at the threshold.

See more Knowledge, Reasoning, and Logic flashcards →

Planning Knowledge, Reasoning, and Logic for Artificial Intelligence

Knowledge, Reasoning, and Logic (Artificial Intelligence) FAQ