Artificial

Intelligence

Unit 4: First Order Logic

& Inference in First Order Logic

Compiled by:Kanchan Taksale

[Link]@[Link]

Vidyalankar School
of Information
Technology
Wadala (E),
Mumbai
[Link]
 Certificate

This is to certify that the e-book titled “Artificial Intelligence” comprises all
elementary learning tools for a better understating of the relevant concepts. This
e-book is comprehensively compiled as per the predefined eight parameters and
guidelines.

Date: 3-08-2022

[Link] Taksale
Department of IT & DS

DISCLAIMER: Theinformation contained in this e-book is compiledand

distributedforeducationalpurposesonly. Thise-book has beendesignedto help
learners understand relevant concepts with amore dynamicinterface.
The compilers of this e-book and Vidyalankar School of Information technology
give full and due credit to the authors of the contents, developers and all websites
from wherever information has been sourced. We acknowledge ourgratitude
towardsthewebsites YouTube, Wikipedia, and Google search engine. No
commercial benefits are being drawn from this project.
 Unit IV: First Order Logic and Inference in First Order Logic

Contents:
First Order Logic
• Syntax and semantics,
• Using First Order Logic
• Knowledge engineering in First Order Logic.

Inference in First Order Logic:

• propositional vs. First Order
• Unification and lifting
• Forward and backward chaining
• Resolution.

Recommended Books
• Artificial Intelligence: A Modern Approach , Stuart Russel and Peter Norvig
• A First Course in Artificial Intelligence, Deepak Khemani

Prerequisites and Linking

Unit IV Pre- requisites Linking

First Order Sem. I Sem. II Sem. III Sem. IV Sem. V Sem. VI

Logic
and - - Python Core Java - Business
Inference in Programming Intelligence
First Order
Logic
 First-Order logic.

• 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.

Fig 1 First Order Logic

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:
o Objects: A, B, people, numbers, colors, wars, theories, squares, pits, wumpus,
......
o 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
o Function: Father of, best friend, third inning of, end of, ......
• As a natural language, first-order logic also has two main parts:
o Syntax
o 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.

Following are the basic elements of FOL syntax:

Constant 1, 2, A, John, Mumbai, cat,....

Variables x, y, z, a, b,....
Predicates Brother, Father, >,....
Function sqrt, LeftLegOf, ....
Connectives ∧, ∨, ¬, ⇒, ⇔
Equality ==
Quantifier ∀, ∃
 Introduction to First Order Logic

Introduction to First Order Logic: [Link]

Quantifiers in First-order logic?

• A quantifier is a language element which generates quantification, and quantification

specifies the quantity of specimen in the universe of discourse.
• These are the symbols that permit to determine or identify the range and scope of the
variable in the logical expression. There are two types of quantifier:
1. Universal Quantifier, (for all, everyone, everything)
2. Existential quantifier, (for some, at least one).

Universal Quantifier with example.

Universal quantifier is a symbol of logical representation, which specifies that the statement
within its range is true for everything or every instance of a particular thing.

The Universal quantifier is represented by a symbol ∀, which resembles an inverted A.

If x is a variable, then ∀x is read as:

• For all x
• For each x
• For every x.

Example:

All man drink coffee.

Let a variable x which refers to a cat so all x can be represented in UOD as below:
 Fig 2 Universal Quantifier

∀x man(x) → drink (x, coffee).

It will be read as: There are all x where x is a man who drink coffee.

Existential Quantifier with example.

Existential quantifiers are the type of quantifiers, which express that the statement within its
scope is true for at least one instance of something.

It is denoted by the logical operator ∃, which resembles as inverted E. When it is used with a
predicate variable then it is called as an existential quantifier.

If x is a variable, then existential quantifier will be ∃x or ∃(x). And it will be read as:

• There exists a 'x.'

• For some 'x.'
• For at least one 'x.'

Example:

Some boys are intelligent.

 Fig 3 Existential Quantifier

∃x: boys(x) ∧ intelligent(x)

It will be read as: There are some x where x is a boy who is intelligent.

Objects, Relations and functions with example. Objects:

1) When we look at the syntax of natural language, the most obvious elements are nouns
and noun phrases that refer to objects.
2) E.g.:- people, houses, numbers, theories, Ronald McDonald, colors, baseball games,
wars, centuries.

Relation:
1) Verbs and verb phrases that refer to relations among objects (is breezy, is adjacent to,
shoots).
2) E.g.:- these can be unary relations or properties such as red, round, bogus, prime,
multistoried ..., or more general n-ary relations such as brother of, bigger than, inside,
part of, has color, occurred after, owns, comes between.

Functions:
1) Relations in which there is only one “value” for a given “input.
2) E.g.:- father of, best friend, third inning of, one more than, beginning of.

Example:
“One plus two equals three.” Objects: one, two, three, one plus two; Relation: equals;
Function: plus. (“One plus two” is a name for the object that is obtained by applying the
function “plus” to the objects “one” and “two.” “Three” is another name for this object.)
• “Squares neighboring the wumpus are smelly.” Objects: wumpus, squares; Property:
smelly; Relation: neighboring.
• “Evil King John ruled England in 1200.” Objects: John, England, 1200; Relation: ruled;
 Properties: evil, king.

Formal languages and their ontological and epistemological commitments.

Fig 4 Formal languages and their ontological and epistemological commitments.

Ontological commitment - what is assumed about reality

Epistemological commitment - possible states of knowledge

syntax of FOL with Basic elements. Constants

KingJohn, 2, UT CN, Klaus . . . Predicates Brother, >, .
..
Functions Sqrt, LeftLegOf, . . .
Variables x, y, a, b, . . .
Connectives ∧ ∨ ¬ ⇒ ⇔
Equality =
Quantifiers ∀ ∃

Atomic sentences?

• Atomic sentences are the most basic sentences of first-order logic. These sentences
are formed from a predicate symbol followed by a parenthesis with a sequence of
terms.
• We can represent atomic sentences as Predicate (term1, term2, ....... , term n).

Example: Ravi and Ajay are brothers: => Brothers(Ravi, Ajay).

Chinky is a cat: => cat (Chinky).

Atomic sentence = predicate(term1, ....... , termn)

or term1 = term2

Term = function(term1, ...... , termn) or constant or variable

E.g., Brother(KingJohn, RichardT heLionheart)

> (Length(Lef tLegOf(Richard)), Length(Lef tLegOf(KingJohn))) M arried(F
ather(Richard),Mother(Richard))

Complex sentences?

• Complex sentences are made by combining atomic sentences using connectives.

First-order logic statements can be divided into two parts:

 • Subject: Subject is the main part of the statement.
• Predicate: A predicate can be defined as a relation, which binds two atoms together
in a statement.

Consider the statement: "x is an integer.", it consists of two parts, the first part x is the
subject of the statement and second part "is an integer," is known as a predicate.

Complex sentences are made from atomic sentences using connectives

¬S, S1 ∧ S2, S1 ∨ S2, S1 ⇒ S2, S1 ⇔ S2

E.g. Sibling(KingJohn, Richard) ⇒ Sibling(Richard, KingJohn)

>(1, 2) ∨ ≤(1, 2)
>(1, 2) ∧ ¬>(1, 2)
¬Brother(Lef tLeg(Richard), John)

Model for FOL with Example

Fig 5 Model for FOL

Consider the interpretation in which
Richard → Richard the Lionheart
John → the evil King John
Brother → the brotherhood relation

Under this interpretation, Brother(Richard, John) is true just in case Richard the Lionheart
and the evil King John are in the brotherhood relation in the model

Universal quantification?
∀ (variables) (sentence)
Everyone in this room is smart:
∀ x At(x, D21) ⇒ Smart(x)
∀ x P is true in a model m iff P is true with x being each possible object in the model

Roughly speaking, equivalent to the conjunction of instantiations of P

(At(J ipaGeorge, D21) ⇒ Smart(J ipaGeorge))
∧ (At(P opaAndrada, D21) ⇒ Smart(P opaAndrada))
 ∧ (At(M acariaGeorgiana, D21) ⇒ Smart(M acarieGeorgiana))
∧. . .

Existential quantification?
∃ variables) (sentence)
Someone at Stanford is smart:
∃ x At(x, Stanford) ∧ Smart(x)
∃ x P is true in a model m iff P is true with x being some possible object in the model

Roughly speaking, equivalent to the disjunction of instantiations of P

(At(KingJohn, Stanford) ∧ Smart(KingJohn))
∨ (At(Richard, Stanford) ∧ Smart(Richard))
∨ (At(Stanford, Stanford) ∧ Smart(Stanford))
∨...

Properties of quantifiers?
∀ x ∀ y is the same as ∀ y ∀ x
x ∃ y is the same as ∃ y ∃ x
∃ x ∀ y is not the same as ∀ y ∃ x
∃ x ∀ y Loves(x, y) - “There is a person who loves everyone in the world”
∀ y ∃ x Loves(x, y) - “Everyone in the world is loved by at least one person”
“Everybody loves somebody”
“There is someone who is loved by everyone”
Quantifier duality: each can be expressed using the other
∀ x Likes(x, IceCream) ¬∃ x ¬Likes(x, IceCream)
∃ x Likes(x, Broccoli) ¬∀ x ¬Likes(x, Broccoli)

FOL examples with sentences.

Brothers are siblings
∀ x, y Brother(x, y) ⇒ Sibling(x, y).

“Sibling” is symmetric
∀ x, y Sibling(x, y) ⇔ Sibling(y, x).

One’s mother is one’s female parent

∀ x, y Mother(x, y) ⇔ (F emale(x) ∧ P arent(x, y)).

A first cousin is a child of a parent’s sibling

∀ x, y F irstCousin(x, y) ⇔ ∃ p, ps P arent(p, x) ∧ Sibling(ps, p) ∧ P arent(ps, y)

Equality?
Father(John) = Henry
term1 = term2 is true under a given interpretation
if and only if term1 and term2 refer to the same object
E.g., 1 = 2 and ∀ x ×(Sqrt(x), Sqrt(x)) = x are satisfiable
2 = 2 is valid

E.g., definition of (full) Sibling in terms of Parent:

∀ x, y Sibling(x, y) ⇔ [¬(x = y) ∧ ∃ m, f ¬(m = f) ∧ Parent(m, x) ∧
 Parent(f, x) ∧ Parent(m, y) ∧ Parent(f, y)]

Theorem: ∀ x, y Sibling(x, y) ⇔ Sibling(y, x)

“Richard’s brothers are John and Geoffrey”

first-order logic with equality, specified in Backus–Naur form.

Fig 6 first-order logic with equality

Terms, Atomic sentences, Complex sentences, Quantifiers, Equality.

Terms:
1) A term is a logical expression that refers to an object.
2) Constant symbols are therefore terms, but it is not always convenient to have a
distinct symbol to name every object.
3) For example, in English we might use the expression “King John’s left leg” rather
than giving a name to his leg. This is what function symbols are for: instead of using a
constant symbol, we use LeftLeg(John).
4) The formal semantics of terms is straightforward. Consider a term f(t1,...,tn). The
function symbol f refers to some function in the model (call it F); the argument terms
refer to objects in the domain (call them d1,...,dn); and the term as a whole refers to
the object that is the value of the function F applied to d1,...,dn.
5) For example, suppose the LeftLeg function symbol refers to the function shown in
Equation (8.2) and John refers to King John, then LeftLeg(John) refers to King John’s
left leg. In this way, the interpretation fixes the referent of every term.
Atomic sentences:
1) An atomic sentence (or atom for short) is formed from a predicate symbol optionally
followed by a ATOM parenthesized list of terms, such as
Brother(Richard,John).
 2) This states, under the intended interpretation given earlier, that Richard the Lionheart
is the brother of King John.6 Atomic sentences can have complex terms as arguments.
Thus,
Married(Father (Richard),Mother(John))
3) States that Richard the Lionheart’s father is married to King John’s mother (again,
under a suitable interpretation). An atomic sentence is true in a given model if the
relation referred to by the predicate symbol holds among the objects referred to by the
arguments.
Complex sentences:
1) We can use logical connectives to construct more complex sentences, with the same
syntax and semantics as in propositional calculus.
2) ¬Brother(LeftLeg(Richard),John)
Brother(Richard,John) ∧ Brother(John,Richard)
King(Richard) ∨ King(John)
¬King(Richard) ⇒ King(John) .
Quantifiers:
1) Once we have a logic that allows objects, it is only natural to want to express
properties of entire collections of objects, instead of enumerating the objects by name.
Quantifiers let us do this.
2) First-order logic contains two standard quantifiers, called universal and existential.
3) E.g. of universal quantifier:
All kings are persons.
∀x King(x) ⇒ Person(x) .
4) E.g. of existential quantifier:
King John has a crown on his head
∃x Crown(x) ∧ OnHead(x,John) .
Equality:
1) First-order logic includes one more way to make atomic sentences, other than using a
predicate and terms as described earlier. We can use the equality symbol to signify
that two terms refer to the same object.
2) For example, Father (John)=Henry
3) says that the object referred to by Father (John) and the object referred to by Henry
are the same. Because an interpretation fixes the referent of any term, determining the
truth of an equality sentence is simply a matter of seeing that the referents of the two
terms are the same object.
4) The equality symbol can be used to state facts about a given function.

Example of domain of family relationships, or kinship.

1) One’s mother is one’s female parent:
∀m,c Mother(c)=m ⇔ Female(m) ∧ Parent(m,c) .
2) One’s husband is one’s male spouse:
∀w,h Husband(h,w) ⇔ Male(h) ∧ Spouse(h,w) .
3) Male and female are disjoint categories:
∀x Male(x) ⇔¬Female(x) .
4) Parent and child are inverse relations:
∀p,c Parent(p,c) ⇔ Child(c,p) .
5) A grandparent is a parent of one’s parent:
∀g,c Grandparent(g,c) ⇔∃ p Parent(g,p) ∧ Parent(p,c) .
6) A sibling is another child of one’s parents:
∀x,y Sibling(x,y) ⇔ x = y ∧∃p Parent(p,x) ∧ Parent(p,y) .
 wumpus world problem using FOL.
1) The first order axioms in this section are much more concise, capturing in a natural
way exactly what we want to say.
2) Recall that the wumpus agent receives a percept vector with five elements.
3) The corresponding first-order sentence stored in the knowledge base must include
both the percept and the time at which it occurred; otherwise, the agent will get
confused about when it saw what. We use integers for time steps.
4) A typical percept sentence would be:

Percept([Stench,Breeze,Glitter,None,None], .
Here, Percept is a binary predicate, and Stench and so on are constants placed in a
list.
5) The actions in the wumpus world can be represented by logical terms:
Turn(Right), Turn(Left), Forward , Shoot, Grab, Climb .
6) To determine which is best, the agent program executes the query
ASKVARS(∃a BestAction(a,5)) ,
which returns a binding list such as {a/Grab}.
7) The agent program can then return Grab as the action to take. The raw percept data
implies certain facts about the current state.
8) For example:
∀t,s,g,m,c Percept([s,Breeze,g,m,c ],t) ⇒ Breeze(t) , ∀t,s,b,m,c
Percept([s,b,Glitter,m,c ],t) ⇒ Glitter(t) , and soon
9) These rules exhibit a trivial form of the reasoning process called perception,which we
study in depth in Chapter 24. Notice the quantification over time t.
10) In propositional logic, we would need copies of each sentence for each time step.

Examples of FOL using quantifier.

1. All birds fly.

In this question the predicate is "fly(bird)."
And since there are all birds who fly so it will be represented as follows.
∀x bird(x) →fly(x).

2. Every man respects his parent.

In this question, the predicate is "respect(x, y)," where x=man, and y= parent.
Since there is every man so will use ∀, and it will be represented as follows:
∀x man(x) → respects (x, parent).

3. Some boys play cricket.

In this question, the predicate is "play(x, y)," where x= boys, and y= game. Since there are
some boys so we will use ∃, and it will be represented as:
∃x boys(x) → play(x, cricket).

4. Not all students like both Mathematics and Science.

In this question, the predicate is "like(x, y)," where x= student, and y= subject.
Since there are not all students, so we will use ∀ with negation, so following representation
for this:
¬∀ (x) [ student(x) → like(x, Mathematics) ∧ like(x, Science)].
 5. Only one student failed in Mathematics.
In this question, the predicate is "failed(x, y)," where x= student, and y= subject.
Since there is only one student who failed in Mathematics, so we will use following
representation for this:
∃(x) [ student(x) → failed (x, Mathematics) ∧∀ (y) [¬(x==y) ∧ student(y) →
¬failed (x, Mathematics)].

Knowledge base for the wumpus world.

“Perception”
∀ b, g, t Percept([Smell, b, g], t) ⇒ Smelt(t)
∀ s, b, t Percept([s, b, Glitter], t) ⇒ AtGold(t)

Reflex: ∀ t AtGold(t) ⇒ Action(Grab, t)

Reflex with internal state: do we have the gold already?

∀ t AtGold(t) ∧ ¬Holding(Gold, t) ⇒ Action(Grab, t)

Holding(Gold, t) cannot be observed

⇒ keeping track of change is essential

∀ x, y, a, b Adjacent([x, y], [a, b]) ⇔ (x = a ∧ (y = b − 1 ∨ y = b + 1)) ∨ (y = b ∧ (x = a − 1 ∨

x = a + 1))

Knowledge engineering in first-order logic in short?

Knowledge engineer: investigates a particular domain, learns what concepts are important,
creates a formal representation of the objects and relations in the domain.

Knowledge engineering steps in short

1. Identify the task. - list compentency questions that the KB will respond
2. Assemble the relevant knowledge. - knowledge acuisition
3. Decide on a vocabulary of predicates, functions, and constants - translate the important
domain-level concepts into logic-level names - ontology
4. Encode general knowledge about the domain - axioms for all vocabulary terms
5. Encode a description of the specific problem instance - atomic sentences about instances of
concepts in the ontology
6. Pose queries to the inference procedure and get answers
7. Debug the knowledge base

Steps of Knowledge engineering projects?

1) Identify the task:
• The knowledge engineer must delineate the range of questions that the
knowledge base will support and the kinds of facts that will be available for
each specific problem instance.
• For example, does the wumpus knowledge base need to be able to choose
actions or is it required to answer questions only about the contents of the
environment? Will the sensor facts include the current location? The task will
determine what knowledge must be represented in order to connect problem
instances to answers.
 2) Assemble the relevant knowledge.:
• The knowledge engineer might already be an expert in the domain, or might
need to work with real experts to extract what they know—a process called
knowledge acquisition.
• At this stage, the knowledge is not represented KNOWLEDGE
ACQUISITION formally. The idea is to understand the scope of the
knowledge base, as determined by the task, and to understand how the domain
actually works.
3) Decide on a vocabulary of predicates, functions, and constants.:
• That is, translate the important domain-level concepts into logic-level names.
This involves many questions of knowledge-engineering style.
• Like programming style, this can have a significant impact on the eventual
success of the project. For example, should pits be represented by objects or
by a unary predicate on squares? Should the agent’s orientation be a function
or a predicate? Should the wumpus’s location depend on time? Once the
choices have been made, the result is a vocabulary that is known as the
ontology of the domain.
• The word ontology means a particular theory of the nature of being or
existence. The ontology determines what kinds of things exist, but does not
determine their specific properties and interrelationships.
4) Encode general knowledge about the domain.
• The knowledge engineer writes down the axioms for all the vocabulary terms.
This pins down (to the extent possible) the meaning of the terms, enabling the
expert to check the content. Often, this step reveals misconceptions or gaps in
the vocabulary that must be fixed by returning to step 3 and iterating through
the process.
5) Encode a description of the specific problem instance.
• If the ontology is well thought out, this step will be easy. It will involve
writing simple atomic sentences about instances of concepts that are already
part of the ontology. For a logical agent, problem instances are supplied by the
sensors, whereas a “disembodied” knowledge base is supplied with additional
sentences in the same way that traditional programs are supplied with input
data.
6) Pose queries to the inference procedure and get answers.
• This is where the reward is: we can let the inference procedure operate on the
axioms and problem-specific facts to derive the facts we are interested in
knowing. Thus, we avoid the need for writing an application-specific solution
algorithm.
7) Debug the knowledge base.
• Alas, the answers to queries will seldom be correct on the first try. More
precisely, the answers will be correct for the knowledge base as written,
assuming that the inference procedure is sound, but they will not be the ones
that the user is expecting. For example, if an axiom is missing, some queries
will not be answerable from the knowledge base. A considerable debugging
process could ensue. Missing axioms or axioms that are too weak can be easily
identified by noticing places where the chain of reasoning stops unexpectedly.

Universal instantiation (UI).

Every instantiation of a universally quantified sentence is entailed by it:
 ∀ v α / Subst({v/g }, α)
for any variable v and ground term g

E.g., ∀ x King(x) ∧ Greedy(x) ⇒ Evil(x) yields

King(John) ∧ Greedy(John) ⇒ Evil(John)
King(Richard) ∧ Greedy(Richard) ⇒ Evil(Richard)
King(F ather(John)) ∧ Greedy(F ather(John)) ⇒ Evil(F ather(John))
...
UI can be applied several times to add new sentences; the new KB is logically equivalent to
the old

Existential instantiation (EI)

For any sentence α, variable v, and constant symbol k that does not appear elsewhere in the
knowledge base:

∃ v α /Subst({v/k }, α)

E.g., ∃ x Crown(x) ∧ OnHead(x, John) yields

Crown(C 1) ∧ OnHead(C 1, John)
provided C 1 is a new constant symbol, called a Skolem constant

EI can be applied once to replace the existential sentence;

predicates with its syntax and semantics.

• First-order logic is used to model the world in terms of

– objects which are things with individual identities

e.g., individual students, lecturers, companies, cars ...

– properties of objects that distinguish them from other objects

e.g., mortal, blue, oval, even, large, ...

– classes of objects (often defined by properties)

e.g., human, mammal, machine, ...

– relations that hold among objects

e.g., brother of, bigger than, outside, part of, has color, occurs after, owns, a member of, ...
– functions which are a subset of the relations in which there is only one ``value'' for any
given ``input''.

e.g., father of, best friend, second half.

• Predicates: P(x[1], ..., x[n])
– P: predicate name; (x[1], ..., x[n]): argument list
– A special function with range = {T, F};
– Examples: human(x), /* x is a human */

father(x, y) /* x is the father of y */

– When all arguments of a predicate is assigned values (said to be instantiated), the predicate
becomes either true or false, i.e., it becomes a proposition. Ex. Father(Fred, Joe)
 A predicate, like a membership function.

Quantifiers with the types with syntax and example.

Once we have a logic that allows objects, it is only natural to want to express properties of
entire collections of objects, instead of enumerating the objects by name. Quantifiers let us
do this. First-order logic contains two standard quantifiers, called universal and existential.

The Universal Quantifier

The expression: x P(x), denotes the universal quantification of the atomic formula P(x).
Translated into the English language, the expression is understood as: "For all x, P(x) holds",
"for each x, P(x) holds" or "for every x, P(x) holds". is called the universal quantifier, and x
means all the objects x in the universe. If this is followed by P(x) then the meaning is that
P(x) is true for every object x in the universe. For example, "All cars have wheels" could be
transformed into the propositional form, x P(x), where:
P(x) is the predicate denoting: x has wheels, and the universe of discourse is only
populated by cars.

The Existential Quantifier

The expression: xP(x), denotes the existential quantification of P(x). Translated into the
English language, the expression could also be understood as: "There exists an x such that
P(x)" or "There is at least one x such that P(x)" is called the existential quantifier, and x
means at least one object x in the universe. If this is followed by P(x) then the meaning is that
P(x) is true for at least one object x of the universe. For example, "Someone loves you" could
be transformed into the propositional form, x P(x), where:

P(x) is the predicate meaning: x loves you, The universe of discourse contains (but is not
limited to) all living creatures.

Convert the following into predicate form:

i. Virat is software engineer.
ii. All vehicles have wheels
iii. Some-one speaks some language in this class.
iv. Everybody loves somebody sometime.
v. All software engineer develops software.
Ans:
i. Virat is software engineer.
softwareengineer(Virat)

ii. All vehicles have wheels

∀x y vehical(x) →wheelof(y,x)

iii. Some-one speaks some language in this class.

y x person(y)  language (x) → speaks (y, x)

iv. Everybody loves somebody sometime.

∀x y loves-sometime(x, y)

v. All software engineer develops software.

 ∀x softwareengineer (x) →software(x)

Convert the following natural sentences into FOL form:

i. Virat is cricketer.

Virat(cricketer)

ii. All batsman are cricketers.

For-all(x): batsman(x) -> cricketer(x)

iii. Everybody speaks some language

For-all(x) Exist(y): Person(x) V language(y) -> speaks(x,y)

iv. Every car has wheel.

(forall (x) (if (Car x) (exists (y) wheel-of (x y)))

v. Everybody loves somebody some time.

(forall (x) (exists (y) -> loves-sometime(x y))).

Unification and its Example.

1) Lifted inference rules require finding substitutions that make different logical
expressions look identical. This process is called unification and is a key component
of all first-order inference algorithms.
2) The UNIFY algorithm takes two sentences and returns a unifier for them if one exists:
UNIFY(p,q)=θ where SUBST(θ,p)=SUBST(θ,q) .
3) Example:
AskVars(Knows(John,x)): whom does John know?
4) Answers to this query can be found by finding all sentences in the knowledge base
that unify with Knows(John,x). Here are the results of unification with four different
sentences that might be in the knowledge base:
UNIFY(Knows(John,x), Knows(John,Jane)) = {x/Jane}
UNIFY(Knows(John,x), Knows(y,Bill)) = {x/Bill,y/John}
UNIFY(Knows(John,x), Knows(y,Mother(y))) = {y/John,x/Mother(John)}
UNIFY(Knows(John,x), Knows(x,Elizabeth)) = fail
5) The last unification fails because x cannot take on the values John and Elizabeth at the
same time.
6) Now, remember that Knows(x,Elizabeth) means “Everyone knows Elizabeth,” so we
should be able to infer that John knows Elizabeth.
7) The problem arises only because the two sentences happen to use the same variable
name, x. The problem can be avoided by standardizing apart one of the two sentences
being unified, which means renaming its variables to avoid name clashes. For
example, we can rename x in Knows(x,Elizabeth) to x17 (a new variable name)
without changing its meaning. Now the unification will work:
 UNIFY(Knows(John,x), Knows(x17,Elizabeth)) = {x/Elizabeth,x17/John} .
8) There is one more complication: we said that UNIFY should return a substitution that
makes the two arguments look the same. But there could be more than one such
unifier.

Unification in Artificial Intelligence Examples

Unification in Artificial Intelligence Examples:

[Link]

Forward chaining algorithm.

Fig 7 Forward chaining algorithm.

Forward chaining.
9) it is a crime for an American to sell weapons to hostile nations”:
American(x) ∧ Weapon(y) ∧ Sells(x,y,z) ∧ Hostile(z) ⇒ Criminal(x) .
10) “Nono ...has some missiles.” The sentence ∃x Owns(Nono,x)∧Missile(x) is
transformed into two definite clauses by Existential Instantiation, introducing a new
constant M1:
Owns(Nono,M1)
Missile(M1)
11) All of its missiles were sold to it by Colonel West
Missile(x) ∧ Owns(Nono,x) ⇒ Sells(West,x,Nono) .
12) We will also need to know that missiles are weapons:
Missile(x) ⇒ Weapon(x)
13) enemy of America counts as “hostile”:
Enemy(x,America) ⇒ Hostile(x) .
14) West, who is American ...”:
American(West) .
15) The country Nono, an enemy of America
Enemy(Nono,America) .

Explain Backward chaining algorithm.

Backward chaining.
16) it is a crime for an American to sell weapons to hostile nations”:
American(x) ∧ Weapon(y) ∧ Sells(x,y,z) ∧ Hostile(z) ⇒ Criminal(x) .
17) “Nono ...has some missiles.” The sentence ∃x Owns(Nono,x)∧Missile(x) is
transformed into two definite clauses by Existential Instantiation, introducing a new
constant M1:
Owns(Nono,M1)
Missile(M1)
18) All of its missiles were sold to it by Colonel West
Missile(x) ∧ Owns(Nono,x) ⇒ Sells(West,x,Nono) .
19) We will also need to know that missiles are weapons:
Missile(x) ⇒ Weapon(x)
20) enemy of America counts as “hostile”:
Enemy(x,America) ⇒ Hostile(x) .
21) West, who is American ...”:
American(West) .
22) The country Nono, an enemy of America
Enemy(Nono,America) .
 Fig 8 Forward chaining & backward chaining artificial intelligence

Forward chaining & backward chaining artificial intelligence:

[Link]

Properties of forward chaining and backward chaining.

Properties of forward chaining

 • It is a down-up approach, as it moves from bottom to top.
• It is a process of making a conclusion based on known facts or data, by starting from
the initial state and reaches the goal state.
• Forward-chaining approach is also called as data-driven as we reach to the goal using
available data.
• Forward -chaining approach is commonly used in the expert system, such as CLIPS,
business, and production rule systems.

Properties of backward chaining

• It is known as a top-down approach.

• Backward-chaining is based on modus ponens inference rule.
• In backward chaining, the goal is broken into sub-goal or sub-goals to prove the facts
true.
• It is called a goal-driven approach, as a list of goals decides which rules are selected
and used.
• Backward -chaining algorithm is used in game theory, automated theorem proving
tools, inference engines, proof assistants, and various AI applications.
• The backward-chaining method mostly used a depth-first search strategy for proof.

Difference between Forward Chaining and Backward Chaining

S.
Forward Chaining Backward Chaining
No.
Forward chaining starts from known facts Backward chaining starts from the goal and
1. and applies inference rule to extract more works backward through inference rules to
data unit it reaches to the goal. find the required facts that support the goal.
2. It is a bottom-up approach It is a top-down approach
Forward chaining is known as data- Backward chaining is known as goal-driven
3. driven inference technique as we reach to technique as we start from the goal and
the goal using the available data. divide into sub-goal to extract the facts.
Forward chaining reasoning applies a Backward chaining reasoning applies a
4.
breadth-first search strategy. depth-first search strategy.
Forward chaining tests for all the Backward chaining only tests for few
5.
available rules required rules.
Forward chaining is suitable for the
Backward chaining is suitable for diagnostic,
6. planning, monitoring, control, and
prescription, and debugging application.
interpretation application.
Forward chaining can generate an infinite Backward chaining generates a finite number
7.
number of possible conclusions. of possible conclusions.
8. It operates in the forward direction. It operates in the backward direction.
Forward chaining is aimed for any Backward chaining is only aimed for the
9.
conclusion. required data.

Logic programming
Logical programing.

23) Logic programming is a technology that comes fairly close to embodying the
declarative ideal that systems should be constructed by expressing knowledge in a
formal language and that problems should be solved by running inference processes
on that knowledge.
24) The ideal is summed up in Robert Kowalski’s equation,
Algorithm = Logic + Control .
25) Prolog is the most widely used logic programming language. It is used primarily as a
rapid-PROLOG prototyping language and for symbol-manipulation tasks such as
writing compilers (VanRoy, 1990) and parsing natural language (Pereira and Warren,
1980).
26) Many expert systems have been written in Prolog for legal, medical, financial, and
other domains. Prolog programs are sets of definite clauses written in a notation
somewhat different from standard first-order logic.
27) Prolog uses uppercase letters for variables and lowercase for constants—the opposite
of our convention for logic.
28) Commas separate conjuncts in a clause, and the clause is written “backwards” from
what we are used to; instead of A ∧ B ⇒ C in Prolog we have C :- A, B. Here is a
typical example:
criminal(X) :- american(X), weapon(Y), sells(X,Y,Z), hostile(Z).

Conjuctive normal form for first order logic.

29) As in the propositional case, first-order resolution requires that sentences be in
conjunctive normal form (CNF)—that is, a conjunction of clauses, where each clause
is a disjunction of literals.6 Literals can contain variables, which are assumed to be
universally quantified.
30) For example, the sentence
∀x American(x) ∧ Weapon(y) ∧ Sells(x,y,z) ∧ Hostile(z) ⇒ Criminal(x) becomes, in
CNF,
¬American(x) ∨¬Weapon(y) ∨¬Sells(x,y,z) ∨¬Hostile(z) ∨ Criminal(x) .
31) Every sentence of first-order logic can be converted into an inferentially equivalent
CNF sentence. In particular, the CNF sentence will be unsatisfiable just when the
original sentence is unsatisfiable.
32) The procedure for conversion to CNVF is similar to the propositional case, The
principal difference arises from the need to eliminate existential quantifiers.
33) Example:
Everyone who loves all animals is loved by someone,” or
 ∀x [∀y Animal(y) ⇒ Loves(x,y)] ⇒ [∃y Loves(y,x)] .
34) The steps are as follows:
• Eliminate implications:
∀x [¬∀y ¬Animal(y) ∨ Loves(x,y)] ∨ [∃y Loves(y,x)]
• Move ¬ inwards:
In addition to the usual rules for negated connectives, we need rules for negated
quantifiers.
Thus, we have ¬∀xp becomes ∃x ¬p ¬∃xp becomes ∀x ¬p.
Our sentence goes through the following transformations:
∀x [∃y ¬(¬Animal(y) ∨ Loves(x,y))] ∨ [∃y Loves(y,x)] .
∀x [∃y ¬¬Animal(y) ∧¬Loves(x,y)] ∨ [∃y Loves(y,x)] .
∀x [∃y Animal(y) ∧¬Loves(x,y)] ∨ [∃y Loves(y,x)] .
• Standardize variables:
For sentences like (∃xP(x))∨(∃xQ(x)) which use the same variable name twice,
change the name of one of the variables. This avoids confusion later when we
drop the quantifiers. Thus, we have
∀x [∃y Animal(y) ∧¬Loves(x,y)] ∨ [∃z Loves(z,x)] .
• Skolemize:
Skolemization is the process of removing existential quantifiers by elimination. In
the simple case, it is just like the Existential Instantiation rule of Section 9.1:
translate ∃xP(x) into P(A), where A is a new constant. However, we can’t
apply Existential Instantiation to our sentence above because it doesn’t match
the pattern ∃vα ; only parts of the sentence match the pattern. If we blindly
apply the rule to the two matching parts we get
∀x [Animal(A) ∧¬Loves(x,A)] ∨ Loves(B,x) ,
• Drop universal quantifiers:
At this point, all remaining variables must be universally quantified. Moreover,
the sentence is equivalent to one in which all the universal quantifiers have
been moved to the left. We can therefore drop the universal quantifiers:
[Animal(F(x)) ∧¬Loves(x,F(x))] ∨ Loves(G(z),x) .
• Distribute ∨ over ∧:
[Animal(F(x)) ∨ Loves(G(z),x)] ∧ [¬Loves(x,F(x)) ∨ Loves(G(z),x)] .

Different resolution strategies

35) Unit preference:
• This strategy prefers to do resolutions where one of the sentences is a single
literal (also known as a unit clause).
• The idea behind the strategy is that we are trying to produce an empty clause,
so it might be a good idea to prefer inferences that produce shorter clauses.
• Resolving a unit sentence (such as P) with any other sentence (such as ¬P
∨¬Q∨R) always yields a clause (in this case, ¬Q ∨ R) that is shorter than the
other clause.
• When the unit preference strategy was first tried for propositional inference in
1964, it led to a dramatic speedup, making it feasible to prove theorems that
could not be handled without the preference. Unit resolution is a restricted
form of resolution in which every resolution step must involve a unit clause.
36) Set of support:
• Preferences that try certain resolutions first are helpful, but in general it is
more effective to try to eliminate some potential resolutions altogether.
 • For example, we can insist that every resolution step involve at least one
element of a special set of clauses—the set of support. The resolvent is then
added into the set of support.
• If the set of support is small relative to the whole knowledge base, the search
space will be reduced dramatically.
37) Input resolution:
• In this strategy, every resolution combines one of the input sentences (from
the KB or the query) with some other sentence.
• Clearly, the space of proof trees of this shape is smaller than the space of all
proof graphs.
• Thus, it is no surprise that input resolution is complete for knowledge bases
that are in Horn form, but incomplete in the general case.
38) Subsumption:
• The subsumption method eliminates all sentences that are subsumed by (that
is, more specific than) an existing sentence in the KB.
• For example, if P(x) is in the KB, then there is no sense in adding P(A) and
even less sense in adding P(A) ∨ Q(B). Subsumption helps keep the KB small
and thus helps keep the search space small.

Resolution proof that West is a criminal.

American(x)∧Weapon(y)∧Sells(x, y, z)∧Hostile(z) ⇒ Criminal(x)

∀ x Missile(x) ∧ Owns(Nono, x) ⇒ Sells(West, x, Nono)

Missile(x) ⇒ Weapon(x)

Enemy(x, America) ⇒ Hostile(x)

American(West)

Enemy(Nono, America)

Owns(Nono,M1)

Missile(M1)
 Fig 9 Resolution proof that West is a criminal.

Resolution in Artificial Intelligence | Convert into FOL

Resolution in Artificial Intelligence | Convert into FOL:

[Link]
Structure of a completeness proof for resolution.

Fig 10 Structure of a completeness proof for resolution.

Resolution

Resolution is a theorem proving technique that proceeds by building refutation proofs, i.e.,
proofs by contradictions. It was invented by a Mathematician John Alan Robinson in the year
1965.

Resolution is used, if there are various statements are given, and we need to prove a
conclusion of those statements. Unification is a key concept in proofs by resolutions.
Resolution is a single inference rule which can efficiently operate on the conjunctive normal
form or clausal form.

Clause: Disjunction of literals (an atomic sentence) is called a clause. It is also known as a
unit clause.

Conjunctive Normal Form: A sentence represented as a conjunction of clauses is said to be

conjunctive normal form or CNF.

Steps for Resolution:

1. Conversion of facts into first-order logic.

2. Convert FOL statements into CNF
3. Negate the statement which needs to prove (proof by contradiction)
4. Draw resolution graph (unification).

Example of Resolution

1. John likes all kind of food.

 2. Apple and vegetable are food
3. Anything anyone eats and not killed is food.
4. Anil eats peanuts and still alive
5. Harry eats everything that Anil eats.
Prove by resolution that:
6. John likes peanuts.

Step-1: Conversion of Facts into FOL

In the first step we will convert all the given statements into its first order logic.
Step-2: Conversion of FOL into CNF

In First order logic resolution, it is required to convert the FOL into CNF as CNF form makes
easier for resolution proofs.

• Eliminate all implication (→) and rewrite

1. ∀x ¬ food(x) V likes(John, x)
2. food(Apple) Λ food(vegetables)
3. ∀x ∀y ¬ [eats(x, y) Λ ¬ killed(x)] V food(y)
4. eats (Anil, Peanuts) Λ alive(Anil)
5. ∀x ¬ eats(Anil, x) V eats(Harry, x)
6. ∀x¬ [¬ killed(x) ] V alive(x)
7. ∀x ¬ alive(x) V ¬ killed(x)
8. likes(John, Peanuts).
• Move negation (¬)inwards and rewrite
1. ∀x ¬ food(x) V likes(John, x)
2. food(Apple) Λ food(vegetables)
3. ∀x ∀y ¬ eats(x, y) V killed(x) V food(y)
4. eats (Anil, Peanuts) Λ alive(Anil)
5. ∀x ¬ eats(Anil, x) V eats(Harry, x)
6. ∀x killed(x) ] V alive(x)
7. ∀x ¬ alive(x) V ¬ killed(x)
8. likes(John, Peanuts).
• Rename variables or standardize variables
1. ∀x ¬ food(x) V likes(John, x)
2. food(Apple) Λ food(vegetables)
3. ∀y ∀z ¬ eats(y, z) V killed(y) V food(z)
4. eats (Anil, Peanuts) Λ alive(Anil)
5. ∀w¬ eats(Anil, w) V eats(Harry, w)
6. ∀g killed(g) ] V alive(g)
7. ∀k ¬ alive(k) V ¬ killed(k)
8. likes(John, Peanuts).
• Eliminate existential instantiation quantifier by elimination.
In this step, we will eliminate existential quantifier ∃, and this process is known as
Skolemization. But in this example problem since there is no existential quantifier so
all the statements will remain same in this step.
• Drop Universal quantifiers.
In this step we will drop all universal quantifier since all the statements are not
implicitly quantified so we don't need it.
1. ¬ food(x) V likes(John, x)
2. food(Apple)
3. food(vegetables)
4. ¬ eats(y, z) V killed(y) V food(z)
5. eats (Anil, Peanuts)
6. alive(Anil)
7. ¬ eats(Anil, w) V eats(Harry, w)
8. killed(g) V alive(g)
9. ¬ alive(k) V ¬ killed(k)
10. likes(John, Peanuts).
Note: Statements "food(Apple) Λ food(vegetables)" and "eats (Anil, Peanuts) Λ
alive(Anil)" can be written in two separate statements.

• Distribute conjunction ∧ over disjunction ¬.

This step will not make any change in this problem.

Step-3: Negate the statement to be proved

In this statement, we will apply negation to the conclusion statements, which will be written
as ¬likes(John, Peanuts)

Step-4: Draw Resolution graph:

Now in this step, we will solve the problem by resolution tree using substitution. For the
above problem, it will be given as follows:

Hence the negation of the conclusion has been proved as a complete contradiction with the
given set of statements.
GQs
1. What is meant by First Order Logic? Explain syntax and semantics of First
Order Logic.
2. Explain following w.r.t. First Order Logic. 1. Term 2. Atomic Sentences 3.
Complex Sentences 4. Quantifiers. 5. Existential quantification 6. Equality
3. Explain Assertions And Queries In First-order Logic.
4. Explain Kinship Domain (Family relationship of statement Domain).
5. Explain steps of Knowledge Engineering projects in First Order Logic.
6. Explain how A.I is useful in Electronic Circuits Domain.
7. Explain Inference rules for quantifiers with example.
8. Explain Generalized Modus Ponens Rule in detail.
9. Explain First-order Inference Rule.
10. What is meant by Unification And Lifting? Explain lifted Modus Pones rule
in detail.
11. Explain Datalog used in first order definite clause.
12. Explain Simple Forward-chaining Algorithm in detail with example and
advantage.
13. Explain Backward chaining and Working of Backward chaining.
14. Explain Resolution Theorem and its disadvantages.
15. Explain eight-stage process that converts any sentence into CNF.
16. Explain Resolution Inference Rule in detail.
17. Explain Completeness Of Resolution and basic structure of it.
18. Explain following inference methods. 1. Reflexive 2. Symmetric 3. Transitive
19. Explain Demodulation and Paramodulation
20. Write a short note on Resolution Strategies.
21. Explain universal and existential quantifier with suitable example.
22. Convert the following natural sentences into FOL form:
i. Virat is cricketer.
ii. All batsman are cricketers.
iii. Everybody speaks some language
iv. Every car has wheel.
v. Everybody loves somebody some time.
23. Explain in brief about unification.
Multiple Choice Questions
1. There exist only two types of quantifiers, Universal Quantification and Existential
Quantification.
a) True
b) False

2. Translate the following statement into FOL.

“For every a, if a is a philosopher, then a is a scholar”
a) ∀ a philosopher(a) scholar(a)
b) ∃ a philosopher(a) scholar(a)
c) All of the mentioned
d) None of the mentioned

3. A is used to demonstrate, on a purely syntactic basis, that one formula is a

logical consequence of another formula.
a) Deductive Systems
b) Inductive Systems
c) Reasoning with Knowledge Based Systems
d) Search Based Systems

4. The statement comprising the limitations of FOL is/are

a) Expressiveness
b) Formalizing Natural Languages
c) Many-sorted Logic
d) All of the mentioned

5. A common convention is:

a) is evaluated first
b) and are evaluated next
c) Quantifiers are evaluated next
d) is evaluated last.
a) True
b) False

6. A Term is either an individual constant (a 0-ary function), or a variable, or an n-ary

function applied to n terms: F(t1 t2 ..tn).
a) True
b) False

7. First Order Logic is also known as

a) First Order Predicate Calculus
b) Quantification Theory
c) Lower Order Calculus
d) All of the mentioned

8. The adjective “first-order” distinguishes first-order logic from in which

there are predicates having predicates or functions as arguments, or in which one or both
of predicate quantifiers or function quantifiers are permitted.
a) Representational Verification
b) Representational Adequacy
c) Higher Order Logic
d) Inferential Efficiency

9. Which is created by using single propositional symbol?

a) Complex sentences
b) Atomic sentences
c) Composition sentences
d) None of the mentioned

10. Which is used to construct the complex sentences?

a) Symbols
b) Connectives
c) Logical connectives
d) All of the mentioned

11. How many proposition symbols are there in artificial intelligence?

a) 1
b) 2
c) 3
d) 4

12. How many logical connectives are there in artificial intelligence?

a) 2
b) 3
c) 4
d) 5

13. Which is used to compute the truth of any sentence?

a) Semantics of propositional logic
b) Alpha-beta pruning
c) First-order logic
d) Both Semantics of propositional logic & Alpha-beta pruning

14. Which are needed to compute the logical inference algorithm?

a) Logical equivalence
b) Validity
c) Satisfiability
d) All of the mentioned

15. From which rule does the modus ponens are derived?
a) Inference rule
b) Module rule
c) Both Inference & Module rule
d) None of the mentioned

16. Which is also called single inference rule?

a) Reference
b) Resolution
c) Reform
d) None of the mentioned

17. Which form is called as a conjunction of disjunction of literals?

a) Conjunctive normal form
b) Disjunctive normal form
c) Normal form
d) All of the mentioned

18. What can be viewed as a single lateral of disjunction?

a) Multiple clause
b) Combine clause
c) Unit clause
d) None of the mentioned

19. Which condition is used to cease the growth of forward chaining?

a) Atomic sentences
b) Complex sentences
c) No further inference
d) All of the mentioned
 20. Which algorithm will work backward from the goal to solve a problem?
a) Forward chaining
b) Backward chaining
c) Hill-climb algorithm
d) None of the mentioned

21. Translate the given statement into First-order logic.

“For every a, if a is a poet, then a is a writer”
a) ∃ a poet ((A). writer ((A).
b) ∀ a poet ((A). writer ((A).
c) All of these
d) None of these

22. Which is a refutation complete inference procedure for propositional logic?

a) Clauses
b) Variables
c) Propositional resolution
d) Proposition

23. What is the total number of possible sources of complexity in the forwarding chaining
approach?
a) 3
b) 4
c) 5
d) 2

24. Which of the following are more appropriate normal forms to be helpful with a definite
clause?
a) Positive literal
b) Generalized modus ponens
c) Negative literal
d) Neutral literal

25. Which of the following closely looks like a propositional definite clause?
a) Resolution
b) First-order definite clauses
c) Conjunction
d) Inference
Previous Year University Questions
1. What is first order logic? Discuss the different elements used in first order logic. Oct
2018
2. Explain universal and existential quantifier with suitable example. Oct 2018
or
3. Explain universal qualifier with example. May 2019
4. Convert the following natural sentences into FOL form: Oct 2018
i. Virat is cricketer.
ii. All batsman are cricketers.
iii. Everybody speaks some language
iv. Every car has wheel.
v. Everybody loves somebody some time.
5. What is knowledge engineering? Write the steps for its execution. Oct 2018
6. Give comparison between forward chaining and backward chaining. Oct 2018
7. Explain in brief about unification. Oct 2018
8. Explain the following with example May 2019
i. Atomic sentence ii. Complex sentence
9. Define the wumpus world problem in terms of first order logic. May 2019
10. Explain the following concepts May 2019
i. Universal Instantiation ii. Existential Instantiation.
11. Write and explain a simple backward chaining algorithm for first order knowledge
bases. May 2019
12. Explain the first order definite clause. May 2019

Problem Based Learning:

a. Representing Facts in First-Order Logic

1. Lucy* is a professor

2. All professors are people.

3. John is the dean.

4. Deans are professors.

5. All professors consider the dean a friend or don’t know him.

6. Everyone is a friend of someone.

7. People only criticize people that are not their friends.

8. Lucy criticized John .

Knowledge base:

• is-prof(lucy)

•  x ( is-prof(x) → is-person(x) )

• is-dean(John)

•  x (is-dean(x)  is-prof(x))
•  x ( y ( is-prof(x)  is-dean(y) → is-friend-of(y,x)  knows(x, y) ) )

•  x ( y ( is-friend-of (y, x) ) )

•  x ( y (is-person(x) is-person(y) criticize (x,y) → is-friend-of (y,x)))

• criticize(lucy, John )

Question: Is John no friend of Lucy? is-friend-of(John ,lucy)

b. Explain Resolution Example:

c. Example of resolution

Jack owns a dog. Every dog owner is an animal lover. No animal lover kills an animal. Either
Jack or Curiosity killed the cat, who is named Tuna. Did Curiosity kill the cat?

d. Practice in 1st-order predicate logic – with answers.

1. Mary loves everyone. [assuming D contains only humans]

2. Mary loves everyone. [assuming D contains both humans and non-humans, so we need to
be explicit about ‘everyone’ as ‘every person’]

3. No one talks. [assume D contains only humans unless specified otherwise.]

4. Everyone loves himself.

5. Everyone loves everyone.

6. Everyone loves everyone except himself. (= Everyone loves everyone else.)

7. Every student smiles.

8. Every student except George smiles.

9. Everyone walks or talks.

10. Every student walks or talks.

11. Every student who walks talks.

12. Every student who loves Mary is happy