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: Cấu trúc rời rạc
Trường: Trường Đại học Công nghệ Thông tin, Đại học Quốc gia Thành phố Hồ Chí Minh
Thông tin:
Tác giả:
Thông tin :
Môn:
Trường:
Trường Đại học Công nghệ Thông tin, Đại học Quốc gia Thành phố Hồ Chí Minh
Tác giả:
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 P 0 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 và 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 q iii. 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 và
p q r p q r
vii. Luật lũy đẳng:
p p p và
p p p
viii. Luật trung hòa: p 1 p và p 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 và
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 pn q
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 r p 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 q q p
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 s p s 7DPÿRҥQOXұQ mà s p (PP phӫÿӏQK mà p r r (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 s r t t p
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 x A.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 a A 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 ... A i 1 2 n i 1 n và
A A A ... A i 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) F Chú ý:
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.
f là toàn ánh nӃXf(A)=B ii.
f là đơn ánh nӃXKDLSKҫQWӱNKiFQKDXEҩWNǤFӫD$FyҧQKNKiFQKDX nghƭDOà: x , x ' ,
A x x ' f (x) f (x ') iii.
f là song á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 và 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à A B là tұSKӧSWҩWFҧFiF
cһSWKӭWӵDEYӟL a A và 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ì A B cNJQJOà tұSKӧSKӳXKҥQYà 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ұ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