[Toán rời rạc/Chương II] Cấu trúc cơ bản: Tập hợp, hàm, dãy và tổng

CHƯƠNG II: TẬP HỢP, HÀM, DÃY VÀ TỔNG

I, Tập hợp

- Định nghĩa:

+ Tập hợp là các đối tượng không có thứ tự

+ Mỗi đối tượng của 1 tập hợp gọi là 1 phần tử hoặc 1 thành viên của tập hợp đó

+ Các tính chất/lực lượng (Cardinality) của tập hợp A là số phần tử riêng biệt của A. KH: |A|

+ Tập rỗng là tập hợp có tính chất/lực lượng bằng 0 hay số phần tử bằng 0. KH: \(\emptyset\)

Ví dụ: {a, b, {a,b},c, {a,b,c}, \(\emptyset\)} có 6 phần tử 

* Tính chất: 

+ Nếu phần tử x là của A thì x \(\in\) A

    Nếu phần tử x không phải là của A thì x \(\notin\) A

+ Nếu tất cả phần tử của A đều là phần tử của B thì A \(\subseteq\) B

+ Nếu tất cả phần tử của A đều là phần tử của B nhưng A \(\neq\) B thì A \(\subset\) B

+ Tập rỗng là tập con của tất cả các tập hợp (hay nói cách khác là tất cả các tập hợp đều chứa tập rỗng)

Ví dụ: {x} \(\subseteq\) {x}; {a,b} \(\subseteq\) {a, b, {a,b}, c}

* Định lý: 

+ Tích Cartesion của 2 tập A và B, KH: AxB, là tập chứa tất cả các cặp có thứ tự (a,b) mà a \(\subset\) A và b\(\subset\) B

+ Tập lũy thừa của tập A, KH: P(A), là tập hợp các tập con của A

* Lưu ý: + Nếu |A| = m và |B| = n thì |AxB| = m.n

                + Nếu |A| = n thì |P(A)| = \(2^n\)

II, Phép toán trên tập hợp

- Cho tập A và tập B:

+ Hợp (Union) của A và B: A \(\cup\) B = {x | (x \(\in\) A) \(\vee\) (x \(\in\) B)}

+ Giao (Intersection) của A và B: A \(\cap\) B = {x | (x \(\in\) A) \(\wedge\) (x \(\in\) B)}

+ Hiệu (Difference) của A và B: A - B = {x | (x \(\in\) A) \(\wedge\) (x \(\notin\) B)}

+ Hiệu đối xứng (Symmetric difference) của A và B: A \(\oplus\) B = {x | (x \(\in\) A) \(\oplus\) (x \(\in\) B)}

+ Bù (Complement) của A và B: \(\overline{A}\) = U - A = {x | x \(\notin\) A}

* Lưu ý: U là tập vũ trụ (là tập chứa tất cả các giá trị) 

* Hằng đẳng thức trên tập hợp:

* Biểu diễn tập hợp trong máy tính

- Nếu A là tập con của U, biểu diễn A dưới dạng chuỗi bit có chiều dài là n, bit \(i^{th}\) là 1 nếu \(a_i\) trong A và là 0 nếu \(a_i\) không trong A

Ví dụ: Cho A = {1, 2, 3, 4, 5, 6, 7, 8} và tập con B = {1, 3, 4, 6} thì số bit được biểu diễn dưới dạng: 10110100

III, Hàm (Functions) (liên quan đến ánh xạ - mapping)

- Tập A (bên trái) gọi là tập nguồn (domain) của f

  Tập B (bên phải) gọi là tập đích (codomain) của f

- Nếu f(a) = b thì b gọi là ảnh (image) của a và a là nghịch ảnh (preimage) của b

- Cho S là tập con của A. Tập:

                            f(S) = { b \(\in\) B | \(\exists\)a\(\in\)A(f(a) = b) }

        là tập ảnh của S (tương tự tập giá trị)

- Tương tự, tập: \(f^{-1}(S)\) = { a \(\in\) A | f(a) \(\in\) S }

        là tập nghịch ảnh của S (tương tự tìm bất phương trình, phương trình)

* 1 số function quan trọng:

    + Floor function: \(\lfloor x \rfloor\) - làm tròn xuống

    + Ceiling function: \(\lceil x \rceil\) - làm tròn lên

* Lưu ý: x - 1 < \(\lfloor x \rfloor\) \(\leq\) x \(\leq\) \(\lceil x \rceil\) < x + 1

* Đơn ánh (One-to-One)

- Cho f: X \(\rightarrow\) Y là đơn ánh khi f(\(a_1\)) \(\neq\) f(\(a_2\)) với mọi \(a_1 \neq a_2\) trong X

* Toàn ánh (Onto)

- Cho f: X \(\rightarrow\) Y gọi là toán ánh nếu với mọi y thuộc tập Y luôn tìm được ít nhất 1 giá trị x trong tập X sao cho f(x) = y

* Song ánh (Bijection)

- Cho f: X \(\rightarrow\) Y được gọi là toàn ánh nếu nó vừa đơn ánh, vừa toàn ánh

* Lưu ý: Hàm f: X \(\rightarrow\) Y là khả nghịch khi và chỉ khi f song ánh

IV, Sequences and Summations (Dãy/chuỗi và tổng)

* Sequences: Là cấu trúc rời rạc được dùng để biểu diễn danh sách thứ tự

              Nó thường được biểu diễn dưới dạng: {\(a_1\), \(a_2\),...} = {\(a_n\); n = 1, 2, ...}

* Summations:

- Cho dãy{\(a_n\); n = 1, 2, ...}. Summation, KH: \( \sum\) được sử dụng\[ \sum_{i=1}^{100} a_i = a_1 + a_2 + \cdots + a_{100} \]\[ \sum_{i=1}^{100} a_{2i+1} = a_3 + a_5 + \cdots + a_{201} \] 

* Tính chất: 

+ \(\displaystyle \sum_{i=1}^{n} (a_{i} + b_i) =  \sum_{i=1}^{n} a_{i} +  \sum_{i=1}^{n} b_{i} \)

+  \(\displaystyle \sum_{i=1}^{n} k.a_{i} = k.\sum_{i=1}^{n} a_{i}\)

P/s: Bài tập và tài liệu nghiên cứu thêm (nếu cần) được tổng hợp ở link dưới sau:

https://drive.google.com/drive/folders/14OZeHi9WCX31a5KaQPFuhulbaXhNOzg0?usp=sharing