ARTIFICIAL INTELLIGENCE & MACHINE LEARNING

Unit:3

Using Predicate logic: Representing simple facts in logic - Representing

Instance and Isa relationships - Computable functions and predicates -
Resolution - Natural deduction. Representing knowledge using rules:
Procedural Vs Declarative knowledge- Logic programming
-Forward Vs Backward reasoning -Matching-Control knowledge.

Using Predicate logic:

The Frame Problem in AI and knowledge representation, when using predicate logic, poses
significant challenges because predicate logic primarily focuses on describing the world in
terms of relations between objects, actions, and states. In order to represent dynamic
actions and their consequences (such as what remains unchanged when an action is
performed), predicate logic must be extended or supplemented with additional mechanisms
to efficiently manage these non-effects.

Let's break down how predicate logic can be used in the context of the frame problem and
the approaches that have been used to address it.

Predicate Logic Basics

Predicate logic (also called first-order logic) allows us to represent facts using predicates. A
predicate is a function that takes one or more arguments and returns a true/false value. For
example:

 On(table, cup) could be a predicate that states "the cup is on the table."
 At(robot, location) could be a predicate that says "the robot is at the given location."

A typical example of using predicate logic for representing actions:

 Move(cup, tableA, tableB) represents the action of moving a cup from Table A to Table B.
 The effects of this action could be represented as:
o ¬On(cup, tableA) (the cup is no longer on Table A).
o On(cup, tableB) (the cup is now on Table B).

The Challenge of the Frame Problem in Predicate Logic

The Frame Problem arises when trying to represent the fact that certain properties of the
world do not change as a result of an action. For example, after moving the cup from Table
A to Table B, the color of the cup, its weight, and the presence of other objects on the tables
should be unchanged. In predicate logic, however, to ensure correctness, we would have to
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING

explicitly state all the properties that do not change, which is impractical for complex
domains.

Example: Using Predicate Logic to Represent Actions and Non-effects

Let’s walk through a simple example using predicate logic:

1. Initial State:
o On(cup, tableA) (The cup is on Table A)
o Color(cup, red) (The cup is red)
o On(book, tableB) (There’s a book on Table B)

2. Action:
o Move(cup, tableA, tableB) (Move the cup from Table A to Table B)

3. Effect of the Action:

o ¬On(cup, tableA) (The cup is no longer on Table A)
o On(cup, tableB) (The cup is now on Table B)

4. Non-effects (What doesn't change):

o Color(cup, red) (The color of the cup remains red)
o On(book, tableB) (The book remains on Table B)

Problem: Non-effects Need to Be Explicitly Represented

In predicate logic, you would need to explicitly write out what does not change after the
action. For instance, for every object and property in the world, you would need to specify
that their status remains unchanged unless directly modified by the action. If there are
hundreds or thousands of predicates, this becomes unwieldy.

For example, after the move action, you might need to state:

 ¬On(cup, tableA) (Cup is no longer on Table A)

 On(cup, tableB) (Cup is now on Table B)
 Color(cup, red) (Color is still red)
 On(book, tableB) (Book is still on Table B)

For a large number of objects, this quickly grows redundant and inefficient.

Solutions Using Predicate Logic

To address this issue in predicate logic, several techniques have been developed:

1. Frame Axioms

 Frame axioms are used to explicitly represent which facts do not change after an action. In a
naive approach, you would need to write an axiom for every possible property of every object to
specify that it remains unchanged after an action.
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING

Example of a frame axiom for a cup being moved:

∀x (Move(cup, tableA, tableB) → (¬On(cup, tableA) ∧ On(cup, tableB)) ∧ (Color(cup, red)) ∧ (∀y ≠ cup
(¬On(y, tableA) → ¬On(y, tableB))))

Here, you would have to explicitly state that the color of the cup and other unrelated facts
(e.g., On(book, tableB)) do not change. This is feasible for small problems, but as the world
grows in complexity, the number of frame axioms becomes prohibitive.

2. Reified Fluents and Fluent Calculus

 Fluent calculus is a formalism that reifies properties (called fluents) into state variables that can
change over time. Rather than explicitly stating what remains unchanged, it focuses only on
those properties that do change, implicitly leaving the rest unchanged.

Example using fluent calculus:

 On(cup, tableA) becomes a fluent that can change, but you don’t need to explicitly say it doesn’t
change in every action.
 When you move the cup, the state of On(cup, tableA) and On(cup, tableB) will change. All other
facts (like the color of the cup or the position of the book) are assumed to remain unchanged
unless affected by some action.

3. Nonmonotonic Reasoning

 Nonmonotonic reasoning allows the system to assume default behavior (such as properties that
remain unchanged) but to retract that assumption if new evidence contradicts it. This approach
addresses the problem by allowing for defaults that can be updated when necessary.

Example:

 If an agent knows that typically, actions do not change the color of the cup, it can assume that
Color(cup, red) remains unchanged unless an action specifies otherwise (e.g., painting the cup).
 Nonmonotonic reasoning lets the system make conclusions based on default assumptions, but
revise those conclusions if the action contradicts the default assumption.

4. Situation Calculus with Frame Axioms

 Situation calculus is a formalism used to represent actions, states, and their effects in dynamic
environments. In situation calculus, the world is represented as a sequence of situations, and
actions are modeled as transitions between these situations.

To address the frame problem in situation calculus, we would use frame axioms to specify
that most things remain unchanged unless an action explicitly modifies them. While this is
still an explicit representation, it helps structure the world in a way that actions and their
consequences are easier to model.

For example:
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING
 Before and after moving the cup:
o On(cup, tableA, s) becomes On(cup, tableB, s') after the action Move(cup, tableA, tableB).
o Color(cup, red, s) ≡ Color(cup, red, s') (Color remains unchanged).
 This requires fewer frame axioms than representing all properties explicitly, though it still relies
on some explicit non-effects.

Representing simple facts in logic:

Representing simple facts in logic, especially in predicate logic (also called first-order logic),
involves encoding facts as logical statements or predicates. Predicates are functions that
take one or more arguments and return a true or false value, and they are used to represent
relationships or properties in a formal way. These facts are structured using logical symbols
and can be interpreted by a computer or reasoning system.

Components of Predicate Logic

1. Predicates: These represent relations or properties. A predicate can take one or

more arguments. For example:
o On(x, y): "Object x is on object y"
o Likes(person, food): "Person likes food"
o Married(x, y): "x is married to y"

2. Constants: These represent specific objects or entities in the domain of discourse.

o John, Mary, table, cup could all be constants in a certain knowledge domain.

3. Variables: These are placeholders that can stand for any object in the domain of
discourse. For example, x, y, z can represent arbitrary objects.

Universal Quantifier ( ∀ ): "For all..."

4. Quantifiers: These specify the scope of variables in a logical statement.

Existential Quantifier ( ∃ ): "There exists..."

o
o

For example:

∀x Likes(x, pizza): "Everyone likes pizza."

∃x Likes(x, pizza): "Someone likes pizza."
o
o

Representing Simple Facts

Now, let’s look at how to represent simple facts in predicate logic. Here are a few examples
of how common facts can be represented:

1. Describing Properties of Objects

 Fact: "John is tall."

o In predicate logic:
 Tall(John)
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING
o Here, Tall is a predicate representing the property of being tall, and John is a constant
representing a specific person.

 Fact: "The cup is red."

o In predicate logic:
 Red(cup)
o Red is a predicate that represents the property of being red, and cup is a constant
representing a specific object.

2. Describing Relations Between Objects

 Fact: "John is sitting on the table."

o In predicate logic:
 On(John, table)
o On is a predicate representing the relationship between the two objects (John and the
table).

 Fact: "The book is next to the cup."

o In predicate logic:
 NextTo(book, cup)
o NextTo is a predicate that indicates the spatial relationship between book and cup.

3. Describing Relationships Between Entities

 Fact: "John likes pizza."

o In predicate logic:
 Likes(John, pizza)
o Likes is a predicate representing the relationship between John and pizza. John and
pizza are constants, and the predicate signifies a positive liking relationship.

 Fact: "Mary is married to John."

o In predicate logic:
 Married(Mary, John)
o Married is a predicate that represents a relationship between two individuals.

4. Universal and Existential Quantifiers

Using quantifiers, we can generalize facts.

 Fact: "Everyone likes pizza."

 ∀x Likes(x, pizza)
o In predicate logic:
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING
o This uses the universal quantifier (∀x), meaning "for all x", where x could be any
person.

 Fact: "Someone likes pizza."

 ∃x Likes(x, pizza)
o In predicate logic:

o This uses the existential quantifier (∃x), meaning "there exists an x", where x is a person
who likes pizza.

5. Combining Facts with Logical Connectives

Logical connectives (AND, OR, NOT, IMPLIES) allow you to combine multiple facts into
one more complex logical expression.

 Fact: "John is tall and the cup is red."

 Tall(John) ∧ Red(cup)
o In predicate logic:

o Here, ∧ is the logical AND, meaning both facts need to be true.

 Fact: "If it is raining, then the ground is wet."

o In predicate logic:
 Rainy → Wet(ground)
o → represents implication (if-then), meaning if the first fact ( Rainy) is true, then the
second fact (Wet(ground)) must also be true.

6. Negative Facts

We can also represent facts in the negative.

 Fact: "John is not tall."

o In predicate logic:
 ¬Tall(John)
o ¬ represents negation (not), indicating that the property of being tall does not hold for
John.

 Fact: "The cup is not on the table."

o In predicate logic:
 ¬On(cup, table)
o This negates the On relation, meaning the cup is not currently on the table.

Examples of Simple Facts in Predicate Logic

 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING

Let’s look at several examples of simple facts and how they would be represented in
predicate logic:

1. Fact: "The cat is on the mat."

o On(cat, mat)

∃x (Book(x) ∧ On(x, table))

2. Fact: "There is a book on the table."
o

The existential quantifier (∃x) means that such a book exists.

o Here, Book(x) says that x is a book, and On(x, table) states that the book is on the table.

∀x (Person(x) → Likes(x, ice_cream))

3. Fact: "Every person likes ice cream."
o
o This states that for all x, if x is a person (Person(x)), then x likes ice cream (Likes(x,
ice_cream)).

∃x (Person(x) ∧ Likes(x, ice_cream))

4. Fact: "There is a person who likes ice cream."
o
o This states that there exists some x who is a person and likes ice cream.

Representing Instance and Isa relationships:

In knowledge representation, the instance and ISA (is-a) relationships are fundamental for
organizing knowledge and capturing how entities and concepts are related. These
relationships are commonly used to model taxonomies or hierarchical structures.

Let's break down how instance and ISA relationships are represented in logic.

1. The ISA (Is-A) Relationship

The ISA relationship is used to indicate that an object or entity is a type or subclass of
another more general concept or class. In other words, it expresses a hierarchical
relationship where one entity is a more specific example of a more general category.

 Example: "A dog is an animal."

o This can be read as: "dog is a type of animal."

In predicate logic, we can represent the ISA relationship as follows:

Representation in Predicate Logic:

We use the predicate ISA(x, y) to represent the idea that x is an instance of y (or that x is a
type of y).

 ISA(dog, animal) means "dog is a type of animal."

 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING
 ISA(crow, bird) means "crow is a type of bird."

More generally, you could define a rule that states that if something is a type of animal, it
might inherit certain properties or relationships. For example, you might have a rule that
states "All dogs are animals" in a more formal logic system:

 ∀x (Dog(x) → ISA(x, animal))

This says: "For all x, if x is a dog, then x is an animal."

2. The Instance Relationship

The instance relationship (sometimes called individual relationship) refers to the

connection between a specific object (or individual) and the class it belongs to. It indicates
that a particular entity is an instance of a given class or type.

 Example: "Fido is a dog."

o Here, Fido is an instance of the class dog.

Representation in Predicate Logic:

We can represent the instance relationship using the predicate Instance(x, y), where x is an
individual object and y is the class.

 Instance(fido, dog) means "Fido is an instance of the class dog."

More commonly, we express an instance relationship in terms of classes or types as

individuals belonging to a type. So, Fido being a dog can be represented as:

 Dog(fido) means "Fido is a dog."

Combining ISA and Instance Relationships

In many knowledge representation systems, ISA and Instance relationships are closely tied,
and together they help structure the knowledge. For instance, the ISA relationship is often
used to represent a taxonomic hierarchy, and the instance relationship can link specific
objects to their types.

Example 1: Hierarchical Structure

Consider a hierarchical structure like:

 dog is an instance of the class mammal (a dog is a type of mammal).

 mammal is an instance of the class animal (a mammal is a type of animal).

In predicate logic:
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING
1. ISA(dog, mammal) means "dog is a type of mammal."
2. ISA(mammal, animal) means "mammal is a type of animal."
3. Instance(fido, dog) means "Fido is an instance of dog."

We could represent this as:

 ISA(dog, mammal) (dog is a type of mammal)

 ISA(mammal, animal) (mammal is a type of animal)
 Instance(fido, dog) (Fido is a dog)

This structure can be extended to represent other entities in a hierarchy (e.g., cat is an
animal, sparrow is a bird, etc.).

Example 2: Class Inheritance with Properties

The ISA relationship is often used to inherit properties from parent classes. For example, if
we say "all mammals have a backbone," the ISA relationship allows us to inherit this
property for all instances of mammals.

 ISA(dog, mammal) means "dog is a mammal."

 HasBackbone(mammal) means "All mammals have a backbone."
 So, because dog is a mammal, HasBackbone(dog) holds as well.

This can be formalized as:

 ∀x (ISA(x, mammal) → HasBackbone(x))

 ISA(fido, dog) → HasBackbone(fido)

This means, "If fido is an instance of dog, and dogs are mammals, then fido must have a
backbone."

Generalization in Predicate Logic

Example 3: Generalizing the ISA and Instance Relationships

If you want to represent instances of specific classes and also the inheritance of properties
through the ISA relationship, you can generalize this in the following way:

 Let’s say we have an ISA relationship:

o ISA(dog, mammal) (dog is a type of mammal)
o ISA(mammal, animal) (mammal is a type of animal)
 You could combine these with properties inherited from the parent classes:
o HasBackbone(mammal) (mammals have a backbone)
o HasBackbone(dog) (since dog is a mammal, dogs have a backbone)

To represent this:

1. ∀x (ISA(x, mammal) → HasBackbone(x))

2. ISA(fido, dog) (Fido is a dog)
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING
3. ISA(dog, mammal) (Dog is a type of mammal)
4. HasBackbone(fido) (Fido has a backbone)

Computable functions and predicates:

In the context of logic and knowledge representation, computable functions and predicates
are two essential components used to express relations, properties, and operations in formal
systems. These concepts are crucial for reasoning about the world and representing
information that can be processed by an artificial intelligence system.

Let’s break down the concepts and their usage:

1. Predicates

A predicate is a fundamental concept in logic, especially in predicate logic (also known as

first-order logic). It is used to express a property of an object or a relationship between
objects. A predicate takes arguments (which can be constants, variables, or functions) and
returns a true/false value, indicating whether a certain property holds or a relation exists.

Key Characteristics of Predicates:

 Arity: The number of arguments a predicate takes. For example, a predicate On(x, y) has arity 2
because it takes two arguments.
 Domain: The set of possible values for the arguments (objects or entities) that the predicate can
operate on.

Examples of Predicates:

1. Unary Predicate (Property of a single object):

o Tall(x) — "x is tall"
o Red(x) — "x is red"
o Here, x is a single object, and the predicate evaluates whether this object has the
property of being tall or red.

2. Binary Predicate (Relation between two objects):

o On(x, y) — "x is on y"
o Loves(x, y) — "x loves y"
o These predicates take two arguments and express relationships between the objects.

3. Higher-Order Predicate (Relation involving more complex structures):

o Friend(x, y, z) — "x and y are friends with z"
o This predicate could be defined with more complex relationships between the involved
objects.

Example in Predicate Logic:

 On(cup, table) means "the cup is on the table."

 Likes(john, pizza) means "John likes pizza."
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING

In this case, On and Likes are predicates, and cup, table, john, and pizza are the arguments.

2. Computable Functions

A computable function is a function that can be evaluated or computed using a well-defined

procedure or algorithm. In the context of formal logic, computable functions are typically
used to map objects from one set to another, often to represent numerical calculations or
transformations on data.

Computable functions are more general than predicates. A predicate gives a true/false
value based on the properties or relations of its arguments, whereas a computable function
returns an object of a specific type, such as a number, set, or another object, based on the
input.

Key Characteristics of Computable Functions:

 Domain and Range: A function has a domain (the set of all possible inputs) and a range (the set
of all possible outputs).
 Evaluability: A function is called "computable" if there is an algorithm or procedure to evaluate
it for any given input.

Examples of Computable Functions:

1. Arithmetic Function:
o Add(x, y) — "Add x and y"
 If x = 3 and y = 4, then Add(x, y) = 7.
2. String Manipulation Function:
o Concatenate(x, y) — "Concatenate two strings x and y"
 If x = "Hello" and y = "World", then Concatenate(x, y) = "HelloWorld".
3. Distance Function:
o Distance(x, y) — "The distance between point x and point y"
 If x and y represent coordinates in a 2D plane, then this function computes the
Euclidean distance between the two points.

Example of a Computable Function:

 Let Add(x, y) be a function that returns the sum of two numbers.

o If Add(3, 4) is evaluated, the result is 7.

3. Relationship Between Functions and Predicates

While both computable functions and predicates are used to represent relationships and
properties in formal logic, they differ in their outputs and how they are used in reasoning.
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING
 Predicates return a truth value (true or false) based on whether a specific relation or property
holds.
 Functions return a value (such as a number, object, or set), often based on the transformation of
input objects.

For instance, consider the following example:

 Predicate Example: On(x, y) — "x is on y". This evaluates to true if the object x is indeed on the
object y, and false otherwise.
 Function Example: Distance(x, y) — "The distance between x and y". This returns a numerical
value, which could be used in calculations.

4. Computability and Logic

The concept of computability is central in formal systems, and it ties closely to what can be
effectively represented and reasoned about using logic. For a function to be considered
computable, it must be evaluable by an algorithm or mechanical procedure.

In first-order logic and related areas of AI and computer science, computable functions are
usually defined based on some formal model of computation, such as:

 Turing machines
 Lambda calculus
 Recursive functions

These models help define which functions are "computable" and can be used within the
system for reasoning or problem-solving.

5. Example of Predicates and Functions in a Knowledge Base

Consider a knowledge base about geographical locations:

 City(name) — "name is a city"

 Country(name) — "name is a country"
 Capital(city, country) — "city is the capital of country"

You could use the following predicates and functions in reasoning about cities and
countries:

 Predicate Example: Capital(paris, france) — "Paris is the capital of France."

 Function Example: Distance(city1, city2) — "The distance between two cities." It returns a
numerical value (e.g., 350 km) rather than a true/false value.
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING

You might use a computable function like Distance to compute distances between various
cities and combine this with predicates to infer relationships like "Which cities are
capitals?" or "How far apart are two cities?"

6. Using Predicates and Functions in Logical Systems

 Predicates and functions are used together to reason about the world, query knowledge bases,
and perform computations.
 Predicate logic allows for complex relationships between objects, while computable functions
enable more dynamic and numerical operations.

For example, in a planning system:

 A predicate could be used to check if a goal is satisfied ( At(robot, location)), and a function could
be used to calculate the time to move from one location to another ( TimeToMove(robot, from,
to)).

Natural deduction:

Natural Deduction is a formal system used in logic to represent reasoning steps and prove
the validity of logical statements. It is often used in propositional logic and first-order logic
(predicate logic). Natural Deduction focuses on deriving conclusions from premises using a
set of inference rules that mirror the natural patterns of human reasoning. It is called
"natural" because it aims to reflect how we might reason about truth in a structured,
logical way.

The system of natural deduction provides rules for both introduction and elimination of
logical connectives (such as AND, OR, NOT, and IMPLIES), as well as quantifiers (in
predicate logic). These rules allow us to break down complex formulas into simpler
components and build up arguments step-by-step.

Key Components of Natural Deduction

1. Propositions: These are logical statements that are either true or false.
o Example: P, Q, R, etc.

2. Logical Connectives: These are operators that connect propositions.

∧ (conjunction, or "and")
o ¬ (negation)

∨ (disjunction, or "or")
o
o
o → (implication, or "if-then")
o ↔ (biconditional, or "if and only if")

3. Inference Rules: These are the rules that allow us to derive new propositions from
existing ones.
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING

Inference Rules in Natural Deduction

1. Propositional Logic

Here are the main rules used in propositional logic within natural deduction:

 Modus Ponens (→-Elimination):

o If you have a statement of the form "P → Q" (if P then Q), and you also have "P" (P is
true), you can conclude "Q".
o Rule:
1. P → Q
2. P
Conclusion: Q
 Modus Tollens (¬→-Elimination):
o If you have "P → Q" and "¬Q" (not Q), you can conclude "¬P" (not P).
o Rule:
1. P → Q
2. ¬Q
Conclusion: ¬P

o If you have "P" and "Q", you can conclude "P ∧ Q" (P and Q).
 Conjunction (∧-Introduction):

o Rule:
1. P

Conclusion: P ∧ Q
2. Q

o If you have "P ∧ Q", you can conclude both "P" and "Q".
 Conjunction Elimination (∧-Elimination):

∧
o Rule:
1. P Q
Conclusion: P
Conclusion: Q

o If you have "P", you can conclude "P ∨ Q" (P or Q).

 Disjunction (∨-Introduction):

o Rule:

Conclusion: P ∨ Q
1. P

o If you have "P ∨ Q", and you can prove "R" from both "P" and "Q", you can conclude
 Disjunction Elimination (∨-Elimination):

"R".

1. P ∨ Q
o Rule:

2. P → R
3. Q → R
Conclusion: R
 Negation Introduction (¬-Introduction):
o To prove "¬P" (not P), you assume "P" and derive a contradiction, showing that P
cannot be true.
o Rule:
1. Assume P
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING
2. Derive a contradiction (e.g., both P and ¬P are true).
Conclusion: ¬P
 Negation Elimination (¬-Elimination):
o If you have "¬¬P", you can conclude "P" (double negation elimination).
o Rule:
1. ¬¬P
Conclusion: P
 Implication Introduction (→-Introduction):
o To prove "P → Q", assume "P", and from that assumption, prove "Q".
o Rule:
1. Assume P
2. Derive Q
Conclusion: P → Q

2. Predicate Logic (First-Order Logic)

In predicate logic, you have variables, predicates, and quantifiers ( ∀ for "for all" and ∃ for
"there exists"). The rules of natural deduction extend to these constructs.

 Universal Introduction (∀-Introduction):

specific assumption about x), you can conclude ∀x P(x) (for all x, P(x) is true).
o If you can derive a statement P(x) for an arbitrary object x (not depending on any

o Rule:

Conclusion: ∀x P(x)
1. Derive P(x) with no assumptions about x.

o If you know that ∀x P(x) (for all x, P(x)), you can instantiate it with any specific object,
 Universal Elimination (∀-Elimination):

say a, and conclude P(a).

1. ∀x
o Rule:
P(x)
Conclusion: P(a)

o If you can prove P(a) for some specific object a, you can conclude ∃x P(x) (there exists
 Existential Introduction (∃-Introduction):

some x such that P(x) is true).

o Rule:

Conclusion: ∃x P(x)
1. P(a)

o If you know that ∃x P(x) (there exists some x such that P(x) is true), and you can prove R
 Existential Elimination (∃-Elimination):

from both an assumption of P(a) and a subsequent argument, you can conclude R.

1. ∃x P(x)
o Rule:

2. Assume P(a) for some arbitrary a

3. Derive R from P(a)
Conclusion: R

Example of Natural Deduction in Action

 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING

Let's go through an example of a natural deduction proof:

Premises:

1. P → Q (If P then Q)
2. P (P is true)

Goal:

Prove Q.

Proof:

1. P → Q (Premise)
2. P (Premise)
3. Q (By Modus Ponens on 1 and 2)

Since we derived Q using Modus Ponens (from P → Q and P), the proof is complete.

Advantages of Natural Deduction

 Intuitive: The rules mimic natural reasoning patterns, which makes the system easier to
understand and use.
 Formal and Rigorously Defined: Even though the rules reflect natural reasoning, they are
formally defined, allowing for precise proofs and derivations.
 Foundations for Automated Theorem Proving: Many automated theorem-proving systems, like
those used in artificial intelligence and computer science, rely on natural deduction for
formalizing and checking proofs.

Representing knowledge using rules:

Representing knowledge using rules is a central concept in artificial intelligence (AI), logic
programming, and expert systems. Rules allow a system to infer new knowledge based on
known facts, which makes it easier to reason and make decisions based on available
information.

Rules are typically represented as if-then statements or logical implications that capture
relationships or causal connections between different pieces of knowledge. In the context of
knowledge representation, these rules are used to define how to infer new information from
existing facts or how to automate decision-making processes.

Key Components of Rule-Based Knowledge Representation

1. Facts: These are the basic pieces of information or knowledge that are known or
assumed to be true. Facts represent the state of the world or system at any given
time.
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING
o Example: "John is a student", "The sky is blue".

2. Rules: These are the logical connections that express how facts or data lead to other
facts. Rules are generally written in the form of if-then statements:
o If condition(s) are true, then conclusion follows.
o Example: "If it is raining, then the ground is wet".
o Rules can be written formally in a variety of logical forms, such as propositional logic or
predicate logic.

3. Inference Mechanism: The process or engine that applies the rules to known facts to
derive new facts or make decisions.
o Forward Chaining: This involves starting with known facts and applying rules to infer
new facts (data-driven reasoning).
o Backward Chaining: This involves starting with a goal (or hypothesis) and working
backward to find the facts that support it (goal-driven reasoning).

Types of Rules

1. Production Rules (or IF-THEN Rules): These rules are the most common form of
rule-based representation. They specify a condition that triggers an action.
o Format: IF condition THEN action
o Example: IF X is true THEN Y is true

2. Logical Rules: These rules are more formal and are typically used in systems based
on logic (like propositional logic or predicate logic). They are written in the form of
logical implications.
o Example: P → Q (If P is true, then Q is true)

3. Derivation Rules: In formal logic, these rules describe how to derive new
propositions or facts from others. These rules follow logical deduction and may be
used in inference systems to build complex reasoning processes.
o Example: Modus Ponens: IF P → Q AND P THEN Q

Example of Representing Knowledge Using Rules

Let's consider a medical diagnosis system as an example, where rules are used to infer a
diagnosis based on symptoms.

Facts:

 "Patient has a fever"

 "Patient has a sore throat"
 "Patient has a cough"
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING
Rules:

1. If the patient has a fever and a sore throat, then the patient might have a viral infection.
o IF Fever AND SoreThroat THEN ViralInfection
2. If the patient has a cough and a fever, then the patient might have the flu.
o IF Cough AND Fever THEN Flu
3. If the patient has a sore throat and a cough, then the patient might have a cold.
o IF SoreThroat AND Cough THEN Cold

Applying the Rules (Inference):

1. The system checks the known facts.

o "Patient has a fever" is true.
o "Patient has a sore throat" is true.
o "Patient has a cough" is true.

2. The system applies the rules:

o The first rule (fever + sore throat → viral infection) applies and concludes that the
patient might have a viral infection.
o The second rule (fever + cough → flu) applies and concludes that the patient might have
the flu.
o The third rule (sore throat + cough → cold) applies and concludes that the patient might
have a cold.

3. The system can use forward chaining or backward chaining to derive further
conclusions or actions based on these facts and rules.

Knowledge Representation Languages for Rules

There are several formal languages for representing knowledge using rules. Some common
ones include:

1. Prolog (Programming in Logic):

o Prolog is a declarative programming language based on first-order logic. It represents
knowledge as a set of rules and facts.
o Example:
o fever(patient).
o sore_throat(patient).
o cough(patient).
o
o viral_infection(Patient) :- fever(Patient), sore_throat(Patient).
o flu(Patient) :- fever(Patient), cough(Patient).
o cold(Patient) :- sore_throat(Patient), cough(Patient).

2. Rule-based Expert Systems:

o Expert systems often use a production rule language to represent knowledge. These
systems use an inference engine to apply rules to facts in order to derive conclusions.
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING
o Common rule-based languages include CLIPS and Jess.

3. RDF and SPARQL (for Semantic Web):

o RDF (Resource Description Framework) is a standard for representing information on
the web using triples (subject-predicate-object). Rules can be used in conjunction with
RDF to make inferences.
o SPARQL is a query language used to retrieve and manipulate RDF data, including
rules-based inferences.

Advantages of Representing Knowledge Using Rules

1. Transparency and Interpretability: Rule-based systems are often easy to understand

because they use explicit "if-then" statements, which makes reasoning transparent.
2. Flexibility: You can easily add, modify, or remove rules to adjust the system's
behavior or knowledge base.
3. Logical Inference: Rules enable formal logic-based reasoning, such as deriving new
facts or conclusions from existing ones.
4. Automation: Once the rules and facts are established, the system can automatically
make inferences or decisions, which is useful in decision support systems and AI
applications.

Challenges in Rule-Based Knowledge Representation

1. Complexity: As the number of facts and rules increases, managing and maintaining
the rule base becomes more difficult. Large rule bases may also lead to inefficiency
in processing.
2. Ambiguity: Rules may become ambiguous or inconsistent, especially when facts and
rules are contradictory.
3. Scalability: As systems grow in size and complexity, ensuring that rules are applied
efficiently and correctly can become a challenge.
4. Handling Uncertainty: Standard rule-based systems often assume binary true/false
logic, but in real-world applications, knowledge is often uncertain. Techniques like
fuzzy logic or probabilistic reasoning may be needed.

Procedural Vs Declarative knowledge:

Procedural knowledge and declarative knowledge are two fundamental types of knowledge
representation in artificial intelligence (AI), cognitive science, and philosophy of mind.
These concepts describe different ways that knowledge is stored, processed, and applied,
and they correspond to different types of reasoning and problem-solving strategies.

1. Declarative Knowledge
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING

Declarative knowledge refers to knowledge about facts, concepts, and relationships that can
be explicitly stated or described. It is static knowledge that can be represented as facts or
statements that are true or false.

 Nature: Describes what something is, what is true, or what exists in the world.
 Format: It is often represented in the form of propositions, sentences, or statements.
o Example: "The sky is blue" or "John is a doctor."
 Also Known As: "Knowing that" (e.g., knowing that the Earth revolves around the Sun).

Characteristics of Declarative Knowledge:

 Explicit: It consists of facts, information, and definitions that can be directly retrieved.
 Formal Representation: Can be represented in formal structures like semantic networks,
frames, propositional logic, or first-order logic.
 Retrieval-Based: To use declarative knowledge, the system typically retrieves or looks up the
relevant facts or information.

Example of Declarative Knowledge:

 Fact Representation: "Water boils at 100°C at sea level."

o This is a statement that can be verified as true or false.
 In a Knowledge Base:
o BoilingPoint(water, 100°C)
o Human(age=30, name=John)

In an expert system or AI system, declarative knowledge can be stored in databases or

knowledge bases and used for inference or answering queries.

2. Procedural Knowledge

Procedural knowledge refers to knowledge about how to do something—i.e., the methods,

processes, or procedures that lead to a specific outcome. It is dynamic knowledge that
describes actions or steps in a sequence, often involving problem-solving or skills.

 Nature: Describes how things are done, how to perform tasks or operations.
 Format: It is typically represented in the form of instructions, algorithms, or processes.
o Example: "To boil water, heat it until it reaches 100°C" or "To solve a math equation,
first isolate the variable."
 Also Known As: "Knowing how" (e.g., knowing how to ride a bike or knowing how to cook).

Characteristics of Procedural Knowledge:

 Implicit: Unlike declarative knowledge, procedural knowledge is often not explicitly stated. It's
learned through experience or practice.
 Action-Oriented: Focuses on carrying out operations, performing actions, or following a
sequence of steps to achieve a goal.
 Dynamic: Procedural knowledge changes or adapts based on context and goals, and is more
about how to perform tasks rather than simply recalling facts.
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING
Example of Procedural Knowledge:

 Cooking Procedure: "To bake a cake, mix flour, sugar, and eggs, then put the mixture in an oven
at 180°C for 30 minutes."
 Algorithm: The step-by-step procedure for sorting numbers (e.g., the bubble sort algorithm or
quick sort algorithm).

In an AI system, procedural knowledge is represented by rule-based systems, algorithms,

or programming that describe how to achieve a goal. For instance, an AI agent might
follow a set of procedural rules to navigate a maze or perform an operation in robotics.

Comparison: Procedural vs. Declarative Knowledge

Aspect Declarative Knowledge Procedural Knowledge

"Knowing that" facts, truths, or "Knowing how" to perform tasks,
Definition
information about the world. procedures, or actions.
Nature Static, descriptive, and declarative. Dynamic, action-oriented, and operational.
Focused on knowledge about what things Focused on knowledge about how to do
Focus
are. things.
Facts, rules, relationships (e.g., "The Algorithms, procedures, instructions (e.g.,
Examples
Earth is round"). "How to drive").
Often represented using logic, facts, or Often represented using rules, procedures,
Representation
knowledge bases. or code.
Used for reasoning, query answering, and Used for solving problems, performing
Use Case
knowledge retrieval. tasks, or taking actions.
Knowledge requires action or execution
Retrieval Knowledge can be retrieved directly.
(often in a specific order).
Can be easily updated or added to a Often requires practice or experience to
Flexibility
knowledge base. acquire.

Key Differences in AI Applications

1. Expert Systems:
o Declarative Knowledge is used to represent domain facts and relationships (e.g., a rule
stating "IF the car won't start AND there is no gas, THEN the gas tank is empty").
o Procedural Knowledge is used to define how the system should act based on the rules,
such as steps to diagnose or repair the car.

2. Machine Learning:
o Declarative Knowledge in machine learning can be used to represent the data features
or labels.
o Procedural Knowledge could represent the algorithms used to train models and the
specific steps taken in the process (e.g., training, validation, evaluation).

3. Robotics:
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING
o Declarative Knowledge might include facts about the environment (e.g., "The object is
located at coordinates (x, y)").
o Procedural Knowledge could include instructions for moving a robot to a specific
location or performing an action (e.g., "Move forward by 3 meters").

Which Is Better?
 Declarative Knowledge is typically more useful when you need to store facts, perform logical
reasoning, or answer specific questions.
 Procedural Knowledge is more suitable when you need to automate tasks, perform operations,
or provide step-by-step instructions for problem-solving.

In many cases, both types of knowledge are needed together. For instance, an intelligent
system may store facts (declarative knowledge) and then use procedures (procedural
knowledge) to act upon those facts to solve problems or make decisions.

Example: AI System Using Both Knowledge Types

Imagine a smart home system that adjusts the temperature based on user preferences.

 Declarative Knowledge:
o Facts like "Room temperature is 22°C" or "User prefers the living room at 20°C."
o Rules like "If the room temperature is above 25°C, turn on the air conditioner."

 Procedural Knowledge:
o The procedure for adjusting the air conditioner: "To cool the room, turn on the air
conditioner and set it to 20°C."
o Algorithms for monitoring temperature changes and adjusting the air conditioning
system based on real-time data.

In this example, declarative knowledge defines the facts about the system (current room
temperature, user preferences), while procedural knowledge defines how to take action to
change the room temperature (e.g., adjusting the air conditioning). Both types of
knowledge work together to enable the system to make decisions and take actions.

Logic programming:

Logic programming is a programming paradigm that is based on formal logic. In this

paradigm, programs are written in the form of logical statements, and computation is
performed through logical inference rather than through explicit step-by-step instructions
(as in procedural programming).
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING

In logic programming, the program consists of a set of facts and rules about a problem
domain, and the system uses a query or goal to deduce new facts or find solutions through
logical reasoning.

Key Features of Logic Programming:

1. Declarative Nature: In logic programming, you describe what the solution is rather than how to
find it. You specify the facts and rules, and the system determines how to find the solution.
2. Automatic Inference: Logic programming systems use inference mechanisms to deduce new
facts based on the given facts and rules.
3. Backtracking: If a goal cannot be immediately satisfied, the system backtracks and tries
alternative paths to find a solution.
4. Horn Clauses: Logic programs are typically based on Horn clauses, which are a specific type of
logical formula used in logic programming.

Basic Components of Logic Programming

1. Facts: These are basic assertions or facts about the world. They are the foundation
of the knowledge base in logic programming.
o Example: father(john, mary). (John is the father of Mary)

2. Rules: These are logical statements that define relationships between facts. Rules
specify how one fact leads to another.
o Example: grandfather(X, Y) :- father(X, Z), parent(Z, Y).
 This rule says that "X is a grandfather of Y if X is the father of Z, and Z is a
parent of Y."

3. Queries: These are questions asked to the system, and the system attempts to find
answers based on the facts and rules in the knowledge base.
o Example: ?- father(john, mary).
 This query asks whether John is the father of Mary. The system would check its
knowledge base to see if this fact is true.

4. Inference: The process of deriving new information or answering queries by

applying rules to facts. The system uses forward chaining (starting from known
facts and applying rules) or backward chaining (working backward from a query
and trying to satisfy the conditions of the rule).

Logic Programming Languages

The most well-known and widely used logic programming language is Prolog
(Programming in Logic). Prolog is designed specifically for expressing logic programs and
is based on predicate logic (a type of formal logic).
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING
Prolog Example:

Let's consider a simple knowledge base about family relationships:

Facts:

father(john, mary). % John is the father of Mary

father(john, paul). % John is the father of Paul
mother(susan, mary). % Susan is the mother of Mary
mother(susan, paul). % Susan is the mother of Paul

Rules:

parent(X, Y) :- father(X, Y). % X is a parent of Y if X is the father of Y

parent(X, Y) :- mother(X, Y). % X is a parent of Y if X is the mother of Y

sibling(X, Y) :- father(Z, X), father(Z, Y), X \= Y. % X and Y are siblings if they share the same father

Queries:

1. To find out if John is the father of Mary:

2. ?- father(john, mary).
o The system will respond with true, because it matches the fact in the knowledge base.

3. To find all the parents of Mary:

4. ?- parent(X, mary).
o The system will respond with X = john and X = susan (because both John and Susan are
parents of Mary).

5. To find if Mary and Paul are siblings:

6. ?- sibling(mary, paul).
o The system will respond with true, because they share the same father (John).

Key Concepts in Logic Programming

1. Horn Clauses:
o A Horn clause is a special kind of logical statement that can be written in the form A :-
B1, B2, ..., Bn, which means "A is true if B1, B2, ..., Bn are true." Horn clauses are a
central element of logic programming and provide the foundation for inference.

2. Unification:
o Unification is the process of making two logical expressions identical by finding a
substitution for variables. It's a key concept in logic programming, as it allows the
system to match facts and rules during inference.
o Example: In the query ?- father(john, X)., the system will unify father(john, X) with the
facts in the knowledge base and find X = mary and X = paul.
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING

3. Backtracking:
o Backtracking is a search technique used by logic programming languages like Prolog to
explore all possible solutions to a query. If the current path doesn't lead to a solution,
the system backtracks and tries another possibility.
o Example: If a query has multiple possible solutions, the system will find one, return it,
and then backtrack to explore other potential solutions.

4. Recursion:
o Logic programming supports recursive rules, where a rule refers to itself. This allows
for powerful definitions, such as calculating factorials or traversing hierarchical
structures.
o Example: To define an ancestor relationship:
o ancestor(X, Y) :- parent(X, Y). % X is an ancestor of Y if X is a parent of Y
o ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y). % X is an ancestor of Y if X is a parent of Z,
and Z is an ancestor of Y

Applications of Logic Programming

1. Artificial Intelligence (AI):

o Logic programming is used in AI for tasks like knowledge representation, expert
systems, and natural language processing. For example, Prolog is often used for
symbolic reasoning and solving puzzles or problems that involve constraints.

2. Expert Systems:
o In expert systems, logic programming is used to encode rules and facts about a specific
domain, allowing the system to reason about problems and provide solutions or
recommendations based on the knowledge base.

3. Constraint Solving:
o Logic programming languages can be used to solve constraint satisfaction problems,
where a set of variables must satisfy certain conditions or constraints. For example,
solving Sudoku puzzles or scheduling problems.

4. Natural Language Processing (NLP):

o Logic programming is used in NLP to parse sentences, represent grammatical
structures, and infer meaning from text. Prolog, with its ability to handle recursive
rules, is particularly suited for tasks involving language syntax.

5. Database Querying:
o Logic programming languages, especially Datalog, are used in querying relational
databases where relationships between data can be expressed using logical rules.

Advantages of Logic Programming

1. Declarative Nature: You focus on the what (facts and rules), rather than the how (steps to
perform the computation). This leads to more concise and understandable programs.
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING
2. Automatic Inference: Logic programming languages, like Prolog, automatically deduce new
facts from existing knowledge, allowing for powerful reasoning capabilities.
3. Expressive Power: Logic programming can be highly expressive for tasks involving complex
relationships, reasoning, and problem-solving, especially in domains like AI and knowledge
representation.

Disadvantages of Logic Programming

1. Efficiency: Logic programming languages can sometimes be less efficient than procedural
languages, especially for tasks that require extensive computation or large-scale data processing.
2. Non-Deterministic: The backtracking mechanism in logic programming can lead to non-
deterministic behavior, which may require optimization in complex queries.
3. Limited I/O: Logic programming typically focuses on reasoning and may not be as well-suited
for tasks that require intensive input/output operations or interaction with external systems.

Forward Vs Backward reasoning:

Forward reasoning and backward reasoning are two primary types of inference strategies
used in artificial intelligence (AI), logic programming, and knowledge-based systems. These
two approaches determine how a system derives conclusions from a set of facts and rules.

Here's a breakdown of the difference between forward and backward reasoning:

1. Forward Reasoning (Forward Chaining)

Forward reasoning, or forward chaining, starts with the known facts and applies rules to
infer new facts. It is a data-driven approach that works from specific facts to general
conclusions. The process proceeds forward from facts and rules until a goal is reached.

How It Works:

1. You start with a set of initial facts or conditions.

2. You examine the rules in the knowledge base to find those whose conditions (antecedents) are
satisfied by the known facts.
3. Once a rule's conditions are satisfied, the conclusion (consequent) of that rule becomes a new
fact.
4. This new fact may trigger other rules, and the process continues until no more rules can be
applied or a goal is reached.

Characteristics of Forward Reasoning:

 Data-driven: The reasoning starts with facts and proceeds to conclusions.

 It is often used when you have a large number of facts and you want to propagate information
through the system.
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING
 Complete Search: It tries to exhaustively apply all the rules as long as new facts can be
generated.
 Efficient when there is a lot of data and you want to derive information progressively.

Example:

Suppose we have the following facts and rules in a system about animals:

 Facts:
o Bird(ostrich)
o HasFeathers(ostrich)
o CanFly(sparrow)
 Rules:
o IF Bird(X) AND HasFeathers(X) THEN CanFly(X)
 Forward Reasoning:
o Start with known facts: Bird(ostrich) and HasFeathers(ostrich).
o Apply the rule: Since both conditions are satisfied, we can infer that CanFly(ostrich) is
true.

This process can continue as long as there are new facts to deduce.

Applications of Forward Reasoning:

 Expert systems: Used to infer new knowledge from a set of initial facts.
 Diagnostic systems: For example, in troubleshooting, forward chaining can help generate all
possible conclusions from known symptoms.

2. Backward Reasoning (Backward Chaining)

Backward reasoning, or backward chaining, works in the opposite direction: it starts with
a goal or hypothesis and works backward to find facts that support that goal. It is a goal-
driven approach that tries to prove whether a conclusion is true by searching for
supporting facts.

How It Works:

1. You start with a goal or query (e.g., "Is X true?").

2. You check if the goal can be derived from any rule in the knowledge base by working backward
through the rule.
3. If a rule can be applied, the conditions of the rule (antecedents) must also be true.
4. You then attempt to prove each of the conditions. This may involve additional subgoals, and the
process continues recursively until you either find supporting facts or determine that the goal
cannot be proved.

Characteristics of Backward Reasoning:

 Goal-driven: The reasoning process starts with a specific goal or query and works backward to
find the facts that support the goal.
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING
 Often used when you want to prove or disprove a specific hypothesis.
 Efficient when you have a specific goal or query, as it focuses on finding the necessary facts to
prove that goal.

Example:

Using the same system as before:

 Facts:
o Bird(ostrich)
o HasFeathers(ostrich)
o CanFly(sparrow)

 Rules:
o IF Bird(X) AND HasFeathers(X) THEN CanFly(X)

 Backward Reasoning:
o Query: "Can ostrich fly?"
o The system checks the goal "CanFly(ostrich)" and looks for rules that could prove this.
o It finds the rule IF Bird(X) AND HasFeathers(X) THEN CanFly(X).
o To prove "CanFly(ostrich)", it checks if Bird(ostrich) and HasFeathers(ostrich) are true.
o Since both facts are already known, it concludes that "ostrich can fly" (even though this
conclusion may be incorrect in reality, the reasoning is logically sound based on the
given facts and rules).

Applications of Backward Reasoning:

 Theorem proving: Used in formal logic systems where you want to prove a specific theorem or
statement.
 Expert systems: Particularly useful in situations where you want to check if a hypothesis is true
(such as diagnosis or rule-based decision-making).
 Question answering systems: In systems that answer queries by verifying them against known
facts.

Comparison of Forward and Backward Reasoning

Backward Reasoning (Backward

Aspect Forward Reasoning (Forward Chaining)
Chaining)
Starting Point Starts with known facts Starts with a goal or hypothesis
Direction of
Moves from facts to conclusions Moves from goal to facts
Inference
Goal-driven: Seeks facts that
Approach Data-driven: Uses facts to derive new facts
support a goal
Searches only for facts that support
Search Method Exhaustive search through all possible facts
the goal
Efficient when you have many facts and need to Efficient when you have a specific
Efficiency
generate conclusions goal to prove
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING

Backward Reasoning (Backward

Aspect Forward Reasoning (Forward Chaining)
Chaining)
Used for generating conclusions, diagnosing Used for proving or verifying
Use Case
systems specific hypotheses
Example Expert systems, diagnostic systems (e.g., medical Theorem proving, querying in
Application systems) expert systems

Which One to Use?

 Forward reasoning is suitable when you have a set of facts and want to derive
conclusions or propagate knowledge. It’s ideal for situations where the goal is to
explore the entire knowledge base and generate all possible conclusions based on the
initial facts.
 Backward reasoning is more appropriate when you have a specific goal or
hypothesis and want to focus on proving or disproving that goal. It is often more
efficient in scenarios where only certain facts or conditions need to be examined to
reach a conclusion.

In practice, many systems combine both reasoning methods. For example, an expert system
might use forward chaining to generate possible solutions and then apply backward
chaining to verify and refine these solutions based on specific goals.

Matching-Control knowledge:

Matching-Control Knowledge is a concept used in artificial intelligence (AI) and expert

systems, particularly when discussing reasoning and problem-solving processes. It relates
to the system's ability to match available data or facts with specific rules or knowledge
structures in a controlled manner.

Key Concepts

1. Matching:
o Matching refers to the process of comparing elements (such as facts, conditions, or
goals) in a knowledge base with known information. In the context of rule-based
systems, matching typically involves checking whether the premises (or conditions) of a
rule are satisfied by the current facts in the system.
o The system matches facts with rules to determine which rules can be applied to derive
new conclusions or take actions.

2. Control Knowledge:
o Control knowledge is the knowledge that guides the reasoning process or search
strategy. It defines how a system should navigate through the possible application of
rules, how to prioritize rules, or how to deal with uncertainties or conflicting facts.
o It provides mechanisms to control the order in which rules are applied, how the system
should make decisions, and how to handle search spaces efficiently.
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING
o Control knowledge helps the system decide which facts are relevant and when to apply
certain rules to achieve the desired outcome.

How Matching-Control Knowledge Works Together

In an expert system, matching refers to comparing the conditions of available rules with
the current facts to determine which rules are applicable. Control knowledge provides
guidelines for efficiently performing this matching process. It answers questions like:

 Which rules should be applied first?

 How do you resolve conflicts when multiple rules can apply?
 How do you prioritize certain facts over others?

Thus, matching-control knowledge helps the system decide not just what can be inferred,
but how to make the reasoning process efficient, logical, and goal-oriented.

Example: Rule-Based Expert System

Consider an expert system used to diagnose a mechanical problem in a car:

Rules:

1. Rule 1: IF the car won't start AND the battery is dead THEN the problem is the battery.
2. Rule 2: IF the car won't start AND the battery is fine AND the starter motor makes a clicking
noise THEN the problem is the starter motor.
3. Rule 3: IF the car won't start AND the battery is fine AND the starter motor works THEN the
problem is the ignition switch.

Matching Process:

 The system starts with the fact that "the car won't start."
 It then checks if the battery is dead and compares it against Rule 1. If the battery is dead, it
concludes the problem is with the battery.
 If the battery is not dead, the system checks Rule 2 and looks for a clicking noise from the
starter motor. If the noise is present, the problem is identified as the starter motor.
 If neither of the above conditions holds, the system proceeds to Rule 3 to check if the ignition
switch might be the issue.

Control Knowledge:

 The system’s control knowledge might determine the order in which these rules are checked:
o First, it could prioritize checking if the car won't start and then assess whether the
battery is dead.
o It could handle the search space efficiently, so it doesn't check for the starter motor or
ignition issues unless the battery is confirmed to be functional.
o Control knowledge may also help the system resolve conflicting information, such as
when a rule is applicable but leads to a contradictory conclusion.
 ARTIFICIAL INTELLIGENCE & MACHINE LEARNING

Matching-Control Knowledge in Practice

In AI systems, matching-control knowledge plays a critical role in the efficiency and

effectiveness of reasoning processes. It is especially important in the following areas:

1. Expert Systems:
o Expert systems rely heavily on rules to simulate human expertise in specific domains.
Matching-control knowledge helps guide the system in determining which rules are most
relevant and how to apply them in an intelligent, goal-directed manner.
o For example, in a medical diagnosis system, control knowledge could determine which
symptoms should be considered first based on the severity of the patient's condition.

2. Problem Solving:
o In AI planning and problem-solving, matching-control knowledge can guide search
strategies (such as depth-first or breadth-first search) and help select the most
promising paths or solutions.
o For instance, in a puzzle-solving system, the control knowledge could specify which
moves to try first or how to prune the search tree to avoid unnecessary computations.

3. Machine Learning:
o In more advanced systems, matching-control knowledge might play a role in feature
selection or model tuning. For instance, in a supervised learning system, control
knowledge could guide the system in selecting the most relevant features to match with
the training data.