Artificial Intelligence (AL-304) - Unit 2 Short Notes

How unit 2 is examined

How an AI system stores knowledge and reasons over it; marks sit in KR problems, logic, resolution and non-monotonic reasoning.

Knowledge Representation

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>Knowledge representation (KR) is the way facts, rules and relations about the world are encoded in a form a program can store, search and reason over to derive new knowledge.</mark>

Need. Without stored knowledge an agent cannot answer, infer or plan. Inference ($\vdash$) is sound if $\vdash \Rightarrow \models$ and complete if $\models \Rightarrow \vdash$ ($KB \models \alpha$: $\alpha$ holds in every model of KB).

Key points (Newell's knowledge level hypothesis).

1. Newell's levels: knowledge level (what the system knows, its goals), symbol level (logic, rules or networks encoding it) and implementation level (data structures, hardware).
2. Principle of rationality: an agent that knows an action leads to its goal selects it.
3. Facts are truths in the world and representations encode them; forward mapping takes facts to representations, backward mapping takes derived ones back.
4. Schemes and their inference: propositional logic (Rain $\rightarrow$ Wet) uses truth tables or resolution; first-order logic (objects, quantifiers) uses unification and resolution; semantic networks (Tweety isa Bird) and frames use inheritance; production rules (IF fever AND rash THEN measles) use chaining.
5. Declarative knowledge states what is true (Bird(Tweety)), usable by any procedure; procedural knowledge is how-to code, efficient but single-use.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-01" viewBox="0 0 338 252" width="338" height="252" role="img" aria-label="Rich and Knight: initial facts to internal representation, reasoning, back to derived facts"><style>#dsfig-u2-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-01 .t{fill:#16181D;font-weight:500}#dsfig-u2-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-01 .dot{fill:#16181D}#dsfig-u2-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-01 .ah{fill:#454C5A}#dsfig-u2-01 .ah.hi{fill:#2340B8}#dsfig-u2-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-01 .e{stroke:#B1B7C3}html.dark #dsfig-u2-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-01 .t{fill:#E6E8ED}html.dark #dsfig-u2-01 .t.inv{fill:#0F1115}html.dark #dsfig-u2-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-01 .dot{fill:#E6E8ED}html.dark #dsfig-u2-01 .ann{fill:#8FA3FF}html.dark #dsfig-u2-01 .lbl{fill:#858D9C}html.dark #dsfig-u2-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-01 .ah{fill:#B1B7C3}html.dark #dsfig-u2-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah6" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh6" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L277,40" marker-end="url(#ah6)"/><path class="e" d="M298,59 L298,191" marker-end="url(#ah6)"/><path class="e" d="M279,212 L61,212" marker-end="url(#ah6)"/><path class="e" d="M40,59 L40,191" marker-end="url(#ah6)"/><g class="wl"><rect x="138.3" y="31" width="61.5" height="18" rx="9"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">forward</text></g><g class="wl"><rect x="260.1" y="117" width="75.9" height="18" rx="9"/><text class="t" x="298" y="126" dy=".35em" text-anchor="middle">reasoning</text></g><g class="wl"><rect x="134.7" y="203" width="68.7" height="18" rx="9"/><text class="t" x="169" y="212" dy=".35em" text-anchor="middle">backward</text></g><g class="wl"><rect x="9.3" y="117" width="61.5" height="18" rx="9"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">desired</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">IF</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">IR</text><circle class="n" cx="298" cy="212" r="18"/><text class="t" x="298" y="212" dy=".35em" text-anchor="middle">DR</text><circle class="n" cx="40" cy="212" r="18"/><text class="t" x="40" y="212" dy=".35em" text-anchor="middle">DF</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Rich and Knight: initial facts to internal representation, reasoning, back to derived facts</figcaption></figure>

Conceptual Dependency (Schank), the scheme for NLU. CD represents meaning with primitive acts, so same-meaning sentences share one structure.

1. Primitive acts: ATRANS (transfer of ownership, give), PTRANS (change of location, go), MTRANS (transfer of information, tell), MBUILD (decide), PROPEL (push), MOVE (move a body part), GRASP (hold), INGEST (eat), EXPEL (cry), SPEAK (say), ATTEND (listen).
2. Cases: actor, object (o), recipient or direction (R, D), instrument (I); tenses p past, f future.
3. Advantages: one language-independent structure per meaning, inference rules written once per primitive, and expected slots that infer missing information.
4. Limits: primitives miss emotions and abstract ideas, simple sentences become large, and CD inference is not standardised.

Example. "Ram gave Sita a book" is Ram $\overset{p}{\Leftrightarrow}$ ATRANS, o = book, R from Ram to Sita; "Sita received a book from Ram" gets the same structure. "Ram went to Delhi" is PTRANS. "Sita bought a book from Ram" is two ATRANS: book from Ram to Sita, money from Sita to Ram.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-02" viewBox="0 0 379.4 303.6" width="379.4" height="303.6" role="img" aria-label="CD for Ram gave Sita a book; Src is Ram as the giver, p marks past tense"><style>#dsfig-u2-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-02 .t{fill:#16181D;font-weight:500}#dsfig-u2-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-02 .dot{fill:#16181D}#dsfig-u2-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-02 .ah{fill:#454C5A}#dsfig-u2-02 .ah.hi{fill:#2340B8}#dsfig-u2-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-02 .e{stroke:#B1B7C3}html.dark #dsfig-u2-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-02 .t{fill:#E6E8ED}html.dark #dsfig-u2-02 .t.inv{fill:#0F1115}html.dark #dsfig-u2-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-02 .dot{fill:#E6E8ED}html.dark #dsfig-u2-02 .ann{fill:#8FA3FF}html.dark #dsfig-u2-02 .lbl{fill:#858D9C}html.dark #dsfig-u2-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-02 .ah{fill:#B1B7C3}html.dark #dsfig-u2-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah7" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh7" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M61,126 L156.6,126" marker-end="url(#ah7)" marker-start="url(#ah7)"/><path class="e" d="M193.7,115.9 L291.5,54.8" marker-end="url(#ah7)"/><path class="e" d="M195.6,132 L305.8,168.7" marker-end="url(#ah7)"/><path class="e" d="M191.8,138.6 L316.7,249.6" marker-end="url(#ah7)"/><g class="wl"><rect x="99.2" y="117" width="19.2" height="18" rx="9"/><text class="t" x="108.8" y="126" dy=".35em" text-anchor="middle">p</text></g><g class="wl"><rect x="236.8" y="74" width="19.2" height="18" rx="9"/><text class="t" x="246.4" y="83" dy=".35em" text-anchor="middle">o</text></g><g class="wl"><rect x="234.6" y="142.8" width="40.8" height="18" rx="9"/><text class="t" x="255" y="151.8" dy=".35em" text-anchor="middle">R-to</text></g><g class="wl"><rect x="227.9" y="185.8" width="54.3" height="18" rx="9"/><text class="t" x="255" y="194.8" dy=".35em" text-anchor="middle">R-from</text></g><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">Ram</text><circle class="n" cx="177.6" cy="126" r="18"/><text class="t" x="177.6" y="126" dy=".35em" text-anchor="middle">ATR</text><rect class="n" x="290.2" y="25" width="50" height="30" rx="15"/><text class="t" x="315.2" y="40" dy=".35em" text-anchor="middle">Book</text><rect class="n" x="307.4" y="162.6" width="50" height="30" rx="15"/><text class="t" x="332.4" y="177.6" dy=".35em" text-anchor="middle">Sita</text><circle class="n" cx="332.4" cy="263.6" r="18"/><text class="t" x="332.4" y="263.6" dy=".35em" text-anchor="middle">Src</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">CD for Ram gave Sita a book; Src is Ram as the giver, p marks past tense</figcaption></figure>

Ambiguity. Lexical ("bank"): pick the sense that fits the neighbouring words. Syntactic ("saw Sita with a telescope"): keep the parse with a consistent CD. Semantic: one parse with several meanings, such as quantifier scope in "Every student read a book" (one book or one each), settled by context. A grammatical but meaningless sentence ("Colourless green ideas sleep furiously") is semantic anomaly, rejected by case constraints.

Context and pragmatics. Scripts (restaurant) supply unstated events: "Ram ate and left" implies he paid; expectation-driven inference uses a primitive's slots (ATRANS expects a recipient) to predict missing parts; anaphora binds a pronoun to the CD role filler that fits. Alternatives: ontologies (shared classes and relations) and knowledge graphs (triples such as Ram, friendOf, Sita).

Answer frame. Levels: definition; Newell's levels and rationality; the mapping diagram; schemes, declarative versus procedural. NLU: ambiguities; CD with the diagram; context; advantages and limits.

Asked: [7 marks] (Nov 2022) Elucidate various knowledge level representations involved in reasoning process. Asked: [7 marks] (Jun 2024) Analyze a complex AI problem, such as natural language understanding, and propose a knowledge representation scheme that would effectively address its challenges.

Problems in representing knowledge

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>Knowledge representation issues are the properties a good scheme must have and the difficulties that remain when real-world knowledge is encoded, such as adequacy, efficiency, granularity, incompleteness and change.</mark>

Need for KR. A system must hold much knowledge to reason and act, and its scheme decides what it can express and how fast it infers.

Approaches.

1. Simple relational knowledge stores facts as table rows (below); it answers lookups but supports little inference.
2. Inheritable knowledge uses an isa hierarchy in which classes pass values down.
3. Inferential knowledge stores facts as logic: $\forall x\,(Man(x) \rightarrow Mortal(x))$.
4. Procedural knowledge stores how-to as code: batting average = look up hits and at-bats, return hits / at-bats.

Inheritance. Adult-Male (height 5-10) isa Person; Baseball-Player (height 6-1, batting average .252) isa Adult-Male; Fielder (.262) and Pitcher (.106) isa Baseball-Player; Pee-Wee-Reese instance Fielder. Pee-Wee-Reese inherits height 6-1 and batting average .262, because the value on the most specific class overrides the general ones (6-1 over 5-10, .262 over .252).

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-03" viewBox="0 0 596 209" width="596" height="209" role="img" aria-label="Person, Adult-Male, Baseball-Player, Fielder, Pitcher, Pee-Wee-Reese; arrows point child to parent"><style>#dsfig-u2-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-03 .t{fill:#16181D;font-weight:500}#dsfig-u2-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-03 .dot{fill:#16181D}#dsfig-u2-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-03 .ah{fill:#454C5A}#dsfig-u2-03 .ah.hi{fill:#2340B8}#dsfig-u2-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-03 .e{stroke:#B1B7C3}html.dark #dsfig-u2-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-03 .t{fill:#E6E8ED}html.dark #dsfig-u2-03 .t.inv{fill:#0F1115}html.dark #dsfig-u2-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-03 .dot{fill:#E6E8ED}html.dark #dsfig-u2-03 .ann{fill:#8FA3FF}html.dark #dsfig-u2-03 .lbl{fill:#858D9C}html.dark #dsfig-u2-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-03 .ah{fill:#B1B7C3}html.dark #dsfig-u2-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M150,40 L61,40" marker-end="url(#ah8)"/><path class="e" d="M279,40 L190,40" marker-end="url(#ah8)"/><path class="e" d="M408,40 L319,40" marker-end="url(#ah8)"/><path class="e" d="M413.6,155.6 L312.8,54.8" marker-end="url(#ah8)"/><path class="e" d="M537,40 L448,40" marker-end="url(#ah8)"/><g class="wl"><rect x="87.7" y="31" width="33.6" height="18" rx="9"/><text class="t" x="104.5" y="40" dy=".35em" text-anchor="middle">isa</text></g><g class="wl"><rect x="216.7" y="31" width="33.6" height="18" rx="9"/><text class="t" x="233.5" y="40" dy=".35em" text-anchor="middle">isa</text></g><g class="wl"><rect x="345.7" y="31" width="33.6" height="18" rx="9"/><text class="t" x="362.5" y="40" dy=".35em" text-anchor="middle">isa</text></g><g class="wl"><rect x="345.7" y="95.5" width="33.6" height="18" rx="9"/><text class="t" x="362.5" y="104.5" dy=".35em" text-anchor="middle">isa</text></g><g class="wl"><rect x="457.2" y="31" width="68.7" height="18" rx="9"/><text class="t" x="491.5" y="40" dy=".35em" text-anchor="middle">instance</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">Per</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">AM</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">BP</text><circle class="n" cx="427" cy="40" r="18"/><text class="t" x="427" y="40" dy=".35em" text-anchor="middle">Fld</text><circle class="n" cx="427" cy="169" r="18"/><text class="t" x="427" y="169" dy=".35em" text-anchor="middle">Pit</text><circle class="n" cx="556" cy="40" r="18"/><text class="t" x="556" y="40" dy=".35em" text-anchor="middle">PWR</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Person, Adult-Male, Baseball-Player, Fielder, Pitcher, Pee-Wee-Reese; arrows point child to parent</figcaption></figure>

Properties of a good scheme.

1. Representational adequacy: it can represent every kind of knowledge the domain needs.
2. Inferential adequacy: it can manipulate stored structures to derive new ones; representational adequacy concerns what can be stored, inferential adequacy what can be derived.
3. Inferential efficiency: it stores guidance (indexes, heuristics) that steers inference to useful paths.
4. Acquisitional efficiency: new knowledge is added easily, ideally automatically.

KR issues (Rich and Knight).

1. Important attributes: isa and instance support inheritance, so are explicit.
2. Relationships among attributes: inverses (team, team-members), single-valued attributes, computed values.
3. Granularity: "John spotted Sue" is spotted(John, Sue) or primitive see(John, Sue); primitives make facts large.
4. Sets of objects: whole-set properties are stored on the set, listed (extension) or by rule (intension).
5. Finding the right structures: select one, revise it when it does not fit.
6. Uncertainty and vagueness ("tall") need probability and fuzzy logic.
7. New facts may contradict old ones, so beliefs are revised (non-monotonic).
8. Incompleteness: the KB never holds every fact, so the system reasons with defaults.
9. Common-sense knowledge (a dropped glass breaks) is vast and unstated, so it is hard to encode.

Expressiveness versus tractability. The more a language says, the harder reasoning becomes: propositional logic is decidable (truth tables end) but has no general rules; FOL has them but is semi-decidable, proving every entailed sentence while a non-entailed one may run forever. Horn clauses trade expressiveness for tractability.

Classic problems, with a robot moving block A.

1. Frame: after move(A, table), what does not change (A's colour, B's position) must be stated, one axiom per fact.
2. Qualification: A not too heavy, gripper working, path clear; preconditions never end.
3. Ramification: moving A also moves the cup on A, so indirect effects must be derived.

Answer frame. Need; approaches with table and hierarchy if asked; four properties; Rich and Knight issues; trade-off; classic problems; close that no scheme satisfies all.

Pitfall: Do not confuse inferential adequacy (can it derive) with inferential efficiency (how fast it derives).

Asked: [7 marks] (Jun 2023, Dec 2024) Explain the various problems in knowledge representation? List and explain some common problems and challenges in representing knowledge in AI systems. Asked: [7 marks] (Jun 2025) Discuss various approaches and issues in knowledge representation. Also discuss various problems in representing knowledge. Asked: [7 marks] (Jun 2023, Dec 2024, Dec 2025) Explain knowledge representation issues.

Knowledge representation using propositional and predicate logic

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>Propositional logic represents facts as whole statements that are true or false, while predicate (first-order) logic represents objects, their properties and relations, and uses quantifiers to state general facts.</mark>

Propositional syntax. WFF rules: (1) every symbol and T, F is a WFF; (2) if $\alpha$ is, so is $\neg\alpha$; (3) if $\alpha, \beta$ are, so are $(\alpha \wedge \beta)$, $(\alpha \vee \beta)$, $(\alpha \rightarrow \beta)$, $(\alpha \leftrightarrow \beta)$; (4) nothing else is.

Propositional semantics. A truth assignment gives each symbol T or F and compounds follow the table; a sentence is satisfiable if some assignment makes it true, valid if all do. It cannot express relations or generalisations.

First-order syntax. FOL helps KR by stating relations and general rules with exact semantics and sound inference. Constants name objects (Marcus), variables stand for any object ($x$), functions map objects to objects (father(x)); a term is a constant, variable or function of terms. Predicates (Roman(x), LoyalTo(x,y)) applied to terms give atoms; connectives and equality (father(Ram) = Dasharath) and the quantifiers $\forall x\, F$, $\exists x\, F$ build formulas. $\forall$ normally pairs with $\rightarrow$, $\exists$ with $\wedge$.

First-order semantics. An interpretation fixes a non-empty domain D and maps constants to objects, predicates to relations and functions to functions on D; $\forall x\, P(x)$ is true iff $P$ holds for every object in D, $\exists x\, P(x)$ iff for at least one. Limits for KR: semi-decidable, no uncertainty, no defaults or exceptions, and monotonic.

Example (Jun 2025 paper).

Exclusive "or" adds $\neg (L \wedge H)$.

Answer frame. FOL's definition; syntax and semantics; role and limits in KR; two translated sentences; close that FOL underlies logic-based AI. Translation: state predicate meanings first.

Pitfall: $\forall$ with $\wedge$ or $\exists$ with $\rightarrow$ gives a wrong meaning; "Everyone is loyal to someone" is $\forall x \exists y$, not $\exists y \forall x$.

Asked: [9 marks] (Jun 2023, Dec 2025) Explain how does predicate logic help in knowledge representation in AI? Asked: [7 marks] (Dec 2023) Write short notes on: i) Propositional logic ii) First Order Predicate logic. Asked: [7 marks] (Jun 2025) Use predicate logic to express formally: i) Marcus tried to assassinate Caesar. ii) All Pompeian's were Roman. iii) All Romans were either loyal to Caesar or hated him. iv) Everyone is loyal to someone. v) People only try to assassinate rulers they are not loyal to.

Comparison of propositional and predicate logic

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>Propositional logic deals with complete statements as true or false units, whereas predicate logic looks inside the statement at objects, predicates and quantifiers.</mark>

Key points. Predicate logic contains propositional logic, so it is strictly more powerful. Propositional logic suits small fixed domains (circuits); predicate logic suits many objects (databases, NLP).

Answer frame. Definitions; a syntax and semantics block for each (WFF rules and truth table; terms, atoms, quantifiers, from the section above); the table; close that predicate logic wins for relations and generalisation.

Asked: [7 marks] (Jun 2024) Compare and contrast propositional logic and predicate logic in terms of their expressiveness and applicability in different problem domains. Asked: [7 marks] (Jun 2024, Dec 2025) Compare propositional logic and predicate logic.

Resolution

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>Resolution is a single inference rule that takes two clauses containing complementary literals and produces a new clause (the resolvent) by removing that pair; it is sound and, used as refutation, complete.</mark>

Rule. From $A \vee B$ and $\neg A \vee C$ infer $B \vee C$; $A$ with $\neg A$ gives the empty clause.

Deduction, resolution, refutation. (1) Deduction derives conclusions certainly true if the premises are. (2) Resolution is one deductive rule on clauses. (3) Refutation proves $P$ by adding $\neg P$ and deriving the empty clause. (4) Together: axioms plus negated goal are resolved to the empty clause, so $P$ is deduced.

Steps (conversion to clause form).

Step 1: Eliminate -> and <-> (A -> B is not-A or B).
Step 2: Move negation inward (De Morgan, quantifier negation).
Step 3: Standardise variables: one variable per quantifier.
Step 4: Move all quantifiers left (prenex form).
Step 5: Skolemize existential variables.
Step 6: Drop universal quantifiers.
Step 7: Convert to CNF (distribute or over and).
Step 8: Make each conjunct a clause.
Step 9: Standardise apart: no two clauses share a variable.

Worked: $\forall x (Student(x) \rightarrow \exists y (Course(y) \wedge Takes(x,y)))$. Skolemize $y = f(x)$, then CNF: $\neg Student(x) \vee Course(f(x))$ and $\neg Student(x) \vee Takes(x,f(x))$.

Unification finds a substitution making two literals identical.

Step 1: Different predicate or arity: fail.
Step 2: Unify arguments left to right, applying the substitution so far.
Step 3: Equal constants match; different constants fail.
Step 4: Variable x with term t gives x/t, but fail if x occurs in t.
Step 5: Return the composed substitution when all match.

Worked: $Knows(John, x)$ and $Knows(y, Mother(y))$ give $\{y/John, x/Mother(John)\}$. $Knows(John, x)$ and $Knows(x, Elizabeth)$ fail: $x/John$, then John and Elizabeth mismatch.

Example (Dec 2023 paper). Facts: $\forall x (Easy(x) \rightarrow Likes(Steve,x))$; $\forall x (Science(x) \rightarrow Hard(x))$; $\forall x (CSE(x) \rightarrow Easy(x))$; $CSE(CS3101)$. Goal $\exists z\, Likes(Steve,z)$, negated to $\neg Likes(Steve,z)$, with $Ans(z)$ to record the answer.

Proof: C5, C1, $\{x/z\}$: $\neg Easy(z) \vee Ans(z)$; C3, $\{y/z\}$: $\neg CSE(z) \vee Ans(z)$; C4, $\{z/CS3101\}$: $Ans(CS3101)$, the empty clause with the answer. Steve likes CS3101.

Answer frame. Definition, rule; the three terms, combined; procedure (Inferencing); clause steps; unification; close that resolution underlies Prolog.

Pitfall: Forgetting to negate the goal, or skipping Skolemization before dropping quantifiers.

Asked: [7 marks] (Nov 2022, Dec 2025) Explain resolution and inference mechanisms. Asked: [7 marks] (Nov 2022) Explain resolution in predicate logic. Explain about resolution, refutation and deduction. Asked: [7 marks] (Dec 2023) Steve likes easy courses; science courses are hard; all courses in the CSE department are easy; CS3101 is a CSE course. Translate into predicate logic, convert to clausal form, and using resolution prove "What course would Steve like".

Refutation

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>Refutation (proof by contradiction) proves a statement by assuming its negation and deriving the empty clause.</mark>

Key points.

1. To prove $P$ from KB, add $\neg P$ and resolve until the empty clause appears.
2. The empty clause means KB $\wedge \neg P$ is unsatisfiable, so KB entails $P$; resolution is refutation-complete.

Deduction

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>Deduction is reasoning from general premises to a specific conclusion that is certainly true whenever the premises are true.</mark>

Key points.

1. KR encodes facts and rules in a formal language a program can reason over; logic has exact syntax and semantics, so sentences are manipulated mechanically, which makes deduction possible.
2. An inference engine applies Modus Ponens ($P$, $P \rightarrow Q$, so $Q$) and resolution soundly; resolution refutation is refutation-complete, so if KB entails $P$, adding $\neg P$ always yields the empty clause.
3. Example: from Man(Socrates) and $\forall x (Man(x) \rightarrow Mortal(x))$ deduce Mortal(Socrates).
4. Limits: it adds nothing beyond the premises and fails on incomplete or uncertain knowledge.

Asked: [7 marks] (Jun 2024) How does knowledge representation facilitate the process of deductive reasoning in AI?

Theorem proving

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>Automated theorem proving is the use of a program to show that a statement follows logically from a set of axioms, using inference rules.</mark>

Key points. The theorem is the goal, the axioms are the KB and the proof is a sequence of inference steps; resolution refutation is the standard method.

Inferencing

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>Inference is deriving new facts or conclusions from known facts and rules; in AI the inference engine of a knowledge-based system does it.</mark>

Key points.

1. Rules of inference: Modus Ponens ($P$, $P \rightarrow Q$ give $Q$), Modus Tollens ($\neg Q$, $P \rightarrow Q$ give $\neg P$), And-elimination, Universal instantiation ($\forall x\, P(x)$ gives $P(a)$) and resolution ($A \vee B$, $\neg A \vee C$ give $B \vee C$).
2. Deduction goes general to specific and is certain.
3. Induction goes from examples to a probable rule (the sun rose daily, so it always will).
4. Abduction finds the best explanation (wet grass, so it probably rained).
5. Forward chaining fires rules whose conditions hold from known facts until the goal appears (data-driven).
6. Backward chaining makes the conditions of rules concluding the goal into sub-goals until facts are reached (goal-driven).

Steps (resolution procedure).

Step 1: Convert the KB to clause form.
Step 2: Negate the goal, convert it to clauses and add them.
Step 3: Pick two clauses with complementary literals (unify in FOL).
Step 4: Resolve them and add the resolvent.
Step 5: Empty clause: proved; no new clause: not provable; else Step 3.

Example: KB $P \rightarrow Q$, $P$; goal $Q$. Clauses $\neg P \vee Q$, $P$, $\neg Q$. $\neg Q$ with $\neg P \vee Q$ gives $\neg P$; with $P$ gives the empty clause, so $Q$ is proved.

Chaining example. R1: Fever $\wedge$ Rash $\rightarrow$ Measles; R2: Measles $\rightarrow$ Isolate; R3: Isolate $\wedge$ Bed $\rightarrow$ Admit; facts Fever, Rash, Bed; goal Admit. Forward: R1 adds Measles, R2 adds Isolate, R3 adds Admit. Goal reached. Backward: Admit needs Isolate, Bed (R3); Isolate needs Measles (R2), which needs Fever, Rash (R1); all facts. Proved.

Answer frame. Definition and engine; rules of inference; the three types; chaining on the rule base; the comparison.

Asked: [5 marks] (Jun 2023, Dec 2025) What is AI Inference? Explain.

Monotonic and non-monotonic reasoning

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>In monotonic reasoning, adding new information never invalidates conclusions already drawn, whereas in non-monotonic reasoning a conclusion may be withdrawn when new information arrives.</mark>

Monotonic, formally. If $KB \models \alpha$ then $KB \wedge \beta \models \alpha$ for any $\beta$: conclusions only grow, proofs stay valid whatever is added, but incomplete knowledge cannot be handled.

Key points.

1. It is needed because real-world knowledge is incomplete, so agents use defaults and revise them.
2. Default logic states rules such as "birds normally fly" that hold unless contradicted.
3. Circumscription minimises chosen predicates (Abnormal(x)): only objects that must be abnormal are.
4. The closed-world assumption takes any fact not stated or derivable as false.
5. A justification-based TMS records each belief's justification and retracts dependents when a premise changes: Flies(Tweety) goes once Penguin(Tweety) is added.
6. Medical diagnosis: fever and cough suggest flu by default; a test showing bacteria retracts flu and concludes pneumonia.
7. Automated driving: the car assumes the lane is clear and keeps speed; sensing a pedestrian or closed road, it drops that and replans.

Example (default logic). $\frac{Bird(x) : Flies(x)}{Flies(x)}$: if x is a bird and Flies(x) is consistent, conclude Flies(x). Bird(Tweety) gives Flies(Tweety); adding Penguin(Tweety) and $\forall x (Penguin(x) \rightarrow \neg Flies(x))$ makes it inconsistent, so it is withdrawn.

Answer frame. Definitions; the table; need with Tweety; default logic, circumscription, JTMS; scenarios; close that changing knowledge needs non-monotonic reasoning.

Asked: [7 marks] (Dec 2024, Dec 2025) Give examples of scenarios where non-monotonic reasoning is essential in AI applications. What distinguishes it from monotonic reasoning? Asked: [7 marks] (Dec 2024, Dec 2025) Discuss monotonic and non-monotonic reasoning.

Last-minute revision

• KR encodes knowledge for reasoning; sound is $\vdash \Rightarrow \models$, complete is $\models \Rightarrow \vdash$.
• CD: 11 primitive acts; "Ram gave Sita a book" is ATRANS; buying is two ATRANS.
• $\forall$ pairs with $\rightarrow$, $\exists$ with $\wedge$; a truth table has $2^n$ rows.
• Resolution: $A \vee B$, $\neg A \vee C$ give $B \vee C$; refutation-complete.
• Steve likes CS3101 via $x/z$, $y/z$, $z/CS3101$.
• Monotonic: $KB \models \alpha$ implies $KB \wedge \beta \models \alpha$.

Memory hooks

• Frame, Qualification, Ramification: what stays, what is needed, what follows.
• Resolution: "Negate, Unify, Resolve, Empty".

Coverage checklist

• Knowledge Representation: Nov 2022, Jun 2024.
• Problems in representing knowledge: Jun 2023, Dec 2024, Jun 2025, Dec 2025.
• knowledge representation using propositional and predicate logic: Jun 2023, Dec 2023, Jun 2025, Dec 2025.
• comparison of propositional and predicate logic: Jun 2024, Dec 2025.
• Resolution: Nov 2022, Dec 2023, Dec 2025.
• refutation: see Resolution, Nov 2022.
• deduction: Jun 2024.
• theorem proving: not asked recently.
• inferencing: Jun 2023, Dec 2025.
• monotonic and non-monotonic reasoning: Dec 2024, Dec 2025.