Year: 2024-2025
Spring Semester
Natural Language
Processing
Dr. Wafaa Samy
Dr. Hanaa Eissa
Knowledge Representation
(Part 1)
Lecture (13)
2
Contents
• Knowledge Representation (KR)
o Propositional Logic
3
Knowledge Representation (KR)
• Knowledge representation (KR) is the field of study concerned
with using formal symbols to represent a collection of
propositions believed by some agent.
• The primary goal of knowledge representation is to enable an
intelligent agent (program) with a knowledge base (KB), a
collection of symbolic structures representing what it believes
and reasons with, to make intelligent decisions about its
environment.
• From the context of NLP, representing knowledge is focused on
using that knowledge to solve problems.
• Therefore, the manner in which the knowledge is stored is
important.
• The knowledge must be stored in a way that makes it possible
for NLP to search it, and if necessary, infer new knowledge from it.
4
Propositional Logic
• The simplest, and most abstract logic we can
study is called propositional logic.
• It is a formal system in which knowledge is
represented as a proposition.
o The statements are made by propositions.
o The sentence (or statement) is declarative, which
is either true or false, but can not be both.
5
Proposition
• Definition:
o A proposition is a statement that can be either true or false, but it
cannot be both.
• It is possible to determine whether any given statement is a
proposition by prefixing it with:
It is true that ………………………………..……
and seeing whether the result makes grammatical sense.
• Examples:
o The following are propositions: Two Types of Propositions:
The heater is on. 1. Atomic Proposition.
John Major is prime minister. 2. Complex/Compound
Ahmed is a teacher. Proposition.
o The following are not propositions:
Are you going out somewhere?
6 2+3
Atomic Proposition
• Atomic propositions are the set of smallest
propositions.
• Definition: An atomic proposition is one whose truth
or falsity does not depend on the truth or falsity of any
other proposition.
• So, all the previous propositions are atomic.
• Now, rather than write out propositions in full, we will
abbreviate them by using propositional variables.
• If we do this, we must define what we mean by writing
something like:
• Let P stands for: John Major is prime Minister.
7
Complex Proposition
• Many statements are of the
• There are a number of connectives which form: If……….Then………..
will allow us to build up complex if P is true then Q is true.
Another way of saying the same
propositions.
thing is to write: P implies Q.
• The connectives include:
• Another common form of
1. Conjunction: ∧ and statement is:
2. Disjunction: ∨ or P is true if, and only if, Q is true.
3. Negation: ¬ not The sense of such statements is
4. Implication: ⇒ implies captured using the biconditional
5. Equivalence: ⇔ iff (biconditional implication) operator ⇔.
P Q ¬P P∧Q P∨Q P⇒Q P⇔Q
Connectives F F T F F T T
F T T F T T F
T F F F T F F
8
T T F T T T T
Proposition: Examples
• Proposition is an abstract entity that can be either true or false.
Complex If Adel is intelligent and Adel is
Proposition
Hardworking then Adel gets high scores.
• Let P stands for: Adel is Intelligent. Atomic
Propositions
• Let Q stands for: Adel is Hardworking.
P and Q
• What is the meaning of P ˄ Q?
• What is the meaning of P ˅ Q? P or Q
• P ˄ Q , P ˅ Q are compound propositions.
9
Elements of Propositional Logic (PL)
• PL is a simple language useful for showing key ideas and definitions.
• Alphabet
o A set of propositional atomic symbols (P , Q , R etc.) each of which can
be either True or False.
o Set of logical operators:
∧ (AND) , ˅ (OR), ¬ (NOT), ⇒ (Implies), and ⇔ (Equivalence).
Parenthesis, ( ) , are used for grouping.
o Two logical symbols called logical constants: True (T) and False (F)
• Forming Propositional Sentence:
A sentence (well formed formula) is defined as follows:
o A symbol is a sentence.
o If S is a sentence, then S is a sentence.
o If S is a sentence, then (S) is a sentence.
o If S and T are sentences, then (S T), (S T), (S ⇒ T), and (S ⇔ T) are
sentences.
10 o A sentence results from a finite number of applications of the above
rules.
Examples of PL Sentences
• User defines a set of propositional symbols, like P and Q.
• User defines the semantics of each propositional symbol:
o P means “It is hot”.
o Q means “It is humid”.
o R means “It is raining”.
• (P Q) ⇒ R “If it is hot and it is humid, then it is raining”.
• Q⇒P “If it is humid, then it is hot”.
• We can nest complex formulas as deeply as we want. We can use
parentheses (i.e. ( , )). If P, Q, R, S and T are atomic propositions, then all of
the following are formulas:
P∧Q (P ∨ Q) ⇒ R ¬ (P ∨ Q)
P^Q⇒R ((P ∧ (Q ⇒ R)) ∨ S) ∧ T
• Whereas the following are not propositions:
P∧
11 P ∧ Q)
P¬
Context-Free Grammar for
Propositional Logic
12
Practice
• P: You learn the simple things well.
• Q: The difficult things become easy.
• You do not learn the simple things well.
• If you learn the simple things well then the difficult things
become easy.
• If you do not learn the simple things well, then the difficult
things will not become easy.
• The difficult things become easy but you did not learn the
simple things well.
• You learn the simple things well but the difficult things did not
13 become easy.
Practice (Cont.)
• P: You learn the simple things well.
• Q: The difficult things become easy.
• You do not learn the simple things well. ¬ P
• If you learn the simple things well then the difficult things
become easy. P ⇒ Q
• If you do not learn the simple things well, then the difficult
things will not become easy. ¬ P ⇒ ¬ Q
• The difficult things become easy but you did not learn the
simple things well. Q ∧ ¬ P
• You learn the simple things well but the difficult things did not
14 become easy. P ∧ ¬ Q
Example (1)
• Convert the following to propositional logic:
o If I am clever then I will pass.
o If I will pass then I am clever.
o Either I am clever or I will pass.
o I am clever and I will pass.
15
Example (1): Solution
• P: I am clever.
• Q: I will pass.
• Convert the following to propositional logic:
o If I am clever then I will pass.
P⇒Q
o If I will pass then I am clever.
Q⇒P
o Either I am clever or I will pass.
P∨Q
o I am clever and I will pass.
P∧Q
16
Compound Propositions
• Let:
o p: 2 is a prime number ….. T ()
o q: 6 is a prime number ….. F Highest
• Determine the truth value of
the following statements:
¬p :F
p∧q :F Lowest
p ∧ ¬q : T
p∨q :T
p⇒q :F
q⇒p :T
17
Constructing the Truth Table
18
Constructing the Truth Table (Cont.)
19
Example (2): Constructing the Truth
Table
20
Tautology and Contradiction
21
Example (3)
22
Logical Equivalence
• Logical equivalence: Two statements are called
logically equivalent if the truth values of both the
statements are always identical.
• For example: If we take two statements p ⇒ q and
¬q ⇒ ¬p , then their truth table values must be
equal to satisfy the condition of logical equivalence.
23
Example (4)
• Show if the two statements p ⇒ q and ¬q ⇒ ¬p are
logically equivalent.
p q ¬p ¬q p⇒q ¬q⇒¬p
F F T T T T
F T T F T T
T F F T F F
T T F F T T
Since, the truth table values of both statements is the same. Thus,
the two statements p ⇒ q and ¬q ⇒ ¬p are logically equivalent.
24
Applications of Propositional Logic
• Translation of English sentences.
• Inference and reasoning:
o New true propositions are inferred from existing
ones in the knowledge base.
o Used in Artificial Intelligence:
E.g. Rule based (expert) systems.
• Design of logic circuit.
25
Translation
26
Translation (Cont.)
27
Translation: Example
• Assume a sentence:
If you are older than 13 or you are with your parents then you
can go to the trip with other students.
1. Parse:
If ( you are older than 13 or you are with your parents ) then
( you can go to the trip with other students).
2. Atomic (elementary) propositions:
o A = you are older than 13
o B = you are with your parents
o C = you can go to the trip with other students
3. Translation: A ∨ B ⇒ C
28
Example (5)
• Use the propositional logic to write the truth table for the
following sentence: The sun is shining and the day is warm.
F
F
F
T
29
Example (6)
Propositional Logic formula:
30
Example (6): Solution
Propositional Logic formula:
31
Reasoning
• Reasoning is the formal manipulation of the symbols
representing a collection of believed propositions to produce
representations of new ones.
• What is inference?
o So far, we’ve considered how to:
Express statements using propositional logic.
Compute statements using propositional logic.
Show equivalence of different ways to express or compute
statements.
o Logic also has methods to infer statements from the ones we
know.
32
o Each inference by the application of an inference rule.
Inference Rules
1. Modus Ponens:
P, P ⇒ Q, then Q
• For example:
P The light is on
P⇒Q if the light is on then the switch is on
----------
Q the switch is on
33
Inference Rules (Cont.)
1. Modus Ponens:
34
Inference Rules (Cont.)
2. Modus Tollens:
• P ⇒ Q, and Not Q then Not P
• For example:
P⇒Q if the light is on then the switch is on
¬Q The switch is not on
----------
¬P The light is not on
35
Inference: Example
• Assume we know the following sentences are true:
o If you are older than 13 or you are with your parents then you
can go to the trip with other students.
o You are older than 13.
• Translation:
• If ( you are older than 13 or you are with your parents ) then ( you
can go to the trip with other students). (You are older than 13).
o A = you are older than 13
o B = you are with your parents
o C = you can go to the trip with other students
• (A ∨ B ⇒ C) is True, and A is True.
• With the help of the Modus Ponens inference rule, we can
infer the following statement (proposition):
36
o You can go to the trip with other students or C is True
Note
• There are many aspects of Natural language that
propositional logic cannot express.
• For example when translating the sentences:
o Every prince saw a lady.
o Some prince saw a beautiful lady.
• In propositional logic, the connection between their meanings
is lost because they would have to be represented as
completely different propositions P and Q.
• To capture some of the internal structure of sentences like
those, the first-order predicate logic is used, which is an
extension of propositional logic with variables and quantifiers.
37
Exercise (1)
38
Exercise (1): Solution
• p = False , q = True , r = False
1. p ∨ q = False ∨ True = True
2. ¬p ∨ ¬q = (¬p) ∨ (¬q) = True ∨ False = True
3. ¬p ∨ q = (¬p) ∨ q = True ∨ True = True
39
Exercise (1): Solution (Cont.)
• p = False , q = True , r = False
4. ¬p ∨ ¬(q ∧ r) = True ∨ ¬(False) = True ∨ True = True
5. ¬(p ∨ q) ∧ (¬q ∨ r) = ¬(True) ∧ (False) = False ∧ False = False
6. (p ∨ ¬r) ∧ ¬[(q ∨ r) ∨ ¬(r ∨ p)] = True ∧ False = False
True ∧ ¬ [ True ∨ ¬ ( False )]
40 True ∧ False
Exercise (2)
41
Exercise (3)
42
