Báo cáo bài tập lớn môn toán rời rạc tập hợp, quan hệ
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
BÁO CÁO BÀI TẬP LỚN
MÔN TOÁN RỜI RẠC
Đề tài 1
Nhóm 26
BÀI TẬP LỚN TOÁN RỜI RẠC
MỤC LỤC
GIẢI BÀI TẬP – LÝ THUYẾT ĐỒ THỊ..........................................................2
Vấấn đềề 1:.............................................................................................................................................2
Vấấn đềề 2:.............................................................................................................................................2
Vấấn đềề 3:.............................................................................................................................................6
Vấấn đềề 4:.............................................................................................................................................7
Vấấn đềề 5:.............................................................................................................................................8
Vấấn đềề 6:.............................................................................................................................................8
Vấấn đềề 7:.............................................................................................................................................9
Vấấn đềề 8:...........................................................................................................................................10
DỊCH TÀI LIỆU– TẬP HỢP, QUAN HỆ.......................................................12
Chương 1.............................................................................................................12
Tập hợp, quan hệ............................................................................................................................12
1.1. Định nghĩa.............................................................................................................................12
1.2. Các phép toán tập hợp..........................................................................................................15
1.3. Đại sốấ tập hợp......................................................................................................................21
1.4. Biểu diềễn tập hợp trền máy tnh...........................................................................................23
1.5 Quan hệ..................................................................................................................................26
NHÓM 26
Page 1
BÀI TẬP LỚN TOÁN RỜI RẠC
GIẢI BÀI TẬP – LÝ THUYẾT ĐỒ THỊ
Vấn đề 1:
Đồ thị hình 1 có phải đồ thị Euler? Hãy chỉ ra 1 chu trình Euler hoặc
chứng minh tại sao nó không phải.
Hình 1: Bạn có thể vẽ đồ thị trong 1 nét không?
Trả lời:
Đồ thị trên là đồ thị Euler.
Cơ sở: Là đồ thị liên thông.
Đồ thị không có đỉnh bậc lẻ.
Chu trình Euler: A B C F J H E B F E D G H D A
Vấn đề 2:
Một lá là một đỉnh với duy nhất một đỉnh lân cận. Mọi cây G với nhiều
hơn 1 đỉnh có ít nhất 2 lá.
Thật vậy: Cho G là một đồ thị liên thông không chu trình tùy ý với nhiều
hơn 1 đỉnh.
Vì G là đồ thị liên thông và có nhiều hơn 1 đỉnh, mọi đỉnh có bậc lớn hơn
1.
NHÓM 26
Page 2
BÀI TẬP LỚN TOÁN RỜI RẠC
Lấy vo, v1,….,vn là đường đi dài nhất trong G. Vì đường đi dài nhất, nó
phải đi qua đỉnh lân cận của v n. Nếu vn kề với vi với mọi i < n-1, khi đó v i, vi+1,
…., vn, vi là 1 chu trình của G. Vì G là đồ thị không chu trình nên không thể có
chu trình nào trong G.
Vì vậy, vn chỉ kề với duy nhất vn-1, vì thế vn là 1 lá. Chứng minh tương tự
v0 cũng là lá. => đpcm
a)
b)
c)
d)
e)
f)
g)
h)
i)
Các vấn đề khác bạn nên chứng minh:
Mọi đồ thị liên thông có ít nhất |V| - 1 cạnh.
Mọi đồ thị không chu trình có nhiều nhất |V| - 1 cạnh.
Bất kỳ đồ thị liên thông nào có |V| - 1 cạnh là 1 cây.
Bất kỳ đồ thị không chu trình bào có |V| - 1 cạnh là 1 cây.
Mọi đồ thị liên thông tối thiểu là 1 cây.
Mọi đồ thị không chu trình tối đa là 1 cây.
Một đồ thị là một cây khi và chỉ khi có duy nhất một đường đi từ đỉnh này
sang đỉnh khác.
Mọi cây có chứa đỉnh bậc N thì có tối thiểu N lá.
Trong 1 cây bất kỳ, đa số các đỉnh có bậc lớn nhất là 2.
Chứng minh:
a, Mọi đồ thị liên thông có ít nhất |V| - 1 cạnh.
Trường hợp cơ sở: |V| = 0 và |V| = 1, |E| >= 0 >= |V| - 1.
Với đồ thị lớn hơn: Giả sử E ∨ ∨V ∨−1 , ta chứng minh G không phải
đồ thị liên thông.
Ta có
∑ deg v
2 E ≤ 2 V −2
=> Có ít nhất 1 đỉnh v với deg v ≤ 1
=> G không liên thông => loại.
deg v 1 , xét đồ thị G thu được bằng cách loại v và cạnh nối của v.
deg v 0
1
|E1| = |E|-1 < |V1| - 1 = |V| - 2
Tiếp tục loại 1 đỉnh và 1 cạnh ra khỏi đồ thị, cuối cùng ta đưa về trường
hợp |V| = 1, khi đó gia thiết ban đầu |E| < |V| - 1 sai.
=> G1 không liên thông => G không liên thông => |E| >= |V| - 1. Đpcm
b, Mọi đồ thị không chu trình có nhiều nhất |V| - 1 cạnh.
NHÓM 26
Page 3
BÀI TẬP LỚN TOÁN RỜI RẠC
Trường hợp cơ sở: |V| = 1 khi đó |E| = 0 | => |E| <= |V| - 1 đúng.
Ta sẽ bổ sung vào trường hợp cơ sở để số cạnh đạt tối đa. Ta chia ra làm 3
trường hợp:
- Thêm vào đồ thị đỉnh, 1 cạnh nối của đỉnh đó với đồ thị: ta thu được đồ
thị mạch hở và liên thông. Khi đó |E| = |V| - 1
- Thêm vào đồ thị số cạnh ít hơn số đỉnh: đây không phải là cách thêm để
đồ thị đạt số cạnh tối đa. => loại
- Thêm vào số đỉnh lớn hơn số cạnh: với đồ thị được xây theo kiểu bổ sung
1 nút, 1 cạnh, khi đó sẽ xuất hiện chu trình trong đồ thị => loại
Như vậy bằng cách bổ sung 1 đỉnh, 1 cạnh nối của đỉnh đó với đồ thị đã có ta
sẽ thu được đồ thị không chu trình có số cạnh lớn nhất |E| = |V| - 1.
=> |E| <= |V| - 1 với đồ thị không chu trình bất kỳ. Đpcm
c, Bất kỳ đồ thị liên thông nào có |V| - 1 cạnh là 1 cây.
Với |V| = 0, |V| = 1 => Đồ thị G liên thông không có chu trình.
Với đồ thị G lớn hơn.
2 E ≤ 2 V −2
=> ∃deg v ≤ 1
Nếu deg v 0 khi đó đồ thị không liên thông, điều này trái với giả
∑ deg v
thiết.
Nếu deg v 1 , ta loại v và cạnh của v ra khỏi đồ thị G thu được đồ thị
G1 có:
|V| - 1 đỉnh và |E| - 1 = |V| - 2 cạnh.
Bằng cách qui nạp => G1 là mạch hở.
Nếu thêm v vào G1 thì không thể tạo thêm 1 chu trình vì bất kì chu trình
nào đi vào v sẽ không có cạnh để đi tiếp => G không có chu trình.
=> G là cây
d, Bất kỳ đồ thị không chu trình bào có |V| - 1 cạnh là 1 cây.
Như chứng minh ở phần b, đồ thị không chu trình có |V| - 1 cạnh được xây
dựng bằng cách thêm liên tục 1 cạnh và 1 nút mới vào 1 đồ thị cơ sở 1 nút cho
NHÓM 26
Page 4
BÀI TẬP LỚN TOÁN RỜI RẠC
đến khi số đỉnh bằng |V|. Bằng cách làm vậy ta sẽ thu được một đồ thị liên
thông, không chu trình, có số cạnh bằng |V| - 1. Như vậy đây sẽ là 1 cây.
e, Mọi đồ thị liên thông tối thiểu là 1 cây.
Giả sử G là một đồ thị liên thông, có một chu trình. Giả sử u, v là đỉnh
liền kề trên chu trình, và có chu trình là u, x 1, … , xk, v, u. Ta xóa bất kỳ 1
cạnh trên chu trình đó ví dụ cạnh (u, v) ta vẫn có con đường đi từ u đến v là
u, x1, …, xk, v do đó đồ thị G vẫn còn liên thông, không bị ngắt kết nối, G
không phải là đồ thị liên thông tối thiểu. => đồ thị liên thông tối thiểu là đồ
thị liên thông không có chu trình. Mà theo định nghĩa cây là một đồ thị liên
thông không có chu trình.
Vậy một đồ thị liên thông tối thiểu là cây.
f, Mọi đồ thị không chu trình tối đa là 1 cây.
Đồ thị không chu trình tối đa là đồ thị không chu trình mà khi thêm 1 cạnh
vào đồ thị sẽ tạo ra chu trình.
Giả sử G là đồ thị không chu trình tối đa. Ta thêm 1 cạnh nối 2 đỉnh bất kì u,
v của đồ thị và đồ thị sẽ có 1 chu trình đi qua u, v => trước đó phải tồn tại đường
đi từ u đến v. Từ đó ta thấy luôn có đường đi giữa các đỉnh trong đồ thị G, tức là
G là 1 đồ thị liên thông không có chu trình. Và vì thế G là 1 cây.
g, Một đồ thị là một cây khi và chỉ khi có duy nhất một đường đi từ đỉnh này
sang đỉnh khác.
- Chứng minh một đồ thị là 1 cây thì có duy nhất một đường đi từ đỉnh này
sang đỉnh khác:
Một đồ thị là một cây thì đồ thị đó sẽ liên thông và không có chu trình. Đồ thị
liên thông đảm bảo luôn có 1 đường đi từ đỉnh này sang đỉnh khác. Đồ thị
không chu trình sẽ đảm bảo có nhiều nhất một con đường đi giữa 2 đỉnh bất
kỳ vì nếu có nhiều hơn 1 con đường giữa 2 đỉnh thì sẽ có 1 chu trình đi qua 2
điểm đó.
Vì vậy đồ thị là 1 cây sẽ có duy nhất một con đường từ đỉnh này đến đỉnh
khác.
- Chứng minh đồ thị có duy nhất một đường từ đỉnh này đến đỉnh khác là
một cây
Có 1 con đường từ đỉnh này đến đỉnh khác => luôn tồn tại đường đi giữa 2
đỉnh bất kỳ và do đó đồ thị là liên thông.
NHÓM 26
Page 5
BÀI TẬP LỚN TOÁN RỜI RẠC
Nếu giữa 2 đỉnh bất kỳ chỉ có 1 con đường, giả sử là 2 đỉnh u, v. Khi đi từ u
đến v sẽ không còn con đường nào khác để đi từ v về u. Và khi đó đồ thị sẽ
không có chu trình. Một đồ thị liên thông không có chu trình thì sẽ là một
cây.
h, Mọi cây có chứa đỉnh bậc N thì có tối thiểu N lá.
Xét tại đỉnh v với deg(v) = N => v có N đỉnh lân cận u1, …, uN.
Xét đường đi dài nhất đi qua v và u 1 giả sử đó là yn…, v, u1, x1, …, xn. Vì
đây là đường đi dài nhất nên nó sẽ đi qua tất cả các đỉnh lân cận của x n. Nếu xn
có đỉnh lân cận là yn, v, u1, xi 1≤ i ≤ n−2 thì sẽ tồn tại 1 chu trình, điều này là
không thể với 1 cây. => xn chỉ có đỉnh lân cận duy nhất là xn-1 => xn là 1 lá =>
nhánh u1 có ít nhất 1 lá.
Tương tự ta sẽ có cây con đỉnh v sẽ có ít nhất N lá.
=> Mọi cây chứa đỉnh bậc N sẽ có ít nhất N lá.
Vấn đề 3:
Gọi T là một đơn đồ thị vô hướng liên thông kết nối trật tự n . Chứng
minh T là một cây nếu kích thước của T là n -1 .
Biết trật tự của một cây là số nút mà nó có và kích thước của cây là số
cạnh mà nó có.
=>Gọi T là một đơn đồ thị vô hướng liên thông có n nút. Chứng minh T là
một cây nếu nó có n-1 cạnh.
Chứng minh:
Điều kiện cần: Nếu T là một cây có n nút thì nó là 1 đơn đồ thị vô hướng
liên thông có n – 1 cạnh.
Gọi P(n) là mệnh đề một cây có n nút thì có n-1 cạnh và T k là cây có k
cạnh. Ta thấy với n = 1 thì cây T có 1 nút và không có cạnh nào ∃ P(1) đúng.
Giả sử mệnh đề P đúng với n = k. Ta cần chứng minh P đúng với n = k+1.
Thật vậy: Ta xét việc thêm 1 nút v vào cây T k. Để đảm bảo T vẫn là 1 cây
sau khi thêm nút v thì v phải là 1 nút lá ∃ bậc của v là 1 hay chỉ có 1 cạnh nối
nút v vào cây Tk ∃ ta được cây Tk+1 mới có thêm 1 cạnh và 1 nút so với Tk.Mà
cây Tk có k nút và k-1 cạnh
đúng.
NHÓM 26
∃
cây Tk+1 có k+1 nút và k cạnh
Page 6
∃
P(k+1)
BÀI TẬP LỚN TOÁN RỜI RẠC
∃ Giả thiết quy nạp đúng.
Thử lại: Cho Tk+1 là cây bất kì với k+1 nút. Hủy bỏ bất kì một cạnh e của
T.Vì Tk+1 không có chu trình, nên e phải là cầu nối. Vì vậy loại e khỏi T k+1 sẽ tạo
ra 2 cây con T1 và T2 có k1 và k2 nút. Theo giả thiết quy nạp thì 2 cây T1 và T2 có
k1-1 và k2-1 cạnh. Đưa cạnh e lại một lần nữa ta được cây T k+1 có (k1 - 1) + (k2 1) + 1 = k cạnh. ∃ Giả thiết quy nạp đúng.
Điều kiện đủ: Nếu T là một đơn đồ thị vô hướng liên thông có n nút với
n-1 cạnh thì T là 1 cây.
Giả sử T không phải là 1 cây. Khi đó nó có chứa ít nhất một chu trình. Vì
đò thị T tồn tại chu trình nên tồn tại ít nhất 1 cạnh không phải là cầu nối. Loại bỏ
cạnh này khỏi đồ thị ta được đò thị T’ có n nút và n-2 cạnh.
Ta thử xây dựng 1 đơn đồ thị liên thông với n nút và n-2 cạnh xem có thể xảy ra
không. Đầu tiên chọn 2 đỉnh bất kì trong n đỉnh gọi là u 1 và u2, ta sử dụng một
cạnh để kết nối chúng, gọi là cạnh e1.
Tiếp theo chọn bất kì đỉnh khác đánh số là u 3 và sử dụng 1 cạnh để kết nối
nó với 1 trong 2 đỉnh u1 hoặc u2, gán nhãn là e2. Tiếp tục chọn bất kì một đỉnh
khác đánh số là u4, và sử dung 1 cạnh e3 để kết nối nó với 1 trong ba đỉnh còn
lại.Tiếp tục bước này cho đến khi chọn 1 đỉnh gắn nhãn nó là u n-1 , và sử dụng
cạnh en-2 để kết nối nó một trong các đỉnh u 1, u2, ….., un-2. en-2 đã là phần tử cuối
cùng trong tập cạnh, trong khi vẫn chưa kết nối hết số đỉnh. Vì vậy không thể
tạo một đơn đồ thị vô hướng liên thông từ n đỉnh và n-2 cạnh.
T phải là 1 cây.
Kết luân: từ điều kiện cần và đủ ∃ đpcm.
Vấn đề 4:
Đối với một đồ thị liên thông, nếu có 2k đỉnh bậc lẻ, thì đồ thị đó có thể
vẽ trong k nét.
Chứng minh:
Với G là 1 đồ thị liên thông, nếu có đúng 2 đỉnh bậc lẻ là u và v thì có thể
vẽ bằng 1 nét.
Thật vậy, ta gọi G’ là đồ thị thu được từ G bằng cách thêm vào cạnh (u,
v). Khi đó mọi đỉnh của G’ đều có bậc chẵn hay G’ là 1 đồ thị Euler. Bỏ cạnh (u,
v) ra khỏi chu trình Euler trong G’ ta có được đường đi Euler từ u đến v trong G
NHÓM 26
Page 7
BÀI TẬP LỚN TOÁN RỜI RẠC
hay G có thể vẽ bằng 1 nét. Đối với 1 đồ thị liên thông, nếu có 2k đỉnh bậc
lẻ( k>1), ta nối 2(k-1) đỉnh bậc lẻ bằng k-1 nét thì bài toán đưa về đồ thị có đúng
2 đỉnh bậc lẻ thì có thể vẽ bằng 1 nét mà ta đã chứng minh bên trên.
Vậy đối với một đồ thị liên thông, nếu có 2k đỉnh bậc lẻ, thì đồ thị đó có
thể vẽ trong k nét.
Vấn đề 5:
Chứng minh một đồ thị là một cây khi và chỉ khi nó là liên thông tối thiểu,
tức là loại bỏ bất kỳ cạnh sẽ ngắt kết nối của đồ thị.
Chứng minh:
Chiều thuận: Một đồ thị là một cây thì nó là liên thông tối thiểu.
Theo định nghĩa, cây là một đồ thị mà trong đó hai đỉnh bất kì đều được
nối với nhau bằng đúng một đường đi. Nếu chúng ta loại bỏ cạnh (u, v), thì u và
v sẽ ngắt kết nối do (u, v) là con đường duy nhất. Như vậy một cây là đồ thị liên
thông tối thiểu.
Chiều đảo: Một đồ thị liên thông tối thiểu thì nó là cây.
Giả sử G là một đồ thị liên thông, có một chu trình. Giả sử u, v là đỉnh
liền kề trên chu trình, và có chu trình là u,x1,x2,…,xk,v,u. Ta xóa bất kỳ 1 cạnh
trên chu trình của đồ thị G ví dụ cạnh (u, v) ta vẫn có con đường đi từ u đến v là
u,x1,x2,…,xk,v do đó đồ thị G vẫn còn liên thông, không bị ngắt kết nối, G không
phải là đồ thị liên thông tối thiểu. Ngược lại đồ thị liên thông tối thiểu là đồ thị
liên thông không có chu trình. Mà theo định nghĩa cây là một đồ thị liên thông
không có chu trình. Vậy một đồ thị liên thông tối thiểu là cây.
Kết luận: Một đồ thị là một cây khi và chỉ khi nó là liên thông tối thiểu.
Vấn đề 6:
Ông bà Smith tổ chức buổi tiệc tại nhà cùng với n cặp vợ chồng. Mọi
người bắt tay nhau và ông Smith quan sát thấy:
- Không có cặp vợ chồng nào bắt tay nhau.
- Không có ai tự bắt tay với mình.
- Không có ai bắt tay nhiều hơn 1 lần với 1 người khác.
NHÓM 26
Page 8
BÀI TẬP LỚN TOÁN RỜI RẠC
- Số cái bắt tay của mỗi người (bao gồm n cặp đôi và bà Smith) là khác
nhau.
1. Với n=3, n=4 tính số cái bắt tay của ông bà Smith.
2. Tính số cái bắt tay của ông bà Smith trong trường hợp tổng quát.
Chứng minh:
1. Với n=3 . ta sẽ có 3 că ăp vợ chồng đến tham dự nên sẽ có 6 người . khi đó
do không có ai bắt tay nhiều hơn 1 lần với 1 người khác nên ta sẽ có ông bà
smith mỗi người có 3 lần bắt tay
Với n=4 . tương tự ta sẽ được số lần bắt tay của ông bà smith là 4 lần
2. Với trường hợp tổng quát . Để thuận tiện, ta kí hiệu Pi là vị khách (hoặc bà
Smith) với i cái bắt tay. P2n là số cái bắt tay với mỗi người trừ vợ/chồng của
mình do đó P0 là vợ hoặc chồng mình. Bây giờ chúng ta thấy rằng cặp đôi
không thể ông bà Smith: thấy rằng ông Smith không thể có 0 cái bắt tay, hoặc
P2n có thể có nhiều hơn một cái bắt tay. Bây giờ không tính ông bà Smith thì số
lượng cái bắt tay của những người khác ít nhất giảm đi 1. Số cái bắt tay của ông
bà Smith và n-1 cặp vợ chồng là 0,1,2... 2n-2. Bằng giả thiết quy nạp, ông bà
Smith sẽ có n-1 cái bắt tay với n-1 cặp vợ chồng. Cộng từng cái bắt tay 1 của họ
đã có với P2n , ông bà Smith đã có n cái bắt tay. Do đó với n bất kì >1, ông bà
Smith có tất cả n cái bắt tay.
Vấn đề 7:
Xác định cặp đồ thị đẳng cấu.
NHÓM 26
Page 9
BÀI TẬP LỚN TOÁN RỜI RẠC
Hình 2
Hình 3
Trả lời:
2 đồ thị hình 2 là đẳng cấu.
|
V1| = |V2| = 6
|E1| = |E2| = 9
Điều kiện cần để 2 đồ thị đẳng cấu
Số đỉnh bậc chẵn bằng nhau
Chuyển tên đỉnh theo cách: A(2), B(3), C(4), D(1), E(5), F(6)
2 đồ thị hình 3 là đẳng cấu.
|V1| = |V2| = 5
NHÓM 26
Điều kiện cần để 2 đồ thị đẳng cấu
Page 10
BÀI TẬP LỚN TOÁN RỜI RẠC
|E1| = |E2| = 5
Số đỉnh bậc chẵn bằng nhau
Chuyển tên đỉnh theo cách: A(A), B(C), C(E), D(B), E(D)
Vấn đề 8:
Các trình tự bên dưới có phải trình tự bậc của đồ thị đơn giản? Với mỗi
trường hợp, hãy làm theo các yêu cầu:
Tạo một đồ thị từ tình tự bậc, hoặc chỉ ra trình tự không phải là trình tự
bậc của bất kì đồ thị đơn giản nào.
1.
2.
3.
4.
(3, 3, 3, 1)
(4, 4, 4, 2, 2)
(4, 3, 2, 2, 1)
(3, 3, 3, 3, 3, 3)
Trả lời:
1. (3, 3, 3, 1) đây không phải là trình tự bậc của đồ thị. Mỗi đỉnh bậc 3 có
thể có tối đa 2 cạnh nối từ 2 đỉnh bậc 3 khác, nhưng 1 đỉnh bậc 1 còn lại
chỉ có thể có 1 cạnh. Như vậy không đủ số cạnh để tạo ra được 3 đỉnh bậc
3.
2. (4, 4, 4, 2, 2) đây không phải là trình tự bậc của đồ thị. Mỗi đỉnh bậc 4 có
thể có tối đa 2 cạnh nối từ 2 đỉnh bậc 4 khác. Như vậy cần thêm 6 cạnh
nữa để có 3 đỉnh bậc 4 trong khi 2 đỉnh bậc 2 chỉ cung cấp tối đa 4 cạnh.
Như vậy không thể có đồ thị với số bậc như trên.
3. (4, 3, 2, 2, 1) là trình tự bậc của đồ thị như hình dưới
4. (3, 3, 3, 3, 3, 3) là trình tự bậc của đồ thị như hình dưới
NHÓM 26
Page 11
BÀI TẬP LỚN TOÁN RỜI RẠC
NHÓM 26
Page 12
BÀI TẬP LỚN TOÁN RỜI RẠC
DỊCH TÀI LIỆU– TẬP HỢP, QUAN HỆ
Chương 1
Tập hợp, quan hệ
1.1. Định nghĩa
1.1.1.Tập hợp và giá trị
Khái niệm tập hợp là một trong những khái niệm cơ bản của toán học.
Chúng tôi sẽ không cố gắng để định nghĩa chính xác một tập hợp. Tuy
nhiên, chúng ta có thể mô tả tập hợp: một bộ xác định các đối tượng nào
đó. Các đối tượng cấu thành tập hợp có thể là bất kì đối tượng nào và
được gọi là phần tử của tập hợp. Các phần tử trong một tập hợp không cần
phải có bất kỳ điểm chung (trừ các thuộc đặc trưng để chúng là phần tử
tập hợp). Như vậy, nếu không có hạn chế về số lượng các phần tử được
cho phép trong một tập hợp; có thể có vô hạn, hữu hạn hoặc thậm chí
không có phần tử nào trong tập hợp. Tuy nhiên, một hạn chế cần chú ý:
cho trước một tập hợp và một đối tượng, chúng ta sẽ có thể quyết định (về
nguyên tắc - nó có thể khó khăn trong thực tế) có hay không các đối
tượng thuộc một tập hợp. Một khái niệm chung như thế có rất nhiều ví dụ
quen thuộc và cũng có rất nhiều những ví dụ trừu tượng.
Ví dụ 1.
1. Một tập hợp có thể chứa các phần tử: Niuton, Tháp Hà Nội và số
π . Đây là một tập hợp hữu hạn.
2. Tập hợp các số nguyên dương chẵn là tập hợp vô hạn.
3. Xem xét “tập hợp” 10 bài hát hay nhất mọi thời đại. Điều đó chưa
được thừa nhận cho đến khi ta đưa ra được định nghĩa “hay nhất”.
Tốt nhất đối với bạn, hay với tôi? Nếu không câu nệ chúng ta có thể
xác định một bài hát có thuộc tập hợp không.
Ký hiệu
Chúng ta thường dùng chữ hoa để đặt tên cho tập hợp và dùng chữ thường
để biểu thị phần tử. (Đôi khi điều này không đúng, ví dụ như khi phần tử
là các tập hợp.) Ký tự ∃ để chỉ “một phần tử thuộc”.
a ∃ A nghĩa là (phần tử) a thuộc (tập hợp) A
NHÓM 26
Page 13
BÀI TẬP LỚN TOÁN RỜI RẠC
a ∃ A nghĩa là
¬ a∃ A
hoặc a không thuộc A
1.1.2.Đặc điểm của tập hợp
Tập hợp có thể được định nghĩa bằng nhiều cách khác nhau. Trước tiên
chúng ta xem xét 2 cách: liệt kê và vị từ đặc trưng.
Liệt kê: Đơn giản nhất là liệt kê các giá trị trong dấu {}. 2 ví dụ đầu có thể
viết:
A Niuton ,Tháp Hà Nội , π
B 2, 4, 6,8,…
Ở trường hợp tập B không liệt kê hết các phần tử. Chúng ta liệt kê vừa đủ
các phần tử để tạo ra qui luật và dùng dấu “…” để biểu thị vẫn còn nhiều
phần tử khác. Một ví dụ khác:
Cho một số nguyên dương xác định n, Nn 1, 2,…, n} là tập hợp n số
nguyên dương đầu tiên. “…” biểu thị rằng có rất nhiều các phần tử khác
nhưng chúng ta không viết. Mặc dù trong trường hợp này chỉ có hữu hạn
các phần tử như vậy.
D , là tập hợp rỗng, nó không chứa phần tử nào. Tập rỗng được ký
hiệu là ∃ .
Vị từ đặc trưng. Liệt kê các phần tử của tập hợp là không thực tế ngoại trừ
các tập hợp nhỏ hoặc tập hợp giống như B, Nn. Ta thay thế bằng cách định
nghĩa các phần tử bằng tính chất hoặc điều kiện. Nếu P(x) là điều kiện của
biến đơn x, ta có thể chỉ ra giá trị của tập hợp là a với a thỏa mãn điều
kiện P(a). Một tập hợp có thể được định nghĩa như vậy.
A x : P x
(Điều này có nghĩa: tập hợp tất cả các giá trị x thỏa mãn P(x).)
Ví dụ 2
1. Tập hợp B có thể định nghĩa bằng cách B n :n là số chẵn, nguyên
dương}, hoặc B n :n 2 m , khi m >0 và m nguyên} hoặc
B 2 m: m0
và m nguyên}. Chú ý, mặc dù các điều kiện khác nhau
nhưng các phần tử là như nhau.
NHÓM 26
Page 14
BÀI TẬP LỚN TOÁN RỜI RẠC
2. Tập hợp Nn cũng có thể định nghĩa Nn p : p là số nguyên và
1≤ p ≤ n .
2
3. Tập hợp {3, 5} có thể định nghĩa bằng cách x : x −8 x 150 . Ta
2
nói {3, 5} là tập nghiệm của phương trình x −8 x 150 .
4. Đồ thị rỗng có thể định nghĩa bằng bất kỳ điều kiện nào không có giá
trị thỏa mãn. Ví du: ∃ x : x là một con thỏ màu xanh có đôi tai màu
tím}.
5. X x : x là một chính trị gia trung thực} không phải là tập hợp cho
đến khi định nghĩa chính xác “trung thực”.
Định nghĩa. Nếu A là một tập hợp hữu hạn, số phần tử của A, kí hiệu |A|,
là số lượng phần tử chứa trong A. Nếu A có vô hạn số phần tử, ta nói số
phần tử là vô hạn và viết |A| = ∞ . Ký hiệu khác cho số phần tử của tập
A là N(A), #A.
Ví dụ 3
1.
2.
∃∨ 0
πX, 2, Niuton., 3 .
0,1, … n
3. If
thì |X| = n+1.
4. |{2, 4, 6, 8, …}| = ∞ .
Mặc dù số phần tử dường như là một khái niệm đơn giản, nhưng xác định
số phần tử của một tập hợp có thể khó khăn trong thực tế. Trường hợp đặc
biệt khi một vài hoặc toàn bộ phần tử của một tập hợp chính là tập hợp. Ví
dụ cho X = {{1, 2}}. X chứa duy nhất một phần tử là tập hợp {1, 2}, vì
vậy |X| = 1. Đây là ví dụ rõ ràng để thấy sự khác biệt giữa tập hợp {1, 2}
(có 2 phần tử) và X, đồ thị chứa 1 phần tử {1, 2} duy nhất. Tương tự, tập
hợp ∃ và ∃ là khác nhau. Tập hợp phía trước không có phần tử
trong khi cái sau có 1 phần tử - tên là ∃ . Vì vậy
Ví dụ 4
NHÓM 26
Page 15
∃ 1
.
BÀI TẬP LỚN TOÁN RỜI RẠC
1. Cho A 1, 1, 2 . Chú ý rằng A có 2 phần tử, số 1 và tập hợp
{1, 2}. Vì vậy |A|=2.
∃ , 1, 2 2 ,
2. Tương tự, 1, 2, 1, 2 ∨ 3 ,
∃ , ∃ , 1, 2
3 .
1.1.3.Nghịch lý Russell
Nghịch lý, được đặt tên theo nhà logic học Bertrand Russell (1872-1970),
chỉ ra “tập hợp của các tập hợp” là khái niệm có vấn đề. Nếu coi nó là một
tập hợp, nó có thể là một ví dụ cho tập hợp chứa chính nó. Như vậy, một
vài “tập hợp” có thể chứa chính nó như một phần tử và số khác thì không.
Cho S là một “tập hợp” chứa “các tập hợp không chứa chính nó như là
phần tử”.
S A∨ A∃ A
Câu hỏi: Liệu S có là phần tử của chính nó?
Nếu “có”, thì S không là môt phần tử của chính nó theo đúng định
nghĩa.
Nếu “không”, thì S là một phần tử của S (theo định nghĩa)
Một giải pháp là tập hợp của mọi tập hợp không là một tập hợp.
1.2. Các phép toán tập hợp
1.2.1.So sánh các tập hợp
Hai tập hợp là bằng nhau nếu chúng chứa các phần tử như nhau, tức là A
= B nếu ∃ x x ∃ A∃ x ∃ B la mệnh đề đúng và ngược lại. Thứ tự các
phần tử được liệt kê là không quan trọng. Ta cũng có thể không quan tâm
đến sự lặp đi lặp lại của phần tử trong danh sách. Như vậy các tập hợp
dưới đây là bằng nhau:
11,−12, π ,
−12,11,0.5,0.5,,
π
−12, 11, 0.5,11,−12, π
.
Chúng ta nên lưu ý rằng ở đây chỉ có một tập rỗng, hoặc, nói một cách
khác, tất cả các tập rỗng là bằng nhau. Điều này là bởi vì bất kỳ hai tập
rỗng nào đều cùng không chứa cái gì.
Vì vậy nếu P(x) và Q(x) là 2 mệnh đề mà nó đúng với cùng đối tượng x
thì các đồ thị được chúng định nghĩa là bằng nhau.
x : P x x: Q x .
NHÓM 26
Page 16
BÀI TẬP LỚN TOÁN RỜI RẠC
2
x−9 0 , vì 2 mệnh đề
Q x x 1 x −9 0 đúng với cùng giá trị x =
x : x−4 25 x : x 1
Cho ví dụ:
2
P x x −4 25 và
-1 và x = 5.
Tập hợp con
Tập hợp B là tập hợp con của A, kí hiệu B ∃ A hoặc A ∃ B , nếu mọi
phần tử của B là phần tử của A: B ∃ A ∃∃ x x ∃ B ∃ x ∃ A .
Tập hợp B là tập hơp con thực sự của A nếu B là tập con của A và A chứa
ít nhất một phần tử không thuộc B. Kí hiệu B ∃ A thường được dùng
khi B là con thực sự của A, nhưng thỉnh thoảng nó được dùng với nghĩa
một tập con tùy ý. Như vậy B ∃ A khi và chỉ khi B ∃ A và B ≠ A .
Lưu ý ∃∃ A với mọi tập hợp A.
Ví dụ 5
2, 4, 6, … ∃ 1,2,3,… ∃ 0,1,2,3,…
∃
1.
hiệu
2.
Tương tự ta có thể sử dụng kí
để biểu diễn quan hệ 3 tập hợp trên.
Cho X 1, 2,3 . Thì 1 ∃ X trong khi 2, 3 không là con
của X. Tuy vậy 2, 3 là một phần tử của X, vì vậy 2,3 ∃ X
.
Để chứng minh 2 tập hợp bằng nhau, A B , ta chứng minh đầy đủ mỗi
tập hợp là con của tập hợp còn lại, A ∃ B và B ∃ A .
Từ một khái niệm rộng lớn, tập hợp thường được hạn chế phạm vi để các
tập hợp liên quan ở trong bối cảnh cụ thể. Đó là điều thuận lợi để xác định
tập tổng quát có tập con là các tập ta đang nghiên cứu hoặc học tập.
N 0,1,2,3…
là tập hợp các số tự nhiên.
Z .. ,−2,−1,0,1,2, …
Q
NHÓM 26
p
: p ,q∃ Z ,q ≠0
q
là tập các số nguyên.
là tập sô hữu tỉ
Page 17
BÀI TẬP LỚN TOÁN RỜI RẠC
R = tập hợp các số thực;
Số thực coi như tương ứng với điểm trên trục số hoặc được viết dưới dạng
thập phân.
2
C x iy : x , y ∃ R và i −1
là tập số phức.
Ta có quan hệ: N ∃ Z ∃ Q∃ R∃ C
Cũng thường xuyên được xử dụng là Z+, Q+ và R+. Chú ý N không bằng
Z+ vì 0 không thuộc Z+.
1.2.2.Sơ đồ Venn
Sơ đồ Venn là dạng biểu diễn trực quan quan hệ của các tập hợp. Một tập
hợp được biểu diễn như một vùng trong mặt phẳng, các phần tử được đặt
bên trong. Nếu một phần tử thuộc nhiều hơn một sơ đồ sẽ có 2 sơ đồ phải
chồng lên nhau và vùng đó gọi là vùng cắt nhau.
Ví dụ, nếu B ∃ A thì vùng mặt phẳng của B có thể ở trong vùng A.
Hình 1.
Hình 1
Ví dụ 7
Tập hợp A 1,2, … , 10 , B 2,4,6,8,12,13 ,C 2,3,5,7,11,13 có thể biểu
diễn bằng sơ đồ Venn như hình 2.
NHÓM 26
Page 18
BÀI TẬP LỚN TOÁN RỜI RẠC
Hình 2
1.2.3.Các phép toán tập hợp
Cho 2 tập hợp A, B ta có thể tạo ra tập hợp mới bằng cách.
Giao
Giao của A và B là tập hợp chứa mọi phần tử thuộc cả A và B. Kí hiệu
A ∩ B . Như vậy
A ∩ B x x ∃ A và x ∃ B
.
Tập hợp A giao B có thể hình dung dễ nhất qua sơ đồ Venn
A∩B
Kí hiệu
i∃ I Ai x x ∃ Ai ∃i ∃ I
Được sử dụng cho sự giao nhau của họ các đồ thị A, chỉ mục là tập hợp I.
2 tập hợp A, B không thể giao khi A ∩ B∃ .
Tập các tập hợp Ai i ∃ I
không giao nhau khi
i∃ I Ai ∃
.
Một tập các tập hợp đôi một không giao nhau nếu mỗi cặp tập hợp đều
không giao nhau.
NHÓM 26
Page 19