CHAPTER 4: Knowledge and Reasoning

4.1 Logical Agents

Logical agents apply inference to a knowledge base to derive new information and make decisions.
Logical Agents are Computational systems that “think” rationally. Logic (Knowledge-Based) agents combine general
knowledge with current percepts to infer hidden aspects of current state prior to selecting actions.
The central component of a knowledge-based agent is its knowledge base, or KB. A knowledge base is a set
of sentences. Each sentence is expressed in a language called a knowledge representation language and represents some
assertion about the world. There must be a way to add new sentences to the knowledge base and a way to query what is
known. The standard names for these operations are TELL and ASK, respectively.

Figure 4.1
Both operations may involve inference—that is, deriving new sentences from old. Inference must obey the requirement
that when one ASKs a question of the knowledge base, the answer should follow from what has been told (or TELLed)
to the knowledge base previously.

function KB-AGENT(percept ) returns an action

persistent: KB, a knowledge Base
t , a counter, initially 0, indicating time
TELL(KB,MAKE_PERCEPT_SENTENCE(percept , t ))
action ←ASK(KB,MAKE_ACTION_QUERY(t ))
TELL(KB,MAKE_ACTION_SENTENCE(action, t ))
t ←t + 1
return action

Figure 4.2 A generic knowledge-based agent. Given a percept, the agent adds the percept to its knowledge base, asks
the knowledge base for the best action, and tells the knowledge base that it has in fact taken that action.

Like all our agents, it takes a percept as input and returns an action. The agent maintains a knowledge
base, KB, which may initially contain some background knowledge. Each time the agent program is called, it does
three things.

First, it TELLs the knowledge base what it perceives.

Second, it ASKs the knowledge base what action it should perform. In the process of answering this query, extensive
reasoning may be done about the current state of the world, about the outcomes of possible action sequences, and so
on.

Third, the agent program TELLs the knowledge base which action was chosen, and the agent executes the action.

MAKE-PERCEPT-SENTENCE:
It constructs a sentence asserting that the agent perceived the given percept at the given time.
MAKE-ACTION-QUERY:
It constructs a sentence that asks what action should be done at the current time.
MAKE-ACTION-SENTENCE:
It constructs a sentence asserting that the chosen action was executed.

28
We can also provide a knowledge-based agent with mechanisms that allow it to learn for itself. These mechanisms
create general knowledge about the environment from a series of percepts. A learning agent can be fully autonomous.

The agent must be able to do:

 Represent states, actions, etc.
 Incorporate new percepts
 Update internal representations of the world
 Deduce hidden properties of the world
 Deduce appropriate actions

The wumpus world

The wumpus world is a cave consisting of rooms connected by passageways. Lurking somewhere in the
cave is the terrible wumpus, a beast that eats anyone who enters its room. The wumpus can be shot by an agent, but the
agent has only one arrow. Some rooms contain bottomless pits that will trap anyone who wanders into these rooms
(except for the wumpus, which is too big to fall in). The only mitigating feature of this bleak environment is the
possibility of finding a heap of gold. Although the wumpus world is rather tamed by modern computer game
standards, it illustrates some important points about intelligence. A sample wumpus world is shown in Figure 4.3.

Figure 4.3 A sample wumpus world

Wumpus World PEAS Description

• Performance measure:
+1000 for climbing out of the cave with the gold,
–1000 for falling into a pit or being eaten by the wumpus,
–1 for each action taken and
–10 for using up the arrow.
The game ends either when the agent dies or when the agent climbs out of the cave.

• Environment:
A 4×4 grid of square rooms
The agent always starts in the square labeled [1,1], facing to the right.
 Squares adjacent to wumpus are smelly (stench)
 Squares adjacent to pit are breezy
 Glitter iff gold is in the same square
 Shooting kills wumpus if agent is facing it

29
  Shooting uses up the only one arrow
 Grabbing picks up gold if in same square
 Releasing drops the gold in same square
• Actuators:
The agent can move Forward, TurnLeft by 90◦, or TurnRight by 90◦.
The action Grab can be used to pick up the gold if it is in the same square as the agent.
The action Shoot can be used to fire an arrow in a straight line in the direction the agent is facing. The arrow continues
until it either hits (and hence kills) the wumpus or hits a wall. The agent has only one arrow, so only the
first
Shoot action has any effect.
Finally, the action Climb can be used to climb out of the cave, but only from square [1,1].

• Sensors:
The agent has five sensors, each of which gives a single bit of information:
1. In the square containing the wumpus and in the directly (not diagonally) adjacent squares,
the agent will perceive a Stench.
2. In the squares directly adjacent to a pit, the agent will perceive a Breeze.
3. In the square where the gold is, the agent will perceive a Glitter.
4. When an agent walks into a wall, it will perceive a Bump.
5. When the wumpus is killed, it emits a woeful Scream that can be perceived anywhere in the cave.
The percepts will be given to the agent program in the form of a list of five symbols;

[Stench, Breeze, Glitter, Bump, Scream ]

For example, if there is a stench and a breeze, but no glitter, bump, or scream, the agent program will get the percepts
[Stench, Breeze, None, None, None].

Let us watch a knowledge-based wumpus agent exploring the environment shown in Figure 4.3(a,b,c,d,e).

[1,1] KB initially contains the rules of the environment.

First percept is [none, none,none,none,none], move to safe cell e.g. [2,1]

[2,1] Breeze which indicates that there is a pit in [2,2] or [3,1], return to [1,1] to try next safe cell

30
 (c)

[1,2] Stench in cell which means that wumpus is in [1,3] or [2,2] but not in [1,1]
YET … not in [2,2] or stench would have been detected in [2,1]
THUS … wumpus is in [1,3]
THUS [2,2] is safe because of lack of breeze in [1,2]
THUS pit in [3,1]
move to next safe cell [2,2]

(d) (e)
[2,2] Move to [2,3]
[2,3] Detect glitter, smell, breeze
Pick up gold
THUS pit in [3,3] or [2,4]

4.2 Propositional Logic

Propositional logic is a way of representing knowledge. In Propositional logic every expression is a sentence, which
represents a fact. It assumes the world contains facts.
In logic and mathematics, a propositional calculus or logic is a formal system in which formulae representing
propositions can be formed by combining atomic propositions using logical connectives

31
 Symbols in propositional logic are the logical constants True and False. Sentences considered in propositional logic are
not arbitrary sentences but are the ones that are either true or false, but not both. This kind of sentences is called
propositions.

Syntax
The syntax of propositional logic defines the allowable sentences.
The atomic sentences consist of a single proposition symbol.
Each such symbol stands for a proposition that can be true or false.
We use symbols that start with an uppercase letter and may contain other letters or subscripts, for example:
P, Q, R, W1,3 and North.
The names are arbitrary but are often chosen to have some mnemonic value—we use W1,3 to stand for the
proposition that the wumpus is in [1,3]. There are two proposition symbols with fixed meanings: True is the
always-true proposition and False is the always-false proposition.
Example
Some facts in propositional logic:
It is raining. - RAINING
It is sunny - SUNNY
It is windy - WINDY

Complex sentences are constructed from simpler sentences, using parentheses and logical connectives.
Example
If it is raining, then it is not sunny - RAINING ->      SUNNY

Elements of propositional logic

Simple sentences which are true or false are basic propositions.
Larger and more complex sentences are constructed from basic propositions by combining them
with connectives.
Thus propositions and connectives are the basic elements of propositional logic.
Though there are many connectives, we are going to use the following five basic connectives here:
, , , , `
The symbols of propositional logic are:
1. The logical constants True and False
2. The propositional symbol such as P or Q
3. The 5 logical connectives , , , , 
4. The parentheses ( , )

All sentences are made by putting these symbols together using the following rules:
i. The logical constants True and False are sentences themselves.
ii. A propositional symbol such as P or Q is a sentence itself.
iii. Wrapping parentheses around a sentence yields a sentence by itself, eg. (P Q) 
iv.  A sentence can be formed by combining simpler sentences with one of the 5 logical connectives.
 
  The 5 logical connectives according to their hierarchy are:  
NOT ; only connective that operates on a single sentence
; a sentence such as P is called as negation of P
// the following connectives combine two sentences into one sentence.
AND ; conjunction
; a sentence whose main connective is , such as P (Q R)
;its parts are called conjuncts P and Q R

OR ; disjunction
; a sentence using , such as P (Q R)
;its parts are called disjuncts P and Q R
; P ∨ Q is true iff either P or Q is true

32
 IMPLIES ; conditional
; a sentence using , such a s (P Q) R is called an implication
; its premise or antecedent is (P Q), and its conclusion or consequent is R
; Implications are also known as rules or if-then- statements
; P ⇒ Q is true unless P is true and Q is false

 EQUIVALENT ; biconditional
; the sentence (P Q) (Q P) is an equivalence
;IF_AND_ONLY_IF
; P ⇔ Q is true iff P and Q are both true and both false

Figure 4.4 gives a formal grammar of propositional logic

Sentence → AtomicSentence | ComplexSentence
AtomicSentence → True | False | Symbol
Symbol →P|Q|R|...
ComplexSentence → ( Sentence ) | [ Sentence ]
| ￢Sentence
| Sentence ∧ Sentence
| Sentence ∨ Sentence
| Sentence ⇒ Sentence
| Sentence ⇔ Sentence

OPERATOR PRECEDENCE : ￢, ∧, ∨,⇒,⇔

Figure 4.4 A BNF (Backus–Naur Form) grammar of sentences in propositional logic,

along with operator precedences, from highest to lowest.

The order of preference in propositional logic is , , , , and  .

Hence the sentence,
P Q R S
is equivalent to the sentence
(( P) (Q R)) S
Semantics
The semantics defines the rules for determining the truth of a sentence with respect to a particular model. In
propositional logic, a model simply fixes the truth value—true or false—for every proposition symbol.

Semantics of propositional logic is the interpretation of proposition symbols and constants, and specifying the meaning
of logical connectives.
For complex sentences, we have five rules, which hold for any sub sentences P and Q in any model m
(here “iff” means “if and only if”):
• ￢P is true iff P is false in m.
• P ∧ Q is true iff both P and Q are true in m.
• P ∨ Q is true iff either P or Q is true in m.
• P ⇒ Q is true unless P is true and Q is false in m.
• P ⇔ Q is true iff P and Q are both true and both false in m.
P Q P PQ‘If P then PQ‘IF_AND_ONLY_IF’
Q’
False False True False False True True
False True True False True True False
True False False False True False False
True True False True True True True
Truth table for the 5 logical connectives
What is inference?

33
Inference is the process deriving new sentences from old ones.

Validity and Inference

If the sentence is True in every row of the truth table, then the sentence is valid. This can be done by building a
truth table for the sentence
PremisesConclusion
and checking all the rows. If every row is True, then the conclusion is entailed by the premises. This means that the
fact represented by the conclusion follows from the state of affairs represented by the premises.
P H (P H)H ((P H)H)P
False False False False True
False True True False True
True False True True True
True True True True True

Table: Validity of a complex sentence

Rules of Inference for propositional logic

There are standard patterns of inference that can be applied to derive chains of conclusions that lead to the desired
goal. These patterns of inference are called inference rules.
The notation
a╞ b
says that  can be derived from  by inference. An alternative notation is
a
b
This is known as entailment where a sentence follows logically from another sentence.

If there are several sentences in either the premise or in the conclusion, they are separated by commas.
A list of 7 commonly used inference rules for propositional logic are given below.

i) Modus Ponens or Implication-Elimination:

The best-known inference rule is called Modus Ponens and is written as follows:
aÞ b, a
b
The notation means that the sentence  can be inferred from  .
For example, if ( WumpusAhead WumpusAlive) Shoot and ( WumpusAhead WumpusAlive) are given, then
Shoot can be inferred.

ii) And-Elimination: From a conjunction, we can infer any of the conjuncts.

a 1 Ù a 2 Ù a 3 Ù . . .Ùa n
ai
For example, from ( WumpusAhead WumpusAlive), WumpusAlive can be inferred.

iii) And-Introduction: From a list of sentences, their conjunction can be inferred.

a1 , a2 , a3 , . . .,an
. a 1 Ù a 2 Ù a3 Ù . . .Ùan

34
iv) Or-Introduction: From a sentence, we can infer disjunction with anything else at all.
ai
a 1 Ú a 2 Ú a 3 Ú . . .Ú a n

v) Double Negation Elimination: From a doubly negated sentence, we can infer a positive sentence.
Ø Øa
a
vi) Unit Resolution: From a disjunction, if one of the disjuncts is FALSE then we can infer the other one is TRUE.

a Ú b ,Øb
a
vii) Resolution: This is the most difficult one. Because ɣ cannot be both TRUE and FALSE, one of the other disjuncts
must be TRUE in one of the premises. Or equivalently, implication is transitive.

a Ú b,Ø bÚ ɣ Ø a Þ b , bÞ ɣ
aÚɣ or ØaÞ ɣ

4.3 Predicate (First-Order) Logic

FOL makes a stronger set of ontological commitments. Ontology =(computing) a rigorous(Rigidly accurate; allowing
no deviation from a standard) and exhaustive(Performed comprehensively and completely`) organization of some
knowledge domain that is usually hierarchical and contains all the relevant entities and their relations

Definition of First order Logic

Whereas propositional logic assumes the world contains facts, First-order logic (like natural language) assumes the
world consists of Objects, that is, things with individual identities and properties that distinguish from other objects.
Objects: people, houses, numbers, colors, baseball games, wars,
Properties: red, round, bogus, prime, multistoried, ……
Among these objects various relations hold. Some of these relations are functions- relations in which there is only one
‘value’ for a given ‘input.
Relations: has color, brother of, bigger than, part of, comes between, occurred after…
Functions: father of, best friend, one more than, plus, …

Examples:
i) “one plus two equals three”
Objects: one, two, three, one plus two,
Property: --------
Relation: equals
Function: plus
ii) “Squares neighboring the wumpus are smelly”
Objects: Squares, wumpus
Property: smelly
Relation: neighboring
Function: --------
iii) “Evil king John ruled England in 1200”
Objects: John, England, 1200
Properties: Evil, king
Relation: ruled
Function: ______

Syntactic elements of First Order Logic

First-order logic has sentences, but it also has terms, which represent objects. Constant symbols, Predicate symbols,
and Function symbols are used to build terms and quantifiers and predicate symbols are used to build sentences.

The basic syntactic elements of first-order logic are the symbols that stand for objects, relations, and functions.

35
The symbols come in three kinds:
a) Constant symbols, which stand for objects;
b) Predicate symbols, which stand for relations; and
c) Function symbols, which stand for functions.
We adopt the convention that these symbols will begin with uppercase letters.
Example:
Constant symbols: A, B, Richard, and John;
Predicate symbols: Brother, OnHead, Person, King, and Crown;
Function symbols: FatherOf, LeftLegOf

Terms: Term is a logical expression that refers to an object. Constant symbols are therefore terms.
A term with no variables is called a ground term.
Quantifiers
Quantifiers are needed to express properties of entire collections of objects, instead of enumerating the objects by
name.

FOL contains two standard quantifiers called

a) Universal (" ) and
b) Existential ($ )

a) Universal quantification
“Spot is a cat” is represented by Cat (Spot) and
“Spot is a mammal” is represented by Mammal (Spot).
In English, what we want to say is that for any object x, if x is a cat then x is a mammal.
First –Order Logic let us do this as follows:
"x Cat(x) Mammal(x)

Thus in general a sentence is represented as

("x) P(x)
where
" is pronounced as “ For all ..”,
the symbol x is called a variable (lower case letters) and First letter of all predicate, constant &
function symbols are capitalized.
P is logical expression says that P is true for all objects x in the Universe.
Hence the symbol " is called Universal quantifier.
This means that P holds for all values of x in the domain associated with that variable.

E.g.1
Rules such as "All kings are persons,'' is written in first-order logic as
"x King(x) => Person(x)
Thus, the sentence says, "For all x, if x is a king, then x is a person."

E.g.2
("x) dolphin(x) => mammal(x)

b) Existential quantification

($ x)P(x) means that P holds for some value of x in the domain associated with that variable.
E.g., ($ x) mammal(x)  lays-eggs(x)

Universal quantification makes statements about every object. Similarly, we can make a statement about some object
in the Universe without naming it, by using an Existential quantifier.
For example,
”Spot has a sister who is a cat” can be written as
($ x) Sister(x, Spot)  Cat(x)

36
Thus in general a sentence is represented as
($x) P(x)
where
$x is pronounced “There exists an x such that ..” or “ For some x ..”,
the symbol x is called a variable (lower case letters) and all predicate, constant & function
symbols are capitalized.
P is logical expression says that ($x) P is true if P is true for some object x in the Universe.
Hence the symbol $ is called Existential quantifier.

c) Nested quantifiers
More complex sentences can be expressed using multiple quantifiers.
The simplest case is where the quantifiers are of the same type.
For example, “For all x and y if x is the parent of y then y is the child of x”
"x"y Parent(x, y)Child(y, x)
"x"y is equivalent to "x, y.
Similarly, “Brothers are siblings” can be written as
"x, y Brother(x, y)Sibling(y, x)

The other cases are where the quantifiers are of the mixture type " and $

“Everybody loves somebody” means that for every person, there is someone that person loves:
"x $ y Loves(x, y)
On the other hand, to say “There is someone who is loved by everyone” we write
$ y "x Loves(x, y)
The order of quantification is therefore very important. It becomes clearer if we put in parenthesis.

Connections between " and $

The two connectors " and $ are actually intimately connected with each other, through negation.
“Everyone likes ice cream “ is equivalent to
“there is no one who does not like ice cream”
This can be expressed as :
"x Likes(x, IceCream) is equivalent to $ x Likes(x, IceCream)

d)Equality
FOL includes Equality symbol (¿) to represent atomic sentences, other than using a predicate and terms.
The Equality symbol (¿) can be used to represent two terms to refer to the same object. For example,
Father(John)= Henry
says that the object referred to by Father(John) and the object referred to by Henry are the same.

Sentence → AtomicSentence | ComplexSentence

AtomicSentence → Predicate | Predicate(Term, . . .) | Term = Term
ComplexSentence → ( Sentence ) | [ Sentence ]
| ￢Sentence
| Sentence ∧ Sentence
| Sentence ∨ Sentence
| Sentence ⇒ Sentence
| Sentence ⇔ Sentence
| Quantifier Variable, . . . Sentence
Term → Function(Term, . . .)
| Constant
| Variable

37
 Quantifier → ∀| ∃
Constant → A | X1 | John | ・ ・ ・
Variable → a | x | s | ・・・
Predicate → True | False | After | Loves | Raining | ・・・
Function → Mother | LeftLeg | ・ ・ ・

OPERATOR PRECEDENCE : ￢,=, ∧, ∨,⇒,⇔

Figure 8.3 The syntax of first-order logic with equality, specified in Backus–Naur Form

Compare different knowledge representation languages

Language Ontological Commitment Epistemological Commitment
(What exists in the world) (What an agent believes about facts)
Propositional logic facts true/false/unknown
First-order logic facts, objects, relations true/false/unknown
Temporal logic facts, objects, relations, times true/false/unknown
Probability theory facts degree of belief  [0, 1]
Fuzzy logic facts with degree of truth  [0, 1] known interval value

Table: Formal languages and their ontological and epistemological commitments.

4.4 Inference in First-Order Logic

Some simple inference rules lead naturally to the idea that first-order inference can be done by converting
the knowledge base to propositional logic and using propositional inference. We will use the notation
SUBST(θ, a)
to denote the result of applying the substitution θ to the sentence a. For example:
SUBST({x/Sam, y/Pam}), Likes(x, y)= Likes(Sam, Pam).

Inference rules for quantifiers

Let us begin with universal quantifiers. Suppose our knowledge base contains the standard
folkloric axiom stating that all greedy kings are evil:
∀ x King(x) ∧ Greedy(x) ⇒ Evil(x)
Then it seems quite permissible to infer any of the following sentences:
King(John) ∧ Greedy(John) ⇒ Evil(John)
King(Richard ) ∧ Greedy(Richard) ⇒ Evil(Richard)
King(Father (John)) ∧ Greedy(Father (John)) ⇒ Evil(Father (John)) ,

(1) Universal instantiation (UI): This rule says that we can infer any sentence obtained by substituting a ground
term (a term without variables) for the variable. Let SUBST(, θ) denotes the result of applying the substitution θ
to the sentence . Then every instantiation of a universally quantified sentence is entailed as:

for any sentence , variable v and ground term g.

Example:
Let =All greedy Kings are evil.
i.e., For all x, if x is a Greedy King then x is evil.
"x King(x) Ù Greedy(x) Þ Evil(x) , which yields:
when substituting x=John
King(John) Ù Greedy(John) Þ Evil(John);
when substituting x= Richard
King(Richard) Ù Greedy(Richard) Þ Evil(Richard);

38
 when substituting x= Father(John)
King(Father(John)) Ù Greedy(Father(John)) Þ Evil(Father(John)).
UI can be applied several times to add new sentences; the new KB is logically equivalent to the old.

(2) Existential instantiation (EI)

In the rule for Existential Instantiation, the variable is replaced by a single new constant symbol. The
formal statement is as follows:
For any sentence, variable v, and constant symbol k that does not appear elsewhere in the knowledge base,

For example, from the sentence

∃ x Crown(x) ∧ OnHead(x, John)
we can infer the sentence
Crown(C1) ∧ OnHead(C1, John)
as long as C1 is a new constant symbol that does not appear elsewhere in the knowledge base.
C1 is a new constant symbol, called a Skolem constant.
Existential Instantiation can be applied once, and then the existentially quantified sentence can be discarded.
For example, from $x Kills (x, Victim), we can infer that $x Kills (Murderer, Victim)
as long as the constant symbol k=Murderer that does not appear elsewhere in the knowledge base.

(3) Inferential Equivalence

Whereas Universal Instantiation can be applied many times to produce many different consequences, Existential
Instantiation can be applied once, and then the existentially quantified
sentence can be discarded. For example, we no longer need
∃ x Kill (x, Victim)
once we have added the sentence
Kill (Murderer, Victim).
Strictly speaking, the new knowledge base is not logically equivalent to the old, but it can be shown to be
inferentially equivalent in the sense that it is satisfiable exactly when the original knowledge base is satisfiable.

4.5 Knowledge Representation

Knowledge representation is the method used to encode knowledge in an intelligent system’s knowledge base.
The object of knowledge representation is to express knowledge in computer-tractable form, such that it can be used to
help intelligent system to perform well. Knowledge is an abstract term that attempts to capture an individual’s
understanding of a given subject.
Knowledge base
A knowledge base is an integral part of any knowledge-based intelligent system.
It maps objects and relationships of the real world to computational objects and relationships.

There are 4 schemes of knowledge representation:

39
(1)Logical schemes: Logical schemes represent knowledge, using mathematical or orthographic symbols, inference
rules and are based on precisely defined syntax and semantics.
i. Propositional calculus
ii. Predicate(FOL) calculus
(2)Procedural schemes: In procedural schemes knowledge is represented as a set of instructions for problem-solving.
That allows to modify a knowledge base easily and to separate a knowledgebase from an inference mechanism.
IF..THEN..rules
(3)Structured schemes: Structured schemes extend networked representation by displaying each node in a graph as a
complex data structure.
i. Frames
ii. Scripts
(4)Networked schemes: Networked schemes use a graph to represent knowledge. Nodes of a graph display objects or
concepts in a domain, but arcs define relationships between objects, their attributes, and values of attributes.
i. Semantic nets
ii. Conceptual graphs

The Networked schemes are described below:

Networked schemes
(i) Semantic nets
Semantic network is a knowledge representation schema that captures knowledge as a graph. The nodes
denote objects or concepts, their properties and corresponding values. The arcs denote relationships between the
nodes. Both nodes and arcs are generally labeled (arcs have weights).

Symbols of semantic nets:

Nodes of semantic nets can represent: Concepts, Objects, Events, Features, Time etc.
Several kinds of relationships are used in semantic nets:
1.“Class -Superclass” or “Is-a” relationship

2.“Instance-class” or “Is an instance of” relationship

3.“Part-Whole” or “Part of” relationship

4.“Object-Attribute” or “Has” relationship

5.“Attribute-Value”or“Value” relationship

6. Logical relationships (and, or, not)

7. Linguistic relationships (examples: likes, owns, travels…)

40
Inheritance is possible in semantic nets. Inheritance is a process by which the local information of a superclass node is
assumed by a class node, a subclass node, and an instance node.
Example:
All vehicles have a brand name and a model. A car is a class of a superclass Vehicle. So Car inherits all features of
Vehicle that is, Brand Name and Model.

Fig. Example of semantic nets

Fig. Inheritance is possible in

semantic nets

(ii) Conceptual graphs

Concepts are a part of knowledge
about world. People perceive concepts and reason with them. Concepts are related with relationships
between them. Relationships between concepts form understanding of people.
A conceptual graph is a finite, connected, bipartite graph. Two types of nodes are used in conceptual
graphs:

In conceptual graphs the following arcs are allowed:

Between a concept and a conceptual relationship

Between a conceptual relationship and a concept

The following arcs are not allowed in conceptual graphs:

Between a concept and a concept

Between a conceptual relationship and a conceptual relationship

Every conceptual relation r has a relation type t and a nonnegative integer n called its valence.
•The number of arcs that belong to r is equal to its valence n. A conceptual relation of valence n is said to be n-adic,
and its arcs are numbered from 1 to n.
•For every n-adic conceptual relation r, there is a sequence of n concept types t1,...,tn, called the signature of r. A 0-adic
conceptual relation has no arcs, and its signature is empty.

41
•All conceptual relations of the same relation type t have the same valence n and the same signature s.
•The term monadic is synonymous with 1-adic, dyadic with 2-adic, and triadic with 3-adic.

1-adic relation–Must be one outgoing arc from a conceptual relationship

2-adic relation–Must be one outgoing and one ingoing arc.

3-adic relation–Must be two ingoing arcs and one outgoing arc.

Concepts have the following form:

Concept= Type+ Referent,
Where Type is a type of a concept, cannot be empty;
Referent = Quantifier+ Designator, can be empty

: Forms of concepts
1. A node containing only a type of a concept
“There is a dog, but it is not specified which one dog”

2. Type + individual marker. Names of persons, places, or organizations can be displayed by an individual marker.

3. Specific but unnamed individual. Identity of an object can be acquired from context performing inference

4. Several objects:
-By listing them

-Using {*}

5. Precise number of objects: @number

6. Units of measurements

7.All by using “ or ∀

42
 “All fish are wet”
8. A conceptual graph can include a concept which is a conceptual graph by itself.

9. Different combinations

Operations of conceptual graphs:

Theory of conceptual graphs defines 4 operations:
i. Copying
ii. Restricting
iii. Joining
iv. Simplifying
Copying allows acquiring of a new conceptual graph G1 which is identical with the already existent conceptual graph
G.
Restricting allows replacing of a concept node by its specialization. Two cases are possible:
•Type can be replaced by an individual marker
•Type can be replaced by its subtype
Joining allows joining of two conceptual graphs if they have an identical concept node.
Simplifying allows removing of one of two identical nodes of a conceptual relation together with all its arcs.

In order to apply the mentioned operations a type hierarchy must be defined:

if s and t are types of concepts and t ≤ s, then t is subtype of s.
Examples:
Manager≤Employee≤Person
Dog≤Animal
John≤Man≤Person
For example, we have two conceptual graphs G1 and G2 and a type hierarchy
Dog ≤ Animal

43
Restricting operation can be applied to the graph G1 by replacing type Animal with its subtype Dog: Reksi.
A new graph G3 is acquired as a result.

Now we can join graphs G2 and G3, because they have an identical concept node Dog:Reksi.
A new graph G4 is acquired.

By simplifying the graph G4 a new graph G5 is acquired.

Inheritance in conceptual graphs

By using restriction and joining operations of conceptual graphs it is possible to support inheritance. When
a type is replaced by an individual marker an instance inherits features from a type. When a type is replaced by a
subtype then the subtype inherits features from the type.
Example: The type hierarchy Chimpanzee ≤ Primate is defined.

Logic and conceptual graphs

In conceptual graphs it is possible to represent logical operations AND, OR and NOT.
1. Negation is implemented using a propositional node and a unary conceptual relation NOT.
Example:
A conceptual graph displaying a sentence “The sun is not shining”

44
2. Conjunction is displayed by placing both conceptual graphs in the common propositional node.
Example:
A conceptual graph displaying a sentence “The study course is interesting and difficult”

3. Disjunction is represented by negation and conjunction.

a. A graph G1 must be placed as a propositional node and its negation must be made.
b. A graph G2must be placed as a propositional node and its negation must be made.
c. Both negations must be placed in a propositional node and its negation must be made.

4.6 Knowledge-based Systems

A knowledge-based system (KBS) is a computer program that reasons and uses a knowledge
base to solve complex problems. A knowledge based system has two types of sub-systems:
a knowledge base and
an inference engine(search program).
The knowledge base represents facts about the world. The knowledge base can be used as a repository of
knowledge in various forms. This may includes an empty WorkSpace to store temporary results and
information/knowledge pieces/chunks.

The IE(inference engine) is a software program, which infers the knowledge available in the knowledge base.

As an expert’s power the expert system’s creditability also depends on the Explanation and Reasoning of the decision
made/suggested by the system. Also, human beings have an ability to learn new things and forget the unused
knowledge from their minds. Simulation of such learning is essential component of KBS. The life of KBS may vary
according to the degree of such simulation. KBS may be either manually updated (manual update) or automatically
updated by machine (machine learning). Ideally, the basic frame of a KBS rarely needs to be modified. In addition to
all these, there should be an appropriate User Interface, which may have the Natural Language Processing facility.
These components are shown in Figure 2.

Figure 2: Architecture of a Knowledge-Based System

There are main 5 types of the KBS exist:
(i) Expert Systems,
(ii) Hypertext Manipulation Systems,
(iii) CASE Based Systems,
(iv) Database in conjunction with an Intelligent User Interface and

45
 (v) Intelligent Tutoring Systems.

KBS ADVANTAGES AND LIMITATIONS

Knowledge-based systems are more useful in many situations than the traditional computer based information
systems. Some major situations include:
 When expert is not available.
 When expertise is to be stored for future use or when expertise is to be cloned or multiplied.
 When intelligent assistance and/or training are required for the decision making for problem solving.
 When more than one experts’ knowledge have to be grouped at one platform.

46