Bài giảng Hệ chuyên gia - Phan Huy Khánh - Chương 2: Biểu diễn tri thức nhờ logic vị từ bậc một (Phần 2)

rue
Q
False
True
False 
True
P
False
False
True
True
39/68
Terminology
(P ∧
¬R ∧
Q) →
(¬P ∨
R ∨
Q) 
propositional
variables
literals
a A literal is either a propositional variable, or the negation 
of a propositional variable
conjunction of literals
disjunction of literals
40/68
Special Forms
a A formula is in Disjunctive Normal Form (DNF) if it is a 
disjunction 
D
1
∨
D
2
∨
…
∨
D
n
where
each D
i
is a conjunction of literals
a A formula is in Conjunctive Normal Form (CNF) if it is a 
conjunction 
C
1
∧
C
2
∧
…
∧
C
n
where each C
i
is a disjunction of literals
41/68
Example
a Disjunctive Normal Forms
(¬P ∧
¬R) ∨
(¬P ∧
Q) ∨
(Q ∧
¬R) ∨
Q
(¬P ∧
¬R ∧
¬Q) ∨
(¬P ∧
¬R ∧
Q) ∨
(¬P ∧
R ∧
Q)
 ∨
(P ∧
¬R ∧
Q) ∨
(P ∧
R ∧
Q) 
a Conjunctive Normal Forms
(¬P ∨
¬R ∨
Q) ∧
(¬P ∨
R ∨
Q) ∧
(P ∨
¬R ∨
Q)
(¬P ∨
Q) ∧
(¬R ∨
Q)
P ∧
Q
42/68
Logical
Equivalence
Two propositions are (logically) equivalent
if and only if for each case 
their truth values are the same (“≡”)
also called identities
Examples: 
P ≡
(P∨P)
“1+1=2”
↔
“1+1=2 or 1+1=2”
¬¬P ≡
P
“He did not not do it”
↔
“He did it”
¬(P∧Q) ≡
¬P ∨
¬Q
“If P then not P”
≡
“not P”
Proving that two propositions are equivalent 
can be done by comparing their two truth tables
43/68
Example of Equivalence
a How to prove “Q ∧ (¬R→P) ↔ (R∧Q)∨(P∧Q)”?
a Earlier we saw…
while for the other proposition…
44/68
Biconditional
vs. Equivalence
a Don’t confuse
the equivalence ≡
with the biconditional ↔
(only the biconditional has a truth table) 
a For example:
P ≡
P is a proposition/tautology, 
a statement within logic, 
P ≡
P is mathematically correct, … about logic
P ≡ ¬P is a contradiction (False), 
P ≡ ¬P is incorrect
Hence P↔P ≡ ¬(P↔¬P), and so on
TFF
FTF
FFT
TTT
QPQP ↔
45/68
“The Laws of Logic”
1
1)
Double negation law:
¬¬P
≡
P
2)
De Morgan’s laws: ¬(P∧Q)
≡
¬P∨¬Q and
 ¬(P∨Q)
≡
¬P∧¬Q
3)
Commutative laws:
P∧Q
≡
Q∧P
and 
P∨Q
≡
Q∨P
4)
Associative laws:
P∧(Q∧R)
≡
(P∧Q)∧R
and
 P∨(Q∨R)
≡
(P∨Q)∨R
5)
Distributive laws:
P∧(Q∨R)
≡
(P∧Q)∨(P∧R)
and
 P∨(Q∧R)
≡
(P∨Q)∧(P∨R)
Augustus De Morgan 
(June 27, 1806 – March 18, 1871)
46/68
“The Laws of Logic”
2
6)
Idempotent laws:
P∧P
≡
P
and 
P∨P
≡
P
7)
Identity laws:
P∨False
≡
P
and 
P∧True
≡
P
8)
Inverse laws:
P∨¬P
≡
True
and 
P∧¬P
≡
False
9)
Domination laws:
P∨True
≡
True
and 
P∧False
≡
False
10)Absorption laws:
P∨(P∧Q)
≡
P
and 
P∧(P∨Q)
≡
P
47/68
Proving Equivalences
Here is how to prove our “Q
∧
(¬R→P)
≡
(R∧Q)∨(P∧Q)”
Q
∧
(¬R→P)
≡
Q∧(¬¬R∨P)
[P→Q
≡
¬P∨Q
rule]
≡
Q∧(R∨P)
[double negation]
≡
(Q∧R)∨(Q∧P)
[distributive law]
≡
(R∧Q)∨(Q∧P)
[commutative law]
≡
(R∧Q)∨(P∧Q)
[commutative law]
48/68
Rules of Inference
a In real life when proving mathematical statements often 
we do not establish an equivalence but a consequence
V Theorems are true/correct mathematical statements
V Axioms are “self-evident” theorems
V Using the rules of inference we can make a (valid) argument to 
derive other theorems from the axioms
V An argument is valid if and only if the validity of the hypotheses 
implies the validity of the conclusion
a Typically, an argument uses hypotheses or premises to
reach a conclusion
a Example:
“Assuming the hypotheses H1, H2, H3
it follows that conclusion C holds”
a How to do this is described by the rules of inference
49/68
Theorem
a Every formula is logically
equivalent to formula in disjunctive normal form
a Example:
(P →
Q ) ∧
(R →
Q)
is
logically equivalent to:
(¬P ∧
¬R ∧
¬Q) ∨
(¬P ∧
¬R ∧
Q) ∨
(¬P ∧
R ∧
Q) ∨
(P ∧
¬R ∧
Q) ∨
(P ∧
R ∧
Q)
50/68
Shape of an Argument
premises or 
hypotheses
conclusion
“therefore” 
symbol
The therefore symbol “∴” is a bit old fashioned
C
H
H
H
3
2
1
∴
51/68
Some Small Arguments
Valid 
Arguments
RQ
RP
QP
P
∧∴
→
→
Q
QP
QP
∴
∨¬
∨
QQ ¬∨∴ Invalid 
Arguments
“inverse 
fallacy”
RP
Q
P
∧∴
Q
P
QP
¬∴
¬
→
52/68
About Arguments
We can check arguments with the help of truth tables
An argument is valid if for all cases where the hypotheses 
are True, the
Conclusion is True as well
Arguments are to conditionals (“→”), what
 Equivalences (“↔”)
are to biconditionals
(“↔”)
Arguments are correct or incorrect / valid or invalid;
 a conditional is True or False
53/68
About Arguments
a For propositions P, Q, 
if P→Q is a tautology, 
then P logically implies Q
This is denoted by “P → Q”
a Arguments are correct or incorrect / valid or invalid;
a conditional is True or False
a Arguments are to conditionals (“→”), 
what Equivalences (“↔”) are to biconditionals (“↔”)
54/68
Checking Arguments
a An argument (H1∧ … ∧Hn) → C is valid if
V for all cases where the hypotheses Hj are True
V the Conclusion C is True as well
aWe can check arguments with the help of truth tables
But just as with equivalences there are other ways of 
proving the validity of an argument
55/68
Rules of Inference I
Modus 
Tollens
P
Q
QP
¬∴
¬
→
Rule of Detachment 
(Modus Ponens)
Q
P
QP
∴
→
nConjunctio
QP
Q
P
∧∴
Syllogism
RP
RQ
QP
→∴
→
→
56/68
Rules of Inference II
Rule of Disjunctive 
Syllogism
Rule of 
Contradiction
Conjunctive 
Simplification
Disjunctive 
Amplification
Q
P
QP
∴
¬
∨
P
QP
∴
∧
QP
P
∨∴P
FalseP
¬∴
→
Mần reng tui lấy ví
dụ
?
1.
Tìm không gian các sự
kiện, 
nhân vật thật
2.
Tìm các phát biểu tương 
ứng với các biến trong luật
3.
Gán nghĩa cho tứng thành 
phần của luật
4.
Nhận kết quả
57/68
Rules of Inference III
Conditional 
Proof
Proof by 
Cases
Constructive 
Dilemma
Destructive 
Dilemma
RP
SQ
SR
QP
¬∨¬∴
¬∨¬
→
→
SQ
RP
SR
QP
∨∴
∨
→
→
r
)RQ(P
QP
∴
→→
∧
R)QP(
RQ
RP
→∨∴
→
→
58/68
Proving Validity of Arguments
Using basic inference steps and equivalence rules one can 
prove the validity of arguments
Example: Yes, according 
to truth tables
But also, And because 
P→¬P ↔ ¬P∨¬P ↔ ¬P 
we have the validity 
proven a second time
Valid?
Syllogism
pp
pq
qp
¬→∴
¬→
→
p
pq
qp
¬∴
¬→
→
59/68
Longer Arguments…
Example:
((¬P∨¬Q)→(R∧S))
∧
(R→T)
∧
(¬T)
→
P
1)
R→T
[Premise]
2)
¬T
[Premise]
3)
¬R
[Steps 1, 2
and Modus Tollens]
4)
¬R∨¬S
[Step 3 and Disjunctive Amplification]
5)
¬(R∧S)
[Step 4 and DeMorgan’s
Law]
6)
(¬P∨¬Q)→(R∧S)
[Premise]
7)
¬(¬P∨¬Q)
[Steps 5, 6
and Modus Tollens]
8)
¬¬P∧¬¬Q
[Step 7 and DeMorgan’s
Law]
9)
P∧Q
[Step 8 and Double Negation]
10)
P
[Step 9 and Conjunctive Simplification]
60/68
General Remarks
a Propositions that only use ∧, ∨, ¬, (, ) are the objects in 
Boolean algebra (without the implication “→”)
V Note: the Laws of Logic do not use “→”
a This is what you typically have in IF … THEN construction
a The implication becomes useful when you want to connect 
Boolean algebra with the rules of inference
a “False → P ↔ True” follows from proof by contradiction
V It holds that (P∧¬P) → P hence (P∧¬P) → P↔ True
V Take the two cases P ↔ True and P↔ False
61/68
Terminology: 4 Conditionals
a For the propositions P and Q and the conditional P → Q, 
we have the three other conditionals:
converse:
Q
→
P
inverse:
¬P
→
¬Q
contrapositive:
¬Q
→
¬P
… the contrapositive, hence: (P→Q) ↔ (¬Q→¬P).
We also have for the other two: (Q→P) ↔ (¬P→¬Q) 
but not: (P→Q) ↔ (Q→P) or (P→Q) ↔ (¬P→¬Q)
O n l y o n
e o f 
t h e s e i s
 e q u i v a l
e n t 
w i t h P → Q
…
63/68
Example of Inferencing
a Consider the following argument:
1.
Today is Tuesday or Wednesday
2.
But it can't be Wednesday, since the doctor's office is open 
today, and that office is always closed on Wednesdays
3.
Therefore today must be Tuesday
a This sequence of reasoning (inferencing) can be 
represented as a series of application of modus ponens to 
the corresponding propositions as follows
Q
P
QP
∴
→
64/68
Example of Inferencing (Cont)
a The modus ponens is an inference rule which deduces 
Q from P -> Q and P
T
Today is Tuesday
W
Today is Wednesday
D
The doctor's office is open today
C
The doctor's office is always closed on Wednesdays
a The above reasoning can be represented by propositions as follows
1. T
V W 
2. D 
C 
------------
 ¬W
 ------------
3. T
Q
P
QP
∴
→
65/68
Example of Inferencing (Cont)
a To see if this conclusion T is correct, let us first find the 
relationship among C, D, and W
C
can be expressed using D
and W
That is, restate C
first as the doctor's office is always closed
 if it is Wednesday
Then C
≡
(W →
¬D)
Thus substituting (W →
¬D)
for C, we can proceed as follows
D
 W →
¬D
 ------------
 ¬W
which is correct by modus tollens
66/68
Example of Inferencing (Cont)
a From this ¬W combined with T V W of 1. above,
¬W
T
V W 
------------
T
which is correct by disjunctive syllogism
Thus we can conclude that the given argument is correct
To save space we also write this process as follows eliminating one of the ¬W's: 
D
W →
¬D
------------
¬W
T
V W 
------------
T
67/68
Limitations of Propositional Logic 1
a Propositional Logic :
V is good for facts, not individuals
But hard to identify individuals (terms)
V E.g., Mary, John, 17, Canada
aWe could try a variable JohnIsTall, but suppose we 
then want to encode a rule that tall people are good 
at basketball
V E.g., TallPeople → GoodAtBasketball
Given a knowledge base that consists of
V JohnIsTall
V TallPeople → GoodAtBasketball
68/68
Limitations of Propositional Logic 2
aCan't directly talk about properties of individuals
or relations between individuals
V E.g., how to represent the fact that John is tall?
aWe have no way to conclude that John is good at 
basketball! 
aGeneralizations, patterns, regularities can't easily be 
represented
V E.g., all triangles have 3 sides