Logical Agents and First-Order Logic

Logical Agents

• Logical agents use formal logic to represent knowledge and make decisions in AI.
• They use logical reasoning to infer new knowledge and determine the best actions to achieve goals.
• A logical agent is an AI system that employs formal logic for knowledge representation, reasoning, and decision-making.
• They utilize symbolic representations and logical operations to derive conclusions and make decisions.
• Knowledge-based agents reason over an internal representation of knowledge to decide actions.
• An intelligent agent needs knowledge about the real world for efficient decision-making and reasoning.
• Knowledge-based agents maintain an internal state of knowledge, reason over it, update it after observations, and take actions.
• These agents can represent the world with some formal representation and act intelligently.

Knowledge-Based Agents

• Knowledge-based agents are composed of two main parts:
  • Knowledge-base (KB)
  • Inference system
• A knowledge-based agent must be able to:
  • Represent states, actions, etc.
  • Incorporate new percepts.
  • Update the internal representation of the world.
  • Deduce the internal representation of the world.
  • Deduce appropriate actions.
• Architecture of a knowledge-based agent:
  • The KBA takes input from the environment.
  • The inference engine communicates with the KB to decide actions.
  • The learning element updates the KB by learning new knowledge.

Knowledge Base

• The knowledge-base (KB) is a central component of a knowledge-based agent.
• It is a collection of sentences expressed in a knowledge representation language.
• The Knowledge-base of KBA stores facts about the world.
• A knowledge base is required for updating knowledge for an agent to learn with experiences and take action as per the knowledge.

Inference System

• Inference means deriving new sentences from old.
• The inference system allows adding new sentences to the knowledge base.
• A sentence is a proposition about the world.
• The inference system applies logical rules to the KB to deduce new information.
• The inference system generates new facts so that an agent can update the KB.
• An inference system works mainly with two rules:
  • Forward chaining
  • Backward chaining

Operations Performed by KBA

• The KBA performs three operations:
  1. TELL: Tells the knowledge base what it perceives from the environment.
  2. ASK: Asks the knowledge base what action it should perform.
  3. Perform: Performs the selected action.

Generic Knowledge-Based Agent

• The knowledge-based agent takes percept as input and returns an action as output.
• The agent maintains the knowledge base, KB, and it initially has some background knowledge of the real world.
• It also has a counter to indicate the time for the whole process, and this counter is initialized with zero.
• Each time when the function is called, it performs its three operations:
  • Firstly, it TELLs the KB what it perceives.
  • Secondly, it asks KB what action it should take.
  • Third, the agent program TELLS the KB which action was chosen.
• The MAKE-PERCEPT-SENTENCE generates a sentence setting that the agent perceived the given percept at the given time.
• The MAKE-ACTION-QUERY generates a sentence to ask which action should be done at the current time.
• MAKE-ACTION-SENTENCE generates a sentence which asserts that the chosen action was executed.

Levels of Knowledge-Based Agent

• A knowledge-based agent can be viewed at different levels:
  1. Knowledge level:
     • Specify what the agent knows and its goals.
     • Fix its behavior.
     • Example: An automated taxi agent needs to go from station A to station B, and it knows the way.
  2. Logical level:
     • Understand how knowledge is stored.
     • Sentences are encoded into different logics.
     • Example: Encoding knowledge into logical sentences for the automated taxi agent to reach destination B.
  3. Implementation level:
     • Physical representation of logic and knowledge.
     • Example: An automated taxi agent actually implements its knowledge and logic to reach the destination.

The Wumpus World

• The Wumpus world is a simple example world to illustrate the worth of a knowledge-based agent and to represent knowledge representation.
• It was inspired by a video game Hunt the Wumpus by Gregory Yob in 1973.
• The Wumpus world is a cave with 4x4 rooms connected with passageways, totaling 16 rooms.
• We have a knowledge-based agent who will go forward in this world.
• The cave has a room with a beast called Wumpus, who eats anyone who enters the room.
• The Wumpus can be shot by the agent, but the agent has a single arrow.
• In the Wumpus world, there are some Pits rooms which are bottomless, and if an agent falls in Pits, then he will be stuck there forever.
• In one room there is a possibility of finding a heap of gold.
• The agent goal is to find the gold and climb out the cave without falling into Pits or being eaten by Wumpus.
• The agent will get a reward if he comes out with gold, and he will get a penalty if eaten by Wumpus or falls in the pit.

Components to Navigate the Cave

• The rooms adjacent to the Wumpus room are smelly (stench).
• The rooms adjacent to PITs have a breeze.
• There will be glitter in the room if and only if the room has gold.
• The Wumpus can be killed by the agent if the agent is facing it, and Wumpus will emit a horrible scream which can be heard anywhere in the cave.

PEAS Description of Wumpus World

• Performance measure:
  • $+1000$ reward points if the agent comes out of the cave with the gold.
  • $-1000$ points penalty for being eaten by the Wumpus or falling into the pit.
  • $-1$ for each action, and $-10$ for using an arrow.
• The game ends if either agent dies or came out of the cave.
• Environment:
  • A 4*4 grid of rooms.
  • The agent initially is in room square [1, 1], facing toward the right.
  • The location of Wumpus and gold are chosen randomly except the first square [1,1].
  • Each square of the cave can be a pit with probability 0.2 except the first square.
• Actuators:
  • Left turn,
  • Right turn
  • Move forward
  • Grab
  • Release
  • Shoot.
• Sensors:
  • The agent will perceive the stench if he is in the room adjacent to the Wumpus (not diagonally).
  • The agent will perceive breeze if he is in the room directly adjacent to the Pit.
  • The agent will perceive the glitter in the room where the gold is present.
  • The agent will perceive the bump if he walks into a wall.
  • When the Wumpus is shot, it emits a horrible scream which can be perceived anywhere in the cave.
  • These percepts can be represented as a five-element list, in which we will have different indicators for each sensor.
  • Example: If agent perceives stench, breeze, but no glitter, no bump, and no scream, then it can be represented as: [Stench, Breeze, None, None, None].

Wumpus World Properties

• Partially observable: The agent can only perceive the close environment such as an adjacent room.
• Deterministic: The result and outcome of the world are already known.
• Sequential: The order is important.
• Static: Wumpus and Pits are not moving.
• Discrete: The environment is discrete.
• One agent: There is one agent only, and Wumpus is not considered as an agent.

Exploring the Wumpus World

• Agent's First step:
  • Initially, the agent is in the first room or on the square [1,1], and we already know that this room is safe for the agent, so to represent on the below diagram (a) that room is safe we will add symbol OK.
  • Symbol A is used to represent agent, symbol B for the breeze, G for Glitter or gold, V for the visited room, P for pits, W for Wumpus.
  • At Room [1,1] agent does not feel any breeze or any Stench which means the adjacent squares are also OK.
• Agent's second Step:
  • Now agent needs to move forward, so it will either move to [1, 2], or [2,1].
  • Let's suppose agent moves to the room [2, 1], at this room agent perceives some breeze which means Pit is around this room.
  • The pit can be in [3, 1], or [2,2], so we will add symbol P? to say that, is this Pit room?
  • Now agent will stop and think and will not make any harmful move.
  • The agent will go back to the [1, 1] room.
  • The room [1,1], and [2,1] are visited by the agent, so we will use symbol V to represent the visited squares.
• Agent's third step:
  • At the third step, now agent will move to the room [1,2] which is OK.
  • In the room [1,2] agent perceives a stench which means there must be a Wumpus nearby.
  • But Wumpus cannot be in the room [1,1] as by rules of the game, and also not in [2,2] (Agent had not detected any stench when he was at [2,1]).
  • Therefore agent infers that Wumpus is in the room [1,3], and in current state, there is no breeze which means in [2,2] there is no Pit and no Wumpus.
  • So it is safe, and we will mark it OK, and the agent moves further in [2,2].
• Agent's fourth step:
  • At room [2,2], here no stench and no breezes are present, so let's suppose agent decides to move to [2,3].
  • At room [2,3] agent perceives glitter, so it should grab the gold and climb out of the cave.

Logic

• A representation language is defined by its syntax, which specifies the structure of sentences, and its semantics, which defines the truth of each sentence in each possible world or model.
  • Syntax: The sentences in KB are expressed according to the syntax of the representation language, which specifies all the sentences that are well formed.
  • Semantics: The semantics defines the truth of each sentence with respect to each possible world.
  • Models: We use the term model in place of “possible world” when we need to be precise.
  • Possible worlds are potentially real environments that the agent might or might not be in.
  • Models are mathematical abstractions, each of which simply fixes the truth or falsehood of every relevant sentence.

Propositional Logic

• Propositional logic (PL) is the simplest form of logic where all the statements are made by propositions.
• A proposition is a declarative statement which is either true or false.
• It is a technique of knowledge representation in logical and mathematical form.

A Very Simple Logic

• Propositional logic is also called Boolean logic as it works on 0 and 1.
• In propositional logic, we use symbolic variables to represent the logic, and we can use any symbol for representing a proposition, such as A, B, C, P, Q, R, etc.
• Propositions can be either true or false, but it cannot be both.
• Propositional logic consists of an object, relations or function, and logical connectives.
• These connectives are also called logical operators.
• The propositions and connectives are the basic elements of the propositional logic.
• Connectives can be said as a logical operator which connects two sentences.
• A proposition formula which is always true is called tautology, and it is also called a valid sentence.
• A proposition formula which is always false is called Contradiction.
• A proposition formula which has both true and false values is called contingency.
• Statements which are questions, commands, or opinions are not propositions, such as "Where is Rohini", "How are you", "What is your name", are not propositions.

Syntax of Propositional Logic

• The syntax of propositional logic defines the allowable sentences for the knowledge representation.
  • Atomic Propositions
  • Compound propositions
• Atomic Proposition:
  • Atomic propositions are the simple propositions.
  • It consists of a single proposition symbol.
  • These are the sentences which must be either true or false.
  • Example:
    • It is Sunday.
    • The Sun rises from West (False proposition)
    • $3+3= 7$(False proposition)
    • 5 is a prime number.
• Compound proposition:
  • Compound propositions are constructed by combining simpler or atomic propositions, using parenthesis and logical connectives.

Logical Connectives

• Logical connectives are used to connect two simpler propositions or representing a sentence logically.

• We can create compound propositions with the help of logical connectives.

• There are mainly five connectives:

  1. Negation:
     • A sentence such as $¬ P$ is called negation of P.
     • A literal can be either Positive literal or negative literal.
  2. Conjunction:
     • A sentence which has $∧$ connective such as, $P ∧ Q$ is called a conjunction.
     • Example: Rohan is intelligent and hardworking. It can be written as, $P=$ Rohan is intelligent, $Q=$ Rohan is hardworking. → $P∧ Q$.
  3. Disjunction:
     • A sentence which has $∨$ connective, such as $P ∨ Q$ is called disjunction, where P and Q are the propositions.
     • Example: "Ritika is a doctor or Engineer", Here $P=$ Ritika is Doctor. $Q=$ Ritika is Doctor, so we can write it as $P ∨ Q$.
  4. Implication:
     • A sentence such as $P → Q$, is called an implication.
     • Implications are also known as if-then rules.
     • It can be represented as If it is raining, then the street is wet.
     • Let $P=$ It is raining, and $Q=$ Street is wet, so it is represented as $P → Q$
  5. Biconditional:
     • A sentence such as $P⇔ Q$ is a Biconditional sentence.
     • Example: If I am breathing, then I am alive
     • $P=$ I am breathing, $Q=$ I am alive, it can be represented as $P ⇔ Q$.

Truth Table for Propositional Logic Connectives

• In propositional logic, we need to know the truth values of propositions in all possible scenarios.
• We can combine all the possible combination with logical connectives, and the representation of these combinations in a tabular format is called Truth table.

Logical Equivalence

• Logical equivalence is one of the features of propositional logic.
• Two propositions are said to be logically equivalent if and only if the columns in the truth table are identical to each other.
• Let's take two propositions A and B, so for logical equivalence, we can write it as $A⇔B$.
• In below truth table we can see that column for $¬A∨ B$ and $A→B$, are identical hence A is Equivalent to B.

Limitations of Propositional Logic

• We cannot represent relations like ALL, some, or none with propositional logic.
  • Example:
    • All the girls are intelligent.
    • Some apples are sweet.
• Propositional logic has limited expressive power.
• In propositional logic, we cannot describe statements in terms of their properties or logical relationships.

Propositional Theorem Proving in AI

• Propositional theorem proving in AI is one of the earliest applications of propositional calculus.
• It involves using logical reasoning to prove mathematical theorems, relying on the principles of propositional logic.
• In simple terms, it is the ability of computers to automatically prove or disprove mathematical statements and propositions using formal logic.

First-Order Logic in Artificial Intelligence

• In propositional logic, we can only represent the facts, which are either true or false.
• PL is not sufficient to represent the complex sentences or natural language statements.
• The propositional logic has very limited expressive power.
• Consider the following sentence, which we cannot represent using PL logic: "Some humans are intelligent", or "Sachin likes cricket."

First-Order Logic (FOL)

• First-order logic is another way of knowledge representation in artificial intelligence.
• It is an extension to propositional logic.
• FOL is sufficiently expressive to represent the natural language statements in a concise way.
• First-order logic is also known as Predicate logic or First-order predicate logic.
• First-order logic is a powerful language that develops information about the objects in a more easy way and can also express the relationship between those objects.
• First-order logic (like natural language) does not only assume that the world contains facts like propositional logic but also assumes the following things in the world:
  • Objects: A, B, people, numbers, colors, wars, theories, squares, pits, wumpus, ……
  • Relations: It can be unary relation such as: red, round, is adjacent, or n-any relation such as: the sister of, brother of, has color, comes between
  • Function: It maps object to other object. Eg: Father of, best friend, third inning of, end of, ……
  • Predicate :: Functions that return true or false, representing properties of objects or relationship between them.
• As a natural language, first-order logic also has two main parts:
  • Syntax
  • Semantics

Syntax of First-Order Logic

• The syntax of FOL determines which collection of symbols is a logical expression in first-order logic.
• The basic syntactic elements of first-order logic are symbols.
• We write statements in short-hand notation in FOL.