BÀI-GIẢNG-NHẬP-MÔN-TOÁN-CC (1)

BÀI-GIẢNG-NHẬP-MÔN-TOÁN-CC (1) Sjsisjsisjsjdjsisjdjsjxjejsjsudjeujxusjsjdjdjxjxjdie

LÝ THUYẾT TẬP HỢP 7 1.1 Khái niệm về tập hợp

Quan hệ

Cho X và A 1 , A 2 ,ã ã ã, A n là cỏc tập hợp Khi đú, cỏc khẳng định sau là đỳng:

(i) X∩(Sn i=1A i ) = Sn i=1(X∩A i ) (ii) X∪(Tn i=1A i ) =Tn i=1(X∪A i ) (iii) X\(Sn i=1A i ) =Tn i=1(X\A i ) (iv) X\(Tn i=1A i ) = Sn i=1(X\A i ). Định lý

1.1.9 Tập hợp các tập con của một tập hợp

Cho X là một tập hợp Nếu coi mỗi tập con của X là một phần tử thì ta có tập P(X) có các phần tử là các tập con củaX Nói một cách khác, P(X) = {A|A⊆X}.

1.2.1 Tích Descartes Định nghĩa 9: Tích Descartes của hai tập hợp A và B, kí hiệu A×B, là tập hợp tất cả các cặp (a, b),a trước b sau, được tạo nên do lấy a∈A, b∈B một cách bất kì Nói một cách khác

Cho A 1 , A 2 , , A n là các tập hợp.Tích Descartes của các tập hợpA 1 , A 2 , , A n , kí hiệu A 1 ×A 2 × ×A n , được xác định như sau:

A 1 ìA 2 ì ã ã ã ìA n ={(a 1 , a 2 , , a n )|a i ∈A i , i= 1, n}. Đặc biệt, nếu A 1 =A 2 = =A n =A thỡ tớch A 1 ìA 2 ì ã ã ã ìA n được kớ hiệu lại là A n

Một quan hệ m-ngôi trên tập X được định nghĩa là một tập con S của lũy thừa Descartes X m Nếu S là quan hệ m-ngôi trên X, thì khi (a1, a2, , am) thuộc S, ta có thể nói rằng a1, a2, , am có quan hệ S với nhau.

Quan hệ 2-ngôi được gọi vắn tắt là quan hệ Như vậy quan hệ 2-ngôi S trên X là một tập con S của X 2

X là tập hợp các công dân Việt Nam, trong khi S là tập hợp tất cả các bộ ba (x, y, z), với x là chồng của y và z là con của x và y Do đó, S ⊆ X 3 tạo thành một quan hệ 3-ngôi trên tập hợp X.

1.2 Quan hệ Chương 1 Lý thuyết tập hợp b)X là tập hợp các sinh viên của một lớp,S là tập các cặp (x, y)trong đóx, y cùng tuổi, S⊆X 2 là quan hệ trênX.

1.2.3 Tính chất của quan hệ 2-ngôi

Cho quan hệ S trên X Nếu (x, y)∈S thì ta nói x cóS-quan hệ với y, và viết xSy.

1) Quan hệ S gọi là có tính phản xạ nếu với mọi x∈X ta có xSx.

2) Quan hệ S gọi là có tính đối xứng nếu với mọi x, y ∈X,xSy thì ySx.

3) Quan hệ S gọi là có tính chất phản đối xứng hay phản xứng nếu với mọi x, y ∈ X,xSy và ySx thì x=y.

4) Quan hệ S gọi là có tính bắc cầu nếu với mọi x, y ∈X,xSy và ySz thì xSz.

Trong lớp học, quan hệ xSy giữa hai học sinh x và y cùng tuổi có tính chất phản xạ, đối xứng và bắc cầu Tương tự, trong tập số tự nhiên N, quan hệ xSy nếu x ≤ y cũng sở hữu các tính chất tương tự Ngoài ra, trong tập hợp các tam giác, quan hệ "đồng dạng" cũng thể hiện các tính chất phản xạ, đối xứng và bắc cầu Những quan hệ này đều thuộc về khái niệm quan hệ tương đương.

Một quan hệ S trên tập X gọi là quan hệ tương đương nếu S có tính chất phản xạ, đối xứng, bắc cầu.

Trong lý luận tổng quát, quan hệ tương đương được ký hiệu là ∼ Cụ thể, nếu S là một quan hệ tương đương trên tập hợp X, thì xSy được ký hiệu là x∼y, có nghĩa là x tương đương với y.

Ví dụ a) Cho X là một tập hợp các sinh viên trong một lớp Ta định nghĩa một quan hệ hai ngôi trên X như sau: x∼y ⇐⇒ x ngồi cùng bàn vớiy.

Khi đó,∼ là một quan hệ tương đương trên X. b) Trên tập hợp số nguyên Z, xét quan hệ hai ngôi∼ như sau: n∼m ⇐⇒ 3|n−m.

Khi đó,∼ là một quan hệ tương đương trên Z. c) Trên tập hợp số nguyên Z, xét quan hệ hai ngôi∼ như sau: n∼m ⇐⇒ n−m là số lẻ.

Khi đó,∼ không phải là một quan hệ tương đương trên Z vì nó không có tính phản xạ.

1.2 Quan hệ Chương 1 Lý thuyết tập hợp

Cho tập X và quan hệ ∼ là quan hệ tương đương trên X Với mỗi x∈X, tập hợp

[x] ={y ∈X|y∼x} được gọi là lớp tương đương của xtheo quan hệ tương ∼.

Các lớp tương đương khác rỗng, hoặc bằng nhau, hoặc rời nhau. Định lý

Để chứng minh rằng lớp tương đương [x] không rỗng, ta thấy rằng x∼x nên x thuộc [x], tức là [x] khác rỗng Giả sử [x]∩[y] khác rỗng, ta cần chứng minh [x] = [y] Chọn z thuộc [x]∩[y], ta có z thuộc [x] và z thuộc [y] Từ đó, vì z thuộc [x] nên x∼z, và vì z thuộc [y] nên z∼y Do đó, ta có t thuộc [x] nếu và chỉ nếu t∼x, tức là t∼z, và t∼y, nên t thuộc [y].

Vậy [x] = [y] Do đó, định lý đã được chứng minh.

Chú ý: Từ Định lí 1 suy ra rằng y∈[x]khi và chỉ khi [x] = [y] và x∼y khi và chỉ khi [x] = [y].

Các lớp tương đương phân chia tập X thành các tập con rời nhau, tạo thành một phân hoạch trên tập X Tập hợp các lớp tương đương của X theo quan hệ tương đương ∼ được gọi là tập thương của X, ký hiệu là X/∼.

Trong bài viết này, chúng ta xem xét các quan hệ tương đương trong tập hợp Đầu tiên, cho tập X là các sinh viên trong lớp học, với quan hệ x∼y nếu x và y ngồi cùng bàn Các lớp tương đương theo quan hệ này sẽ bao gồm những sinh viên ngồi cùng bàn, tạo thành tập X∼ Tiếp theo, trên tập Z các số nguyên, chúng ta định nghĩa quan hệ a∼b nếu a−b chia hết cho 3 Khi đó, a∼b tương đương với việc a và b có cùng số dư khi chia cho 3, dẫn đến ba lớp tương đương: các số có dư 0, 1, và 2 khi chia cho 3.

0 = {3k|k ∈Z}, các số chia hết cho 3;

1 = {3k+ 1|k∈Z}, các số chia cho 3 dư 1;

2 = {3k+ 2|k∈Z}, các số chia cho 3 dư 2.

1.2.6 Quan hệ thứ tự a) Định nghĩa

Một quan hệ S trên tập X gọi là quan hệ thứ tự nếu S có các tính chất phản xạ, phản xứng,bắc cầu.

Ánh xạ

Nếu S là quan hệ thứ tự thì thay cho cách viết xSy ta viếtx≤y

Tập X cùng quan hệ thứ tự ≤trên nó gọi là tập được sắp thứ tự, khi đó kí hiệu(X,≤).

Ví dụ 1) TrongN,Z,Q,R quan hệ ≤ thông thường là quan hệ thứ tự.

2) Trong N ∗ xét quan hệ "chia hết": a chia hết cho b nếu tồn tại q ∈ N ∗ sao cho aq = b, kí hiệu a|b Quan hệ này là quan hệ thứ tự.

3) Quan hệ bao hàm “⊆” trong tập hợp P(X) các tập con của một tập hợp X là một quan hệ thứ tự. b) Quan hệ thứ tự toàn phần và bộ phận

Cho X là một tập được sắp thứ tự, Nếu với x, y ∈ X ta có x ≤ y hoặc y ≤ x thì ta nói x và y so sánh được với nhau Nếu với mọi x, y ∈ X đều so sánh được với nhau thì ta nói X là tập sắp thứ tự toàn phần, hay tập sắp thứ tự tuyến tính Trong trường hợp trái lại ta nói X là tập sắp thứ tự bộ phận.

Trong một tập hợp A được sắp thứ tự toàn phần bởi ≤, với n là một số nguyên dương, ta định nghĩa một quan hệ L giữa hai chuỗi a và b Cụ thể, a = (a1, a2, , an) và b = (b1, b2, , bn) sẽ có quan hệ aLb khi a và b bằng nhau, hoặc a1 nhỏ hơn b1, hoặc tồn tại một chỉ số i (i = 2, , n) sao cho các phần tử đầu tiên của a và b bằng nhau cho đến chỉ số i-1, và ai nhỏ hơn bi.

Khi đó, kiểm tra đượcA n sắp thứ tự toàn phần bởiL Quan hệL này được gọi làquan hệ thứ tự từ điển.

Ví dụ dưới đây sẽ giải thích tại sao người ta gọi quan hệL là quan hệ từ điển:

Xét A = {, a, b, , x, y, z} với ký hiệu "không có chữ cái nào" Rõ ràng, A là tập hợp toàn phần với thứ tự xác định như sau: α ≤ β khi α = β hoặc α đứng trước β Giả sử n là số tự nhiên sao cho bất kỳ từ tiếng Anh nào đều có số chữ cái k (k ≤ n) Một từ tiếng Anh với k chữ cái được xem như phần tử của A_n, trong đó k thành phần đầu là các chữ cái của từ (theo thứ tự) và n - k thành phần còn lại là rỗng Như vậy, quan hệ L được định nghĩa sẽ cung cấp cách sắp xếp các từ tiếng Anh theo thứ tự từ điển.

1.3.1 Định nghĩa và ví dụ

Cho hai tập hợp X và Y, một ánh xạ f từ X vào Y là quy tắc tương ứng mỗi phần tử x ∈ X với một phần tử duy nhất y = f(x) ∈ Y Để chỉ ra rằng f là một ánh xạ từ tập hợp X đến tập hợp Y, ta sử dụng ký hiệu f: X → Y, với x 7→ y = f(x).

1.3 Ánh xạ Chương 1 Lý thuyết tập hợp

Tập X gọi là tập nguồn của ánh xạ.

Tập Y gọi là tập đích của ánh xạ.

Phần tử y=f(x) gọi là ảnh của phần tửx∈X qua ánh xạf.

Phần tử x∈X đểf(x) = y gọi là một tạo ảnh của y∈Y.

Tập hợp G f ={(x, f(x))|x∈X} được gọi là đồ thị của ánh xạ f.

Giả sử tập hợp các cuốn sách choX = {a, b, c, d} và tập hợp các học sinh Y = {1, 2, 3, 4, 5} Các cuốn sách sẽ được phân phối cho các học sinh mượn sử dụng theo bảng đã được thiết lập.

Mỗi phần tử của tập hợp X được ánh xạ tương ứng với một phần tử duy nhất của tập hợp Y, từ đó xác định ánh xạ f: X → Y Trong lớp học, mỗi cách sắp xếp chỗ ngồi của sinh viên cũng là một ánh xạ, trong đó tập hợp A gồm các sinh viên được ánh xạ đến tập hợp B của chỗ ngồi tương ứng Tuy nhiên, quy tắc f: R → R với x ↦ f(x) = 1 không phải là một ánh xạ, vì không thỏa mãn điều kiện ánh xạ.

Ánh xạ đồng nhất của tập X, ký hiệu là 1X, được định nghĩa bởi 1X(x) = x cho mọi x trong X Nếu X là một tập con của tập hợp Y, thì phép nhúng chính tắc từ X vào Y được biểu diễn bởi ánh xạ iX: X → Y, với iX(x) = x cho mọi x thuộc X.

1.3 Ánh xạ Chương 1 Lý thuyết tập hợp

1.3.2 Ánh xạ bằng nhau, thu hẹp và mở rộng ánh xạ

Hai ánh xạ cùng tập nguồn và tập đích f :X −→Y, g :X −→Y được gọi là bằng nhau, kí hiệu f =g, nếu f(x) =g(x), ∀x∈X. Định nghĩa

Ví dụ: (i) Cho hai ánh xạ f :R→R + x7→f(x) = x 2 và g :R→R + x7→g(x) = |x| 2

Khi đó, hai ánh xạh và g (xác định ở trên) là khác nhau vì chúng có tập đích khác nhau.

Ánh xạ f : X −→ Y và A là tập con của X tạo ra ánh xạ thu hẹp f | A : A → Y, với f | A (a) = f(a) Ngược lại, nếu X là tập con của A và f là ánh xạ từ A đến Y với điều kiện f(x) = f(x) cho mọi x ∈ X, thì f được gọi là ánh xạ mở rộng của f ra A.

1.3 Ánh xạ Chương 1 Lý thuyết tập hợp

Ví dụ: Cho ánh xạ d:R→ {0,1} x7→d(x) 

Rõ ràngd| I có một ánh xạ mở rộng ra Rlàd Ngoài ra,d| I còn có thêm một ánh xạ mở rộng ra Rnữa là d :R→ {0,1} x7→d(x) = 1.

Nhận xét ánh xạ thu hẹp f| X được xác định duy nhất Tuy nhiên, ánh xạ f có thể mở rộng ra một tập hợp theo nhiều cách khác nhau.

1.3.3 Ảnh và tạo ảnh i) Cho f :X −→Y là một ánh xạ và A là một tập con của X Khi đó, tập hợp f(A) = {y∈Y | ∃x∈A:y=f(a)} được gọi là ảnh của X qua f Đặc biệt f(X)được gọi là ảnh của f, và kí hiệu lại làIm(f). ii) Cho f :X −→Y là một ánh xạ và B là một tập con của Y Khi đó, tập hợp f −1 (B) ={x∈X|f(x)∈B} được gọi là tạo ảnh của B qua f Đặc biệt, nếu B = {b} thì f −1 ({b}) được kí hiệu lại là f −1 (b), và gọi làtạo ảnh của b qua f.

Ví dụ: Cho ánh xạ f :R→R + x7→f(x) =x 2 Khi đó, ta có f((−1,2)) = (1,4),Im(f) = R 2 , f −1 (4) ={−2,2}và f −1 ([4,9]) = [−3,−2]∪[2,3]. 1.3.4 Hợp thành của các ánh xạ

1.3 Ánh xạ Chương 1 Lý thuyết tập hợp Khi đó, ta có ánh xạ h:X →Z x7→h(x) = g(f(x)).

Ta gọi ánh xạ này làánh xạ hợp thành hay ánh xạ tích của f vàg, và được kí hiệu là g◦f hay gf.

Ví dụ: Cho hai ánh xạ dưới đây f :R ∗ →R x7→f(x) = 1 x và g :R→R + x7→g(x) =x 4 + 2.

Khi đó, ta có ánh xạ hợp thành của f vàg là gf :R ∗ →R + x7→gf(x) = 2x 4 + 1 x 4

Với mỗi ánh xạ f :X −→Y, ta luôn có 1 Y f =f small> X

Sử dụng định nghĩa, ta dễ dàng chỉ ra rằng phép hợp thành của các ánh xạ có tính kết hợp.

1.3 Ánh xạ Chương 1 Lý thuyết tập hợp

1.3.5 Các ánh xạ đặc biệt

Cho f :X −→Y là một ánh xạ Khi đó,

(i)f được gọi là đơn ánh nếu

Hàm số f được gọi là toàn ánh khi ảnh của nó bao trùm toàn bộ tập Y, tức là với mỗi phần tử y thuộc Y, luôn tồn tại ít nhất một phần tử x thuộc X sao cho y = f(x) Ngoài ra, f được xem là song ánh nếu nó vừa là hàm đơn ánh vừa là hàm toàn ánh.

Nhận xét dưới đây cho phép ta kiểm tra tính đơn ánh, toàn ánh và song ánh thông qua các tạo ảnh.

Cho f :X −→Y là một ánh xạ Khi đó,

(i)f là đơn ánh khi và chỉ khi với mỗiy∈Y, tập hợp f −1 (y) chứa nhiều nhất một phần tử.

(ii) f là toàn ánh khi và chỉ khi với mỗi y∈Y, tập hợp f −1 (y)chứa ít nhất một phần tử.

(iii) f là toàn ánh khi và chỉ khi với mỗi y∈Y, tập hợp f −1 (y)chứa duy nhất một phần tử.

Ví dụ (i) Cho X là một tập hợp Khi đó, ánh xạ 1 X :X −→X là một song ánh.

(ii) Cho ánh xạ dưới đây f :R→R x7→f(x) =x 3

Để chứng minh rằng hàm số f là một song ánh, trước tiên cần xác minh rằng f là đơn ánh và toàn ánh Đầu tiên, ta chứng minh f là đơn ánh: Giả sử x₁, x₂ ∈ R và f(x₁) = f(x₂) Từ đó, ta có x₁³ = x₂³, dẫn đến x₁ = x₂ Như vậy, f là đơn ánh.

Tiếp theo, ta chứng minhf là toàn ánh: Cho bất kỳy∈R Chọn x=√ 3 y∈R Ta cóf(x) = x 3 (√ 3 y) 3 =y.Vậy f là toàn ánh.

Tóm lại, qua chứng minh trên ta được f là song ánh.

Khi đó,g không là đơn ánh vìf(−2) = 4 =f(2) nhưng−26= 2 Đồng thời,f cũng không là toàn ánh vì dễ thấyf −1 (−2) =∅.

1.3 Ánh xạ Chương 1 Lý thuyết tập hợp

(i) Nếu f và g là các đơn ánh thì gf là đơn ánh.

(ii) Nếu f và g là các toàn ánh thì gf là toàn ánh.

(iii) Nếu f và g là các song ánh thì gf là song ánh. Định lý

Giả sử f và g là các đơn ánh, ta cần chứng minh rằng gf cũng là đơn ánh Cho x₁, x₂ ∈ X sao cho gf(x₁) = gf(x₂) Khi đó, từ định nghĩa, ta có g(f(x₁)) = gf(x₁) = gf(x₂) = g(f(x₂)) Vì g là đơn ánh, suy ra f(x₁) = f(x₂) Với f cũng là đơn ánh, ta kết luận x₁ = x₂.

Giả sử f và g là toàn ánh, ta chứng minh rằng gf cũng là toàn ánh Với bất kỳ z ∈ Z, do g là toàn ánh nên tồn tại y ∈ Y sao cho z = g(y) Đồng thời, vì f là toàn ánh, nên tồn tại x ∈ X sao cho y = f(x) Do đó, ta có z = g(y) = g(f(x)) = gf(x) Vậy nên, gf là toàn ánh.

(iii) được suy ra từ (i) và (ii) Vậy định lý đã được chứng minh.

(i) Nếu gf là đơn ánh thì f là đơn ánh.

(ii) Nếu gf là toàn ánh thì g là toàn ánh. Định lý

Để chứng minh rằng hàm số \( f \) là đơn ánh, giả sử \( gf \) là đơn ánh Nếu \( x_1, x_2 \in X \) sao cho \( f(x_1) = f(x_2) \), ta có \( gf(x_1) = g(f(x_1)) = g(f(x_2)) = gf(x_2) \) Do \( gf \) là đơn ánh, suy ra \( x_1 = x_2 \) Như vậy, ta kết luận rằng \( f \) cũng là đơn ánh.

Giả sử hàm gf là toàn ánh, ta cần chứng minh rằng g cũng là toàn ánh Cho z thuộc Z, vì gf là toàn ánh, tồn tại x thuộc X sao cho z = gf(x) = g(f(y)) Đặt y = f(x), từ đó suy ra y thuộc Y và g(y) = z Điều này chứng tỏ g là toàn ánh, hoàn thành chứng minh định lý.

Nếu gf = 1X và f g= 1Y thì ta nói g là ánh xạ ngược của f. Định nghĩa

Từ định nghĩa ta dễ thấy rằng nếu g là ánh xạ ngược của f thì f cũng là ánh xạ ngược của g.

1.3 Ánh xạ Chương 1 Lý thuyết tập hợp

Ví dụ (i) ánh xạ f :R→R x7→f(x) =x 3 có ánh xạ ngược là g :R→R x7→g(x) = √ 3 x.

(ii) ánh xạ f :R + →R + x7→f(x) =x 2 có ánh xạ ngược là g :R + →R + x7→g(x) = √ x.

Giải tích tổ hợp

. Ánh xạ ngược (nếu có) của f là duy nhất và kí hiệu làf −1

Thật vậy, giả sử g, g 0 : Y −→ X là các ánh xạ ngược của f : X −→ Y Ta chứng minh g =g 0 Thật vậy, sử dụng Nhận xét 3.4.2 và Định lý 3.4.3, ta có g =g1 Y =g(f g 0 ) = (gf)g 0 = 1 X g 0 =g 0

Cho f :X −→Y và g :Y −→Z là các song thì gf có ánh xạ ngược và

Chứng minh rằng vì f và g là song ánh, theo Định lý 3.5.3, gf cũng là song ánh Áp dụng Định lý 3.6.2, ta có gf có ánh xạ ngược Cụ thể, f −1 g −1 (gf) = f −1 (g −1 g)f = f −1 1 Y f = f −1 f = 1 X và gf(f −1 g −1 ) = g(f f −1 )g −1 = g1 Y g −1 = gg −1 = 1 Z.

Từ đây, ta suy ra ngay(gf) −1 =f −1 g −1 Vậy định lý đã được chứng minh.

1.4.1 Quy tắc cộng và quy tắc nhân a) Quy tắc cộng

Nếu một công việc được chia thành k trường hợp, trong đó trường hợp 1 có n1 cách thực hiện, trường hợp 2 có n2 cách thực hiện, và tiếp tục như vậy cho đến trường hợp k với nk cách thực hiện, và không có cách thực hiện nào ở trường hợp này trùng với cách thực hiện ở trường hợp khác, thì tổng số cách thực hiện công việc sẽ là n1 + n2 + + nk.

Ví dụ Từ các chữ số 1,2,3 có thể lập ra được bao nhiêu số có các chữ số khác nhau?

Giải: Ta chia ra ba trường hợp

- Lập các số có 1 chữ số: có 3 số là 1,2,3;

- Lập các số có hai chữ số: có 6 số là 12, 13, 21, 23, 31, 32;

- Lập các số có 3 chữ số: có 6 số là: 123, 132, 213, 231, 312, 321;

Theo quy tắc cộng có 3+6+6 số. b) Quy tắc nhân

Nếu một công việc được chia thành k giai đoạn, mỗi giai đoạn có một cách thực hiện riêng biệt, thì tổng số cách thực hiện để hoàn thành toàn bộ công việc sẽ là n1.n2 nk.

1.4 Giải tích tổ hợp Chương 1 Lý thuyết tập hợp

Ví dụ Một thiết bị tạo thành bởi 3 bộ phận Bộ phận 1 có 10 loại, bộ phận 2 có 7 loại, bộ phận

3 có 5 loại Hỏi thiết bị trên có bao nhiêu loại.

Trong quá trình lựa chọn thiết bị, giai đoạn 1 có 10 cách chọn bộ phận 1, giai đoạn 2 có 7 cách chọn bộ phận 2, và giai đoạn 3 có 5 cách chọn bộ phận 3 Theo quy tắc nhân, tổng số loại thiết bị có thể tạo ra là 10 x 7 x 5 = 350 loại.

Chỉnh hợp chập k từ n phần tử là một tập hợp có thứ tự, bao gồm k phần tử khác nhau được chọn từ n phần tử đã cho Số lượng chỉnh hợp chập k từ n phần tử được ký hiệu là A_k^n.

Ví dụ: Có bao nhiêu số có 3 chữ số gồm toàn các chữ số lẽ khác nhau?

Để tìm số lượng các số có 3 chữ số lẻ khác nhau từ 5 chữ số 1, 3, 5, 7, 9, ta cần lấy từng bộ 3 chữ số khác nhau và sắp xếp chúng Số lượng các số thỏa mãn điều kiện là A(3, 5) = 5.4.3 = 60.

Chỉnh hợp lặp chập k từ n phần tử là một tập hợp có thứ tự gồm k phần tử, trong đó các phần tử có thể trùng lặp, được chọn từ n phần tử đã cho Số lượng chỉnh hợp lặp chập k từ n phần tử được ký hiệu là A −k n = n k.

Ví dụ Có bao nhiêu cách xếp 8 người lên 5 toa tàu?

Giải: Một cách xếp 8 người lên 5 toa tàu tương ứng với một chỉnh hợp lặp chập 8 từ 5 phần tử.

Do đó số cách là A −8 5 = 5 8 = 390625.

Một hoán vị từ n phần tử là một bộ có kể thứ tự gồm n phần tử khác nhau đã cho.

Số các hoán vị từ n phần tử kí hiệu là P n

Ví dụ Một tổ có 10 học sinh Hỏi có bao nhiêu cách tổ này đứng thành một hàng dọc.

Giải: Một cách đứng thành một hàng dọc tương ứng với một hoán vị từ 10 phần tử.

Do đó số cách đứng thành một hàng dọc là: P 10 = 10! = 3628800

Một tổ hợp chập k từ n phần tử là một tập con gồm k phần tử láy từ n phần tử đã cho.

Một tập con gồm k phần tử còn gọi là một bộ không kể thứ tự gồm k phần tử khác nhau.

Số tổ hợp chập k từ n phần tử kí hiệu là C n k

1.4 Giải tích tổ hợp Chương 1 Lý thuyết tập hợp

Ví dụ Một lô hàng có 10 sản phẩm Hỏi có bao nhiêu cách chọn ra 3 sản phẩm?

Giải: Mỗi cách chọn tương ứng với một tổ hợp chập 3 từ 10 phần tử Vậy số cách chọn làC 10 3 = 120.

Tổ hợp có hai tính chất quan trọng sau đây: Định lý 1.

Hệ quả Chứng minh rằng:

1.4 Bài tập chương 1 Chương 1 Lý thuyết tập hợp

1 Liệt kê các phần tử của các tập hợp sau: a) A={x∈R|(x−1)(2x 2 + 3x+ 1) = 0} b) B ={x∈Z|2 x =x} c) C ={x∈N|x là ước của 24} d) D={x∈N|x 2 + 4x−5 = 0}

2 Viết lại các tập hợp sau bằng cách chỉ ra một tính chất đặc trưng của các phần tử. a) A={5,10,15,20,25} b) B ={−2,−1,0,1,2} c) C ={1,1

3 Cho tập hợp X ={a, b, c} Hãy liệt kê các phần tử của tập hợp P(X).

4 Xét quan hệ giữa các tập A và B cho dưới đây: a) A={n∈N|n 2 0”đúng vì với mọi số thực, ta đều có x 2 + 4x+ 5 = (x+ 2) 2 + 1>0. b) Lượng từ ∃ (đọc là "tồn tại")

Cho mệnh đề chứa biến "P(x) vớix∈X" Khi đó câu khẳng định

Mệnh đề "Tồn tại một phần tử X thuộc X sao cho P(x) đúng" (2.3.2) được xác định là đúng khi tồn tại ít nhất một phần tử x0 trong X sao cho P(x0) là đúng Ngược lại, mệnh đề này sẽ sai nếu mọi phần tử x thuộc X đều khiến P(x) trở thành sai.

Áp dụng mệnh đề vào suy luận và chứng minh

Ví dụ: Cho mệnh đề chứa biến: "2 n + 1 chia hết cho n, vớin ∈N" Khi đó mệnh đề: "∃n ∈N: 2 n + 1 chia hết cho n" là mệnh đề đúng vì vớin = 3, ta có 2 3 + 1 = 9chia hết cho 3.

Với các mệnh đề chứa nhiều biến, ta cũng có thể gán các lượng từ ∀ và ∃ vào theo các cách khác nhau để biến chúng thành một mệnh đề.

2.3.8 Phủ định của mệnh đề có chứa lượng từ "với mọi" và "tồn tại"

Cho mệnh đề chứa biến P(x)với x∈X Khi đó:

- Mệnh đề phủ định của mệnh đề ”∀x∈X, P(x)”là mệnh đề ”∃x∈X, P(x)”.

- Mệnh đề phủ định của mệnh đề ”∃x∈X, P(x)” là mệnh đề ”∀x∈X, P(x)”.

Chẳng hạn, mệnh đề phủ định của mệnh đề "∀x ∈ N,2n+ 5 chia hết cho 5" là mệnh đề ∃x ∈

Ví dụ: Phủ định của định nghĩa ánh xạ liên tục. Ánh xạ f : D −→ R được gọi là liên tục tại x 0 ∈ D nếu với mọi ε > 0, tồn tại δ > 0, sao cho

∀x∈D, |x−x 0 |< δ thì |f(x)−f(x 0 )|< ε. Ánh xạ f :D−→R được gọi là không liên tục (gián đoạn) tại x 0 ∈D nếu tồn tại ε >0, sao cho với mọiδ >0, tồn tại x∈D, để |x−x 0 |< δ và |f(x)−f(x 0 )| ≥ε.

2.4 ÁP DỤNG MỆNH ĐỀ VÀO SUY LUẬN VÀ CHỨNG MINH

2.4.1 Diễn đạt một định lí

Các định lý trong toán học là những mệnh đề đúng, có thể diễn đạt bằng các mệnh đề chứa biến và các phép toán mệnh đề Chúng thường sử dụng các lượng từ như "với mọi" và "tồn tại".

5 là số vô tỉ có thể diễn đạt bởi các mệnh đề:

2.4 Áp dụng mệnh đề vào suy luận và chứng minh Chương 2 Logic

2.4.2 Điều kiện cần, điểu kiện đủ, điều kiện cần và đủ

Cho hai mệnh đề chứa biến P(x) và Q(x) Xét định lí có dạng

P(x) được gọi là giả thiết và Q(x) được gọi là kết luận. Định lí dạng (2.4.3) còn được phát biểu:

P(x) là điều kiện đủ để có Q(x) hoặc Q(x) là điều kiện cần để có P(x).

Nếu mệnh đề (2.4.4) đúng thì nó được gọi là định lí đảo của định lí dạng (1) Lúc đó định lí dạng

(1) sẽ được gọi là định lí thuận Định lí thuận và đảo có thể viết gộp thành một định lí

P(x) được coi là điều kiện cần và đủ để có Q(x) Chúng ta có thể diễn đạt điều này bằng các cách khác nhau, như "P(x) nếu và chỉ nếu Q(x)", "P(x) khi và chỉ khi Q(x)", hoặc "Điều kiện cần và đủ để có P(x) là có Q(x)".

Định lí cho biết rằng với mỗi số tự nhiên n, nếu n chia hết cho 4 thì n cũng chia hết cho 2 Cụ thể, định lí này có thể được biểu diễn dưới dạng ∀n ∈ N, P(n) ⇒ Q(n), trong đó P(n) là điều kiện "n chia hết cho 4" và Q(n) là kết luận "n chia hết cho 2".

Định lý về chia hết có thể được diễn đạt là: "n chia hết cho 4 là điều kiện đủ để n chia hết cho 2" và "n chia hết cho 2 là điều kiện cần để n chia hết cho 4" Xét về hình học, định lý 1 phát biểu rằng: "Nếu một tứ giác lồi nội tiếp được trong đường tròn thì tổng hai góc đối của nó bằng 180 độ" Ngược lại, định lý 2 khẳng định: "Nếu một tứ giác lồi có tổng hai góc đối bằng 180 độ thì tứ giác đó nội tiếp được trong đường tròn" Hai định lý này có thể được gộp lại thành định lý 3.

"Một tứ giác lồi nội tiếp được trong đường tròn khi và chỉ khi tổng hai góc đối của nó bằng180 0 "

Định lý 3 phát biểu rằng: "Tứ giác có thể nội tiếp trong một đường tròn nếu và chỉ nếu tổng hai góc đối của nó bằng 180 độ."

Mỗi chứng minh được cấu thành từ một số bước suy luận đơn giản có giới hạn Trong từng bước này, việc áp dụng quy tắc suy luận là cần thiết để đảm bảo các mệnh đề được công nhận là đúng.

2.4 Áp dụng mệnh đề vào suy luận và chứng minh Chương 2 Logic suy ra được một mệnh đề mới Các mệnh đề được thừa nhận là đúng được gọi là các tiền đề, mệnh đề mới được suy ra là hệ quả lôgic của các tiền đề.

Giả sử A1, A2, , An, B là các công thức Ta gọi B là hệ quả lôgic của A1, A2, , An nếu trong mọi hệ chân trị của các biến mệnh đề có mặt trong các công thức đó, khi A1, A2, , An đều nhận giá trị 1 thì B cũng nhận giá trị 1.

Khi B là hệ quả lôgic của A 1 , A 2 , , A n thì ta cũng nói có một quy tắc suy luận từ các tiền đề

A 1 , A 2 , , A n tới hệ quả lôgic của chúng. Định nghĩa

Qui tắc suy luận nói trên được kí hiệu là:

Từ định nghĩa trên ta thấy rằng, để chứng minh một quy tắc suy luận có thể dùng phương pháp lập bản chân trị.

Ví dụ 1: Chứng minh qui tắc suy luận p, p⇒q q

Ta lập bảng chân trị p q p⇒q

Chỉ có một hệ chân trị làm cho pvà p⇒qcùng nhận giá trị 1 là dòng đầu tiên, trong trường hợp đóq cũng nhận giá trị 1.

Vậy chúng ta có qui tắc suy luận p, p⇒q q

Ví dụ 2: Chứng minh qui tắc p⇒q, q⇒r p⇒r

Ta lập bản chân trị p q r p⇒q q⇒r p⇒r

2.4 Áp dụng mệnh đề vào suy luận và chứng minh Chương 2 Logic

Từ bản chân trị, chúng ta nhận thấy có 4 hệ chân trị mà trong đó p ⇒ q và q ⇒ r đều nhận giá trị 1, đồng thời p ⇒ r cũng nhận giá trị 1 ở các dòng 1, 5, 7 và 8 Điều này dẫn đến quy tắc suy luận p ⇒ q, q ⇒ r suy ra p ⇒ r.

2.4.4 Liên hệ giữa qui tắc suy luận và luật

Ta cóA 1 , A 2 , , A n đồng thời nhận giá trị 1 khi và chỉ khi A 1 ∧A 2 ∧ .∧A n nhận giá trị 1 và

A 1 ∧A 2 ∧ .∧A n ⇒B đúng khi và chỉ khi A 1 ∧A 2 ∧ .∧A n nhận giá trị 1 thì B nhận giá trị 1 Do đó có quy tắc suy luận

A 1 , A 2 , , A n B khi và chỉ khi có luật A 1 ∧A 2 ∧ .∧A n ⇒B.

Từ đó, để chứng minh quy tắc suy luậnA 1 , A 2 , , A n

B , ta có thể chỉ ra mệnh đềA1∧A2∧ .∧An ⇒

Ví dụ:Chứng minh quy tắc suy luận p∧q p

Ta lập bảng chân trị p q p∧q p∧q⇒p

Từ bảng chân trị ta có luật p∧q ⇒p.

Do đó, chúng ta có quy tắc suy luận p∧q p 2.4.5 Bảng một số quy tắc suy luận trong toán học

2.4 Áp dụng mệnh đề vào suy luận và chứng minh Chương 2 Logic

2.4.6 Hai kiểu suy luận a) Suy luận diễn dịch

Suy luận diễn dịch, hay còn gọi là suy diễn, là quá trình suy luận dựa trên các quy tắc nhất định, nhằm khẳng định rằng nếu các tiền đề được đưa ra là đúng, thì kết luận rút ra từ chúng cũng sẽ đúng.

Suy luận diễn dịch là suy luận hợp lôgic, các kết luận nhận được là kết luận lôgic.

Ví dụ: Từ hai tiền đề e >2và e