20CS16-Principals of Artificial Intelligence

By

Mrs. S.Jyothi

Asst Professor

Dept of IT LBRCE,Mylavaram

1

UNIT IV

Chapter I Knowledge Representation

using Predicate logic

2

Knowledge Representation using Predicate logic

3

• Introduction

​

• Representing simple facts in logic

​

• Representing instance and ISA Relationships

​

• Computable functions and predicates

​

• Resolution

​

• Natural deduction

Introduction

4

Propositional logic

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

Example:

1. It is Sunday.
2. The Sun rises from West (False proposition)
3. 3+3= 7(False proposition)
4. 5 is a prime number.

5

Following are some basic facts about propositional logic:

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

"Where is Rohan", "How are you", "What is your name", are not propositions.

Syntax of propositional logic

6

The syntax of propositional logic defines the allowable sentences for the knowledge representation. There are two types of Propositions:

Atomic Proposition: Atomic propositions are the simple propositions. It consists of a single

proposition symbol. These are the sentences which must be either true or false.

​

1. 2+2 is 4, it is an atomic proposition as it is a true fact.
2. "The Sun is cold" is also a proposition as it is a false fact.

​

Compound proposition: Compound propositions are constructed by combining simpler or atomic propositions, using parenthesis and logical connectives.

• "It is raining today, and street is wet."
• "Ankit is a doctor, and his clinic is in Mumbai."

Logical Connectives

Logical connectives are used to connect two simpler propositions or representing a sentence logically. We can create compound propositions with the help of logical connectives. There are mainly five connectives, which are given as follows

7

• Negation: A sentence such as ¬ P is called negation of P. A literal can be either Positive

literal or negative literal.

• Conjunction: A sentence which has 𝖠 connective such as, P 𝖠 Q is called a conjunction.

Example: Rohan is intelligent and hardworking. It can be written as,

P= Rohan is intelligent,

Q= Rohan is hardworking. P𝖠 Q.

• Disjunction: A sentence which has ∨ connective, such as P ∨ Q. is called disjunction, where P and Q are the propositions.

Example: "Ritika is a doctor or Engineer",

Here P= Ritika is Doctor. Q= Ritika is Engineer, so we can write it as P ∨ Q.

• Implication: A sentence such as P → Q, is called an implication. Implications are also known as if-then rules. It can be represented as

If it is raining, then the street is wet.

Let P= It is raining, and Q= Street is wet, so it is represented as P → Q

• Biconditional: A sentence such as P⇔ Q is a Biconditional sentence, example If I am breathing, then I am alive

P= I am breathing, Q= I am alive, it can be represented as P ⇔ Q.

8

9

10

Precedence of connectives

11

The is a precedence order for propositional connectors or logical operators. This order should be followed while evaluating a propositional problem. Following is the list of the precedence order for operators:

Logical equivalence

Logical equivalence is one of the features of propositional logic. Two propositions are said to be logically equivalent if and only if the columns in the truth table are identical to each other.

Let's take two propositions A and B, so for logical equivalence, we can write it as A⇔B. In below truth table we can see that column for ¬A∨ B and A→B, are identical hence A is Equivalent to B

12

Properties of Operators

13

• Commutativity:
• P𝖠 Q= Q 𝖠 P, or
• P ∨ Q = Q ∨ P.
• Associativity:
• (P 𝖠 Q) 𝖠 R= P 𝖠 (Q 𝖠 R),
• (P ∨ Q) ∨ R= P ∨ (Q ∨ R)
• Identity element:
• P 𝖠 True = P,
• P ∨ True= True.
• Distributive:
• P𝖠 (Q ∨ R) = (P 𝖠 Q) ∨ (P 𝖠 R).
• P ∨ (Q 𝖠 R) = (P ∨ Q) 𝖠 (P ∨ R).
• DE Morgan's Law:
• ¬ (P 𝖠 Q) = (¬P) ∨ (¬Q)
• ¬ (P ∨ Q) = (¬ P) 𝖠 (¬Q).
• Double-negation elimination:
• ¬ (¬P) = P.

14

Limitations of Propositional logic:

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

Predicate logic/First-Order logic

15

• First-order logic is another way of knowledge representation in artificial intelligence. It is

an extension to propositional logic.

• FOL is sufficiently expressive to represent the natural language statements in a concise

way.

• First-order logic is also known as Predicate logic or First-order predicate logic. First- order logic is a powerful language that develops information about the objects in a more easy way and can also express the relationship between those objects.
• First-order logic (like natural language) does not only assume that the world contains facts like propositional logic but also assumes the following things in the world:
• Objects: A, B, people, numbers, colours, wars, theories, squares, pits, Wumpus, ......
• Relations: It can be unary relation such as: red, round, is adjacent, or n-any relation such as: the sister of, brother of, has colour, comes between
• Function: Father of, best friend, third inning of, end of, ......
• As a natural language, first-order logic also has two main parts:
• Syntax

• Semantics

Syntax of First-Order logic

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

16

Basic Elements of First-order logic

17

Atomic sentences

18

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

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.

19

Quantifiers in First-order logic

20

• 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:
• Universal Quantifier, (for all, everyone, everything)
• Existential quantifier, (for some, at least one).

Universal Quantifier

21

• 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 man so all x can be represented in UOD as below:

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

It will be read as: There are all x where x is a man who drink coffee. The main connective for universal quantifier ∀ is implication →.

22

Existential Quantifier

23

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

∃x: boys(x) 𝖠 intelligent(x)

It will be read as: There are some x where x is a boy who is intelligent. The main connective for existential quantifier ∃ is and 𝖠.

24

Properties of Quantifiers

25

• In universal quantifier, ∀x∀y is similar to ∀y∀x.
• In Existential quantifier, ∃x∃y is similar to ∃y∃x.
• ∃x∀y is not similar to ∀y∃x.

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)

26

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.

​

How it will be represented?

Ans is             

 ∃(x) [ student(x) → failed (x, Mathematics) ∧∀ (y) [¬(x==y) ∧ student(y) → ¬failed (x, Mathematics)].

�

Free and Bound Variables

28

The quantifiers interact with variables which appear in a suitable way.

There are two types of variables in First-order logic which are given below: Free Variable: A variable is said to be a free variable in a formula if it occurs outside the scope of the quantifier.

Example: ∀x ∃(y)[P (x, y, z)], where z is a free variable.

Bound Variable: A variable is said to be a bound variable in a formula if it occurs within the scope of the quantifier.

Example: ∀x ∀y [A (x) B( y)], here x and y are the bound variables.

Representing simple facts in logic

Using proportional logic:

• Real world facts are represented as logical propositions written as well- formed formulas(wffs)

Example1:

29

Example2:

Since the assertions are separate, it is not possible to draw any conclusion about similarities between Socrates and Plato.

​

It would be much better to represent these facts as

30

31

• This is fail to capture the relationship between any individual being a man and that individual being a mortal.

​

• Therefore it is necessary to move to first order predicate logic as a way of representing knowledge because it permits representation of things that can't reasonably be represented in propositional logic.

​

• In predicate logic, real world facts are represented as statements written as wff’s

Propositional logic Vs Predicate logic

32

Consider the following statements

33

34

1. Marcus was a man man(Marcus)
2. Marcus was a Pompeain.

Pompeians(Marcus)

3. All Pompeians are Romans

∀(x):Pompeians(x) →Roman(x) 4.Casear was a ruler

ruler(Casear)

5.All Romans were either loyal to Casear or hated him.

∀(x): Roman(x) →loyalto(x,Casear) V hate(x,Casear) 6.Every one is loyal to someone.

∀x: ∃(y):loyalto(x,y)

35

7. People only try to assassinate rulers they are not loyal to.

∀x :∀(y):person(x) 𝖠 ruler(y) 𝖠 tryassassinate(x,y) → ¬loyalto(x,y)

​

8. Marcus try to assassinate Casear. tryassassinate(Marcus,Casear)

To Answer the question

Was Marcus loyal to Caesar?

To produce a formal proof, reasoning backward from the desired goal

¬ loyalto(Marcus, Caesar)

To prove the goal, rules of inference are to be used to transform into another goal that in turn to be transformed and so on, until there no unsatisfied goals remaining

36

37

• This attempt fails, since there is no way to satisfy the goal Person(Marcus) with the statements available.
• The problem is although its known that Marcus was a man there is no way to conclude it.
• There for another representation added namely.

​

9.All men are people

∀x :man(x) → person(x)

​

this satisfies the last goal and produces a proof that Marcus was not loyal to Ceasar.

38

Three important statements to be addressed in this process of converting English sentences to logical sentences to deduce new ones.

​

• Many English sentences are ambiguous. Choosing the correct interpretation may be difficult.
• There is often a choice of how to represent knowledge
• Obvious information may be necessary for reasoning
• We may not known in advance which statements to deduce(p or ¬p)

Representing Instance and Isa Relationships

39

Attributes " IsA " and " Instance " support property inheritance and play important role in knowledge representation. The ways these two attributes "instance" and "isa", are logically expressed are shown in the example below : Example : A simple sentence like "Joe is a musician" Here "is a" (called IsA) is a way of expressing what logically is called a class-instance relationship between the subjects represented by the terms "Joe" and "musician". "Joe" is an instance of the class of things called "musician". " Joe" plays the role of instance, "musician" plays the role of class in that sentence.

​

Note : In such a sentence, while for a human there is no confusion, but for computers each relationship have to be defined explicitly.

This can be specified as:

[Joe] Isa [Musician]

i.e [Instance] Isa [class]

40

41

• The first part of the figure contains the representations, in which the class membership is represented with unary predicates, each corresponding to a class. Asserting that p(x) is true is equivalent to asserting that X is an instance of p.

​

• The second part uses the instance predicate explicitly. It is a binary one, whose first argument is an object and whose second argument is a class to which the object belongs. The implication rule in statement 3 states that object is an instance of the sub class Pompeian then it is an instance of the superclass Roman.

​

• The third part contains representations that use both the instance and isa predicates explicitly. Use of isa simplifies the representation of sentence 3 but requires one additional axiom. It describes how an instance relation and an isa relation combined to derive a new instance relation.

Computable functions and predicates

42

• All the simple facts can be expressed as combination of individual predicates such as

tryassassinate(Marcus, Caesar)

• This is fine if the number of facts is not very large. But suppose if we want to express simple facts such as greater-than and less-than relationships:

Computable predicates greater-than(1, 0)

greater-than(2, 1)

greater-than(3, 2)

……

less-than(0, 1)

less-than(1, 2)

less-than(2, 3)

……

43

• It is not possible to write out the representation of each of these facts individually as they are infinitely many of them.
• But if only the finite number of them are to be represented, it would be extremely inefficient to store explicitly a large set of statements instead so easily compute each one as we need it.
• Thus it becomes useful to argument the representations by computable predicates.
• A procedure will be invoked which is specified in addition to the regular rules, that will evaluate it and return true or false.
• It is often useful to have computable functions as well as computable predicates.
• Eg:gt(2+3,1), the value of the plus function is computed given the arguments 2 and 3 , and then send the arguments 5 and 1 to gt

Consider the following set of facts, again involving Marcus:

44

45

Set of facts about Marcus

The numbering is changed slightly because sentence 5 has been split into two parts

46

The question is "Is Marcus alive?" This question can be answered by proving

¬alive(Marcus,now)

The term nil at the end of each proof indicates that the list of conditions remaining to be proved is empty and so the proof has succeeded.

47

Resolution

48

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

Rules to Convert into CNF

49

1.Eliminate implication (→) and double implication (↔) a →b can be converted as ¬ a V b

a↔b can be converted as a →b Λ b → a 2.Move negation( ¬) inward

¬(∀xp)=ⱻx ¬p

¬(ⱻxp)= ∀x ¬p

¬(a V b)= ¬ a Λ ¬ b

¬ (a Λb) = ¬ a V ¬ b

¬ ¬ a = a 3.Rename variable

4.Replace the existential quantifier by skolem constant

ⱻx rich(x)=rich(G) 5.Drop the universal quantifier

Steps for Resolution

50

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

51

Example:

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.

52

53

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
• ∀x ¬ food(x) V likes(John, x)
• food(Apple) Λ food(vegetables)
• ∀x ∀y ¬ [eats(x, y) Λ ¬ killed(x)] V food(y)
• eats (Anil, Peanuts) Λ alive(Anil)
• ∀x ¬ eats(Anil, x) V eats(Harry, x)
• ∀x¬ [¬ killed(x) ] V alive(x)
• ∀x ¬ alive(x) V ¬ killed(x)
• likes(John, Peanuts).

54

• Move negation (¬)inwards and rewrite
• ∀x ¬ food(x) V likes(John, x)
• food(Apple) Λ food(vegetables)
• ∀x ∀y ¬ eats(x, y) V killed(x) V food(y)
• eats (Anil, Peanuts) Λ alive(Anil)
• ∀x ¬ eats(Anil, x) V eats(Harry, x)
• ∀x killed(x) V alive(x)
• ∀x ¬ alive(x) V ¬ killed(x)
• likes(John, Peanuts).

55

• Rename variables or standardize variables
• ∀x ¬ food(x) V likes(John, x)
• food(Apple) Λ food(vegetables)
• ∀y ∀z ¬ eats(y, z) V killed(y) V food(z)
• eats (Anil, Peanuts) Λ alive(Anil)
• ∀w¬ eats(Anil, w) V eats(Harry, w)
• ∀g killed(g) V alive(g)
• ∀k ¬ alive(k) V ¬ killed(k)
• 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.

56

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

​

Distribute conjunction 𝖠 over disjunction ¬.

This step will not make any change in this problem.

57

Step-3: Negate the statement

statement,

to be proved

we

In this will apply

negation to the conclusion

which will be

as ¬likes(John,

statements, written 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:

Explanation of Resolution graph

58

• In the first step of resolution graph, ¬likes(John, Peanuts) , and likes(John, x) get resolved(cancelled) by substitution of {Peanuts/x}, and we are left with ¬ food(Peanuts)
• In the second step of the resolution graph, ¬ food(Peanuts) , and food(z) get resolved (cancelled) by substitution of { Peanuts/z}, and we are left with ¬ eats(y, Peanuts) V killed(y) .
• In the third step of the resolution graph, ¬ eats(y, Peanuts) and eats (Anil, Peanuts) get resolved by substitution {Anil/y}, and we are left with Killed(Anil)
• In the fourth step of the resolution graph, Killed(Anil) and ¬ killed(k) get resolve by substitution {Anil/k}, and we are left with ¬ alive(Anil) .
• In the last step of the resolution graph ¬ alive(Anil) and alive(Anil) get resolved.

Unification

59

• Unification is a process of making two different logical atomic expressions identical by finding a substitution. Unification depends on the substitution process.
• It takes two literals as input and makes them identical using substitution.
• Let Ψ₁ and Ψ₂ be two atomic sentences and 𝜎 be a unifier such that, Ψ₁𝜎 = Ψ₂𝜎, then it can be expressed as UNIFY(Ψ₁, Ψ₂).

​

Example: Find the MGU for Unify{King(x), King(John)}

Let Ψ₁ = King(x), Ψ₂ = King(John),

Substitution θ = {John/x} is a unifier for these atoms and applying this substitution, and both expressions will be identical.

​

60

Substitution θ = {John/x} is a unifier for these atoms and applying this substitution, and

both expressions will be identical.

• The UNIFY algorithm is used for unification, which takes two atomic sentences and

returns a unifier for those sentences (If any exist).

• Unification is a key component of all first-order inference algorithms.
• It returns fail if the expressions do not match with each other.
• The substitution variables are called Most General Unifier or MGU.

E.g. Let's say there are two different expressions, P(x, y), and P(a, f(z)).

In this example, we need to make both above statements identical to each other. For this, we will perform the substitution.

P(x, y)......... (i)

P(a, f(z))......... (ii)

• Substitute x with a, and y with f(z) in the first expression, and it will be represented as a/x and f(z)/y.
• With both the substitutions, the first expression will be identical to the second expression

and the substitution set will be: [a/x, f(z)/y].

Conditions for Unification

61

Following are some basic conditions for unification:

• Predicate symbol must be same, atoms or expression with different predicate symbol can never be unified.
• Number of Arguments in both expressions must be identical.
• Unification will fail if there are two similar variables present in the same expression.

Unification Algorithm

62

Natural deduction

63

Problems with resolution:

The heuristic information contained in the original statements can be lost in the transformation.

Example: all judges who are not crooked are well-educated

​

∀x:judge(x) Λ ¬ crooked(x)→educated(x)

​

In this form, the statement suggests a way of deducing that someone is educated. But same statement is converted to clause form.

​

¬judge(x) V crooked(x) V educated(x)

​

It appears also to be a way of deducing that someone is not a judge by showing that he is not crooked and not educated.

64

• Natural deduction: A way of doing machine theorem proving that corresponds more closely to processes used in human theorem proving.

​

• Natural deduction in not a precise term. Rather it describes a mélange of techniques, used in combination to solve problems that are not tractable by one method alone.

UNIT IV

Chapter II Representing Knowledge Using Rules

65

Representing Knowledge Using Rules

66

• Procedural versus declarative knowledge

​

• Logic programming

​

• Forward versus backward reasoning

​

• Matching

​

• Control knowledge

Procedural versus declarative knowledge

67

Declarative representation

• Knowledge is specified but the use is not given.
• Need a program that specifies what is to be done to the knowledge and how.

​

Example:

• Logical assertions and Resolution theorem prover.
• A different way: Logical assertions can be viewed as a program, rather than as data to a program.

=> Logical assertions = Procedural representations of knowledge

68

Procedural representation

• The control information that is necessary to use the knowledge is considered to be embedded in the knowledge itself.

​

• Need an interpreter that follows the instructions given in the knowledge.

​

• The real difference between the declarative and the procedural views of knowledge lies in where control information resides.

Kowalski's equation: Algorithm = Logic + Control

69

71

The real difference between the declarative and procedural views of knowledge lies in where control information resides

Example: man(Marcus) man(Caesar) person(Cleopatra)

∀x: man(x)→ person(x)

Now consider trying to extract from this knowledge base the answer to the question

ⱻy: person(y)

We want bind x to a particular value for which person is true. Our knowledge base justifies any of the following answers.

y=Marcus y=Caesar y=Cleopatra

72

• Because there is no more than one value that satisfies the predicate, but only one value is needed, the answer depends on the order in which the assertions are examined.

​

• Declarative assertions do not say how they will be examined. y=cleopatra is the answer for the question when viewed declaratively.

​

• When viewed procedurally, the answer is Marcus. This happens because the first statement the person goal is the inference rule

∀x: man(x)→ person(x)

​

• This rule sets up a sub goal to find a man. Again the statements are examined from the beginning and now Marcus is found to satisfy the sub goal and thus also the goal.

73

• So Marcus is reported as the answer.

​

• There is no clear cut answer whether declarative or procedural knowledge representation frameworks are better.

Logic programming

74

• Logic Programming is a programming language paradigm on which logical assertions are viewed as programs.
• PROLOG program is described as a series of logical assertions each of which is a Horn Clause.

Prolog program = {Horn Clauses}

Definite clause: A clause which is a disjunction of literals with exactly one positive literal is known as a definite clause or strict horn clause.

Horn clause: disjunction of literals of which at most one(zero or one) is positive literal Hence all the definite clauses are horn clauses.

p, ¬pvq, and p→q are horn clauses.

Example: (¬ p V ¬ q V k). It has only one positive literal k.

It is equivalent to p ∧ q → k.

=>Prolog program is decidable

Control structure: Prolog interpreter = backward reasoning + depth-first with backtracking

75

A representation in logic

∀x:pet(x) Λ small(x) →apartmentpet(x)

∀x:cat(x) v dog(x) →pet(x)

∀x:poodle(x) →dog(x) Λ small(x) Poodle(fluffy)

A representation in PROLOG apartmentpet(x) :- pet(x),small(x) pet(x) :- cat(x)

pet(x) :-dog(x)

dog(x) :-poodle(x)

small(x):-poodle(x) poodle(fluffy)

77

Prolog vs logic

• Quantification is provided implicitly by the way the variables are interpreted. Variables: begin with UPPERCASE letter

Constants: begin with lowercase letters or number

• There is an explicit symbol for AND (,), but there's none for OR. Instead, disjunction must be represented as a list of alternative statements

“p implies q" is written as q :- p

​

• Logical negation (¬) cannot be represented explicitly in pure PROLOG. So, for example, it is not possible to encode directly the logical assertion.

∀x:dog(x) → ¬cat(x)

Problem solving strategy: NEGATION AS FAILURE

?- cat(fullfy). => false because it is unable to prove Fluffy is a cat.

78

• Negation as failure requires: CLOSED WORLD ASSUMPTION which states that all relevant ,true assertions are contained in our knowledge base or derivable from assertions that are so contained.

​

• Whatever not present assertions are take them as false

Forward vs. Backward Reasoning

82

• Reason backward from the goal states: Begin building a tree of move sequences that might be solutions by starting with the goal configurations at the root of the tree.
• Generate the next level of the tree by finding all the rules whose right side match the root node. Use the left sides of the rules to generate the nodes at this second level of the tree.
• Generate the next level of the tree by taking each node at the previous level and finding all the rules whose right sides match it.
• Then use the corresponding left sides to generate the new nodes. Continue until a node that matches the initial state is generated.
• This method of reasoning backward from the desired final state if often called goal-directed reasoning.

83

Forward: from the start states. Backward: from the goal states.

• Reason forward from the initial states: Begin building a tree of move sequences that might be solutions by starting with the initial configurations at the root of the tree. Generate the next level of the tree by finding all the rules whose left sides match the root node and using their right sides to create the new configurations. Continue until a configuration that matches the goal state is generated.
• Reason backward from the goal states: Begin building a tree of move sequences that might be solutions by starting with the goal configurations at the root of the tree. Generate the next level of the tree by finding all the rules whose right side match the root node.

84

Four factors influence forward or Backward?

• Move from the smaller set of states to the larger set of states
• Proceed in the direction with the lower branching factor
• Proceed in the direction that corresponds more closely with the way the user will think
• Proceed in the direction that corresponds more closely with the way the problem-solving episodes will be triggered

​

• To encode the knowledge for reasoning, we need 2 kinds of rules:

​

• Forward rules: to encode knowledge about how to respond to certain input.

​

• Backward rules: to encode knowledge about how to achieve particular goals.

​

The knowledge base:�It contains the specialized expertise required for problem-solving. The information is represented as a set of rules in a rules-based system. Every rule has an IF (condition) THEN (action) structure and defines a relationship, suggestion, directive, strategy, or heuristic. The rule is activated, and the action portion is carried out as soon as the conditional portion of the rule is met.

The database:�The database contains a collection of facts compared to the knowledge base's rules IF (condition) clause.

The inference engine:�The expert system uses the inference engine to derive the logic and arrive at a conclusion. The inference engine's task is to connect the facts kept in the database with the rules specified in the knowledge base. The semantic reasoner is another name for the reasoning engine. It deduces information or executes necessary actions based on data and the rule base present in the knowledge base. For example, the match-resolve-act loop used by the semantic reasoner goes like this:

Match:�A portion of the production rule system is compared to the information in the working memory to create a conflict in which numerous examples of satisfied productions are present.

Conflict Resolution:�Following the matching of the production systems, one of the production cases involved in the conflict will be executed to gauge the procedure's status.

Act:�The production instance chosen in the step before is carried out, changing the information in the working memory.

KR using Rules

87

88

89

90

91

92

93

https://youtu.be/RYIjxRfOPWY?si=vPEsOOlKQdPma2eC refer this video

94

95

Preconditions :

Matching

97

How to extract from the entire collection of rules that can be applied at a given point?

=> Matching between current state and the precondition of the rules Indexing

• One way to select applicable rules is to do a simple search through all the rules, comparing each one's preconditions to the current state and
• extracting all the ones that match.
• But there are two problems with this simple solution:
• It will be necessary to use a large number of rules. scanning through all of them at every step of the search would be hopelessly inefficient.
• It is not always immediately obvious whether a rule's preconditions are satisfied by a particular state.

98

Indexing

• A large number of rules => too slow to find a rule
• Indexing: Use the current state as an index into rules and select the matching ones immediately
• There's a trade-off between the ease of writing rules (high-level descriptions) and the simplicity of the matching process

100

2. Matching with the variables

Many to many mapping algorithm–RETE Algoritham

RETE one efficient many-many match algorithm fot three main reasons.

a)The temporal nature of data.

Whenever u apply rules usually do not alter the state description radically.

If a rule did not match in the previous cycle ,it will most likely fail to apply in the current cycle

Instead a rule will add one or two elements or delete one or two elements but the state remains the same.

RETE maintains a network of rule conditions and (is filtering process )

It uses changes in the state description to determine which new rules might apply and which is no longer apply.(Many to Many matching) Many rules are matched against many elements in the state description simultaneously.

​

b)Structural similarity in rules.

Different rules may share a large number of pre-conditions

EX: one rule concludes jaguar(x) if mammal(x),feline(x),carnivorous(x) and has-spots(x). Another rule concludes tiger(x) and is identical to the first rule except that it replaces has-spots with has-stripes. If two rules are matched independently, a lot of work is repeated unnecessarily.

RETE stores rules so that they share structures in memory. Sets of conditions that appear in sever at rules are matched once per cycle.

101

• C)Persistence of variable binding consistency: while all the individual preconditions of a rule might be met there may be variable binding conflicts that prevent the rule from firing.

​

• Son(Mary,joe) and son (Bill,Bob).
• The individual preconditions of the rule can be matched
• Son(x,y) A son(y,z) → grandparent(x,z)
• Can be matched, but not in a manner that satisfies the constraint imposed by the variable y.

102

3.Approximate matching (Complex and appropriate matching)

• Rules should be applied if their preconditions approximately match the current situation
• Example: A speech-understanding program
• Rules: A description of a physical waveform to phones (a, e, ...)
• Physical signal: differences in the way individuals speak, result of background noise, ...

105

106

4. Conflict resolution:

The result of the matching process is a list of rules whose antecedents have matched the current state description along with the binding variables

The order of the rules

• Preferences based on rules:

-Specificity the physical order of rules and give priority the first that appeear first

-Physical order of rules

• Preferences based on objects:

-Importance of objects

-Position of objects

• Preferences based on action:

-Evaluation of states

Applying all the rules at a time and examine result is appropriate use it other things throw them out

Control knowledge

107

• Knowledge about which paths are most likely to lead quickly to a goal state is often called search control knowledge.

Knowledge about -Which states are more preferable to others.

-Which rule to apply in a given situation.

-The order in which to pursue sub goals

-Useful sequences of rules to apply.

Here we r acquiring

Search control knowledge = Meta knowledge(knowledge about knowledge)

108

There are a number of Al systems that represent their control knowledge with rules. Example SOAR,PRODIGY SOAR is a general architecture for building intelligent systems.

​

• Long-term memory is stored as a set of productions (or, rules).
• Short term memory (also called working memory) is a buffer that is affected by perceptions and serves as a storage area for facts deduced by rules in long term memory. Working memory is analogous to the state description in problem solving.
• All problem-solving activity takes place as state space traversal. There are several classes of problem-solving activities, including reasoning about which states to explore, which rules to apply in a given situation, and what effects those rules will have.
• MI intermediate and final results of problem solving are remembered (or, chunked) for future reference.

109

• PRODIGY is a general purpose problem solving system, that incorporates several different learning mechanisms.
• It can acquire control rules in a number of ways:
• Through hand coding by programmers
• Through a static analysis of the domain's operators.
• Through looking at traces of its own problem solving behaviour.
• PRODIGY learns control rules from its experience,
• but unlike SOAR it learns from its failures.
• PRODIGY pursues an unfruitful path, it will try to come up with an explanation of why that path failed. It will then use that explanation to build control knowledge that will help it avoid fruitless search paths in future.

110

Two issues concerning control rules:

• The first issue is called the utility problem. As we add more and more control knowledge to a system, the system is able to search more judiciously. If there are many control of rules, simply matching them all can be very time consuming.

​

• The second issue concerns with the complexity of the production system interpreter.

THE END

111