Unit-4 Knowledge Representation

Introduction
 Knowledge is a theoretical or practical understanding of a subject or a domain.

 Knowledge refers to the fact of knowing something that has been gained through an experience and
learning which makes the agent (AI application like a chatbot) familiar.

 In Artificial Intelligence, a machine will perform a specific action based on a specific condition only if it
has gained an experience from the past.

 Knowledge is also the sum of what is currently known.

 Knowledge is a fact, skills, past experience etc.

 An intelligent agent needs knowledge about the real world for taking decisions and reasoning to act
efficiently.

Types of knowledge
 Classification-based Knowledge: Ability to classify information

 Decision-oriented Knowledge: Choosing the best option.

 Descriptive knowledge: what is known about problem.

 Procedural knowledge: How to do something

 Reasoning knowledge: What conclusion is valid in what situation?

Importance of Knowledge

Knowledge is fundamental to Artificial Intelligence (AI) for several reasons:

 Understanding and Reasoning: Just like humans, AI systems need knowledge to understand the world
around them. This knowledge can be factual (like the capital of France) or conceptual (like the relationship
between speed and distance). With this knowledge, AI systems can reason about situations, draw
inferences, and make logical decisions.
 Learning and Adapting: While some AI systems learn primarily from data, knowledge can play a crucial
role in guiding that learning. A base of knowledge helps AI systems distinguish between relevant and
irrelevant information, generalize from specific examples, and adapt to new situations.
 Problem-Solving and Task Completion: Many AI applications involve solving problems or completing
tasks. Knowledge equips AI systems with the information they need to approach these challenges
effectively. For instance, a medical diagnosis system needs medical knowledge to analyze symptoms and
suggest diagnoses.
 Communication and Interaction: For AI systems to interact meaningfully with humans, they need
knowledge about language, the world, and common sense. This knowledge allows them to understand what
is being said, respond appropriately, and generate human-like text or speech.
 Supporting natural language processing: Knowledge is fundamental for AI to understand and generate
human language. Natural Language Processing (NLP) models, such as those used in chatbots or virtual
assistants, rely on extensive knowledge bases to comprehend context, disambiguate meaning, and provide
relevant responses

By providing a foundation of knowledge, AI systems can act more intelligently and achieve better results in
various applications.

Issues in Knowledge Representation in AI

Knowledge representation in AI involves encoding information about the world into formats that AI systems
can utilize to solve complex tasks. Knowledge representation (KR) is a fundamental challenge in Artificial
Intelligence (AI).

It deals with how to encode and structure the vast amount of knowledge the world has to offer in a way that
machines can understand and reason with. Here are some of the key issues that arise in knowledge
representation for AI:

1. Choosing the Right Representation(techniques): There's no one-size-fits-all solution for representing

knowledge. Different AI tasks and domains require different KR techniques. Common KR techniques include
logic-based representations (e.g., propositions, rules), semantic networks (conceptual relationships between
entities), and frames (structured knowledge about objects and situations).

2. Handling Uncertainty and Incompleteness: The real world is messy. Our knowledge is often incomplete,
and things aren't always black and white. KR systems need to deal with:
o Uncertainty: How to represent and reason with knowledge that might be imprecise or probabilistic (e.g.,
"It will probably rain tomorrow").
o Inconsistency: Conflicting information can exist. The system needs to identify and handle inconsistencies
or provide methods to resolve them.
Techniques like fuzzy logic and probabilistic reasoning can help represent and reason with uncertainty.

3. Integrating Knowledge from Multiple Sources:

 AI systems might need to access and combine knowledge from various sources, each with its own structure
and format. Knowledge integration involves:
o Semantic Alignment: Ensuring concepts and relationships from different sources have consistent meanings.

4. Reasoning with Inconsistent Knowledge: Developing methods to reason and draw conclusions even if
the knowledge sources disagree.

5. Expressiveness: More expressive systems often lead to computational complexity, making reasoning slower
and more resource-intensive.

6. Ethical and Bias Issues:

 Bias in Representation: Knowledge representations can inadvertently(accidentaly) encode biases present
in the training data or the assumptions of the developers.
 Ethical Considerations: The way knowledge is represented and used by AI systems can have significant
ethical implications, requiring careful consideration

Researchers are constantly developing new techniques and approaches to address these issues. The goal is to
create knowledge representation systems that are expressive, efficient, and adaptable to handle the
complexities of the real world.

Knowledge Representation Systems

 Knowledge representation is a fundamental concept in artificial intelligence (AI) that involves creating
models and structures to represent information and knowledge in a way that intelligent systems can use.

 It is responsible for representing information about the real world so that a computer can understand and
can utilize this knowledge to solve the complex real world problems such as diagnosis a medical condition
or communicating with humans in natural language.

 Knowledge representation in AI involves encoding information about the world into formats that AI
systems can utilize to solve complex tasks.

 Knowledge representation is not just storing data into some database, but it also enables an intelligent
machine to learn from that knowledge and past experiences so that it can behave intelligently like a human.

 Objects, events, performance, meta-knowledge, facts, and knowledge-base are the different kinds of
knowledge.

Properties for knowledge Representation System

The following properties should be possessed by a knowledge representation system.

 Representational Accuracy: The KRS should be able to represent all the different kinds of knowledge
required for the task at hand.

 Inferential Adequacy: The KRS should allow the system to derive new knowledge based on the existing
knowledge.

 Comprehensiveness: The KRS should be able to represent a broad range of knowledge, not limited to a
specific domain.

 Computability: The knowledge representation needs to be structured in a way that the system can process
and manipulate it using its computational abilities.

 Accessibility: The knowledge base should be easy for humans to understand and interact with, allowing for
easier maintenance and knowledge editing.

 Relevance: The KRS should focus on storing knowledge that is relevant to the specific task or domain the
system is designed for.
 Conciseness: The knowledge representation should be efficient in its use of storage space, avoiding
redundancy and unnecessary complexity.

By considering these properties, developers can choose or design a knowledge representation system that best
suits the needs of their specific AI application.

Types of Knowledge Representation Systems

There are several fundamental knowledge representation techniques used in Artificial Intelligence (AI). Each
technique has its strengths and weaknesses, and the choice of which technique to use depends on the specific
problem being addressed. Here's a breakdown of the common ones:

1) Logical Representation:

 Knowledge is represented in a formal language based on logic, similar to mathematical formulas.

 This allows for clear and unambiguous representation, enabling powerful reasoning capabilities.

 However, logical representations can be complex and difficult to understand for humans, and knowledge
acquisition can be challenging.

 There are two types of logical representation: Propositional Logic and First-order Logic.

o Propositional Logic:- Propositional logic is the simplest formal logic for the representation of the
knowledge in terms of propositions. Propositional logic is also called Boolean logic as it works on 0 and 1
or true and false.

o First-order logic (FOL):- It also known as first-order predicate calculus (FOPC) or first-order logic with
identity, is an extension of propositional logic that allows for the representation of more complex
relationships between objects. It uses quantifiers for showing the relationship between propositions.

2) Semantic Networks

 Semantic networks are a type of graphical model that shows the relationships between concepts, ideas, and
objects in a way that is easy for humans to understand.

 Semantic networks are used to represent both simple and complex knowledge structures.

 Knowledge is structured as a network of nodes and links between them.

 Nodes represent concepts or entities, and links represent relationships between them.

 Semantic networks are good for representing relationships and hierarchies between concepts, but they can
become unwieldy for large knowledge bases.

 The syntax of a semantic network consists of nodes and links, and the semantics involve defining the
meaning of each node and link.
 One of the main advantages of semantic networks is that they can be easily visualized, making them more
easy to understand than logical representations.

 However, there are some drawbacks associated with this representation method. For instance, semantic
networks can be computationally expensive at runtime, as traversing the entire network tree may be
necessary to answer certain questions.

 Example: The following are a few statements that must be represented with nodes and arcs:

3) Frame Representation:

 Frame representation is a technique for organizing knowledge in a hierarchical structure.

 Knowledge is organized around frames, which are data structures containing slots for attributes and their
values.

 Frames can represent stereotypical objects, situations, or events.

 In artificial intelligence, frames serve as a data structure that divides knowledge into substructures by
representing typical situations.

 This approach is good for representing objects with similar properties and allows for inheritance of
attributes between related frames. However, frames can be less efficient for representing complex
relationships.
4) Production Rules:

 Knowledge is encoded as a set of production rules, which are "if-then" statements.

 The antecedent (if) part of the rule specifies a condition, and the consequent (then) part specifies an action.

 The production rules system is composed of three key components:

o The set of production rules

o The working memory

o The recognize-act-cycle

 Production rules are good for representing procedural knowledge and reasoning steps, but they can be less
efficient for representing complex factual knowledge.

 One advantage of this system is that production rules can be expressed in natural language, which makes
them easier to understand and modify.

 However, there are also some drawbacks to the production rules system. They do not possess any learning
capabilities and cannot store the result of a problem for future use.
Example:

o IF (at bus stop AND bus arrives) THEN action (get into the bus)
o IF (on bus AND unpaid) THEN action (pay charges).
o IF (bus arrives at destination) THEN action (get down from the bus).

Propositional Logic

 Propositional logic is the simplest formal logic for the representation of the knowledge in terms of
propositions.

 It provides a formal framework for representing and manipulating statements (propositions) to perform
automated reasoning tasks.

 Propositional logic is also called Boolean logic as it works on 0 and 1 or true and false.

 Propositions logic can be true or false, but not both at the same time.

 The propositions and connectives are the basic elements of the propositional logic. Connectives can be said
as a logical operator which connects two sentences(propositions).

 It provides a formal system for representing these propositions and the relationships between them using
logical operators like AND, OR, and NOT.

 Propositional logic consists of an object, relations, and logical connectives.

Important of propositional logic in AI?

 Knowledge Representation: Propositional logic allows us to express facts and rules in a clear way. We
can represent simple statements about the world as propositions (e.g., "It is raining" or "The car is red"). By
combining these propositions with logical operators, we can build more complex knowledge structures.

 Reasoning: Once knowledge is represented, propositional logic allows AI systems to reason and draw
conclusions based on that knowledge. We can use inference rules to derive new propositions from existing
ones. This enables AI systems to make decisions and solve problems without needing everything explicitly
programmed.

 Expert Systems: These systems use knowledge bases built with propositional logic to diagnose problems,
recommend solutions, and answer questions in specific domains.

 Natural Language Processing (NLP): Propositional logic can help understand the logical structure of
sentences and perform tasks like question answering or sentiment analysis.

 Game Playing: AI players in games like chess or checkers can use propositional logic to evaluate the
game state and make optimal moves based on the rules.

Syntax of propositional logic:

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

 Atomic Propositions

 Compound 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.

Example :-

a) 2+2 is 4, it is an atomic proposition as it is a true fact.

b) "The Sun is cold" is also a proposition as it is a false fact.

Compound proposition: A combination of simple sentences connected by logical connectors is called

Compound proposition.

Example :-
a) today is Friday and people visit Temple today.

b) It's raining, and the match is called off.

Logical Connectives uses in propositional logic

 Logical connectives are used to connect two simpler propositions or representing a sentence logically.
 There are mainly five connectives, which are given as follows:

1. Negation :- A sentence such as ¬ P is called negation of P. The symbol uses in negation is “¬” in word
“Not”.

Truth table of Negation

P ¬P

1 (true) 0 (false)

0 (false) 1 (true)

2. Conjunction (Conjunctive Normal Form): A sentence which has ∧ connective such as, P ∧ Q is called a
conjunction. The symbol uses in Conjunction is “∧” in word “AND”.
Example: Rohan is intelligent and hardworking.

It can be written as,

P= Rohan is intelligent,
Q= Rohan is hardworking. → P∧ Q.

Truth table of Conjunction:-

P Q P^Q

1 (true) 1 (true) 1 (true)

1 (true) 0 (false) 0 (false)

0 (false) 1 (true) 0 (false)

0 (false) 0 (false) 0 (false)

3. Disjunction (Disjunctive Normal Form):

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

 The symbol uses in Disjunction is “∨” in word “OR”.

Example:

"Ritika is a doctor or Engineer",

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

Truth table of Disjunction: -

P Q PvQ
1 (true) 1 (true) 1 (true)

1 (true) 0 (false) 1 (true)

0 (false) 1 (true) 1 (true)

0 (false) 0 (false) 0 (false)

4. Implication (if-then): 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

Truth table of Implication: -

P Q P→Q

1 (true) 1 (true) 1 (true)

1 (true) 0 (false) 0 (false)

0 (false) 1 (true) 1 (true)

0 (false) 0 (false) 1 (true)

5. Bi-conditional (if and only if): A sentence such as P⇔ Q is a Bi-conditional 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.

P Q P⇔Q

1 (true) 1 (true) 1 (true)

1 (true) 0 (false) 0 (false)

0 (false) 1 (true) 0 (false)

0 (false) 0 (false) 1 (true)

Q ) X = It is cold , Y= It is Sunny and Z = It is Breezy solve all the below questions using logical
connectives.

1) It is not cold
Ans :- ¬ X

2) It is cold and it is Breezy.

Ans :- X ^ Z

3) It is cold or It is Breezy.

Ans :- X V Z

4) If it is Breezy and cold then it is not sunny.

Ans :- ( Z ^ X )  ¬ Y

5) If it is breezy then it is cold.

Ans :- Z  X

6) It will be cold if and only if it is Breezy.

Ans :- X ⇔ Z

Q ] You can access the internet from SPA College if and only if you are BIM Student or you are not
freshman .

Ans:-

Q] If it is daytime and it is not raining then it is warm.

Ans:-

Q] It is sunny and it is not raining.

Ans:-

Q] You can log in if and only if you have a valid password.

Ans:-

Q ) Prove [(A→B)∧A]→B is a tautology. (every value are true)

Ans :- The truth table is as follows

A B A→B (A→B) ∧ A [(A→B)∧A]→B

True True True True True

True False False False True

False True True False True

False False True False True

As we can see every value of [( A  B ) ∧ A]  B is "True", it is a tautology.

Q ): Prove (A∨B)∧(¬A) a contingency (every value are true or false)

Ans :- The truth table is as follows

A B A∨B ¬A (A∨B) ∧ (¬A)

True True True False False

True False True False False

False True True True True

False False False True False

As we can see every value of (A ∨ B) ∧ (¬A) has both ―True and ―False, it is a contingency.

Q ) Prove (A∨B)∧[(¬A)∧(¬B)] is a contradiction. (every values are false)

Ans :- The truth table is as follows :

A B AvB ¬A ¬B ( ¬A ) ∧ ( ¬B ) (A∨B) ∧ [ (¬A) ∧ (¬B) ]

True True True False False False False

True False True False True False False

False True True True False False False

False False False True True True False

As we can see every value of (A ∨ B) ∧ [(¬A) ∧ (¬B)] is ―False‖, it is a contradiction.

Inference rules uses propositional logic

 Inference rules are the templates for generating valid arguments.

 Inference rules are applied to derive proofs in artificial intelligence, and the proof is a sequence of the
conclusion that leads to the desired goal.

 Following are some terminologies related to inference rules:

 Implication: It is one of the logical connectives which can be represented as P → Q. It is a Boolean

expression.

 Converse: The converse of implication, which means the right-hand side proposition goes to the left-hand
side and vice-versa. It can be written as Q → P.

 Contrapositive: The negation of converse is termed as contrapositive, and it can be represented as ¬ Q →

¬ P.

 Inverse: The negation of implication is called inverse. It can be represented as ¬ P → ¬ Q.

From the terminologies related to inference rules are equivalent to each other, which we can prove using truth
table:

Or

Q} Prove that P → Q is equivalent to ¬ Q → ¬ P, and Q→ P is equivalent to ¬ P → ¬ Q. using inference

rules.

Answer:- Let true = 1 and false = 0;

P Q P→Q Q→P ¬Q→¬P ¬P→¬Q

1 (T) 1 (T) 1 (T) 1 (T) 1 (T) 1 (T)

1 (T) 0 (F) 0 (F) 1 (T) 0 (F) 1 (T)

0 (F) 1 (T) 1 (T) 0 (F) 1 (T) 0 (F)

0 (F) 0 (F) 1 (T) 1 (T) 1 (T) 1 (T)

Hence from the above truth table, we can prove that P → Q is equivalent to ¬ Q → ¬ P, and Q→ P is
equivalent to ¬ P → ¬ Q.

Rule Based Systems (Production System)

 The production System is a model of computation that has proved particularly important in AI, both for
implementing search algorithms and for modeling human problem solving.

 Production system provide a structure for describing and performing the search process in AI program.

 A production system is a set of rule, each rule consists L.H.S (Situation) and R.H.S (Action). These rules,
termed productions, are a basic representation found useful in automated planning, expert systems and
action selection.

Situation / Condition Action / Operation

Rule (Production System)

 A production system provides pattern-directed control of a problem solving process and consists of:–

 Global Database or knowledge base

 Set of Production Rules

 A Control System (control strategy and rule applier)

Components of Production System

Global Database: The global database serves as the system’s memory, storing facts, data, and knowledge
relevant to its operation. It is a repository that production rules can access to make informed decisions and
draw conclusions.

Production Rules: Production rules form the core logic of the system. They are a set of guidelines that the
system follows while making decisions. These regulations outline the system’s reaction to various inputs and
circumstances.

Control System: The control system manages the execution of production rules. It determines the sequence in
which rules are applied, ensuring efficient processing and optimizing the system’s performance.

Example of Production System

 Problem: Sorting a string composed of letters a, b & c.

 Short Term Memory: “cbaca”

 Production Set:

1. ba → ab

2. ca → ac

3. cb → bc

Inference engine:
 The inference engine is the component of the intelligent system in artificial intelligence, which applies
logical rules to the knowledge base.
 It acquires and manipulates knowledge from the knowledge base(database) to arrive at particular solution.
 It is like a search engine.
 It is rule-based expert system.
 There are two principal ways in which rules are executed.

1) Forward chaining (what can happen next?)

 Forward chaining is also known as a forward deduction or forward reasoning method when using an
inference engine.

 Forward chaining starts from the start state(Known facts or data) and proceeds towards the goal state
(conclusion).

 It is a down-up approach, as it moves from bottom to top.

 It is a process of making a conclusion based on known facts or data, by starting from the initial state and
reaches the goal state.

 Forward chaining can be used in planning, monitoring, controlling, and interpreting applications.

 Example chess game.

Fig: Forward chaining

Examples of forward chaining:

 A simple example of forward chaining can be explained in the following sequence.

A, A->B, B

 A is the starting point. A->B represents a fact. This fact is used to achieve a decision B.

A practical example will go as follows;

 Tom is running (A)

 If a person is running, he will sweat (A->B)

 Therefore, Tom is sweating. (B)

2) Backward Chaining (why this happen?)

 Backward-chaining is also known as a backward deduction or backward reasoning method when using an
inference engine.

 A backward chaining algorithm is a form of reasoning, which starts with the goal and works backward,
chaining through rules to find known facts that support the goal.

 It is known as a top-down approach or goal driven approach.

 In backward chaining, the goal is broken into sub-goal or sub-goals to prove the facts true.

 The modus ponens inference rule is used as the basis for the backward chaining process.

 A backward chaining algorithm is employed in inference engines, game theories, and complex database
systems.

Fig: Backward Chaining

Example of backward chaining

Backward chaining can be explained in the following sequence:

 B, A->B, A

 B is the goal or endpoint, that is used as the starting point for backward tracking. A is the initial state.
A->B is a fact that must be asserted to arrive at the endpoint B.

A practical example of backward chaining will go as follows:

 Tom is sweating (B).

 If a person is running, he will sweat (A->B).

 Tom is running (A).

First Order Predicate Logic (FOPL)/ Predicate Logic

 First-order predicate logic is another way of knowledge representation in artificial intelligence. It is an
extension to propositional logic.
 First order Predicate logic, also known as predicate logic, is a powerful tool used in AI for knowledge
representation and reasoning.
 It includes a collection of rules and symbols that enable us to build complex statements from simpler ones.

 First-order logic is a powerful language that develops information about the objects in an easier way and
can also express the relationship between those objects.

 First-order predicate logic also assumes the following things in the world:

 Objects: Students, lectures, companies, cars,

 Properties: blue, oval, even, large,

 Relations: Brother, bigger-than, outside, part-of, has-color, occurs-after, owns, visits,

First-order logic in Artificial Intelligence comprises two main components, which are as follows.

1) Syntax

2) Semantics

1) Syntax of First-Order logic:

 The syntax of FOL decides which collection of symbols is a logical expression.

 The basic syntactic elements of FOL are symbols. We use symbols to write statements in shorthand
notation.

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

Variables x, y, z, a, b,....

Predicates <, >, brother, sister, father...

Equality ==

Function Sqrt, LessThan, GreaterThan...

Quantifier ∀, ∃

Connectives ∧, ∨, ¬, ⇒, ⇔

2) Semantics
 Semantics refers to the techniques that we use to evaluate an expression of First Order Logic in AI.

 In AI, semantics of First-Order Logic (FOL) play a vital role in enabling machines to reason and
understand the meaning of statements within a specific context.
 It provides a way to assign meanings to the symbols and structures used in first-order logic.

 Semantics refers to the techniques that we use to evaluate an expression of First Order Logic in AI.

Example: Cat is white = Cat(x)white(x)

Quantifiers in First-order logic:

 Quantifiers allow us to determine or identify the range and scope of the variable in a logical expression.

 There are two types of quantifiers:

1) Universal quantifier: for all, everyone, everything.

2) Existential quantifier: for some, at least one.

1) Universal quantifier (all, everything, everyone)-(to identify range)

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

 The Universal quantifier is represented by a symbol ∀.

 It uses implication “ → “ symbol for statement representation.

 Example:

All man drink coffee.

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

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

2) Existential Quantifier: (some, atleast one)

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

 If x is a variable, then existential quantifier will be ∃x or ∃(x).

 It uses Conjunction “ ^ “ symbol for statement representation.

 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.
Note:-

 The main connective for universal quantifier ∀ is implication →.

 The main connective for existential quantifier ∃ is and ∧.

Q] All cats like meat. => ∀x:cats(x)  like ( x , meat ).

Q] Some girls hate dancing => ∃x:girls(x) ∧ hate ( x , dancing ).

Q] All boys love football => ∀x:boys(x)  like ( x , football ).

Q] Every person who buys a share is smart. => ∀x∀y:person(x) ∧ share(y) ∧ buys(x , y) smart(x) .

Q] No person buys expensive share => ∀x∀y:person(x) ∧ share(y) ∧ expensive(y)  ¬buys( x , y)