chương 1: quan hệ ma trận

Chia sẻ: Lê Trang | Ngày: | Loại File: PDF | Số trang:3

Thêm vào BST

Báo xấu

100
lượt xem 12
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

câu 1: có bao nhiêu quan hệ khác nhau từ tập có m phần tử n phần tử.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: chương 1: quan hệ ma trận

Ch−¬ng 1. Quan hÖ Bμi tËp cho 1.1 1. Cã bao nhiªu quan hÖ kh¸c nhau tõ tËp cã m phÇn tö ®Õn tËp cã n phÇn tö? Quan hÖ bï cña quan hÖ R, ký hiÖu lμ R, lμ tËp c¸c cÆp ®−îc s¾p {(a, b)|(a, b) ∈ R}. T×m R−1 vμ R trong c¸c tr−êng hîp sau: / 2. R lμ quan hÖ < trªn Z . 3. R lμ quan hÖ chia hÕt trªn N + 4. R lμ quan hÖ hμm , nghÜa lμ R = {(a, f (a))|f (a) lμ ¶nh cña a qua ¸nh x¹ f }. 5. LiÖt kª 16 quan hÖ kh¸c nhau trªn tËp {0, 1} 6. Trong sè 16 quan hÖ kh¸c nhau trªn tËp {0, 1}, nh÷ng quan hÖ nμo lμ a. Ph¶n x¹ b. §èi xøng. c. Ph¶n xøng. d. B¾c cÇu. 7. Cã bao nhiªu quan hÖ trªn tËp gåm n phÇn tö lμ a. Ph¶n x¹ b. §èi xøng. c. Ph¶n xøng. 8. Cho R lμ quan hÖ cã tÝnh ph¶n x¹ trªn tËp A. Chøng minh r»ng Rn còng cã tÝnh ph¶n x¹ víi mäi sè nguyªn d−¬ng n. 9. Cho R lμ quan hÖ cã tÝnh ®èi xøng trªn tËp A. Chøng minh r»ng Rn còng cã tÝnh ®èi xøng víi mäi sè nguyªn d−¬ng n. 10. ChØ ra mét vÝ dô vÒ mét quan hÖ b¾c cÇu R sao cho R2 = R Bμi tËp cho 1.2 1. Cho tËp A = {1, 2, 3, 4}. BiÓu diÔn c¸c quan hÖ R, S trªn A b»ng ma trËn víi thø tù cña c¸c phÇn tö cña A ®−îc liÖt kª t¨ng dÇn vμ R, S cho sau ®©y: a. R = {(1, 1), (1, 2), (2, 3), (4, 2)}. 1
b. S = {(1, 1), (1, 3), (2, 1), (2, 3), (2, 4), (3, 1), 3, 2), (4, 1)} Cho tËp A = {a, b, c, d} vμ c¸c quan hÖ P, Q trªn tËp A ®−îc biÓu diÔn 2. bëi ma trËn sau (t−¬ng øng víi thø tù ®· ®−îc liÖt kª cña phÇn tö cña ⎛ ⎞ ⎛ ⎞ 1010 1001 ⎜0 1 0 1⎟ ⎜0 1 1 0⎟ A): a. MP = ⎝ b. MQ = ⎝ ⎠; ⎠. H·y 1100 1010 0011 0011 liÖt kª c¸c cÆp thuéc mçi quan hÖ P, Q. 3. C¸c quan hÖ ®· cho trong c¸c bμi tËp 1 vμ 2 cã nh÷ng tÝnh chÊt g× trong c¸c tÝnh chÊt ph¶n x¹, ®èi xøng, ph¶n xøng, b¾c cÇu. T×m c¸c ma trËn biÓu diÔn cña c¸c quan hÖ P −1 , P , P 2 víi P lμ quan 4. hÖ t×m ®−îc trong bμi tËp 2. 5. T×m c¸c ma trËn biÓu diÔn cña c¸c quan hÖ P ∪ Q, P ∩ Q, P Q, QP, P 2 , P 3 , P 4 víi P vμ Q lμ c¸c quan hÖ cã ma trËn biÓu diÔn MP , MQ cho trong bμi tËp 2. VÏ c¸c ®å thÞ biÓu diÔn c¸c quan hÖ R, S cho trong bμi tËp 1 vμ c¸c ®å 6. thÞ biÓu diÔn c¸c quan hÖ P, Q t×m ®−îc trong bμi tËp 2. [k] Chøng minh r»ng nÕu MR lμ ma trËn biÓu diÔn quan hÖ R th× MR lμ 7. ma trËn biÓu diÔn quan hÖ Rk , víi k = 1, 2, 3, .... 8. BiÓu diÔn quan hÖ b»ng danh s¸ch liªn kÕt. 9. BiÓu diÔn quan hÖ b»ng m¶ng c¸c b¶n ghi Bμi tËp cho 1.3. 1. Cho R lμ quan hÖ {(a, b)|a = b} trªn tËp hîp c¸c sè nguyªn Z . T×m bao ®ãng ph¶n x¹ cña R. 2. Cho R lμ quan hÖ {(a, b)|a lμ −íc cña b} trªn tËp hîp c¸c sè tù nhiªn N . T×m bao ®ãng ®èi xøng cña R. 3. Chøng minh r»ng: Bao ®ãng ph¶n x¹ cña quan hÖ R lμ S = R ∪ I . Bao ®ãng ®èi xøng cña quan hÖ R lμ S = R ∪ R−1 . 4. Chøng minh r»ng nÕu R lμ quan hÖ trªn tËp h÷u h¹n A ®−îc biÓu diÔn bëi ma trËn MR , th×: 2
a. Ma trËn biÓu diÔn bao ®ãng ph¶n x¹ cña R lμ MR ∨ In . t b. Ma trËn biÓu diÔn bao ®ãng ®èi xøng cña R lμ MR ∨ MR trong ®ã M t lμ ma trËn chuyÓn vÞ cña M . 5. Dïng c¸c thuËt to¸n 1 vμ 2 ®Ó t×m bao ®ãng b¾c cÇu cña c¸c quan hÖ sau ®©y: a. R = {(1, 0)} trªn tËp A = {0, 1} b. R = {(a, b), (a, c)} trªn tËp A = {a, b, c}. c. R = {(a, a), (a, b), (b, c), (b, d), (c, a), (d, a), (d, b)} trªn tËp A = {a, b, c, d}. 6. ViÕt mét ch−¬ng tr×nh thùc hiÖn c¸c c«ng viÖc sau ®©y: a. NhËp sè phÇn tö n cña tËp A vμ c¸c phÇn tö cña A lμ c¸c ch÷ c¸i b. NhËp c¸c cÆp ch÷ c¸i thuéc mét quan hÖ R trªn A. c. X¸c ®Þnh ma trËn biÓu diÔn quan hÖ R vμ in ra mμn h×nh ma trËn ®ã. d. T×m vμ in ra mμn h×nh ma trËn biÓu diÔn quan hÖ bao ®ãng b¾c cÇu cña R. e. In ra mμn h×nh tÊt c¶ c¸c cÆp phÇn tö cña bao ®ãng b¾c cÇu cña R. Bμi tËp cho 1.4. 1. Chøng tá r»ng mçi quan hÖ t−¬ng ®−¬ng ®Òu cã thÓ biÓu diÔn bëi ma trËn khèi d¹ng ⎛ ⎞ ··· A11 A12 A1k ⎜ A21 A2k ⎟ ··· A22 MR = ⎜ . ⎟ . ⎝. ··· ⎠ . ··· . . · · · Akk Ak1 Ak2 trong ®ã ma trËn cã mäi phÇn tö b»ng 1 nÕu i = j Aij = ma trËn kh«ng (cã mäi phÇn tö b»ng 0) nÕu i = j 2. Cã thÓ cã bao nhiªu quan hÖ t−¬ng ®−¬ng trªn mét tËp cã n phÇn tö? 3