Knowledge Representation and Propositional Logic #

An intelligent agent can store observations and rules, combine them through logical reasoning, and use the resulting conclusions to choose an action. Knowledge representation makes this information explicit so that the agent can reuse what it knows and reason about situations it has not directly observed.

Module topics

• Overview of Logics- Propositional, Predicate, TT-Entail, Theorem Proving
• Logic Representation of a sample agent, Proof by resolution, DPLL Algorithm, Agents based on Propositional logic
• Unification, forward chaining, Backward Chaining, Resolution

The explanations below develop knowledge-based agents and propositional reasoning, using one continuous Wumpus World example.

In modern AI, knowledge representation and logical reasoning are used when a system must follow explicit rules, satisfy constraints, or justify its conclusions. For example, a planning system can represent action preconditions and effects, then check whether a proposed sequence of actions achieves a goal. A neural model can recognise objects or suggest solutions, while a symbolic reasoning component checks what follows from the available facts and rules. Google DeepMind’s AlphaGeometry illustrates this combination: a neural language model proposes useful geometric constructions, and a symbolic deduction engine develops proofs. Its reasoning uses richer mathematical representations than basic propositional logic, but follows the same principle of deriving conclusions from explicit knowledge. These methods are especially useful when correctness and traceability matter; their conclusions still depend on the accuracy of the facts and rules supplied.

flowchart TD
  L["Logic"] --> PL["Propositional<br/>Logic"]
  L --> PDL["Predicate Logic<br/>(First-Order Logic)"]

  PL --> PROP["Propositions<br/>True or False"]
  PL --> INF["Inference"]

  INF --> TT["Truth Table<br/>Entailment"]
  INF --> TP["Theorem<br/>Proving"]

  TP --> PC["Proof by<br/>Contradiction"]
  TP --> RES["Resolution<br/>using CNF"]

  PDL --> OBJ["Objects and<br/>Predicates"]
  PDL --> VAR["Variables"]
  PDL --> Q["Quantifiers<br/>forall / exists"]

  style L fill:#90CAF9,stroke:#1E88E5,color:#000

  style PL fill:#CE93D8,stroke:#8E24AA,color:#000
  style PDL fill:#CE93D8,stroke:#8E24AA,color:#000
  style INF fill:#CE93D8,stroke:#8E24AA,color:#000

  style PROP fill:#C8E6C9,stroke:#2E7D32,color:#000
  style TT fill:#C8E6C9,stroke:#2E7D32,color:#000
  style TP fill:#C8E6C9,stroke:#2E7D32,color:#000
  style PC fill:#C8E6C9,stroke:#2E7D32,color:#000
  style RES fill:#C8E6C9,stroke:#2E7D32,color:#000
  style OBJ fill:#C8E6C9,stroke:#2E7D32,color:#000
  style VAR fill:#C8E6C9,stroke:#2E7D32,color:#000
  style Q fill:#C8E6C9,stroke:#2E7D32,color:#000

Learning Objectives #

• distinguish facts, rules, queries and inferred conclusions
• explain how TELL and ASK support a knowledge-based agent
• interpret propositional symbols, connectives and truth assignments
• formulate rules for breeze, stench and safe locations
• combine successive observations to infer hazards before entering a square
• test entailment using the models that satisfy a knowledge base
• apply equivalence laws and inference rules to prove a query
• convert propositional sentences into conjunctive normal form
• prove entailment through resolution refutation
• distinguish resolution from DPLL satisfiability checking

Big Picture #

flowchart TD
    P["Current percept"] --> T["TELL: add facts"]
    R["Rules about the world"] --> K["Knowledge base"]
    T --> K
    K --> I["Logical inference"]
    Q["ASK: action query"] --> I
    I --> A["Select and record action"]
    A --> E["Execute action"]
    E --> P

    style P fill:#E1F5FE
    style T fill:#C8E6C9
    style R fill:#EDE7F6
    style K fill:#E1F5FE
    style I fill:#FFF9C4
    style Q fill:#EDE7F6
    style A fill:#C8E6C9
    style E fill:#E1F5FE

1. Knowledge, Facts and Rules #

A knowledge base, usually written as KB, is a collection of sentences expressed in a knowledge representation language. These sentences describe what the agent knows about the world and the relationships it can use to derive further information.

Some sentences are accepted as starting assumptions or axioms. Other sentences are obtained through observation or inferred from earlier knowledge.

Why store knowledge? #

Suppose an agent has found and verified a shortest route between two locations. Storing the route avoids repeating the same search when the environment is unchanged. If a new road appears, the agent must update its knowledge before relying on the stored route.

A knowledge base supports more than retrieval. It also allows the agent to combine facts and rules to answer a question whose answer was never stored directly.

The agent may know that no breeze is present in its current square without having visited the neighbouring squares. A rule connecting breeze to pits lets it infer something about those unvisited squares.

2. Knowledge-Based Agents: TELL and ASK ☆ #

A knowledge-based agent combines perception, stored knowledge, inference and action.

TELL #

TELL adds a sentence to the knowledge base. The sentence might describe a newly observed percept, an initial condition or an action the agent has selected.

ASK #

ASK queries the knowledge base. The inference procedure determines what follows from the stored sentences and uses that information to support a decision.

Agent cycle #

1. Receive a percept from the environment.
2. TELL the knowledge base what was perceived.
3. ASK which action should be performed.
4. TELL the knowledge base which action was selected.
5. Execute the action and receive the next percept.

When facts can change over time, their time or state must be represented appropriately. Recording that an action was selected does not by itself establish that every intended outcome occurred.

3. Propositional Logic: Language and Meaning #

Propositional logic represents statements that are either true or false. Compound sentences are built by joining simpler statements with logical connectives.

flowchart TD
    PL["Propositional Logic"] --> INF["Inference"]
    INF --> TT["Truth Table<br/>Entailment"]
    INF --> TP["Theorem<br/>Proving"]

    TP --> PC["Proof by<br/>Contradiction"]
    TP --> RES["Resolution<br/>using CNF"]

style PL fill:#90CAF9,stroke:#1E88E5,color:#000
style INF fill:#CE93D8,stroke:#8E24AA,color:#000
style TT fill:#C8E6C9,stroke:#2E7D32,color:#000
style TP fill:#C8E6C9,stroke:#2E7D32,color:#000
style PC fill:#C8E6C9,stroke:#2E7D32,color:#000
style RES fill:#C8E6C9,stroke:#2E7D32,color:#000

Basic terminology #

A unit clause contains one literal, such as \( \neg P_{1,1} \) .

A question such as “Where is the pit?” is not itself a proposition. To query an agent, formulate a sentence whose truth can be tested, such as “There is no pit at (1,2).”

Syntax and semantics #

• Syntax specifies which expressions are well formed.
• Semantics specifies when an expression is true in a model.

The sentence \( P_{1,2}\lor P_{2,1} \) is true in a model where either symbol is true, including a model where both are true.

4. Logical Connectives ☆ #

Truth table #

Understanding implication #

The implication \( P\Rightarrow Q \) is false only when P is true and Q is false. It places a requirement on cases where P holds.

For example, “If there is a pit here, neighbouring squares have breeze” does not say that the absence of this particular pit removes every possible cause of breeze.

Precedence #

The usual order is negation, conjunction, disjunction, implication, then biconditional. Use parentheses whenever the intended grouping could be unclear.

5. Wumpus World: A Logical Agent’s Environment #

Wumpus World is a four-by-four grid containing pits, a Wumpus and gold. The agent starts safely at (1,1), initially facing right. The locations of the hazards and gold are hidden from the agent.

The objective is to obtain the gold and leave through the starting square while avoiding death and unnecessary actions.

Example layout #

The layout below is used in the worked example. The x-coordinate increases to the right and the y-coordinate increases upwards. The agent discovers the hidden locations through local percepts.

PEAS description #

Actions #

For example, an agent at (2,1) facing east must turn left and then move forward to reach (2,2). Turning alone changes orientation, not position.

Percepts #

Diagonal squares are not adjacent for these warning rules. The safety deductions below concern the world before the Wumpus is killed.

Task environment #

Random placement at the beginning does not make the subsequent action model stochastic. A deterministic transition can still have an outcome the agent cannot predict fully because it does not know the complete state.

6. Representing Wumpus World with Logic ☆ #

Symbols #

Gold, glitter, visited locations and safe locations can also be recorded. The deductions here concentrate on pits and the Wumpus.

Neighbourhood rules #

Let \( N(x,y) \) be the set of valid orthogonally adjacent squares. Exclude coordinates outside the grid.

A breeze is present exactly when at least one neighbouring square contains a pit:

The corresponding Wumpus rule is:

These expressions are templates for generating propositional sentences for each valid square.

Positive and negative observations #

If breeze is present, at least one neighbouring square has a pit. If breeze is absent, every neighbouring square is pit-free:

Similarly:

A pit causes breeze in its valid neighbouring squares. However, another pit may also cause breeze in those squares. Establishing that one square is pit-free therefore does not establish that its neighbours have no breeze.

Absence of breeze describes neighbouring pits, not whether the current square contains a pit. The safety of the starting square is supplied as an initial condition.

Safe and visited are different #

Before the Wumpus is killed, a location is safe when it contains neither a pit nor the Wumpus:

A square can be known to be safe before it has been visited. A safe square may still contain breeze or stench because these warn about adjacent hazards.

7. Worked Wumpus Deductions ☆ #

Use only the observations available to the agent at each stage. A complete diagram may reveal the true world to the reader, but those hidden locations are not automatically facts in the agent’s KB.

Observation 1: no breeze and no stench at (1,1) #

The valid neighbours are (1,2) and (2,1).

Both neighbours are safe. The agent chooses to visit (2,1).

Observation 2: breeze and no stench at (2,1) #

Breeze gives three possible pit locations:

The starting square is already known to be pit-free. Combining that fact with the disjunction gives:

At least one candidate contains a pit; both remain possible. The agent cannot yet identify which candidate is pit-free.

No stench establishes:

The agent can return to (1,1) and explore the known safe square (1,2). Backtracking provides new information without entering an unresolved hazard location.

Observation 3: stench and no breeze at (1,2) #

No breeze establishes:

Combining \( \neg P_{2,2} \) with the earlier \( P_{2,2}\lor P_{3,1} \) identifies a pit at (3,1).

Stench gives:

Earlier knowledge excludes a Wumpus at (1,1) and (2,2), leaving:

Location (2,2) is now known to be both pit-free and Wumpus-free.

Observation 4: no breeze and no stench at (2,2) #

Its neighbours are (1,2), (2,1), (2,3) and (3,2). The first two are visited; the last two are unvisited.

The negative percepts establish that (2,3) and (3,2) are safe. In this world, visiting (2,3) produces glitter, allowing the agent to grab the gold and return through known safe squares to climb out at (1,1).

What the agent has achieved #

Combine current percepts with earlier facts. A conclusion about an unvisited square can become certain even when no single observation establishes it alone.

8. Entailment and Truth-Table Inference ☆ #

Entailment asks whether a conclusion must be true whenever the knowledge base is true.

Here, \( M(KB) \) is the set of models satisfying every sentence in the KB.

A five-sentence knowledge base #

Consider a KB restricted to information associated with the first two observations:

The query is:

TT-Entail procedure #

1. Collect the distinct symbols appearing in the KB and query.
2. Enumerate their possible True/False assignments.
3. Evaluate every KB sentence under each assignment.
4. Keep only assignments where all KB sentences are true.
5. Check whether the query is true in every retained model.

For \( n \) distinct symbols:

This KB contains seven distinct symbols, so there are \( 2^7=128 \) assignments.

The three satisfying models #

Every satisfying model has:

The remaining choices are:

The query is true in all three, so:

The same KB entails \( \neg P_{2,1} \) and \( P_{2,2}\lor P_{3,1} \) .

True, false and undetermined #

For a consistent KB:

In the five-sentence KB, \( P_{2,2} \) is undetermined. The later no-breeze observation at (1,2) supplies additional information and eliminates models containing that pit.

Truth in two of three models does not establish a probability of two-thirds. Logical entailment does not assign probabilities to models.

Computational cost #

The assignment count grows exponentially. Five symbols produce 32 assignments, ten produce 1024, and twenty produce 1,048,576.

If evaluating the KB costs \( O(m) \) for sentence size \( m \) , straightforward enumeration takes \( O(m2^n) \) time. The commonly stated \( O(2^n) \) highlights the exponential dependence on symbol count.

A depth-first implementation can evaluate one assignment at a time using \( O(n) \) additional assignment/recursion space, excluding the stored input. Storing a complete truth table requires much more space.

9. Theorem Proving and Inference Rules ☆ #

Theorem proving derives a conclusion by applying sound rules to existing sentences. A proof is a sequence of justified steps, each based on what is already available.

Useful logical equivalences #

Commutativity allows the order of AND/OR operands to change. Associativity allows regrouping of consecutive ANDs or consecutive ORs. Neither permits exchanging AND with OR.

Modus ponens #

If a premise is known to be true and a rule says that it implies a conclusion, infer that conclusion:

AND elimination #

If a conjunction is true, each of its components is true:

Direct proof of the Wumpus query #

Start with \( R_2 \) because it relates the query’s pit symbol to an observed breeze symbol. Split the biconditional into its two implications, then select the direction connecting the possible pits to breeze.

The query follows without constructing 128 truth-table rows.

Choosing a useful next step #

Look for a sentence containing the query symbol and connect it to facts already known. Here, the useful known fact is no breeze at (1,1). The biconditional provides a relationship in both directions; contraposition then produces a rule whose premise matches that negative fact.

Rule selection is a search problem. Applying a sound rule preserves validity, but applying irrelevant rules may not move the proof towards its goal.

10. Conjunctive Normal Form ☆ #

Conjunctive normal form, or CNF, is an AND of clauses, where each clause is an OR of literals.

This expression contains three clauses. The last clause is a unit clause.

Conversion procedure #

1. Eliminate biconditionals.
2. Replace implications using implication elimination.
3. Push negations inward using De Morgan’s laws and double negation.
4. Distribute OR over AND.
5. Separate the resulting conjunction into clauses.

Worked conversion of R2 #

Start with:

Eliminate the biconditional:

Eliminate implications:

Apply De Morgan’s law to the second part, then distribute OR over AND:

Complete clause set for the five-sentence KB #

The clauses are jointly required: the KB is their conjunction.

11. Proof by Contradiction and Resolution ☆ #

Proof by contradiction tests whether the knowledge base can remain true when the query is assumed false.

The extra sentence is a temporary assumption for the proof. It is not a new observation about the environment.

Resolution rule #

Resolution combines two clauses containing complementary literals:

Here, A and B stand for the remaining disjunctions. The complementary literal is removed, and the remaining literals form the resolvent.

Unit resolution #

When one parent clause is a unit clause:

Wumpus resolution proof #

The query is \( \neg P_{1,2} \) , so add its negation, \( P_{1,2} \) , to the CNF clause set.

The empty clause \( \Box \) contains no literals and is always false. Deriving it establishes that the KB and negated query cannot all be satisfied together.

Therefore, the KB entails \( \neg P_{1,2} \) .

A second resolution example #

Let:

Prove \( \neg C \) by adding \( C \) :

The negated query is inconsistent with the KB, so \( KB\models\neg C \) .

Interpreting the result #

• Unsatisfiability of \( KB\land\neg q \) establishes entailment.
• A satisfying model of \( KB\land\neg q \) is a counterexample, establishing that q is not entailed.
• A counterexample does not establish that the KB entails the opposite query.
• Failure to find a contradiction during an unfinished search is not a conclusion about entailment.

12. DPLL: Satisfiability Checking #

The Davis-Putnam-Logemann-Loveland algorithm, or DPLL, is a complete backtracking procedure for deciding whether a propositional CNF formula is satisfiable.

It searches over truth assignments and uses three improvements:

DPLL can test entailment by checking satisfiability of \( KB\land\neg q \) . An unsatisfiable result establishes \( KB\models q \) .

Resolution derives clauses. DPLL principally searches for a model, using unit propagation and backtracking to reduce the work.

13. Consistency and a Recommendation Example #

Logical reasoning depends on how the information is represented and whether the supplied facts can hold together.

Representing a fixed customer #

Suppose the rules are:

Their CNF is:

Given E, repeated modus ponens derives T, then L, then R. The customer receives recommendations under these rules.

One satisfying assignment to these four rules with E true is:

An assignment with X true also satisfies the rules. Tech-savviness alone does not determine whether this customer makes expensive purchases.

Statements about a population #

“Not all tech-savvy customers make expensive purchases” means that at least one tech-savvy customer does not make expensive purchases. It leaves open whether other tech-savvy customers make expensive purchases.

Representing this claim requires identifying customers explicitly or using a language with quantifiers. A proposition about one arbitrary customer does not automatically express a claim about the whole population.

Checking for inconsistent facts #

If E and \( \neg T \) are both supplied, the rule \( E\Rightarrow T \) derives T, producing a contradiction.

The inconsistency exists independently of any recommendation query. In classical logic, an inconsistent KB has no satisfying models and formally entails every sentence. A useful decision system must therefore resolve the conflicting facts or assumptions before interpreting its conclusions.

Propositional reasoning establishes logical consequences. A numerical likelihood requires a probabilistic model in addition to these logical rules.

14. Comparing Propositional Inference Methods #

All these approaches can be implemented in an automated reasoning system.

Strengths and limits of propositional logic #

Propositional logic is declarative: sentences describe what holds in the world. It supports negative information and alternatives, such as “a pit is in one of these two squares,” without requiring an immediate choice.

Its expressive power is limited. Separate symbols and sentences are needed for particular locations or individuals. General statements about all objects or some object motivate predicate logic and quantifiers.

Practical Exploration #

The following Python example checks the five-sentence Wumpus KB. Each iteration represents one complete truth assignment.

from itertools import product

satisfying_models = []

for P11, B11, P12, P21, B21, P22, P31 in product(
    (False, True), repeat=7
):
    sentences = [
        not P11,
        B11 == (P12 or P21),
        B21 == (P11 or P22 or P31),
        not B11,
        B21,
    ]

    if all(sentences):
        satisfying_models.append({
            "P22": P22,
            "P31": P31,
            "query_not_P12": not P12,
        })

print("Satisfying models:", len(satisfying_models))
for model in satisfying_models:
    print(model)

The output contains three models, and the query is true in all three. This demonstrates the distinction between generating a candidate assignment and accepting it as a model of the KB.

Practice Questions #

1. What is the difference between a fact, a rule and an inferred conclusion?
2. An agent detects no breeze at (2,2). Which locations can it identify as pit-free?
3. How many truth assignments exist for five distinct propositional symbols?
4. Does the five-sentence Wumpus KB entail that there is a pit at (2,2)?
5. Convert \( A\Rightarrow(B\lor C) \) into CNF.
6. Given \( A\lor B \) and \( \neg A \) , identify the resolvent.

Short Answers #

1. A fact is available information; a rule links statements; an inferred conclusion follows by applying rules to existing information.
2. The valid neighbours (1,2), (2,1), (2,3) and (3,2). The observation alone does not establish the current square’s pit status.
3. \( 2^5=32 \) .
4. No. Some KB-satisfying models contain that pit and others do not, so its presence is undetermined.
5. \( \neg A\lor B\lor C \) , which is already a single CNF clause.
6. B, obtained by unit resolution.

Key Takeaways #

• A knowledge-based agent combines observations with rules to derive useful conclusions.
• Negative warning percepts can establish the safety of unvisited neighbouring squares.
• Entailment requires truth in every model satisfying the KB.
• An undetermined statement is not automatically false.
• CNF is a conjunction of disjunctions of literals.
• Resolution refutation proves a query by making its negation inconsistent with the KB.
• DPLL searches for satisfying assignments using propagation and backtracking.

Checklist #

• I can distinguish facts, rules, literals, clauses and models.
• I can explain the TELL/ASK agent cycle.
• I can formulate valid neighbouring-square rules.
• I can infer safe squares from successive percepts.
• I can distinguish entailment, negation entailment and uncertainty.
• I can convert a biconditional into CNF.
• I can show a resolution proof ending in an empty clause.
• I can explain the purpose and three main improvements of DPLL.

References #

• Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, 4th edition, Chapters 7 and 8.
• UC Berkeley CS188, Propositional Logic and Propositional Logical Inference.

Home | Artificial and Computational Intelligence