Công thức tổng hợp Môn Toán rời rạc | Đại học Cần Thơ

lOMoAR cPSD| 58488183
Chương 1: Phép đếm I. Nguyên lý đếm:
- Nguyên lý cộng: sử dụng khi các giai đoạn đã kết thúc.
- Nguyên lý nhân: sử dụng khi các gia đoạn được chia nhỏ chưa kêt thúc. - Nguyên lý bù trừ:
|A ∪ B| = |A| +|B| - |A∩B| II.
Hoán vị, chỉnh hợp , tổ hợp: Loại Lặp Công thức Hóan vị Không P=n! Chỉnh hợp chập k Không n!
(n−k )! Tổ hợp chập k Không n!
k !(n−k )! Hóan vị Có n! n1!.n2!…nk!¿ ¿ Chỉnh hợp chập k Có nk Tổ hợp chập k Có
(n+k−1)! k
!(n−1)!
Chương 2: Mệnh đề và vị từ I. Mệnh đề:
1. Phép tính mệnh đề: - Phép phủ định: P ¬P T F F T - Phép hội (^); P Q PQ T T T T F F F T F F F F lOMoAR cPSD| 58488183 - Phép tuyển (v): P Q PvQ T T T T F T F T T F F F - Phép XOR: P Q PxorQ T T F T F T F T T F F F - Phép kéo theo: P Q P→Q T T T T F F F T T F F T
¬Q→¬P : là phản đảo của P-> Q; - Phepstươngđương: P Q P↔Q T T T T F F F T F F F T 2. Công thức TDLG: 1. {PPvFT==FT 2. {PPvTF==PP 3. { ❑
ppv❑ pp==pp 4. ¬¬ P=P lOMoAR cPSD| 58488183
5. {PPv❑❑¬¬PP==FT
6. {PvPQQ==QQPv P 7. ) PvQ v R= P v
¿ (P vQQ Rv R=(Q ❑❑R ) (Qv R)
P =(P ) =P
Pv(QR)=(P v Q) ^ (P v R) {8. (QvR) Q R P
=(P )v(P ) 9.
{PQvQ=¬P¬Q P =¬Pv¬Q 10. {Pv Q
(P(PvQ ))=P P =P
11. P Q = ¬P vQ II. Vị từ:
Chương 3: Quy tắc suy luận I. Các quy tắc
- Cộng: P→(PvQ) - Rút gọn: (P ^ Q) P
- Khẳng định: (P ^ (P Q)) Q
- Phủ định: (Q ^ (P Q)) ¬P
- Tam đoạn luận giả định: ((P Q)^(Q R)) (P R)
- Tam đoạn luận ttuyể: ((PvQ)^P) Q II. Các phương pháp chứng minh:
1. Chứng minh rỗng (P là sai):
Để P Q = T thì ta cần chứng minh P là F.
2. Chứng minh tầm thường (Q là đúng)
Ta chỉ cần chứng minh Q là T thì suy ra điều ccaanf chứng minh T.
3. Chứng minh trực tiếp:
- Giả sủ P là đúng sau đó dùng các quy tắc suy luận và TDLG chứng minh Q là T. 4. Chứng minh gián tiếp: P Q = Q→P lOMoAR cPSD| 58488183
Chứng minh vế phải là đúng;
5. Chứng minh phản chứng: 6. Chứng minh quy nạp:
- Kiểm trức P(n) dúng với n= n0.
- Giả sự P(n) đứng với n: n 0 <= n <= k chứng minh P(n) ddungs voiws n = k+1.
- Kết luận ∀n≥n0P(n) là đúng.
Chương 4: Quan hệ I. Biểu diễn: - Theo giản đồ - Dùng bảng Descartes - Dùng ma trận II.
Tính chất quan hệ 2 ngôi: 1. Tính chất trên tập hợp:
a. Quan hệ phản hồi: ∀a∈ A,aRa b. Quan hệ đối xứng:
∀a,b∈ A,nếuaRbthìbRa
c. Quan hệ phản đối xứng: ∀a,b∈ A,nếuaRb vàbRathìa=b d. Quan hệ bấc cầu:
∀a,b,c∈ A ,nếu (aRbvàbRc )thìaRc III. Quan hệ tương đương:
- Bao gồm 3 tính chất: phản hồi , đối xứng, bắc cầu. IV. Quan hệ thứ tự:
- Bao gồm 3 tính chất: Phản hồi , phản đối xứng, bắc cầu. Chương 5: Hàm Bool I.
Dạng tuyển chuản tắc và hội chuận tắc: 1. Tuyển chuẩn tắc: - Lập bct của f.
- Mỗi lần f nhận giá trị 1 tại các bit thì:
+ Viét tích của các biến.
+ Đặt dấu bù lên biến có bit là 0.
- Viết f bằng tổng của các tích vuawf tìm. 2. Hội chuẩn tắc: - Lập bct của f.
- Mỗi lần f nhận giá trị 0 tại các bit thì: lOMoAR cPSD| 58488183
+ Viét tổng của các biến.
+ Đặt dấu bù lên biến có bit là 1.
- Viết f bằng tích của các tổng vừa tìm. II.
Hệ phương trình bool và phủ tối tiểu:
1. Phương pháp giải hệ phương trình bool:
- Biến các vế của phongw trình thành dạng
tổng và tích ủa các biến.
- Chuyển đổi để có dang A=1: CT: (G=D) (1 =
GD v G D). - Nhân tất cả với nhau: F1 F2 ... F3
=1 - Rút gọn biểu thức trên.
- Phân tích các tổng ra 2. Phủ tối tiểu:
Lập hệ phương trình bool và giải (VD trang 59 – 60). Chương 6 lý
thuyết chia và đồng dư: I. Phép chia hết và có dư:
1.Tính chất phép chia hết:
- B|A ±B∨± A
- ∀a≠0a∨a - ∀a±1∨a - ∀a≠0a∨0
- (a|b) và b|a) khi và chỉ khi a=±b - Nếu (a|b và b|c) thì a|c.
- Nếu c|a và c|b thì c|(ax+by)
- Nếu a|x và b|y thì ax|by 2. Phép chia cho dư:
a,b∈Z vàb≠0 ¿ II.
Ước chung lớn nhất và bội chung nhỏ nhất: 1. Ước chung lớn nhất: - Tính chất (tr70).
- Thuật toán Euclide tìm UCLN: (a,b) =(b,r) 2. Bội chung nhỏ nhất:
[a, b]= ¿ab∨(a¿,b)¿ - Tính chất (tr72). III. Phương trình nguyên:
1. Bậc nhất 2 ẩn: ax +by = c d= (a,b)
Nếu d không là ước của c thì pt vô nghiệm. lOMoAR cPSD| 58488183
Ngược laij,phoungw trình có vô số nghiệm. b x=x0+ t d a
y=y0− t
d Giải trưcj tiếp ( xem vid dụ trang 77). 2.Bậc nhất nhiều ẩn.
Đặt ẩn phụ đưa về dạng 2 ẩn để giải. IV. Quan hệ đồng dư lOMoAR cPSD| 58488183 3. Lớp thạng du: lOMoAR cPSD| 58488183 V.
Phương trình đồng dư: lOMoAR cPSD| 58488183 VI.
Hệ phương trình đồng dư bậc nhất: lOMoAR cPSD| 58488183