Bài giảng Cấu trúc rời rạc - Phép đếm

Chia sẻ: Lê Tẹt | Ngày: | Loại File: PPT | Số trang:50

Thêm vào BST

Báo xấu

108
lượt xem 12
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tập hợp bằng nhau: Tập A được gọi là bằng tập B, nếu mọi phần tử của tập A đều là phần tử của tập B và ngược lại mọi phần tử của B đều là phần tử của A. ( x  A)  ( x  B) Tập con: Tập A được gọi là tập con của tập hợp X, nếu mọi phần tử của A đều là phần tử của X, kí hiệu là A X. (A  X)  ( x  A  x  X)

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc rời rạc - Phép đếm

LOGO Cấu trúc rời rạc Chương II Phép đếm Nhóm 7
Cấu trúc rời rạc Nội dung 1 Tập hợp 2 Phép đếm 3 Nhị thức Newton
I.Tập hợp  Tập hợp bằng nhau: Tập A được gọi là bằng tập B, nếu mọi phần tử của tập A đều là phần tử của tập B và ngược lại mọi phần tử của B đều là phần tử của A. (∀ x ∈ A) ↔ (∀ x ∈ B)  Tập con: Tập A được gọi là tập con của tập hợp X, nếu mọi phần tử của A đều là phần tử của X, kí hiệu là A ⊆X. (A ⊆ X) ↔ (∀ x ∈ A → x ∈ X)
Ví dụ : + A= {a, b, c,d}, X = {a, b, c, d, x, y, z} Khi đó A ⊆ X. + Z2={Tập các số chẵn},Z={Tập các số nguyên} Khi đó Z2 ⊆ Z. Nếu A là tập con của X và A không bằng X, thì A được gọi là tập con thực sự của tập X, kí hiệu là A ⊂X. X A Hình 1.1. Tập con
+ Tập rỗng: Tập hợp không chứa phần tử nào gọi là tập rỗng, kí hiệu là ∅. Tập rỗng là tập con của mọi tập hợp. Ví dụ 3: A= {Tập các nghiệm thực của phương trình: x2 +1= 0 } Khi đó A= ∅. + Tập các tập con: Tập tất cả các tập con của A bao gồm cả tập rỗng và A là một tập hợp. Kí hiệuText là p(A). Ví dụ 1.4 : Cho tập A= {2, 4, 6} p(A)= {{2}, {4}, {6}, {2, 4}, {2, 6}, {4, 6}, {2, 4, 6}, { ∅ }}
Các phép toán trên tập hợp. + Phép hợp: Hợp của hai tập hợp A và B là một tập hợp bao gồm các phần tử thuộc ít nhất một trong hai tập hợp đã cho. Kí hiệu là A ∪ B. x∈A ∪ B ⇔ x∈A ∨x∈B. A={1, 3, 5, 7} B A B={2, 3, 4, 5} A ∪ B ={1,2, 3, 4, 5, 7}
+ Phép giao: Giao của hai tập A và B là một tập hợp bao gồm các phần tử thuộc cả hai tập đã cho. Kí hiệu là A ∩ B . x∈ A ∩ B ⇔ x∈A ∧x∈B. A={1, 3, 5, 7} A B B={2, 3, 4, 5} A ∩ B ={3, 5}
+ Phép hiệu : Hiệu của hai tập hợp A và B là một tập hợp bao gôm các phần tử thuộc A nhưng không thuộc B. Kí hiệu: A \ B x∈A \ B ⇔ x∈A ∧x∉B. A={1, 3, 5, 7} B A B={2, 3, 4, 5} A \ B ={1,7}
+ Hiệu đối xứng: Hiệu đối xứng của hai tập hợp A và B là một tập hợp. Kí hiệu là: A ⊕ B x∈A ⊕ B ⇔ x∈ A ∪ B ∧x∉ A ∩ B . A={1, 3, 5, 7} B A B={2, 3, 4, 5} A ⊕ B ={1,2,4,7}
Phần bù :Cho A⊂E thì A= E \ A E={1, 2, 3, 4, 5, 6, 7} A E A={2, 3, 4, 5} A ={1,6,7}
Tích Descartes: A × B = {(a,b) | a∈A,b ∈B} A1× A2× …× An = {(a1,a2,…,an) | ai∈A i , i = 1,2,…,n} Tổng quát: ∏ A i = { (xi )i∈ I ∀ i ∈ I , xi ∈ A i } i∈ I
Tính chất của phép toán trên tập hợp 1) Tính luỹ đẳng: A ∩ A = A và A ∪ A = A 2) Tính giao hoán: A ∩ B = B ∩ A và A ∪ B = B ∪ A. 3) Tính kết hợp: (A ∩ B) ∩ C = A ∩ (B ∩ C) và (A ∪ B) ∪ C = A ∪ (B ∪ C)
4) Tính phân phối: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) và A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) 5) Công thức De Morgan: A ∩ B = A ∪ B vaø A ∪ B = A ∩ B Suy ra: A \ (B ∩ C) = (A \ B) ∪ (A \ C) và A \ (B ∪ C) = (A \ B) ∩ (A \ C).
• Lực lượng của tập hợp Cho A là tập hợp hữu hạn.Số phần tử của tập A ký hiệu là | A| .Ta có: 1) | A∪B| = | A| + | B| - | A∩B| . 2) | A× B| = | A| | B| 3) | P (A)| = 2 | A| ,P (A) là tập các tập con của A A={1, 3, 5, 7}; B={ 3, 5,6}; A∪B = {1,3,5,6,7}; A∩B={3,5} |A| = 4; |B| = 3; |A∪B | = 5; |A∩B| = 2 P (A)=24=16
• Các phương pháp chứng minh PP1: Chứng minh trực tiếp Áp dụng phép suy diễn logic: A1 → A2→ ... Ak → B VD: Với mọi n nguyên thì n2 – n + 5 là một số lẻ CM: Với mọi n nguyên: n(n-1) là một số chẵn → n(n-1) +5 = n2 – n + 5 là một số lẻ
• Các phương pháp chứng minh PP2: Chứng minh lựa chọn VD: CMR với mọi n nguyên, 9n2 + 3n – 2 là một số chẵn. CM: Ta có 9n2 + 3n – 2 = (3n+2) (3n-1). Xảy ra 2 TH - TH1: 3n+2 là số chẵn → (3n+2) (3n-1) là số chẵn - TH2: 3n+2 là số lẻ → (3n+2)-3 là số chẵn → (3n+2)(3n-1) là số chẵn
• Các phương pháp chứng minh PP3: Chứng minh phản chứng: Để chứng minh mệnh đề A đúng ta chỉ cần CMR phủ định của A là sai. Chú ý: Ta thường dựa vào công thức logic sau A→B=B→A VD: CMR nếu n là số nguyên và n2 chẵn thì n chẵn. Ta cần CM nếu n lẻ thì n2 lẻ. Mà n lẻ → n = 2m +1 → n2 = 4m2 + 4m + 1 là số lẻ
• Các phương pháp chứng minh PP4: Chứng minh quy nạp: CM mệnh đề “với mọi n ≥ n0 ta có P(n) đúng” - B1: Kiểm tra, CM P(n0) đúng - B2: Giả thiết rằng với n=k (k > n0), P(k) đúng, ta cần CM P(k+1) đúng Kết luận P(n) đúng với mọi n≥n0
• Các phương pháp chứng minh PP4: Chứng minh quy nạp: Áp dụng: Để đưa ra công thức tổng quát liên quan đến số tự nhiên n thường vận dụng theo hai bước - B1: Quy nạp không hoàn toàn: Để tìm và đưa ra công thức P(n) tổng quát - B2: Quy nạp hoàn toàn hay CM công thức P(n) đã dự đoán trên bằng PP quy nạp
II. Phép đếm 1. Nguyên lý cộng và nguyên lý nhân 1.1. Nguyên lý cộng. Nếu có m cách chọn x, n cách chọn đối tượng y và nếu cách chọn đối tượng x không trùng với bất kỳ cách chọn đối tượng y nào ,thì có m+n cách chọn 1 trong các đối tượng đã cho. 1.2. Nguyên lý nhân. Nếu có m cách chọn đối tượng x và cứ mỗi cách chọn x luôn luôn có n cách chọn đối tượng y thì có m.n cách chọn cặp đối tượng (x, y). 20