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

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)
Nội dung trích xuất từ tài liệu:
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 ...