Logic and Reasoning

Week 6 Introduction

Reasoning with Logic

This week focuses on reasoning using logic, with a particular emphasis on truth tables, which are fundamental in determining the validity of logical expressions and arguments.

Today's Lecture: We will explore the foundational concepts of truth tables and their essential role in logical reasoning. Students will learn how to construct truth tables for various logical expressions and understand how these tables can be used to evaluate the truth values of complex statements.
Thursday's Lecture: We will delve into various simple reasoning algorithms that are crucial for logical deduction. This includes:
- Forward Chaining: A data-driven approach where reasoning moves from the premises (known facts) to conclude new facts.
- Backward Chaining: A goal-driven approach that starts with the conclusion and works backwards to find supporting facts. This method is particularly useful in problem-solving scenarios where specific goals are established.
- General Proof Methods in Propositional Logic: Techniques that include direct proofs, indirect proofs, and proof by contradiction.
Friday: An in-class test focused on critical topics such as uninformed and heuristic search, local search and optimization, adversarial search, and games. This test will assess students' understanding of key concepts and their application in problem-solving contexts.

Note: Today's and Thursday's lectures are not relevant to the upcoming test but will be included in the final exam, emphasizing the importance of continuous engagement with all materials.

Assignment 2

The second assignment builds on the first, closely mirroring its structure while introducing new challenges involving Python programming:

Implementation of local search algorithms (hill climbing, genetic algorithms, and simulated annealing) specifically tailored to solve the k-network puzzle. Students will develop an understanding of how these algorithms function, their strengths, and their limitations.
Configuration of implemented algorithms is necessary to develop optimal solutions, requiring adjustments based on algorithmic performance metrics and outcomes.
Implementation of local beam search alongside its stochastic variant will be explored. Students will analyze how these search methods differ and when to apply them effectively.

K-Network Puzzle

The k-network puzzle presents a challenge that involves rotating tiles to maximize connections between neighboring pieces. The ultimate goal is to achieve the maximum number of connections, with the example showing that attaining 20 connections is the optimal solution. This puzzle not only tests programming ability but also analytical problem-solving skills.

Reasoning Using Propositional Logic

We are transitioning from search-based problem-solving to reasoning, especially in partially observable environments where agents lack complete state information. This transition emphasizes the importance of logic in drawing conclusions about unseen aspects of the environment.

Logic becomes a critical tool for the agent to deduce missing information successfully.
The agent maintains a knowledge base, which is initialized with fundamental rules and relationships given by the designer. As the agent interacts with the environment, percepts (observations) are gradually added to the knowledge base.
Logical reasoning facilitates the agent's ability to infer and integrate new knowledge into its existing knowledge base, enhancing decision-making accuracy and efficiency.

Knowledge Base

The knowledge base can be likened to axioms in mathematics. It comprises essential rules governing the environment in which the agent operates. Logical inferences can expand the knowledge base, drawing parallels to academic fields such as mathematics:

Just as mathematicians expand the knowledge base of mathematics through rigorous proofs and theorems, agents can enhance their operational effectiveness through careful and logical reasoning.
The process of drawing logical inferences contributes significantly to a dynamic increase in knowledge available to the agent, allowing for adaptability in various environments.

Propositional Logic

Propositional logic serves as a fundamental formal language used for reasoning. In this course, we will primarily focus on propositional logic and will not extend to first-order logic or predicate logic. The distinction between propositional and predicate logic is essential to understand; propositional logic utilizes simple declarative statements, whereas predicate logic employs variables to make statements about collections of objects.

Wumpus World Example

The Wumpus World presents a complex dungeon environment where the agent seeks gold while simultaneously avoiding adversarial entities, such as a monster (the Wumpus) and pits (which pose hazards). To successfully navigate, the agent must engage in:

Dynamic reasoning: Which enables it to avoid danger by assessing the environment continuously.
Informal reasoning: Initially used for basic decision-making, followed by formal tools such as truth tables and pseudo-code-based proofs to solidify its conclusions and justify its actions.

Knowledge-Based Agents

These agents are characterized by the maintenance of a knowledge base of sentences represented in propositional logic. This systematic organization of information is crucial in aiding the agent in determining safe actions while traversing its environment, ensuring both efficiency and safety.

Formal Representation Language

While propositional logic is the primary tool employed, it is essential to recognize that alternative logical systems, such as first-order logic, could provide different benefits. A formal language must be established to accurately articulate the information stored within the knowledge base.

Background Knowledge

The background knowledge is the initial information provided to the agent, detailing the essential aspects of the environment. As actions are performed and percepts acquired, this knowledge base is dynamically updated, with new sentences derived from existing knowledge through inference mechanisms utilizing truth tables or established inference rules.

Syntax of Propositional Logic

The formulation of sentences in propositional logic adheres to specific syntax rules:

Sentences can be classified as atomic or complex.
- Atomic sentences: Can be evaluated as True, False, or represented by propositional symbols (e.g., p, q, r).
- Complex sentences: Formed using logical connectives that interrelate atomic sentences.

Logical Connectives

The following logical connectives are available for constructing complex sentences:

Negation: $ eg$ (inverts the truth value of a proposition)
Conjunction:
eg igwedge (evaluates as true only if both components are true)
Disjunction:
eg igvee (evaluates as true if at least one component is true)
Implication: $ eg ightarrow$ (evaluates as true when the antecedent is false)
Biconditional: $ eg ightarrow$ (evaluates as true if both components share the same truth value)

Semantics and Interpretation

The semantics of propositional logic hinge on the truth values assigned to propositional symbols.

Propositional symbols can take on the values true or false, and the meaning of logical connectives is defined based on these truth values.

In terms of syntax, 'True' and 'False' are atomic sentences with fixed truth values, differentiating them from the variable evaluations of expressions which can yield different truth values.

Operator precedence for logical connectives is essential for proper sentence interpretation. The order of precedence, from highest to lowest, is: Negation, conjunction, disjunction, implication, and biconditional, with the option to use parentheses to override this order.

Wumpus World Example Cont.

An agent navigating the Wumpus World operates within a grid setup, perceiving solely its immediate surroundings. This represents a partially observable environment where sensory input dictates behavior:

Initial State: The agent starts at position (1,1), lacking prior knowledge of its environment.
Percepts: The agent can observe breezes near pits and stench near the Wumpus, requiring careful movement to avoid hazards.
Goal: To successfully obtain the gold and safely return to the exit at (1,1).

Reasoning Steps

The agent utilizes available percepts and background knowledge to make informed inferences in propositional logic scenarios:

Initially stationed at (1,1) with no percepts, the agent begins inferring that locations (1,2) and (2,1) are non-threatening as no stench or breeze is detected.

If the agent moves to (2,1) and detects a breeze:

It infers that either (2,2) or (3,1) must contain a pit, necessitating a return to (1,1) and the exploration of (1,2), where a stench has begun to develop.

Discoveries

The absence of a breeze in (1,2) entails that (2,2) is a safe space.
The lack of stench in (2,1) confirms that the Wumpus cannot inhabit (3,1).
The agent deduces that the Wumpus must be located at (1,3).

By advancing to (2,2), the agent successfully acquires the gold, using logical inference based on the knowledge contained within its accumulated knowledge base.

Limitations of Propositional Logic

Propositional logic's constraints become evident, particularly in environments necessitating numerous propositional variables to adequately represent and interpret percepts along with fundamental environmental information.

For a 4x4 location environment, 16 propositional variables become necessary for accurately reflecting pits and another 16 for breezes, leading to considerable complexity in truth table management.

To streamline operations, the focus on breeze and pit identification in bottom-left locations assists in minimizing the logical space required for truth table construction.

Background Knowledge

The background knowledge takes on a propositional logic representation. For instance, the rule stating "no pit in location (1,1)" would be articulated simply as $ eg P_{1,1}$ . The established relationships among percepts and environmental properties can be expressed as follows:

A breeze exists in location (1,1) if and only if there is a pit in location (1,2) or (2,1):

B{1,1} ightarrow (P{1,2} igvee P_{2,1})
A breeze exists in location (2,1) if and only if there is a pit in (1,1) or (2,2) or (3,1):

B{2,1} ightarrow (P{1,1} igvee P{2,2} igvee P{3,1})

Additional knowledge surfaces through the agent’s experiences moving through its environment. For example, upon reaching (2,1):

The absence of a breeze in (1,1) translates to $ eg B{1,1}$ and a breeze detected at (2,1) is denoted as $B{2,1}$ .

Logical reasoning is then utilized to derive conclusions about what has occurred. A sentence $\alpha$ is deemed a logical consequence of the knowledge base (KB) if the knowledge base entails $\alpha$ , formally represented as $KB \vDash \alpha$ .

Models and Entailment

The possible configurations of the world that result in expressions being true or false are designated as models:

In the context of propositional logic, models equate to the various assignments of truth values made to all propositional variables in use.
A truth table visually Represents models of the knowledge base, where each row symbolizes a potential model configuration.
The row configurations that correspond to a true knowledge base (M(KB)) are those rows in the truth table where all expressions remain true, thus indicating valid models of the knowledge base.

Entailment: A sentence $\alpha$ is a logical consequence of KB if the set of rows validating KB is a subset of the rows for which $\alpha$ is valid.

Truth Table Example

A truth table is strategically employed to illustrate a contained segment of the world, particularly focusing on relationships between pits and breezes. The structure includes columns dedicated to propositional variables and expressions representing the knowledge base. Models that meet the conditions of the knowledge base manifest in the rows where all propositions hold true.

When aiming to prove a statement, it is added as an additional column in the table. If the proposed expression validates across all models within the knowledge base, it is classified as a logical consequence.
A pertinent example is offering proof for $\neg P{1,2}$ ; by introducing a column for $\neg P{1,2}$ and ascertaining that it holds true throughout, we enhance the logical rigor of our deductions.

Mechanical Algorithm for Truth Table Checking

A mechanized algorithm can systematically traverse all conceivable combinations of truth values assigned to the propositional variables. This algorithm recursively incorporates propositional assignments to newly introduced propositional variables:

Required components include: a knowledge base, the Alpha (the sentence to be verified), a queue of symbols containing all potential propositional symbols relevant to the world (e.g., P11, P12, etc.), and a parameter representing the current model state under scrutiny.
Note: Though the algorithm exhibits exponential complexity in relation to the number of variables involved, it benefits from linear space complexity due to its implementation of depth-first search strategies, thus optimizing memory usage.

This mechanical process proves advantageous in scenarios where the number of propositional variables is manageable. Looking ahead, the following lectures will introduce pragmatic algorithms for theorem proving, utilizing established proof rules effectively.