Artificial Intelligence

Representing Knowledge Using

Propositional & Predicate Logic
 Epistemology
(Greek word episteme means "knowledge";
logos means, "theory"),
 the science of knowledge
 branch of philosophy concerned with
the theory of knowledge: Nature,
Structure, Scope, Validity, Foundations
and Origin
2
 Epistemology

 The main problems with which

epistemology is concerned are the definition
of knowledge and related concepts, the
sources and criteria of knowledge, the kinds
of knowledge possible and the degree to
which each is certain, and the exact relation
between the one who knows and the object

3 known.
 Knowledge Definitions

 The fact or condition of knowing something

with familiarity gained through experience or
association
 Acquaintance with or understanding of a
science, art, or technique
 The range of one's information or
understanding

4
 Knowledge Definitions
 The circumstance or condition of
apprehending truth or fact through reasoning
 The sum of what is known : the body of truth,
information, and principles acquired by
mankind
 knowledge applies to facts or ideas acquired
by study, investigation, observation, or
experience
5
 Types of Knowledge
 a priori knowledge
– From Latin word & means “ That which
precedes”
– comes before and independent of the
knowledge perceived through senses
– considered to be universally true
– Exp. All triangles in plane have 180 degrees
– Can not be denied without a contradiction

6
 Types of Knowledge

 a posteriori knowledge
– Opposite of a priori knowledge
– knowledge verifiable through the senses
– may not always be reliable
– Can be denied on the basis of new
knowledge

7
 Types of Knowledge
 procedural knowledge
– knowing how to do something, How
something occurs
– knowledge that is used over and over
again.
– Exp. How to make a cup of tea

8
 Types of Knowledge
 declarative knowledge
– knowing that something is true or false
– knowledge that the expert is aware or
conscious of.
– It is shallow knowledge.
– Expressed in the form of declarative
statements like “Don’t touch hot surface.”

9
 Types of Knowledge
 tacit knowledge
– Implied (actionable) knowledge & difficult to
articulate
– knowledge not easily expressed by language
– expertise & experiences in person’s mind i.e.,
derived from experience and embodies beliefs
– usually shared through highly interactive
conversation, story-telling, shared experience.
– generation of new knowledge
10
 Types of Knowledge
 Explicit knowledge
– more precisely and formally articulated

– easily codified, documented, transferred

and shared.

– manuals, procedures, product literature,

computer software, etc

11
 Knowledge Pyramid

Meta-

Knowledge

Information

Data

Noise
12
Data,
Data, Information,
Information, Knowledge
Knowledge

Intelligence Human, judgemental

Contextual, tacit
Knowledge Transfer needs learning

Information
Codifiable, explicit
Easily transferable
Data
 Representation Representation Representation
 Think about knowledge, rather than data in AI
 Facts
 Procedures
 Meaning
– Cannot have intelligence without knowledge
 Always been very important in AI
 Choosing the wrong representation
– Could lead to a project failing
 Still a lot of work done on representation issues
14
 Representations for
Problem solving techniques
 For certain problem solving techniques
– The “best” representation has already been worked out
– Often it is an obvious requirement of the technique
– Or a requirement of the programming language (e.g.,
Prolog)
 Examples:
– First order theorem proving (first order logic)
– Inductive logic programming (logic programs)
– Neural networks learning (neural networks)
 But what if you have a new project?
– What kind of general representations schemes are
15 there?
 Four General Representation Types
 Production Rules

 Logical Representations

 Semantic Networks

 Frames

16
 Knowledge representation
 representation not the same as encoding
 Encoding maintains ambiguity
 examples -
– The hammer hit the vase and it broke
– The vase hit by the Munir and it broke
 Representation implies organization

Vase: Container for flowers

17
 Representation concepts

 “A representation - a set of syntactic and

semantic conventions that make it
possible to describe things”
 The syntax of a representation specifies a set
of rules for combining symbols to form
expressions in the representation language.

18
 Logic

 Logic consists of the following:

 A formal system for expressing knowledge
about a domain describing the Syntax and
Semantics.
 The Proof theory- a set of rules of inference
for deducing the sentences from a Knowledge
Base (a set of sentences).

19
 Logic
 Earliest form of Formal Logic was developed
by Aristotle in 14th century B.C. based on the
Syllogism.
 Syllogism is one of the oldest and simplest
types of formal logic.
 A Syllogism is an arrangement involving three
propositions:
– Two premises
– One conclusion
20
 Propositional Logic (PL)

 A branch of Deductive Logic.

 Propositional logic also known as Boolean Logic; is a

symbolic logic for manipulating logic variables
representing propositions.

 It is concerned with the subset of declarative

sentences which can be classified as either TRUE or
FALSE.

21
 Propositional Logic (PL)
 Propositions are statements of fact.
The English sentence
 “The sky is blue” expresses the
proposition that the sky is blue.
 Using Logic Connectives more
complex sentences or compound
statements can be formed.

22
 Propositional Logic

Syntax Semantics

 AND; Conjunction (The  looks like an “A” for “And”.)

OR; Disjunction (The  comes from the Latin “vel” which means “or”.
 Its easy to remember as an upside-down ‘and’.)
NOT; Negation (Only connective that operates on single statement. i.e.
 Unary Connective.)
IMPLIES THAT; Conditional (Implications are also known as rules or
 if -then statements.)

EQUIVALENCE; Biconditional (It also means if and only if.

 Biconditional P  Q is equivalent to (P  Q)  (Q  P) )

23 Order of precedence is First:  Second:  and  Third:  and .

 Truth Table for Connectives

P Q ¬ P
  PQ PQ PQ PQ

True True False True True True True

True False False False True False False

False True True False True True False

False False True False False True True

24
 More on Syntax and Semantics of Logics
 Syntax
– How we can construct legal sentences in the logic
– Which symbols we can use (English: letters, punctuation)
– How we are allowed to write down those symbols
 Semantics
– How we interpret (read) sentences in the logic
– i.e., what the meaning of a sentence is
 Example: “All Students are six feet tall”
– Perfectly valid sentence (syntax)
– And we can understand the meaning (semantics)
– This sentence happens to be false (there is a counterexample)

25
 Propositional Logic
 Syntax
– Propositions such as P meaning “it is wet”
– Connectives: and, or, not, implies, equivalent

– Brackets, T (true) and F (false)

 Semantics
– How to work out the truth of a sentence
 Need to know how connectives affect truth
 E.g., P and Q is true if and only if P is true and Q is true
 P implies Q is true if P and Q are true or if P is false
– Can draw up truth tables to work out the truth of
statements
26
 Automated Reasoning

 “Reasoning” usually means deductive

(truth-preserving) reasoning
– New facts are deduced logically from old
ones
 Two main aspects of deductive reasoning
– Logical representations (thousands of them)
– Rules of deduction (how to deduce new
things)
27
 First Order Predicate Logic
 Keep thinking of predicate logic as a language
 Predicate Logic is a development of
Propositional Logic.
 Propositional Logic is a subset of FOPL.
 FOPL is concerned with the internal structure
of the sentences.
 It is more simple, easy and makes use of
Predicates , Functions and symbols like
Variables, Constants, Logic connectives
and Quantifiers.
29
 Syntax and Semantics of FOPL
 We need to communicate (share knowledge)
with AI agent
– Using logic as the knowledge representation scheme
– Need to inform and to understand
 Syntax
– Symbols used and how sentences are put together
 Predicates, connectives, constants, functions, variables,
quantifiers
 Semantics
– How we interpret what sentences mean
– How we translate between the two languages
– How we tell the truth of a sentence
30
 Predicates
 Predicates are statements that
– Certain things are related in specific ways
– Predicate name identifies the relationship
– Arguments are the things being related
– Arity is the number of things being related
 Example: father( Shahid, Wajid)
 Father is the predicate name
– Relationship is (nearly) obvious: Shahid is Wajid’s father
– Shahid and Wajid are the arguments (arity here is 2)
 Predicates can relate
– Constants, functions and variables

31
 Connectives: And, Or
 “And” represented by: (i) & (ii) ∧ (iii) ,
– If predicates p1 and p2 are true then (p1 ∧ p2) is true

 “Or” represented by: (i) ∨ (ii) | (iii) ;

– If either predicate p1 or predicate p2 is true (or both)
 Then (p1 ∨ p2) is true

 Also note the use of brackets

– Indicate where to stop and work out truth values

32
 Connectives:
Not, Implies, Equivalence
 “Not” represented by: (i) ┓(ii) ∼ (iii) \+
– Changes predicate truth (true to false, or false to true)

 “Implies” represented by: → or ←

– If one statement is true, then another is also true

 “is equivalent to” represented by: ↔

– You’ll also hear:
 “if and only if” & “necessary and sufficient condition”

33
 Examples of Connectives in Use
 “Azam lectures AI and OOP”
lectures_ai(Azam) ∧ lectures_OOP(Azam)
Better:
lectures(Azam,ai) ∧ lectures(Azam,OOP)
 “If Azam isn’t lecturing AI, Shahab must be”
┓lectures(Azam,ai) → lectures(Shahab,ai)
 “George and Tony will win or Saddam will lose”
(will_win(george) ∧ will_win(tony)) ∨ ┓will_win(saddam)

34
 Constants
 Stand for actual things or objects found with
their particualr names or values like:
– Fido is a dog
– Cat is a mammal
 Also use constants for specific words like blue
– But blue has different shades…
– In this case you should have:
 Made blue a predicate name, then you could have had:
 shade_of_blue(aqua_marine), shade_of_blue(navy), etc.
– Choosing predicates and constants is important

35
 Convention: use lower case letters for constants
 Functions
 Special predicates
– Where we think of them having inputs and an output
– If arity n, then the first n-1 arguments are inputs
 And the final argument is thought of the output
 Important
– A function has an output for a set of inputs
 Use the equals sign to make I/O clear
– And to make it clear this is a function

36
 Example of a Function
 “The cost of an omelette at the Red Onion is 500”
 Normally:
– cost_of(omelette,red_Onion,five_hundred)
 But cost_of is a function
– Input: the name of a meal and the name of a resturant
– Output: the cost of the meal
 So, we can write this as:
– cost_of(omelette,red_Onion) = five_hundred

37
 Using Functions for Abbreviation
 We want to minimise misunderstanding
– So, if we can, we should make sentences brief and to the point
– If we want to, we can abbreviate:
– If we are talking about the output of a function
– We can replace it with the predicate part
– i.e., replace the RHS of equality with the LHS

 Example:
– “Omelettes at the Red Onion cost less than
pancakes at House of Pancakes”
less_than(cost_of(omelette,red_Onion),cost_of(pancake,pancake_house))

38
 Variables
 Want to be more expressive now
– “There’s a meal at the Red Onion which costs £3”
 cost_of(meal,red_Onion) = 3
– But meal is a constant, like omelette or pancake
– Doesn’t express what we wanted it to
 We’re really talking about some general meal
– Not a meal in particular
– Call this meal X (a variable)
 cost_of(X,red_Onion) = 3
– Not quite right yet
39
 Variables Continued
 Need to further express our beliefs about X
 We say that:
– “There is such a meal X”
– “There exists such a meal X”
 We need a symbol for “there exists”
– This is represented as: ∃
– ∃ X (cost_of(X,red_Onion) = 3)
– Still not quite right (see later)

40
 Quantifiers
 The exists sign is known as a quantifier
– A sentence is known as “existentially quantified”
 Using quantifiers is known as quantification
 One other quantifier: ∀ (“forall sign”)
 Example: “all students enjoy AI lectures”
∀ X (student(X) → enjoys(X,ai_lectures))
 This is “universally quantified”
– Forall says that each predicate involving the quantified variable
is true for every possible choice of that variable
 Terminology:
– Constants are ‘ground variable’, and we ‘instantiate’ a variable
– “All meals cost £3” becomes “Spaghetti costs £3”
41
 Be careful with quantifiers!!

“There is a meal at the Red Onion which costs three pounds”

∃ X (meal(X) ∧ cost_of(red_Onion, X) = 3)
What about:
“All the meals at the Red Onion cost three pounds”
Replace exists by forall:

∀ X (meal(X) ∧ cost_of(red_Onion, X) = 3)

∀ X (meal(X) → cost_of(red_Onion, X) = 3)

∀42
X (meal(X) & serves(red_Onion, X) → cost_of(red_Onion, X) =3)
 Even More Pitfalls
 Getting ∧ and ∨ mixed up
“Every Monday and Wednesday I go to Ali’s house for Study”
∀ X (day(X,mon) ∨ day(X,weds)
→ go(me,house(Ali)) ∧ study_with(me,Ali))
 Getting confused with quantifiers
 Translate: “All things in the bag are red”
 Which of these translations is correct?

1. ∃ X (in_bag(X) → red(X))

2. ∀ X (red(X) → in_bag(X))

43 3. ∀ X (∀ Y (bag(X) ∧ in_bag(Y,X) → red(Y)))

 Nested quantifiers

Use of Nested quantifiers

 There is someone who is loved by everyone.
 y x Loves(x,y)
 If X is parent of y then Y is child of X
 x,y Parent(x,y)  Child(y,x)

44
 Translating Logic to English
 Take explicit sentence, make it more succinct
 Example:

∃ X (meal(X) ∧ cost_of(red_Onion, X) = 3)
1. “There is something called X, where X is a meal
and X costs three pounds at the Red Onion”
2. “There is a meal, X, which costs three pounds at
the Red Onion”
3. “There is a meal which costs £3 at the Red
Onion”
45