5/10/2013
1
Môn học: TOÁN RỜIRẠC
Môn

học:

TOÁN

RỜI

RẠC
Số Tiết LT: 45
Gv: Huỳnh Thị Thu Thủy
Tài liệu tham khảo
1. Toán rời rạc ứng dụng trong tin học -
Kenneth H. Rosen
2. Đại số quan hệ - Nguyễn Thanh Sơn
Gv:HuỳnhThịThuThủy2
Nội dung
1. Chương 1: CƠ SỞ LOGICCƠ SỞ LOGIC
2. Chương 2: PHÉP ĐẾMPHÉP ĐẾM
3. Chương 3
: QUAN HỆQUAN HỆ
4. Chương 4
: ĐẠI SỐ BOOLE ĐẠI SỐ BOOLE ––
HÀM BOOLEHÀM BOOLE
Gv:HuỳnhThịThuThủy3
HÀM

BOOLEHÀM

chính xác của các mệnh đề.
• Ứng dụng các qui tắc logic trong tin học:
–
Thiết kế mạn
g
má
y
tính
Gv:HuỳnhThịThuThủy6
gy
–Xây dựng chương trình máy tính
–Kiểm tra tính đúng đắn của chương trình
2- Mệnh đề
• Là câu đúng hoặc sai, không thể vừa
đú ừ i
đú
ng, v
ừ
a sa
i
• Ví dụ:
–Mặt trời mọc ở phương Đông
– 1+2 = 3
–
2+2 = 5
Gv:HuỳnhThịThuThủy7
–
2+2

=

g
hợp còn lại
Gv:HuỳnhThịThuThủy10
ýg g
2- Mệnh đề(tt)
•Bảng chân trị cho các toán tử logic:
pq
pp qpqpqpqpq
TT
T
F
Gv:HuỳnhThịThuThủy11
T
F
FT
FF
2- Mệnh đề(tt)
•Dịch câu thông thường thành biểu thức logic
ế
•
V
í dụ: “Bạn không được lái xe máy n
ế
u bạn
cao dưới 1,5m trừ khi bạn trên 18 tuổi”.
•p: “Bạn được lái xe máy”
•r: “Bạn cao dưới 1,5m”
ổ
Gv:HuỳnhThịThuThủy12
•s: “Bạn trên 18 tu

a
)
Nhi
ệ
t đ
ộ
dưới 0 và tu
y
ết rơi
Gv:HuỳnhThịThuThủy14
)
ệ ộ y
b) Có tuyết rơi hoặc nhiệt độ dưới 0 hoặc cả 2
c) Nếu nhiệt độ dưới 0 thì cũng có tuyết rơi
Bài tập mệnh đề
2. Cho p, q và r là những mệnh đề:
ố
p: Bạn bị cúm ; q: Bạn bị trượt kỳ thi cu
ố
i khoá
r: Bạn được lên lớp
Hãy diễn đạt những mệnh đề sau thành câu
thông thường:
a
)
p

q
Gv:HuỳnhThịThuThủy15
)

a)
p



p
b) p p
c) p q
d) (p q) q
e) (p  q)  (p  q)
Gv:HuỳnhThịThuThủy17
f) (p  q)  (q p)
g) p  q  r
h) (p  q)  (p q)
Bài tập mệnh đề
5. Tìm các OR bit, AND bit, XOR bit của
các cặp xâu bit sau:
a) 1011110 ; 0100001
b) 11110000 ; 10101010
c) 0001110001 ; 1001001000
d) 1111111111 ; 0000000000
6.
Xác định các biểuthức sau:
Gv:HuỳnhThịThuThủy18
6.
Xác

định

các


đề

là

tương

đương

logic:
–Bảng giá trị chân lý
– Dùng các tương đương logic
5/10/2013
6
3- Các qui tắc suy diễn(tt)
CÁC TƯƠNG ĐƯƠNG LOGIC
Tương đương Tên gọi
p
T

L ật đồng nhất
p

T

p
p  F  p
L
u
ật

q)

(p

r)
Luật phân phối
Gv:HuỳnhThịThuThủy22
p


(q


r)

(p


q)


(p


r)
 (p  q) pq
 (p  q) pq
Luật De Morgan
3- Các qui tắc suy diễn(tt)
• Một số tương đương tiện ích:

7
Bài tập các qui tắc suy diễn
2. CM các mệnh đề kéo theo sau là hằng
đú
đú
ng:
a) (p  q ) p
b) p  (p  q)
c)  p  (p  q)
d)
(p

q)

(

p

q)
Gv:HuỳnhThịThuThủy25
d)
(p


q)


(

p

có

là

hằng

đúng

không:
( p  (p  q)) q
4- Vị từ -Lượng từ
• Vị từ:
– Là hàm nhận giá trị đúng hoặc sai tùy thuộc
hàm tác dụng vào cá thể nào.
– VD: VN(x): “x là người Việt nam”.
–
Boolean
Gv:HuỳnhThịThuThủy27
–
Boolean
4- Vị từ -Lượng từ (tt)
• Lượng từ:
–Lượng từ “với mọi” của P(x) là mệnh đề P(x)
đúng với mọi giá trị của x trong không gian”.
–Kí hiệu: x P(x)
–VD: “Tất cả sinh viên ở lớp này đều đã học
Gv:HuỳnhThịThuThủy28
giải tích”.
• P(x) kí hiệu cho câu: “x đã học giải tích”.
•Khi đó: x P(x)

y
l
à

bạ
n
tốt
nh
ất

của
x”.
Gv:HuỳnhThịThuThủy30
G ả
(,y) yàbạ tốt ấtcủa
 x y z [ B(x,y)  (z ≠ y) B(x,z) ]
4- Vị từ -Lượng từ (tt)
• VD2:
“
Tấtcả sư tử đều hung dữ
”
–
Tất

cả

sư

tử


nạp
:

CM

phép

kéo

theo:
P(n)  P(n+1) đúng với mọi số nguyên dương n.
Với P(n) là giả thiết quy nạp.
5/10/2013
9
5- Nguyên lý quy nạp (tt)
•VD: Bằng quy nạp toán học, hãy CM:
1. “Tổng n số nguyên dương lẻ đầu tiên là n
2
”.
2. “n < 2
n
với mọi số nguyên dương n”.
3. “n
3
–n chia hết cho 3 n nguyên dương”.
4
“1+2+2
2
++2
n

6. “2
n
< n!, n nguyên n  4”.
TỔNG KẾT CHƯƠNG 1
1. Giới thiệu.
2. Mệnh đề.
3. Các quy tắc suy diễn.
4
Vị từ
-
lượng từ
Gv:HuỳnhThịThuThủy34
4
.
Vị

từ

-
lượng

từ
.
5. Nguyên lý quy nạp.
Chương 2: PHÉP ĐẾMPHÉP ĐẾM
Gv:HuỳnhThịThuThủy35
NỘI DUNG
1. Lý thuyết tập hợp và ánh xạ
2. Phép đếm.
3. Giải tích tổ hợp.

•Một cách khác để mô tả các tập hợp:
–Chỉ rõ các thuộc tính đặc trưng của các phần
tử thuộc tập hợp đó.
– Ví dụ
:
TậpOcủatấtcả các số nguyên dương lẻ và nhỏ
Gv:HuỳnhThịThuThủy39
•
Tập

O

của

tất

cả

các

số

nguyên

dương

lẻ

và


chỉ

nếu mỗi phần tử của A đều là 1 phần tử của
B.
–Kí hiệu: A  B
– Ví dụ:
A{/ là ố êd }
Gv:HuỳnhThịThuThủy40
A
=
{
x
/
x
là
s
ố
nguy
ê
n
d
ương
}
B={x/ x là số nguyên tố không vượt quá 100
A ? B
5/10/2013
11
1- Lý thuyết tập hợp và ánh xạ(tt)
• Định nghĩa 4:
ế

: Tập hợp các số nguyên dương là tập
vô hạn.
Gv:HuỳnhThịThuThủy42
1- Lý thuyết tập hợp và ánh xạ(tt)
• Định nghĩa 6:
ấ
–
Cho tập S, tập lũy thừa của S là tập của t
ấ
t cả
các tập con của S.
–Tập lũy thừa của S được kí hiệu: P(S)
– Ví dụ
:
•Xác định tập lũy thừa của tập {0,1,2}.
Gv:HuỳnhThịThuThủy43
• P({0,1,2}) = {,{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2}}
• Cho S={a,b,c}
• Tìm P(S)=?
1- Lý thuyết tập hợp và ánh xạ(tt)
• Định nghĩa 7:
ề
–
Cho A và B là hai tập hợp. Tích đ
ề
các của A
và B là tập hợp của tất cả các cặp (a,b) với
aA và bB.
–Kí hiệu: A x B
– Ví dụ

i
A
i
(i=1,2, ,n)
– Kí hiệu:
A
1
x A
2
x x A
n
={(a
1
, a
2
, ,a
n
)| a
i
A
i
(i=1,2, ,n)}
Gv:HuỳnhThịThuThủy45
Bài tập
1. Liệt kê các phần tử của tập hợp sau:
ố
o
S
1
={x| x là s

o
S={a a
bb
}
o
S={a
,
a
1
,
b
,
b
1
}
o S={a,{a,b},a,{a,b}}
o S={a,{a},{{a}},{a,b}}
Gv:HuỳnhThịThuThủy47
2- Phép đếm
• Quy tắc cộng: Giả sử có 2 công việc.
– Công việc thứ 1 có thể làm bằng n
1
cách
– Công việc thứ 2 có thể làm bằng n
2
cách
–Và nếu 2 việc này không thể làm đồng thời
Gv:HuỳnhThịThuThủy48
–
Khi đó sẽ có n

c
ô
ng v
iệ
c
)
:
–Giả sử các việc T
1
, T
2
, ,T
m
có thể làm tương
ứng bằng n
1
, n
2
, ,n
m
cách và giả sử không
có 2 công việc nào có thể làm đồng thời.
–Khi đó số cách làm 1 trong m công việc đó là
Gv:HuỳnhThịThuThủy50
n
1
+ n
2
+ + n
m

cách.
–Việc thứ 2 có thể làm bằng n
2
cách sau khi
việc thứ 1 đã được làm.
–Khi đó sẽ có n
1
.n
2
cách thực hiện nhiệm vụ
Gv:HuỳnhThịThuThủy52
này.
5/10/2013
14
2- Phép đếm (tt)
• Ví dụ 1:
ể ế
–
Người ta có th
ể
ghi nhãn cho những chi
ế
c
ghế trong 1 giảng đường bằng 1 chữ cái và 1
số nguyên dương không vượt quá 100
–Hỏi nhiều nhất có bao nhiêu chiếc ghế được
ghi nhãn khác nhau.
Gv:HuỳnhThịThuThủy53
2- Phép đếm (tt)
• Ví dụ 2:

biể
n c
hứ
a m
ột

dãy 2 chữ cái tiếp sau là 3 chữ số (không
bỏ dãy chữ nào cả)?
Gv:HuỳnhThịThuThủy56
5/10/2013
15
2- Phép đếm (tt)
• Quy tắc nhân mở rộng: Giả sử 1 nhiệm
à đó đ thi hà h bằ áhth
vụ n
à
o
đó

đ
ược
thi

hà
n
h

bằ
ng c
á

cách thi hành các
Gv:HuỳnhThịThuThủy57
nhiệm vụ đã cho.
2- Phép đếm (tt)
• Nguyên lý bù trừ:
ể ồ
–
Khi 2 công việc (CV) có th
ể
được làm đ
ồ
ng
thời. Ta không thể dùng quy tắc cộng để tính
số cách thực hiện nhiệm vụ gồm cả 2 việc.
– Số cách thực hiện nhiệm vụ: Cộng số cách
làm mỗi 1 trong 2 CV trừ đi số cách làm đồng
thời ả 2CV

Nêlýbùtừ
Gv:HuỳnhThịThuThủy58
thời
c
ả

2

CV


N

hỏi
c
ó

4
p
h
ương
á
n
trả lời.
a) Có bao nhiêu cách điền 1 phiếu trắc nghiệm
nếu mọi câu hỏi đều được trả lời?
b) Có bao nhiêu cách điền 1 phiếu trắc nghiệm
Gv:HuỳnhThịThuThủy60
nếu có thể bỏ trống?
5/10/2013
16
Bài tập
2. Từ NewYork đến Denver có 6 hãng hàng
khô à ó 7 hã b từ D đế
khô
ng v
à
c
ó

7

hã

viết

tắt

bằng 3 chữ cái khác nhau?( CÁC chữ
cái có thể lặp lại)
Bài tập
4. Có bao nhiêu người có tên họ viết tắt
bằ 3hữ ái khá h t đó
bằ
ng
3
c
hữ
c
ái

khá
c n
h
au
t
rong
đó

không chữ cái nào được lặp lại?
5. Có bao nhiêu xâu nhị phân có độ dài
bằng 16, có bít đầu tiên và bít cuối cùng
là 1?
Gv:HuỳnhThịThuThủy62

có

bao

nhiêu

số:
a) Lẻ?
b) Có 3 chữ số như nhau?
Bài tập
10.Có bao nhiêu xâu gồm 3 chữ số thập
phân:
phân:
a) Không chứa cùng 1 chữ số 3 lần?
b) Bắt đầu bằng chữ số lẻ?
c) Có đúng 2 chữ số 4?
11.Có bao nhiêu xâu gồm 4 chữ số thập
hâ
Gv:HuỳnhThịThuThủy64
p
hâ
n:
a) Không chứa cùng 1 chữ số 2 lần?
b) Kết thúc bằng chữ số chẵn(0?)?
5/10/2013
17
3- Giải tích tổ hợp
• Hoán vị:
ố
–

–
Cách sắ
p
xế
p
3,2 là 1 chỉnh h
ợp
ch
ập
2 của
Gv:HuỳnhThịThuThủy66
p p ợp ập
S.
3- Giải tích tổ hợp (tt)
• Định lý 1:
ố ầ
–
S
ố
chỉnh hợp chập r của tập S có n ph
ầ
n tử là:
– Đặc biệt:
)!(
!
),(
rn
n
rnP


c thi đều có th
ể
xả
y
ra?
Gv:HuỳnhThịThuThủy69
ụ ộ y
3- Giải tích tổ hợp (tt)
• Ví dụ 3:Giả sử một thương nhân định đi bán
hà t i8thà h hố
hà
ng
t
ạ
i

8

thà
n
h
p
hố
.
– Anh ta bắt đầu cuộc hành trình của mình tại 1
thành phố nào đó nhưng có thể đến 7 thành phố
kia theo bất kỳ thứ tự nào mà anh ta muốn.
– Hỏi, anh ta có thể đi qua tất cả các thành phố
Gv:HuỳnhThịThuThủy70
này theo bao nhiêu lộ trình khác nhau?

• Hệ quả 1:
– Cho n và r là các số nguyên không âm sao
cho r ≤ n. Khi đó:
C(n, r) = C(n, n-r)
Gv:HuỳnhThịThuThủy74
3- Giải tích tổ hợp (tt)
• Ví dụ:
ể ố ầ
–
Có bao nhiêu cách tuy
ể
n 5 trong s
ố
10 c
ầ
u
thủ của 1 đội bóng quần vợt để đi thi đấu tại
một trường khác?
Gv:HuỳnhThịThuThủy75
Bài tập giải tích tổ hợp
1. Có bao nhiêu thứ tự có thể xảy ra trong
cuộcthichạygiữa5vận động viên
cuộc

thi

chạy

giữa


4- Nguyên lý Dirichlet
• Định lý 1( Nguyên lý lồng chim bồ câu):
–Nếu có K+1 hoặc nhiều hơn đồ vật được đặt
trong K hộp thì có ít nhất 1 hộp chứa 2 hoặc
nhiều hơn 2 đồ vật.
Gv:HuỳnhThịThuThủy77
4- Nguyên lý Dirichlet (tt)
• Ví dụ 1:
ấ
–
Một nhóm b
ấ
t kỳ có 367 người.
–Chắc chắn có ít nhất 2 người trùng ngày sinh.
–Vì?
Gv:HuỳnhThịThuThủy78
4- Nguyên lý Dirichlet (tt)
• Ví dụ 2:
ấ ế
–
Cho 1 nhóm b
ấ
t kỳ có 27 từ ti
ế
ng Anh.
–Chắc chắn có ít nhất 2 từ bắt đầu bằng
cùng 1 chữ cái.
– Vì?
Gv:HuỳnhThịThuThủy79
4- Nguyên lý Dirichlet (tt)


sinh viên cùng điểm thi?
5/10/2013
21
4- Nguyên lý Dirichlet (tt)
• Định lý 2 (Nguyên lý Dirichlet tổng quát):
–Nếu có N đồ vật được đặt vào trong K hộp,
sẽ tồn tại một hộp chứa ít nhất vật.






K
N
Gv:HuỳnhThịThuThủy81
4- Nguyên lý Dirichlet (tt)
• Ví dụ1:
ấ


–
Trong 100 người sẽ có ít nh
ấ
t

100/12

= 9

Số
m
ã
v
ù
ng c
ầ
n
thiết
n
hỏ
n
hất
p
hải

là

bao nhiêu để đảm bảo 25 triệu máy điện
thoại trong 1 bang có số điện thoại khác
nhau.
–
Mỗisố gồm10chữ số.(Giả sử số điện
Gv:HuỳnhThịThuThủy84
Mỗi

số

gồm



chứa

1

tá

chiếc

tất

màu

nâu và 1 tá chiếc tất màu đen. Một người
lấy các chiếc tất một cách ngẫu nhiên
trong bóng tối. Anh ta cần phải lấy ra bao
ế ấ ể ắ ắ ằ
Gv:HuỳnhThịThuThủy85
nhiêu chi
ế
c t
ấ
t đ
ể
ch
ắ
c ch
ắ
n r
ằ


bảo

có

ít

nhất

100

người

cùng bang?
Bài tập nguyên lý Dirichlet
3. Một công ty giữ hàng hoá trong kho. Số các
ở ố
ngăn chứa trong kho được xác định b
ở
i s
ố

gian hàng, số ô trong mỗi gian và số các
giá ở mỗi ô.
Biết nhà kho có 50 gian, mỗi gian có 80 ô, mỗi
Gv:HuỳnhThịThuThủy87
ô có 5 giá. Hỏi hàng hoá phải tối thiểu bằng
bao nhiêu để ít nhất có 2 sản phẩm được
đặt trong cùng 1 ngăn?
TỔNG KẾT CHƯƠNG 2

kết nối giữa các phần tử trong cùng 1 tập
hợp
Gv:HuỳnhThịThuThủy91
hợp
.
2- Quan hệ hai ngôi
• Định nghĩa
– Cho A và B là các tập hợp. Một quan hệ 2
ngôi từ A đến B là một tập con của A x B.
• Kí hiệu: R  A x B
–Phần tử (x,y) của quan hệ R có thể được biểu
Gv:HuỳnhThịThuThủy92
diễn: (x,y)  R, hay xRy
5/10/2013
24
2- Quan hệ hai ngôi (tt)
• Ví dụ:
– Cho S={PhạmThái, CaoBáNhạ, PhạmThiênThư,
NguyễnDu}
– T= {ĐoạnTrườngVôThanh, TựTìnhKhúc,
SơKínhTânTrang, ChiếnTụngTâyHồPhú,
ChinhPhụNgâm}
–
R=
{
(
Ph
ạ
mThái, Sơkínhtântran
g)

–Ví dụ: R = { (1,1),(1,2),(2,1) }
3- Các tính chất của quan hệ (tt)
• Tính bắc cầu (tính chất truyền)-transitive:
–Một quan hệ R trên tập A được gọi là có tính
chất bắc cầu nếu (a,b)  R và (b,c)  R thì
(a,c)  R với a,b,c  A.
–Ví dụ:
Gv:HuỳnhThịThuThủy96
• R1= {(1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4)}
• R2={(1,1),(1,2),(2,1)}
• R3={(2,1),(3,1),(3,2),(4,1),(4,2),(4,3)}
Quanhệnàocótínhbắccầu?
5/10/2013
25
4- Quan hệ tương đương
• Quan hệ R của SxS còn được gọi là quan
hệ cấp 2.
• Quan hệ cấp hai R là quan hệ tương
đương nếu có các tính chất:
–
Phản x
ạ
Gv:HuỳnhThịThuThủy97
ạ
– Đối xứng
–Bắc cầu
4- Quan hệ tương đương(tt)
• Ví dụ:
– Cho tập X={a,b,c,d,e}
– Quan hệ R trên tập X:

–
Dễ dàn
g
ki
ể
m tra
q
uan h
ệ
R là
q
uan h
ệ
thứ
Gv:HuỳnhThịThuThủy 100
g q ệ q ệ
tự.