Tập Hợp Và ánh Xạ Toán Rời Rạc - Tài Liệu Text - 123doc

Tải bản đầy đủ (.pdf) (11 trang)

1. Trang chủ
>>
2. Cao đẳng - Đại học
>>
3. Công nghệ thông tin

Tập hợp và ánh xạ Toán rời rạc

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (445.2 KB, 11 trang )

Bà i 1 .TẬP HỢP VÀ ÁNH XẠ1.1. TẬP HỢP VÀ PHẦN TỬTập hợp và phần tử là những khái niệm tốn học ngun sơ, khơng thể địnhnghĩa mà ta chỉ có thể mơ tả chúng.Có 2 cách mơ tả tập hợp:Cách thứ nhất:Tất cả những đối tượng có một hoặc một vài tính chất chung nào đó tạo thànhmột tập hợp (đơi khi nói ngắn gọn là một tập); khi đó mỗi đối tượng là một phầntử của tập hợp đó.Thí dụ 1. Tập hợp các số ngun dương tạo nên tập N+.N  {1, 2, 3, ..., n, ...} . Khi đó các số 1, 2, 3, … là các phần tử của N+. Cácphần tử của N+ có 2 tính chất chung: đó là ngun và dương.Thí dụ 2. A  {1, 3, 5, 7, ...} là tập hợp các số nguyên dương lẻ. Các phần tửcủa A có 3 tính chất chung là ngun, dương và lẻ.Nếu x là phần tử của A ta viết x  A ; nếu x không phải phần tử của A thì taviết x  A .Khi mơ tả tập hợp theo cách này phải đạt được yêu cầu sau đây: Khi đưa ramột đối tượng bất kỳ thì các tính chất chung mà chúng ta nêu lên phải đủ đểkhẳng định đối tượng đó có phải là phần tử của tập hợp hay khơng.Trong thí dụ 2: số 15  A ; số 16  A vì 16 khơng có tính chất lẻ.Trong trường hợp u cầu trên khơng đạt được ta phải dùng cách khác.Cách thứ hai:Liệt kê các phần tử của tập hợp.Thí dụ 1. B  {2, 4, 5, 6, 8}Khi mô tả tập hợp theo cách này thì lại khơng địi hỏi các phần tử của tập hợpphải có một tính chất nào giống nhau.Thí dụ 2. C  {0, a, Hà Nội, *}.1.1.1. Tập hữu hạn và tập vô hạn.Số lượng phần tử của A gọi là bản số của A; ký hiệu là |A| hay N(A); đó làmột số nguyên dương.Nếu |A| là một số hữu hạn thì A là tập hữu hạn, cịn gọi là tập rời rạc. Tốnrời rạc chỉ quan tâm đến các tập rời rạc.Nếu A không phải tập hữu hạn thì A là tập vơ hạn.Thí dụ.A  {2, 4, 6, 8} là tập hữu hạn.N  {0, 1, 2, ...,n, ...} : tập các số tự nhiên là tập vô hạn.Z  {0,  1,  2, ...,  n, ...} : tập các số nguyên là tập vô hạn.1 1.1.2. Tập rỗng.Nếu | A |  0 thì A gọi là tập rỗng, đó là tập khơng chứa một phần tử nào.Việc đưa vào tập rỗng rất có ý nghĩa khi ta nghiên cứu về các phép toán trên tậphợp.Thí dụ.A là tập các nghiệm số thực của phương trình x 2  3x  2  0 thìA  {1, 2} .Cịn tập nghiệm thực của phương trình x 2  x  1  0 là một tập rỗng vìphương trình này khơng có nghiệm thực.Ta ký hiệu tập rỗng là  .1.1.3. Sự bằng nhau của hai tập.Hai tập A và B gọi là bằng nhau (ta viết A  B ) nếu chúng bao gồm nhữngphần tử như nhau, nghĩa là:xA  x BThí dụ.A  {x, 2, 5, 4} và B  {5, x, 4, 2} là hai tập bằng nhau.Thứ tự hay vị trí của các phần tử khơng quan trọng.1.1.4. Sự bao hàm và tập con.Nếu x  A  x  B thì ta nói: A bao hàm trong B hoặc A chứa trong B. B bao hàm A hay B chứa A. A là tập con của B.Để diễn đạt điều này ta viết A  B hay B  A .VậyA  B nếu A  B và B  A A chứa các phần tử của nó. Tập rỗng  là tập con của mọi tập A.Để hình dung quan hệ giữa hai tập người ta dùng sơ đồ Ven để biểu diễn hìnhhọc một tập, coi mỗi tập là một vịng phẳng kín, mỗi điểm bên trong là một phầntử của tập đó. Khi đó quan hệ A  B được biểu thị bởi hình 1 – vịng A nằmtrong vịng B.ABHình 12 1.1.5. Tập vũ trụ.Tập vũ trụ ký hiệu là U, đó là tập bao hàm mọi tập khác; khi biểu diễn tập Ubằng sơ đồ Ven, người ta dùng 1 hình vng hoặc hình chữ nhật. Khi đó mọi tậpkhác đều nằm trong hình vng hoặc hình chữ nhật đó (Hình 2).CABHình 21.1.6. Tập lũy thừa.Cho tập A, tập lũy thừa của A ký hiệu là P(A) hay 2A là tập mọi tập con của A(bao gồm cả tập rỗng và bản thân tập A).Thí dụ: A  {1, 2, 3} thìP(A)  , {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} .Tập lũy thừa của A thường liên quan đến việc trắc nghiệm những tập con củaA để xem chúng có thỏa mãn một tính chất nào đó hay khơng.Sau này ta sẽ chứng minh: Nếu | A |  n thì | P(A) |  | 2A |  2n.1.2. CÁC PHÉP TOÁN TẬP HỢPTừ hai tập A và B cho trước tạo ra một tập mới theo một cách nào đó, ta gọiđó là phép hợp thành. Mỗi phép hợp thành như thế là một phép toán tập hợp.1.2.1. Phép hợp.Hợp của 2 tập A và B, ký hiệu là A  B , là tập chứa tất cả các phần tử thuộcA hoặc thuộc B, nghĩa là:x  A  B  {x  A hoặc x  B}A  B được biểu diễn bởi sơ đồ Ven như hình 3.ABABHình 33 Thí dụ. A  {1, 3, 5}, B  {1, 2, 3} A  B  {1, 2, 3, 5}1.2.2. Phép giao.Giao của hai tập A và B, ký hiệu là A  B , là tập chứa tất cả các phần tử vừathuộc A, vừa thuộc B, nghĩa làx  A  B  {x  A và x  B}Biểu diễn của A  B bằng sơ đồ Ven có dạng như hình 4.BAABHình 4Thí dụ.Cũng trong thí dụ trênA  {1, 3, 5}, B  {1, 2, 3} thìA  B  {1, 3}Nếu A  B   thì ta nói rằng A và B là hai tập rời nhau.Thí dụ: A  {1, 3, 5, 7, 9}, B  {2, 4, 6, 8} là hai tập rời nhau vìA  B  .1.2.3. Phép trừ.Hiệu của hai tập A và B ký hiệu là A\B, là tập chứa các phần tử thuộc A màkhông thuộc B. Biểu diễn của A\B bằng sơ đồ Ven có dạng như hình 5.BAA\BHình 5Thí dụ. A  {1, 2, 5}, B  {1, 2, 3} A\B = {5}1.2.4. Tập bù.Nếu A  E thì E\A là tập bù của A trong E và ký hiệu là A .Dễ dàng nhận thấy A  ATrường hợp đặc biệt nếu E  U thì A  U \ A được gọi ngắn gọn là tập bù củaA.4 AAHình 6 Luật De Morgan: A  E;  B  E ta có:a) A  B  A  Bb) A  B  A  BCác phép toán a) và b) có thể mở rộng cho n tập; khi đó định luật De Morgansẽ có dạng tổng quát sau đây:i Ii IAi Ai i Ii IAiAiCác phép toán nêu trên thỏa mãn các đẳng thức dưới đây mà ta gọi đó là cácluậtĐẳng thứcTên gọiA ALuật đồng nhấtAUAAUUALuật nuốtAAAAAALuật lũy đẳngABBAABBALuật giao hoánA  (B  C)  (A  B)  CA  (B  C)  (A  B)  CLuật kết hợpA  (B  C)  (A  B)  (A  C)A  (B  C)  (A  B)  (A  C)Luật phân phốiABABLuật De MorganABABAALuật bù5 1.2.5. Phủ và phân hoạch.Cho S  {A1, A2 , ..., An } trong đó Ai (i  1, n) là các tập con của E. Nếuni 1Ai  E thì S gọi là một phủ của E.Nếu S là một phủ của E và Ai  A j    i  j thì S gọi là một phânhoạch của E.Thí dụ.E  {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};A1  {1, 3, 5, 7, 9};A2  {0, 2, 4, 6, 8};thì S  {A1, A2} là một phân hoạch của E.Khái niệm phân hoạch là cơ sở của “nguyên lý cộng” trong bài toán đếm màta sẽ nghiên cứu ở chương sau.1.2.6. Tích Đề-các.Tích Đề-các của 2 tập A và B, ký hiệu là A  B , là một tập được định nghĩanhư sau:A  B  {(a, b): a  A; b  B}Dễ dàng nhận thấy A  B khơng có tính giao hốn.Mở rộng cho tích Đề-các của n tập:A1  A2  ...  An  {(a1, a 2 , ..., a n ): a i  Ai , i  1, n}Nếu A1  A2  ...  An  A thì tích Đề-các được ký hiệu là A n , nghĩa là:An  A  A  ...  ADễ dàng chứng minh được A  B  A  BCho nên tích Đề-các là cơ sở của “nguyên lý nhân” trong bài toán đếm ởchương sau.1.3. QUAN HỆ TƯƠNG ĐƯƠNG VÀ QUAN HỆ THỨ TỰ1.3.1. Quan hệ 2 ngôi.Ta đưa vào tập E một quan hệ R có liên quan đến 2 phần tử của E. Xét 2 phầntử a và b của E, nếu a có quan hệ R với b thì ta viết aRb; khi đó R là quan hệ 2ngơi trên tập E.Thí dụ 1. Trên tập số thực : aRb  a  b là quan hệ 2 ngôi trên tập số thực.Thí dụ 2.E là tập các đường thẳng trên một mặt phẳng P nào đó.aRb  a / / b là quan hệ 2 ngôi.6 Thí dụ 3.E là tập các sinh viên trong 1 lớp học nào đóaRb  ”a cùng năm sinh với b” là một quan hệ 2 ngôi.Quan hệ 2 ngôi trên một tập E có thể có các tính chất sau đây:a) Tính phản xạ:Quan hệ R có tính chất phản xạ nếu aRa  a  EThí dụ:- Quan hệ “cùng năm sinh” có tính phản xạ- Quan hệ “nhỏ hơn” (a < b) khơng có tính phản xạ vì khơng thể cóa < a.b) Tính đối xứng:Quan hệ R có tính đối xứng nếu aRb  bRaThí dụ.- Quan hệ “cùng năm sinh” có tính đối xứng- Quan hệ “nhỏ hơn” (a < b) khơng có tính đối xứng vì từ a < b khơng thểsuy ra b < a.c) Tính bắc cầu:Quan hệ R gọi là có tính bắc cầu nếu (aRb và bRc)  aRcThí dụ 1.Quan hệ “cùng năm sinh” có tính bắc cầu; quan hệ “nhỏ hơn” cũng có tínhbắc cầu vì từ (a < b và b < c) suy ra a < c.Thí dụ 2.Trên tập các số nguyên dương N+ ta đưa vào quan hệ như sau:aRb  a và b là 2 số nguyên tố cùng nhau.Quan hệ R này khơng có tính bắc cầu; vì (4R5 và 5R8) khơng thể suy ra4R8 vì 4 và 8 khơng ngun tố cùng nhau do chúng có 2 ước chung khác 1 đó là2 và 4.d) Tính phản xứng:Quan hệ R gọi là có tính phản xứng nếu (aRb và bRa)  a = bThí dụ 1.Quan hệ aRb  a  b có tính phản xứng vì từ a  b và b  a ta suy raa = b (trên tập số thực)Thí dụ 2.E là tập các cán bộ trong một cơ quan, ta đưa vào quan hệ R như sau:aRb  lương của a không cao hơn lương của b.Quan hệ R này khơng có tính phản xứng vì (aRb và bRa) ta chỉ suy ralương của a = lương của b mà không thể suy ra a = b ; nghĩa là a và b có thể vẫnlà hai cán bộ khác nhau của cơ quan đó.7 1.3.2. Các phương pháp biểu diễn quan hệ 2 ngôi.a) Phương pháp liệt kê.Theo định nghĩa thì mọi quan hệ 2 ngôi R trên tập E đều là tập con của tậptích Đề-các E  E , nghĩa là ln viết được R  E  E . Do đó một trong nhữngphương pháp biểu diễn R là liệt kê tất cả các phần tử của R trong E  E .Thí dụ. Cho E  {a1, a 2 , a 3} . Tìm trong E một quan hệ 2 ngơi có tính phảnxạ, đối xứng nhưng khơng bắc cầu.Ta có:R  {(a1, a1 ), (a 2 , a 2 ), (a 3 , a 3 ), (a1, a 2 ), (a 2 , a1), (a 2 , a 3 ), (a 3 , a 2 )}Tính phản xạ được thể hiện ở 3 phần tử đầu, 4 phần tử sau thể hiện tính đốixứng. Ở đây ta có (a1, a 2 ) và (a 2 , a 3 )  R nhưng (a1, a 3 )  R nên khơng cótính chất bắc cầu..b) Phương pháp sơ đồ.Mỗi phần tử của E là một đỉnh của đồ thị, nếu a i Ra j thì có cung nối a i đếna j . Trong thí dụ trên ta cóa1a2a3c) Phương pháp ma trận quan hệ.Nếu E  {a1, a 2 , ..., a n } thì R được biểu diễn bởi ma trận vuông cấp n:R  (rij )n  n trong đó1rij  0khi a i Ra jkhi khơng có a i Ra j hay (a i , a j )  RTrong thí dụ trên ta có:1 1 0R   1 1 1 0 1 11.3.3. Quan hệ tương đương.Quan hệ 2 ngôi trên tập E gọi là quan hệ tương đương nếu nó có 3 tính chất:phản xạ, đối xứng và bắc cầu. Dễ dàng thấy rằng:- Quan hệ “cùng năm sinh” trên tập các sinh viên của một lớp là quan hệtương đương.- Quan hệ “song song” trên tập các đường thẳng trong một mặt phẳng nào đólà quan hệ tương đương.8 - Quan hệ “a < b” trên tập số thực không phải là quan hệ tương đương.Nếu R là quan hệ tương đương thì aRb có thể viết là a  b .Ta có định nghĩa sau:Giả sử R là một quan hệ tương đương trên E và x  E . Khi đó lớp tươngđương chứa x là tập con:x  {y  E : yRx}Định lý 1. Giả sử R là quan hệ tương đương trên E. Khi đó:1) x  E : x  x2) x, y  E, xRy  x  y3) Nếu x  y   thì 2 lớp tương đương x và y trùng nhau.Khi đưa quan hệ tương đương R vào E thì chúng chia E thành các lớp tươngđương.Các lớp tương đương này rời nhau và tạo nên một phủ của E; do đó nó là mộtphân hoạch của E.Việc đưa vào tập E một quan hệ tương đương là một cách tìm một phân hoạchcủa E, nhờ đó ta có thể tìm số phần tử của E bằng cách tìm tổng số các phần tửcủa tất cả các lớp tương đương.1.3.4. Quan hệ thứ tự.Quan hệ 2 ngôi R trên tập E gọi là quan hệ thứ tự nếu nó có 3 tính chất: phảnxạ, phản xứng và bắc cầu. Dễ dàng thấy rằng quan hệ ( a  b ) hay ( a  b ) làquan hệ thứ tự trên tập các số tự nhiên cũng như trên tập các số thực.a) Quan hệ thứ tự toàn phần.Cho R là một quan hệ thứ tự trên E, nếu  a, b  E ta đều có aRb hoặc bRathì R gọi là quan hệ thứ tự tồn phần; khi đó mọi phần tử của E được sắp xếptheo một thứ tự xác định theo quan hệ R và E là một tập có thứ tự tồn phần.b) Quan hệ thứ tự khơng tồn phần.Nếu R là một quan hệ thứ tự trên E nhưng không phải là quan hệ thứ tự tồnphần thì ta nói R là quan hệ thứ tự khơng tồn phần.Thí dụ.- Quan hệ  trên tập số thực là quan hệ thứ tự tồn phần vì với mọi số thựca và b ta ln có a  b hoặc b  a , và dó đó tập các số thực là tập có thứ tự toànphần.- Quan hệ  trên tập các véc tơ n chiều (trong không gian véc tơ n chiềuR n ) là quan hệ thứ tự khơng tồn phần vì  a  R n và  b  R n mà ta khơng cóa  b và cũng khơng có b  a . Tập R n cịn gọi là tập có thứ tự bộ phận.1.4. ÁNH XẠ1.4.1. Các định nghĩa.9 Định nghĩa 1.f gọi là ánh xạ từ tập A vào tập B nếu  x  A,  y duy nhất  B mà ta kýhiệu là f(x) và gọi là ảnh của x qua ánh xạ f. Ta viết:f :A Bxf (x)Định nghĩa 2.Nếu E  A thì ảnh của E qua f là tập:f (E)  {y  B:  x  E; y  f (x)}Hoặc ta cũng viết:f (E)  {f (x) : x  E}Chú ý.- Nếu f 1 (y)   thì y  f (A)- Nếu f 1 (y)  x thì x là phần tử duy nhất có ảnh là y.Định nghĩa 3.Cho f là một ánh xạ từ tập A vào tập B.a) f là toàn ánh nếu f (A)  Bb) f là đơn ánh nếu  x1, x 2  A và x1  x 2  f (x1 )  f (x 2 )c) f là một song ánh nếu f vừa là toàn ánh vừa là đơn ánh.Chú ý.Nếu f là một song ánh từ A lên B thì ta viết f : A  B . Khi đó  y  B,  xduy nhất  A để cho y  f (x) ; như vậy sự tương ứng y  x là một ánh xạ từB vào A mà ta ký hiệu f 1 .f 1 : B  Ayf 1 (y)  x với y  f (x)Và ta cóf f 1 (y)   y,  y  Bf 1  f (x)  x,  x  AVà trong trường hợp này ta nói f 1 là ánh xạ ngược của f.Thí dụ. Ký hiệu R là tập số thực; R  là tập số thực không âm.a) f : R  R cho bởi y  x 2 là một ánh xạ nhưng khơng phải là tồn ánh vìcác số âm không là ảnh của bất kỳ số x nào qua ánh xạ y  x 2 ; cũng không phảilà đơn ánh vì hai số x và x (với x  0 ) có chung một ảnh.b) f : R  R  cho bởi y  x 2 là tồn ánh nhưng khơng phải là đơn ánh.c) f : R   R  cho bởi y  e x là đơn ánh nhưng khơng phải là tồn ánh vìcác số  1 khơng là ảnh của bất kỳ số x  0 qua ánh xạ y  e x .10 d) f : R  R cho bởi y  ax  b (a  0) là song ánh (vừa là toàn ánh, vừalà đơn ánh). Ánh xạ ngược của nó là:f 1 : R  Ry  a 1y  a 1b1.4.2. Hợp (hay tích) của 2 ánh xạ.Cho 2 ánh xạ: f : A  B và g : B  C , khi đó: x  A,  y  B sao cho f (x)  yVà  y  B,  z  C sao cho g(y)  zDo đó  x  A,  z  C (qua ánh xạ trung gian f) sao cho g f (x)  zVậy có một ánh xạ từ A tới C xác định như sau:x  A  z  g f (x)  CĐịnh nghĩa 4.Hợp (hay tích) của hai ánh xạ f và g ký hiệu là g f : A  C xác định nhưsau: x  A  (g f )(x)  g f (x)   CHợp của 2 ánh xạ thường được biểu diễn bởi sơ đồ:ABfgCxy = f(x)z = g(y)g fThí dụ. Cho A  B  C  R ;x  R  y  f (x)  x 2  Ry  R  z  g(y)  y  3  RKhi đó ánh xạ hợp: g f : R  R xác định như sau:x  R  (g f )(x)  g f (x)   x 2  3  RĐịnh lý 3.Hợp của 2 đơn ánh là một đơn ánh.Hợp của 2 toàn ánh là một toàn ánh.Hợp của 2 song ánh là một song ánh.Cho ánh xạ f : A  B và A1, A 2 là 2 tập con bất kỳ của A; B1 , B2 là 2tập con bất kỳ của B. Khi đó:f (A1  A2 )  f (A1 )  f (A2 )f (A1  A2 )  f (A1 )  f (A2 )f 1 (B1  B2 )  f 1 (B1 )  f 1(B2 )f 1 (B1  B2 )  f 1 (B1 )  f 1(B2 )11

Tài liệu liên quan

• giao cua hai tap hop;hop cua hai tap hop
  • 3
  • 141
  • 0
• Tập hợp và các phép toán về tập hợp (phần 3)
  • 1
  • 449
  • 2
• Tập hợp và các phép toán về tập hợp
  • 1
  • 707
  • 1
• Giải bài tập trang 13 SGK Toán lớp 6 tập 1: Số phần tử của một tập hợp, Tập hợp con
  • 2
  • 899
  • 0
• Giải bài tập trang 13 SGK toán lớp 6 tập 1 số phần tử của một tập hợp, tập hợp con
  • 2
  • 606
  • 0
• Giải bài tập SGK trang 14 toán lớp 6 tập 1 số phần tử của một tập hợp, tập hợp con
  • 3
  • 538
  • 0
• Giải bài tập trang 6 SGK toán lớp 6 tập 1 tập hợp, phần tử của tập hợp
  • 2
  • 309
  • 0
• Tập hợp – phần tử của tập hợp
  • 5
  • 83
  • 0
• Tập hợp và các phép toán trên tập hợp
  • 7
  • 561
  • 3
• Tập hợp . Phần tử của tập hợp
  • 6
  • 246
  • 0

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(445.2 KB - 11 trang) - Tập hợp và ánh xạ Toán rời rạc Tải bản đầy đủ ngay ×