Introduction to AI

AAPP002-4-2 Ver 1.0

Knowledge Representation 2
 Topic & Structure of The Lesson

• Proposition logic
• Predicate Logic

AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide ‹2› of 28

 Learning Outcomes

• At the end of this topic, You should be

able to
• Knowledge Representation 2
• Semantic Network
• Frame
• Predicate logic

AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide ‹3› of 28

 Key Terms You Must Be Able To
Use
• If you have mastered this topic, you should be able to use the
following terms correctly in your assignments and exams:

• propositions
• disjunction
• conjunction
• negation
• implication
• truth tables
AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide 4 of 28
 Predicate Logic @ Predicate Calculus

To determine the truth of assertions about objects, or

events by using the techniques of propositional logic
(calculus).

Predicate logic is the basis for the computer

language – PROLOG.

AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide 5 of 28

 Step

Propositional
Logic English

Predicate
Calculus @
First Order Logic

Prolog

AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide 6 of 28

 Logic

• Includes
– Syntax—symbols of the language and how the
symbols can be combined
– Semantics—rules for interpreting symbols and
sentences in the language

AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide 7 of 28

 Propositions

Propositions must have a truth value !

Therefore a sentence which is classified as
a proposition must be either
true(T) or false(F)

No intermediate values allowed !!

AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide 8 of 28

 Propositional Logic

• The simplest formal logic.

• Largely based on set theory.
• Will present syntax and semantics.

AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide 9 of 28

 Interpretations

1) Negation (NOT): ~
2) Disjunction (OR): 
3) Conjunction (AND): 
4) Implication (IF…THEN…):  

AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide 10 of 28

 Syntax of Propositional Logic

• A propositional symbol (e.g., P, Q, R, S)

is a sentence.
• If  is a sentence and  is a sentence,
then the following are sentences.
()
~


AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide 11 of 28

 Semantics of Propositional Logic

The rules in propositional logic:

If sentence a is True, then so is (a).

If sentence a if False, then ~ is True.
If either a or b is True, then  is True.

AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide 12 of 28

 Truth Tables

a ~a a b ab
T F T T T
F T T F T
F T T
F F F

AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide 13 of 28

 More Truth Tables

a b ab
T T T
T F F
F T F
F F F

a b ab
T T T
T F F
F T T
F F T
AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide 114 of 28
 Derived Sentences

• All sentences can be derived from

sentences involving the operators ~,  and
.

•     ~~  ~
•  ~

AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide 15 of 28

 Proof by Truth Tables

• Given: P1  P2 and ~P2

• Prove :

AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide 16 of 28

 Class Exercise 2

Find the truth value for each proposition.

p = F, q = T, r = F

1. p q
2. p qp
3. ~(p qq r
4. (p qp q) p qp q

AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide 17 of 28

 Class Exercise 3

Let p and q be the propositions

p: I bought a lottery ticket this week
q: I won the million dollars jackpot on Friday
Write the statements for the logic below:
(a) ~p
(b) p  q
(c) p q
(d) ~p ~q
(e) p  q
AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide 18 of 28
 Class Exercise 4

Let p and q be the propositions

p: It is below freezing
q: It is snowing
Write the following propositions using p and q logic
connectives.
(a) It is below freezing and snowing
(b) It is below freezing but not snowing
(c) It is not below freezing and it is not snowing.
(d) It is either snowing or below freezing (or both)
(e) If it is below freezing, it is also snowing
(f) If is either below freezing or it is snowing, but it is not
snowing if it is below freezing
AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide 19 of 28
 Predicate Logic

Uses quantifiers like universals and existentials:

• Universals :
– x P(x) means For every x where x is P
• Existentials :
– x P(x) means There exists x where x is P

AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide 20 of 28

 Universal

Question:
Let P(x) = “x > 0 where x is the set of positive
numbers ”.
What are the truth values of P(4) and P(20) ?
Solution:
For P(4), it is T and for P(20) it is T.

Therefore, it can be concluded:

(x) P(x)

AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide 21 of 28

 Existential

Question:
Let P(x) = “x > 3.”
What are the truth values of P(4) and P(2) ?

Solution:
For P(4), it is T and for P(20) it is T. But for P(2),
it is F.
Therefore, it can be concluded:

(x) P(x)

AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide 22 of 28

 Predicate Logic representation

• Every gardener likes the sun.

– x gardener(x) likes(x,Sun)
• You can fool some of the people all of the time.
– x t (person(x)  time(t) can-fool(x,t)
• No purple mushrooms is poisonous.
~x purple(x)  mushroom(x)  poisonous(x) @
x purple(x)  mushroom(x) ~poisonous(x

AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide 23 of 28

 First-Order Logic

Question:
Express the statement “If somebody is female and is a
parent, then this person is someone’s mother” as a
logical expression.
Solution:
Let F(x) be the statement “x is female,” let P(x) be the
statement “x is a parent,” and let M(x,y) be the statement “x is
the mother of y.” Since the statement in the question pertains
to all people, we can write it symbolically as
" x: (F(x)  P(x) M(x,y))

AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide 24 of 28

 Quick Review Question

• Represent the following facts in predicate

logic or first-order logic:
• Some paper clips come in boxes
• All metals conduct electricity well
• All living hearts have a rhythm
• No person is both male and female
• One child is a sibling of another if they
both have the same two parents
AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide ‹25› of 28
 Summary of Main Teaching Points

• Creating propositions is the first step in producing

predicate logic representation
• Propositions will always have a truth value
• There are four interpretations available in the
propositional logic
• Producing truth tables is one way of deriving the truth
value of a proposition
• Sentences can be derived from other sentences using
the operators in propositional logics

AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide ‹26› of 28

 Question and Answer Session

Q&A

AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide ‹27› of 28

 What we will cover next

• Knowledge Representation 2
–Frame

AAPP002-4-2 Introduction to Artificial Intelligence Knowledge Representation 2 Slide ‹28› of 28