Sách Cấu Trúc Rời Rạc | Trường Đại Học Công Nghệ Thông Tin, ĐHQG-TPHCM

Định nghĩa. Mệnh đề là các khẳng định có giá trị chân lý xác định (đúng hoặc sai, nhưng không thể vừa đúng, vừa sai). Các mệnh đề đúng được nói là có chân trị đúng, các mệnh đề sai được nói là có chân trị sai. Tài liệu giúp bạn tham khảo, củng cố kiến thức và ôn tập đạt kết quả cao

Môn:
Thông tin:
51 trang 4 tháng trước

Bình luận

Vui lòng đăng nhập hoặc đăng ký để gửi bình luận.

Sách Cấu Trúc Rời Rạc | Trường Đại Học Công Nghệ Thông Tin, ĐHQG-TPHCM

Định nghĩa. Mệnh đề là các khẳng định có giá trị chân lý xác định (đúng hoặc sai, nhưng không thể vừa đúng, vừa sai). Các mệnh đề đúng được nói là có chân trị đúng, các mệnh đề sai được nói là có chân trị sai. Tài liệu giúp bạn tham khảo, củng cố kiến thức và ôn tập đạt kết quả cao

61 31 lượt tải Tải xuống
TRƯỜNG ĐẠI HỌC SƯ PHẠM TP.HCM
KHOA TOÁN – TIN HỌC
TÓM TT BÀI GIẢNG
Môn
TOÁN RI RC
Giảng viên biên soạn: Nguyễn Ngọc Trung
TP.HCM 9.2006
MỤC LỤC
&KѭѫQJ0ӋQKÿӅ........................................................................................ 3
1.1 MӋQKÿӅ- Tính chҩW.......................................................................... 3
1.1.1 MӋQKÿӅYà các phép toán mӋQKÿӅ............................................ 3
1.1.2 DҥQJPӋQKÿӅ ............................................................................ 5
1.1.3 Các quy tҳFVX\GLӉQ .................................................................. 7
1.2 VӏWӯ- /ѭӧQJWӯ.............................................................................. 11
1.3 Nguyên lý quy nҥS.......................................................................... 14
&KѭѫQJ3KpSÿӃP.................................................................................... 15
2.1 TұSKӧS Tính chҩW........................................................................ 15
2.2 Ánh xҥ ............................................................................................ 17
2.3 GiҧLWtFKWәKӧS ............................................................................... 18
2.3.1 Các nguyên lý cѫEҧQFӫDSKpSÿӃP ....................................... 18
2.3.2 GiҧLWtFKWәKӧS ........................................................................ 19
2.3.3 Nguyên lý Dirichlet. (nguyên lý chuӗQJEӗFkX...................... 23
&KѭѫQJ4XDQKӋ ...................................................................................... 24
3.1 Quan hӋ .......................................................................................... 24
3.2 Quan hӋWѭѫQJÿѭѫQJ ..................................................................... 25
3.3 Quan hӋWKӭWӵ- BiӇXÿӗ+DVVH ...................................................... 26
&KѭѫQJĈҥLVӕ%RROH ............................................................................... 30
4.1 ĈҥLVӕ%RROHĈӏQKQJKƭD Tính chҩW ............................................. 30
4.2 Hàm Boole – DҥQJQӕLUӡLFKtQKWҳF............................................... 36
4.3 Bài toán mҥFKÿLӋQ MҥQJFiFFәQJ.............................................. 42
4.4 Tìm công thӭFÿDWKӭFWӕLWLӇX 3KѭѫQJSKiS.DUQDXJK ............... 44
TÀI LIỆU THAM KHẢO.......................................................................... 51
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Trang 3
1 Chương 1. Mệnh đề
1.1 Mệnh đề - Tính chất
1.1.1 Mệnh đề và các phép toán mệnh đề
Định nghĩa. MӋQKÿӅOà các khҷQJÿӏQKFyJLiWUӏFKkQOê[iFÿӏQKÿ~QJKRһFVDL
QKѭQJ NK{QJWKӇ YӯD ÿ~QJYӯDVDL &iFPӋQKÿӅÿ~QJÿѭӧFQyL Oà chân tr
đúng, các mӋQKÿӅVDLÿѭӧFQyLOà có chân trị sai.
Ví d: - Các khҷQJÿӏQKVDXOà mӋQKÿӅ
. “1 + 2 = 5” là mӋQKÿӅVDL
. “10 là sӕFKҹQ´Oà mӋQKÿӅÿ~QJ
- Các khҷQJÿӏQKVDXNK{QJSKҧLOà mӋQKÿӅ
³7{LÿLKӑF´
. “n là sӕQJX\ên tӕ´
hiệu: 7DWKѭӡQJNêKLӋXFiFPӋQKÿӅEҵQJFiFFKӳFiLLQKRD345«Yà
chân trӏÿ~QJVDLÿѭӧFNêKLӋXEӣL
Các phép toán mệnh đề:
Phép phủ định: phӫÿӏQKFӫDPӋQKÿӅ3ÿѭӧFêKLӋXEӣL
P
ÿӑFOà “không
P” hoһF³SKӫÿӏQKFӫD3´&KkQWUӏFӫD
P
là 0 nӃXFKkQWUӏFӫD3Oà mӝWYà
QJѭӧFOҥL
VD. P = “3 là sӕQJX\ên tӕ´ là mӋQKÿӅÿ~QJ. 'RÿyPӋQKÿӅ
P
= “3 không
là sӕQJX\ên tӕOà mӋQKÿӅVDL
BҧQJVDXJӑLOà bҧQJFKkQWUӏFӫDSKpSSKӫÿӏQK
P
P
0
1
1 0
Phép nối liền: MӋQKÿӅQӕLOLӃQFӫDKDLPӋQKÿӅ3Yj4ÿѭӧFNêKLӋXEӣL
P Q
ÿӑFOà “P Q”. Chân trӏFӫD
P Q
1 nӃXFҧ3OүQ4ÿӅXFyFKkQ
trӏOjWURQJFiFWUѭӡQJKӧSNKiF
P Q
có chân trӏOà 0.
VD. P = “Hôm nay trӡLÿҽS´Yà Q = “TrұQEyQJÿiKҩSGүQ´.KLÿyWDFy
mӋQKÿӅQӕLOLӅQFӫD3Yà Q là:
P Q
= “Hôm nay trӡLÿҽSYà trұQEyQJÿi
hҩSGүQ´0ӋQKÿӅQӕLOLӅQQày sӁÿ~QJQӃXQKѭFҧKDLPӋQKÿӅ3Yj4ÿӅX
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Trang 4
ÿ~QJ1JѭӧFOҥLQӃu có mӝWWURQJKDLPӋQKÿӅWUên sai hoһFFҧKDLFùng sai thì
mӋQKÿӅQӗLOLӅQVӁOà sai.
BҧQJFKkQWUӏFӫDSKpSQӕLOLӅQ
P Q
P Q
0 0 0
0 1 0
1
0
0
1 1 1
Phép nối rời: MӋQKÿӅQӕLUӡLFӫDKDL PӋQKÿӅ3Yj4ÿѭӧFNêKLӋXi
P Q
ÿӑFOà “P hay Q”. Chân trӏFӫD
P Q
0 nӃXFҧ3OүQ4ÿӅXFyFKkQ
trӏOjWURQJFiFWUѭӡQJKӧSNKiF
P Q
có chân trӏOà 0.
VD. P = “An là ca sƭ´3 ³$QOjJLiRYLrQ´.KLÿyta có mӋQKÿӅQӕLUӡLFӫD
P Q
P Q
= “An ca sƭKD\$QOà giáo viên”. MӋQKÿӅQӕLOLӅQQày sӁ
ÿ~QJQӃXQKѭPӝWWURQJKDLPӋQKÿӅWUrQOjÿ~QJKRһFFҧKDLPӋQKÿӅWUên
ÿӅXÿ~QJ1ӃXFҧKDLPӋQKÿӅ3Yj4ÿӅXVDLWKì
P Q
sӁVDL
BҧQJFKkQWUӏFӫDSKpSQӕLUӡL
P Q
P Q
0 0 0
0 1 1
1 0 1
1 1 1
Phép kéo theo: MӋQKÿӅ3NpRWKHR4ÿѭӧFNêKLӋXOà
P Q
ĈӇ[iFÿӏQK
chân trӏFӫDPӋQKÿӅ3NpRWKHR4WD[pWdөVDX3³An trúng sӕ”, Q =
³$QPXD[HPi\´NKLÿyPӋQKÿӅ3NpSWKHR4VӁOà Nếu An trúng sӕthì
An sӁPXD[HPi\´7DFyFiFWUѭӡQJKӧSVDXÿk\
$Qÿã trúng sӕYà anh ta mua xe máy: hiӇQQKLên mӋQKÿӅ
P Q
ÿ~QJ
$Q ÿã trúng sӕ QKѭQJ DQK WD NK{QJ PXD [H Pi\ Uõ ràng mӋQK ÿӅ
P Q
là sai.
An không trúng sӕQKѭQJDQKWDYүQPXD[HPi\PӋQKÿӅ
P Q
vүQ
ÿ~QJ
An không trúng sӕYà anh ta không mua xe máy: mӋQKÿӅ
P Q
ÿ~QJ
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Trang 5
BҧQJFKkQWUӏFӫDSKpSNpRWKHR
P Q
P Q
0 0 1
0 1 1
1 0 0
1 1 1
Phép kéo theo hai chiều: MӋQKÿӅ3NpRWKHR4YjQJѭӧFOҥLÿѭӧFNêKLӋX
bӣL
P Q
mӋQKÿӅFyFKkQWUӏÿ~QJNKL3Yà Q chân trӏJLӕQJQKDX
FQJ ÿ~QJ KRһFFùng sai) chân trӏ VDL NKL 3 Yà Q chân trӏNKiF
nhau.
VD. P = “An hӑFJLӓL´4³$QÿѭӧFÿLӇPFDR´.KLÿyPӋQKÿӅ
P Q
=
“NӃX$QKӑFJLӓLWKì An sӁÿѭӧFÿLӇPFDRYjQJѭӧFOҥL´
BҧQg chân trӏFӫDSKpSNpRWKHRKDLFKLӅXQKѭVDX
P Q
P Q
0 0 1
0 1 0
1 0 0
1
1
1
1.1.2 Dạng mệnh đề
Định nghĩa. Dạng mệnh đề ÿѭӧF[k\GӵQJWӯ
- Các mӋQKÿӅOà các hҵQJPӋQKÿӅ
- Các biӃQPӋQKÿӅSTU«FyWKӇOҩ\JLiWUӏOà các mӋQKÿӅQjRÿy
- Các phép toán trên mӋQKÿӅ, và các dҩXQJRһF.
dụ.
( , , )
E p q r p q r p
mӝW GҥQJ PӋQK ÿӅ WURQJ ÿy S T U Oà các
biӃQPӋQKÿӅ
ĈӇêUҵQJWDFyWKӇ[k\GӵQJQKLӅXGҥQJPӋQKÿӅSKӭFWҥSWӯFiFGҥQJPӋQKÿӅ
ÿѫQ JLҧQ KѫQ EҵQJ Fich sӱ GөQJ FiF SKpS WRiQ PӋQK ÿӅ ÿӇ NӃW KӧS FK~QJ OҥL
ChҷQJ KҥQ QKѭ GҥQJ PӋQK ÿӅ (STUӣ WUrQ ÿѭӧF NӃWQӕL Wӯ KDL GҥQJ PӋQKÿӅ
1
( , , )
E p q r p q
2
( , , )
E p q r r p
bҵQJSKpSWRiQQӕLUӡL
).
MӛLGҥQJPӋQKÿӅVӁÿѭӧFVӁFyPӝWEҧQJFKkQWUӏ[iFÿӏQKWURQJÿyPӛLGòng cho
biӃWFKkQWUӏFӫDGҥQJPӋQKÿӅÿyWKHRFiFFKkQWUӏFөWKӇFӫDFiFELӃQ
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Trang 6
Ví dụ.
( , , )
E p q r p q r p
có bҧQJFKkQWUӏQKѭVDX
p q r
r
p q
r p
E(p,q,r)
0
0
0
1
0
0
0
0 0 1 0 0 1 1
0
1
0
1
1
0
1
0 1 1 0 1 1 1
1
0
0
1
1
1
1
1 0 1 0 1 1 1
1 1 0 1 1 1 1
1 1 1 0 1 1 1
Định nghĩa. Hai dҥQJPӋQKÿӅ(Yj)ÿѭӧFQyLOà tương đương logic nӃXFK~QJFy
cùng bҧQg chân trӏ.KLҩ\WDYLӃW
E F
.
Chú ý rҵQJnӃX(Yj)WѭѫQJÿѭѫQJORJLFWKì dҥQJPӋQKÿӅ
P Q
luôn lҩ\JLiWUӏ
là 1 dù các biӃQFyOҩ\EҩWFӭJLiWUӏQào.
Định nghĩa.
i. MӝWGҥQJPӋQKÿӅÿѭӧFJӑLOà mӝWKҵQJÿ~QJQӃXQyOX{QOX{QOҩ\FKkQWUӏ
1
ii. MӝWGҥQJPӋQKÿӅÿѭӧFJӑLOà mӝWKҵQJVDLQӃXQyOX{QOҩ\FKkQWUӏ
Mệnh đề. Hai dҥQg mӋQKÿӅ(Yj)WѭѫQJÿѭѫQJORJLFNKLYjFKӍNKL
P Q
là mӝW
hҵQJÿ~QJ
Định nghĩa. DҥQJPӋQKÿӅ)ÿѭӧFQyL hӋTXҧORJLFFӫD GҥQJPӋQKÿӅ( QӃX
E F
là mӝWKҵQJÿ~QJ Khi ҩ\WDYLӃW
E F
.
Các quy luật logic:
Định lý. VӟLSTUOà các biӃQPӋQKÿӅOà hҵQJÿ~QJOà hҵQJVDLWDFyFiF
WѭѫQJÿѭѫQJORJLF
i. Phủ định của phủ định:
p p

ii. Quy tắc De Morgan:
p q p q
p q p q
iii. Luật kéo theo:
p q p q
iv. Luật giao hoán:
p q q p
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Trang 7
p q q p
v. Luật phân phối:
p q r p q p r
p q r p q p r
vi. Luật kết hợp:
p q r p q r
p q r p q r
vii. Luật lũy đẳng:
p p p
p p p
viii. Luật trung hòa:
1
p p
0
p p
ix. Phần tử bù:
0
p p
1
p p
x. Luật thống trị:
0 0
p
1 1
p
xi. Luật hấp thụ:
p p q p
p p q p
Ví dụ. sӱGөQJFiFTX\OXұWORJLFFKӭQJPLQKUҵQJGҥQJPӋQKÿӅ
( , )
E p q p p q q
là hҵQJÿ~QJ
Giải. E(p,q)
p p q q
p p p q
0
p q q
p q q
p q q
1
p
1
1.1.3 Các quy tắc suy diễn
Trong chӭQJPLQKWRiQKӑF[XҩWSKiWWӯPӝWVӕNKҷQJÿӏQKÿ~QJPӋQKÿӅÿ~QJ
gӑLOà tiӅQÿӅWDVӁiSGөQJFiFTX\WҳFVX\GLӉQÿӇVX\UDFKkQOêFӫDPӝWNKҷQJ
ÿӏQKTPà ta gӑLOà kӃWOXұQNói cách khác, ta sӁSKҧLWìm cách chӭQJPinh dҥQJ
mӋQK ÿӅ
1 2 n
p p p q
mӝW KҵQJ ÿ~QJ WURQJ ÿy
1 2
, ,..., ,
n
p p p q
các
dҥQJPӋQKÿӅWKHRPӝWVӕELӃQORJLFQjRÿy
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Trang 8
Ví dụ. GiҧVӱWDFyFiFWLӅQÿӅ
p
1
: “NӃX$QKӑFFKăPWKì An ÿҥWÿLӇPFDR´
p
2
³1rX$QNK{QJKD\ÿLFKѫLWKì An hӑFFKăP´
p
3
³$QNK{QJÿѭӧFÿLӇPFDR´
Ta muӕQGùng các quy tҳFVX\GLӉQÿӇVX\UDNӃWOXұQT³$QKD\ÿLFKѫL´0XӕQ
vұ\WDSKҧLWUӯXWѭӧQJKyDFiFPӋQKÿӅQJX\ên thӫ\³An hӑFFKăP´³$QKD\ÿL
FKѫL´Yj³$QÿѭӧFÿLӇPFDR´WKành các biӃQPӋQKÿӅSTU1KѭYұ\FiFWLӅQÿӅ
bây giӡWUӣWKành các dҥQJPӋQKÿӅ
1
p p r
2
p q p
3
p r
Ta phҧLFKӭQJPLQKGҥQJPӋQKÿӅVDXOà mӝWKҵQJÿ~QJ
p r q p r q
Ta thӇFKӭQJPLQKÿLӅXQày bҵQJFiFKOұSEҧQJFKkQWUӏFӫDGҥQJPӋQKÿӅWUên.
Tuy nhiên cách này sӁJһSUҩWQKLӅXNKyNKăQNKLFiFELӃQPӋQKÿӅOӟQVӕGòng
cӫDEҧQJFKkQWUӏEҵQJ
n
, vӟLQOà sӕELӃQPӋQKÿӅ0ӝWSKѭѫQJSKiSNKiFOjVӱ
dөQJFiFTX\WҳFVX\GLӉQÿӇ chia bài toán ra thành nhiӅXEѭӟFQKӓQJKƭDOà tӯFiF
tiӅQÿӅWDVX\UDPӝWVӕNӃWOXұQWUXQJJLDQWUѭӟFNKLiSGөQJFiFTX\WҳFVX\GLӉQ
ÿӇVX\UDNӃWOXұQĈӇWLӋQWDP{Kình hóa phép suy diӉQWKjQKVѫÿӗQKѭVDX
1
2
n
p
p
p
q
6DXÿk\Oj mӝWVӕ TX\WҳFVX\GLӉQWKѭӡQJGùng chân cӫD QyFyWKӇÿѭӧF
kiӇPWUDGӉGàng bҵQJFiFKOұSEҧQJFKkQWUӏ
Quy tҳF0RGXV3RQHQV3KѭѫQJSKiSNKҷQJÿӏQK
Quy tҳFQj\ÿѭӧFWKӇKLӋQEӣLKҵQJÿ~QJ
p q p q
hoһFGѭӟLGҥQJ
Vѫÿӗ
p q
p
q
dụ. NӃX$QKӑFFKăPWKì An sӁÿѭӧFÿLӇPFDRPà An hӑFFKăP6X\UD
$QÿѭӧFÿLӇPFDR
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Trang 9
7DPÿRҥQOXұQ6\OORJLVP
Quy tҳFQj\ÿѭӧF WKӇKLӋQEҵQJKҵQJÿ~QJ
p q q r p r
KD\GѭӟLGҥQJP{Kình:
p q
q r
p r
dụ. NӃX$QNK{QJKD\ÿLFKѫLWKì An hӑFFKăPYà nӃX$QKӑFFKăPWKì
An sӁÿѭӧFÿLӇPFDR6X\UDQӃX$QNK{QJKD\ÿLFKѫLWKì An sӁÿѭӧFÿLӇP
cao.
Quy tҳF0RGXV7ROOHQVSKѭѫQJSKiSSKӫÿӏQK
Quy tҳF Qj\ ÿѭӧF WKӇ KLӋQEӣL KҵQJ ÿ~QJ
p q q p
KD\GѭӟL
dҥQJP{Kình:
p q
q
p

dụ. NӃXWUӡLPѭDWKì ÿѭӡQJѭӟWPjÿѭӡQJNK{QJѭӟW6X\UDWUӡLNK{QJ
PѭD
Quy tҳFPkXWKXүQFKӭQJPLQKEҵQJSKҧQFKӭQJ
Quy tҳFQày dӵDWUrQWѭѫQJÿѭѫQJORJLFVDX
1 2 1 2
0
n n
p p p q p p p q
Ví dụ. Hãy sӱGөQJSKѭѫQJSKiSSKҧQFKӭQJFKRFKӭQJPLQKVDX
p r
p q
q s
r s

- 7UѭӟFKӃWWDOҩ\SKӫÿӏQKFӫDNӃWOXұQ
r s r s r s
- 6DX ÿyWD VӁ WKêm vào các tiӅQÿӅKDL JLҧ WKLӃWSKө
r
s
tìm cách
ch
ӭQJPLQKVX\OXұQVDXOjÿ~QJ
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Trang 10
0
p r
p q
q s
r
s
&iFEѭӟFVX\OXұQVӁÿѭӧFWKӵFKLӋQQKѭVDX
p q
q s
p s
7DPÿRҥQOXұQ
s
p
(PP phӫÿӏQK
p r
r
(PP khҷQJÿӏQK
KӃW OXұQ U Fùng vӟL JLҧ WKLӃW SKө
r
cho ta
0
r r
 'R ÿy theo
SKѭѫQJSKiSSKҧQFKӭQJFKӭQJPLQKEDQÿҫXOjÿ~QJ
Quy tҳFFKӭQJPLQKWKHRWUѭӡQJKӧS
Quy tҳFQj\ÿѭӧFWKӇKLӋQEҵQJKҵQJÿ~QJVDX
p r q r p q r
Ý nghƭDFӫDTX\WҳFQày là nӃXPӝWJLҧWKLӃWFyWKӇWiFUDWKjQKKDLWUѭӡQJKӧS
Sÿ~QJKD\Tÿ~QJYjWDÿã chӭQJPLQKÿѭӧFULêng rӁFKRWӯQJWUѭӡQJKӧSOà
kӃWOXұQUÿ~QJNKLҩ\UFNJQJÿ~QJWURQJFҧKDLWUѭӡQJKӧS
dụ. ĈӇFKӭQJPLQKUҵQJIQQQOX{QFKLDKӃWFKR vӟLPӑLVӕWӵ
QKLrQQWD[pWKDLWUѭӡQJKӧSO
à n chҹQQOҿYà thҩ\UҵQJWURQJFҧKDLWUѭӡQJKӧS
f(n) luôn chia hӃWFKR9ұ\WDU~WUDNӃWOXұQFҫQFKӭQJPLQKOà f(n) luôn chia hӃW
cho 2 vӟLPӑLVӕWӵQKLên n.
7UrQÿk\OjPӝWVӕTX\WҳFVX\GLӉQWDWKѭӡQJGùng trong các quá trình suy luұQ
6DXÿk\WDVӁ[pWPӝWYtGөFөWKӇFyVӱGөQJNӃWKӧSQKLӅXTX\WҳFVX\GLӉQ
dụ. KiӇPWUDVX\OXұQVDXÿ~QJKD\VDL“Nếu nghệ Văn Ba không trình diễn
hay số vé bán ra ít hơn 50 vé thì đêm diễn sẽ bị hủy bỏ và Ông bầu sẽ rất buồn. Nếu
đêm diễn bị hủy bỏ thì phải trả lại cho người xem. Nhưng tiền đã không được
trả lại cho người xem. Vậy nghệ sĩ Văn Ba đã trình diễn”.
ĈӇNLӇPWUDVX\OXұQWUên, ta thay các mӋQKÿӅQJX\ên thӫ\EҵQJFiFELӃQPӋQKÿӅ
p: “nghӋVƭ9ăQ%Dÿã trình diӉQ´
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Trang 11
q: “sӕYpEiQUDtWKѫQYp´
r: ³ÿrPGLӉQEӏKӫ\Eӓ´
s: “ông BҫXUҩWEXӗQ´
t: “trҧWLӅQYpOҥLFKRQJѭӡL[HP´
TӯÿyVX\OXұQEDQÿҫXFyWKӇP{Kình nhѭVDX
p q r s
r t
t
p
Suy luұQWUên có thӇÿѭӧFWKӵFKLӋQWKHRFiFEѭӟFVDX
p q r s
( tiӅQÿӅ
r s r
(hҵQJÿ~QJ
r t
(tiӅQÿӅ
p q t
(tam đoạn luận mở rộng)
t
(tiӅQÿӅ
p q
(phương pháp phủ định và luật De
Morgan)
p q p
(hҵQJÿ~QJ
p
(phương pháp khẳng định)
Vұ\VX\OXұQEDQÿҫXOà chính xác.
1.2 Vị từ - Lượng từ
Định nghĩa. MӝWYӏWӯOà mӝWNKҷQJÿӏQKS[\«WURQJÿyFyFKӭDPӝWVӕELӃQ
x,y, … lҩ\JLiWUӏWURQJQKӳQJWұSKӧSFKRWUѭӟF$%«VDRFKR
i. BҧQWKkQS[\«NK{QJSKҧLOà mӋQKÿӅ
ii. NӃX WKD\ [ \ « EҵQJ QKӳQJ
a A
,
b B
, …ta sӁ ÿѭӧF PӝW PӋQK ÿӅ
p(a,b,…) nghƭDchân trӏFӫDQyKRjQWRjQ[iFÿӏQK&iFELӃQ[\«ÿѭӧF
nói là biӃQWӵGRFӫDYӏWӯ
Ví dụ.
a. p(n) = “n sӕQJX\ên tӕ´Oà mӝWYӏWӯWKHRELӃQWӵGR n
, vӟLQ
WDÿѭӧFFiFPӋQKÿӅÿ~QJSSSFòn vӟLQ WDÿѭӧF
các mӋQKÿӅVDLSSS
b. q(x,y) = “x + y sӕOҿ´Oà vӏWӯWKHRELӃQWӵGR
,x y
, chҷQJKҥQT
là mӝWPӋQKÿӅÿ~QJT-3, -7) là mӝWPӋQKÿӅVDL«
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Trang 12
Định nghĩa. &KRWUѭӟFFiFYӏWӯS[T[WKeo mӝWELӃQ
x A
.KLÿy
i. PhӫÿӏQKFӫDSNêKLӋXOà
p
vӏWӯWKHRELӃQ[Pà khi thay x bҵQJPӝW
phҫQWӱDFӕÿӏQKFӫD$WKì ta ÿѭӧFPӋQKÿӅ
p a
.
ii. Phéo nӕLOLӅQWѭѫQJӭQJQӕLUӡLNéo theo, …) cӫDSYà q, hiӋXEӣL
p q
(
p q
,
p q
, …) vӏWӯWKHRELӃQ[Pà khi thay x bҵQJPӝWSKҫQWӱDFӕ
ÿӏQKFӫD$WKì ta ÿѭӧFPӋQKÿӅ
p a q a
( ) ( ), ( ) ( ),...
p a q a p a q a
Ví dụ: p(x) = “x là sӕQJX\ên tӕ´T[ ³[Oà sӕFKҹQ´.KLÿyWDFy
PhӫÿӏQKFӫDS
( )
p x
= “x không là sӕQJX\ên tӕ´
Phép nӕLOLӅQFӫDSYà q:
( )
p q x
= “x là sӕQJX\ên tӕYD[Oà sӕ
chҹQ´
. . .
Định nghĩa. Các mӋQKÿӅ³
, ( )
x A p x
” và “
, ( )
x A p x
´ÿѭӧFJӑLOjOѭӧQJWӯKyD
cӫDYӏWӯS[EӣLOѭӧQJWӯSKәGөQJ
YjOѭӧQJWӯWӗQWҥL
).
Chú ý:
a. Trong các mӋQKÿӅOѭӧQJWӯKyDELӃQ[NK{QJFòn biӃQWӵGRQӳDWDQyL
nó bӏEXӝFEӣLFiFOѭӧQJWӯ
hay
.
b. MӋQKÿӅ
, ( )
x A p x
sӁÿ~QJQӃXWKD\[EҵQJJLiWUӏDEҩWNǤQKѭQJFӕÿӏQK
trong A, p(a) luôn là mӋQKÿӅÿ~QJ
c. MӋQKÿӅ
, ( )
x A p x
sӁÿ~QJQӃXFyPӝWJLiWUӏDWURQJ$VDRFKRSDOà
mӋQKÿӅÿ~QJ
Xét mӝWYӏWӯS[\WKHRKDLELӃQ ,
x A y B
. Khi ҩ\QӃXWKD\[EҵQJPӝWSKҫQWӱ
cӕÿӏQKQKѭQJW\ý
a A
, ta sӁÿѭӧFPӝWYӏWӯSD\WKHRELӃQ\.KLÿyWDFyWKӇ
OѭӧQJ Wӯ KyD Qy WKHR ELӃQ \ Yj ÿѭӧF KDL PӋQK ÿӅ VDX ³
, ( , )
y B p a y
, ( , )
y B p a y
'R[ÿѭӧFWKD\EҵQJPӝWSKҫQWӱFӕÿӏQKQKѭQJW\ý a cӫD$
nên ta hai vӏ Wӯ VDX ÿk\ Oà hai vӏ Wӯ WKHR ELӃQ
x A
:
, ( , )
y B p x y
, ( , )
y B p x y
”. TiӃSWөFOѭӧQJWӯKyDKDLYӏWӯWUên theo biӃQ[WDÿѭӧFPӋQKÿӅ
VDXÿk\
, , ( , )
x A y B p x y
, , ( , )
x A y B p x y
, , ( , )
x A y B p x y
, , ( , )
x A y B p x y
7ѭѫQJ Wӵ WDFNJQJFyWKӇ OѭӧQJ WӯKyDS[\ WKHR ELӃQ[WUѭӟFUӗLELӃQ \VDX ÿӇ
ÿѭӧFPӋQKÿӅQӳD
, , ( , )
y B x A p x y
, , ( , )
y B x A p x y
, , ( , )
y B x A p x y
, , ( , )
y B x A p x y
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Trang 13
Câu hӓLÿһWUDO~FQày liӋXWKӭWӵOѭӧQJWӯKyDFyTXDQWUӑQJKD\NK{QJ"1yL
cách khác, các mӋQKÿӅWѭѫQJӭQJFyWѭѫQJÿѭѫQJORJLFYӟLQKDXNK{QJ"ĈӏQKOê
sau sӁÿӅFұSÿӃQYҩQÿӅQày
Định lý. NӃXS[\Oà mӝt vӏWӯWKHRELӃQ[\WKì ta có các ÿLӅXVDX
i.
, , ( , )
x A y B p x y
, , ( , )
y B x A p x y
ii.
, , ( , )
x A y B p x y
, , ( , )
y B x A p x y
iii.
, , ( , )
x A y B p x y
, , ( , )
y B x A p x y
Chứng minh. Xem tài liӋXWKDPNKҧR>@
CNJQJWѭѫQJ Wӵ FiFKOjPQKѭ WUrQ WDFy WKӇPӣ UӝQJ GӉGàng cho các vӏ Wӯ WKHR
nhiӅXELӃQWӵGRĈһFELӋWWDFy
Mệnh đề. Trong mӝWPӋQKÿӅOѭӧQJtӯKyDWӯPӝWYӏWӯWKHRQKLӅXELӃQÿӝFOұS
nӃXWDKRiQYӏKDLOѭӧQJWӯÿӭQJFҥQKQKDXWKì:
i. MӋQKÿӅPӟLYүQFòn tѭѫQJÿѭѫQJORJLFYӟLPӋQKÿӅFNJQӃXKDLOѭӧQJ
tӯQày cùng loҥL
ii. MӋQKÿӅPӟLVӁOà hӋTXҧORJLFFӫDPӋQKÿӅFNJQӃXKDLOѭӧQJWӯWUѭӟF
khi hoán vӏFyGҥQJ
ĈӏQKOêVDXVӁFKRFK~QJWDELӃWFiFKOҩ\SKӫÿӏQKFӫDPӝWPӋQKÿӅOѭӧQJWӯKyD
Định lý. PhӫÿӏQKFӫDPӝWPӋQKÿӅOѭӧQJWӯKyDWӯYӏWӯS[\«FyÿѭӧFEҵQJ
FiFKWKD\OѭӧQJ
bӣLOѭӧQJ tӯ
WKD\OѭӧQJ
bҵQJOѭӧQJ
thay vӏWӯ
p(x,y,…) bҵQJSKӫÿӏQK
p(x,y,…).
dụ. Phӫ ÿӏQK FӫD PӋQK ÿӅ ³
,x y
, x + y sӕ FKҹQ´ Oà mӋQK ÿӅ
, ,
x y
x+y không là sӕFKҹQ´.
Quy tắc đặc biệt hóa phổ dụng:
“Nếu một mệnh đề đúng có dạng lượng từ hóa, trong đó một biến
x A
bị buộc bởi
lượng từ phổ dụng
, khi đó nếu thay x bằng
a A
ta sẽ được một mệnh đề đúng”.
dụ. Ta mӋQKÿӅÿ~QJVDX³
, ( 1) 2
n n n
´NKLÿyQӃXWKD\QEҵQJVӕWӵ
nhiên bҩWNǤFKҷQJKҥQQ NK{QJFҫQNLӇPWUDOҥLWDFNJQJFKҳFFKҳQUҵQJPӋQK
ÿӅ³
*(5+1)
2” là mӋQKÿӅÿ~QJ
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Trang 14
1.3 Nguyên lý quy nạp
Nguyên lý quy nạp:
Mệnh đề “
, ( )
n p n
là hệ quả logic của “
(0) , ( ) ( 1)
p n p n p n
Nguyên quy nҥSÿѭӧFFөWKӇKyDWKjQKSKѭѫQJSKiSFKӭQJPLQKTX\QҥSQKѭ
sau: GiҧVӱWDSKҧLFKӭQJPLQKPӋQKÿӅ
, ( )
n p n
NKLÿyWDVӁWKӵFKLӋQFiF
EѭӟFVDX
%ѭӟF.LӇPWUDSO
à mӋQKÿӅÿ~QJWURQJWKӵFWӃWDFyWKӇEҳWÿҫXEҵQJ
giá trӏQKӓQKҩWFyWKӇÿѭӧFFӫDQNK{QJQKҩWWKLӃWSKҧLEҳWÿҫXWӯ0)
%ѭӟF  9ӟLQ EҩW NǤJLҧ Vӱ SQ Oà mӋQKÿӅÿ~QJ WDVӁ SKҧL FKӭQJPLQK
p(n+1) cNJQJOà mӋQKÿӅÿ~QJ
dụ. ĈӇ FKӭQJ PLQK n
,
( 1)
0 1 ...
2
n n
n
,ta xét vӏ Wӯ SQ
( 1)
0 1 ...
2
n n
n
”. Ta có:
p(0) = “
0.1
0
2
´ÿk\Uõ ràng là mӝWPӋQKÿӅÿ~QJ
Xét n là sӕWӵQKLên bҩWNǤJLҧVӱSQOà mӋQKÿӅÿ~QJnghƭDOà ta có:
( 1)
0 1 ...
2
n n
n
ta sӁFKӭQJPLQKSQFNJQJÿ~QJ7KұWYұ\WDFy
1 ( 1) 1
( 1)
0 1 ... ( 1) ( 1)
2 2
n n
n n
n n n
suy ra p(n+1) là mӋQKÿӅÿ~QJ
Theo nguyên lý quy nҥSWDFyÿLӅXSKҧLFKӭQJPLQK
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Trang 15
2 Chương 2. Phép đếm
2.1 Tập hợp Tính chất
7URQJFKѭѫQJWUѭӟFFK~QJWDÿã mӝWYài lҫQVӱGөQJNKiLQLӋPWұSKӧSWURQJPӝW
sӕYtGөÿһFELӋWOjWURQJÿӏQKQJKƭDFӫDFiFOѭӧQJWӯ7URQJFKѭѫQJQj\WDVӁQyL
rõ hѫQYӅNKiLQLӋPQày.
Trong toán hӑFWұSKӧSOà mӝWNKiLQLӋPFѫEҧQNK{QJWKӇÿӏQKQJKƭDWK{QJTXD
FiFÿӕLWѭӧQJNKiFÿѭӧF0ӝWFiFKWUӵFTXDQWұSKӧSOà mӝWNKiLQLӋPÿӇFKӍFiF
ÿӕLWѭӧQJÿѭӧFQKyPOҥLWKHRPӝWWtQKFKҩWQjRÿó. NӃXDOjÿӕLWѭӧQJFӫDWұSKӧS
A, ta viӃW
a A
, nӃXNK{QJWDYLӃW
a A
.
ĈӇêUҵQJWӯ³WtQKFKҩW´ÿѭӧFKLӇXWKHRPӝWQJKƭDUӝQJUãi. Thông thѭӡQJQyVӁ
ÿѭӧFELӇXKLӋQEӣLPӝWYӏWӯS[WKHRPӝWELӃQ
x
U
. Khi ҩ\WұSKӧSÿѭӧFNêKLӋX
bӣL
( )
A x U p x
8ÿѭӧFJӑLOà tұSYNJWUө
Ví dụ.
1.
2
A x x
ÿk\OjWұSKӧSFiFVӕWӵQKLên chҹQ
2.
2
5
A x x
ÿk\OjWұSKӧSFiFVӕQJX\ên có bìQKSKѭѫQJQKӓKѫQ
TұSKӧSFòn có thӇÿѭӧFELӇXGLӉQEҵQJFiFKOLӋWNê các phҫQWӱFӫDQy&KҷQJKҥQ
QKѭWұSKӧSWURQJPөFFӫDYtGөWUên có thӇÿѭӧFYLӃWOà: A = {-2,-1,0,1,2}.
TұSKӧSNK{QJFKӭDEҩWFӭSKҫQWӱQào gӑLOà tұSKӧSUӛQJYjÿѭӧFNêKLӋu là
.
Xét hai tұSKӧS$Yà B trong tұSYNJWUөU. Ta nói A tұSKӧSFRQFӫD%KD\$
chӭDWURQJ%QӃX
,
x U x A x B
. Ta có thӇKLӇXÿѫQJLҧQOà bҩWFӭSKҫQWӱ
nào nҵPWURQJ$FNJQJQҵPWURQJ%
Ta thӇVӱng các phép toán trên mӋQKÿӅYà vӏWӯÿӇÿӏQKQJKƭDFic phép toán
trên t
ұSKӧSQKѭSKpSKӧS
), phép giao (
) và phҫQEWKHRÿӏQKQJKƭDVDXÿk\:
Định nghĩa. GiҧVӱ$%Oà hai tұSKӧSFRQFӫDWұSKӧSvNJWUө8.KLҩ\
( ) ( )
( ) ( )
A B x U x A x B
A B x U x A x B
A x U x A
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Trang 16
ĈӏQKOêVDXVӁJLӟLWKLӋXFiFWtQKFKҩWFӫDFiFSKpSWRiQWUên tұSKӧS
Định lý. A, B, C là các tұSFRQWùy ý cӫD8WDFy
i. Tính giao hoán:
=
A B B A
A B B A
ii. Tính kӃWKӧS
A B C A B C
A B C A B C
iii. LuұW'H0RUJDQ
A B A B
A B A B
iv. Tính phân phӕL
A B C A B A C
A B C A B A C
v. PhҫQWӱWUXQJKòa:
A A
A U A
vi. PhҫQEù:
A A U
A A
vii. Tính thӕQJWUӏ
A U U
A
viii. Tính lNJ\ÿҷQJ
A A A
A A A
ix. LuұWKҩSWKө
A A B A
A A B A
Chứng minh. Các tính chҩWWUrQÿѭӧFVX\UDWӯÿӏQKQJKƭDYà các quy luұWORJLF
Chú ý. Ta có thӇOҩ\KӧSKRһFJLDRFӫDQKLӅXWұSKӧSYà ký hiӋXQKѭVDX
1 2
1
...
n
i n
i
A A A A
1 2
1
...
n
i n
i
A A A A
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Trang 17
2.2 Ánh x
Định nghĩa.
i. MӝWiQK[ҥIWӯWұSKӧS$Yào tұSKӧS%OjSKpSWѭѫQJӭQJOLên kӃWPӛLSKҫQ
tӱ[FӫD$YӟLPӝWSKҫQWӱGX\QKҩW\FӫD%Pà ta ký kiӋXOà f(x) và gӑLOà ҧQK
cӫD[EӣLI7DYLӃW
:
( )
f A B
x f x
ii. Hai ánh xҥ I Yà g tӯ $ YjR % ÿѭӧF QyL Oà bҵQJ QKDX QӃX
, ( ) ( )
x A f x g x
Định nghĩa.
i. NӃX(Oà mӝWWұSKӧSFRQFӫD$WKì ҧQKFӫD(EӣLIOà tұSKӧS
( ) , ( ) ( )
f E y B x A y f x f x x E
ii. NӃX)Oà mӝWWұSKӧSFRQFӫD%WKì ҧQKQJѭӧFFӫD)TXDiQK[ҥIOà tұS
hӧS
1
( ) ( )
f F x A f x F
Chú ý:
1. NӃX
y B
ta viӃW
1 1
( )
f y f y
2. NӃX
1
( )f y
thì y không nҵPWURQJҧQKI$FӫD$
3. NӃX
1
( ) {x}
f y
thì x là phҫQWӱGX\QKҩWFyҧQKOà y.
Định nghĩa. GӑLf là mӝWiQK[ҥWӯWұS$Yà tұS%.KLҩ\WDQyL
i. ftoàn ánh nӃXf(A)=B
ii. f đơn ánh nӃXKDLSKҫQWӱNKiFQKDXEҩWNǤFӫD$FyҧQKNKiFQKDX
nghƭDOà:
, ' , ' ( ) ( ')
x x A x x f x f x
iii. fsong ánh nӃXQyYӯDÿѫQiQKYӯDWRiQiQK
Xét f mӝWVRQJiQKWӯA lên B, NKLÿyYӟLPӛL
y B
tùy ý, sӁFyGX\QKҩWPӝW
phҫQWӱ
x A
sao cho f(x)=y1KѭWKӃWѭѫQJӭQJ
y x
mӝWiQK[ҥWӯ%Yào A
ta hiӋX Oà
1
f
gӑL Oà ánh xҥ QJѭӧF FӫD iQK [ҥ f. Ta có:
1
( ) ( )
f y x f x y
.
Ta có tính chҩWFӫDiQK[ҥQJѭӧFQKѭVDX
1
1
( ( )) ,
( ( )) ,
f f y y y B
f f x x x A
ĈӏQKQJKƭD&KRKDLiQK[ҥ
:
f A B
: '
g B C
WURQJÿy
'
B B
. Ánh xҥKӧS
h là ánh xҥWӯ$Yào C ÿѭӧF[iFÿӏQKEӣL
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Trang 18
:
( ) ( ( ))
h A C
x h x g f x
Ta ký hiӋX
h f g
.
Các tính chất của ánh xạ:
Định lý. Cho f mӝWiQK[ҥWӯWұS$Yào tұS%(
1
E
2
hai tұSFRQWùy ý cӫD
A, F
1
và F
2
là hai tұSFRQWùy ý cӫD%7DFy
i.
1 2 1 2
( ) ( ) ( )
f E E f E f E
ii.
1 2 1 2
( ) ( ) ( )
f E E f E f E
iii.
1 1
1 2 1 2
( ) ( ) ( )
f F F f F f F
iv.
1 1
1 2 1 2
( ) ( ) ( )
f F F f F f F
2.3 Giải tích tổ hợp
3KpSÿӃPFiFSKҫQWӱFӫDPӝWWұSKӧS$FKtQKOà tìm mӝWVRQJiQKJLӳD$Yà mӝW
tұSFRQ{1,2,…,n} cӫD N. NӃX$KӳXKҥQWKì n chính là sӕSKҫQWӱFӫDQyĈӏQK
nghƭDVDXÿk\VӁÿӅFұSÿӃQYҩQÿӅQày:
Định nghĩa.
i. MӝWWұSKӧS$ÿѭӧFQyLOà hӳXKҥQYà có n phҫQWӱQӃXWӗQWҥLPӝWVRQJiQK
giӳD$Yà tұSKӧSFRQ{1,2,...,n} cӫD N. Khi ÿyWDYLӃW
A n
.
ii. NӃX$NK{QJKӳXKҥQWDQyL$Y{KҥQ
2.3.1 Các nguyên lý cơ bản của phép đếm:
Nguyên cộng: NӃXPӝWF{QJYLӋFFyWKӇÿѭӧFWKӵFKLӋQEҵQJPӝWWURQJQFiFK
loҥLWUӯOүQQKDXN
1
, k
2
, …, k
n
7URQJÿyÿӇWKӵFKLӋQWKHRFách k
i
lҥLFyW
i
SKѭѫQJ
iQNKiFQKDXL Q.KLÿyWәQJVӕSKѭѫQJiQÿӇWKӵFKLӋQF{QJYLӋFEDQÿҫXOà:
t
1
+ t
2
+ … + t
n
.
dụ: ĈӇÿLWӯ7S+&0UD+à NӝLFyFiFKÿL{W{ÿLWàu hӓDKRһFÿLPi\ED\
ĈLEҵQJ{W{FyFiFKÿLWD[LÿL[Hÿò, thuê xe ULrQJĈLEҵQJWàu hӓDFyFiFKÿL
bҵQJWjXQKDQKYjÿLEҵQJWàu bình thѭӡQJĈLEҵQJPi\ED\FNJQJFyKDLFiFKÿL
bҵQJ9LHWQDPDLUOLQHKRһFÿLEҵQJ3DcLILFDLUOLQH1KѭYұ\WәQJFӝQJFy 
FiFKÿLWӯ7S+&0UD+à NӝL
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Trang 19
Nguyên lý cộng mở rộng:
i. Cho A và B là hai tұSKӧSEҩWNǤNKLÿyWDFy
A B A B A B
ii. Cho A1, A2, …, An là n tұSKӧSEҩWNǤ. Ta có:
1
1 2 1 2
... ... ( 1)
n
n n
A A A N N N
WURQJÿy1
k
là tәQJVӕSKҫQWӱFӫDFiFWҩWFҧFiFSKҫQJLDRFӫDNWұSEҩWNǤWURQJVӕ
n tұSEDQÿҫX
Ví dụ. VӟLWұS$%&Q WKHRQJX\ên lý cӝQJWәQJTXiWWDFyF{QJWKӭFVDX
A B C A B C A B B C C A A B C
Nguyên nhân: NӃXPӝWF{QJYLӋFphҧL thӵFKLӋQÿѭӧFWKHRQJLDLÿRҥQliên tiӃS
nhau: k
1
, k
2
, …, k
n
. MӛLJLDLÿRҥQN
i
t
i
FiFKÿӇ thӵFKLӋQ1KѭYұ\VӁFyt
1
.t
2
…t
n
FiFKNKiFQKDXÿӇWKӵFKLӋQF{QJYLӋFEDQÿҫX
dụ. MӝWQJѭӡLFyFiLiR-mi khác nhau, 2 cái quҫQGjLNKiFQKDXYjÿ{L
JLj\NKiFQKDX1KѭYұ\FyWҩWFҧEӝWUDQJSKөFNKiFQKDXÿӇQJѭӡLQày
l
ӵDFKӑQNKLPһF
Định nghĩa. 7tFKĈӅ-các cӫDWұSKӧS$%NêKLӋXOà
A B
tұSKӧSWҩWFҧFiF
cһSWKӭWӵDEYӟL
a A
b B
WURQJÿyKDLFһSDEYjD¶E¶ÿѭӧFQyLOà bҵQJ
nhau nӃXYà chӍQӃXD D¶Yà b=b’.
ĈӏQKOê1ӃX$Yà B là hai tұSKӧSKӳXKҥQWKì
A B
cNJQJOà tұSKӧSKӳXKҥQYà ta
có:
.
A B A B
2.3.2 Giải tích tổ hợp
Hoán vị.
Định nghĩa. Cho n vұWNKiFQKDX0ӝWKRiQYӏFӫDQYұWQày mӝWFiFKVҳS[ӃS
chúng theo mӝWFiFKQjRÿy
Mệnh đề. SӕFiFKRiQYӏFӫDQYұWNKiFQKDXOà:
! 1.2.3...
n
P n n
.
Chứng minh. Ta chӭQJPLQKF{QJ WKӭF Qày dӵD WUên nguyên nhân. Xét công
viӋF[k\GӵQJPӝWKRiQYӏFӫDQYұWEDQÿҫX&{QJYLӋFQj\ÿѭӧFFKLDWKành các
EѭӟFVDX
- %ѭӟF&KӑQYұWÿӭQJÿҫXFyQFiFKFKӑQQYұWÿӅXFyWKӇÿӭQJÿҫX
- %ѭӟF&KӑQYұWÿӭQJWKӭKDLFyQ-1 cách chӑQGRÿã chӑQYұWÿӭQJÿҫX
nên bây giӡWDFKӍFòn n-1 vұW
-
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Trang 20
- %ѭӟFQ&KӑQYұWFòn lҥLFXӕLFùng: chӍFyFiFKGX\QKҩW
1KѭYұ\ theo nguyên nhân, sӕFiFK[k\GӵQJKRiQYӏFNJQJFKtQKOà sӕFiFKRiQ
vӏFӫDQYұWEDQÿҫXOà n.(n-1)…2.1 = n!.
Ví dụ. SӕFiFVӕWӵQKLên có 5 chӳVӕNKiFQKDXÿѭӧFWҥRWӯFiFFKӳVӕ
là 5! = 120 cách.
Hoán vị lặp
Hoán vӏOһSFNJQJPDQg ý nghƭDQKѭKRiQYӏÿLӅXNKiFELӋWӣÿk\Oà trong n vұWEDQ
ÿҫXFyQKLӅXYұWJLӕQJQKDX MӋQKÿӅVDXÿk\VӁFKRFK~QJWDELӃWF{QJWKӭFÿӇ
tính hoán vӏOһS
Mệnh đề. Cho n vұWWURQJÿyFyW
1
vұWORҥLJLӕQJQKDXW
2
vұWORҥLJLӕQJQKDX
…, t
k
vұWOoҥLNJLӕQJQKDX.KLÿyVӕFiFKRiQYӏNKiFQKDXFӫDQYұWEDQÿҫXOà
1 2
!
! !... !
k
n
t t t
.
Ch
ứng minh. ĈҫX WLên, nӃX[HP QKѭ Q YұW Oà khác nhau, ta n! hoán vӏ 7X\
nhiên do t
1
vұWORҥLJLӕQJQKDXQên ӭQJYӟLPӝWKRiQYӏEDQÿҫXQӃXWDhoán
vӏW
1
phҫQWӱQày (có t
1
! hoán vӏQKѭYұ\WDQÿѭӧFKRiQYӏÿy&KtQKYì vұ\WKӵF
chҩWW
1
! hoán vӏNLӇXQày chӍOà mӝWKRiQYӏ'RÿyVӕKRiQYӏWKӵFVӵNKiFQKDX
nӃXFyW
1
vұWORҥLJLӕQJQKDXFKӍFòn là:
1
!
!
n
t
. TiӃSWKHRWa lҥLFyW
2
phҫQWӱORҥL
giӕQJQKDXQên sӕKRiQYӏWKӵFVӵNKiFQKDXEk\JLӡVӁOà
1 2
!
! !
n
t t
. CӭWLӃSWөFQKѭ
vұ\FKRÿӃQNKLNӃWWK~FWDVӁÿѭӧFF{QJWKӭFFҫQFKӭQJPLQKWURQJPӋQKÿӅ
dụ: SӕFiFVӕWӵQKLên 6 chӳVӕWURQJ ÿyEҳWEXӝFSKҧLFyFKӳVӕFKӳ
sӕYà 1 chӳVӕOà:
6!
60
3!2!1!
.
Chỉnh hợp
Định nghĩa. Cho n vұWNKiFQKDX0ӝWFKӍQKKӧSFKұSNFӫDQYұWQày mӝWFiFK
chӑQNYұWkhác nhau có kӇÿӃQWKӭWӵWURQJVӕQYұWÿy
Mệnh đề. SӕFKӍQKKӧSFKұSNFӫDQYұWNKiFQKDXOà:
!
( )!
k
n
n
A
n k
Chứng minh. Dùng nguyên lý nhân.
| 1/51

Preview text:

TRƯỜNG ĐẠI HỌC SƯ PHẠM TP.HCM
KHOA TOÁN – TIN HỌC TÓM TẮT BÀI GIẢNG Môn TOÁN RỜI RẠC
Giảng viên biên soạn: Nguyễn Ngọc Trung TP.HCM 9.2006 MỤC LỤC
&KѭѫQJ0ӋQKÿӅ........................................................................................ 3 1.1
MӋQKÿӅ- Tính chҩW.......................................................................... 3 1.1.1
MӋQKÿӅYà các phép toán mӋQKÿӅ ............................................ 3 1.1.2
DҥQJPӋQKÿӅ ............................................................................ 5 1.1.3
Các quy tҳFVX\GLӉQ .................................................................. 7 1.2
VӏWӯ- /ѭӧQJWӯ.............................................................................. 11 1.3
Nguyên lý quy nҥS.......................................................................... 14
&KѭѫQJ3KpSÿӃP.................................................................................... 15 2.1
TұSKӧS– Tính chҩW........................................................................ 15 2.2
Ánh xҥ ............................................................................................ 17 2.3
GiҧLWtFKWәKӧS ............................................................................... 18 2.3.1
Các nguyên lý cѫEҧQFӫDSKpSÿӃP ....................................... 18 2.3.2
GiҧLWtFKWәKӧS ........................................................................ 19 2.3.3
Nguyên lý Dirichlet. (nguyên lý chuӗQJEӗFkX ...................... 23
&KѭѫQJ4XDQKӋ ...................................................................................... 24 3.1
Quan hӋ .......................................................................................... 24 3.2
Quan hӋWѭѫQJÿѭѫQJ ..................................................................... 25 3.3
Quan hӋWKӭWӵ- BiӇXÿӗ+DVVH ...................................................... 26
&KѭѫQJĈҥLVӕ%RROH ............................................................................... 30 4.1
ĈҥLVӕ%RROHĈӏQKQJKƭD– Tính chҩW ............................................. 30 4.2
Hàm Boole – DҥQJQӕLUӡLFKtQKWҳF ............................................... 36 4.3
Bài toán mҥFKÿLӋQ– MҥQJFiFFәQJ.............................................. 42 4.4
Tìm công thӭFÿDWKӭFWӕLWLӇX– 3KѭѫQJSKiS.DUQDXJK ............... 44
TÀI LIỆU THAM KHẢO.......................................................................... 51
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
1 Chương 1. Mệnh đề
1.1 Mệnh đề - Tính chất
1.1.1 Mệnh đề và các phép toán mệnh đề
Định nghĩa. MӋQKÿӅOà các khҷQJÿӏQKFyJLiWUӏFKkQOê[iFÿӏQKÿ~QJKRһFVDL
QKѭQJ NK{QJWKӇ YӯD ÿ~QJ YӯD VDL &iF PӋQKÿӅÿ~QJ ÿѭӧFQyL Oà có chân trị
đúng, các mӋQKÿӅVDLÿѭӧFQyLOà có chân trị sai. Ví dụ:
- Các khҷQJÿӏQKVDXOà mӋQKÿӅ
. “1 + 2 = 5” là mӋQKÿӅVDL
. “10 là sӕFKҹQ´Oà mӋQKÿӅÿ~QJ
- Các khҷQJÿӏQKVDXNK{QJSKҧLOà mӋQKÿӅ ³7{LÿLKӑF´ . “n là sӕQJX\ên tӕ´
Ký hiệu: 7DWKѭӡQJNêKLӋXFiFPӋQKÿӅEҵQJFiFFKӳFiLLQKRD345«Yà
chân trӏÿ~QJVDLÿѭӧFNêKLӋXEӣL
Các phép toán mệnh đề:
Phép phủ định: phӫÿӏQKFӫDPӋQKÿӅ3ÿѭӧFêKLӋXEӣL P ÿӑFOà “không
P” hoһF³SKӫÿӏQKFӫD3´&KkQWUӏFӫD P
 là 0 nӃXFKkQWUӏFӫD3Oà mӝWYà QJѭӧFOҥL
VD. P = “3 là sӕQJX\ên tӕ´ là mӋQKÿӅÿ~QJ. 'RÿyPӋQKÿӅ P  = “3 không
là sӕQJX\ên tӕOà mӋQKÿӅVDL
BҧQJVDXJӑLOà bҧQJFKkQWUӏFӫDSKpSSKӫÿӏQK P P0 1 1 0
Phép nối liền: MӋQKÿӅQӕLOLӃQFӫDKDLPӋQKÿӅ3Yj4ÿѭӧFNêKLӋXEӣL
P Q ÿӑFOà “P và Q”. Chân trӏFӫD P Q là 1 nӃXFҧ3OүQ4ÿӅXFyFKkQ
trӏOjWURQJFiFWUѭӡQJKӧSNKiF P Q có chân trӏOà 0.
VD. P = “Hôm nay trӡL ÿҽS´ Yà Q = “TrұQ EyQJ ÿi KҩSGүQ´ .KL ÿyWD Fy
mӋQK ÿӅQӕLOLӅQ FӫD 3 Yà Q là: P Q = “Hôm nay trӡL ÿҽSYà trұQEyQJ ÿi
hҩSGүQ´0ӋQKÿӅQӕLOLӅQQày sӁÿ~QJQӃXQKѭFҧKDLPӋQKÿӅ3Yj4ÿӅX Trang 3
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
ÿ~QJ1JѭӧFOҥLQӃu có mӝWWURQJKDLPӋQKÿӅWUên sai hoһFFҧKDLFùng sai thì mӋQKÿӅQӗLOLӅQVӁOà sai. BҧQJFKkQWUӏFӫDSKpSQӕLOLӅQ P Q P Q 0 0 0 0 1 0 1 0 0 1 1 1
Phép nối rời: MӋQKÿӅQӕLUӡLFӫDKDLPӋQKÿӅ3Yj4ÿѭӧFNêKLӋXEӣi
P Q ÿӑFOà “P hay Q”. Chân trӏFӫD P Q là 0 nӃXFҧ3OүQ4ÿӅXFyFKkQ
trӏOjWURQJFiFWUѭӡQJKӧSNKiF P Q có chân trӏOà 0.
VD. P = “An là ca sƭ´3 ³$QOjJLiRYLrQ´.KLÿyta có mӋQKÿӅQӕLUӡLFӫD
P và Q là P Q = “An là ca sƭKD\$QOà giáo viên”. MӋQKÿӅQӕLOLӅQQày sӁ
ÿ~QJQӃXQKѭPӝWWURQJKDLPӋQKÿӅWUrQOjÿ~QJKRһFFҧKDLPӋQKÿӅWUên
ÿӅXÿ~QJ1ӃXFҧKDLPӋQKÿӅ3Yj4ÿӅXVDLWKì P Q sӁVDL BҧQJFKkQWUӏFӫDSKpSQӕLUӡL P Q P Q 0 0 0 0 1 1 1 0 1 1 1 1
Phép kéo theo: MӋQKÿӅ3NpRWKHR4ÿѭӧFNêKLӋXOà P Q ĈӇ[iFÿӏQK
chân trӏFӫDPӋQKÿӅ3NpRWKHR4WD[pWví dөVDX3 ³An trúng sӕ”, Q =
³$QPXD[HPi\´NKLÿyPӋQKÿӅ3NpSWKHR4VӁOà “Nếu An trúng sӕthì
An sӁPXD[HPi\´7DFyFiFWUѭӡQJKӧSVDXÿk\
 $Qÿã trúng sӕYà anh ta mua xe máy: hiӇQQKLên mӋQKÿӅ P Q là ÿ~QJ
 $Q ÿã trúng sӕ QKѭQJ DQK WD NK{QJ PXD [H Pi\ Uõ ràng mӋQK ÿӅ P Q là sai.
 An không trúng sӕQKѭQJDQKWDYүQPXD[HPi\PӋQKÿӅ P Q vүQ ÿ~QJ
 An không trúng sӕYà anh ta không mua xe máy: mӋQKÿӅ P Q ÿ~QJ Trang 4
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0 BҧQJFKkQWUӏFӫDSKpSNpRWKHR P Q P Q 0 0 1 0 1 1 1 0 0 1 1 1
Phép kéo theo hai chiều: MӋQKÿӅ3NpRWKHR4YjQJѭӧFOҥLÿѭӧFNêKLӋX
bӣL P Q là mӋQKÿӅFyFKkQ WUӏÿ~QJNKL3Yà Q có chân trӏJLӕQJQKDX
FQJ ÿ~QJ KRһF Fùng sai) và có chân trӏ VDL NKL 3 Yà Q có chân trӏ NKiF nhau.
VD. P = “An hӑFJLӓL´4 ³$QÿѭӧFÿLӇPFDR´.KLÿyPӋQKÿӅ P Q =
“NӃX$QKӑFJLӓLWKì An sӁÿѭӧFÿLӇPFDRYjQJѭӧFOҥL´
BҧQg chân trӏFӫDSKpSNpRWKHRKDLFKLӅXQKѭVDX P Q P Q 0 0 1 0 1 0 1 0 0 1 1 1
1.1.2 Dạng mệnh đề
Định nghĩa. Dạng mệnh đề ÿѭӧF[k\GӵQJWӯ -
Các mӋQKÿӅOà các hҵQJPӋQKÿӅ -
Các biӃQPӋQKÿӅSTU«FyWKӇOҩ\JLiWUӏOà các mӋQKÿӅQjRÿy -
Các phép toán trên mӋQKÿӅ, và các dҩXQJRһF.
Ví dụ. E( p, q, r)   p q  r p là mӝW GҥQJ PӋQK ÿӅ WURQJ ÿy S T U Oà các biӃQPӋQKÿӅ
ĈӇêUҵQJWDFyWKӇ[k\GӵQJQKLӅXGҥQJPӋQKÿӅSKӭFWҥSWӯFiFGҥQJPӋQKÿӅ
ÿѫQ JLҧQ KѫQ EҵQJ Fich sӱ GөQJ FiF SKpS WRiQ PӋQK ÿӅ ÿӇ NӃW KӧS FK~QJ OҥL
ChҷQJ KҥQ QKѭ GҥQJ PӋQK ÿӅ (STU ӣ WUrQ ÿѭӧF NӃW QӕL Wӯ KDL GҥQJ PӋQK ÿӅ
E ( p, q, r)  p q E ( p, q, r)  r p bҵQJSKpSWRiQQӕLUӡL  ). 1 2
MӛLGҥQJPӋQKÿӅVӁÿѭӧFVӁFyPӝWEҧQJFKkQWUӏ[iFÿӏQKWURQJÿyPӛLGòng cho
biӃWFKkQWUӏFӫDGҥQJPӋQKÿӅÿyWKHRFiFFKkQWUӏFөWKӇFӫDFiFELӃQ Trang 5
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Ví dụ. E( p, q, r)   p q  r p có bҧQJFKkQWUӏQKѭVDX p q r r p q
r p E(p,q,r) 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1
Định nghĩa. Hai dҥQJPӋQKÿӅ(Yj)ÿѭӧFQyLOà tương đương logic nӃXFK~QJFy
cùng bҧQg chân trӏ.KLҩ\WDYLӃW E F .
Chú ý rҵQJnӃX(Yj)WѭѫQJÿѭѫQJORJLFWKì dҥQJPӋQKÿӅ P Q luôn lҩ\JLiWUӏ
là 1 dù các biӃQFyOҩ\EҩWFӭJLiWUӏQào. Định nghĩa.
i. MӝWGҥQJPӋQKÿӅÿѭӧFJӑLOà mӝWKҵQJÿ~QJQӃXQyOX{QOX{QOҩ\FKkQWUӏ 1
ii. MӝWGҥQJPӋQKÿӅÿѭӧFJӑLOà mӝWKҵQJVDLQӃXQyOX{QOҩ\FKkQWUӏ
Mệnh đề. Hai dҥQg mӋQKÿӅ(Yj)WѭѫQJÿѭѫQJORJLFNKLYjFKӍNKL P Q là mӝW hҵQJÿ~QJ
Định nghĩa. DҥQJPӋQKÿӅ)ÿѭӧFQyL là hӋTXҧORJLFFӫDGҥQJPӋQKÿӅ(QӃX
E F là mӝWKҵQJÿ~QJ Khi ҩ\WDYLӃW E F . Các quy luật logic:
Định lý. VӟLSTUOà các biӃQPӋQKÿӅOà hҵQJÿ~QJOà hҵQJVDLWDFyFiF WѭѫQJÿѭѫQJORJLF i.
Phủ định của phủ định: p p ii. Quy tắc De Morgan:
 p q  p q  và
 p q  p qiii. Luật kéo theo:
p q  p q iv. Luật giao hoán:
p q q p Trang 6
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0 và
p q q p v. Luật phân phối:
p  q r    p q   p r  và
p  q r    p q   p r vi. Luật kết hợp:
p  q r    p q  r
p  q r    p q  r
vii. Luật lũy đẳng:
p p p
p p p
viii. Luật trung hòa: p 1  pp  0  p ix. Phần tử bù: p  p  0 và p  p  1 x. Luật thống trị: p  0  0 và p 1  1 xi. Luật hấp thụ:
p   p q  p
p   p q  p
Ví dụ. sӱGөQJFiFTX\OXұWORJLFFKӭQJPLQKUҵQJGҥQJPӋQKÿӅ
E( p, q)   p   p q  q là hҵQJÿ~QJ Giải. E(p,q)   p  
p q  q  
 p  p   p q    0  
p q  q
  p q  q
 p  q q  p 1  1
1.1.3 Các quy tắc suy diễn
Trong chӭQJPLQKWRiQKӑF[XҩWSKiWWӯPӝWVӕNKҷQJÿӏQKÿ~QJPӋQKÿӅÿ~QJ
gӑLOà tiӅQÿӅWDVӁiSGөQJFiFTX\WҳFVX\GLӉQÿӇVX\UDFKkQOêFӫDPӝWNKҷQJ
ÿӏQKTPà ta gӑLOà kӃWOXұQNói cách khác, ta sӁSKҧLWìm cách chӭQJPinh dҥQJ
mӋQK ÿӅ  p p  p q là mӝW KҵQJ ÿ~QJ WURQJ ÿy p , p ,..., p , q là các 1 2 n  1 2 n
dҥQJPӋQKÿӅWKHRPӝWVӕELӃQORJLFQjRÿy Trang 7
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Ví dụ. GiҧVӱWDFyFiFWLӅQÿӅ
p1: “NӃX$QKӑFFKăPWKì An ÿҥWÿLӇPFDR´ p ³1rX$QNK{QJKD\ÿLFKѫLWK 2 ì An hӑFFKăP´ p ³$QNK{QJÿѭӧFÿLӇPFDR´ 3
Ta muӕQGùng các quy tҳFVX\GLӉQÿӇVX\UDNӃWOXұQT ³$QKD\ÿLFKѫL´0XӕQ
vұ\WDSKҧLWUӯXWѭӧQJKyDFiFPӋQKÿӅQJX\ên thӫ\³An hӑFFKăP´³$QKD\ÿL
FKѫL´Yj³$QÿѭӧFÿLӇPFDR´WKành các biӃQPӋQKÿӅSTU1KѭYұ\FiFWLӅQÿӅ
bây giӡWUӣWKành các dҥQJPӋQKÿӅ
p p r 1
p  q p 2 p  r 3
Ta phҧLFKӭQJPLQKGҥQJPӋQKÿӅVDXOà mӝWKҵQJÿ~QJ
 p r q p  r  q
Ta có thӇFKӭQJPLQKÿLӅXQày bҵQJFiFKOұSEҧQJFKkQWUӏFӫDGҥQJPӋQKÿӅWUên.
Tuy nhiên cách này sӁJһSUҩWQKLӅXNKyNKăQNKLFiFELӃQPӋQKÿӅOӟQVӕGòng
cӫDEҧQJFKkQWUӏEҵQJn, vӟLQOà sӕELӃQPӋQKÿӅ0ӝWSKѭѫQJSKiSNKiFOjVӱ
dөQJFiFTX\WҳFVX\GLӉQÿӇ chia bài toán ra thành nhiӅXEѭӟFQKӓQJKƭDOà tӯFiF
tiӅQÿӅWDVX\UDPӝWVӕNӃWOXұQWUXQJJLDQWUѭӟFNKLiSGөQJFiFTX\WҳFVX\GLӉQ
ÿӇVX\UDNӃWOXұQĈӇWLӋQWDP{Kình hóa phép suy diӉQWKjQKVѫÿӗQKѭVDX p1 p2  pnq
6DXÿk\Oj mӝWVӕTX\WҳFVX\GLӉQWKѭӡQJGùng mà chân lý cӫD QyFyWKӇÿѭӧF
kiӇPWUDGӉGàng bҵQJFiFKOұSEҧQJFKkQWUӏ
 Quy tҳF0RGXV3RQHQV3KѭѫQJSKiSNKҷQJÿӏQK
Quy tҳFQj\ÿѭӧFWKӇKLӋQEӣLKҵQJÿ~QJ  p q  p  q  hoһFGѭӟLGҥQJ Vѫÿӗ p q p q
Ví dụ. NӃX$QKӑFFKăPWKì An sӁÿѭӧFÿLӇPFDRPà An hӑFFKăP6X\UD $QÿѭӧFÿLӇPFDR Trang 8
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0  7DPÿRҥQOXұQ6\OORJLVP
Quy tҳF Qj\ ÿѭӧF WKӇ KLӋQ EҵQJ KҵQJ ÿ~QJ  p q  q r    p r KD\GѭӟLGҥQJP{Kình: p q q rp r
Ví dụ. NӃX$QNK{QJKD\ÿLFKѫLWKì An hӑFFKăPYà nӃX$QKӑFFKăPWKì
An sӁÿѭӧFÿLӇPFDR6X\UDQӃX$QNK{QJKD\ÿLFKѫLWKì An sӁÿѭӧFÿLӇP cao.
 Quy tҳF0RGXV7ROOHQVSKѭѫQJSKiSSKӫÿӏQK
Quy tҳF Qj\ ÿѭӧF WKӇ KLӋQ EӣL KҵQJ ÿ~QJ  p q  q  p  KD\ GѭӟL dҥQJP{Kình: p qqp
Ví dụ. NӃXWUӡLPѭDWKì ÿѭӡQJѭӟWPjÿѭӡQJNK{QJѭӟW6X\UDWUӡLNK{QJ PѭD
 Quy tҳFPkXWKXүQFKӭQJPLQKEҵQJSKҧQFKӭQJ
Quy tҳFQày dӵDWUrQWѭѫQJÿѭѫQJORJLFVDX
 p p  p q   p p  p  q  0  1 2 n    1 2 n  
Ví dụ. Hãy sӱGөQJSKѭѫQJSKiSSKҧQFKӭQJFKRFKӭQJPLQKVDX p r p   q q s r s -
7UѭӟFKӃWWDOҩ\SKӫÿӏQKFӫDNӃWOXұQ  r
  s  r s  r  s -
6DX ÿyWDVӁ WKêm vào các tiӅQ ÿӅKDL JLҧ WKLӃW SKө r và s tìm cách chӭQJPLQKVX\OXұQVDXOjÿ~QJ Trang 9
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0 p r p   q q s r s  0 
&iFEѭӟFVX\OXұQVӁÿѭӧFWKӵFKLӋQQKѭVDX p q q sp   s 7DPÿRҥQOXұQ mà sp (PP phӫÿӏQK mà p rr (PP khҷQJÿӏQK
KӃW OXұQ U Fùng vӟL JLҧ WKLӃW SKө r cho ta r  r  0 'R ÿy theo
SKѭѫQJSKiSSKҧQFKӭQJFKӭQJPLQKEDQÿҫXOjÿ~QJ
 Quy tҳFFKӭQJPLQKWKHRWUѭӡQJKӧS
Quy tҳFQj\ÿѭӧFWKӇKLӋQEҵQJKҵQJÿ~QJVDX
 p r  q r   p q  r    
Ý nghƭDFӫDTX\WҳFQày là nӃXPӝWJLҧWKLӃWFyWKӇWiFUDWKjQKKDLWUѭӡQJKӧS
Sÿ~QJKD\Tÿ~QJYjWDÿã chӭQJPLQKÿѭӧFULêng rӁFKRWӯQJWUѭӡQJKӧSOà
kӃWOXұQUÿ~QJNKLҩ\UFNJQJÿ~QJWURQJFҧKDLWUѭӡQJKӧS
Ví dụ. ĈӇ FKӭQJPLQKUҵQJ IQ QQ OX{QFKLDKӃWFKR vӟLPӑLVӕ Wӵ
QKLrQQWD[pWKDLWUѭӡQJKӧSOà n chҹQQOҿYà thҩ\UҵQJWURQJFҧKDLWUѭӡQJKӧS
f(n) luôn chia hӃWFKR9ұ\WDU~WUDNӃWOXұQFҫQFKӭQJPLQKOà f(n) luôn chia hӃW cho 2 vӟLPӑLVӕWӵQKLên n.
7UrQÿk\OjPӝWVӕTX\WҳFVX\GLӉQWDWKѭӡQJGùng trong các quá trình suy luұQ
6DXÿk\WDVӁ[pWPӝWYtGөFөWKӇFyVӱGөQJNӃWKӧSQKLӅXTX\WҳFVX\GLӉQ
Ví dụ. KiӇPWUDVX\OXұQVDXÿ~QJKD\VDL“Nếu nghệ sĩ Văn Ba không trình diễn
hay số vé bán ra ít hơn 50 vé thì đêm diễn sẽ bị hủy bỏ và Ông bầu sẽ rất buồn. Nếu

đêm diễn bị hủy bỏ thì phải trả lại vé cho người xem. Nhưng tiền vé đã không được
trả lại cho người xem. Vậy nghệ sĩ Văn Ba đã trình diễn”
.
ĈӇNLӇPWUDVX\OXұQWUên, ta thay các mӋQKÿӅQJX\ên thӫ\EҵQJFiFELӃQPӋQKÿӅ
p: “nghӋVƭ9ăQ%Dÿã trình diӉQ´ Trang 10
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0 q: “sӕYpEiQUDtWKѫQYp´ r: ³ÿrPGLӉQEӏKӫ\Eӓ´ s: “ông BҫXUҩWEXӗQ´
t: “trҧWLӅQYpOҥLFKRQJѭӡL[HP´
TӯÿyVX\OXұQEDQÿҫXFyWKӇP{Kình nhѭVDX  p
  q  r sr ttp
Suy luұQWUên có thӇÿѭӧFWKӵFKLӋQWKHRFiFEѭӟFVDX  p
  q  r s ( tiӅQÿӅ
r s  r (hҵQJÿ~QJ r t (tiӅQÿӅ  p
  q  t
(tam đoạn luận mở rộng) mà t (tiӅQÿӅ p q
(phương pháp phủ định và luật De Morgan) mà  p q    p (hҵQJÿ~QJ  p
(phương pháp khẳng định)
Vұ\VX\OXұQEDQÿҫXOà chính xác.
1.2 Vị từ - Lượng từ
Định nghĩa. MӝWYӏWӯOà mӝWNKҷQJÿӏQKS[\«WURQJÿyFyFKӭDPӝWVӕELӃQ
x,y, … lҩ\JLiWUӏWURQJQKӳQJWұSKӧSFKRWUѭӟF$%«VDRFKR
i. BҧQWKkQS[\«NK{QJSKҧLOà mӋQKÿӅ
ii. NӃX WKD\ [ \ « EҵQJ QKӳQJ a A , b B , …ta sӁ ÿѭӧF PӝW PӋQK ÿӅ
p(a,b,…) nghƭDlà chân trӏFӫDQyKRjQWRjQ[iFÿӏQK&iFELӃQ[\«ÿѭӧF nói là biӃQWӵGRFӫDYӏWӯ Ví dụ.
a. p(n) = “n là sӕQJX\ên tӕ´Oà mӝWYӏWӯWKHRELӃQWӵGR n   , vӟLQ
WDÿѭӧFFiFPӋQKÿӅÿ~QJSSSFòn vӟLQ WDÿѭӧF các mӋQKÿӅVDLSSS
b. q(x,y) = “x + y là sӕOҿ´Oà vӏWӯWKHRELӃQWӵGR x, y   , chҷQJKҥQT
là mӝWPӋQKÿӅÿ~QJT-3, -7) là mӝWPӋQKÿӅVDL« Trang 11
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Định nghĩa. &KRWUѭӟFFiFYӏWӯS[T[WKeo mӝWELӃQ xA.KLÿy
i. PhӫÿӏQKFӫDSNêKLӋXOà p
 là vӏWӯWKHRELӃQ[Pà khi thay x bҵQJPӝW
phҫQWӱDFӕÿӏQKFӫD$WKì ta ÿѭӧFPӋQKÿӅ  pa .
ii. Phéo nӕLOLӅQWѭѫQJӭQJQӕLUӡLNéo theo, …) cӫDSYà q, ký hiӋXEӣL p q
( p q , p q , …) là vӏWӯWKHRELӃQ[Pà khi thay x bҵQJPӝWSKҫQWӱDFӕ
ÿӏQKFӫD$WKì ta ÿѭӧFPӋQKÿӅ pa  qa  p(a)  q(a), p(a)  q(a),...
Ví dụ: p(x) = “x là sӕQJX\ên tӕ´T[ ³[Oà sӕFKҹQ´.KLÿyWDFy
 PhӫÿӏQKFӫDS p(x) = “x không là sӕQJX\ên tӕ´
 Phép nӕLOLӅQFӫDSYà q: p q(x) = “x là sӕQJX\ên tӕYD[Oà sӕ chҹQ´  . . .
Định nghĩa. Các mӋQKÿӅ³ x   ,
A p(x) ” và “ x   ,
A p(x) ´ÿѭӧFJӑLOjOѭӧQJWӯKyD
cӫDYӏWӯS[EӣLOѭӧQJWӯSKәGөQJ  YjOѭӧQJWӯWӗQWҥL  ). Chú ý:
a. Trong các mӋQKÿӅOѭӧQJWӯKyDELӃQ[NK{QJFòn là biӃQWӵGRQӳDWDQyL
nó bӏEXӝFEӣLFiFOѭӧQJWӯ  hay  . b. MӋQKÿӅ x   ,
A p(x) sӁÿ~QJQӃXWKD\[EҵQJJLiWUӏDEҩWNǤQKѭQJFӕÿӏQK
trong A, p(a) luôn là mӋQKÿӅÿ~QJ c. MӋQK ÿӅ x   ,
A p(x) sӁ ÿ~QJ QӃX Fy PӝW JLi WUӏ D WURQJ $ VDR FKR SD Oà mӋQKÿӅÿ~QJ
Xét mӝWYӏWӯS[\WKHRKDLELӃQ x  ,
A y B . Khi ҩ\QӃXWKD\[EҵQJPӝWSKҫQWӱ
cӕÿӏQKQKѭQJW\ý a A , ta sӁÿѭӧFPӝWYӏWӯSD\WKHRELӃQ\.KLÿyWDFyWKӇ
OѭӧQJ Wӯ KyD Qy WKHR ELӃQ \ Yj ÿѭӧF KDL PӋQK ÿӅ VDX ³ y
  B, p(a, y) ” và “ y
  B, p(a, y) ”'R[ÿѭӧFWKD\EҵQJPӝWSKҫQWӱFӕÿӏQKQKѭQJW\ý a cӫD$
nên ta có hai vӏ Wӯ VDX ÿk\ Oà hai vӏ Wӯ WKHR ELӃQ x A: “ y
  B, p(x, y) ” và “ y
  B, p(x, y) ”. TiӃSWөFOѭӧQJWӯKyDKDLYӏWӯWUên theo biӃQ[WDÿѭӧFPӋQKÿӅ VDXÿk\ x   , A y
  B, p(x, y) x   , A y
  B, p(x, y) x   , A y
  B, p(x, y) x   , A y
  B, p(x, y)
7ѭѫQJ Wӵ WDFNJQJFyWKӇ OѭӧQJWӯ KyDS[\ WKHR ELӃQ[WUѭӟF UӗLELӃQ \VDX ÿӇ ÿѭӧFPӋQKÿӅQӳD y
  B, x  , A p(x, y) y   B, x   , A p(x, y) y
  B, x  , A p(x, y) y   B, x   , A p(x, y) Trang 12
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Câu hӓL ÿһW UD O~F Qày là liӋX WKӭ Wӵ OѭӧQJ Wӯ KyDFy TXDQ WUӑQJ KD\ NK{QJ"1yL
cách khác, các mӋQKÿӅWѭѫQJӭQJFyWѭѫQJÿѭѫQJORJLFYӟLQKDXNK{QJ"ĈӏQKOê
sau sӁÿӅFұSÿӃQYҩQÿӅQày
Định lý. NӃXS[\Oà mӝt vӏWӯWKHRELӃQ[\WKì ta có các ÿLӅXVDX i. x   , A y
  B, p(x, y)  y
  B, x  , A p(x, y) ii. x   , A y
  B, p(x, y)  y   B, x   , A p(x, y) iii. x   , A y
  B, p(x, y)  y
  B, x  , A p(x, y)
Chứng minh. Xem tài liӋXWKDPNKҧR>@
CNJQJ WѭѫQJ Wӵ FiFK OjP QKѭ WUrQ WD Fy WKӇ Pӣ UӝQJ GӉ Gàng cho các vӏ Wӯ WKHR nhiӅXELӃQWӵGRĈһFELӋWWDFy
Mệnh đề. Trong mӝWPӋQKÿӅOѭӧQJ tӯKyDWӯPӝWYӏWӯWKHRQKLӅXELӃQÿӝFOұS
nӃXWDKRiQYӏKDLOѭӧQJWӯÿӭQJFҥQKQKDXWKì: i.
MӋQKÿӅPӟLYүQFòn tѭѫQJÿѭѫQJORJLFYӟLPӋQKÿӅFNJQӃXKDLOѭӧQJ tӯQày cùng loҥL ii.
MӋQKÿӅPӟLVӁOà hӋTXҧORJLFFӫD PӋQKÿӅFNJQӃXKDLOѭӧQJWӯWUѭӟF khi hoán vӏFyGҥQJ 
ĈӏQKOêVDXVӁFKRFK~QJWDELӃWFiFKOҩ\SKӫÿӏQKFӫDPӝWPӋQKÿӅOѭӧQJWӯKyD
Định lý. PhӫÿӏQKFӫDPӝWPӋQKÿӅOѭӧQJWӯKyDWӯYӏWӯS[\«FyÿѭӧFEҵQJ
FiFKWKD\OѭӧQJWӯ bӣLOѭӧQJ tӯ  WKD\OѭӧQJWӯ  bҵQJOѭӧQJWӯ và thay vӏWӯ
p(x,y,…) bҵQJSKӫÿӏQK  p(x,y,…).
Ví dụ. Phӫ ÿӏQK FӫD PӋQK ÿӅ ³ x
  ,y   , x + y là sӕ FKҹQ´ Oà mӋQK ÿӅ “ x   , y
  , x+y không là sӕFKҹQ´.
Quy tắc đặc biệt hóa phổ dụng:
“Nếu một mệnh đề đúng có dạng lượng từ hóa, trong đó một biến x A bị buộc bởi
lượng từ phổ dụng , khi đó nếu thay x bằng aA ta sẽ được một mệnh đề đúng”.
Ví dụ. Ta có mӋQKÿӅÿ~QJVDX³ n
  ,n(n 1)2 ´NKLÿyQӃXWKD\QEҵQJVӕWӵ
nhiên bҩWNǤFKҷQJKҥQQ NK{QJFҫQNLӇPWUDOҥLWDFNJQJFKҳFFKҳQUҵQJPӋQK
ÿӅ³*(5+1)2” là mӋQKÿӅÿ~QJ Trang 13
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
1.3 Nguyên lý quy nạp Nguyên lý quy nạp: Mệnh đề “ n
  , p(n) ” là hệ quả logic của “ p(0)  n
  , p(n)  p(n 1)
Nguyên lý quy nҥSÿѭӧFFөWKӇKyDWKjQKSKѭѫQJSKiSFKӭQJ PLQKTX\QҥSQKѭ
sau: GiҧVӱ WDSKҧLFKӭQJ PLQK PӋQKÿӅ n
  , p(n) NKLÿyWDVӁWKӵFKLӋQFiF EѭӟFVDX
%ѭӟF.LӇPWUDSOà mӋQKÿӅÿ~QJWURQJWKӵFWӃWDFyWKӇEҳWÿҫXEҵQJ
giá trӏQKӓQKҩWFyWKӇÿѭӧFFӫDQNK{QJQKҩWWKLӃWSKҧLEҳWÿҫXWӯ0)
%ѭӟF 9ӟL QEҩW NǤJLҧ Vӱ SQ Oà mӋQK ÿӅÿ~QJ WDVӁ SKҧL FKӭQJPLQK p(n+1) cNJQJOà mӋQKÿӅÿ~QJ n(n 1)
Ví dụ. ĈӇ FKӭQJ PLQK n
   , 0 1... n  ,ta xét vӏ Wӯ SQ 2 n(n 1)
“ 0 1 ...  n  ”. Ta có: 2  0.1 p(0) = “ 0 
´ÿk\Uõ ràng là mӝWPӋQKÿӅÿ~QJ 2
 Xét n là sӕWӵQKLên bҩWNǤJLҧVӱSQOà mӋQKÿӅÿ~QJnghƭDOà ta có: n(n 1) 0 1 ...  n  2
ta sӁFKӭQJPLQKSQFNJQJÿ~QJ7KұWYұ\WDFy n(n 1) n   1 (n 1)   1
0 1 ...  n  (n 1)   (n 1)  2 2
suy ra p(n+1) là mӋQKÿӅÿ~QJ
Theo nguyên lý quy nҥSWDFyÿLӅXSKҧLFKӭQJPLQK Trang 14
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
2 Chương 2. Phép đếm
2.1 Tập hợp – Tính chất
7URQJFKѭѫQJWUѭӟFFK~QJWDÿã mӝWYài lҫQVӱGөQJNKiLQLӋPWұSKӧSWURQJPӝW
sӕYtGөÿһFELӋWOjWURQJÿӏQKQJKƭDFӫDFiFOѭӧQJWӯ7URQJFKѭѫQJQj\WDVӁQyL rõ hѫQYӅNKiLQLӋPQày.
Trong toán hӑFWұSKӧSOà mӝWNKiLQLӋPFѫEҧQNK{QJWKӇÿӏQKQJKƭDWK{QJTXD
FiFÿӕLWѭӧQJNKiFÿѭӧF0ӝWFiFKWUӵFTXDQWұSKӧSOà mӝWNKiLQLӋPÿӇFKӍFiF
ÿӕLWѭӧQJÿѭӧFQKyPOҥLWKHRPӝWWtQKFKҩWQjRÿó. NӃXDOjÿӕLWѭӧQJFӫDWұSKӧS
A, ta viӃW a A , nӃXNK{QJWDYLӃW a  A .
ĈӇêUҵQJWӯ³WtQKFKҩW´ÿѭӧFKLӇXWKHRPӝWQJKƭDUӝQJUãi. Thông thѭӡQJQyVӁ
ÿѭӧFELӇXKLӋQEӣLPӝWYӏWӯS[WKHRPӝWELӃQ x U . Khi ҩ\WұSKӧSÿѭӧFNêKLӋX bӣL
A  x U p(x  ) 8ÿѭӧFJӑLOà tұSYNJWUө Ví dụ.
1. A  x   x 
2 ÿk\OjWұSKӧSFiFVӕWӵQKLên chҹQ 2. A   2
x   x  
5 ÿk\OjWұSKӧSFiFVӕQJX\ên có bìQKSKѭѫQJQKӓKѫQ
TұSKӧSFòn có thӇÿѭӧFELӇXGLӉQEҵQJFiFKOLӋWNê các phҫQWӱFӫDQy&KҷQJKҥQ
QKѭWұSKӧSWURQJPөFFӫDYtGөWUên có thӇÿѭӧFYLӃWOà: A = {-2,-1,0,1,2}.
TұSKӧSNK{QJFKӭDEҩWFӭSKҫQWӱQào gӑLOà tұSKӧSUӛQJYjÿѭӧFNêKLӋu là  .
Xét hai tұSKӧS$Yà B trong tұSYNJWUөU. Ta nói A là tұSKӧSFRQFӫD%KD\$ chӭDWURQJ%QӃX x
 U, x A x B . Ta có thӇKLӇXÿѫQJLҧQOà bҩWFӭSKҫQWӱ nào nҵPWURQJ$FNJQJQҵPWURQJ%
Ta có thӇVӱGөng các phép toán trên mӋQKÿӅYà vӏWӯÿӇÿӏQKQJKƭDFic phép toán
trên tұSKӧSQKѭSKpSKӧS  ), phép giao (  ) và phҫQEWKHRÿӏQKQJKƭDVDXÿk\:
Định nghĩa. GiҧVӱ$%Oà hai tұSKӧSFRQFӫDWұSKӧSvNJWUө8.KLҩ\
A B  x U (x  )
A  (x B  )
A B  x U (x  )
A  (x B  )
A  x U x   A Trang 15
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
ĈӏQKOêVDXVӁJLӟLWKLӋXFiFWtQKFKҩWFӫDFiFSKpSWRiQWUên tұSKӧS
Định lý. A, B, C là các tұSFRQWùy ý cӫD8WDFy i. Tính giao hoán:
A B=B A
A B B A ii. Tính kӃWKӧS
A   B C    A B  C
A   B C    A B  C iii. LuұW'H0RUJDQ
A B A B
A B A B iv. Tính phân phӕL
A   B C    A B   A C
A   B C    A B   A C  v. PhҫQWӱWUXQJKòa: A    A
A U A vi. PhҫQEù:
A A U A A   vii. Tính thӕQJWUӏ
A U U A     viii. Tính lNJ\ÿҷQJ
A A A
A A A ix. LuұWKҩSWKө
A   A B  A
A   A B  A
Chứng minh. Các tính chҩWWUrQÿѭӧFVX\UDWӯÿӏQKQJKƭDYà các quy luұWORJLF
Chú ý. Ta có thӇOҩ\KӧSKRһFJLDRFӫDQKLӅXWұSKӧSYà ký hiӋXQKѭVDX n
A A A ...  Ai 1 2 n i 1  n
A A A  ...  Ai 1 2 n i 1  Trang 16
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0 2.2 Ánh xạ Định nghĩa.
i. MӝWiQK[ҥIWӯWұSKӧS$Yào tұSKӧS%OjSKpSWѭѫQJӭQJOLên kӃWPӛLSKҫQ
tӱ[FӫD$YӟLPӝWSKҫQWӱGX\QKҩW\FӫD%Pà ta ký kiӋXOà f(x) và gӑLOà ҧQK cӫD[EӣLI7DYLӃW
f : A B
x f (x) ii.
Hai ánh xҥ I Yà g tӯ $ YjR % ÿѭӧF QyL Oà bҵQJ QKDX QӃX x   ,
A f (x)  g(x) Định nghĩa. i.
NӃX(Oà mӝWWұSKӧSFRQFӫD$WKì ҧQKFӫD(EӣLIOà tұSKӧS
f (E)  y B x  ,
A y f (x
)   f (x) x E ii.
NӃX)Oà mӝWWұSKӧSFRQFӫD%WKì ҧQKQJѭӧFFӫD)TXDiQK[ҥIOà tұS hӧS 1
f  (F )  x A f (x)  FChú ý:
1. NӃX y B ta viӃW 1 f    y  1 f   ( y) 2. NӃX 1 f
( y)   thì y không nҵPWURQJҧQKI$FӫD$ 3. NӃX 1 f
( y)  {x} thì x là phҫQWӱGX\QKҩWFyҧQKOà y.
Định nghĩa. GӑLf là mӝWiQK[ҥWӯWұS$Yà tұS%.KLҩ\WDQyL i.
ftoàn ánh nӃXf(A)=B ii.
f đơn ánh nӃXKDLSKҫQWӱNKiFQKDXEҩWNǤFӫD$FyҧQKNKiFQKDX nghƭDOà: x  , x ' ,
A x x '  f (x)  f (x ') iii.
fsong ánh nӃXQyYӯDÿѫQiQKYӯDWRiQiQK
Xét f là mӝWVRQJiQKWӯA lên B, NKLÿyYӟLPӛL y B tùy ý, sӁFyGX\QKҩWPӝW
phҫQWӱ x A sao cho f(x)=y1KѭWKӃWѭѫQJӭQJ y x là mӝWiQK[ҥWӯ%Yào A mà ta ký hiӋX Oà 1 f
và gӑL Oà ánh xҥ QJѭӧF FӫD iQK [ҥ f. Ta có: 1
f  ( y)  x f (x)  y .
Ta có tính chҩWFӫDiQK[ҥQJѭӧFQKѭVDX 1 f ( f
( y))  y, y B 1
f  ( f (x))  x, x A
ĈӏQKQJKƭD&KRKDLiQK[ҥ f : A B g : B'  C WURQJÿy B B '. Ánh xҥKӧS
h là ánh xҥWӯ$Yào C ÿѭӧF[iFÿӏQKEӣL Trang 17
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
h : A C
x h(x)  g( f (x))
Ta ký hiӋX h f g .
Các tính chất của ánh xạ:
Định lý. Cho f là mӝWiQK[ҥWӯWұS$Yào tұS%(1 và E2 là hai tұSFRQWùy ý cӫD
A, F1 và F2 là hai tұSFRQWùy ý cӫD%7DFy
i. f (E E )  f (E )  f (E ) 1 2 1 2
ii. f (E E )  f (E )  f (E ) 1 2 1 2 iii. 1  1 f
(F F )  f
(F )  f (F ) 1 2 1 2 iv. 1  1 f
(F F )  f
(F )  f (F ) 1 2 1 2
2.3 Giải tích tổ hợp
3KpSÿӃPFiFSKҫQWӱFӫDPӝWWұSKӧS$FKtQKOà tìm mӝWVRQJiQKJLӳD$Yà mӝW
tұSFRQ{1,2,…,n} cӫD N. NӃX$KӳXKҥQWKì n chính là sӕSKҫQWӱFӫDQyĈӏQK
nghƭDVDXÿk\VӁÿӅFұSÿӃQYҩQÿӅQày: Định nghĩa.
i. MӝWWұSKӧS$ÿѭӧFQyLOà hӳXKҥQYà có n phҫQWӱQӃXWӗQWҥLPӝWVRQJiQK
giӳD$Yà tұSKӧSFRQ{1,2,...,n} cӫD N. Khi ÿyWDYLӃW A n .
ii. NӃX$NK{QJKӳXKҥQWDQyL$Y{KҥQ
2.3.1 Các nguyên lý cơ bản của phép đếm:
Nguyên lý cộng: NӃXPӝWF{QJYLӋFFyWKӇÿѭӧFWKӵFKLӋQEҵQJPӝWWURQJQFiFK loҥLWUӯOүQQKDXN 7URQJÿyÿӇWKӵFKLӋQWKHRF SKѭѫQJ 1, k2, …, kn ách ki lҥLFyWi
iQNKiFQKDXL Q.KLÿyWәQJVӕSKѭѫQJiQÿӇWKӵFKLӋQF{QJYLӋFEDQÿҫXOà: t1 + t2 + … + tn.
Ví dụ: ĈӇÿLWӯ7S+&0UD+à NӝLFyFiFKÿL{W{ÿLWàu hӓDKRһFÿLPi\ED\
ĈLEҵQJ{W{FyFiFKÿLWD[LÿL[Hÿò, thuê xe ULrQJĈLEҵQJWàu hӓDFyFiFKÿL
bҵQJWjXQKDQKYjÿLEҵQJWàu bình thѭӡQJĈLEҵQJPi\ED\FNJQJFyKDLFiFKÿL
bҵQJ9LHWQDPDLUOLQHKRһFÿLEҵQJ3DcLILFDLUOLQH1KѭYұ\WәQJFӝQJFy FiFKÿLWӯ7S+&0UD+à NӝL Trang 18
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0
Nguyên lý cộng mở rộng:
i. Cho A và B là hai tұSKӧSEҩWNǤNKLÿyWDFy
A B A B A B
ii. Cho A1, A2, …, An là n tұSKӧSEҩWNǤ. Ta có: 1 A A ... A N N ... ( 1)n         N 1 2 n 1 2 n
WURQJÿy1k là tәQJVӕSKҫQWӱFӫDFiFWҩWFҧFiFSKҫQJLDRFӫDNWұSEҩWNǤWURQJVӕ n tұSEDQÿҫX
Ví dụ. VӟLWұS$%&Q WKHRQJX\ên lý cӝQJWәQJTXiWWDFyF{QJWKӭFVDX
A B C   A B C    A B B C C A   A B C
Nguyên lý nhân: NӃXPӝWF{QJYLӋFphҧL thӵFKLӋQÿѭӧFWKHRQJLDLÿRҥQliên tiӃS nhau: k FiFKÿӇ
1, k2, …, kn. MӛLJLDLÿRҥQNi có ti
thӵFKLӋQ1KѭYұ\VӁFyt1.t2…tn
FiFKNKiFQKDXÿӇWKӵFKLӋQF{QJYLӋFEDQÿҫX
Ví dụ. MӝWQJѭӡLFyFiLiRVѫ-mi khác nhau, 2 cái quҫQGjLNKiFQKDXYjÿ{L
JLj\NKiFQKDX1KѭYұ\FyWҩWFҧ EӝWUDQJSKөFNKiFQKDXÿӇQJѭӡLQày lӵDFKӑQNKLPһF
Định nghĩa. 7tFKĈӅ-các cӫDWұSKӧS$%NêKLӋXOà AB là tұSKӧSWҩWFҧFiF
cһSWKӭWӵDEYӟL a A b B WURQJÿyKDLFһSDEYjD¶E¶ÿѭӧFQyLOà bҵQJ
nhau nӃXYà chӍQӃXD D¶Yà b=b’.
ĈӏQKOê1ӃX$Yà B là hai tұSKӧSKӳXKҥQWKì AB cNJQJOà tұSKӧSKӳXKҥQYà ta có:
AB A . B
2.3.2 Giải tích tổ hợp Hoán vị.
Định nghĩa. Cho n vұWNKiFQKDX0ӝWKRiQYӏFӫDQYұWQày là mӝWFiFKVҳS[ӃS chúng theo mӝWFiFKQjRÿy
Mệnh đề. SӕFiFKRiQYӏFӫDQYұWNKiFQKDXOà: P n!  1.2.3...n . n
Chứng minh. Ta chӭQJ PLQK F{QJ WKӭF Qày dӵD WUên nguyên lý nhân. Xét công
viӋF[k\GӵQJPӝWKRiQYӏFӫDQYұWEDQÿҫX &{QJYLӋFQj\ÿѭӧFFKLDWKành các EѭӟFVDX -
%ѭӟF&KӑQYұWÿӭQJÿҫXFyQFiFKFKӑQQYұWÿӅXFyWKӇÿӭQJÿҫX -
%ѭӟF&KӑQYұWÿӭQJWKӭKDLFyQ-1 cách chӑQGRÿã chӑQYұWÿӭQJÿҫX
nên bây giӡWDFKӍFòn n-1 vұW - … Trang 19
Tóm tҳWEài giҧQJ7RiQUӡLUҥF 7UѭӡQJĈ+6373+&0 -
%ѭӟFQ&KӑQYұWFòn lҥLFXӕLFùng: chӍFyFiFKGX\QKҩW
1KѭYұ\ theo nguyên lý nhân, sӕFiFK[k\GӵQJKRiQYӏFNJQJFKtQKOà sӕFiFKRiQ
vӏFӫDQYұWEDQÿҫXOà n.(n-1)…2.1 = n!. 
Ví dụ. SӕFiFVӕWӵQKLên có 5 chӳVӕNKiFQKDXÿѭӧFWҥRWӯFiFFKӳVӕ là 5! = 120 cách. Hoán vị lặp
Hoán vӏOһSFNJQJPDQg ý nghƭDQKѭKRiQYӏÿLӅXNKiFELӋWӣÿk\Oà trong n vұWEDQ
ÿҫXFyQKLӅXYұWJLӕQJQKDX MӋQKÿӅVDXÿk\VӁFKRFK~QJWDELӃWF{QJWKӭFÿӇ tính hoán vӏOһS
Mệnh đề. Cho n vұWWURQJÿyFyW1 vұWORҥLJLӕQJQKDXW2 vұWORҥLJLӕQJQKDX
…, tk vұWOoҥLNJLӕQJQKDX.KLÿyVӕFiFKRiQYӏNKiFQKDXFӫDQYұWEDQÿҫXOà n! .
t !t !...t ! 1 2 k
Chứng minh. ĈҫX WLên, nӃX [HP QKѭ Q YұW Oà khác nhau, ta có n! hoán vӏ 7X\
nhiên do có t1 vұWORҥLJLӕQJQKDXQên ӭQJYӟLPӝWKRiQYӏEDQÿҫXQӃXWDhoán
vӏW1 phҫQWӱQày (có t1! hoán vӏQKѭYұ\WDYүQÿѭӧFKRiQYӏÿy&KtQKYì vұ\WKӵF
chҩWW1! hoán vӏNLӇXQày chӍOà mӝWKRiQYӏ'RÿyVӕKRiQYӏWKӵFVӵNKiFQKDX n!
nӃXFyW1 vұWORҥLJLӕQJQKDXFKӍFòn là:
. TiӃSWKHRWa lҥLFyW2 phҫQWӱORҥL t ! 1 n!
giӕQJQKDXQên sӕKRiQYӏWKӵFVӵNKiFQKDXEk\JLӡVӁOà . CӭWLӃSWөFQKѭ t !t ! 1 2
vұ\FKRÿӃQNKLNӃWWK~FWDVӁÿѭӧFF{QJWKӭFFҫQFKӭQJPLQKWURQJPӋQKÿӅ 
Ví dụ: SӕFiFVӕWӵQKLên có 6 chӳVӕWURQJ ÿyEҳWEXӝFSKҧLFyFKӳVӕFKӳ 6! sӕYà 1 chӳVӕOà:  60 . 3!2!1! Chỉnh hợp
Định nghĩa. Cho n vұWNKiFQKDX0ӝWFKӍQKKӧSFKұSNFӫDQYұWQày là mӝWFiFK
chӑQNYұWkhác nhau có kӇÿӃQWKӭWӵWURQJVӕQYұWÿy n k !
Mệnh đề. SӕFKӍQKKӧSFKұSNFӫDQYұWNKiFQKDXOà: A n (n k)!
Chứng minh. Dùng nguyên lý nhân. Trang 20