Lecture 8: Logic in Artificial Intelligence

Author

Your Name

Published

February 10, 2025

Introduction

Course and Lecture Overview

Welcome to Lecture 8 of Artificial Intelligence. Today’s topic is the application of logic in AI systems to construct intelligent agents. We will continue our discussion from the previous lecture, aiming to complete the section on propositional logic today. In the next lecture, we will transition to first-order logic, a more expressive and powerful logical system.

Please note the upcoming schedule adjustment: there will be no lectures during the week of Easter Monday and the subsequent Tuesday. Lectures will resume the week after. Further details regarding the lecture schedule for lectures 9, 10, 11, and 12 will be announced later. For now, please be aware that lectures will recommence in the week following the week after Easter.

Knowledge-Based Agents and Logic

This course explores the construction of intelligent agents that are knowledge-based. A core concept in this approach is the explicit representation of knowledge within the agent. This knowledge is stored in a structure called a knowledge base (). The can be thought of as a specialized database designed to hold knowledge rather than raw data. While drawing a definitive line between data and knowledge can be philosophically challenging, for our purposes, the will contain statements and relationships representing an agent’s understanding of its world.

The idea of explicit knowledge representation has been a cornerstone of AI for several decades, particularly from the 1960s through the 1990s. It was the foundational approach behind expert systems, which were among the early successful applications of AI. Expert systems aimed to capture and utilize the knowledge of human experts in specific domains to solve complex problems. This paradigm remains a significant area within AI, and our textbook dedicates a substantial portion to exploring knowledge-based systems and logical reasoning.

In this lecture, we will use the Wumpus World environment as a running example to illustrate the principles of knowledge representation and logical reasoning in agents. This example will help us understand how agents can use logic to make inferences and decisions in a complex and uncertain world.

Reasoning in the Wumpus World

Wumpus World Scenario

The Wumpus World provides a compelling scenario for exploring agent reasoning. Imagine an agent navigating a grid of rooms, each potentially containing a pit, a Wumpus, or gold. The agent’s objective is to find the gold and return to the starting point (square [1,1]) safely.

The agent is equipped with an arrow to potentially defeat the Wumpus and has the following perceptual capabilities:

Location: The agent always knows its current square coordinates.
Stench: The agent perceives a stench in a square if and only if the Wumpus is in an adjacent square (horizontally or vertically).
Breeze: The agent perceives a breeze in a square if and only if at least one adjacent square contains a pit.
Glitter: The agent perceives glitter in a square if and only if gold is in the same square.
Bump: The agent perceives a bump if it attempts to move into a wall.
Scream: The agent perceives a scream if it shoots and kills the Wumpus.

Entering a square with a pit or a live Wumpus results in immediate death for the agent. The agent starts with a single arrow, which can be used to shoot and potentially kill the Wumpus. The Wumpus, if killed, emits a scream perceptible to the agent.

The Wumpus World is an interesting environment for AI because:

Reasoning is crucial: Blindly exploring the world can be fatal. The agent must reason about its perceptions to infer the locations of dangers and the gold.
Inference is necessary: The agent needs to deduce properties of unvisited squares based on perceptions in visited squares. For example, perceiving a breeze in one square implies the possibility of a pit in a neighboring square. Conversely, not perceiving a breeze in a safe square can imply the absence of pits in adjacent unvisited squares.
Search alone is insufficient: While search algorithms can be used for path planning, they are ineffective without incorporating reasoning. Randomly trying actions without considering perceptions and making inferences can quickly lead to the agent’s demise.

As an exercise, consider the dimensions of the task environment in the Wumpus World. What are the performance measures, environment, actuators, and sensors (PEAS)?

Let’s examine a step-by-step example of how an intelligent agent might reason in the Wumpus World.

Agent’s Reasoning Process: A Walkthrough

Consider an agent starting in square [1,1]. We will trace its reasoning as it explores the initial part of the Wumpus World.

Initial State: Square [1,1]

The agent begins in square [1,1]. By the rules of the game setup, square [1,1] is guaranteed to be safe, meaning it contains neither a pit nor a Wumpus.

Perception in [1,1]: The agent perceives nothing – no breeze, no stench, no glitter.

Inference from [1,1] Perception: Since there is no breeze in [1,1], the agent can infer that the squares adjacent to [1,1], namely [1,2] and [2,1], are safe from pits. Similarly, the absence of stench in [1,1] implies that adjacent squares [1,2] and [2,1] are safe from the Wumpus. Therefore, based on the lack of perceptions in [1,1], the agent can deduce that both [1,2] and [2,1] are safe to explore. We can mark these squares as ‘OK’.

Decision: The agent can choose to move to either [1,2] or [2,1] as both are inferred to be safe. Let’s assume the agent decides to move to [2,1].

Moving to Square [2,1]

The agent moves to square [2,1].

Perception in [2,1]: Upon entering [2,1], the agent perceives a breeze.

Inference from [2,1] Breeze Perception: Perceiving a breeze in [2,1] indicates that there must be a pit in at least one adjacent square. The squares adjacent to [2,1] are [1,1], [2,2], [3,1], and [2,0] (which is outside the grid, hence invalid). Since [1,1] is already known to be safe, the pit must be in either [2,2] or [3,1] or both. Therefore, squares [2,2] and [3,1] are potentially dangerous (unsafe) due to the possible presence of a pit. The agent should avoid moving directly into [2,2] or [3,1] without further information.

Considering Safe Alternatives: The agent recalls that square [1,2] was previously inferred to be safe from the initial perception in [1,1]. Thus, [1,2] remains a viable and safe square to explore.

Planning a Path to [1,2]: To move from [2,1] to [1,2], assuming the agent is initially facing right (East), it needs to execute a sequence of actions. For example: Turn Right (face South), Turn Right again (face West - 180° turn), Move Forward (to [2,1]), Turn Right (face North), Move Forward (to [1,2]). This path planning aspect can utilize search algorithms discussed in previous lectures to determine the sequence of actions required to reach a desired location.

Moving to Square [1,2]

The agent executes the plan and moves to square [1,2].

Perception in [1,2]: In square [1,2], the agent perceives a stench.

Inference from [1,2] Stench Perception and Prior Knowledge: Perceiving a stench in [1,2] means there is a Wumpus in an adjacent square. Adjacent squares are [1,1], [1,3], [2,2], and [0,2] (invalid). However, the agent remembers that it did not perceive a stench in [1,1]. This is crucial prior knowledge. Since there was no stench in [1,1], and stench indicates a Wumpus in an adjacent square, the Wumpus cannot be in [2,1] or [1,2] (as these are adjacent to [1,1]).

Combining the current perception of stench in [1,2] with the prior knowledge of no stench in [1,1], the agent can deduce that the Wumpus must be in [1,3] or [2,2] (or both, though there is only one Wumpus in the game).

Furthermore, the agent perceives no breeze in [1,2]. This absence of breeze in [1,2] implies that there are no pits in the squares adjacent to [1,2], excluding the already visited squares [1,1] and [2,1]. Therefore, based on the no-breeze perception in [1,2], squares [1,3] and [2,2] are inferred to be safe from pits.

Combined Inference for [1,3] and [2,2]: From the stench in [1,2], we know a Wumpus is in [1,3] or [2,2]. From the no-breeze in [1,2], we know there are no pits in [1,3] or [2,2]. Thus, squares [1,3] and [2,2] are potentially unsafe due to the Wumpus but are safe from pits.

Continuing Exploration and Gold Acquisition

The agent can continue this process of perception, inference, and planning to explore further. For instance, moving to [1,3] (if safe) and perceiving glitter would indicate the presence of gold. Upon finding the gold, the agent’s goal shifts to returning safely to [1,1] and then climbing out of the Wumpus World, ideally without encountering the Wumpus or falling into a pit. The return path would involve retracing steps through squares that have been visited and deemed safe, effectively utilizing the knowledge accumulated during exploration.

This step-by-step example demonstrates how an agent can use logical reasoning to navigate the Wumpus World, making informed decisions based on its perceptions and prior knowledge. In the following sections, we will formalize these reasoning processes using propositional logic.

Fundamentals of Propositional Logic

Syntax and Semantics of Propositional Logic

Logic serves as a formal tool for knowledge representation and reasoning, tracing its origins back to ancient philosophers like Aristotle. In the realm of Artificial Intelligence, we employ logic to articulate the content within a knowledge base, enabling intelligent agents to deduce implicit knowledge from explicitly stated facts. For instance, given the statements "There is no breeze in square (1,1)" and "If there is no breeze in square (1,1), then there is no pit in square (1,2)", an agent should logically infer "There is no pit in square (1,2)". This inference relies on established rules of deduction, such as Modus Ponens.

When defining a logical system, it is essential to specify its syntax and semantics.

Definition 1 (Syntax of Propositional Logic). The syntax of propositional logic dictates the rules for constructing valid sentences, also known as formulas. It comprises:

Propositional Symbols: These are atomic symbols, often represented by uppercase letters (e.g., $P, Q, R$), that stand for basic propositions or statements which can be either true or false.
Logical Connectives: These symbols are used to combine propositional symbols and form compound formulas. The fundamental connectives are:
- Negation ($\neg$ or $\lnot$): A unary connective that reverses the truth value of a proposition. If $P$ is true, $\neg P$ is false, and vice versa.
- Conjunction ($\land$): A binary connective that is true if and only if both connected propositions are true. $P \land Q$ is true only when both $P$ and $Q$ are true.
- Disjunction ($\lor$): A binary connective that is true if at least one of the connected propositions is true. $P \lor Q$ is true if $P$ is true, or $Q$ is true, or both are true.
- Implication ($\implies$ or $\rightarrow$): A binary connective representing conditional statements. $P \implies Q$ is false only when $P$ is true and $Q$ is false; in all other cases, it is true. It reads as "If $P$, then $Q$".
- Biconditional ($\iff$ or $\leftrightarrow$): A binary connective that is true if both connected propositions have the same truth value. $P \iff Q$ is true if both $P$ and $Q$ are true, or if both are false. It reads as "$P$ if and only if $Q$".
Parentheses: Used to group parts of formulas and specify the order of operations, ensuring unambiguous parsing of complex sentences.

Well-formed formulas are constructed recursively:

Every propositional symbol is a well-formed formula.
If $\alpha$ is a well-formed formula, then $\neg \alpha$ is a well-formed formula.
If $\alpha$ and $\beta$ are well-formed formulas, then $(\alpha \land \beta)$, $(\alpha \lor \beta)$, $(\alpha \implies \beta)$, and $(\alpha \iff \beta)$ are well-formed formulas.
Nothing else is a well-formed formula.

Definition 2 (Semantics of Propositional Logic). The semantics of propositional logic defines how to interpret formulas and determine their truth value. It is based on the concept of possible worlds or models.

Possible Worlds (Models): In propositional logic, a possible world is an assignment of truth values (true or false) to each propositional symbol. If there are $n$ propositional symbols, there are $2^n$ possible worlds. Each possible world represents a complete specification of the truth values for all propositions under consideration.
Interpretation Function: The semantics is formally defined by an interpretation function that assigns a truth value (true or false) to each well-formed formula in each possible world. This assignment is based on the truth values of the propositional symbols and the semantics of the logical connectives.

The truth value of a compound formula is determined recursively:

$\neg \alpha$ is true in a world $m$ if and only if $\alpha$ is false in $m$.
$\alpha \land \beta$ is true in a world $m$ if and only if $\alpha$ is true in $m$ and $\beta$ is true in $m$.
$\alpha \lor \beta$ is true in a world $m$ if and only if $\alpha$ is true in $m$ or $\beta$ is true in $m$ (or both).
$\alpha \implies \beta$ is true in a world $m$ if and only if $\alpha$ is false in $m$ or $\beta$ is true in $m$ (or both). Equivalently, it is false only when $\alpha$ is true and $\beta$ is false.
$\alpha \iff \beta$ is true in a world $m$ if and only if $\alpha$ and $\beta$ have the same truth value in $m$.

To illustrate, consider the formula $P \lor (\neg Q \land R)$. To evaluate its truth value in a specific world, we need to know the truth values of $P$, $Q$, and $R$ in that world. For example, if in a world $m$, $P$ is false, $Q$ is true, and $R$ is true, we evaluate as follows:

$\neg Q$ is false (since $Q$ is true).
$\neg Q \land R$ is false (since $\neg Q$ is false).
$P \lor (\neg Q \land R)$ is false (since both $P$ and $(\neg Q \land R)$ are false).

Thus, the formula $P \lor (\neg Q \land R)$ is false in the world $m$ where $P$ is false, $Q$ is true, and $R$ is true.

We can conceptualize syntax and semantics as residing in distinct yet interconnected domains: Syntax Land and Semantics Land, as depicted in 1. Syntax Land is concerned with the formal structure of logical sentences, while Semantics Land deals with their meaning and truth in relation to the world. The bridge between these two lands is provided by the concepts of entailment and inference, ensuring that syntactic manipulations are sound with respect to semantic interpretations.

Syntax Land and Semantics Land: Bridging the gap between formal expressions and their meanings.

Propositional logic, often a starting point in the study of logic and computation, provides a simple yet powerful foundation for representing and reasoning with declarative knowledge.

Logical Entailment and Inference

Definition 3 (Logical Entailment).

Logical entailment is a central concept in logic that formalizes the idea of logical consequence. A sentence $\alpha$ logically entails a sentence $\beta$, denoted as $\alpha \vDash\beta$, if and only if for every possible world (model) in which $\alpha$ is true, $\beta$ is also true. Formally, for all models $m$, if $m \models \alpha$, then $m \models \beta$.

Entailment signifies that $\beta$ is a logical consequence of $\alpha$; whenever $\alpha$ holds, $\beta$ must also hold. In terms of possible worlds, the set of worlds in which $\alpha$ is true is a subset of the worlds in which $\beta$ is true.

Example 1.

Consider $\alpha = A$ and $\beta = A \lor B$. We want to check if $A \vDash A \lor B$. In any world where $A$ is true, $A \lor B$ is also true, regardless of the truth value of $B$. Therefore, $A \vDash A \lor B$.

Now consider $\alpha = A \land B$ and $\beta = A$. We want to check if $A \land B \vDash A$. In any world where $A \land B$ is true, both $A$ and $B$ must be true. Thus, $A$ is necessarily true. Therefore, $A \land B \vDash A$.

To establish entailment $\alpha \vDash\beta$, we can employ different methods.

Methods for Determining Entailment

There are two primary approaches to determine if $\alpha \vDash\beta$: model checking and theorem proving.

Model Checking:
- Direct Semantic Verification: Model checking involves a direct examination of the semantics. To verify if $\alpha \vDash\beta$, we enumerate all possible worlds (models). For each world in which $\alpha$ is true, we check if $\beta$ is also true. If $\beta$ is true in all such worlds, then $\alpha \vDash\beta$.
- Feasibility for Propositional Logic: For propositional logic, model checking is a decidable procedure because the number of possible worlds is finite ($2^n$ for $n$ propositional symbols). We can systematically check all truth assignments.
- Computational Cost: While complete, model checking can be computationally expensive for a large number of propositional symbols, as the number of models grows exponentially.
- Example in Wumpus World: In the Wumpus World example, to check if "Breeze in (2,1)" entails "Pit in (2,2) or Pit in (3,1)", we would consider all possible configurations of pits in squares (2,2) and (3,1) in worlds where there is a breeze in (2,1) and verify if in all such worlds, there is indeed a pit in (2,2) or (3,1).
Theorem Proving (Syntactic Inference):
- Syntactic Derivation: Theorem proving focuses on manipulating formulas based on syntactic rules to derive new formulas. To show $\alpha \vDash\beta$, we aim to find a sequence of inference steps that starts with $\alpha$ and derives $\beta$.
- Inference Rules: We use a set of inference rules, which are sound patterns of derivation. Applying these rules guarantees that if we derive $\beta$ from $\alpha$, then $\alpha$ indeed entails $\beta$.
- Soundness and Completeness: A set of inference rules is sound if every derived conclusion is logically entailed. It is complete if every entailed conclusion can be derived. For propositional logic, there exist inference systems that are both sound and complete.
- Abstraction from Models: Theorem proving operates in the "Syntax Land," manipulating symbols and formulas without explicit reference to possible worlds. This can be more efficient and abstract than model checking, especially for complex logical systems.

Fundamental Inference Rules in Propositional Logic

Inference rules are the building blocks of theorem proving. They provide a way to syntactically derive new sentences from existing ones, ensuring that the derivation is logically sound. Some key inference rules in propositional logic are summarized below:

Theorem 1 (Modus Ponens).

\[\frac{\alpha, \quad \alpha \implies \beta}{\beta}\] If we know $\alpha$ is true, and $\alpha$ implies $\beta$, we can infer $\beta$.**

Example 2.

Given: "It is raining" and "If it is raining, then the street is wet." Inference: "The street is wet."

Theorem 2 (And-Elimination).

\[\frac{\alpha \land \beta}{\alpha} \quad \text{and} \quad \frac{\alpha \land \beta}{\beta}\] If we know $\alpha$ and $\beta$ is true, we can infer $\alpha$ is true, and we can infer $\beta$ is true.**

Example 3.

Given: "It is raining and the street is wet." Inference 1: "It is raining." Inference 2: "The street is wet."

Theorem 3 (Or-Introduction).

\[\frac{\alpha}{\alpha \lor \beta}\] If we know $\alpha$ is true, we can infer that $\alpha$ or $\beta$ is true (for any $\beta$).**

Example 4.

Given: "It is raining." Inference: "It is raining or the sun is shining."

Theorem 4 (Double-Negation Elimination).

\[\frac{\neg (\neg \alpha)}{\alpha}\] If we know it is not the case that $\alpha$ is not true, we can infer $\alpha$ is true.**

Example 5.

Given: "It is not true that it is not raining." Inference: "It is raining."

Theorem 5 (Contraposition).

\[\frac{\alpha \implies \beta}{\neg \beta \implies \neg \alpha}\] If we know $\alpha$ implies $\beta$, we can infer that not $\beta$ implies not $\alpha$.**

Example 6.

Given: "If it is raining, then the street is wet." Inference: "If the street is not wet, then it is not raining."

Theorem 6 (Implication Elimination (Equivalence)).

\[(\alpha \implies \beta) \equiv (\neg \alpha \lor \beta)\] An implication can be rewritten as a disjunction.**

Example 7.

"If it is raining, then the street is wet" is equivalent to "Either it is not raining, or the street is wet (or both)."

Theorem 7 (De Morgan’s Laws (Equivalences)).

Negation of Conjunction: $\neg (\alpha \land \beta) \equiv (\neg \alpha \lor \neg \beta)$
Negation of Disjunction: $\neg (\alpha \lor \beta) \equiv (\neg \alpha \land \neg \beta)$

De Morgan’s Laws provide rules for distributing negation over conjunction and disjunction.

Example 8.

$\neg (P \land Q)$ is equivalent to $(\neg P \lor \neg Q)$. "It is not true that it is raining and cold" is equivalent to "It is not raining or it is not cold (or both)."

Theorem 8 (Commutativity (Equivalences)).

Conjunction: $(\alpha \land \beta) \equiv (\beta \land \alpha)$
Disjunction: $(\alpha \lor \beta) \equiv (\beta \lor \alpha)$

The order of operands does not matter for conjunction and disjunction.

Example 9.

$(P \land Q)$ is equivalent to $(Q \land P)$. "It is raining and cold" is the same as "It is cold and raining."

Theorem 9 (Associativity and Distributivity).

Associativity and distributivity laws also apply to conjunction and disjunction, allowing for flexible manipulation of formulas.

These inference rules are fundamental for building theorem provers and automated reasoning systems. Two important inference procedures are forward chaining and resolution.

Forward Chaining and Resolution Inference Procedures

Remark. Remark 1.

Forward chaining and resolution are valuable inference techniques in propositional logic. Forward chaining is data-driven and derives new facts from known facts. Resolution is refutation-based and proves entailment by showing unsatisfiability.

Forward Chaining:
- Data-Driven Inference: Forward chaining is a data-driven inference method. It starts with the known facts in the knowledge base and applies inference rules to derive new facts. This process continues until no new facts can be derived.
- Algorithm Description: The forward chaining algorithm maintains an agenda of facts to be processed. It iteratively takes a fact from the agenda, applies all relevant inference rules, and adds any newly derived facts back to the agenda and the knowledge base.
- Use Case: Forward chaining is particularly useful for reasoning about the consequences of initial conditions or when we want to compute all possible inferences from a given set of facts and rules.
- Soundness and Completeness: For propositional logic with Modus Ponens as the primary inference rule, forward chaining can be shown to be sound and complete for deriving positive conclusions.
  
  Input: Knowledge Base $\mathcal{KB}$ (set of propositional logic sentences), set of inference rules $R$
  Output: Set of all sentences inferred from $\mathcal{KB}$ using $R$
  
  $Agenda \leftarrow \mathcal{KB}$ $Inferred \leftarrow \mathcal{KB}$ $\alpha \leftarrow \text{Pop}(Agenda)$ $\beta \leftarrow \text{Apply}(rule, \alpha)$ $Inferred \leftarrow Inferred \cup \{\beta\}$ $\text{Push}(\beta, Agenda)$ $Inferred$
  
  Complexity Analysis: In the worst case, forward chaining can explore a large portion of the possible inferences. For propositional logic, it is guaranteed to terminate because there is a finite number of propositional symbols and thus a finite number of possible sentences that can be inferred. However, in complex knowledge bases, the process can still be computationally intensive.
Resolution:

Both forward chaining and resolution are valuable inference techniques in propositional logic, each with its strengths and typical applications in AI systems.

Knowledge Representation Challenges: Time and Frame Problem

Temporal Aspects of Knowledge in Dynamic Systems

When we apply propositional logic to model real-world scenarios, especially dynamic environments like the Wumpus World, we quickly realize the necessity of incorporating time. The propositional logic we’ve discussed so far is static; it lacks an explicit way to represent change over time. However, intelligent agents operate in environments that evolve, perceive changes, and perform actions that induce further changes.

Consider the agent’s perception of a ‘stench’ in the Wumpus World. If the agent senses a stench at a particular moment, say time $t$, this perception is only valid at that specific time. If the agent moves to a different square at time $t+1$, the perception of stench from time $t$ might no longer be relevant or accurate in the new location. Therefore, to accurately model dynamic environments, our knowledge representation must account for temporal variations.

One effective approach to handle time in logical representations is to introduce temporal fluents. Instead of using simple propositions like Stench or Breeze, we use predicates that are indexed by time. For instance, we might use Stench(location, time) or Breeze(location, time). Using this notation, Stench(1-1, 4) would assert that "there is a stench in location (1,1) at time 4".

We can broadly classify propositions in dynamic systems into two categories:

Atemporal Propositions (Static): These propositions represent facts that are invariant over time. They describe the unchanging rules and properties of the environment. In the Wumpus World, examples of atemporal propositions include rules like "If there is a pit in a square, then adjacent squares will have a breeze." These rules are always true, regardless of time.
Temporal Fluents (Dynamic): These propositions represent aspects of the world that can change over time. They are used to describe the state of the world at different time points. Examples of temporal fluents in the Wumpus World include:
- Location(agent, location, time): The agent’s position at a given time.
- HasArrow(time): Whether the agent possesses an arrow at a given time.
- WumpusAlive(time): Whether the Wumpus is alive at a given time.
- PerceivesStench(agent, location, time): Whether the agent perceives a stench in a location at a given time.
- FacingDirection(agent, direction, time): The direction the agent is facing at a given time.

By using temporal fluents, we can represent the agent’s perceptions, actions, and the changing state of the Wumpus World at discrete time steps. For example, if the agent perceives a breeze in location (1,1) at time 0, we can add the assertion PerceivesBreeze(agent, 1-1, 0) to our knowledge base.

Furthermore, we need to establish logical connections between perceptions and the actual state of the world at different times. For instance, we can formalize the relationship between perceiving a breeze and the presence of a breeze in the environment with a sentence like: "For all locations XY and times $t$, the agent perceives a breeze in location XY at time $t$ if and only if there is a breeze in location XY at time $t$." This type of rule needs to be defined for all relevant perceptions and environmental properties to create a comprehensive and temporally aware knowledge base.

The Frame Problem: Tracking Non-Changes in Dynamic Worlds

A major challenge in knowledge representation for dynamic environments is the infamous frame problem. This problem arises when we try to describe the effects of actions, particularly in specifying what remains unchanged when an action is performed.

Definition 4 (Frame Problem).

The frame problem is the challenge of efficiently and correctly representing the non-effects of actions in a dynamic world. It is concerned with determining what properties of the world persist or remain unchanged after an action is executed. The difficulty lies in avoiding the explicit and cumbersome enumeration of all these non-effects, which can lead to a combinatorial explosion of axioms, while ensuring that our logical system correctly infers the state of the world after each action.

Consider a simple action in the Wumpus World, such as the agent taking a Forward step. When an agent successfully moves forward, its location changes. However, intuitively, many other aspects of the world should remain the same. For example, whether the agent possesses an arrow, whether the Wumpus is alive, the locations of pits and the Wumpus (unless affected by the action itself, like shooting), and many other fluents should typically not be altered by a simple forward movement. The frame problem is about how to formally and efficiently specify this vast amount of "inertia" or non-change.

Frame Axioms: Explicitly Stating What Doesn’t Change (Inefficient)

One straightforward, albeit inefficient, approach to address the frame problem is to use frame axioms. Frame axioms are logical statements that explicitly assert what remains unchanged when a particular action is performed.

For the action Forward, we might propose frame axioms like:

Arrow Frame Axiom: "If the agent performs Forward at time $t$, then if the agent HasArrow at time $t$, it will also HasArrow at time $t+1$." \[\text{HasArrow}(t) \implies \text{HasArrow}(t+1) \quad \text{after action } \texttt{Forward}(t)\]
Wumpus Alive Frame Axiom: "If the agent performs Forward at time $t$, and if WumpusAlive at time $t$, then WumpusAlive at time $t+1$." \[\text{WumpusAlive}(t) \implies \text{WumpusAlive}(t+1) \quad \text{after action } \texttt{Forward}(t)\]

For every action and every fluent that is not affected by that action, we would need to create a corresponding frame axiom. In a system with $M$ actions and $N$ fluents, this could potentially require up to $M \times N$ frame axioms for each time step. This leads to a significant problem:

Combinatorial Explosion: The number of frame axioms grows rapidly with the number of actions and fluents. For complex environments with many actions and properties, managing and reasoning with this vast number of axioms becomes computationally intractable.
Cumbersome and Unintuitive: Specifying what *doesn’t* change for every action is tedious and counterintuitive. It shifts the focus from describing the actual effects of actions to exhaustively listing their non-effects.
Maintenance Overhead: Adding new actions or fluents requires updating a potentially large set of frame axioms, increasing the complexity of knowledge base maintenance.

Frame axioms, while conceptually simple, lead to a combinatorial explosion and make knowledge representation and reasoning inefficient, especially in complex, dynamic domains. This inefficiency motivated the search for more elegant and scalable solutions to the frame problem.

Successor-State Axioms: Focusing on Change (Efficient)

A more efficient and conceptually cleaner approach to address the frame problem is through the use of successor-state axioms. Instead of explicitly stating what remains unchanged, successor-state axioms focus on defining what causes a fluent to change its truth value from one time step to the next. They directly specify the conditions under which a fluent becomes true or false in the successor state ($t+1$) based on the state at time $t$ and the actions performed at time $t$.

For each fluent $F$, a successor-state axiom has the general form:

\[F(t+1) \iff [\text{Action at } t \text{ caused } F \text{ to become true}] \lor [F(t) \land \neg (\text{Action at } t \text{ caused } F \text{ to become false})]\]

In simpler terms, a fluent $F$ is true at time $t+1$ if and only if either an action at time $t$ made it true, or it was already true at time $t$ and no action at time $t$ made it false (i.e., it persisted from the previous state unless an action explicitly changed it). This formulation elegantly handles the frame problem by concentrating on the conditions that lead to a change in a fluent’s value, implicitly assuming that fluents retain their truth values in the absence of such changes.

Let’s consider successor-state axioms for specific fluents in the Wumpus World:

Successor-State Axiom for HasArrow: \[\text{HasArrow}(t+1) \iff (\text{HasArrow}(t) \land \neg \text{Shoot}(t))\] This axiom states that the agent has an arrow at time $t+1$ if and only if it had an arrow at time $t$ and did not perform the Shoot action at time $t$. This concisely captures the condition under which the agent retains the arrow – persistence unless used. It implicitly handles the frame problem for the HasArrow fluent by only specifying the condition under which it changes (i.e., when shooting).
Successor-State Axiom for Location(1-1) (Simplified Example): Let’s consider a simplified axiom for being in location (1,1) at time $t+1$. Assume actions are Forward, TurnLeft, TurnRight. \[\begin{aligned} \text{Location}(1-1, t+1) \iff & (\text{Location}(1-1, t) \land \neg \text{Forward}(t)) \lor \\ & (\text{Location}(1-2, t) \land \text{FacingDirection}(\text{agent}, \text{South}, t) \land \text{Forward}(t)) \lor \\ & (\text{Location}(2-1, t) \land \text{FacingDirection}(\text{agent}, \text{West}, t) \land \text{Forward}(t)) \end{aligned}\] This axiom states that the agent is at location (1,1) at time $t+1$ if either:
1. It was already at location (1,1) at time $t$ and did not move forward (persistence).
2. It was at location (1,2) at time $t$, was facing South, and moved forward, thus entering (1,1).
3. It was at location (2,1) at time $t$, was facing West, and moved forward, also entering (1,1).
This axiom focuses on the actions that can cause the agent to be in location (1,1) at $t+1$, either by staying put or by moving into it from an adjacent location. It implicitly handles the frame problem for location by only specifying the conditions under which the location changes to (1,1). Locations other than (1,1) would have analogous successor-state axioms. Note that the Bump condition from the transcript example might be relevant in a more complete version to handle cases where the agent attempts to move into a wall, which would prevent a location change despite the Forward action.

Successor-state axioms offer a significant improvement over frame axioms by providing a more concise, modular, and intuitive way to represent change in dynamic environments. They directly address the core of the frame problem by focusing on the causes of change, leading to more efficient and manageable knowledge representation for intelligent agents. By using successor-state axioms, we can build knowledge bases that are both expressive enough to model dynamic worlds and efficient enough for practical reasoning.

Conclusion

In this lecture, we have explored the application of propositional logic as a foundational tool for constructing knowledge-based agents, using the Wumpus World as a practical example. We have systematically covered the core components of propositional logic, including its syntax for constructing logical sentences and its semantics for interpreting their truth values in possible worlds. We examined the concept of logical entailment, which defines logical consequence, and investigated inference rules and procedures like forward chaining and resolution that enable agents to perform automated reasoning. Furthermore, we addressed the significant challenges in knowledge representation for dynamic environments, focusing on the frame problem and introducing successor-state axioms as a more effective solution compared to frame axioms.

Key Takeaways:

While propositional logic offers a valuable starting point and is sufficient for representing and reasoning in relatively simple scenarios, it has inherent limitations, especially when dealing with complex, real-world environments. Propositional logic treats propositions as atomic units and lacks the expressiveness to represent objects, properties of objects, and relations between objects directly. It also struggles with generalization and quantification, which are essential for expressing general rules and dealing with collections of objects.

Looking ahead, the next lecture will introduce first-order logic (FOL), also known as predicate logic. First-order logic significantly expands upon propositional logic by providing:

Objects and Relations: FOL allows us to represent objects, their properties, and relationships between them, offering a much richer and more natural way to describe the world.
Quantification: FOL introduces quantifiers (universal $\forall$ and existential $\exists$) that enable us to make statements about all or some objects in the domain, greatly enhancing expressiveness and the ability to formulate general rules.
Increased Expressiveness and Scalability: With these added capabilities, first-order logic provides a more powerful and flexible framework for knowledge representation and reasoning, capable of handling more complex and scalable AI applications compared to propositional logic.

In the next lecture, we will delve into the syntax and semantics of first-order logic and explore how it addresses the limitations of propositional logic, paving the way for more sophisticated knowledge-based agents. We will see how first-order logic can more naturally and efficiently represent the complexities of environments like the Wumpus World and beyond.

--- title: "Lecture 8: Logic in Artificial Intelligence" author: "Your Name" date: "2025-02-10" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction ## Course and Lecture Overview Welcome to Lecture 8 of Artificial Intelligence. Today's topic is the application of logic in AI systems to construct intelligent agents. We will continue our discussion from the previous lecture, aiming to complete the section on propositional logic today. In the next lecture, we will transition to first-order logic, a more expressive and powerful logical system. Please note the upcoming schedule adjustment: there will be no lectures during the week of Easter Monday and the subsequent Tuesday. Lectures will resume the week after. Further details regarding the lecture schedule for lectures 9, 10, 11, and 12 will be announced later. For now, please be aware that lectures will recommence in the week following the week after Easter. ## Knowledge-Based Agents and Logic This course explores the construction of intelligent agents that are knowledge-based. A core concept in this approach is the explicit representation of knowledge within the agent. This knowledge is stored in a structure called a **knowledge base** (). The can be thought of as a specialized database designed to hold knowledge rather than raw data. While drawing a definitive line between data and knowledge can be philosophically challenging, for our purposes, the will contain statements and relationships representing an agent's understanding of its world. The idea of explicit knowledge representation has been a cornerstone of AI for several decades, particularly from the 1960s through the 1990s. It was the foundational approach behind **expert systems**, which were among the early successful applications of AI. Expert systems aimed to capture and utilize the knowledge of human experts in specific domains to solve complex problems. This paradigm remains a significant area within AI, and our textbook dedicates a substantial portion to exploring knowledge-based systems and logical reasoning. In this lecture, we will use the **Wumpus World** environment as a running example to illustrate the principles of knowledge representation and logical reasoning in agents. This example will help us understand how agents can use logic to make inferences and decisions in a complex and uncertain world. # Reasoning in the Wumpus World ## Wumpus World Scenario The Wumpus World provides a compelling scenario for exploring agent reasoning. Imagine an agent navigating a grid of rooms, each potentially containing a pit, a Wumpus, or gold. The agent's objective is to find the gold and return to the starting point (square \[1,1\]) safely. The agent is equipped with an arrow to potentially defeat the Wumpus and has the following perceptual capabilities: - **Location:** The agent always knows its current square coordinates. - **Stench:** The agent perceives a stench in a square if and only if the Wumpus is in an adjacent square (horizontally or vertically). - **Breeze:** The agent perceives a breeze in a square if and only if at least one adjacent square contains a pit. - **Glitter:** The agent perceives glitter in a square if and only if gold is in the same square. - **Bump:** The agent perceives a bump if it attempts to move into a wall. - **Scream:** The agent perceives a scream if it shoots and kills the Wumpus. Entering a square with a pit or a live Wumpus results in immediate death for the agent. The agent starts with a single arrow, which can be used to shoot and potentially kill the Wumpus. The Wumpus, if killed, emits a scream perceptible to the agent. The Wumpus World is an interesting environment for AI because: - **Reasoning is crucial:** Blindly exploring the world can be fatal. The agent must reason about its perceptions to infer the locations of dangers and the gold. - **Inference is necessary:** The agent needs to deduce properties of unvisited squares based on perceptions in visited squares. For example, perceiving a breeze in one square implies the possibility of a pit in a neighboring square. Conversely, not perceiving a breeze in a safe square can imply the absence of pits in adjacent unvisited squares. - **Search alone is insufficient:** While search algorithms can be used for path planning, they are ineffective without incorporating reasoning. Randomly trying actions without considering perceptions and making inferences can quickly lead to the agent's demise. As an exercise, consider the dimensions of the task environment in the Wumpus World. What are the performance measures, environment, actuators, and sensors (PEAS)? Let's examine a step-by-step example of how an intelligent agent might reason in the Wumpus World. ## Agent's Reasoning Process: A Walkthrough Consider an agent starting in square \[1,1\]. We will trace its reasoning as it explores the initial part of the Wumpus World. ### Initial State: Square \[1,1\] The agent begins in square \[1,1\]. By the rules of the game setup, square \[1,1\] is guaranteed to be safe, meaning it contains neither a pit nor a Wumpus. **Perception in \[1,1\]:** The agent perceives nothing -- no breeze, no stench, no glitter. **Inference from \[1,1\] Perception:** Since there is no breeze in \[1,1\], the agent can infer that the squares adjacent to \[1,1\], namely \[1,2\] and \[2,1\], are **safe from pits**. Similarly, the absence of stench in \[1,1\] implies that adjacent squares \[1,2\] and \[2,1\] are **safe from the Wumpus**. Therefore, based on the lack of perceptions in \[1,1\], the agent can deduce that both \[1,2\] and \[2,1\] are safe to explore. We can mark these squares as 'OK'. **Decision:** The agent can choose to move to either \[1,2\] or \[2,1\] as both are inferred to be safe. Let's assume the agent decides to move to \[2,1\]. ### Moving to Square \[2,1\] The agent moves to square \[2,1\]. **Perception in \[2,1\]:** Upon entering \[2,1\], the agent perceives a **breeze**. **Inference from \[2,1\] Breeze Perception:** Perceiving a breeze in \[2,1\] indicates that there must be a pit in at least one adjacent square. The squares adjacent to \[2,1\] are \[1,1\], \[2,2\], \[3,1\], and \[2,0\] (which is outside the grid, hence invalid). Since \[1,1\] is already known to be safe, the pit must be in either \[2,2\] or \[3,1\] or both. Therefore, squares \[2,2\] and \[3,1\] are potentially dangerous (unsafe) due to the possible presence of a pit. The agent should avoid moving directly into \[2,2\] or \[3,1\] without further information. **Considering Safe Alternatives:** The agent recalls that square \[1,2\] was previously inferred to be safe from the initial perception in \[1,1\]. Thus, \[1,2\] remains a viable and safe square to explore. **Planning a Path to \[1,2\]:** To move from \[2,1\] to \[1,2\], assuming the agent is initially facing right (East), it needs to execute a sequence of actions. For example: Turn Right (face South), Turn Right again (face West - 180° turn), Move Forward (to \[2,1\]), Turn Right (face North), Move Forward (to \[1,2\]). This path planning aspect can utilize search algorithms discussed in previous lectures to determine the sequence of actions required to reach a desired location. ### Moving to Square \[1,2\] The agent executes the plan and moves to square \[1,2\]. **Perception in \[1,2\]:** In square \[1,2\], the agent perceives a **stench**. **Inference from \[1,2\] Stench Perception and Prior Knowledge:** Perceiving a stench in \[1,2\] means there is a Wumpus in an adjacent square. Adjacent squares are \[1,1\], \[1,3\], \[2,2\], and \[0,2\] (invalid). However, the agent remembers that it did **not** perceive a stench in \[1,1\]. This is crucial prior knowledge. Since there was no stench in \[1,1\], and stench indicates a Wumpus in an adjacent square, the Wumpus cannot be in \[2,1\] or \[1,2\] (as these are adjacent to \[1,1\]). Combining the current perception of stench in \[1,2\] with the prior knowledge of no stench in \[1,1\], the agent can deduce that the Wumpus must be in \[1,3\] or \[2,2\] (or both, though there is only one Wumpus in the game). Furthermore, the agent perceives **no breeze** in \[1,2\]. This absence of breeze in \[1,2\] implies that there are no pits in the squares adjacent to \[1,2\], excluding the already visited squares \[1,1\] and \[2,1\]. Therefore, based on the no-breeze perception in \[1,2\], squares \[1,3\] and \[2,2\] are inferred to be **safe from pits**. **Combined Inference for \[1,3\] and \[2,2\]:** From the stench in \[1,2\], we know a Wumpus is in \[1,3\] or \[2,2\]. From the no-breeze in \[1,2\], we know there are no pits in \[1,3\] or \[2,2\]. Thus, squares \[1,3\] and \[2,2\] are potentially unsafe due to the Wumpus but are safe from pits. ### Continuing Exploration and Gold Acquisition The agent can continue this process of perception, inference, and planning to explore further. For instance, moving to \[1,3\] (if safe) and perceiving glitter would indicate the presence of gold. Upon finding the gold, the agent's goal shifts to returning safely to \[1,1\] and then climbing out of the Wumpus World, ideally without encountering the Wumpus or falling into a pit. The return path would involve retracing steps through squares that have been visited and deemed safe, effectively utilizing the knowledge accumulated during exploration. This step-by-step example demonstrates how an agent can use logical reasoning to navigate the Wumpus World, making informed decisions based on its perceptions and prior knowledge. In the following sections, we will formalize these reasoning processes using propositional logic. # Fundamentals of Propositional Logic ## Syntax and Semantics of Propositional Logic Logic serves as a formal tool for knowledge representation and reasoning, tracing its origins back to ancient philosophers like Aristotle. In the realm of Artificial Intelligence, we employ logic to articulate the content within a knowledge base, enabling intelligent agents to deduce implicit knowledge from explicitly stated facts. For instance, given the statements \"There is no breeze in square (1,1)\" and \"If there is no breeze in square (1,1), then there is no pit in square (1,2)\", an agent should logically infer \"There is no pit in square (1,2)\". This inference relies on established rules of deduction, such as Modus Ponens. When defining a logical system, it is essential to specify its **syntax** and **semantics**. ::: definition **Definition 1** (Syntax of Propositional Logic). *The **syntax** of propositional logic dictates the rules for constructing valid sentences, also known as formulas. It comprises:* - ***Propositional Symbols:** These are atomic symbols, often represented by uppercase letters (e.g., $P, Q, R$), that stand for basic propositions or statements which can be either true or false.* - ***Logical Connectives:** These symbols are used to combine propositional symbols and form compound formulas. The fundamental connectives are:* - ***Negation ($\neg$ or $\lnot$)**: A unary connective that reverses the truth value of a proposition. If $P$ is true, $\neg P$ is false, and vice versa.* - ***Conjunction ($\land$)**: A binary connective that is true if and only if both connected propositions are true. $P \land Q$ is true only when both $P$ and $Q$ are true.* - ***Disjunction ($\lor$)**: A binary connective that is true if at least one of the connected propositions is true. $P \lor Q$ is true if $P$ is true, or $Q$ is true, or both are true.* - ***Implication ($\implies$ or $\rightarrow$)**: A binary connective representing conditional statements. $P \implies Q$ is false only when $P$ is true and $Q$ is false; in all other cases, it is true. It reads as \"If $P$, then $Q$\".* - ***Biconditional ($\iff$ or $\leftrightarrow$)**: A binary connective that is true if both connected propositions have the same truth value. $P \iff Q$ is true if both $P$ and $Q$ are true, or if both are false. It reads as \"$P$ if and only if $Q$\".* - ***Parentheses:** Used to group parts of formulas and specify the order of operations, ensuring unambiguous parsing of complex sentences.* *Well-formed formulas are constructed recursively:* 1. *Every propositional symbol is a well-formed formula.* 2. *If $\alpha$ is a well-formed formula, then $\neg \alpha$ is a well-formed formula.* 3. *If $\alpha$ and $\beta$ are well-formed formulas, then $(\alpha \land \beta)$, $(\alpha \lor \beta)$, $(\alpha \implies \beta)$, and $(\alpha \iff \beta)$ are well-formed formulas.* 4. *Nothing else is a well-formed formula.* ::: ::: definition **Definition 2** (Semantics of Propositional Logic). *The **semantics** of propositional logic defines how to interpret formulas and determine their truth value. It is based on the concept of **possible worlds** or **models**.* - ***Possible Worlds (Models):** In propositional logic, a possible world is an assignment of truth values (true or false) to each propositional symbol. If there are $n$ propositional symbols, there are $2^n$ possible worlds. Each possible world represents a complete specification of the truth values for all propositions under consideration.* - ***Interpretation Function:** The semantics is formally defined by an interpretation function that assigns a truth value (true or false) to each well-formed formula in each possible world. This assignment is based on the truth values of the propositional symbols and the semantics of the logical connectives.* *The truth value of a compound formula is determined recursively:* - *$\neg \alpha$ is true in a world $m$ if and only if $\alpha$ is false in $m$.* - *$\alpha \land \beta$ is true in a world $m$ if and only if $\alpha$ is true in $m$ and $\beta$ is true in $m$.* - *$\alpha \lor \beta$ is true in a world $m$ if and only if $\alpha$ is true in $m$ or $\beta$ is true in $m$ (or both).* - *$\alpha \implies \beta$ is true in a world $m$ if and only if $\alpha$ is false in $m$ or $\beta$ is true in $m$ (or both). Equivalently, it is false only when $\alpha$ is true and $\beta$ is false.* - *$\alpha \iff \beta$ is true in a world $m$ if and only if $\alpha$ and $\beta$ have the same truth value in $m$.* ::: To illustrate, consider the formula $P \lor (\neg Q \land R)$. To evaluate its truth value in a specific world, we need to know the truth values of $P$, $Q$, and $R$ in that world. For example, if in a world $m$, $P$ is false, $Q$ is true, and $R$ is true, we evaluate as follows: 1. $\neg Q$ is false (since $Q$ is true). 2. $\neg Q \land R$ is false (since $\neg Q$ is false). 3. $P \lor (\neg Q \land R)$ is false (since both $P$ and $(\neg Q \land R)$ are false). Thus, the formula $P \lor (\neg Q \land R)$ is false in the world $m$ where $P$ is false, $Q$ is true, and $R$ is true. We can conceptualize syntax and semantics as residing in distinct yet interconnected domains: **Syntax Land** and **Semantics Land**, as depicted in [1](#fig:syntax_semantics){reference-type="ref+Label" reference="fig:syntax_semantics"}. Syntax Land is concerned with the formal structure of logical sentences, while Semantics Land deals with their meaning and truth in relation to the world. The bridge between these two lands is provided by the concepts of entailment and inference, ensuring that syntactic manipulations are sound with respect to semantic interpretations. <figure id="fig:syntax_semantics"> <figcaption>Syntax Land and Semantics Land: Bridging the gap between formal expressions and their meanings.</figcaption> </figure> Propositional logic, often a starting point in the study of logic and computation, provides a simple yet powerful foundation for representing and reasoning with declarative knowledge. ## Logical Entailment and Inference :::: definition **Definition 3** (Logical Entailment). ::: tcolorbox ***Logical entailment** is a central concept in logic that formalizes the idea of logical consequence. A sentence $\alpha$ **logically entails** a sentence $\beta$, denoted as $\alpha \vDash\beta$, if and only if for every possible world (model) in which $\alpha$ is true, $\beta$ is also true. Formally, for all models $m$, if $m \models \alpha$, then $m \models \beta$.* ::: :::: Entailment signifies that $\beta$ is a logical consequence of $\alpha$; whenever $\alpha$ holds, $\beta$ must also hold. In terms of possible worlds, the set of worlds in which $\alpha$ is true is a subset of the worlds in which $\beta$ is true. :::: example **Example 1**. ::: tcolorbox *Consider $\alpha = A$ and $\beta = A \lor B$. We want to check if $A \vDash A \lor B$. In any world where $A$ is true, $A \lor B$ is also true, regardless of the truth value of $B$. Therefore, $A \vDash A \lor B$.* *Now consider $\alpha = A \land B$ and $\beta = A$. We want to check if $A \land B \vDash A$. In any world where $A \land B$ is true, both $A$ and $B$ must be true. Thus, $A$ is necessarily true. Therefore, $A \land B \vDash A$.* ::: :::: To establish entailment $\alpha \vDash\beta$, we can employ different methods. ### Methods for Determining Entailment There are two primary approaches to determine if $\alpha \vDash\beta$: model checking and theorem proving. - **Model Checking:** - **Direct Semantic Verification:** Model checking involves a direct examination of the semantics. To verify if $\alpha \vDash\beta$, we enumerate all possible worlds (models). For each world in which $\alpha$ is true, we check if $\beta$ is also true. If $\beta$ is true in all such worlds, then $\alpha \vDash\beta$. - **Feasibility for Propositional Logic:** For propositional logic, model checking is a decidable procedure because the number of possible worlds is finite ($2^n$ for $n$ propositional symbols). We can systematically check all truth assignments. - **Computational Cost:** While complete, model checking can be computationally expensive for a large number of propositional symbols, as the number of models grows exponentially. - **Example in Wumpus World:** In the Wumpus World example, to check if \"Breeze in (2,1)\" entails \"Pit in (2,2) or Pit in (3,1)\", we would consider all possible configurations of pits in squares (2,2) and (3,1) in worlds where there is a breeze in (2,1) and verify if in all such worlds, there is indeed a pit in (2,2) or (3,1). - **Theorem Proving (Syntactic Inference):** - **Syntactic Derivation:** Theorem proving focuses on manipulating formulas based on syntactic rules to derive new formulas. To show $\alpha \vDash\beta$, we aim to find a sequence of inference steps that starts with $\alpha$ and derives $\beta$. - **Inference Rules:** We use a set of **inference rules**, which are sound patterns of derivation. Applying these rules guarantees that if we derive $\beta$ from $\alpha$, then $\alpha$ indeed entails $\beta$. - **Soundness and Completeness:** A set of inference rules is **sound** if every derived conclusion is logically entailed. It is **complete** if every entailed conclusion can be derived. For propositional logic, there exist inference systems that are both sound and complete. - **Abstraction from Models:** Theorem proving operates in the \"Syntax Land,\" manipulating symbols and formulas without explicit reference to possible worlds. This can be more efficient and abstract than model checking, especially for complex logical systems. ### Fundamental Inference Rules in Propositional Logic Inference rules are the building blocks of theorem proving. They provide a way to syntactically derive new sentences from existing ones, ensuring that the derivation is logically sound. Some key inference rules in propositional logic are summarized below: :::::: theorem **Theorem 1** (Modus Ponens). ::::: tcolorbox *$$\frac{\alpha, \quad \alpha \implies \beta}{\beta}$$ *If we know $\alpha$ is true, and $\alpha$ implies $\beta$, we can infer $\beta$.** :::: example ***Example 2**. * ::: tcolorbox **Given: \"It is raining\" and \"If it is raining, then the street is wet.\" Inference: \"The street is wet.\"** ::: :::: ::::: :::::: :::::: theorem **Theorem 2** (And-Elimination). ::::: tcolorbox *$$\frac{\alpha \land \beta}{\alpha} \quad \text{and} \quad \frac{\alpha \land \beta}{\beta}$$ *If we know $\alpha$ and $\beta$ is true, we can infer $\alpha$ is true, and we can infer $\beta$ is true.** :::: example ***Example 3**. * ::: tcolorbox **Given: \"It is raining and the street is wet.\" Inference 1: \"It is raining.\" Inference 2: \"The street is wet.\"** ::: :::: ::::: :::::: :::::: theorem **Theorem 3** (Or-Introduction). ::::: tcolorbox *$$\frac{\alpha}{\alpha \lor \beta}$$ *If we know $\alpha$ is true, we can infer that $\alpha$ or $\beta$ is true (for any $\beta$).** :::: example ***Example 4**. * ::: tcolorbox **Given: \"It is raining.\" Inference: \"It is raining or the sun is shining.\"** ::: :::: ::::: :::::: :::::: theorem **Theorem 4** (Double-Negation Elimination). ::::: tcolorbox *$$\frac{\neg (\neg \alpha)}{\alpha}$$ *If we know it is not the case that $\alpha$ is not true, we can infer $\alpha$ is true.** :::: example ***Example 5**. * ::: tcolorbox **Given: \"It is not true that it is not raining.\" Inference: \"It is raining.\"** ::: :::: ::::: :::::: :::::: theorem **Theorem 5** (Contraposition). ::::: tcolorbox *$$\frac{\alpha \implies \beta}{\neg \beta \implies \neg \alpha}$$ *If we know $\alpha$ implies $\beta$, we can infer that not $\beta$ implies not $\alpha$.** :::: example ***Example 6**. * ::: tcolorbox **Given: \"If it is raining, then the street is wet.\" Inference: \"If the street is not wet, then it is not raining.\"** ::: :::: ::::: :::::: :::::: theorem **Theorem 6** (Implication Elimination (Equivalence)). ::::: tcolorbox *$$(\alpha \implies \beta) \equiv (\neg \alpha \lor \beta)$$ *An implication can be rewritten as a disjunction.** :::: example ***Example 7**. * ::: tcolorbox **\"If it is raining, then the street is wet\" is equivalent to \"Either it is not raining, or the street is wet (or both).\"** ::: :::: ::::: :::::: :::::: theorem **Theorem 7** (De Morgan's Laws (Equivalences)). ::::: tcolorbox - *Negation of Conjunction: $\neg (\alpha \land \beta) \equiv (\neg \alpha \lor \neg \beta)$* - *Negation of Disjunction: $\neg (\alpha \lor \beta) \equiv (\neg \alpha \land \neg \beta)$* **De Morgan's Laws provide rules for distributing negation over conjunction and disjunction.** :::: example ***Example 8**. * ::: tcolorbox **$\neg (P \land Q)$ is equivalent to $(\neg P \lor \neg Q)$. \"It is not true that it is raining and cold\" is equivalent to \"It is not raining or it is not cold (or both).\"** ::: :::: ::::: :::::: :::::: theorem **Theorem 8** (Commutativity (Equivalences)). ::::: tcolorbox - *Conjunction: $(\alpha \land \beta) \equiv (\beta \land \alpha)$* - *Disjunction: $(\alpha \lor \beta) \equiv (\beta \lor \alpha)$* **The order of operands does not matter for conjunction and disjunction.** :::: example ***Example 9**. * ::: tcolorbox **$(P \land Q)$ is equivalent to $(Q \land P)$. \"It is raining and cold\" is the same as \"It is cold and raining.\"** ::: :::: ::::: :::::: :::: theorem **Theorem 9** (Associativity and Distributivity). ::: tcolorbox *Associativity and distributivity laws also apply to conjunction and disjunction, allowing for flexible manipulation of formulas.* ::: :::: These inference rules are fundamental for building theorem provers and automated reasoning systems. Two important inference procedures are forward chaining and resolution. ### Forward Chaining and Resolution Inference Procedures :::: remark **Remark 1**. ::: tcolorbox *Forward chaining and resolution are valuable inference techniques in propositional logic. Forward chaining is data-driven and derives new facts from known facts. Resolution is refutation-based and proves entailment by showing unsatisfiability.* ::: :::: - **Forward Chaining:** - **Data-Driven Inference:** Forward chaining is a data-driven inference method. It starts with the known facts in the knowledge base and applies inference rules to derive new facts. This process continues until no new facts can be derived. - **Algorithm Description:** The forward chaining algorithm maintains an agenda of facts to be processed. It iteratively takes a fact from the agenda, applies all relevant inference rules, and adds any newly derived facts back to the agenda and the knowledge base. - **Use Case:** Forward chaining is particularly useful for reasoning about the consequences of initial conditions or when we want to compute all possible inferences from a given set of facts and rules. - **Soundness and Completeness:** For propositional logic with Modus Ponens as the primary inference rule, forward chaining can be shown to be sound and complete for deriving positive conclusions. ::::: tcolorbox :::: algorithm **Input:** Knowledge Base $\mathcal{KB}$ (set of propositional logic sentences), set of inference rules $R$\ **Output:** Set of all sentences inferred from $\mathcal{KB}$ using $R$ ::: algorithmic $Agenda \leftarrow \mathcal{KB}$ $Inferred \leftarrow \mathcal{KB}$ $\alpha \leftarrow \text{Pop}(Agenda)$ $\beta \leftarrow \text{Apply}(rule, \alpha)$ $Inferred \leftarrow Inferred \cup \{\beta\}$ $\text{Push}(\beta, Agenda)$ $Inferred$ ::: **Complexity Analysis:** In the worst case, forward chaining can explore a large portion of the possible inferences. For propositional logic, it is guaranteed to terminate because there is a finite number of propositional symbols and thus a finite number of possible sentences that can be inferred. However, in complex knowledge bases, the process can still be computationally intensive. :::: ::::: - **Resolution:** Both forward chaining and resolution are valuable inference techniques in propositional logic, each with its strengths and typical applications in AI systems. # Knowledge Representation Challenges: Time and Frame Problem ## Temporal Aspects of Knowledge in Dynamic Systems When we apply propositional logic to model real-world scenarios, especially dynamic environments like the Wumpus World, we quickly realize the necessity of incorporating time. The propositional logic we've discussed so far is static; it lacks an explicit way to represent change over time. However, intelligent agents operate in environments that evolve, perceive changes, and perform actions that induce further changes. Consider the agent's perception of a 'stench' in the Wumpus World. If the agent senses a stench at a particular moment, say time $t$, this perception is only valid at that specific time. If the agent moves to a different square at time $t+1$, the perception of stench from time $t$ might no longer be relevant or accurate in the new location. Therefore, to accurately model dynamic environments, our knowledge representation must account for temporal variations. One effective approach to handle time in logical representations is to introduce **temporal fluents**. Instead of using simple propositions like `Stench` or `Breeze`, we use predicates that are indexed by time. For instance, we might use `Stench(location, time)` or `Breeze(location, time)`. Using this notation, `Stench(1-1, 4)` would assert that \"there is a stench in location (1,1) at time 4\". We can broadly classify propositions in dynamic systems into two categories: - **Atemporal Propositions (Static):** These propositions represent facts that are invariant over time. They describe the unchanging rules and properties of the environment. In the Wumpus World, examples of atemporal propositions include rules like \"If there is a pit in a square, then adjacent squares will have a breeze.\" These rules are always true, regardless of time. - **Temporal Fluents (Dynamic):** These propositions represent aspects of the world that can change over time. They are used to describe the state of the world at different time points. Examples of temporal fluents in the Wumpus World include: - `Location(agent, location, time)`: The agent's position at a given time. - `HasArrow(time)`: Whether the agent possesses an arrow at a given time. - `WumpusAlive(time)`: Whether the Wumpus is alive at a given time. - `PerceivesStench(agent, location, time)`: Whether the agent perceives a stench in a location at a given time. - `FacingDirection(agent, direction, time)`: The direction the agent is facing at a given time. By using temporal fluents, we can represent the agent's perceptions, actions, and the changing state of the Wumpus World at discrete time steps. For example, if the agent perceives a breeze in location (1,1) at time 0, we can add the assertion `PerceivesBreeze(agent, 1-1, 0)` to our knowledge base. Furthermore, we need to establish logical connections between perceptions and the actual state of the world at different times. For instance, we can formalize the relationship between perceiving a breeze and the presence of a breeze in the environment with a sentence like: \"For all locations XY and times $t$, the agent perceives a breeze in location XY at time $t$ if and only if there is a breeze in location XY at time $t$.\" This type of rule needs to be defined for all relevant perceptions and environmental properties to create a comprehensive and temporally aware knowledge base. ## The Frame Problem: Tracking Non-Changes in Dynamic Worlds A major challenge in knowledge representation for dynamic environments is the infamous **frame problem**. This problem arises when we try to describe the effects of actions, particularly in specifying what **remains unchanged** when an action is performed. :::: definition **Definition 4** (Frame Problem). ::: tcolorbox *The **frame problem** is the challenge of efficiently and correctly representing the **non-effects** of actions in a dynamic world. It is concerned with determining what properties of the world persist or remain unchanged after an action is executed. The difficulty lies in avoiding the explicit and cumbersome enumeration of all these non-effects, which can lead to a combinatorial explosion of axioms, while ensuring that our logical system correctly infers the state of the world after each action.* ::: :::: Consider a simple action in the Wumpus World, such as the agent taking a `Forward` step. When an agent successfully moves forward, its location changes. However, intuitively, many other aspects of the world should remain the same. For example, whether the agent possesses an arrow, whether the Wumpus is alive, the locations of pits and the Wumpus (unless affected by the action itself, like shooting), and many other fluents should typically not be altered by a simple forward movement. The frame problem is about how to formally and efficiently specify this vast amount of \"inertia\" or non-change. ### Frame Axioms: Explicitly Stating What Doesn't Change (Inefficient) One straightforward, albeit inefficient, approach to address the frame problem is to use **frame axioms**. Frame axioms are logical statements that explicitly assert what remains unchanged when a particular action is performed. For the action `Forward`, we might propose frame axioms like: - **Arrow Frame Axiom:** \"If the agent performs `Forward` at time $t$, then if the agent `HasArrow` at time $t$, it will also `HasArrow` at time $t+1$.\" $$\text{HasArrow}(t) \implies \text{HasArrow}(t+1) \quad \text{after action } \texttt{Forward}(t)$$ - **Wumpus Alive Frame Axiom:** \"If the agent performs `Forward` at time $t$, and if `WumpusAlive` at time $t$, then `WumpusAlive` at time $t+1$.\" $$\text{WumpusAlive}(t) \implies \text{WumpusAlive}(t+1) \quad \text{after action } \texttt{Forward}(t)$$ For every action and every fluent that is not affected by that action, we would need to create a corresponding frame axiom. In a system with $M$ actions and $N$ fluents, this could potentially require up to $M \times N$ frame axioms for each time step. This leads to a significant problem: - **Combinatorial Explosion:** The number of frame axioms grows rapidly with the number of actions and fluents. For complex environments with many actions and properties, managing and reasoning with this vast number of axioms becomes computationally intractable. - **Cumbersome and Unintuitive:** Specifying what \*doesn't\* change for every action is tedious and counterintuitive. It shifts the focus from describing the actual effects of actions to exhaustively listing their non-effects. - **Maintenance Overhead:** Adding new actions or fluents requires updating a potentially large set of frame axioms, increasing the complexity of knowledge base maintenance. Frame axioms, while conceptually simple, lead to a combinatorial explosion and make knowledge representation and reasoning inefficient, especially in complex, dynamic domains. This inefficiency motivated the search for more elegant and scalable solutions to the frame problem. ### Successor-State Axioms: Focusing on Change (Efficient) A more efficient and conceptually cleaner approach to address the frame problem is through the use of **successor-state axioms**. Instead of explicitly stating what remains unchanged, successor-state axioms focus on defining what causes a fluent to **change** its truth value from one time step to the next. They directly specify the conditions under which a fluent becomes true or false in the successor state ($t+1$) based on the state at time $t$ and the actions performed at time $t$. For each fluent $F$, a successor-state axiom has the general form: ::: tcolorbox $$F(t+1) \iff [\text{Action at } t \text{ caused } F \text{ to become true}] \lor [F(t) \land \neg (\text{Action at } t \text{ caused } F \text{ to become false})]$$ ::: In simpler terms, a fluent $F$ is true at time $t+1$ if and only if either an action at time $t$ made it true, or it was already true at time $t$ and no action at time $t$ made it false (i.e., it persisted from the previous state unless an action explicitly changed it). This formulation elegantly handles the frame problem by concentrating on the conditions that lead to a change in a fluent's value, implicitly assuming that fluents retain their truth values in the absence of such changes. Let's consider successor-state axioms for specific fluents in the Wumpus World: - **Successor-State Axiom for `HasArrow`:** $$\text{HasArrow}(t+1) \iff (\text{HasArrow}(t) \land \neg \text{Shoot}(t))$$ This axiom states that the agent has an arrow at time $t+1$ if and only if it had an arrow at time $t$ and did not perform the `Shoot` action at time $t$. This concisely captures the condition under which the agent retains the arrow -- persistence unless used. It implicitly handles the frame problem for the `HasArrow` fluent by only specifying the condition under which it changes (i.e., when shooting). - **Successor-State Axiom for `Location(1-1)` (Simplified Example):** Let's consider a simplified axiom for being in location (1,1) at time $t+1$. Assume actions are `Forward`, `TurnLeft`, `TurnRight`. $$\begin{aligned} \text{Location}(1-1, t+1) \iff & (\text{Location}(1-1, t) \land \neg \text{Forward}(t)) \lor \\ & (\text{Location}(1-2, t) \land \text{FacingDirection}(\text{agent}, \text{South}, t) \land \text{Forward}(t)) \lor \\ & (\text{Location}(2-1, t) \land \text{FacingDirection}(\text{agent}, \text{West}, t) \land \text{Forward}(t)) \end{aligned}$$ This axiom states that the agent is at location (1,1) at time $t+1$ if either: 1. It was already at location (1,1) at time $t$ and did not move forward (**persistence**). 2. It was at location (1,2) at time $t$, was facing South, and moved forward, thus entering (1,1). 3. It was at location (2,1) at time $t$, was facing West, and moved forward, also entering (1,1). This axiom focuses on the actions that can cause the agent to be in location (1,1) at $t+1$, either by staying put or by moving into it from an adjacent location. It implicitly handles the frame problem for location by only specifying the conditions under which the location changes to (1,1). Locations other than (1,1) would have analogous successor-state axioms. Note that the `Bump` condition from the transcript example might be relevant in a more complete version to handle cases where the agent attempts to move into a wall, which would prevent a location change despite the `Forward` action. Successor-state axioms offer a significant improvement over frame axioms by providing a more concise, modular, and intuitive way to represent change in dynamic environments. They directly address the core of the frame problem by focusing on the causes of change, leading to more efficient and manageable knowledge representation for intelligent agents. By using successor-state axioms, we can build knowledge bases that are both expressive enough to model dynamic worlds and efficient enough for practical reasoning. # Conclusion In this lecture, we have explored the application of propositional logic as a foundational tool for constructing knowledge-based agents, using the Wumpus World as a practical example. We have systematically covered the core components of propositional logic, including its syntax for constructing logical sentences and its semantics for interpreting their truth values in possible worlds. We examined the concept of logical entailment, which defines logical consequence, and investigated inference rules and procedures like forward chaining and resolution that enable agents to perform automated reasoning. Furthermore, we addressed the significant challenges in knowledge representation for dynamic environments, focusing on the frame problem and introducing successor-state axioms as a more effective solution compared to frame axioms. **Key Takeaways:** While propositional logic offers a valuable starting point and is sufficient for representing and reasoning in relatively simple scenarios, it has inherent limitations, especially when dealing with complex, real-world environments. Propositional logic treats propositions as atomic units and lacks the expressiveness to represent objects, properties of objects, and relations between objects directly. It also struggles with generalization and quantification, which are essential for expressing general rules and dealing with collections of objects. Looking ahead, the next lecture will introduce **first-order logic (FOL)**, also known as predicate logic. First-order logic significantly expands upon propositional logic by providing: - **Objects and Relations:** FOL allows us to represent objects, their properties, and relationships between them, offering a much richer and more natural way to describe the world. - **Quantification:** FOL introduces quantifiers (universal $\forall$ and existential $\exists$) that enable us to make statements about all or some objects in the domain, greatly enhancing expressiveness and the ability to formulate general rules. - **Increased Expressiveness and Scalability:** With these added capabilities, first-order logic provides a more powerful and flexible framework for knowledge representation and reasoning, capable of handling more complex and scalable AI applications compared to propositional logic. In the next lecture, we will delve into the syntax and semantics of first-order logic and explore how it addresses the limitations of propositional logic, paving the way for more sophisticated knowledge-based agents. We will see how first-order logic can more naturally and efficiently represent the complexities of environments like the Wumpus World and beyond.