Bài giảng Chương 1 : Đại số mệnh đề

 tắc .................................................................................................. 70 
4.4.5. Phép kéo theo .................................................................................................. 71 
4.5. Logic mờ ................................................................................................................. 72 
4.5.1. Định nghĩa mệnh đề mờ .................................................................................. 72 
4.5.2. Các phép toán trên logic mờ............................................................................ 73 
4.6. Suy diễn mờ (Fuzzy inference)............................................................................... 73 
4.7. Tổng kết chương 4 .................................................................................................. 78 
4.8. Bài tập chương 4..................................................................................................... 79 
Predicates and Quantiers: Suggested Exercises
1. Write each of the following expressions so that negations are only applied to propositional functions
(and not quantiers or connectives).
(a) 
	

	
(b) 


	


	
(c) 
ff

	fifl
	ffi

(d) 
 !ff
"#

" $%"ffi
"
(e)  &
!' "(ff

"!)

"(!*

+"#-,#fi"ffi
"
2. Let 

	 =”  likes  ”, where the universe of discourse for  and  is the set of all people. For each
of the following, translate the expression to English, and tell the truth value.
(a) 
	


	
(b) 


	
(c) 
	

	
(d) 


/.10	2354	
(e) 
	


	
(f) 



	
(g) 

	

	
3. Let 

" =” (68796;:<"#6 ”, where the universe of discourse for all variables is the set of integers.
What are the truth values of each of the following?
(a) 
	
=
"#

"
(b) >
!"=

+"#
(c) 
	"=

+"#
(d) 
	
	"#

"
(e) 
=
"#

"
(f) 	"=

+"#
(g) "#

ff?+@	+"#
(h) 

/A>
(i) 

@=
4. Write each of the following sentences using quantiers and propositional functions (if it is possible).
(a) All disc golfers play ultimate frisbee.
(b) If all students in my class do their homework, then some of the students will pass.
(c) If none of the students in my class study, then all of the students in my class will fail.
(d) Not everybody knows how to throw a frisbee 300 feet.
(e) Some people like ice cream, and some people like cake, but everybody needs to drink water.
(f) Everybody loves somebody.
(g) Everybody is loved by somebody.
(h) Not everybody is loved by everybody.
(i) Nobody is loved by everybody.
(j) You can’t please all of the people all of the time, but you can please some of the people some of
the time.
(k) If only somebody would give me some money, I would buy a new house.
(l) Nobody loves me, everybody hates me, I’m going to eat some worms.
(m) Every rose has it’s thorn, and every night has it’s dawn.
 Rule Tautology 
Rules of Inference 
Disjunctive Syllogism [(p∨q) ∧¬p]→q 
Addition p→(p∨q) 
Simplification (p∧q)→p 
Contrapositive (p→q)→ (¬q→¬p) 
Hypothetical Syllogism [(p→q)∧(q→r)]→(p→r)
Modus Tollens [¬q∧(p→q)]→¬p 
Modus Ponens [p∧(p→q)]→q 
Conjunction ((p)∧(q))→ (p∧q) 
Rules of Inference for Quantifiers 
Universal instantiation ∀x P(x) 
∴ P(c) if c∈U 
Universal generalization P(c) for arbitrary c∈U 
∴ ∀x P(x) 
Existential instantiation ∃x P(x) 
∴ P(c) for some c∈U 
Existential generalization P(c) for some c∈U 
∴ ∃x P(x) 
Equivalence Relations
Denition: A relation

on a set 
 is called an equivalence
relation if it is reexive, symmetric, and transitive. Recall the
denitions:
 reexive:




	


for all



 .
 symmetric:



	


when






, for




 .
 transitive:



	


and





implies






,
for





 .
If two elements are related by an equivalence relation, they
are said to be equivalent.
1
Examples
1. Let

be the relation on the set of English words such
that


if and only if
starts with the same letter as

.
Then

is an equivalence relation.
2. Let

be the relation on the set of all human beings such
that



if and only if

was born in the same country as

. Then

is an equivalence relation.
3. Let

be the relation on the set of all human beings such
that



if and only if

owns the same color car as

.
Then

is an not equivalence relation.
2
Congruence Modulo
Let


 be a positive integer. Then the relation











ff 
fi
is an equivalence relation.
Proof: By denition,



 ff 
if and only if

fl

ffi
, for some integer
ffi
. Using this,we proceed:
 Since

fl






, we have that




ff 
, and

is reexive.
 If



ff 
, then

fl

ffi 
, for some integer
ffi
.
Thus,
fl



fl
ffi


, and we have



ff 
, so

is symmetric.
3
 If



ff 
, and


 ff 
, then we have

fl

ffi 
and
fl

 
, for integers
ffi
and
. Thus,

fl



fl
"
!

fl


ffi 
!
 


ffi
!



and we have



ff 
, and

is transitive.
Therefore, congruence modulo

is an equivalence relation
4
Denition: Let

be an equivalence relation on a set 
 . The
equivalence class of

is
#

$
%









fi'
&
In words,
#

$
%
is the set of all elements that are related to the
element



 . If the relation is clear, we can omit the
subscript (i.e.
#

$
instead of
#

$
%
).
If

#

$
%
, then
is called a representative of the equivalence
class.
5
Examples Continued
1. The equivalence class of Xenon is all words starting with
the letter X. That is,
#
Xenon
$



is an English word starting with the letter X
fi
2. The equivalence class of Chuck Cusack is all people born
in the United States of America. That is,
#
Chuck Cusack
$



  
 is a person that was born in the U.S.A.
fi
6
Example: Congruence Classes Modulo

The congruence class of an integer

modulo

is denoted by
#

$
(
.
Thus,
#*
)
$
+

'
& & &

fl
,

fl
-

)
/
.


)

& & &
fi
#

$
0


& & &

fl

1

fl
.


/
.


1

& & &
fi
#*
2
$4
3

#

$4
3


& & &

fl
,

fl
)



2
/
5

& & &
fi
7
Equivalence Classes and Partitions
Theorem 1: Let

be an equivalence relation on a set 
 . The
following statements are equivalent:
&


- &
#

$

#
$
)
&
#

$7
6
#
$
8

9
Proof: Show that 
:
- , -
:
)
, and
)
:
 .
Notice that this theorem says that if the intersection of two
equivalence classes is not empty, then they are equal. That is,
two equivalence classes are either equal or disjoint.
8
Denition: A partition of a set
;
is a collection of disjoint
nonempty subsets of
;
whose union is
;
. That is, a partition
of
;
is a collections of subsets 

<
,
=

> such that


<
8

9
for
=

> ,


<
6


?

9

when
=
8

@

and
A
<
B
C


<

;
&
( > is an index set. For example, often > 



-

& & &

D
fi
.)
9
Theorem 2: Let

be an equivalence relation on a set
;
.
Then the equivalence classes of

form a partition of
;
.
Conversely, given a partition



<

=

>
fi
of the set
;
, there
is an equivalence relation

that has the sets 

<
,
=

> , as its
equivalence classes.
Proof (informal): The equivalence classes of an equivalence
relation are nonempty (since


#

$
%
), and by Theorem 1 are
disjoint. Since every element of the set
;
is in some
equivalence class (e.g.


#

$
%
), the equivalence classes
partition
;
.
10
(Proof of Theorem 2, continued)
Now, assume we have a partition



<

=

>
fi
of a set
;
.
Dene a relation on
;
by


if and only if





<
for
some
=
. It is not hard to see that this is an equivalence relation
Example: We can partition the set of integers according to
the equivalence classes modulo
2
as follows:
EG
F
H
+J
I
K7
L L L
MO
N
P
F
M
N
Q
M
F
M
Q
M
P
F
M
L L L
R
M
E
P
H
+S
I
K7
L L L
M
N
T
MO
N
U
M
P
MW
V
M
P P
M
L L L
R
M
E7
X
H
+J
I
K7
L L L
M
N
Y
MO
N
Z
M
X
MW
[
M
P X
M
L L L
R
M
E
Z
H
+J
I
K7
L L L
M
N
[
MO
N
X
M
Z
M
Y
M
P
Z
M
L L L
R
M
E
U
H
+\
I
K7
L L L
M
N
V
MO
N
P
M
U
M
T
M
P U
M
L L L
R7
L
11
Example: Let

be the equivalence relation on the set of
English words dened by


if and only if
starts with the
same letter as

. Then we can partition the set of English
words as follows:
#

$




 D]

 D


 
 ^

& & &
fi

#

_ ^ `
$



 ^


 =
a


_ ^ `


_ bc D

& & &
fi

&
&
&
#e
d =
f
$


d ^ 
_ 

d ^`

d =
f 
d b b

& & &
fi
&
12
 Logical Equivalences 
Name Equivalence 
 p∧q ⇔ q∧p
Commutative laws p∨q ⇔ q∨p
 p∧F ⇔ F 
Domination laws p∨T ⇔ T 
 p∨F ⇔ p 
Identity laws p∧T ⇔ p 
 p∧p ⇔p 
Idempotent laws p∨p ⇔ p 
Double negation law ¬(¬p) ⇔p 
(Unofficial name) p∧¬p ⇔ F 
Cancellation laws p∨¬p ⇔ T 
 (p∧q)∧r ⇔ p∧(q∧r)
Associative laws (p∨q)∨r ⇔ p∨(q∨r)
 p∧(q∨r) ⇔ (p∧q)∨(p∧r)
Distributive laws p∨(q∧r) ⇔ (p∨q)∧(p∨r)
 ¬(p∨q) ⇔ ¬p∧¬q 
De Morgan’s laws ¬(p∧q) ⇔ ¬p∨¬q 
Implication law (p→q) ⇔ (¬p∨q)