---

AI - Lecture - Logical Agents, Propositional Logic

• Source: Artificial Intelligence: A Modern Approach, 4ed Chapter 7

Humans know things and what they know helps them do things. In AI, knowledge based agents use a process of reasoning over an internal representation of knowledge to decide what actions to take.

The problem-solving agents of Chapters 3 and 4 know things, but only in a very limited, inflexible sense. They know what actions are available and what the result of performing a specific action from a specific state will be, but they don’t know general fact. For instance a route-finding agent doesn’t know that it is impossible for a road to be a negative number of kilometers long. The knowledge they have is very useful for finding a path from the start to a goal, but not for anything else.

Now we have to consider logic as a general class of representations to support knowledge-based agents. These agents can combine and recombine information to suit myriad purposes.

Knowledge-based agents can accept new tasks in the form of explicitly described goals; they can achieve competence quickly by being told or learning new knowledge about the environment; and they can adapt to changes in the environment by updating the relevant knowledge.

Knowledge-Based Agents

The central component of a knowledge-based agent is its knowledge base, or KB. A knowledge base is a set of sentences, each expressed in a language called knowledge representation language and represents some assertion about the world.

When the sentence is taken as being given without being derived from other sentences, we call it an axiom.

There must be a way to add new sentences to the knowledge base and a way to query what is known. TELL and ASK are the standard name for these operations, but both may involve inferences that is deriving new sentences from old.

Inference must obey the requirements that when one ASKs questions of the knowledge base, the answer should follow from what has been told (or TELLed) to the knowledge base previously.

In the following figure we have the outline of a knowledge-based agent program:

Each time the agent program is called, it does three things:

• It TELLs the knowledge base what it perceives
• It ASKs the knowledge base what action it should perform
• It TELLs the knowledge base which action was chosen, and returns the action so that it can be executed.

MAKE-PERCEPT-SENTENCE constructs a sentence asserting that the agent perceived the given percept at the given time. MAKE-ACTION-QUERY constructs a sentence that asks what action should be done at the current time. MAKE-ACTION-SENTENCE constructs a sentence asserting that the chosen action was executed. The details of the inference mechanisms are hidden inside TELL and ASK.

The agent in Figure: Is quite similar to agents with internal state.

Because of the definitions of TELL and ASK, however, the knowledge-based agent is not an arbitrary program for calculating actions. It is amenable to a description at the knowledge level, where we need specify only what the agent knows and what its goal are, in order to determine its behavior. This analysis is independent of what works at implementation level.

In the 1970s and 1980s, there were heated debates on two approaches:

• declarative approach to system building where the agent designer TELL sentences one by one until the agent knows how to operate in its environment
• procedural approach where desired behaviors are encoded directly as program code.

We now understand that a successfull agent often combines both declarative and procedural elements in its design.

Wumpus World

The wumpus world is a cave consisting of rooms connected by passageways. Lurking somewhere in the cave is the terrible wumpus, a beast that eats anyone who enters its room. The wumpus can be shot by an agent, but the agent has only one arrow. Some rooms contain bottomless pits that will trap anyone who wanders into these rooms (except for the wumpus which is too big to fall in). The only redeeming feature of this bleak environment is the possibility of finding a heap of gold. The wumpus world illustrates some important points about intelligence.

Let’s define formally using PEAS: Performance Measure: +1000 for climbing out of the cave with gold, -1000 for falling into a pit or being eaten by wumpus, -1 for each action tokena nd -10 for using up the arrow. The game ends either when the agent dies or when the agent climbs out of the cave. Environment: a grid of rooms, with walls surroudning the grid. The agent always starts in the square labeled facing to the east. The locations of the gold and the wumpus are chosen randomly, with a uniform distribution, from the squares other than the start square. In addition, each square other than start can be a pit, with probability 0.2. Actuators: The agent can move Forward, TurnLeft by 90°, or TurnRight by 90°. The agent dies a miserable death if it enters a square containing a pit or a live wumpus. (It is safe, albeit smelly, to enter a square with a dead wumpus.) If an agent tries to move forward and bumps into a wall, then the agent does not move. The action Grab can be used to pick up the gold if it is in the same square as the agent. The action. Shoot can be used to fire an arrow in a straight line in the direction the agent is facing. The arrow continues until it either hits (and hence kills) the wumpus or hits a wall. The agent has only one arrow, so only the first Shoot action has any effect. Finally, the action Climb can be used to climb out of the cave, but only from square . Sensors: The agent has five sensors, each of which gives a single bit of information:

• In the squares directly (not diagonally) adjacent to the wumpus, the agent will perceive a Stench
• In the squares directly adjacend to a pit, the agent will perceive a Breeze
• In the square where the gold is, the agent will perceive a Glitter
• When an agent walks into a will, it will perceive a Bump
• When the wumpus is killed, it emits a woeful Scream that can be perceived anywhere in the cave.

The percepts will be given to the agent program in the form of a list of five symbols; for example, if there is a stench and a breeze, but no glitter, bump, or scream, the agent program will get .

The wumpus environment, assuming the wumpus doesn’t move, it is: deterministic, discrete, static and single-agent. It is also sequential because rewards may come only after many actions are taken. It is partially observable because some aspects of the state are not directly perceivable: the agent’s location, the wumpus’ state of health, and the availability of an arrow.

The transition model itself is unknown because the agent doesn’t know which Forward actions are fatal, in which case, discovering the locations of pits and wumpus completes the agent’s knowledge of the transition model. Or alternatively we could consider the location of the pits and wumbus as unobserved parts of the state, and thus the transition model would be defined in a different way such that the it is known for the environment, and finding the locations of pits completes the agent’s knowledge of the state.

For an agent in this environment, the main challenge is its initial ignorance of the configuration of the environment; overcoming this ignorance seems to require logical reasoning.

In most instances of the wumpus world, it is possible for the agent to retrieve the gold safely. Occasionally, the agent must choose between going home empty-handed and risking death to find the gold. About 21% of the environments are utterly unfair, because the gold is in a pit or surrounded by pits

Let us watch a knowledge-based wumpus agent exploring the environment shown in Figure 7.2.

1. Suppose the agent is cautious, so it will move only into a square that it knows to be OK.
2. The agent first moves at 2,1 and perceives a breeze (denoted by B) that indicates that there must be a pit either in 3,1 or 2,2 or both.
3. The prudent agent turn back to 1,1 that is safe, and moves into 1,2. It then pterceives a stench so there must be a wumpus nearby. But the wumbus can only be in 1,3 - since by visiting 2,1 the agent perceived a breeze, but if the wumpus would be in 2,2 then the agent must have perceived the stench in 2,1 - therefore we can confirm that the wumpus is in 1,3.
4. However 2,2 is safe, since the agent only perceived a stench but not a breeze (implying there is no pit nearby), so it can move into 2,2.

Now consider figure 7.4

The agent moves to 2,3. It detects a glitter, so it should grab the gold and then return home.

A fundamental property of logical reasoning is thtat: in each case an agent draws a conclusion from the available information, that conclusion is guaranteed to be correct if the available information is correct.

Logic

A logic must have the following elements:

Syntax in which to express reasoning, usually it is the same representation language used in the knowlege bases

Semantics: logic must define semantics that is meaning of sentences. It defines the truth of each sentence with respect ot each possible world. For example, the semantics for arithmetic specifies that the sentence “x+y=4” is true in a world where and but false in a world where is 1 and is 1. In standard logics, every sentence must be either true or false in each possible world—there is no “in between” (for there there is fuzzy logic).

Model: we can talk of a model in place of “possible world” to be more precise. Models are mathematical abstractions, each of which has a fixed truth value (true or false) for every relevant sentence.

If a sentence is true in model m, we say that m satisfies or sometimes m is a model of . We can use the notation to mean the set of all models of :

Logical reasoning

Once we have a notion of truth, we are ready to talk about logical reasoning. This involves the relation of logical entailment between sentences: the idea that a sentence follows logically from another sentence. In mathematical notation we write:

to mean that sentence entails sentence .

The formal definition of entailment is: if and only if, in every model in which is true, is also true. That can be written as:

Note that the direction of the is important, this implies that is a stronger assertion than i.e. rules out more possible worlds. For example entails that that .

Logical reasoning aims to derive conclusions that are entailed by what is known.

Example of Entailment

Premises:

1. If it did not rain, then Harry visited Hagrid today
2. Harry visited Hagrid or Dumbledore today, but not both
3. Harry visited Dumbledore today

Entailed conclusion:

1. Harry did not visit Hagrid today
2. It rained today

Formally, let : it rained today,

• : harry visited hagrid today

• harry visited dumbledore today

Premises:

Conclusions:

Let’s go back to Figure 7.3(b): The agent has detected nothing in and a breeze in . These percepts, combined with the agent’s knowledge of the rules of the wumpus world, constitute the Knowledge Base.

The agent wants to know in whether the adjacent squares and contains pits. Each of these might or might not contain a pit, so there are possible models. These eight models are shown in figure 7.5:

Model checking

The KB can be thought of as a set of sentences or a single sentence that asserts all the individual sentences. The KB is false in models that contradict what the agent knows for example, the KB is false in any model in which contains a pit, because there is no breeze in . There are in fact just three models in which the KB is true, and these are shown surrounded by a solid line in the figure.

Consider two possible conclusions:

• = there is no pit in
• = there is no pit in .

Both are surrounded with dotted lines.

By inspection we see the following: “in every model in which KB is true, is also true”. Hence : there is no pit in .

We can also see that: “in some models in which KB is true, is false”. Hence KB does not entail : the agent cannot conclude that there is no pit in (nor can it conclude that there is a pit in ).

The preceding example not only illustrates entailment but also shows how the definition of entailment can be applied to derive conclusions—that is, to carry out logical inference.

This particular idea is called model checking: an algorithm that enumerates all possible models to check that is true in all models in which KB is true i.e. .

To understand entailment and inference it might help to think of the set of all consequences of KB as a haystack and of as a needle. Entailment is like the needle being in the haystack; inference is like finding it.

If an inference algorithm can derive from KB we write:

Model checking is the simplest inference algorithm:

1. enumerate all possible models relevant to and
2. identify the models in which is true
3. verify whether is true in every such model
4. If so then otherwise

Properties of model checking

An inference algorithm that derives only entailed sentences is called sound or truth-preserving. The property of completeness is also desirable: an inference algorithm is complete if it can derive any sentence that is entailed.

For real haystacks, which are finite in extent, it seems obvious that a systematic examination can always decide whether the needle is in the haystack. However for many knowledge bases, the haystack of consequences is infinite, and completeness becomes an important issue. This is comparable with the case of “infinite search spaces” that we saw previously.

The final issue to consider is grounding: the connection between logical reasoning processes and the real environment in which the agent exists. In particular how do we know that KB is true in the real world?. This is an hard philosophical question. A simple answer is that the agent’s sensors create the connection. For example in our wumpus-world, the agent has a smalls sensor. The agent program creates a suitable sentence whenever there is a smell. Then whenever that sentence is in the knowledge base, it is true in the real world. The rest of the agent’s knowledge such as its belief that wumpuses cause smells in adjacent squares are not a direct representation of a single percpt but a general rule derived from perceptual experience but not identical to a statement of that experience.

General rules like this are produced by a sentence construction process called learning, which is the subject of Machine Learning. However learning is fallible, it could be cases that wumpus cause smells excepts on Febraury 29 in leap years when they take their baths.

graph TD
Title["Logical Agents"]
KB["Knowledge Base"]
LogicalReasoning["Logical Reasoning"]
Entailment("Entailment $$\; KB \models \alpha$$")
Model("Model: $$\; M(\alpha)$$")
EntailDef("$$\alpha \models \beta \text{ if and only if } M(\alpha) \subseteq M(\beta)$$")
ModelChecking("Model Checking")
ModelCheckingInference("$$KB \vdash_i \alpha$$")

Title --> KB
Title --> Logic
Logic --> LogicalReasoning
Logic --> Syntax
Logic --> Semantics
LogicalReasoning --> Entailment --> Model
Model --Entailment Definition--> EntailDef
KB --> ModelChecking
LogicalReasoning-->ModelChecking-->ModelCheckingInference
ModelChecking-->ModelCheckingProperties("Properties")
ModelCheckingProperties-->MCPSound("Sound")
ModelCheckingProperties-->MCPComplete("Completeness")
ModelCheckingProperties-->MCPGrounding("Grounding")

Propositional Logic

We now present propositional logic from which it is possible to derive a simple syntactic algorithm for logical inference that implements the semantic notion of entailment. Everything take place in the Wumpus Worlds.

Syntax

The syntax of propositional logic defines the allowable sentences.

The atomic sentences consist of a single proposition symbol, each such symbol stands for a proposition that can be true or false. There are two proposition symbols with fixed meaning:

• True is the always-true proposition
• False is the always-false proposition

Complex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives.

These are the five connective in common use (not, and, or, implies and “if and only if”):

• (NOT)
• also called conjunction, its parts are conjuncts. The looks like an “A” for And
• is a disjunction, its parts are disjuncts.
• is called implications. It has a premise or antecedent and on the right a conclusion or consequent. Implications are also known are if-then statements.
• if and only if. It’s a biconditional.

Semantics

The semantics defines the rules for determining the truth of a sentence with respect to a particular model.

In propositional logic, a model simply sets the truth value - true or false - for every proposition symbol. For example if the sentences in the knowledge base make use of the proposition symbols and , then one possible model is:

With three proposition symbols there are possible models, exactly those depicted in Figure 7.5. Notice, however, that the models are purely mathematical objects with no necessary connection to wumpus worlds i.e. is just a symbol.

The model of the sentence are those assignements in which the sentence is true.

The semantics of propositional logic tells us how to compute the truth value of a sentence in a given model. For atomic sentences true is true in every model, false is false in every model and every proposition symbol gets it truth value from the model. For complex sentences their truth value is defined recursively. It depends on:

• the truth values of the component sentences
• the truth tables of the connectives

All sentences are constructed from atomic sentences and the five connectives; therefore, we need to specify how to compute the truth of atomic sentences and how to compute the truth of sentences formed with each of the five connectives.

The rules to compute the truth of complex sentences can be expressed through truth tables:

Propositional logic and natural language

In propositional logic, connectives are interpreted truth-functionally. In natural language, the same words may carry additional meaning For example:

• He fell and broke his leg → and may express a temporal or casual relation
• He broke his leg and fell is not be equivalent in meaning.

Another example:

• A tennis match can be won or lost. → this “or” is naturally understood as exclusive.
• logical disjunction is inclusive, while exlusive or is

The implication operator is false when is true and is false. In all other cases it is true.

In propositional logic the implication operator depends only on the truth value of and . It does not require any causal, temporal, or relevant connection between them For example:

• If 5 is odd, then Tokyo is the capital of Japan → while it is strange in natural language, in propositional logic this is true.
• if 5 is even, then 10 is even → unnatural in natural language, but true in propositional logic because the antecedent is false.

In propositional logic, the biconditional has the following truth table:

is true only when both are true or both are false.

The biconditional means that both implications are true, so it can be written as:

Example from Wumpus World:

• “A square is breezy if and only if a neighbouring square has a pit”

A simple knowledge base for wumpus world

We need to define a propositional vocabulary for example:

• : the agent is in room
• the wumpus is in room

First let’s consider the immutable aspects of the wumpus world. We need the following symbols for each location:

We derived that i.e. there is no pit in . We can label each sentence so that we can refer to them:

With these semantics we could also translate sentences. For example, if the wumpus is in room (3,1), then there is a stench in rooms (2,1), (4,1) and (3,2) can be translated to: .

For example to this figure: It corresponds the following:

• Agent
• Wumpus
• Pits:
• Gold:
• Breezes:
• Stenches:

All other atoms are false.

Initial knowledge base

What the agent knows in the initial configuration

• It is in room (1,1)
• Room (1,1) contains neither a pit nor the Wumpus
• There is no gold in room (1,1)
• There is neither a breeze nor a stench in room (1,1)

Propositional encoding

• for all

Translating knowledge

If the wumpus is in room (3,1) then there is a stench in rooms (2,1), (4,1) and (3,2).

Consider the sentence If there is a pit in room (1,3) then there is a breeze in rooms (1,2), (2,3) and (1,4):

• A pit in room (1,3) is sufficient condition for a breeze in rooms (1,2), (2,3) and (1,4)
• It is not a necessary condition since those breezes could also be caused by pits in other rooms

Hence the correct propositional formula is:

---

graph TD
Title("Propositional Logic")
PDSentences("Sentences")
PDSentencesAtomic("Atomic")
PDSentencesComplex("Complex")
PDConnectives("Connectives")
ConnectiveNot("$$\neg A$$")
ConnectiveConjunction("$$A \land B$$")
ConnectiveDisjunction("$$A \lor B$$")
ConnectiveImplication("$$A \implies B$$")
ConnectiveBidir("$$A \iff B$$")


Title --> PDSentences
PDSentences --> PDSentencesAtomic
PDSentences --> PDSentencesComplex

Title-->PDConnectives
PDConnectives --> ConnectiveNot
PDConnectives --> ConnectiveConjunction
PDConnectives --> ConnectiveDisjunction
PDConnectives --> ConnectiveImplication
PDConnectives --> ConnectiveBidir

PDSentencesAtomic-->PDSemantics("Semantics")
PDSentencesComplex-->PDSemantics
PDSemantics --> TruthTable("Truth Tables")

Propositional Theorem Proving

The first concept is logical equivalence: two sentences and are logically equivalent if they are true in the same set of models, written as .

Alternative definition:

Validity: a sentence is valid if it is true in all models (also known as tautologies).

Deduction theorem:

Satisfability a sentence is satisfiable if it is true in, or satisfied by, some model.

The problem of determining the satisfiability of sentences is called the SAT problem and was the first problem proved to be NP-complete.

Two useful properties connect entailment, validity and satisfability:

• Entailment and validity:
  • for any sentences and : is valid
  • therefore, given a KB and a query : is valid
  • Here KB denotes the conjunction of all premises in the knowledge base
• Entailment and unsatisfability:
  • Inference can also be checked by refutation, or proof by contradiction:
  • is unsatisfiable

Inferences and proofs

Inference is the process of deriving new conclusions from known premises.

Example of Inference

Let P: it is tuesday, Q: It is raining, R: Harry will go for a run

Knowledge Base: Inference:

Model checking is the simplest inference technique given by the already introduced property that is valid. In model checking you systematically enumerate every possible model (world/truth assignement) relevant to the problem and check the truth of the B and query .

Practical inference algorithms often use inference rules instead of explicit model checking.

An inference rule is a standard pattern of reasoning that derives a conclusion from premises with a specific syntactic form. Each rule represents a small reasoning step:

• If the premises match the required pattern,
• Then the conclusion can be added to the knowledge base.

A rule is sound if every conclusion it derives is logically entailed by its premises.

Inference rules are represented as: The following image descrive examples of sound inference rules:

And elimination, And introduction, Or introduction, First De Morgan’s law, Second De Morgan’s law, Double Negation, Modus Ponens

Inference rules can be applied to derive a proof i.e. a chain of conclusions that leads to the desired goal.

Modus Ponens

The best-known rule is called Modus Ponens:

The notation means that, whenever any sentences of the form , and are given, then the sentence can be inferred.

Modus Ponens

If =it is raining, =Harry is inside. Applying modus ponens: That translates to:

And-Elimination

Another useful inference rule is And-Elimination, which says that, from a conjunction, any of the conjuncts can be inferred:

And-Elimination Example

R=Harry is friend with Ron H= Harry is friend with Hermione

Double negation elimination

so a double negation can be removed.

Double Negation Elimination

Let P=Harry passed the test, we want to simplify :

Eliminating implication

Implications can be replaced by disjunctions.

Eliminating implication example

R= It is raining H= Harry is inside If it is raining then harry is inside It is not raining or harry is inside

Biconditional elimination

This follow from biconditional definition.

De Morgan’s Laws

De Morgan's Laws example 1

H = Harry passed the test R = Ron passed the test

De Morgan’s laws is valid also for negation of a disjunction:

De Morgan's Laws example 2

H=Harry passed the test, R= Ron passed the test

These rules can then be used in any particular instances where they apply, generating sound inferences without the need for enumerating models.

Distributive properties

Conjunction distributes over disjunction:

Disjunction distributes over conjunction:

These equivalences are often used as rewrite rules when transforming formulas into normal forms.

Example: Inference Rules in the Wumpus world

Let us see how these inference rules and equivalences can be used in the wumpus world. We start with the knowledge base containing through and show how to prove that (no pits in ):

1. Apply biconditional elimination to to obtain .
2. Apply And-Elimination to to obtain .
3. Logical equivalence for contrapositives gives .
4. Apply Modus Ponens with and the percept (i.e., ), to obtain .
5. Apply De Morgan’s rule, giving the conclusion . That is, neither nor contains a pit.

graph LR
PTR("Propositional Theorem Proving") 
LogicalEquivalence("Logical equivalence")
Validity
Satisfability
Entailment
EntailmentPlusValidity("$$KB \models \alpha \iff (KB \implies \alpha)$$")
EntailmentPlusUnsat("$$KB \models \alpha \iff KB \land \neg \alpha$$")


PTR --> LogicalEquivalence
PTR --> Validity
PTR --> Satisfability
Entailment --> EntailmentPlusValidity
Entailment --> EntailmentPlusUnsat
Validity --> EntailmentPlusValidity
Satisfability --> EntailmentPlusUnsat

Inference --> ModelChecking("Model Checking")
Inference --> InferenceRules("Inference rules$$\; \frac{premises}{conclusions}$$")

InferenceRules --> AndElimination("And Elimination")
InferenceRules --> ModusPonens("Modus Ponens")
InferenceRules--> DoubleNegationElimination("$$\frac{\neg \neg \alpha}{\alpha}$$")
InferenceRules-->RemoveImplication("Remove implication$$\; \alpha \implies \beta \equiv \neg \alpha \lor \beta$$")
InferenceRules --> RemoveBiconditionaL("Remove biconditional")

InferenceRules --> DeMorganLaws("De Morgan Laws")
InferenceRules-->DistributiveProperties("Distributive properties")

Theorem proving as a search problem

Any search problem can be defined by:

• INITIAL STATE: the initial knowledge base.
• ACTIONS: the set of actions consists of all the inference rules applied to all the sentences that match the top half of the inference rule.
• RESULT: the result of an action is to add the sentence in the bottom half of the inference rule.
• GOAL: the goal is a state that contains the sentence we are trying to prove.
• PATH COST FUNCTION: number of inference steps in the proof

Thus, searching for proofs is an alternative to enumerating models.

In many practical cases, a proof can be more efficient than enumeration because the proof can ignore irrelevant propositions, no matter how many of them there are.

One final property of logical systems is monotonicity which says that the set of entailed sentences increases as information is added to the knowledge base.

Proof by resolution

Given a knowledge base 𝐾𝐵 and a query 𝛼, an inference algorithm 𝐴 tries to find a proof:

This means that can be derived from KB by a sequence of inference-rule applications.

A proof is a finite sequence of sentences ending in : where each either is in KB or follows from previous sentences by an inference rule.

We want inference algorithms that are complete:

Search algorithms such as iterative deepening search are complete in the sense that they find any reachable goal. However if the available inference rules are inadequate, then the goal is not reachable—no proof exists that uses only those inference rules.

To prove entailment, resolution uses proof by contradiction:

We introduce:

• a literal is a propositional symbol or its negation:
• A clause is a disjunction of literals:
• A formula is in CNF if it is a conjunction of clauses: .

Note that: is for example and so a formula in CNF would be something like: .

How resolution works: Suppose i have:

or can be inferred from the

Special case is:

That is Modus Ponens.

Resolution Example

• = Ron is in the Great Hall
• is in the Library

Unit Clause: is a clause containing a single literal. It is a special case of resolution, like before:

Unit resolution general form: unit resolution resolves a clause with a unit caluse containing a complementary literal:

The derived clause is called the resolvent.

Intuition:

• makes false
• Therefore, can be removed from the disjunction
• The remaining clause must hold
• This is a generalized version of modus ponens

Resolution is sound: every model satisfying both premises also satisfies the resolvent.

Resolution applies to two clauses that contain complementary literals: and .

General resolution rule:

The complementary literalts and are removed.

Example: G= Ron is in the great hall, = Hermion is in the library, =Harry is sleeping.

Factoring: Resolution may produce clauses containing repeated literals:

Since disjunction is idempotent: , the resolvent can be simplifed by factoring:

Factoring removes duplicate literals from a clause

Empty Clause During the application of inference rules it can happen that we can infer the empty clause, for example:

The empty clause () contains no literals. Since it has no literal that can make it true, the empty clause is always false. Deriving () means that the clause set is unsatisfiable. In resolution-based inference, () represents a contradiction.

Conversion to Conjunction Normal Form (CNF)

Resolution requires formulas to be writen in CNF. Before applying resolution, we transform the KB Into a conjunction class:

1. Eliminate biconditionals → Biconditional elimination
2. Eliminate implications → Eliminating implication
3. Move inward using De Morgan’s Laws e.g
4. Distribute over → Distributive properties

Conversion to CNF example

Convert .

• First eliminate implication:
• Move negation inward using De Morgan’s law:
• Distribute over :
• Final CNF:

Inference by resolution

To determine whether we have to verify that: is unsatisfiable.

Resolution procedure:

• Form
• Convert it to CNF
• Apply resolution repeatedly
• If the empty clause () is derived, then
• If no new clauses can be derived, then

Inference by resolution example

Does entails ?

1. Form KB
2. Consider and from which we obtain
3. Then the KB becomes: , , , ,
4. Now consider and from which we obtain
5. Then we have: , , , ,
6. Then consider and we obtain empty
7. , , , ,
8. Since empty clause is derived, then entails

Horn clauses

Some real-world knowledge bases satisfy certain restrictions on the form of sentences they contain, which enables them to use a more restricted and efficient inference algorithm.

Horn clauses A horn clause is a disjunction of literals with at most one positive literal Example:

Horn clauses can be written as rules:

equivalent to:

Special case:

• ,
• then

Horn clauses support efficient inference.

Forward chaining

Forward chaining is also called data driven inference rule. Suppose the wumpus world: you add facts coming from the agent percept. With these new facts we check if there are any rules for which the premises are true with this fact. This implies what? The conclusion of the rule.

Rules have the form: (See Horn clauses)

Queries are usually atomic and non-negated: .

Both algorithms (forward and backward):

• use Modus Ponens
• are sound
• are complete for atomic queries
• run in time linear in the size of the KB

Forward chaining starts from known facts and repeatedly applies rules:

If all premises are known, infer :

function FORWARD-CHAINING(KB)
repeat
	add every new fact derivable by Modus Ponens
until no new facts can be added

return KB

The algorithm stops when the KB reaches a fixed point.

Example: in the Wumpus World:

• after each move, the agent receives new percepts
• these percpets are added to the KB
• forward chaining derives new facts about the environment, such as which rooms are safe or may contain pits

Forward chaining is widely used in rule-based expert system. It is useful when new data arrive incrementally and many consequences must be derived automatically.

Forward chaining is an example of the general concept of data-driven reasoning—that is, reasoning in which the focus of attention starts with the known data. It can be used within an agent to derive conclusions from incoming percepts, often without a specific query in mind.

Another example Say i know , and my query is ?

Forward chaining derives new facts starting from and . Consider the corresponding set of Horn-clause KB:

Final derived facts: thus is true.

Forward chaining example

Given the Horn-Clause KB:

Facts: Query: ?

Forward chaining derives new facts starting from A and B:

Rule 4 also fires: but is already known Final derived facts: thus .

Backward chaining

Given a Horn-clause 𝐾𝐵 and an atomic query 𝛼, determine whether: . The backward-chaining algorithm, as its name suggests, works backward from the query.

Backward chaining is goal-driven reasoning. It is useful for answering reasoning specific questions such as “What shall I do now?” and “Where are my keys?” Often, the cost of backward chaining is much less than linear in the size of the knowledge base, because the process touches only relevant facts.

function BACKWARD-CHAINING (KB, goal)
	if goal is a known fact in KB then
		return True
	for each rule Beta1 AND ... AND \Betan => goal in KB do
		if for all Beta[i]'s BACKWARD-CHAINING(KB, Beta[i]) = True then
		return true
	return False
		

• Start from the query
• Find rules that could prove it
• Recursively prove their premises as subgoals

Prolog

Prolog is a logic programming language based on goal-directed proof search, closely related to backward chaining.

Backward chaining example - Loan approval

Backward chaining example - Loan approval

We use KB representing loan-approval rules. Query: where means “the loan should be approved”. Other propositional symbols:

• CLLAT satisfactory collaeral
• PYMT ability to repay the loan
• REP good financial reputation
• APP sufficient collateral appraisal
• RATING good credit rating
• INC good, steady income
• BAL excellent balance sheet

The KB contains rules (all Horn clauses) and facts:

1. COLLAT PYMT REP OK
2. APP CLLAT
3. RATING REP
4. INC PYMT
5. BAL REP OK

Consider the facts: APP, RATING, INC, BAL. Goal: prove whether the loan should be approved

A backward-chaining proof can be represented as an AND-OR graph (see AND-OR search trees):

• OR Branches: alternative rules for proving the same goal, any one branch is sufficient
• AND branches: premises of one rule, all subgoals must be proved

In the loan example, the root query is: OK

Initial Query: BACKWARD-CHAINING(KB,OK) Since find rules concluding OK:

• Rule 1
• Rule 5

Both must be proved, so this is an branch

Suppose rule 5 is tried first: Then OK is reduced to two subgoals: .

Let’s prove , we know from rule 3 that and Is present in KB, so is proved.

is not provable and not present in the KB so it returns false.

So the algorithm try the other branch, where it has to prove and .

can be inferred from rule 2 , we can apply modus ponens because is a known fact from KB.

Let’s consider , we have the rule number 4, that , and is a known fact.

Then that we proved to be true before, so this AND node is satisfies and the algorithm stops because we find a rule where all the premises are satisfied, so .

Backward is more efficient because the algorithm stops after the first AND that is proved to be true. While the forward chaining try to generate all the possible facts.

graph TD
Title("Theorem proving as a search problem")
Title--Alternative too-->EnumeratingModels("Enumerating models")
Title--Proof by resolution-->ProofByResolution("$$KB \vdash_A \alpha$$")
ProofByResolution--Property-->ProofByResolutionComplete("Complete")
ProofByResolutionComplete-->ProofByContradiction("$$KB \models \alpha \iff KB \land \neg \alpha \text{ is unsatisfiable}$$")

ProofByContradiction-->How("How does it works")
How -->Literal
How --> Clause
How --> CNF("Conjunction Normal Form") --Apply Modus Ponens-->Resolution
Resolution --> URGF("<small>unit resolution <br> general form</small>")
URGF-->GRR("<small>general resolution rule</small>")

Resolution-->EmptyClause("Empty Clause")

Resolution--Requires-->Conversion("Conversion to CNF") 
Conversion --Apply inference rules--> CNF

EmptyClause --> InferenceByResolution("Inference by resolution")

Clause--disjunction-->HornClauses
InferenceByResolution-->HornClauses
HornClauses-->ForwardChaining("Forward chaining")
HornClauses-->BackwardChaining("Backward chaining")

Exercise - Wumpus World Knowledge Base

Construct a propositional knowledge base for a Wumpus World agent. Your KB should include:

• Propositional symbols
• Rules
• Initial knowledge
• Rules for safety and movement, for example:

At each step, the agent should:

1. add the current percepts to the 𝐾𝐵
2. infer new facts about pits, the Wumpus, and safe cells
3. choose a safe action when possible
4. update its position after moving

Limitations of propositional logic

Propositional logic is useful but it has important limitations

Limited expressive power:

• Atomic sentences are treated as indivisible symbols
• The internal structure of facts cannot be represented
• For example consider proprositional logic can represent: ManSocrates, MortalSocrates but not naturally Man(Socrates), Mortal(Socrates).

If for example i want to reason that Socrates is an individual and an human being, and since he is a human being and so mortal, i cannot use propositional logic in an efficient way, because i have to express every possible cases introducing so many symbols.

No variables or quantifiers

• It cannot express general rules as “All humans are mortal” without listing every individual separately

This is a problem of expressivity but also computational power, the more you introduce the more complex the algorithm becomes.

Lack of conciseness

• Many similar facts require many different propositional symbols
• Example: must all be represented separately.

These limitations motivate first-order logic.

From Propositional to Predicate logic

Propositional logic treats atomic sentences as indivisible symbols.

Predicate logic represents the internal structure of facts:

• Man(Socrates)
• Prime(5)
• Adjacent(Room1, Room2)

It introduces:

• objects e.g. Socrates, Room1
• predicates e.g. Man(x), Prime(x)
• relations e.g., Adjacent(x,y)
• functions e.g. FatherOf(x), Sum(x,y)
• quantifiers e.g. ,

This allows general statements such as: or

Predicate logic is more expressive and more concise than propositional logic.

---