UNIT 3

KNOWLEDGE AND REASONING

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 sentence is expressed in a language called a knowledge representation language and
represents some assertion about the world.
Sometimes we dignify a sentence with the name axiom when the sentence is taken as given
without being derived from other sentences.
There must be a way to add new sentences to the knowledge base and a way to query what is
known. The standard names for these operations are TELL and ASK, respectively.
Both operations may involve inference—deriving new sentences from old.
Inference must obey the requirement that when one ASKs a question of the knowledge base,
the answer should follow from what has been told (or TELLed) to the knowledge base
previously.
The agent maintains a knowledge base, KB, which may initially contain some background
knowledge.
Each time the agent program is called, it does three things.
 First, it TELLs the knowledge base what it perceives.
 Second, it ASKs the knowledge base what action it should perform. In the
process of answering this query, extensive reasoning may be done about the
current state of the world, about the outcomes of possible action sequences,
and so on.
 Third, the agent program TELLs the knowledge base which action was
chosen, and the agent executes the action.

Function of Knowledge based Agent

function KB-AGENT(percept ) returns an action
persistent: KB, a knowledge base
t , a counter, initially 0, indicating time
TELL(KB,MAKE-PERCEPT-SENTENCE(percept , t ))
action ←ASK(KB,MAKE-ACTION-QUERY(t ))
TELL(KB,MAKE-ACTION-SENTENCE(action, t ))
t ←t + 1
return action
 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.
 Finally, MAKE-ACTION-SENTENCE constructs a sentence asserting that the chosen
action was executed.
Various types of approaches in knowledge based agent
A knowledge-based agent can be built simply by TELLing it what it needs to know.
Starting with an empty knowledge base, the agent designer can TELL sentences one by one
until the agent knows how to operate in its environment. This is called the declarative
approach to system building.
In contrast, the procedural approach encodes desired behaviors directly as program code. A
successful agent often combines both declarative and procedural elements in its design, and
that declarative knowledge can often be compile into more efficient procedural code.

THE 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.
The only mitigating feature of this bleak environment is the possibility of finding a heap of
gold. Although the wumpus world is rather tame by modern computer game standards, it
illustrates some important points about intelligence.

The precise definition of the task environment is given, by the PEAS description:
• Performance measure: +1000 for climbing out of the cave with the gold, –1000 for falling
into a pit or being eaten by the wumpus, –1 for each action taken and –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 4×4 grid of rooms. The agent always starts in the square labelled [1,1],
facing to the right. 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 the 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. 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 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 [1,1].
• Sensors: The agent has five sensors, each of which gives a single bit of information:
– In the square containing the wumpus and in the directly (not diagonally) adjacent
 squares, the agent will perceive a Stench.
– In the squares directly adjacent 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 wall, it will perceive a Bump.
– When the wumpus is killed, it emits a woeful Scream that can be perceived
anywhere
in the cave.
Properties of Wumpus Environment
it is discrete, static, and single-agent.
It is 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

Knowledge based Wumpus agent

 Let us watch a knowledge-based wumpus agent exploring the environment shown in
Figure.
 The first percept is [None, None, None, None, None], from which the agent can
conclude that its neighboring squares, [1,2] and [2,1], are free of dangers—they are
OK.
 A cautious agent will move only into a square that it knows to be OK. Let us suppose
the agent decides to move forward to [2,1].
 The agent perceives a breeze (denoted by “B”) in [2,1], so there must be a pit in a
neighboring square. The pit cannot be in [1,1], by the rules of the game, so there must
be a pit in [2,2] or [3,1] or both. Denoted as P?.

 At this point, there is only one known square that is OK and that has not yet been
visited. So the prudent agent will turn around, go back to [1,1], and then proceed to
[1,2].
 The agent perceives a stench in [1,2], resulting in the state of knowledge.
 The stench in [1,2] means that there must be a wumpus nearby.
 wumpus cannot be in [1,1], by the rules of the game, and it cannot be in [2,2] (or the
agent would have detected a stench when it was in [2,1]). Therefore, the agent can
infer that the wumpus is in [1,3]. The notation W! indicates this inference.
 Moreover, the lack of a breeze in [1,2] implies that there is no pit in [2,2]. Yet the
agent has already inferred that there must be a pit in either [2,2] or [3,1], so this means
it must be in [3,1].
  This is a fairly difficult inference, because it combines knowledge gained at different
times in different places and relies on the lack of a percept to make one crucial step.

 The agent has now proved to itself that there is neither a pit nor a wumpus in [2,2], so
it is OK to move there.
 We do not show the agent’s state of knowledge at [2,2];
 we just assume that the agent turns and moves to [2,3], giving us Figure 7.4(b). In
[2,3], the agent detects a glitter, so it should grab the gold and then return home.

LOGIC
Deals with the fundamental concepts of logical representation and reasoning.
knowledge bases consist of sentences.
These sentence are expressed according to the syntax of the representation language.
Eg in arithmentic: x + y = 4 “x4y+ =” is not.
A logic must also define the semantics or meaning of sentences.
The semantics defines the truth of each sentence with respect to each possible world.
Eg: the semantics for arithmetic specifies that the sentence “x + y =4” is true in a world
where x is 2 and y is 2, but false in a world where x is 1 and y is 1.
In standard logics, every sentence must be either true or false in each possible world—there is
no “in between.
The term model is used in place of “possible world.”
If a sentence α is true in model m, we say that m satisfies α or sometimes m is a model of α.
We use the notation M(α) to mean the set of all models of α.
logical reasoning
A sentence follows logically from another sentence. It is called entailment.
In mathematical notation, we write
α |= β
mean that the sentence α entails the sentence β.
The formal definition of entailment is this:
α |= β if and only if, in every model in which α is true, β is also true. Using the notation just

α |= β if and only if M(α) ⊆ M(β) .

introduced, we can write

eg: the sentence x = 0 entails the sentence xy = 0. Obviously, in any model where x is zero, it
is the case that xy is zero.
Eg with Wumpus world:
The agent has detected nothing in [1,1] and a breeze in [2,1]. These percepts, combined with
the agent’s knowledge of the rules of the wumpus world, constitute the KB. The agent is
interested in whether the adjacent squares [1,2], [2,2], and [3,1] contain pits. Each of the three
squares might or might not contain a pit, so (for the purposes of this example) there are 2
3
=8possible models.
The KB can be thought of as a set of sentences or as a single sentence that asserts all the
individual sentences. The KB is false in models that contradict what the agent knows.
the KB is false in any model in which [1,2] contains a pit, because there is no breeze in [1,1].
There are in fact just three models in which the KB is true.

We have surrounded the models of α1 and α2 with dotted lines in Figures 7.5(a) and 7.5(b),
respectively. By inspection, we see the following:
in every model in which KB is true, α1 is also true.
Hence, KB |= α1: there is no pit in [1,2].
We can also see that in some models in which KB is true, α2 is false.
Hence, KB V=α2: the agent cannot conclude that there is no pit in [2,2].
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.
The inference algorithm illustrated in Figure 7.5 is called model checking, because it
enumerates

M(KB) ⊆ M(α)
all possible models to check that α is true in all models in which KB is true, that is,

If an inference algorithm i can derive α from KB, we write

KB ˫i α ,
which is pronounced “α is derived from KB by i” or “i derives α from KB.”
Properties of inference algorithm
 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.
  The final issue to consider is grounding—the connection between logical reasoning
processes and the real environment in which the agent exists. The agent’s sensors
create the connection.
Eg: our wumpus-world agent has a smell 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. Thus, the meaning and truth of percept sentences are
defined by the processes of sensing and sentence construction that produce them.

PROPOSITIONAL LOGIC
It is a simple but powerful logic called propositional logic.
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.
We use symbols that start with an uppercase letter and may contain other letters or subscripts,
for example: P, Q, R, W1,3 and North. W1,3 to stand for the proposition that the wumpus is
in [1,3].
There are two proposition symbols with fixed meanings: True is the always-true proposition
and False is the always-false proposition.
Complex sentences are constructed from simpler sentences, using parentheses and logical
connectives.
There are five connectives in common use:
1. ￢ (not). A sentence such as ￢W1,3 is called the negation of W1,3. A literal is either
an atomic sentence (a positive literal) or a negated atomic sentence (a negative

2. ∧ (and). A sentence whose main connective is ∧, such as W1,3 ∧ P3,1, is called a

literal).

3. ∨ (or). A sentence using ∨, such as (W1,3∧P3,1)∨W2,2, is a disjunction of the

conjunction; its parts are the conjuncts.

disjuncts (W1,3 ∧ P3,1) and W2,2.

4. ⇒ (implies). A sentence such as (W1,3∧P3,1) ⇒ ￢W2,2 is called an implication (or
conditional). Its premise or antecedent is (W1,3 ∧P3,1), and its conclusion or

5. ⇔ (if and only if). The sentence W1,3 ⇔ ￢W2,2 is a biconditional. Some other
consequent is ￢W2,2. Implications are also known as rules or if–then statements.

The “not” operator (￢) has the highest precedence, which means that in the sentence ￢A ∧ B
books write this as ≡.

the ￢ binds most tightly, giving us the equivalent of (￢A)∧B rather than ￢(A∧B)
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 fixes the truth value—true or false—for every
proposition symbol.
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.
Atomic sentences are easy:
• True is true in every model and False is false in every model.
• The truth value of every other proposition symbol must be specified directly in the model.
For example, in the model m1 given earlier, P1,2 is false.
For complex sentences, we have five rules, which hold for any subsentences P and Q in any
model m (here “iff” means “if and only if”):

• P ∧ Q is true iff both P and Q are true in m.

• ￢P is true iff P is false in m.

• P ∨ Q is true iff either P or Q is true in m.

• P ⇒ Q is true unless P is true and Q is false in m.
• P ⇔ Q is true iff P and Q are both true or both false in m.
The rules can also be expressed with truth tables that specify the truth value of a complex
sentence for each possible assignment of truth values to its components.

A simple knowledge base

we can construct a knowledge base for the wumpus world. We focus first on the immutable
aspects of the wumpus world.
For now, we need the following symbols for each [x, y] location:
Px,y is true if there is a pit in [x, y].
Wx,y is true if there is a wumpus in [x, y], dead or alive.
Bx,y is true if the agent perceives a breeze in [x, y].
 Sx,y is true if the agent perceives a stench in [x, y].
The sentences we write will suffice to derive ￢P1,2 (there is no pit in [1,2]), as was done
informally in Section 7.3. We label each sentence Ri so that we can refer to them:
• There is no pit in [1,1]:
R1 : ￢P1,1 .
• A square is breezy if and only if there is a pit in a neighboring square. This has to be stated

R2 : B1,1 ⇔ (P1,2 ∨ P2,1) .

for each square; for now, we include just the relevant squares:

R3 : B2,1 ⇔ (P1,1 ∨ P2,2 ∨ P3,1) .

• The preceding sentences are true in all wumpus worlds. Now we include the breeze percepts
for the first two squares visited in the specific world the agent is in, leading up to the situation
in Figure 7.3(b).
R4 : ￢B1,1 .
R5 : B2,1 .
A simple inference procedure
 Our goal now is to decide whether KB |= α for some sentence α.
Here are some examples of sound rules of inference
 A rule is sound if its conclusion is true whenever the premise is true

We will discuss the knowledge base representation and a method to find the wumpus using
propositional logic representation.
 From the following figure assume that the agent has reached the square (1,2)

The Knowledge Base: The agent percepts are converted into sentences and entered into the
knowledge base, with some valid sentences that are entailed by the percept sentences
 From the above figure we can perceive the following percept sentences and it is added to
the knowledge base.
The rule of three squares,

Finding the wumpus as, We can prove that the Wumpus is in (1, 3) using the four
rules given.

 A general algorithm for deciding entailment in propositional logic is shown in Figure

7.10.
 The algorithm is sound because it implements directly the definition of entailment,
and complete because it works for any KB and α and always terminates—there are
only finitely many models to examine.
Properties of Propositional logic:
 Propositional logic is a declarative language because its semantics is based on a truth
relation between sentences and possible worlds.
 It also has sufficient expressive power o deal with partial information, using
disjunction and negation.
 Propositional logic has a third property that is desirable in representation languages,

a function of the meaning of its parts. For example, the meaning of “S1,4 ∧ S1,2” is
namely, compositionality. In a compositional language, the meaning of a sentence is

related to the meanings of “S1,4” and “S1,2.”

FIRST-ORDER LOGIC
 First-Order Logic is a logic which is sufficiently expressive to represent a good deal of
our common sense knowledge.
 It is also either includes or forms the foundation of many other representation languages.
 It is also called as First-Order Predicate calculus.
 It is abbreviated as FOL or FOPC
 FOL adopts the foundation of propositional logic with all its advantages to build a more
expressive logic on that foundation, borrowing representational ideas from natural
language while avoiding its drawbacks
 The Syntax of natural language contains elements such as,
 Nouns and noun phrases that refer to objects (Squares, pits, rumpuses)
 Verbs and verb phrases that refer to among objects ( is breezy, is adjacent to)
 Some of these relations are functions-relations in which there is only one “Value” for a
given “input”.
 For Example,
 Objects: People, houses, numbers
 Relations: These can be unary relations or properties such as red, round, More generally
n-ary relations such as brother of, bigger than,
 Functions: father of, best friend,…
 Indeed, almost any assertion can be thought of as referring to objects and properties or
relations
 For Example, in the way of Sentence “ One plus Two is Three”
 Where,
o Objects: One, Two, Three, One plus Two
o Relations: equals
o Function: plus
 Ontological commitment of First-Order logic language is “Facts”, “Objects”, and
“Relations”.
 Where ontological commitment means “WHAT EXISTS IN THE WORLD”.
 Epistemological Commitment of First-Order logic language is “True”, “False”, and
 “Unknown”.
 Where epistemological commitment means “WHAT AN AGENT BELIEVES ABOUT
FACTS”.
Advantages:
  It has been so important to mathematics, philosophy, and Artificial Intelligence
precisely because those fields can be usefully thought of as dealing with objects and the
relations among them.
  It can also express facts about some or all of the objects in the universe.
  It enables one to represent general laws or rules, such as the statement “Squares
neighboring the wumpus are smelly”.
Syntax and Semantics of First-Order Logic:
The models of a logical language are the formal structures that constitute the possible worlds
under consideration.
 Models for propositional logic are just sets of truth values for the proposition symbols.
 Models for first-order logic are more interesting.
 First they have objects in them.
 The domain of a model is the set of objects it contains; these objects are sometimes
called domain elements.
 The following diagram shows a model with five objects

The five objects are,

 Richard the Lionheart
 His younger brother
 The evil King John
 The left legs of Richard and John
 A crown
 The objects in the model may be related in various ways, In the figure Richard and
John are brothers.
 Formally speaking, a relation is just the set of tuples of objects that are related.
 A tuple is a collection of Objects arranged in a fixed order and is written with angle
brackets surrounding the objects.
 Thus, the brotherhood relation in this model is the set
{(Richard the Lionheart, King John),(King John, Richard the Lionheart)}
 The crown is on King John’s head, so the “on head” relation contains just one tuple, (the
crown, King John).
 The relation can be binary relation relating pairs of objects (Ex:- “Brother”) or unary
relation representing a common object (Ex:- “Person” representing both Richard and John).
Certain kinds of relationships are best considered as functions that relates an object to exactly
one object.
 For Example:- each person has one left leg, so the model has a unary “left leg”
function that includes the following mappings (Richard the Lionheart) ----> Richard’s left leg
(King John) ----> John’s left leg
 Symbols and Interpretations:
 The basic syntactic elements of first-order logic are the symbols that stand for
objects, relations and functions
 Kinds of Symbols
 The symbols come in three kinds namely,
 Constant Symbols standing for Objects (Ex:- Richard)
 Predicate Symbols standing for Relations (Ex:- King)
 Function Symbols stands for functions (Ex:- LeftLeg)
o Symbols will begin with uppercase letters
o The choice of names is entirely up to the user
o Each predicate and function symbol comes with an arity
o Arity fixes the number of arguments.
 The semantics must relate sentences to models in order to determine truth.
 To do this, an interpretation is needed specifying exactly which objects, relations
and functions are referred to by the constant, predicate and function symbols.
 One possible interpretation called as the intended interpretation- is as follows;
 Richard refers to Richard the Lionheart and John refers to the evil King John.
 Brother refers to the brotherhood relation, that is the set of tuples of objects given in
equation {(Richard the Lionheart, King John),(King John, Richard the Lionheart)}
 OnHead refers to the “on head” relation that holds between the crown and King John;
Person, King and Crown refer to the set of objects that are persons, kings and crowns.
 Leftleg refers to the “left leg” function, that is, the mapping given in
{(Richard the Lionheart, King John),(King John, Richard the
Lionheart)}
There are many other possible interpretations relating these symbols to this particular model.
 The truth of any sentence is determined by a model and an interpretation for the sentence
symbols.
 The syntax of the FOL with equality specified in BNF is as follows
Where,
 Terms:
Λ Logical Conjunction

∀ Universal Quantification
V Logical disjunction

∃ Existential Quantification
⇔ Material Equivalence
⇒ Material Implication
 A Term is a logical expression that refers to an object
 Constant symbol are therefore terms, but it is not always convenient to have a distinct
symbol to name every object.
 For Example:- in English we might use the expression “King Johns left leg” rather than
giving a name to his leg.
A complex term is formed by a function symbol followed by a parenthesized list of terms as
arguments to the function symbol.
 It is just like a complicated kind of name. It’s not a “subroutine call” that returns a
value”.
 The formal semantics of terms is straight forward, Consider a term f(t1……tn)
Where
f- some function in the model (call it F)
The argument terms – objects in the domain
The term – object that is the value of the function F applied to the domain
  For Example:- suppose the LeftLeg function symbol refers to the function is,
(Richard the Lionheart) ------ Richards left leg
(King John ) ------ Johns left leg
John refers to King John, then LeftLeg (John) refers to king Johns left leg.
 In this way the Interpretation fixes the referent of every term.
 Atomic Sentences:-
 An atomic sentence is formed from a predicate symbol followed by a
parenthesized list of terms:
Brother (Richard, John)
 This states that Richard the Lionheart is the brother of King John.
 Atomic Sentences can have complex terms as arguments.
 Thus, Married(Father(Richard), Mother(John)) states that Richard the
Lionheart’s father is married to King John’s mother
 An atomic sentence is true in a given model, under a given interpretation, if the
relation referred to by the predicate symbol holds among the objects referred to by the
arguments.
 Complex Sentences:-
 Logical connectives can be used to construct more complex sentences, just as in
propositional calculus.
 The semantics of sentences formed with logical connectives is identical to that in
the propositional case.
¬ Brother (LeftLeg (Richard), John)
Brother (Richard, John) Λ Brother (John, Richard)

¬ King (Richard) ⇒ King (John)

King (Richard) V King (John)

¬ it refers “ Logical Negation”

 Quantifiers:-
 Quantifiers are used to express properties of entire collections of objects, instead of
enumerating the objects by name if a logic that allows object is found.
 It has two type,
 The following are the types of standard quantifiers,
 Universal
 Existential
 Universal Quantification (∀):-
 Universal Quantification make statement about every object.

∀x king (x) ⇒ Person (x)

 “All Kings are persons”, is written in first-order logic as

 ∀ is usually pronounced “For all….”, Thus the sentences says , “For all x, if x is a
king, then x is a person”.
 The symbol x is called a variable.
 A variable is a term all by itself, and as such can also serve as the argument of a
function-for example, LeftLeg(x).
 A term with no variables is called a ground term.
 Based on our model, we can extend the interpretation in five ways, x --------- Richard the
Lionheart
x --------- King John
x --------- Richard’s Left leg x --------- John’s Left leg
x --------- the crown
 The universally quantified sentence is equivalent to asserting the following five
sentences
 Richard the Lionheart ------ Richard the Lionheart is a person
King John is a King ------ King John is a Person
Richard’s left leg is King -------- Richard’s left leg is a person John’s left leg is a King --------
John’s left leg is a person The crown is a King -------- The crown is a Person
 Existential Quantification (∃):-
 An existential quantifier is used make a statement about some object in the

 To say, for example :- that King John has a crown on his head, write ∃x crown
universe without naming it.

 ∃x is pronounced “ There exists an x such that..,” or “For some x..”

(x) Λ OnHead (x, John).

∃x crown (x) ⇒ OnHead (x,John)

 Consider the following sentence,

 Applying the semantics says that at least one of the following assertion is true,
Richard the Lionheart is a crown Λ Richard the Lionheart is on John’s head
King John is Crown Λ King John is on John’s head Richard’s left leg is a crown Λ Richard’s
left leg is on John’s head John’s left leg is a crown Λ John’s left leg is on John’s head The
crown is a crown Λ The crown is on John’s head
 Now an implication is true if both premise and conclusion are true, or if its premise is
false.
 Nested Quantifiers:-
 More complex sentences are expressed using multiple quantifiers.
 The following are the some cases of multiple quantifiers,
 The simplest case where the quantifiers are of the same type.

∀x ∀y, Brother (x,y) ⇒ sibling (x,y)

 For Example:- “Brothers are Siblings” can be written as

 Consecutive quantifiers of the same type can be written as one quantifier with
several variables.

∀x ,y sibling (x,y) ⇔ sibling (y,z)

 For Example:- to say that siblinghood is a symmetric relationship as

 In some cases it is possible to have mixture of quantifiers.

 For Example:- “Everybody loves somebody” means that for every person, there is

∀x ∃y Loves (x, y).

someone that person loves:

 On the other hand , to say “There is someone who is loved by everyone”, we can

∃y ∀x Loves (x, y).

write as

 Connections between ∀ and ∃

 The two quantifiers are actually intimately connected with each other , through
negation,
 Declaring that everyone dislikes parsnips is the same as declaring there does not exist

∀x ¬ Likes (x, Parsnips) is equivalent to ¬ ∃x Likes (x, Parsnips)

someone who likes them, and vice versa:

 Going one step further: “Everyone likes ice cream” means that there os no one

∀x ¬ Likes (x, IceCream) is equivalent to ¬ ∃x Likes (x, IceCream)

who does not like ice cream:

 Because ∀ is really a conjunction over the universe of objects ∃ is a

disjunction, it should not be surprising that they obey de Morgan’s rules.
 The de Morgan’s rules for quantified and un-quantified sentences are as
follows:
∀x ¬ P ≡ ¬ ∃x P ¬ P Λ ¬ Q ≡ ¬ (P V Q)
 ≡ it refers definition

¬ ∀x P ≡ ∃x ¬ P ¬ (P Λ Q) ≡ ¬ P V ¬ Q
∀x P ≡ ¬ ∃x ¬ P P Λ Q ≡ ¬ (¬ P V ¬ Q)
∃x P ≡ ¬ ∀x ¬P P V Q ≡ ¬ (¬ P Λ ¬ Q )
 Equality:-
 First – order logic includes one more way of using equality symbol to make atomic
sentences.
 Use of equality symbol
 The equality symbol can be used to make statements to the effect that two terms refer to
the same object.
 For Example: - Father (John) = Henry says that the object referred to by
Father (John) and the object referred to by Henry are the same.
 Determining the truth of an equality sentence is simply a matter of seeing that the referents
of the two terms are the same object.
 The equality symbol can be used to state facts about a given function
 It can also be used with negation to insist that two terms are not the same object.

∃x,y Brother(x, Richard) Λ Brother(y,Richard) Λ ¬ (x = y)

 For Example:- To say that Richard has at least two brothers, write as

 The Wumpus World:-

 The first order axioms of wumpus world are more concise, capturing in a natural way
what exactly we want to represent the concept.
 Here the more interesting question is “how an agent should organize what it knows in
order to take the right actions”.
 For this purpose we will consider three agent architectures:
 Reflex agents - classify their percept and act accordingly
 Model based agents - construct an internal representation of the
World and use it to act
 Goal based agents - form goals and try to achieve them
 The first step of wumpus world agent construction is to define the interface between the
environment and the agent.
 The percept sentence must include both the percept and the time at which it occurred, to
differentiate between the consequent percepts.
 For Example:-
Percept ([Stench, Breeze, Glitter, None, None], 3)
 In this sentence
Percept – predicate
Stench, Breeze, Glitter - Constants
3 - Integer to represent to time.
 The agents action are,
Turn (Right)
Turn (Left)
Forward
Shoot
Grab Release Climb

∃a BestActions(a,5)
 To determine which is best, the agent program constructs a query such as

 ASK solves this query and returns a binding list such as {a/Grab}.
 The agent program then calls TELL to record the action which was taken to
update the Knowledge base KB.
Introduction to PROLOG
 Prolog as the name itself suggests, is the short form of LOGical PROgramming. It is a
logical and declarative programming language.
 Logic Programming is one of the Computer Programming Paradigm, in which the
program statements express the facts and rules about different problems within a system
of formal logic.
 Here, the rules are written in the form of logical clauses, where head and body are
present. For example, H is head and B1, B2, B3 are the elements of the body. Now if we
state that “H is true, when B1, B2, B3 all are true”, this is a rule. On the other hand, facts
are like the rules, but without any body. So, an example of fact is “H is true”.
Some logic programming languages are given below −
 ALF (algebraic logic functional programming language).
 ASP (Answer Set Programming)
 CycL
 Datalog
 FuzzyCLIPS
 Janus
 Parlog
 Prolog
 Prolog++
 ROOP

Logic and Functional Programming

 We will discuss about the differences between Logic programming and the traditional
functional programming languages. We can illustrate these two using the below
diagram −


  Now let us see some more differences below −

Functional Programming Logic Programming

Functional Programming follows the Von- Logic Programming uses abstract model, or deals
Neumann Architecture, or uses the sequential with objects and their relationships.
steps.

The syntax is actually the sequence of The syntax is basically the logic formulae (Horn
statements like (a, s, I). Clauses).

The computation takes part by executing the It computes by deducting the clauses.
statements sequentially.

Logic and controls are mixed together. Logics and controls can be separated.

What is Prolog?
Prolog or PROgramming in LOGics is a logical and declarative programming language.
It is one major example of the fourth generation language that supports the declarative
programming paradigm.
This is particularly suitable for programs that involve symbolic or non-numeric
computation.
This is the main reason to use Prolog as the programming language in Artificial Intelligence,
where symbol manipulation and inference manipulation are the fundamental tasks.
Prolog language basically has three different elements −
Facts − The fact is predicate that is true, for example, if we say, “Tom is the son of Jack”,
then this is a fact.
Rules − Rules are extinctions of facts that contain conditional clauses. To satisfy a rule these
conditions should be met. For example, if we define a rule as −
grandfather(X, Y) :- father(X, Z), parent(Z, Y)
This implies that for X to be the grandfather of Y, Z should be a parent of Y and X should be
father of Z.
Questions − And to run a prolog program, we need some questions, and those questions can
be answered by the given facts and rules.

Some Applications of Prolog

Prolog is used in various domains. It plays a vital role in automation system. Following are
some other important fields where Prolog is used −
 Intelligent Database Retrieval
 Natural Language Understanding
 Specification Language
  Machine Learning
 Robot Planning
 Automation System
 Problem Solving
The different topics that will be covered in this chapter are −
Knowledge Base − This is one of the fundamental parts of Logic Programming. We will see
in detail about the Knowledge Base, and how it helps in logic programming.
Facts, Rules and Queries − These are the building blocks of logic programming. We will
get some detailed knowledge about facts and rules, and also see some kind of queries that
will be used in logic programming.
Here, we will discuss about the essential building blocks of logic programming. These
building blocks are Facts, Rules and the Queries.

Facts
We can define fact as an explicit relationship between objects, and properties these objects
might have. So facts are unconditionally true in nature. Suppose we have some facts as given
below −
 Tom is a cat
 Kunal loves to eat Pasta
 Hair is black
 Nawaz loves to play games
 Pratyusha is lazy.
So these are some facts, that are unconditionally true. These are actually statements, that we
have to consider as true.
Following are some guidelines to write facts −
 Names of properties/relationships begin with lower case letters.
 The relationship name appears as the first term.
 Objects appear as comma-separated arguments within parentheses.
 A period "." must end a fact.
 Objects also begin with lower case letters. They also can begin with digits (like
1234), and can be strings of characters enclosed in quotes e.g. color(penink,
‘red’).
 phoneno(agnibha, 1122334455). is also called a predicate or clause.
Syntax
The syntax for facts is as follows −
relation(object1,object2...).
Example
Following is an example of the above concept −
cat(tom).
loves_to_eat(kunal,pasta).
of_color(hair,black).
loves_to_play_games(nawaz).
lazy(pratyusha).

Rules
We can define rule as an implicit relationship between objects. So facts are conditionally true.
So when one associated condition is true, then the predicate is also true. Suppose we have
some rules as given below −
 Lili is happy if she dances.
 Tom is hungry if he is searching for food.
 Jack and Bili are friends if both of them love to play cricket.
 will go to play if school is closed, and he is free.
So these are some rules that are conditionally true, so when the right hand side is true, then
the left hand side is also true.
Here the symbol ( :- ) will be pronounced as “If”, or “is implied by”. This is also known as
neck symbol, the LHS of this symbol is called the Head, and right hand side is called Body.
Here we can use comma (,) which is known as conjunction, and we can also use semicolon,
that is known as disjunction.
Syntax
rule_name(object1, object2, ...) :- fact/rule(object1,
object2, ...)
Suppose a clause is like :
P :- Q;R.
This can also be written as
P :- Q.
P :- R.

If one clause is like :

P :- Q,R;S,T,U.

Is understood as
P :- (Q,R);(S,T,U).
Or can also be written as:
P :- Q,R.
P :- S,T,U.
Example
happy(lili) :- dances(lili).
hungry(tom) :- search_for_food(tom).
friends(jack, bili) :- lovesCricket(jack), lovesCricket(bili).
goToPlay(ryan) :- isClosed(school), free(ryan).

Queries
Queries are some questions on the relationships between objects and object properties. So
question can be anything, as given below −
 Is tom a cat?
 Does Kunal love to eat pasta?
 Is Lili happy?
  Will Ryan go to play?
So according to these queries, Logic programming language can find the answer and return
them.

Knowledge Base in Logic Programming

In this section, we will see what knowledge base in logic programming is.
Well, as we know there are three main components in logic programming − Facts,
Rules and Queries. Among these three if we collect the facts and rules as a whole then that
forms a Knowledge Base. So we can say that the knowledge base is a collection of facts
and rules.
Now, we will see how to write some knowledge bases. Suppose we have our very first
knowledge base called KB1. Here in the KB1, we have some facts. The facts are used to state
things, that are unconditionally true of the domain of interest.
Knowledge Base 1
Suppose we have some knowledge, that Priya, Tiyasha, and Jaya are three girls, among them,
Priya can cook. Let’s try to write these facts in a more generic way as shown below −
girl(priya).
girl(tiyasha).
girl(jaya).
can_cook(priya).
Note − Here we have written the name in lowercase letters, because in Prolog, a string
starting with uppercase letter indicates a variable.
Now we can use this knowledge base by posing some queries. “Is priya a girl?”, it will reply
“yes”, “is jamini a girl?” then it will answer “No”, because it does not know who jamini is.
Our next question is “Can Priya cook?”, it will say “yes”, but if we ask the same question for
Jaya, it will say “No”.
Output
GNU Prolog 1.4.5 (64 bits)
Compiled Jul 14 2018, 13:19:42 with x86_64-w64-mingw32-gcc
By Daniel Diaz
Copyright (C) 1999-2018 Daniel Diaz
| ?- change_directory('D:/TP Prolog/Sample_Codes').

yes
| ?- [kb1]
.
compiling D:/TP Prolog/Sample_Codes/kb1.pl for byte code...
D:/TP Prolog/Sample_Codes/kb1.pl compiled, 3 lines read - 489 bytes written, 10 ms

yes
| ?- girl(priya)
.

yes
| ?- girl(jamini).

no
| ?- can_cook(priya).

yes
| ?- can_cook(jaya).

no
| ?-

Relations in Prolog
In Prolog programs, it specifies relationship between objects and properties of the objects.
Suppose, there’s a statement, “Amit has a bike”, then we are actually declaring the ownership
relationship between two objects — one is Amit and the other is bike.
If we ask a question, “Does Amit own a bike?”, we are actually trying to find out about one
relationship.
There are various kinds of relationships, of which some can be rules as well. A rule can find
out about a relationship even if the relationship is not defined explicitly as a fact.
We can define a brother relationship as follows −
Two person are brothers, if,
 They both are male.
 They have the same parent.
Now consider we have the below phrases −
 parent(sudip, piyus).
 parent(sudip, raj).
 male(piyus).
 male(raj).
 brother(X,Y) :- parent(Z,X), parent(Z,Y),male(X), male(Y)
These clauses can give us the answer that piyus and raj are brothers, but we will get three
pairs of output here. They are: (piyus, piyus), (piyus, raj), (raj, raj). For these pairs, given
conditions are true, but for the pairs (piyus, piyus), (raj, raj), they are not actually brothers,
they are the same persons. So we have to create the clauses properly to form a relationship.
The revised relationship can be as follows −
A and B are brothers if −
 A and B, both are male
 They have same father
 They have same mother
 A and B are not same

Family Relationship in Prolog

Here we will see the family relationship. This is an example of complex relationship that can
be formed using Prolog. We want to make a family tree, and that will be mapped into facts
and rules, then we can run some queries on them.
Suppose the family tree is as follows −

Here from this tree, we can understand that there are few relationships. Here bob is a child of
pam and tom, and bob also has two children — ann and pat. Bob has one brother liz, whose
parent is also tom. So we want to make predicates as follows −
Predicates
 parent(pam, bob).
 parent(tom, bob).
 parent(tom, liz).
 parent(bob, ann).
 parent(bob, pat).
 parent(pat, jim).
 parent(bob, peter).
 parent(peter, jim).
From our example, it has helped to illustrate some important points −
 We have defined parent relation by stating the n-tuples of objects based on the
given info in the family tree.
 The user can easily query the Prolog system about relations defined in the
program.
 A Prolog program consists of clauses terminated by a full stop.
 The arguments of relations can (among other things) be: concrete objects, or
constants (such as pat and jim), or general objects such as X and Y. Objects of
the first kind in our program are called atoms. Objects of the second kind are
called variables.
 Questions to the system consist of one or more goals.
Some facts can be written in two different ways, like sex of family members can be written in
either of the forms −
  female(pam).
 male(tom).
 male(bob).
 female(liz).
 female(pat).
 female(ann).
 male(jim).
Or in the below form −
 sex( pam, feminine).
 sex( tom, masculine).
 sex( bob, masculine).
 … and so on.
Now if we want to make mother and sister relationship, then we can write as given below −

In Prolog syntax, we can write −

 mother(X,Y) :- parent(X,Y), female(X).
 sister(X,Y) :- parent(Z,X), parent(Z,Y), female(X), X \== Y.
Now let us see the practical demonstration −
Knowledge Base (family.pl)
female(pam).
female(liz).
female(pat).
female(ann).
male(jim).
male(bob).
male(tom).
male(peter).
parent(pam,bob).
parent(tom,bob).
parent(tom,liz).
parent(bob,ann).
parent(bob,pat).
parent(pat,jim).
parent(bob,peter).
parent(peter,jim).
mother(X,Y):- parent(X,Y),female(X).
father(X,Y):- parent(X,Y),male(X).
haschild(X):- parent(X,_).
sister(X,Y):- parent(Z,X),parent(Z,Y),female(X),X\==Y.
brother(X,Y):-parent(Z,X),parent(Z,Y),male(X),X\==Y.
Output
| ?- [family].
compiling D:/TP Prolog/Sample_Codes/family.pl for byte code...
D:/TP Prolog/Sample_Codes/family.pl compiled, 23 lines read - 3088 bytes written, 9 ms

yes
| ?- parent(X,jim).

X = pat ? ;

X = peter

yes
| ?-
mother(X,Y).

X = pam
Y = bob ? ;

X = pat
Y = jim ? ;

no
| ?- haschild(X).

X = pam ? ;

X = tom ? ;

X = tom ? ;

X = bob ? ;

X = bob ? ;

X = pat ? ;

X = bob ? ;

X = peter

yes
| ?- sister(X,Y).

X = liz
Y = bob ? ;

X = ann
Y = pat ? ;

X = ann
Y = peter ? ;

X = pat
Y = ann ? ;

X = pat
Y = peter ? ;

(16 ms) no
| ?-