Toán học - Toán rời rạc

Chia sẻ: Nguyen Thi Nga | Ngày: | Loại File: PDF | Số trang:241

Thêm vào BST

Báo xấu

401
lượt xem 138
download

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

Nội dung tài liệu được biên soạn trình bày về: những khái niệm cơ bản về Logic, Tập hợp và suy luận Toán học, phương pháp đếm và nguyên lý Dirichlet, đồ thị và ứng dụng, Automat, văn phạm và ngôn ngữ hình thức của Toán rời rạc. Tài liệu hữu ích với các bạn chuyên ngành Toán.

Chủ đề:

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

Lưu

Nội dung Text: Toán học - Toán rời rạc

Ph¹m ThÕ Long – Chñ biªn NguyÔn §øc HiÕu, NguyÔn ThiÖn LuËn NguyÔn Xu©n Viªn, NguyÔn V¨n XuÊt To¸n rêi r¹c Hµ Néi – 2003
Lêi nãi ®Çu To¸n rêi r¹c lµ mét trong nh÷ng kiÕn thøc c¬ së ®-îc gi¶ng d¹y ë tÊt c¶ c¸c khoa C«ng nghÖ Th«ng tin hiÖn nay. Tuy nhiªn, tuú theo yªu cÇu kiÕn thøc vµ cÊu tróc cña ch-¬ng tr×nh ®µo t¹o mµ kÕt cÊu m«n häc mçi n¬i Ýt nhiÒu cã thÓ kh¸c biÖt. Nh»m ®¸p øng nh÷ng yªu cÇu ®a d¹ng vÒ kiÕn thøc, trong cuèn s¸ch nµy c¸c t¸c gi¶ ®· cè g»ng giíi thiÖu mét c¸ch c« ®äng hÇu hÕt nh÷ng néi dung c¬ b¶n cña To¸n häc rêi r¹c, bao gåm c¸c kiÕn thøc c¬ së vÒ logic, tËp hîp vµ ®¹i sè quan hÖ (Ch-¬ng I); mét sè bµi to¸n trong lý thuyÕt tæ hîp (Ch-¬ng II); ®å thÞ vµ c¸c bµi to¸n trªn ®å thÞ (Ch-¬ng III); ®¹i sè Boole vµ øng dông trong ph©n tÝch m¹ch ®iÖn tö (Ch-¬ng IV); ng«n ng÷ h×nh thøc vµ «t«mat (Ch-¬ng V). Trong c¸ch tr×nh bµy cuèn s¸ch, c¸c t¸c gi¶ quan t©m nhiÒu h¬n ®Õn kü thuËt gi¶i quyÕt vÊn ®Ò, kh«ng qu¸ c©u nÖ vµo nh÷ng ®ßi hái chÆt chÏ vÒ mÆt to¸n häc theo kiÓu “®Þnh lý-chøng minh”, kh«ng Ýt kh¸i niÖm vµ kÕt qu¶ chñ yÕu ®-îc tr×nh bµy th«ng qua c¸c vÝ dô vµ bµi tËp. Ngoµi kh¶ n¨ng t- duy l«gic nhÊt ®Þnh, gi¸o tr×nh kh«ng ®ßi hái tõ phÝa b¹n ®äc mét sù chuÈn bÞ ®Æc biÖt nµo vÒ to¸n häc nãi chung, v× vËy cã thÓ bè trÝ gi¶ng d¹y theo cuèn s¸ch nµy ngay tõ häc kú 1 n¨m thø nhÊt c¸c tr-êng ®¹i häc vµ cao ®¼ng. NÕu ®· cã mét sè hiÓu biÕt c¬ b¶n vÒ l«gic vµ tËp hîp (trong ph¹m vi c¸c môc 1-3 cña ch-¬ng I), b¹n ®äc cã thÓ t×m hiÓu bÊt kú ch-¬ng sau nµo mµ kh«ng cÇn tu©n thñ tr×nh tù c¸c ch-¬ng nªu trong cuèn s¸ch. Trong sè c¸c tµi liÖu tham kh¶o ®-îc nªu ë cuèi s¸ch, c¸c t¸c gi¶ muèn b¹n ®äc ®Æc biÖt l-u ý tµi liÖu To¸n rêi r¹c øng dông trong Tin häc cña Kenneth H. Rosen. Sù phong phó vµ ®a d¹ng cña c¸c vÝ dô vµ bµi tËp trong cuèn s¸ch ®ã sÏ hÕt søc h÷u Ých cho b¹n ®äc. Nh÷ng ai quan t©m ®Õn viÖc ch-¬ng tr×nh ho¸ mét sè thuËt to¸n nªu trong cuèn s¸ch nµy cã thÓ tham kh¶o thªm tµi liÖu To¸n rêi r¹c cña NguyÔn §øc NghÜa vµ NguyÔn T« Thµnh. Ph©n c«ng c«ng viÖc gi÷a c¸c t¸c gi¶ nh- sau:  Chñ biªn vµ hiÖu ®Ýnh toµn bé néi dung b¶n th¶o: Ph¹m ThÕ Long.  Ch-¬ng 1: NguyÔn Xu©n Viªn.  Ch-¬ng 2: NguyÔn ThiÖn LuËn, Ph¹m ThÕ Long.  Ch-¬ng 3: NguyÔn §øc HiÕu, Ph¹m ThÕ Long.  Ch-¬ng 4: Ph¹m ThÕ Long.
 Ch-¬ng 5: NguyÔn V¨n XuÊt. C¸c t¸c gi¶ xin bµy tá lßng c¶m ¬n ch©n thµnh PGS.TSKH NguyÔn Xu©n Huy (ViÖn C«ng nghÖ Th«ng Tin), PGS.TS §Æng Huy RuËn (§HQG Hµ Néi) ®· ®äc kü b¶n th¶o vµ cho nhiÒu ý kiÕn ®ãng gãp x¸c ®¸ng. Ch¾c ch¾n kh«ng thÓ tr¸nh khái nh÷ng thiÕu sãt trong cuèn s¸ch nµy. C¸c t¸c gi¶ rÊt mong nhËn ®-îc sù chØ b¶o vµ ®ãng gãp cña tÊt c¶ b¹n ®äc ®Ó cã thÓ hoµn chØnh néi dung cho nh÷ng lÇn xuÊt b¶n sau. C ¸c t ¸ c g i ¶
Môc lôc Ch-¬ng 1 5 Nh÷ng kh¸i niÖm c¬ b¶n vÒ logic, tËp hîp vµ suy luËn to¸n häc 1. MÖnh ®Ò, mÖnh ®Ò cã ®iÒu kiÖn vµ sù t-¬ng ®-¬ng logic . . . . . . . . . . . . . . . . . . . . . 5 1.1 MÖnh ®Ò . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 C¸c phÐp to¸n trªn mÖnh ®Ò . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 MÖnh ®Ò cã ®iÒu kiÖn vµ sù t-¬ng ®-¬ng logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2. TËp hîp vµ c¸c phÐp to¸n trªn tËp hîp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1 TËp hîp, tËp con vµ tÝch Decac . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 C¸c phÐp to¸n trªn tËp hîp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3. L-îng tö vµ vÞ tõ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.1 Hµm mÖnh ®Ò . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 VÞ tõ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.3 Phñ ®Þnh cña vÞ tõ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4. Quan hÖ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.1 Kh¸i niÖm vµ tÝnh chÊt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.2 Ma trËn quan hÖ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.3 Quan hÖ t-¬ng ®-¬ng, líp t-¬ng ®-¬ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.4 Quan hÖ n - ng«i. C¬ së d÷ liÖu quan hÖ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5. Suy luËn to¸n häc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.1 C¸c ph-¬ng ph¸p chøng minh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.2 Quy n¹p to¸n häc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 5.3 §Ö quy vµ øng dông . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Bµi tËp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Ch-¬ng 2 39 C¸c ph-¬ng ph¸p ®Õm vµ nguyªn lý Dirichlet 1. C¸c nguyªn lý ®Õm c¬ b¶n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 1.1. Nguyªn lý céng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 1.2 Nguyªn lý nh©n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2. Mét sè bµi to¸n ®Õm c¬ b¶n: Ho¸n vÞ, tæ hîp, chØnh hîp . . . . . . . . . . . . . . . . . . . . . 42 2.1. ChØnh hîp lÆp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.2. ChØnh hîp kh«ng lÆp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.3. Ho¸n vÞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.4. Tæ hîp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.5. Tæ hîp lÆp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.6. Ho¸n vÞ cña tËp hîp cã c¸c phÇn tö gièng nhau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.7. Ph©n bæ c¸c ®å vËt vµo trong hép . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.8. So s¸nh c¸c cÊu h×nh tæ hîp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3. Sinh c¸c cÊu h×nh tæ hîp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.1. Sinh c¸c ho¸n vÞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.2. Sinh c¸c tæ hîp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.3. NhÞ thøc Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4. Nguyªn lý Dirichlet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.1. Më ®Çu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.2. Nguyªn lý Dirichlet tæng qu¸t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.3. Mét vµi øng dông thó vÞ cña nguyªn lý Dirichlet . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5. HÖ thøc truy håi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5.1. Kh¸i niÖm vµ c¸c vÝ dô . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5.2. Gi¶i c¸c hÖ thøc truy håi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.3. Quan hÖ chia ®Ó trÞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 6. Nguyªn lý bï trõ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 6.1. Më ®Çu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 6.2. Nguyªn lý bï trõ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 Bµi tËp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 Ch-¬ng 3 85 ®å thÞ vµ øng dông 1. C¸c kh¸i niÖm c¬ b¶n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 1.1. Kh¸i niÖm vµ thuËt ng÷ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 1.2. §-êng ®i. Chu tr×nh. §å thÞ liªn th«ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 1.3. Mét sè d¹ng ®å thÞ ®¬n ®Æc biÖt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 2. BiÓu diÔn ®å thÞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 2.1. Ma trËn kÒ, ma trËn träng sè. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 94 2.2. Ma trËn liªn thuéc. ................................................. 95 2.3. Sù ®¼ng cÊu cña c¸c ®å thÞ. ........................................... 3. C¸c thuËt to¸n t×m kiÕm trªn ®å thÞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 3.1. T×m kiÕm theo chiÒu s©u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 3.2. T×m kiÕm theo chiÒu réng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4. §å thÞ Euler vµ ®å thÞ Hamilton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 4.1 §-êng ®i Euler vµ chu tr×nh Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 4.2. §-êng ®i vµ chu tr×nh Hamilton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 5. Bµi to¸n t×m ®-êng ®i ng¾n nhÊt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 5.1. §å thÞ cã träng sè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 5.2. ThuËt to¸n t×m ®-êng ®i ng¾n nhÊt Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 6. §å thÞ ph¼ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 6.1 Kh¸i niÖm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 6.2. C«ng thøc Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 6.3. §Þnh lý Kuratowski . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 7. T« mµu ®å thÞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 7.1. Më ®Çu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 7.2. Mét sè øng dông cña bµi to¸n t« mµu ®å thÞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 8. C©y vµ øng dông . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 8.1. Më ®Çu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 8.2. C¸c ph-¬ng ph¸p duyÖt c©y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 8.3. C©y vµ bµi to¸n s¾p xÕp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 8.4. C©y khung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 8.5. C©y khung nhá nhÊt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 9. M¹ng. Luång trªn m¹ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 9.1. C¸c kh¸i niÖm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 9.2 ThuËt to¸n t×m luång cùc ®¹i trong m¹ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 Bµi tËp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 Ch-¬ng 4 163 §¹i sè Boole vµ m¹ch tæ hîp 1. Kh¸i niÖm vÒ m¹ch tæ hîp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 1.1 Kh¸i niÖm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 1.2 BiÓu thøc Boole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 2. C¸c tÝnh chÊt cña m¹ch tæ hîp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 2.1 C¸c tÝnh chÊt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 2.2 M¹ch tæ hîp t-¬ng ®-¬ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 3. Hµm Boole vµ vÊn ®Ò tæ hîp m¹ch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 3.1. §¹i sè Boole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 3.2. Hµm Boole vµ vÊn ®Ò tæng hîp m¹ch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 4. Mét vµi øng dông . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
4.1 Bé céng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 4.2 Cùc tiÓu ho¸ c¸c m¹ch. Ph-¬ng ph¸p Quine-McCluskey . . . . . . . . . . . . . . . . . . . . . . 176 Bµi tËp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 Ch-¬ng 5 185 Automat, v¨n ph¹m vµ ng«n ng÷ h×nh thøc 1. M¹ch tuÇn tù vµ m¸y h÷u h¹n tr¹ng th¸i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 1.1. M¹ch tuÇn tù . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 1.2. M¸y h÷u h¹n tr¹ng th¸i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 2. Automat h÷u h¹n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 2.1. Kh¸i niÖm vµ ®Þnh nghÜa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 2.2. BiÓu diÔn automat h÷u h¹n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 2.3. Ng«n ng÷ ®o¸n nhËn bëi automat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 2.4. Automat kh«ng tÊt ®Þnh (nondeterministic automat) . . . . . . . . . . . . . . . . . . . . . . . . . 191 2.5. Quan hÖ gi÷a automat tÊt ®Þnh vµ kh«ng tÊt ®Þnh . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 3. V¨n ph¹m vµ ng«n ng÷ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 3.1. C¸c kh¸i niÖm vµ ®Þnh nghÜa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 3.2. V¨n ph¹m vµ ng«n ng÷ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 3.3. Ph©n lo¹i v¨n ph¹m vµ ng«n ng÷ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 3.4. Mét sè tÝnh chÊt cña ng«n ng÷ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 3.5. TÝnh ®Ö qui ng«n ng÷. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 4. Automat h÷u h¹n vµ ng«n ng÷ chÝnh qui . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 4.1. Quan hÖ gi÷a automat h÷u h¹n vµ ng«n ng÷ chÝnh qui . . . . . . . . . . . . . . . . . . . . . . . . 207 4.2. Mét sè tÝnh chÊt cña ng«n ng÷ lo¹i 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 4.3. Mét sè tÝnh chÊt cña v¨n ph¹m phi ng÷ c¶nh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 4.4. C¸c d¹ng chuÈn cña v¨n ph¹m phi ng÷ c¶nh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 4.5. Lùc l-îng cña v¨n ph¹m phi ng÷ c¶nh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 5. M¸y Turing (Turing machine) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 5.1. Më ®Çu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 5.2. Kh¸i niÖm vµ ®Þnh nghÜa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 5.3. Hµm Turing thùc hiÖn ®-îc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 5.4. §é phøc t¹p cña thuËt to¸n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 Bµi tËp. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 Tµi liÖu tham kh¶o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
Ch-¬ng I. Nh÷ng kh¸i niÖm c¬ b¶n vÒ logic, tËp hîp vµ suy luËn to¸n häc Trong ch-¬ng nµy chóng ta nghiªn cøu mét sè vÊn ®Ò mang tÝnh chÊt c¬ së kh«ng chØ cña to¸n häc rêi r¹c nãi riªng, mµ cña c¶ to¸n häc nãi chung. §ã lµ nh÷ng kh¸i niÖm c¬ b¶n vÒ logic (kh¸i niÖm mÖnh ®Ò, c¸c phÐp to¸n trªn c¸c mÖnh ®Ò), tËp hîp (kh¸i niÖm vÒ tËp hîp vµ c¸c phÐp to¸n trªn tËp hîp) vµ suy luËn to¸n häc (c¸c lËp luËn to¸n häc c¬ së vµ c¸c phÐp chøng minh th-êng dïng trong to¸n häc). Kh¸i niÖm quan hÖ nh- lµ mét tËp con cña tËp tÝch Decac còng sÏ ®-îc ®Ò cËp ®Õn trong ch-¬ng. 1. MÖnh ®Ò, mÖnh ®Ò cã ®iÒu kiÖn vµ sù t-¬ng ®-¬ng logic 1.1 MÖnh ®Ò Logic to¸n lµ m«n häc nghiªn cøu c¸c quy luËt gi÷a nguyªn nh©n vµ hÖ qu¶, gi÷a gi¶ thiÕt vµ kÕt luËn, tõ ®ã rót ra ®-îc nh÷ng quy t¾c quan träng nhÊt ®Ó nhËn ®-îc nh÷ng nguyªn lý ®óng ®¾n ®-îc ¸p dông cho hÇu hÕt c¸c ngµnh khoa häc tù nhiªn còng nh- x· héi. Mét trong nh÷ng kh¸i niÖm quan träng nhÊt cña logic to¸n ®ã lµ logic mÖnh ®Ò, logic to¸n ®-îc ®Æt nÒn mãng trªn ®¹i sè mÖnh ®Ò. Khi ta nãi “HuÕ lµ mét thµnh phè cña ViÖt Nam” th× chóng ta ®· ®-a mét kh¼ng ®Þnh mµ mäi ng-êi ®Òu thÊy ®óng. Nh-ng khi ta nãi 1  2 th× ng-êi ta l¹i thÊy ngay ta ®· nãi sai. §Þnh nghÜa 1.1.1. MÖnh ®Ò lµ mét kh¼ng ®Þnh mµ ta cã thÓ biÕt ®-îc nã ®óng hoÆc sai. Kh«ng cã mÖnh ®Ò võa ®óng võa sai. C¸c mÖnh ®Ò ®-îc ký hiÖu b»ng c¸c ch÷ Latinh in A, B, C... Khi mÖnh ®Ò ®óng th× ta nãi mÖnh ®Ò nhËn gi¸ trÞ ®óng vµ viÕt A : T hay A  T , nÕu mÖnh ®Ò B sai th× ta nãi B nhËn gi¸ trÞ sai vµ viÕt B : F hay B  F . VÝ dô 1.1.1. TÊt c¶ c¸c kh¼ng ®Þnh sau ®Òu lµ c¸c mÖnh ®Ò 1. Hµ Néi lµ Thñ ®« cña ViÖt Nam 2. 2>3 3. 1+3=4 C¸c mÖnh ®Ò 1, 3 lµ c¸c mÖnh ®Ò ®óng cßn mÖnh ®Ò 2 lµ mÖnh ®Ò sai. 1.2 C¸c phÐp to¸n trªn mÖnh ®Ò Tõ c¸c mÖnh ®Ò ban ®Çu A, B, C... ng-êi ta cã thÓ x©y dùng c¸c mÖnh ®Ò míi víi sù gióp ®ì cña c¸c phÐp to¸n logic tuyÓn, héi vµ phñ ®Þnh sau ®©y.
§Þnh nghÜa 1.2.1. Gi¶ sö A, B lµ c¸c mÖnh ®Ò. Héi cña A, B lµ mét mÖnh ®Ò ®-îc ký hiÖu lµ A  B vµ ®äc lµ “A vµ B”. MÖnh ®Ò A  B ®óng khi c¶ A vµ B ®Òu ®óng, vµ sai trong tÊt c¶ c¸c tr-êng hîp cßn l¹i. Cã thÓ biÓu diÔn héi cña A vµ B d-íi d¹ng b¶ng gi¸ trÞ ch©n lý sau A B A B T T T T F F F T F F F F §Þnh nghÜa 1.2.2. Gi¶ sö A, B lµ c¸c mÖnh ®Ò. TuyÓn cña A, B lµ mét mÖnh ®Ò ®-îc ký hiÖu lµ A  B vµ ®äc lµ “A hoÆc B”. MÖnh ®Ò A  B sai chØ khi c¶ A vµ B ®Òu sai, vµ ®óng trong c¸c tr-êng hîp cßn l¹i. A B Ta cã b¶ng gi¸ trÞ ch©n lý cña mÖnh ®Ò sau A B A B T T T T F T F T T F F F VÝ dô 1.2.1. NÕu ký hiÖu A, B, C t-¬ng øng lµ c¸c mÖnh ®Ò 1, 2, 3 trong vÝ dô 1.1.1 A  B lµ mÖnh ®Ò sai v× B sai A  B lµ mÖnh ®Ò ®óng v× A ®óng C  A, C  A ®Òu lµ c¸c mÖnh ®Ò ®óng. §Þnh nghÜa 1.2.3. Gi¶ sö A lµ mét mÖnh ®Ò, phñ ®Þnh cña A, ký hiÖu A , lµ mét mÖnh ®Ò nhËn gi¸ trÞ ®óng khi A sai vµ nhËn gi¸ trÞ sai khi A ®óng.
1.3 MÖnh ®Ò cã ®iÒu kiÖn vµ sù t-¬ng ®-¬ng logic §Þnh nghÜa 1.3.1. Gi¶ sö A, B lµ c¸c mÖnh ®Ò. MÖnh ®Ò cã ®iÒu kiÖn (cßn gäi lµ phÐp suy diÔn hay phÐp kÐo theo) A  B lµ mét mÖnh ®Ò sai chØ khi A ®óng vµ B sai, vµ lµ mÖnh ®Ò ®óng trong mäi tr-êng hîp cßn l¹i. Trong mÖnh ®Ò A  B ng-êi ta gäi A lµ gi¶ thuyÕt (hay A lµ nguyªn nh©n) B lµ kÕt luËn (hay B lµ kÕt qu¶). Nh- vËy, theo ®Þnh nghÜa, phÐp suy diÔn A  B chØ bÞ coi lµ sai nÕu tõ gi¶ thuyÕt ®óng suy ra kÕt luËn sai. Ta cã b¶ng gi¸ trÞ ch©n lý A B A B T T T T F F F T T F F T MÖnh ®Ò cã ®iÒu kiÖn A  B cßn ®-îc ®äc lµ “nÕu A th× B” hay “B chØ nÕu A”. KÕt luËn B biÓu thÞ ®iÒu kiÖn cÇn cña A, cßn gi¶ thiÕt A biÓu thÞ ®iÒu kiÖn ®ñ cña B. VÝ dô 1.3.1. Ký hiÖu A lµ mÖnh ®Ò “H«m nay lµ thø t-” B lµ mÖnh ®Ò “Tam gi¸c vu«ng lµ tam gi¸c cã mét gãc b»ng 90o” C lµ mÖnh ®Ò “1  1  3 ” Khi ®ã, theo ®Þnh nghÜa, A  B lµ mÖnh ®Ò ®óng: “NÕu h«m nay lµ thø t-, th× tam gi¸c vu«ng lµ tam gi¸c cã mét gãc b»ng 90o“ lµ mÖnh ®Ò ®óng cho dï h«m nay cã lµ thø t- hay kh«ng. Cßn mÖnh ®Ò A  C : “H«m nay lµ thø t- th× 1  1  3 ” lµ mÖnh ®Ò nhËn gi¸ trÞ ®óng chØ khi h«m nay kh«ng ph¶i lµ thø t-. §Þnh nghÜa 1.3.2. Gi¶ sö A, B lµ c¸c mÖnh ®Ò. Khi ®ã mÖnh ®Ò A t-¬ng ®-¬ng víi B, ký hiÖu lµ A  B , lµ mét mÖnh ®Ò nhËn gi¸ trÞ ®óng khi vµ chØ khi A vµ B cã gi¸ trÞ ch©n lý gièng nhau. Ta cã b¶ng gi¸ trÞ ch©n lý sau cña mÖnh ®Ò A  B . A B A B T T T T F F F T F F F T Ng-êi ta cßn sö dông c¸c c¸ch gäi kh¸c nhau cña mÖnh ®Ò A  B nh- “cã A khi vµ chØ khi B”, “A lµ cÇn vµ ®ñ ®èi víi B” hay “nÕu A th× B vµ ng-îc l¹i”.
VÝ dô 1.3.2. NÕu gäi A lµ mÖnh ®Ò “H«m nay trêi n¾ng” B lµ mÖnh ®Ò “NhiÖt ®é ngoµi trêi cao h¬n 300C” th× A  B sÏ nhËn gi¸ trÞ ®óng nÕu kh¼ng ®Þnh sau lµ ®óng: Trêi n¾ng th× nhiÖt ®é ngoµi trêi cao h¬n 300C vµ nhiÖt ®é ngoµi trêi cao h¬n 300C th× trêi n¾ng. ë ViÖt Nam ®iÒu nµy râ rµng kh«ng ®óng, v× vµo mïa hÌ ë n-íc ta nhiÖt ®é cã thÓ cao h¬n 300C mµ trêi vÉn kh«ng n¾ng. §Þnh nghÜa 1.3.3. Tõ c¸c mÖnh ®Ò ban ®Çu ng-êi ta x©y dùng nªn c¸c mÖnh ®Ò míi víi sù gióp ®ì cña c¸c phÐp to¸n logic: héi, tuyÓn, phñ ®Þnh, suy diÔn vµ t-¬ng ®-¬ng. C¸c mÖnh ®Ò ban ®Çu ®-îc gäi lµ c¸c mÖnh ®Ò s¬ cÊp, c¸c mÖnh ®Ò míi nhËn ®-îc gäi lµ c¸c c«ng thøc. C«ng thøc cã gi¸ trÞ ®óng víi mäi gi¸ trÞ kh¸c nhau cña c¸c mÖnh ®Ò s¬ cÊp ®-îc gäi lµ c«ng thøc h»ng ®óng hay ®Þnh lý (®«i khi cßn gäi lµ luËt). VÝ dô 1.3.3. XÐt c«ng thøc A  B  A  B Ta thµnh lËp b¶ng gi¸ trÞ ch©n lý cña mÖnh ®Ò nµy A B A B A B A B  A B A T T F T T T T F F F F T F F T T T T F F T T T T Nh×n trong b¶ng nµy ta thÊy mÖnh ®Ò trªn lu«n nhËn gi¸ trÞ ®óng víi mäi gi¸ trÞ kh¸c nhau cña c¸c mÖnh ®Ò s¬ cÊp A, B cho nªn nã chÝnh lµ mét ®Þnh lý. Ghi chó 1.3.1. §Ó ®¬n gi¶n h¬n trong c¸ch viÕt c¸c c«ng thøc ng-êi ta quy -íc trËt tù c¸c phÐp to¸n nh- sau: c¸c phÐp to¸n trong ngoÆc thùc hiÖn tr-íc, c«ng thøc nµo cã phñ ®Þnh ph¶i thùc hiÖn nã tr-íc sau ®ã theo thø tù -u tiªn nÕu kh«ng cã dÊu ngoÆc th× phÐp héi thùc hiÖn tr-íc phÐp tuyÓn thùc hiÖn sau, cuèi cïng míi ®Õn c¸c phÐp to¸n suy diÔn vµ t-¬ng ®-¬ng. VÝ dô c«ng  A  B   C  A  víi c«ng thøc A  B  C  A chØ lµ mét. thøc Sau ®©y chóng ta dÉn ra mét sè tÝnh chÊt quan träng nhÊt cña logic mÖnh ®Ò. C¸c tÝnh chÊt ®ã ®Òu cã thÓ chøng minh ®-îc b»ng ph-¬ng ph¸p lËp b¶ng gi¸ trÞ ch©n lý t-¬ng tù nh- ®· xÐt trong vÝ dô 1.3.3. §Þnh lý 1.3.1. Cho A, B, C lµ c¸c mÖnh ®Ò bÊt kú. Khi ®ã ta cã: a) LuËt giao ho¸n A  B  B  A ; A  B  B  A  A  B  C  A   B  C  ;  A  B  C  A   B  C  b) LuËt kÕt hîp A   B  C   A  B  A  C ; A   B  C    A  B   A  C  c) LuËt ph©n phèi
A A  A; A A  A d) LuËt luü ®¼ng A   A  B  A ; A   A  B  A e) LuËt hÊp thô f) C¸c luËt De Morgan A  B  A  B ; A  B  A  B  g) LuËt hai lÇn phñ ®Þnh A  A h) LuËt chøng minh ph¶n chøng thø nhÊt A  B  B  A i) LuËt chøng minh ph¶n chøng thø hai A  B  A  B 2. TËp hîp vµ c¸c phÐp to¸n trªn tËp hîp 2.1 TËp hîp, tËp con vµ tÝch Decac TËp hîp lµ mét kh¸i niÖm to¸n häc kh«ng ®Þnh nghÜa ®-îc. Ng-êi ta chØ cã thÓ m« t¶ tËp hîp th«ng qua c¸c phÇn tö cña nã. TËp hîp th-êng ®-îc ký hiÖu b»ng c¸c ch÷ Latin hoa nh- A, B, C... , cßn c¸c phÇn tö cña tËp hîp ®-îc ký hiÖu b»ng c¸c ch÷ Latin th-êng a, b, c,... a  A . Nh- vËy gi÷a phÇn tö vµ tËp hîp cã quan hÖ Khi a lµ phÇn tö cña tËp A th× chóng ta viÕt phô thuéc. NÕu a kh«ng ph¶i lµ phÇn tö cña tËp A th× ta viÕt a  A hay a  A . ... , vÝ §Ó ký hiÖu tËp A gåm cã c¸c phÇn tö nµo th× ta viÕt c¸c phÇn tö Êy gi÷a 2 ngoÆc nhän A  a, b a  A , b  A . Còng dÔ dµng thÊy lµ mét tËp hîp cã hai phÇn tö a vµ b; ta viÕt dô 0  A : 0 kh«ng ph¶i lµ phÇn tö thuéc tËp A. trong vÝ dô nµy TËp hîp cã thÓ cã h÷u h¹n phÇn tö, vÝ dô A  1,2,..., n , nh-ng còng cã thÓ cã v« h¹n phÇn tö, vÝ dô B  1, 2,...   x x lµ sè tù nhiª n . Sè c¸c phÇn tö cña mét tËp h÷u h¹n A ký hiÖu lµ A . Nh- vËy  ,2,3  3 . 1 . TËp kh«ng cã phÇn tö ®-îc gäi lµ tËp rçng. TËp rçng ®-îc ký hiÖu lµ §Þnh nghÜa 2.1.1. Hai tËp hîp A vµ B gäi lµ b»ng nhau nÕu chóng cã cïng c¸c phÇn tö. VÝ dô 2.1.1. XÐt tËp A  1,2 cßn B lµ tËp c¸c nghiÖm cña ph-¬ng tr×nh bËc hai x 2  3 x  2  0 . Râ rµng lµ A = B v× ph-¬ng tr×nh x 2  3 x  2  0 cã hai nghiÖm x1  1, x2  2 . §Þnh nghÜa 2.1.2. NÕu mäi phÇn tö cña tËp A ®Òu lµ phÇn tö cña tËp B th× ta nãi tËp A lµ tËp con cña B vµ viÕt A  B . Râ rµng lµ víi mäi A ta ®Òu cã A  A;   A . Theo ®Þnh nghÜa 2.1.1, hai tËp A  B khi vµ chØ khi A  B vµ B  A .
VÝ dô 2.1.2. TËp A  1, 2 , B  1, 2,3, a . ë ®©y A cã 2 phÇn tö 1 vµ 2 th× c¶ hai phÇn tö nµy ®Òu cã trong B cho nªn A lµ tËp con cña B. p ( A) lµ tËp tÊt c¶ c¸c tËp con cña A. Ký hiÖu VÝ dô 2.1.3. NÕu A  1,2,3 th× p ( A) sÏ gåm c¸c phÇn tö lµ c¸c tËp con cña A sau: ,a ,b ,c ,a, b ,b, c ,a, c ,a, b, c cho nªn p  A  8 . p  A  2 . §iÒu nµy chóng ta sÏ chøng minh ë phÇn sau b»ng ph-¬ng ph¸p NÕu A  n th× n quy n¹p to¸n häc. V× lý do p  A   2 khi A  n nªn ng-êi ta cßn ký hiÖu p  A  lµ 2 vµ A n gäi tËp tÊt c¶ c¸c tËp con cña A lµ tËp luü thõa cña A. §Þnh nghÜa 2.1.3. Gi¶ sö A,B lµ hai tËp hîp. Ta x©y dùng tËp míi ký hiÖu lµ A  B , trong ®ã A  B   a , b  a  A, b  B sao cho  a, b    c , d  khi vµ chØ khi a  c, b  d . TËp hîp A  B ®-îc x¸c ®Þnh theo ®Þnh nghÜa 2.1.3 gäi lµ tÝch Decac cña A, B. Cßn bé hai  a, b  trong ®Þnh nghÜa lµ bé hai cã thø tù: phÇn tö thø nhÊt (to¹ ®é thø nhÊt) a  A ; phÇn tö thø hai (to¹ ®é thø hai) b  B . A  1, 2,3 , B  a, b A B VÝ dô 2.1.4. th× gåm cã 6 phÇn tö 1, a  , 1, b  ,  2, a  ,  2, b  ,  3, a  ,  3, b  . A A gåm cã 9 phÇn tö lµ 1,1 , 1,2  , 1,3  ,  2,1 ,  2,2  ,  2,3 ,  3,1 ,  3,2  ,  3,3 . DÔ dµng nhËn thÊy r»ng nÕu A, B lµ c¸c tËp h÷u h¹n th× A  B  A B . §Þnh nghÜa 2.1.4. (TÝch Decac n - ng«i) Gi¶ sö A1 , A2 ,..., An lµ n tËp hîp nµo ®ã. TÝch Decac (n - ng«i) cña ®-îc ký hiÖu lµ A1  A2  ...  An , víi A1 , A2 ,..., An A1  A2  ...  An   a1 , a2 ,..., an  a1  A1 , a2  A2 ,..., an  An  ,  a1 , a2 ,..., an    a1, a2 ,..., an   khi vµ chØ khi ai  ai víi mäi i  1, 2,..., n . Ai Còng nh- trªn, cã thÓ dÔ dµng thÊy r»ng, nÕu c¸c tËp h÷u h¹n th× A1  A2  ...  An  A1 A2 ... An . 2.2 C¸c phÐp to¸n trªn tËp hîp Tõ mét sè tËp hîp ban ®Çu ng-êi ta x©y dùng c¸c tËp míi víi sù gióp ®ì cña c¸c phÐp to¸n trªn tËp hîp. C¸c quy t¾c x©y dùng nªn c¸c tËp míi vµ thùc hiÖn c¸c phÐp to¸n trªn tËp hîp th-êng ®-îc gäi lµ ®¹i sè tËp hîp.
§Þnh nghÜa 2.2.1. Gi¶ sö A, B lµ hai tËp hîp. A hîp B, ký hiÖu A  B , lµ mét tËp hîp chøa tÊt c¶ c¸c phÇn tö cña A, tÊt c¶ c¸c phÇn tö cña B. Nh- vËy   A  B  x  x  A    x  B  hay x  A  B   x  A    x  B  VÝ dô 2.2.1. NÕu A  a, b, c, d  lµ tËp c¸c häc sinh trong mét tæ tËp bãng chuyÒn cßn B  a, c, e, f  lµ tËp c¸c häc sinh cña tæ ®ã tËp b¬i th× tËp c¸c häc sinh cña tæ tham gia tËp thÓ thao (bãng chuyÒn hoÆc b¬i) sÏ lµ A  B  a , b, c, d , e, f  . Ng-êi ta th-êng minh ho¹ c¸c phÐp to¸n trªn tËp hîp b»ng gi¶n ®å Venn: C¸c tËp A,B,... ®Òu lµ tËp con cña mét tËp U gäi lµ tËp vò trô U. TËp vò trô ®-îc biÓu diÔn lµ mét h×nh ch÷ nhËt, c¸c tËp A,B,... lµ c¸c h×nh trßn trong U. Gi¶n ®å Venn cña tËp A  B cã d¹ng sau A B §Þnh nghÜa 2.2.2. Gi¶ sö A, B lµ hai tËp hîp. Giao cña A, B, ký hiÖu A  B , lµ tËp gåm c¸c phÇn tö võa lµ cña A, võa lµ cña B. Nh- vËy   A  B  x  x  A    x  B  hay x  A  B   x  A    x  B  A  B  a , c VÝ dô 2.2.2. Còng lÊy vÝ dô A,B tõ vÝ dô 2.2.1 ta cã lµ tËp c¸c häc sinh trong tæ tËp c¶ hai m«n bãng chuyÒn vµ b¬i. A  B nh- sau: Ta cã gi¶n ®å Venn cña tËp AB
§Þnh nghÜa 2.2.3. Gi¶ sö A, B lµ hai tËp hîp. HiÖu cña A vµ B, ký hiÖu lµ mét tËp hîp A\ B gåm c¸c phÇn tö cña A nh-ng kh«ng ph¶i cña B. Nh- vËy   A \ B  x x  A  x  B hay x  A \ B   x  A   x  B Ta cã gi¶n ®å Venn cña lµ: A\ B A  B . §Æc biÖt trong tr-êng hîp A  U , víi U lµ A\ B Khi B  A th× A \ B th-êng ®-îc viÕt U  A ®-îc gäi lµ phÇn bï cña A (®èi víi U) , ký hiÖu lµ A . Nh- vËy tËp vò trô, ta cã ®Þnh nghÜa sau: §Þnh nghÜa 2.2.4. x A  x A Ta cã gi¶n ®å Venn cña A A VÝ dô 2.2.3. LÊy c¸c tËp A, B tõ vÝ dô 2.2.1 th× A \ B  b, d  B \ A  e, f  . cßn
Sau ®©y chóng ta nªu ra mét sè tÝnh chÊt cña c¸c phÐp to¸n trªn tËp hîp mµ chøng minh chóng ®-îc ®-a vÒ c¸c luËt t-¬ng øng cña logic mÖnh ®Ò. §Þnh lý 2.2.1. Gi¶ sö U lµ tËp vò trô, A, B, C lµ c¸c tËp con cña U.  A  B  C  A   B  C  ; a) LuËt kÕt hîp  A  B  C  A  B  C  A B  B  A; A B  B  A b) LuËt giao ho¸n A B C  A B  AC ; c) LuËt ph©n phèi A   B  C    A  B   A  C  A   A; A  U  A A U  U; A   d) LuËt ®ång nhÊt A AU; A A  e) LuËt nuèt f) LuËt lµm ®Çy A A  A; A A  A g) LuËt luü ®¼ng A   A  B  A ; A   A  B  A h) LuËt hÊp thô  A  A i) LuËt bï  U; U  j) LuËt 0, 1 A B  A B; A B  A B k) LuËt De Morgan Chøng minh. Nh- ta ®· nãi ë trªn tÊt c¶ c¸c luËt trong ®Þnh lý 2.2.1 ®Òu ®-îc chøng minh b»ng ph-¬ng ph¸p ®-a vÒ c¸c luËt t-¬ng øng cña logic mÖnh ®Ò. VÝ dô ta chøng minh luËt hÊp thô A   A  B  A nh- sau. Theo ®Þnh nghÜa 2.2.1, 2.2.2 th×
x  A   A  B    x  A   x   A  B     x  A    x  A   x  B   x A. Theo luËt hÊp thô thø hai trong logic mÖnh ®Ò, ®iÒu sau cïng t-¬ng ®-¬ng víi x  A   A  B    x  A  , theo ®Þnh nghÜa 2.1.1 ®iÒu Nh- vËy ta ®· chøng minh ®-îc A   A  B  A . nµy cã nghÜa lµ Cã thÓ ®Þnh nghÜa t-¬ng tù cho hîp vµ giao cña mét hä bÊt kú c¸c tËp hîp. 3. L-îng tö vµ vÞ tõ 3.1 Hµm mÖnh ®Ò C¸c mÖnh ®Ò ®-îc xÐt trong phÇn ®Çu cña ch-¬ng lµ nh÷ng mÖnh ®Ò mµ chóng ta cã thÓ x¸c ®Þnh ngay gi¸ trÞ cña chóng ®óng hoÆc sai. Trong môc nµy chóng ta sÏ xem xÐt mét lo¹i mÖnh ®Ò kh¸c, mÖnh ®Ò mµ gi¸ trÞ cña nã phô thuéc vµo c¸c gi¸ trÞ kh¸c nhau lÊy tõ mét tËp nµo ®ã. VÝ dô kh¼ng ®Þnh “x lµ mét sè nguyªn lín h¬n 5” lµ mét lo¹i kh¼ng ®Þnh mµ khi thay x b»ng mét gi¸ trÞ nguyªn cô thÓ nµo ®ã ta sÏ ®-îc mét mÖnh ®Ò, ch¼ng h¹n víi x  2 ta cã mÖnh ®Ò “2 lín h¬n 5” viÕt b»ng ký hiÖu to¸n häc lµ “ 2  5 ”, ®©y lµ mÖnh ®Ò sai, cßn víi x b»ng 6 ta sÏ ®-îc mÖnh ®Ò “ 6  5 ” lµ mÖnh ®Ò ®óng. Lo¹i mÖnh ®Ò phô thuéc vµo c¸c tham sè lÊy gi¸ trÞ tõ mét tËp nµo ®ã ®-îc gäi lµ hµm mÖnh ®Ò. Nãi mét c¸ch chÝnh x¸c ta cã ®Þnh nghÜa sau: §Þnh nghÜa 3.1.1. Hµm P  x1 , x2 ,..., xn  x¸c ®Þnh trªn tËp A ®-îc gäi lµ hµm mÖnh ®Ò n - ng«i nÕu khi thay x1  a1 , x2  a2 ,..., xn  an víi a1 , a2 ,..., an  A , ta nhËn ®-îc mét mÖnh ®Ò. Khi n  1 , hµm 1- ng«i P  x  th-êng gäi ®¬n gi¶n lµ hµm mÖnh ®Ò. VÝ dô 3.1.1. x  y lµ mét hµm mÖnh ®Ò 2- ng«i x¸c ®Þnh trªn tËp sè nguyªn Z . ThËt vËy, khi ta g¸n x  m , y  n lµ c¸c sè nguyªn cô thÓ nµo ®ã ta sÏ ®-îc mÖnh ®Ò m  n . 3.2 VÞ tõ XÐt kh¼ng ®Þnh “víi mäi sè tù nhiªn n ta ®Òu cã n  5 ”. §©y lµ mét kh¼ng ®Þnh sai v× ta dÔ dµng t×m thÊy mét sè tù nhiªn, ch¼ng h¹n 1  5 . Tuy nhiªn, dÔ dµng thÊy r»ng, kh¼ng ®Þnh “tån t¹i sè tù nhiªn n sao cho n  5 ” l¹i lµ mét mÖnh ®Ò ®óng. C¸c mÖnh ®Ò nh- nªu ë ®©y ®-îc x©y dùng tõ hµm mÖnh ®Ò  n  5  x¸c ®Þnh trªn tËp sè tù nhiªn víi sù gióp ®ì cña c¸c to¸n tö ®-îc gäi lµ to¸n tö chung (l-îng tö chung) n , ®äc lµ víi mäi n vµ to¸n tö riªng (l-îng tö riªng) n ®äc lµ tån t¹i n.
§Þnh nghÜa 3.2.1. Gi¶ sö P  x  lµ mét hµm mÖnh ®Ò x¸c ®Þnh trªn tËp A. x P  x  (®äc lµ víi mäi x P  x  ) lµ mét mÖnh ®Ò, nã nhËn gi¸ trÞ ®óng khi vµ chØ khi víi phÇn tö bÊt kú a  A ta cã P a  T . x P  x  (®äc lµ tån t¹i x P  x  ) lµ mét mÖnh ®Ò, nã nhËn gi¸ trÞ ®óng khi vµ chØ khi tån t¹i a  A ®Ó P  a   T . C¸c to¸n tö x , x gäi lµ c¸c l-îng tö. x ®-îc gäi lµ l-îng tö chung, x ®-îc gäi lµ l-îng tö riªng. MÖnh ®Ò cã chøa c¸c l-îng tö ®-îc gäi lµ vÞ tõ. Hoµn toµn t-¬ng tù nh- trong ®Þnh nghÜa 3.2.1 ta cã thÓ nhËn ®-îc c¸c vÞ tõ x©y dùng tõ c¸c hµm mÖnh ®Ò n - ng«i ( n  1 ). Ch¼ng h¹n xyP  x, y  hay xyP  x, y  ... Khi hµm mÖnh ®Ò P  x1 , x2 ,..., xn  x¸c ®Þnh trªn tËp A th× ta nãi vÞ tõ t-¬ng øng x¸c ®Þnh trªn tËp A. VÝ dô 3.2.2. xy  x  y  lµ mét vÞ tõ (mÖnh ®Ò) x¸c ®Þnh trªn tËp sè nguyªn. MÖnh ®Ò nµy kh¼ng ®Þnh víi mäi sè nguyªn x  m tån t¹i sè nguyªn y  n ®Ó m  n . Râ rµng ®©y lµ mét mÖnh ®Ò ®óng. 3.3 Phñ ®Þnh cña vÞ tõ Ta xÐt phñ ®Þnh cña vÞ tõ x  x  5  trªn tËp sè nguyªn Z , tøc lµ x  x  5  . §©y lµ mét mÖnh ®Ò nhËn gi¸ trÞ ®óng khi vµ chØ khi x  x  5  sai. Theo ®Þnh nghÜa 3.2.1 th× ®iÒu nµy cã nghÜa lµ x  x  5  hay x  x  5  vËy lµ x  x  5   x x  5   x  x  5  (DÔ dµng thÊy mÖnh ®Ò víi mäi x nguyªn x  5 lµ sai) cho nªn mÖnh ®Ò x  x  5  lµ mÖnh ®Ò sai. Ta cã ®Þnh lý sau: §Þnh lý 3.3.1. NÕu P  x  lµ hµm mÖnh ®Ò x¸c ®Þnh trªn tËp A th× c¸c kh¼ng ®Þnh sau lµ h»ng ®óng: a) xP  x   xP  x  b) xP  x   xP  x  Chøng minh. Ta chøng minh kh¼ng ®Þnh a). MÖnh ®Ò xP  x  nhËn gi¸ trÞ ®óng khi vµ chØ khi xP  x  nhËn gi¸ trÞ sai. Theo ®Þnh nghÜa 3.2.1 ®iÒu nµy cã nghÜa lµ tån t¹i x  a thuéc A ®Ó P  a  sai hay P  a  ®óng, tøc lµ xP  x  ®óng. Do vËy xP  x   xP  x  lµ mét mÖnh ®Ò h»ng ®óng hay lµ mét ®Þnh lý. ViÖc chøng minh kh¼ng ®Þnh b) lµ hoµn toµn t-¬ng tù. VÝ dô 3.3.1. VÞ tõ cña ®Þnh nghÜa d·y sè  an  cã giíi h¹n a lµ
  0 K n  n  K : an  a    .   x¸c ®Þnh trªn tËp sè tù nhiªn n  K , K  N . Theo chó Hµm mÖnh ®Ò n  K : an  a   thÝch 3.3.2 th× vÞ tõ cña ®Þnh nghÜa d·y  an  kh«ng cã giíi h¹n a sÏ lµ:  0 K n  n  K : an  a   0  Tõ ®Þnh lý 1.3.1 ta cã hÖ qu¶ sau: HÖ qu¶ 3.3.1. C¸c c«ng thøc sau lµ c¸c ®Þnh lý   a) x  P  x   Q  x    x P  x   Q  x    b) x  P  x   Q  x    x P  x   Q  x  Chó thÝch 3.3.1. C¸c l-îng tö cïng lo¹i trong vÞ tõ cña hµm mÖnh ®Ò n - ng«i ( n  1 ) cã tÝnh giao ho¸n cßn c¸c l-îng tõ kh¸c lo¹i kh«ng giao ho¸n ®-îc cho nhau. Cã thÓ thÊy ®iÒu ®ã qua vÝ dô sau: VÝ dô 3.3.2. Gi¶ sö P  x , y  lµ hµm mÖnh ®Ò x¸c ®Þnh trªn tËp sè nguyªn Z . VÞ tõ xy  x  y  lµ mét mÖnh ®Ò ®óng (vÝ dô 3.2.2), nh-ng mÖnh ®Ò yx  x  y  lµ mÖnh ®Ò sai v× nã kh¼ng ®Þnh tån t¹i mét sè nguyªn y  m0 ®Ó m0 nhá h¬n hoÆc b»ng tÊt c¶ c¸c sè nguyªn x  n kh¸c, tøc lµ m0 lµ sè nguyªn nhá nhÊt. §iÒu nµy lµ v« lý v× tËp sè nguyªn kh«ng cã sè nguyªn nhá nhÊt. Chó thÝch 3.3..2. Cã thÓ tæng qu¸t ho¸ ®Þnh lý 3.3.1 cho hµm mÖnh ®Ò P  x1 , x2 ,..., xn  n - ng«i víi n  1 : Phñ ®Þnh cña vÞ tõ nhËn ®-îc b»ng c¸ch thay l-îng tö thµnh l-îng tö kh¸c lo¹i vµ hµm mÖnh ®Ò P  x1 , x2 ,..., xn  thµnh phñ ®Þnh cña nã P  x1 , x2 ,..., xn  . 4. Quan hÖ 4.1 Kh¸i niÖm vµ tÝnh chÊt Quan hÖ gi÷a hai tËp theo ng«n nghÜa trùc gi¸c ®-îc hiÓu hiÓu lµ mèi quan hÖ gi÷a mét sè phÇn tö cña tËp nµy víi mét sè phÇn tö cña tËp kh¸c. Ch¼ng h¹n, nÕu lÊy A tËp c¸c sinh viªn nµo ®ã vµ B lµ tËp c¸c m«n häc mµ hä ®ang theo häcth× ta cã thÓ nãi sinh viªn a cã quan hÖ víi m«n häc a nÕu sinh viªn a theo häc m«n a. Hoµn toµn t-¬ng tù nh- vËy nÕu lÊy A lµ tËp mét sè ng-êi nµo
®ã vµ quan hÖ mµ ta quan t©m lµ quan hÖ hä hµng ch¼ng h¹n th× ta nãi anh a vµ c« b thuéc quan hÖ nµy nÕu a vµ b cã hä víi nhau. §Þnh nghÜa 4.1.1. Gi¶ sö X, Y lµ hai tËp hîp. Quan hÖ hai ng«i R tõ X ®Õn Y ®-îc ®Þnh nghÜa lµ tËp con cña tÝch Decac X  Y , tøc lµ R  X  Y . Trong tr-êng hîp X  Y th× ng-êi ta nãi R  X  X lµ quan hÖ hai ng«i trong X. x  X y  Y  x, y   R ®-îc gäi lµ tËp x¸c ®Þnh cña quan hÖ R. Cßn tËp TËp  y  Y x  X  x, y   R ®-îc gäi lµ tËp gi¸ trÞ cña quan hÖ R.  x, y   R ng-êi ta th-êng hay viÕt b¾t ch-íc theo quan hÖ  trong tËp sè §Ó x¸c ®Þnh xRy thùc:  ,    khi vµ chØ khi    . NÕu quan hÖ hai ng«i biÓu diÔn d-íi d¹ng mét b¶ng gåm 2 cét th× cét thø nhÊt gåm c¸c phÇn tö cña miÒn x¸c ®Þnh, cét thø hai - miÒn gi¸ trÞ. VÝ dô 4.1.1. Gi¶ sö X  2,3, 4,5 , Y  1,3, 4,5, 6, 7,9 . Ta x¸c ®Þnh quan hÖ hai ng«i  x, y   R  x y : x lµ -íc sè cña y (hay y chia hÕt cho x). DÔ dµng thÊy khi ®ã R  2,4, 2,6, 3,3, 3,6 , 3,9, 4,4, 5,5. Hay biÓu diÔn d-íi d¹ng b¶ng ta cã A B 2 4 2 6 3 3 3 6 3 9 4 4 5 5 Trong ®ã c¸c phÇn tö trªn cïng mét hµng n»m trong quan hÖ R. Nh×n vµo b¶ng nµy c¸c phÇn tö n»m trªn cét thø nhÊt 2,3,4,5lµ tËp x¸c ®Þnh cña quan hÖ R cßn c¸c phÇn tö trªn cét thø hai 3,4,6,5,9 lµ tËp gi¸ trÞ cña R.