3 min read
On this page

Knowledge Representation and Reasoning

Knowledge representation (KR) encodes information about the world in a form that AI systems can use for reasoning, inference, and decision-making.

Propositional Logic Inference

Resolution

A complete inference procedure for propositional logic in CNF. To prove α, show that KB ∧ ¬α is unsatisfiable.

Resolution rule: From (A ∨ B) and (¬B ∨ C), derive (A ∨ C). Resolving complementary literals.

Completeness: If KB ⊨ α, resolution will derive the empty clause (contradiction) from KB ∧ ¬α.

DPLL (Davis-Putnam-Logemann-Loveland)

Backtracking search for satisfying assignments of CNF formulas.

Optimizations: Unit propagation (if a clause has one literal → must be true), pure literal elimination (if a literal appears with only one polarity → set it true), early termination (clause satisfied → skip; empty clause → backtrack).

CDCL (Conflict-Driven Clause Learning)

Modern SAT solvers. Extend DPLL with:

  • Clause learning: When a conflict occurs, analyze the conflict → learn a new clause preventing the same conflict.
  • Non-chronological backtracking: Jump back to the decision level that caused the conflict.
  • Variable scoring (VSIDS): Prioritize variables involved in recent conflicts.
  • Restarts: Periodically restart search (keep learned clauses).

Performance: Modern CDCL solvers (MiniSat, CaDiCaL, Kissat) solve problems with millions of variables in practical applications.

First-Order Logic

Extends propositional logic with objects, predicates, and quantifiers.

Unification

Find a substitution θ that makes two expressions identical.

Unify(Knows(John, x), Knows(John, Jane)) = {x/Jane}
Unify(Knows(John, x), Knows(y, Jane)) = {x/Jane, y/John}
Unify(Knows(John, x), Knows(x, Jane)) = FAIL (x can't be both John and Jane)

Forward Chaining

Start from known facts. Apply rules to derive new facts. Repeat until the query is answered or no new facts can be derived.

Data-driven: Good when many rules are applicable. Used in production systems (CLIPS, Drools).

Backward Chaining

Start from the query. Find rules that conclude the query. Recursively prove the premises.

Goal-driven: Good when the query is specific. Used in Prolog, expert systems, logic programming.

Resolution in FOL

Requires Skolemization (replace existential quantifiers with Skolem functions) and unification.

Ontologies

Formal representations of concepts and relationships in a domain.

Description Logics

The formal foundation of ontologies. Define concepts using constructors: intersection (⊓), union (⊔), negation (¬), existential restriction (∃R.C), universal restriction (∀R.C).

Example: Parent ≡ Person ⊓ ∃hasChild.Person

Reasoning services: Subsumption (is concept A a subconcept of B?), consistency, instance classification.

Semantic Web

RDF (Resource Description Framework): Triples (subject, predicate, object). Data model for linked data.

<http://example.org/Alice> <http://example.org/knows> <http://example.org/Bob> .
<http://example.org/Alice> <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> <http://example.org/Person> .

OWL (Web Ontology Language): Expressive ontology language built on description logics. Classes, properties, individuals, axioms.

SPARQL: Query language for RDF graphs. SQL-like but for graph data.

SELECT ?person ?name WHERE {
    ?person rdf:type ex:Person .
    ?person ex:name ?name .
    ?person ex:knows ex:Alice .
}

Knowledge Graphs

Large-scale graphs of entities and relationships. Entity nodes connected by typed edges.

Examples: Google Knowledge Graph (500B+ facts), Wikidata (100M+ items), DBpedia, YAGO.

Construction: Information extraction from text, structured data integration, crowdsourcing (Wikidata).

Uses: Search engine knowledge panels, question answering, recommendation, drug discovery.

Embedding methods: TransE, RotatE, CompGCN — learn vector representations of entities and relations for link prediction and reasoning.

Frames and Semantic Networks

Frames (Minsky, 1974): Represent stereotypical situations. Slots with default values and constraints.

Frame: Restaurant
  Type: Business
  Has: Menu, Tables, Kitchen
  Typical-event: OrderMeal
  Default-action: SitDown → ReadMenu → Order → Eat → Pay → Leave

Semantic networks: Graph of concepts connected by labeled relationships (is-a, has-a, part-of).

Applications in CS

  • SAT/SMT solvers: Hardware verification, software verification, planning, scheduling. Modern solvers are incredibly powerful tools.
  • Expert systems: Medical diagnosis (MYCIN), configuration (XCON), legal reasoning. Rule-based systems with forward/backward chaining.
  • Knowledge graphs: Google Knowledge Graph powers search. Amazon's product graph powers recommendations. Enterprise knowledge management.
  • Semantic Web: Linked open data, data integration across organizations, ontology-based data access.
  • NLP: Knowledge-grounded question answering, fact verification, entity linking.