ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 06.05.2024
Просмотров: 165
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
585
ОГЛАВЛЕНИЕ
Ïðåäèñëîâèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
× À Ñ Ò Ü Ï Å Ð Â À ß
ÒÅÎÐÈß ÌÍÎÆÅÑÒÂ
Ââåäåíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1. Àëãåáðà ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.1. Ìíîæåñòâà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2. Ïîäìíîæåñòâà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.3. Äèàãðàììû Âåííà. Óíèâåðñàëüíîå ìíîæåñòâî . . . . . . . . . . . . . . 17 1.4. Îáúåäèíåíèå ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.5. Ïåðåñå÷åíèå ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.6. Äîïîëíåíèå ìíîæåñòâà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.7. Çàêîíû äå Ìîðãàíà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.8. Ðàçíîñòü ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.9. Ñèììåòðè÷åñêàÿ ðàçíîñòü ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . 29 1.10. Çàêîí ïîãëîùåíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.11. Çàêîí ñêëåèâàíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.12. Òåîðåòèêî-ìíîæåñòâåííûå ïðåîáðàçîâàíèÿ . . . . . . . . . . . . . . . . . 35
2. Áèíàðíûå îòíîøåíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.1. Äåêàðòîâî ïðîèçâåäåíèå ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . 37 2.2. Ñòåïåíü ìíîæåñòâà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.3. Ïîíÿòèå áèíàðíîãî îòíîøåíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.4. Ñèììåòðèÿ îòíîøåíèé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.5. Òðàíçèòèâíîñòü îòíîøåíèé . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.6. Ðåôëåêñèâíîñòü îòíîøåíèé . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.7. Îòíîøåíèÿ ýêâèâàëåíòíîñòè . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.8. Îòíîøåíèÿ ñòðîãîãî ïîðÿäêà . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.9. Îòíîøåíèÿ íåñòðîãîãî ïîðÿäêà . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.10. Óïîðÿäî÷åííûå ìíîæåñòâà . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.11. Îòíîøåíèÿ ñîîòâåòñòâèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.12. Ôóíêöèîíàëüíûå îòíîøåíèÿ. Îòîáðàæåíèÿ . . . . . . . . . . . . . . . . 52 2.13. Ðåëÿöèîííàÿ àëãåáðà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3. Áåñêîíå÷íûå ìíîæåñòâà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.1. Ââîäíûå çàìå÷àíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.2. Ñðàâíåíèå áåñêîíå÷íûõ ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . . 59
ОГЛАВЛЕНИЕ
Ïðåäèñëîâèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
× À Ñ Ò Ü Ï Å Ð Â À ß
ÒÅÎÐÈß ÌÍÎÆÅÑÒÂ
Ââåäåíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1. Àëãåáðà ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.1. Ìíîæåñòâà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2. Ïîäìíîæåñòâà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.3. Äèàãðàììû Âåííà. Óíèâåðñàëüíîå ìíîæåñòâî . . . . . . . . . . . . . . 17 1.4. Îáúåäèíåíèå ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.5. Ïåðåñå÷åíèå ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.6. Äîïîëíåíèå ìíîæåñòâà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.7. Çàêîíû äå Ìîðãàíà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.8. Ðàçíîñòü ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.9. Ñèììåòðè÷åñêàÿ ðàçíîñòü ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . 29 1.10. Çàêîí ïîãëîùåíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.11. Çàêîí ñêëåèâàíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.12. Òåîðåòèêî-ìíîæåñòâåííûå ïðåîáðàçîâàíèÿ . . . . . . . . . . . . . . . . . 35
2. Áèíàðíûå îòíîøåíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.1. Äåêàðòîâî ïðîèçâåäåíèå ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . 37 2.2. Ñòåïåíü ìíîæåñòâà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.3. Ïîíÿòèå áèíàðíîãî îòíîøåíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.4. Ñèììåòðèÿ îòíîøåíèé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.5. Òðàíçèòèâíîñòü îòíîøåíèé . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.6. Ðåôëåêñèâíîñòü îòíîøåíèé . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.7. Îòíîøåíèÿ ýêâèâàëåíòíîñòè . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.8. Îòíîøåíèÿ ñòðîãîãî ïîðÿäêà . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.9. Îòíîøåíèÿ íåñòðîãîãî ïîðÿäêà . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.10. Óïîðÿäî÷åííûå ìíîæåñòâà . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.11. Îòíîøåíèÿ ñîîòâåòñòâèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.12. Ôóíêöèîíàëüíûå îòíîøåíèÿ. Îòîáðàæåíèÿ . . . . . . . . . . . . . . . . 52 2.13. Ðåëÿöèîííàÿ àëãåáðà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3. Áåñêîíå÷íûå ìíîæåñòâà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.1. Ââîäíûå çàìå÷àíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.2. Ñðàâíåíèå áåñêîíå÷íûõ ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . . 59
ДИСКРЕТНАЯ МАТЕМАТИКА. Ñ÷åòíûå ìíîæåñòâà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.4. Íåñ÷åòíûå ìíîæåñòâà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.5. Ãèïîòåçà êîíòèíóóìà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.6. Òðàíñöåíäåíòíûå ÷èñëà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.7. Îá ýêâèâàëåíòíîñòè ìíîæåñòâ òî÷åê
ãåîìåòðè÷åñêèõ îáúåêòîâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.8. Òðàíñôèíèòíûå ÷èñëà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.9. Ïàðàäîêñû òåîðèè ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.10. Óïðàæíåíèÿ íà òåìó «Ïàðàäîêñû òåîðèè ìíîæåñòâ» . . . . . . . 76
4. Ýëåìåíòû òåîðèè íå÷åòêèõ ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.1. Ââîäíûå çàìå÷àíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.2. Íå÷åòêèå ìíîæåñòâà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4.3. Îáúåäèíåíèå íå÷åòêèõ ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . 88 4.4. Ïåðåñå÷åíèå íå÷åòêèõ ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . . 89 4.5. Äîïîëíåíèå íå÷åòêîãî ìíîæåñòâà . . . . . . . . . . . . . . . . . . . . . . 91 4.6. Ðàçíîñòü è ñèììåòðè÷åñêàÿ ðàçíîñòü íå÷åòêèõ ìíîæåñòâ . . . . 92 4.7. Îñíîâíûå ñâîéñòâà îïåðàöèé íàä íå÷åòêèìè ìíîæåñòâàìè . . . 93
× À Ñ Ò Ü Â Ò Î Ð À ß
ÁÓËÅÂÀ ÀËÃÅÁÐÀ
Ââåäåíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5. Ââîäíûå ïîíÿòèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 5.1. Äâîè÷íûå ÷èñëà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 5.2. Ïîíÿòèå âûñêàçûâàíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 5.3. Àêñèîìû áóëåâîé àëãåáðû . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 5.4. Ñâîéñòâà äèçúþíêöèè è êîíúþíêöèè . . . . . . . . . . . . . . . . . . . 103 5.5. Òåîðåìû îäíîé ïåðåìåííîé . . . . . . . . . . . . . . . . . . . . . . . . . . 105 5.6. Äèçúþíêòèâíûå è êîíúþíêòèâíûå ôîðìû . . . . . . . . . . . . . . . 106 5.7. Òåîðåìû ïîãëîùåíèÿ, ñêëåèâàíèÿ è äå Ìîðãàíà . . . . . . . . . . . 107 5.8. Èíâåðòèðîâàíèå ñëîæíûõ âûðàæåíèé . . . . . . . . . . . . . . . . . . . 109
6. Äèçúþíêòèâíûå ôîðìû áóëåâûõ ôóíêöèé . . . . . . . . . . . . . . . . . . . . . . . 111 6.1. Ïîíÿòèå áóëåâîé ôóíêöèè . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 6.2. Êàê çàäàòü áóëåâó ôóíêöèþ . . . . . . . . . . . . . . . . . . . . . . . . . 113 6.3. Ìèíòåðìû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 6.4. Ñîâåðøåííàÿ äèçúþíêòèâíàÿ íîðìàëüíàÿ ôîðìà . . . . . . . . . . . 117 6.5. Òåîðåìà ðàçëîæåíèÿ äëÿ ÄÍÔ . . . . . . . . . . . . . . . . . . . . . . . . 119 6.6. Êàðòà Âåé÷à . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 6.7. Íàíåñåíèå ôóíêöèé íà êàðòó Âåé÷à . . . . . . . . . . . . . . . . . . . . 122 6.8. Íàõîæäåíèå ÑÄÍÔ ïðè ïîìîùè êàðò Âåé÷à . . . . . . . . . . . . . 124 6.9. Àëãåáðàè÷åñêîå óïðîùåíèå áóëåâûõ ôîðìóë . . . . . . . . . . . . . . 127 6.10. Ïîíÿòèå èìïëèêàíòû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 6.11. Ìåòîä Êâàéíà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.12. Íàõîæäåíèå ïðîñòûõ èìïëèêàíò ïî êàðòå Âåé÷à . . . . . . . . . . 133 6.13. Ìåòîä Ïåòðèêà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 6.14. Ìèíèìèçàöèÿ áóëåâûõ ôîðìóë ïðè ïîìîùè êàðò Âåé÷à . . . . . 139
7. Êîíúþíêòèâíûå ôîðìû áóëåâûõ ôóíêöèé . . . . . . . . . . . . . . . . . . . . . . . 142 7.1. Îñíîâíîé ñïîñîá íàõîæäåíèÿ ÊÍÔ . . . . . . . . . . . . . . . . . . . . . 142 7.2. Ìàêñòåðìû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 7.3. Ñîâåðøåííàÿ êîíúþíêòèâíàÿ íîðìàëüíàÿ ôîðìà . . . . . . . . . . . 145 7.4. Òåîðåìà ðàçëîæåíèÿ äëÿ ÊÍÔ . . . . . . . . . . . . . . . . . . . . . . . . 146
ãåîìåòðè÷åñêèõ îáúåêòîâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.8. Òðàíñôèíèòíûå ÷èñëà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.9. Ïàðàäîêñû òåîðèè ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.10. Óïðàæíåíèÿ íà òåìó «Ïàðàäîêñû òåîðèè ìíîæåñòâ» . . . . . . . 76
4. Ýëåìåíòû òåîðèè íå÷åòêèõ ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.1. Ââîäíûå çàìå÷àíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.2. Íå÷åòêèå ìíîæåñòâà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4.3. Îáúåäèíåíèå íå÷åòêèõ ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . 88 4.4. Ïåðåñå÷åíèå íå÷åòêèõ ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . . 89 4.5. Äîïîëíåíèå íå÷åòêîãî ìíîæåñòâà . . . . . . . . . . . . . . . . . . . . . . 91 4.6. Ðàçíîñòü è ñèììåòðè÷åñêàÿ ðàçíîñòü íå÷åòêèõ ìíîæåñòâ . . . . 92 4.7. Îñíîâíûå ñâîéñòâà îïåðàöèé íàä íå÷åòêèìè ìíîæåñòâàìè . . . 93
× À Ñ Ò Ü Â Ò Î Ð À ß
ÁÓËÅÂÀ ÀËÃÅÁÐÀ
Ââåäåíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5. Ââîäíûå ïîíÿòèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 5.1. Äâîè÷íûå ÷èñëà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 5.2. Ïîíÿòèå âûñêàçûâàíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 5.3. Àêñèîìû áóëåâîé àëãåáðû . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 5.4. Ñâîéñòâà äèçúþíêöèè è êîíúþíêöèè . . . . . . . . . . . . . . . . . . . 103 5.5. Òåîðåìû îäíîé ïåðåìåííîé . . . . . . . . . . . . . . . . . . . . . . . . . . 105 5.6. Äèçúþíêòèâíûå è êîíúþíêòèâíûå ôîðìû . . . . . . . . . . . . . . . 106 5.7. Òåîðåìû ïîãëîùåíèÿ, ñêëåèâàíèÿ è äå Ìîðãàíà . . . . . . . . . . . 107 5.8. Èíâåðòèðîâàíèå ñëîæíûõ âûðàæåíèé . . . . . . . . . . . . . . . . . . . 109
6. Äèçúþíêòèâíûå ôîðìû áóëåâûõ ôóíêöèé . . . . . . . . . . . . . . . . . . . . . . . 111 6.1. Ïîíÿòèå áóëåâîé ôóíêöèè . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 6.2. Êàê çàäàòü áóëåâó ôóíêöèþ . . . . . . . . . . . . . . . . . . . . . . . . . 113 6.3. Ìèíòåðìû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 6.4. Ñîâåðøåííàÿ äèçúþíêòèâíàÿ íîðìàëüíàÿ ôîðìà . . . . . . . . . . . 117 6.5. Òåîðåìà ðàçëîæåíèÿ äëÿ ÄÍÔ . . . . . . . . . . . . . . . . . . . . . . . . 119 6.6. Êàðòà Âåé÷à . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 6.7. Íàíåñåíèå ôóíêöèé íà êàðòó Âåé÷à . . . . . . . . . . . . . . . . . . . . 122 6.8. Íàõîæäåíèå ÑÄÍÔ ïðè ïîìîùè êàðò Âåé÷à . . . . . . . . . . . . . 124 6.9. Àëãåáðàè÷åñêîå óïðîùåíèå áóëåâûõ ôîðìóë . . . . . . . . . . . . . . 127 6.10. Ïîíÿòèå èìïëèêàíòû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 6.11. Ìåòîä Êâàéíà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.12. Íàõîæäåíèå ïðîñòûõ èìïëèêàíò ïî êàðòå Âåé÷à . . . . . . . . . . 133 6.13. Ìåòîä Ïåòðèêà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 6.14. Ìèíèìèçàöèÿ áóëåâûõ ôîðìóë ïðè ïîìîùè êàðò Âåé÷à . . . . . 139
7. Êîíúþíêòèâíûå ôîðìû áóëåâûõ ôóíêöèé . . . . . . . . . . . . . . . . . . . . . . . 142 7.1. Îñíîâíîé ñïîñîá íàõîæäåíèÿ ÊÍÔ . . . . . . . . . . . . . . . . . . . . . 142 7.2. Ìàêñòåðìû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 7.3. Ñîâåðøåííàÿ êîíúþíêòèâíàÿ íîðìàëüíàÿ ôîðìà . . . . . . . . . . . 145 7.4. Òåîðåìà ðàçëîæåíèÿ äëÿ ÊÍÔ . . . . . . . . . . . . . . . . . . . . . . . . 146
ОГЛАВЛЕНИЕ. Íàõîæäåíèå ñîêðàùåííûõ ÊÍÔ . . . . . . . . . . . . . . . . . . . . . . . 147 7.6. Íàõîæäåíèå òóïèêîâûõ è ìèíèìàëüíûõ ÊÍÔ . . . . . . . . . . . . 148 7.7. Ïåðåâîä ôóíêöèé èç ÊÍÔ â ÄÍÔ . . . . . . . . . . . . . . . . . . . . . 150
8. Íåïîëíîñòüþ îïðåäåëåííûå áóëåâû ôóíêöèè . . . . . . . . . . . . . . . . . . . . . 152 8.1. Ïîíÿòèå íåïîëíîñòüþ îïðåäåëåííîé áóëåâîé ôóíêöèè . . . . . . . 152 8.2. ÑÄÍÔ íåïîëíîñòüþ îïðåäåëåííûõ ôóíêöèé . . . . . . . . . . . . . . 153 8.3. ÑÊÍÔ íåïîëíîñòüþ îïðåäåëåííûõ ôóíêöèé . . . . . . . . . . . . . . 155 8.4. Ìèíèìèçàöèÿ ÄÍÔ íåïîëíîñòüþ îïðåäåëåííûõ ôóíêöèé . . . . 156 8.5. Ìèíèìèçàöèÿ ÊÍÔ íåïîëíîñòüþ îïðåäåëåííûõ ôóíêöèé . . . . 159
9. Ôîðìû âûñøèõ ïîðÿäêîâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 9.1. Ïîíÿòèå ïîðÿäêà áóëåâîé ôóíêöèè . . . . . . . . . . . . . . . . . . . . 162 9.2. Ãðàô-ñõåìà áóëåâîé ôóíêöèè . . . . . . . . . . . . . . . . . . . . . . . . . 164 9.3. Àáñîëþòíî ìèíèìàëüíûå ôîðìû. . . . . . . . . . . . . . . . . . . . . . . 166 9.4. Ïîâûøåíèå ïîðÿäêà áóëåâûõ ôóíêöèé . . . . . . . . . . . . . . . . . . 167 9.5. Êëàññèôèêàöèÿ ôîðì áóëåâûõ ôóíêöèé . . . . . . . . . . . . . . . . . 169 9.6. Î êëàññèôèêàöèè ôîðì âûñøèõ ïîðÿäêîâ. . . . . . . . . . . . . . . . 170
10. Ñèììåòðè÷åñêèå áóëåâû ôóíêöèè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 10.1. Ïîíÿòèå ñèììåòðè÷åñêîé ôóíêöèè . . . . . . . . . . . . . . . . . . . . . 174 10.2. Ñïîñîáû ïðåäñòàâëåíèÿ ñèììåòðè÷åñêèõ ôóíêöèé . . . . . . . . . . 175 10.3. Îïåðàöèè íàä ñèììåòðè÷åñêèìè ôóíêöèÿìè . . . . . . . . . . . . . . 177 10.4. Ðàçëîæåíèå ñèììåòðè÷åñêèõ ôóíêöèé äëÿ ÄÍÔ . . . . . . . . . . . 180 10.5. Ðàçëîæåíèå ñèììåòðè÷åñêèõ ôóíêöèé äëÿ ÊÍÔ . . . . . . . . . . . 182 10.6. Îáùèé ñëó÷àé ñèììåòðèè ôóíêöèé . . . . . . . . . . . . . . . . . . . . 183
11. ×èñëîâîå ïðåäñòàâëåíèå áóëåâûõ ôóíêöèé . . . . . . . . . . . . . . . . . . . . . . 184 11.1. Ïîíÿòèå èçîáðàæàþùåãî ÷èñëà áóëåâîé ôóíêöèè . . . . . . . . . . 184 11.2. Îïåðàöèè íàä èçîáðàæàþùèìè ÷èñëàìè . . . . . . . . . . . . . . . . . 186 11.3. Èçîáðàæàþùèå ÷èñëà ôóíêöèé âûñøèõ ïîðÿäêîâ . . . . . . . . . . 189 11.4. Âîññòàíîâëåíèå áóëåâîé ôóíêöèè ïî èçîáðàæàþùåìó ÷èñëó . . 190 11.5. ×èñëîâîå ïðåäñòàâëåíèå ñèñòåì áóëåâûõ ôóíêöèé. . . . . . . . . . 192 11.6. Çàâèñèìîñòü è íåçàâèñèìîñòü áóëåâûõ ôóíêöèé . . . . . . . . . . . 195 11.7. Âèäû çàâèñèìîñòè ìåæäó äâóìÿ ôóíêöèÿìè . . . . . . . . . . . . . 197 11.8. Íàõîæäåíèå ÿâíîãî âèäà ëîãè÷åñêîé çàâèñèìîñòè . . . . . . . . . . 200
12. Áóëåâû óðàâíåíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 12.1. Óðàâíåíèÿ ñ îäíîé íåèçâåñòíîé ïåðåìåííîé . . . . . . . . . . . . . . 203 12.2. Óðàâíåíèÿ ñ íåñêîëüêèìè íåèçâåñòíûìè ïåðåìåííûìè . . . . . . 207 12.3. Óðàâíåíèÿ êîíúþíêòèâíîãî òèïà . . . . . . . . . . . . . . . . . . . . . . 209 12.4. Óðàâíåíèÿ äèçúþíêòèâíîãî òèïà . . . . . . . . . . . . . . . . . . . . . . 211 12.5. Äðóãèå òèïû áóëåâûõ óðàâíåíèé . . . . . . . . . . . . . . . . . . . . . . 213 12.6. Áóëåâû óðàâíåíèÿ
ñ íåñêîëüêèìè íåèçâåñòíûìè ôóíêöèÿìè . . . . . . . . . . . . . . . . 215 12.7. Åùå ðàç î ôîðìàõ âûñøèõ ïîðÿäêîâ . . . . . . . . . . . . . . . . . . . 218 12.8. Íåðàçðåøèìûå óðàâíåíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
13. Ïîðîãîâûå ôóíêöèè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 13.1. Îñíîâíûå ïîíÿòèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 13.2. Ôóíêöèè, îïðåäåëÿåìûå ïîðîãîì ïðè íåèçìåííûõ âåñàõ . . . . . 224 13.3. Òåîðåìû î ïîðîãîâûõ ôóíêöèÿõ . . . . . . . . . . . . . . . . . . . . . . . 227 13.4. Íàõîæäåíèå ïîðîãîâûõ ôóíêöèé . . . . . . . . . . . . . . . . . . . . . . 228 13.5. Ìàæîðèòàðíûå ôóíêöèè . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 13.6. Ñèììåòðè÷åñêèå ìàæîðèòàðíûå ôóíêöèè . . . . . . . . . . . . . . . . 233
8. Íåïîëíîñòüþ îïðåäåëåííûå áóëåâû ôóíêöèè . . . . . . . . . . . . . . . . . . . . . 152 8.1. Ïîíÿòèå íåïîëíîñòüþ îïðåäåëåííîé áóëåâîé ôóíêöèè . . . . . . . 152 8.2. ÑÄÍÔ íåïîëíîñòüþ îïðåäåëåííûõ ôóíêöèé . . . . . . . . . . . . . . 153 8.3. ÑÊÍÔ íåïîëíîñòüþ îïðåäåëåííûõ ôóíêöèé . . . . . . . . . . . . . . 155 8.4. Ìèíèìèçàöèÿ ÄÍÔ íåïîëíîñòüþ îïðåäåëåííûõ ôóíêöèé . . . . 156 8.5. Ìèíèìèçàöèÿ ÊÍÔ íåïîëíîñòüþ îïðåäåëåííûõ ôóíêöèé . . . . 159
9. Ôîðìû âûñøèõ ïîðÿäêîâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 9.1. Ïîíÿòèå ïîðÿäêà áóëåâîé ôóíêöèè . . . . . . . . . . . . . . . . . . . . 162 9.2. Ãðàô-ñõåìà áóëåâîé ôóíêöèè . . . . . . . . . . . . . . . . . . . . . . . . . 164 9.3. Àáñîëþòíî ìèíèìàëüíûå ôîðìû. . . . . . . . . . . . . . . . . . . . . . . 166 9.4. Ïîâûøåíèå ïîðÿäêà áóëåâûõ ôóíêöèé . . . . . . . . . . . . . . . . . . 167 9.5. Êëàññèôèêàöèÿ ôîðì áóëåâûõ ôóíêöèé . . . . . . . . . . . . . . . . . 169 9.6. Î êëàññèôèêàöèè ôîðì âûñøèõ ïîðÿäêîâ. . . . . . . . . . . . . . . . 170
10. Ñèììåòðè÷åñêèå áóëåâû ôóíêöèè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 10.1. Ïîíÿòèå ñèììåòðè÷åñêîé ôóíêöèè . . . . . . . . . . . . . . . . . . . . . 174 10.2. Ñïîñîáû ïðåäñòàâëåíèÿ ñèììåòðè÷åñêèõ ôóíêöèé . . . . . . . . . . 175 10.3. Îïåðàöèè íàä ñèììåòðè÷åñêèìè ôóíêöèÿìè . . . . . . . . . . . . . . 177 10.4. Ðàçëîæåíèå ñèììåòðè÷åñêèõ ôóíêöèé äëÿ ÄÍÔ . . . . . . . . . . . 180 10.5. Ðàçëîæåíèå ñèììåòðè÷åñêèõ ôóíêöèé äëÿ ÊÍÔ . . . . . . . . . . . 182 10.6. Îáùèé ñëó÷àé ñèììåòðèè ôóíêöèé . . . . . . . . . . . . . . . . . . . . 183
11. ×èñëîâîå ïðåäñòàâëåíèå áóëåâûõ ôóíêöèé . . . . . . . . . . . . . . . . . . . . . . 184 11.1. Ïîíÿòèå èçîáðàæàþùåãî ÷èñëà áóëåâîé ôóíêöèè . . . . . . . . . . 184 11.2. Îïåðàöèè íàä èçîáðàæàþùèìè ÷èñëàìè . . . . . . . . . . . . . . . . . 186 11.3. Èçîáðàæàþùèå ÷èñëà ôóíêöèé âûñøèõ ïîðÿäêîâ . . . . . . . . . . 189 11.4. Âîññòàíîâëåíèå áóëåâîé ôóíêöèè ïî èçîáðàæàþùåìó ÷èñëó . . 190 11.5. ×èñëîâîå ïðåäñòàâëåíèå ñèñòåì áóëåâûõ ôóíêöèé. . . . . . . . . . 192 11.6. Çàâèñèìîñòü è íåçàâèñèìîñòü áóëåâûõ ôóíêöèé . . . . . . . . . . . 195 11.7. Âèäû çàâèñèìîñòè ìåæäó äâóìÿ ôóíêöèÿìè . . . . . . . . . . . . . 197 11.8. Íàõîæäåíèå ÿâíîãî âèäà ëîãè÷åñêîé çàâèñèìîñòè . . . . . . . . . . 200
12. Áóëåâû óðàâíåíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 12.1. Óðàâíåíèÿ ñ îäíîé íåèçâåñòíîé ïåðåìåííîé . . . . . . . . . . . . . . 203 12.2. Óðàâíåíèÿ ñ íåñêîëüêèìè íåèçâåñòíûìè ïåðåìåííûìè . . . . . . 207 12.3. Óðàâíåíèÿ êîíúþíêòèâíîãî òèïà . . . . . . . . . . . . . . . . . . . . . . 209 12.4. Óðàâíåíèÿ äèçúþíêòèâíîãî òèïà . . . . . . . . . . . . . . . . . . . . . . 211 12.5. Äðóãèå òèïû áóëåâûõ óðàâíåíèé . . . . . . . . . . . . . . . . . . . . . . 213 12.6. Áóëåâû óðàâíåíèÿ
ñ íåñêîëüêèìè íåèçâåñòíûìè ôóíêöèÿìè . . . . . . . . . . . . . . . . 215 12.7. Åùå ðàç î ôîðìàõ âûñøèõ ïîðÿäêîâ . . . . . . . . . . . . . . . . . . . 218 12.8. Íåðàçðåøèìûå óðàâíåíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
13. Ïîðîãîâûå ôóíêöèè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 13.1. Îñíîâíûå ïîíÿòèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 13.2. Ôóíêöèè, îïðåäåëÿåìûå ïîðîãîì ïðè íåèçìåííûõ âåñàõ . . . . . 224 13.3. Òåîðåìû î ïîðîãîâûõ ôóíêöèÿõ . . . . . . . . . . . . . . . . . . . . . . . 227 13.4. Íàõîæäåíèå ïîðîãîâûõ ôóíêöèé . . . . . . . . . . . . . . . . . . . . . . 228 13.5. Ìàæîðèòàðíûå ôóíêöèè . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 13.6. Ñèììåòðè÷åñêèå ìàæîðèòàðíûå ôóíêöèè . . . . . . . . . . . . . . . . 233
ДИСКРЕТНАЯ МАТЕМАТИКА. Áóëåâû äèôôåðåíöèàëüíîå è èíòåãðàëüíîå èñ÷èñëåíèÿ . . . . . . . . . . . . . 235 14.1. Àêñèîìû àëãåáðû Æåãàëêèíà . . . . . . . . . . . . . . . . . . . . . . . . . 235 14.2. Ïåðåâîä áóëåâûõ âûðàæåíèé
â àëãåáðó Æåãàëêèíà è íàîáîðîò . . . . . . . . . . . . . . . . . . . . . . 237 14.3. Ïðèìåíåíèå êàðò Âåé÷à â àëãåáðå Æåãàëêèíà . . . . . . . . . . . . 239 14.4. Ïîíÿòèå ïðîèçâîäíîé îò áóëåâîé ôóíêöèè . . . . . . . . . . . . . . . 243 14.5. Ïðîèçâîäíàÿ ïåðâîãî ïîðÿäêà. . . . . . . . . . . . . . . . . . . . . . . . . 245 14.6. Äèôôåðåíöèðîâàíèå áóëåâûõ ôóíêöèé
ñ ïðèìåíåíèåì êàðò Âåé÷à . . . . . . . . . . . . . . . . . . . . . . . . . . 247 14.7. Ñìåøàííûå ïðîèçâîäíûå . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 14.8. Òåîðåìû î ðàçëîæåíèè áóëåâûõ ôóíêöèé . . . . . . . . . . . . . . . . 252 14.9. Ðàçëîæåíèå áóëåâûõ ôóíêöèé â ðÿä Òåéëîðà . . . . . . . . . . . . . 254 14.10. Íàõîæäåíèå îòäåëüíûõ êîíúþíêöèé ðÿäà Òåéëîðà . . . . . . . . . 257 14.11. Òàáëè÷íîå èíòåãðèðîâàíèå áóëåâûõ ôóíêöèé . . . . . . . . . . . . . 259 14.12. Àíàëèòè÷åñêèé ñïîñîá èíòåãðèðîâàíèÿ áóëåâûõ ôóíêöèé . . . . 262
× À Ñ Ò Ü Ò Ð Å Ò Ü ß
ÒÅÎÐÈß ÊÎÍÅ×ÍÛÕ ÀÂÒÎÌÀÒÎÂ
Ââåäåíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
15. Äèîäíî-ðåçèñòîðíûå ñõåìû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 15.1. Ââîäíûå ïîíÿòèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 15.2. Ïðîñòåéøèå äèîäíî-ðåçèñòîðíûå ñõåìû . . . . . . . . . . . . . . . . . . 269 15.3. Âûïðÿìèòåëüíûé ìîñò . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
16. Êîíòàêòíûå ñòðóêòóðû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 16.1. Êîíòàêòíûå ýëåìåíòû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 16.2. Êîíòàêòíàÿ ðåàëèçàöèÿ ëîãè÷åñêèõ îïåðàöèé È, ÈËÈ, ÍÅ . . 277 16.3. Ïîñòðîåíèå êîíòàêòíîé ñòðóêòóðû ïî áóëåâîé ôóíêöèè . . . . . 278 16.4. Ëîãè÷åñêèé ñèíòåç êîíòàêòíûõ ñòðóêòóð . . . . . . . . . . . . . . . . 281 16.5. Ìîñòèêîâûå ñòðóêòóðû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 16.6. Ñèììåòðè÷åñêèå ñòðóêòóðû . . . . . . . . . . . . . . . . . . . . . . . . . . 285 16.7. Ïîëíàÿ ñèììåòðè÷åñêàÿ ñòðóêòóðà Øåííîíà . . . . . . . . . . . . . . 287 16.8. Ñòðóêòóðà «÷åò-íå÷åò» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 16.9. Ïðèìåð ïðàêòè÷åñêîãî ïðèìåíåíèÿ ñòðóêòóðû «÷åò-íå÷åò» . . . 289 16.10. Ñòðóêòóðû ñ ïåðåñòðàèâàåìîé ñõåìîé ñîåäèíåíèé . . . . . . . . . . 290 16.11. Ïðèìåðû êîíòàêòíûõ ñòðóêòóð . . . . . . . . . . . . . . . . . . . . . . . 293 16.12. Êîíòàêòíûå ñòðóêòóðû ñ ýëåìåíòàìè ïàìÿòè . . . . . . . . . . . . . 296
17. Êîìáèíàöèîííûå ñõåìû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 17.1. Ëîãè÷åñêèå ýëåìåíòû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 17.2. Ýëåìåíò È . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 17.3. Ýëåìåíò ÈËÈ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 17.4. Èíâåðòîð è ñõåìà ÈÍÅ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 17.5. Ïîíÿòèå ñóïåðïîçèöèè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 17.6. Î íàãðóçî÷íîé ñïîñîáíîñòè ëîãè÷åñêèõ ýëåìåíòîâ . . . . . . . . . . 308 17.7. Êîìáèíàöèîííûå ñõåìû è áóëåâû ôóíêöèè ÄÍÔ è ÊÍÔ . . . . 310 17.8. Êîìáèíàöèîííûå ñõåìû
è áóëåâû ôóíêöèè âûñøèõ ïîðÿäêîâ . . . . . . . . . . . . . . . . . . . 312 17.9. Ëîãè÷åñêèé ñèíòåç êîìáèíàöèîííûõ ñõåì . . . . . . . . . . . . . . . 314 17.10. Ñèíòåç ïðåîáðàçîâàòåëÿ äâîè÷íîãî ÷èñëà â êîä «2 èç 5». . . . . 317 17.11. Ïîëíûé äåøèôðàòîð . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 17.12. Ñèíòåç íåïîëíîãî äåøèôðàòîðà. . . . . . . . . . . . . . . . . . . . . . . . 320 17.13. Ìóëüòèïëåêñîð . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
â àëãåáðó Æåãàëêèíà è íàîáîðîò . . . . . . . . . . . . . . . . . . . . . . 237 14.3. Ïðèìåíåíèå êàðò Âåé÷à â àëãåáðå Æåãàëêèíà . . . . . . . . . . . . 239 14.4. Ïîíÿòèå ïðîèçâîäíîé îò áóëåâîé ôóíêöèè . . . . . . . . . . . . . . . 243 14.5. Ïðîèçâîäíàÿ ïåðâîãî ïîðÿäêà. . . . . . . . . . . . . . . . . . . . . . . . . 245 14.6. Äèôôåðåíöèðîâàíèå áóëåâûõ ôóíêöèé
ñ ïðèìåíåíèåì êàðò Âåé÷à . . . . . . . . . . . . . . . . . . . . . . . . . . 247 14.7. Ñìåøàííûå ïðîèçâîäíûå . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 14.8. Òåîðåìû î ðàçëîæåíèè áóëåâûõ ôóíêöèé . . . . . . . . . . . . . . . . 252 14.9. Ðàçëîæåíèå áóëåâûõ ôóíêöèé â ðÿä Òåéëîðà . . . . . . . . . . . . . 254 14.10. Íàõîæäåíèå îòäåëüíûõ êîíúþíêöèé ðÿäà Òåéëîðà . . . . . . . . . 257 14.11. Òàáëè÷íîå èíòåãðèðîâàíèå áóëåâûõ ôóíêöèé . . . . . . . . . . . . . 259 14.12. Àíàëèòè÷åñêèé ñïîñîá èíòåãðèðîâàíèÿ áóëåâûõ ôóíêöèé . . . . 262
× À Ñ Ò Ü Ò Ð Å Ò Ü ß
ÒÅÎÐÈß ÊÎÍÅ×ÍÛÕ ÀÂÒÎÌÀÒÎÂ
Ââåäåíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
15. Äèîäíî-ðåçèñòîðíûå ñõåìû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 15.1. Ââîäíûå ïîíÿòèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 15.2. Ïðîñòåéøèå äèîäíî-ðåçèñòîðíûå ñõåìû . . . . . . . . . . . . . . . . . . 269 15.3. Âûïðÿìèòåëüíûé ìîñò . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
16. Êîíòàêòíûå ñòðóêòóðû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 16.1. Êîíòàêòíûå ýëåìåíòû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 16.2. Êîíòàêòíàÿ ðåàëèçàöèÿ ëîãè÷åñêèõ îïåðàöèé È, ÈËÈ, ÍÅ . . 277 16.3. Ïîñòðîåíèå êîíòàêòíîé ñòðóêòóðû ïî áóëåâîé ôóíêöèè . . . . . 278 16.4. Ëîãè÷åñêèé ñèíòåç êîíòàêòíûõ ñòðóêòóð . . . . . . . . . . . . . . . . 281 16.5. Ìîñòèêîâûå ñòðóêòóðû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 16.6. Ñèììåòðè÷åñêèå ñòðóêòóðû . . . . . . . . . . . . . . . . . . . . . . . . . . 285 16.7. Ïîëíàÿ ñèììåòðè÷åñêàÿ ñòðóêòóðà Øåííîíà . . . . . . . . . . . . . . 287 16.8. Ñòðóêòóðà «÷åò-íå÷åò» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 16.9. Ïðèìåð ïðàêòè÷åñêîãî ïðèìåíåíèÿ ñòðóêòóðû «÷åò-íå÷åò» . . . 289 16.10. Ñòðóêòóðû ñ ïåðåñòðàèâàåìîé ñõåìîé ñîåäèíåíèé . . . . . . . . . . 290 16.11. Ïðèìåðû êîíòàêòíûõ ñòðóêòóð . . . . . . . . . . . . . . . . . . . . . . . 293 16.12. Êîíòàêòíûå ñòðóêòóðû ñ ýëåìåíòàìè ïàìÿòè . . . . . . . . . . . . . 296
17. Êîìáèíàöèîííûå ñõåìû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 17.1. Ëîãè÷åñêèå ýëåìåíòû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 17.2. Ýëåìåíò È . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 17.3. Ýëåìåíò ÈËÈ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 17.4. Èíâåðòîð è ñõåìà ÈÍÅ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 17.5. Ïîíÿòèå ñóïåðïîçèöèè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 17.6. Î íàãðóçî÷íîé ñïîñîáíîñòè ëîãè÷åñêèõ ýëåìåíòîâ . . . . . . . . . . 308 17.7. Êîìáèíàöèîííûå ñõåìû è áóëåâû ôóíêöèè ÄÍÔ è ÊÍÔ . . . . 310 17.8. Êîìáèíàöèîííûå ñõåìû
è áóëåâû ôóíêöèè âûñøèõ ïîðÿäêîâ . . . . . . . . . . . . . . . . . . . 312 17.9. Ëîãè÷åñêèé ñèíòåç êîìáèíàöèîííûõ ñõåì . . . . . . . . . . . . . . . 314 17.10. Ñèíòåç ïðåîáðàçîâàòåëÿ äâîè÷íîãî ÷èñëà â êîä «2 èç 5». . . . . 317 17.11. Ïîëíûé äåøèôðàòîð . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 17.12. Ñèíòåç íåïîëíîãî äåøèôðàòîðà. . . . . . . . . . . . . . . . . . . . . . . . 320 17.13. Ìóëüòèïëåêñîð . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
ОГЛАВЛЕНИЕ. Îäíîðîäíûå ñðåäû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324 17.15. Ñõåìû ñðàâíåíèÿ äâóõ äâîè÷íûõ ÷èñåë . . . . . . . . . . . . . . . . . 326 17.16. Ñõåìà «÷åòíå÷åò» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 17.17. Ñèíòåç äâîè÷íîãî ñóììàòîðà . . . . . . . . . . . . . . . . . . . . . . . . . 329 17.18. Âû÷èñëåíèå áåñïîâòîðíûõ áóëåâûõ ôóíêöèé . . . . . . . . . . . . . 331 17.19. Îáíàðóæåíèå îäèíî÷íûõ èñêàæåíèé â äâîè÷íûõ êîäàõ . . . . . 333 17.20. Êîäû Õýììèíãà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336 17.21. Êîìáèíàöèîííûé ôîðìèðîâàòåëü êîäîâ Õýììèíãà . . . . . . . . . . 338 17.22. Ðåôëåêñíûå êîäû. Êîäû Ãðåÿ . . . . . . . . . . . . . . . . . . . . . . . . 340 17.23. Ïðåîáðàçîâàòåëü êîäà Ãðåÿ â âåñîâîé äâîè÷íûé êîä . . . . . . . . 342 17.24. Ïðåîáðàçîâàíèå ïðîèçâîëüíîãî
ðåôëåêñíîãî êîäà â äâîè÷íûé âåñîâîé êîä . . . . . . . . . . . . . . . 343
18. Ôóíêöèîíàëüíàÿ ïîëíîòà ñèñòåìû ëîãè÷åñêèõ ýëåìåíòîâ . . . . . . . . . . . . 346 18.1. Ïîíÿòèå ôóíêöèîíàëüíîé ïîëíîòû . . . . . . . . . . . . . . . . . . . . . 346 18.2. Ñàìîäâîéñòâåííûå ôóíêöèè . . . . . . . . . . . . . . . . . . . . . . . . . . 347 18.3. Ëèíåéíûå ôóíêöèè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349 18.4. Ìîíîòîííûå ôóíêöèè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350 18.5. Ôóíêöèè, ñîõðàíÿþùèå åäèíèöó . . . . . . . . . . . . . . . . . . . . . . 353 18.6. Ôóíêöèè, ñîõðàíÿþùèå íóëü . . . . . . . . . . . . . . . . . . . . . . . . . 355 18.7. Òåîðåìà Ïîñòà î ôóíêöèîíàëüíîé ïîëíîòå . . . . . . . . . . . . . . . 357 18.8. Ôóíêöèè äâóõ àðãóìåíòîâ . . . . . . . . . . . . . . . . . . . . . . . . . . . 358 18.9. Ìèíèìàëüíûå ïîëíûå ñèñòåìû ýëåìåíòàðíûõ ôóíêöèé . . . . . . 362 18.10. Î ðåàëüíûõ ñèñòåìàõ ëîãè÷åñêèõ ýëåìåíòîâ . . . . . . . . . . . . . . 365
19. Ìíîãîòàêòíûå àâòîìàòû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369 19.1. Îäíîòàêòíûå è ìíîãîòàêòíûå àâòîìàòû . . . . . . . . . . . . . . . . . 369 19.2. Òðèããåð òèïà RS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370 19.3. Òðèããåð òèïà Ò . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372 19.4. Àñèíõðîííûå àâòîìàòû íà Ò-òðèããåðàõ . . . . . . . . . . . . . . . . . . 374 19.5. Ñèíòåç ñèíõðîííûõ àâòîìàòîâ íà òðèããåðàõ òèïà Ò . . . . . . . . 377 19.6. Òðèããåð òèïà JK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379 19.7. Ñèíòåç ïðîñòåéøèõ
ìíîãîòàêòíûõ àâòîìàòîâ íà JK-òðèããåðàõ . . . . . . . . . . . . . . . . 381 19.8. Ñäâèãîâûé ðåãèñòð . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383 19.9. Ñèíòåç ìíîãîôóíêöèîíàëüíûõ àâòîìàòîâ . . . . . . . . . . . . . . . . . 385 19.10. Àâòîìàòû ñ ïðîèçâîëüíûì öèêëîì ñìåíû ñîñòîÿíèé . . . . . . . 387 19.11. Àâòîìàò ñ ëîãè÷åñêîé ñõåìîé íà âûõîäàõ . . . . . . . . . . . . . . . 388 19.12. Ñèíòåç ïðåîáðàçîâàòåëÿ êîäîâ, ñîäåðæàùåãî ïàìÿòü . . . . . . . . 390 19.13. Ðàñïðåäåëèòåëè èìïóëüñîâ . . . . . . . . . . . . . . . . . . . . . . . . . . . 394 19.14. Îñíîâíàÿ ìîäåëü êîíå÷íîãî àâòîìàòà . . . . . . . . . . . . . . . . . . . 395 19.15. Àâòîìàò Ìèëè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397 19.16. Àâòîìàò Ìóðà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399
× À Ñ Ò Ü × Å Ò Â Å Ð Ò À ß
ðåôëåêñíîãî êîäà â äâîè÷íûé âåñîâîé êîä . . . . . . . . . . . . . . . 343
18. Ôóíêöèîíàëüíàÿ ïîëíîòà ñèñòåìû ëîãè÷åñêèõ ýëåìåíòîâ . . . . . . . . . . . . 346 18.1. Ïîíÿòèå ôóíêöèîíàëüíîé ïîëíîòû . . . . . . . . . . . . . . . . . . . . . 346 18.2. Ñàìîäâîéñòâåííûå ôóíêöèè . . . . . . . . . . . . . . . . . . . . . . . . . . 347 18.3. Ëèíåéíûå ôóíêöèè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349 18.4. Ìîíîòîííûå ôóíêöèè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350 18.5. Ôóíêöèè, ñîõðàíÿþùèå åäèíèöó . . . . . . . . . . . . . . . . . . . . . . 353 18.6. Ôóíêöèè, ñîõðàíÿþùèå íóëü . . . . . . . . . . . . . . . . . . . . . . . . . 355 18.7. Òåîðåìà Ïîñòà î ôóíêöèîíàëüíîé ïîëíîòå . . . . . . . . . . . . . . . 357 18.8. Ôóíêöèè äâóõ àðãóìåíòîâ . . . . . . . . . . . . . . . . . . . . . . . . . . . 358 18.9. Ìèíèìàëüíûå ïîëíûå ñèñòåìû ýëåìåíòàðíûõ ôóíêöèé . . . . . . 362 18.10. Î ðåàëüíûõ ñèñòåìàõ ëîãè÷åñêèõ ýëåìåíòîâ . . . . . . . . . . . . . . 365
19. Ìíîãîòàêòíûå àâòîìàòû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369 19.1. Îäíîòàêòíûå è ìíîãîòàêòíûå àâòîìàòû . . . . . . . . . . . . . . . . . 369 19.2. Òðèããåð òèïà RS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370 19.3. Òðèããåð òèïà Ò . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372 19.4. Àñèíõðîííûå àâòîìàòû íà Ò-òðèããåðàõ . . . . . . . . . . . . . . . . . . 374 19.5. Ñèíòåç ñèíõðîííûõ àâòîìàòîâ íà òðèããåðàõ òèïà Ò . . . . . . . . 377 19.6. Òðèããåð òèïà JK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379 19.7. Ñèíòåç ïðîñòåéøèõ
ìíîãîòàêòíûõ àâòîìàòîâ íà JK-òðèããåðàõ . . . . . . . . . . . . . . . . 381 19.8. Ñäâèãîâûé ðåãèñòð . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383 19.9. Ñèíòåç ìíîãîôóíêöèîíàëüíûõ àâòîìàòîâ . . . . . . . . . . . . . . . . . 385 19.10. Àâòîìàòû ñ ïðîèçâîëüíûì öèêëîì ñìåíû ñîñòîÿíèé . . . . . . . 387 19.11. Àâòîìàò ñ ëîãè÷åñêîé ñõåìîé íà âûõîäàõ . . . . . . . . . . . . . . . 388 19.12. Ñèíòåç ïðåîáðàçîâàòåëÿ êîäîâ, ñîäåðæàùåãî ïàìÿòü . . . . . . . . 390 19.13. Ðàñïðåäåëèòåëè èìïóëüñîâ . . . . . . . . . . . . . . . . . . . . . . . . . . . 394 19.14. Îñíîâíàÿ ìîäåëü êîíå÷íîãî àâòîìàòà . . . . . . . . . . . . . . . . . . . 395 19.15. Àâòîìàò Ìèëè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397 19.16. Àâòîìàò Ìóðà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399
× À Ñ Ò Ü × Å Ò Â Å Ð Ò À ß
1 ... 69 70 71 72 73 74 75 76 77
ÊÎÌÁÈÍÀÒÎÐÈÊÀ
Ââåäåíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
20. Îñíîâíûå ôîðìóëû êîìáèíàòîðèêè . . . . . . . . . . . . . . . . . . . . . . . . . . . 404 20.1. Ïîíÿòèå ôàêòîðèàëà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404 20.2. Ïðàâèëî ïðîèçâåäåíèÿ â êîìáèíàòîðèêå . . . . . . . . . . . . . . . . . 406 20.3. Ïðàâèëî ñóììû â êîìáèíàòîðèêå . . . . . . . . . . . . . . . . . . . . . . 408 20.4. Ïðàâèëî ñóììû è äèàãðàììû Âåííà . . . . . . . . . . . . . . . . . . . 410 20.5. Ïåðåñòàíîâêè áåç ïîâòîðåíèé . . . . . . . . . . . . . . . . . . . . . . . . . 411
Ââåäåíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
20. Îñíîâíûå ôîðìóëû êîìáèíàòîðèêè . . . . . . . . . . . . . . . . . . . . . . . . . . . 404 20.1. Ïîíÿòèå ôàêòîðèàëà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404 20.2. Ïðàâèëî ïðîèçâåäåíèÿ â êîìáèíàòîðèêå . . . . . . . . . . . . . . . . . 406 20.3. Ïðàâèëî ñóììû â êîìáèíàòîðèêå . . . . . . . . . . . . . . . . . . . . . . 408 20.4. Ïðàâèëî ñóììû è äèàãðàììû Âåííà . . . . . . . . . . . . . . . . . . . 410 20.5. Ïåðåñòàíîâêè áåç ïîâòîðåíèé . . . . . . . . . . . . . . . . . . . . . . . . . 411
ДИСКРЕТНАЯ МАТЕМАТИКА. Ïåðåñòàíîâêè ñ ïîâòîðåíèÿìè . . . . . . . . . . . . . . . . . . . . . . . . 413 20.7. Ðàçìåùåíèÿ áåç ïîâòîðåíèé . . . . . . . . . . . . . . . . . . . . . . . . . . 414 20.8. Ðàçìåùåíèÿ ñ ïîâòîðåíèÿìè . . . . . . . . . . . . . . . . . . . . . . . . . 417 20.9. Ñî÷åòàíèÿ áåç ïîâòîðåíèé . . . . . . . . . . . . . . . . . . . . . . . . . . . 419 20.10. Ñâîéñòâà ñî÷åòàíèé áåç ïîâòîðåíèé . . . . . . . . . . . . . . . . . . . . 424 20.11. Ñî÷åòàíèÿ ñ ïîâòîðåíèÿìè . . . . . . . . . . . . . . . . . . . . . . . . . . . 426 20.12. Óïðàæíåíèÿ íà ïðèìåíåíèå
îñíîâíûõ ôîðìóë êîìáèíàòîðèêè . . . . . . . . . . . . . . . . . . . . . . 428
21. Êîìáèíàòîðíûå çàäà÷è . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432 21.1. Ðàçáèåíèå ìíîæåñòâà íà äâà ïîäìíîæåñòâà . . . . . . . . . . . . . . 432 21.2. Ðàçáèåíèå ìíîæåñòâà íà íåñêîëüêî ïîäìíîæåñòâ . . . . . . . . . . 436 21.3. Çàäà÷à î ïåðåêëþ÷àòåëÿõ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439 21.4. Çàäà÷à î ðàñïèñàíèè çàíÿòèé . . . . . . . . . . . . . . . . . . . . . . . . . 441 21.5. Çàäà÷à î ïîäáîðå ýêèïàæà êîñìè÷åñêîãî êîðàáëÿ . . . . . . . . . . 444 21.6. Çàäà÷à î áåñïîðÿäêàõ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445 21.7. Äâîè÷íî-êîäèðîâàííûå ñèñòåìû . . . . . . . . . . . . . . . . . . . . . . . 447 21.8. Êîä Ìîðçå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450 21.9. Ïðîñòûå ÷èñëà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451 21.10. Çàäà÷à î ÷èñëå äåëèòåëåé . . . . . . . . . . . . . . . . . . . . . . . . . . . 454 21.11. Çàäà÷à î âïèñàííûõ òðåóãîëüíèêàõ . . . . . . . . . . . . . . . . . . . . 455 21.12. Çàäà÷à î ðàçáèåíèè ÷èñëà íà ñëàãàåìûå . . . . . . . . . . . . . . . . . 457 21.13. Çàäà÷à î «ñ÷àñòëèâûõ» òðîëëåéáóñíûõ áèëåòàõ. . . . . . . . . . . . 460 21.14. Óïðàæíåíèÿ ïî âñåìó êóðñó êîìáèíàòîðèêè . . . . . . . . . . . . . 462
× À Ñ Ò Ü Ï ß Ò À ß
ÒÅÎÐÈß ÃÐÀÔÎÂ
Ââåäåíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472
22. Ââîäíûå ïîíÿòèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474 22.1. Ãðàô . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474 22.2. Ïñåâäîãðàô. Ìóëüòèãðàô . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474 22.3. Ïîäãðàô. Íàäãðàô. ×àñòè÷íûé ãðàô . . . . . . . . . . . . . . . . . . . . 475 22.4. Ñìåæíîñòü. Èíöèäåíòíîñòü. Ñòåïåíü âåðøèíû . . . . . . . . . . . . 478 22.5. Îäíîðîäíûé ãðàô. Ïîëíûé ãðàô. Äîïîëíåíèå ãðàôà . . . . . . . . 480 22.6. Îáúåäèíåíèå è ïåðåñå÷åíèå ãðàôîâ . . . . . . . . . . . . . . . . . . . . . 482 22.7. Èçîìîðôèçì . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483 22.8. Ìàòðèöû ñìåæíîñòè è èíöèäåíòíîñòè . . . . . . . . . . . . . . . . . . 485
23. Ñâÿçíûå ãðàôû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489 23.1. Ìàðøðóòû, öåïè, öèêëû . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489 23.2. Ñâÿçíîñòü ãðàôà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491 23.3. Íàõîæäåíèå ïðîñòûõ öåïåé . . . . . . . . . . . . . . . . . . . . . . . . . . 492 23.4. Ïðèìåíåíèå ìåòîäà íàõîæäåíèÿ âñåõ ïðîñòûõ öåïåé . . . . . . . 495 23.5. Ýéëåðîâû öåïè è öèêëû. Óíèêóðñàëüíàÿ ëèíèÿ . . . . . . . . . . . 497 23.6. Ãàìèëüòîíîâû ãðàôû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500 23.7. Çàäà÷à î êîììèâîÿæåðå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502 23.8. Äâóäîëüíûå ãðàôû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503 23.9. Ìåòðèêà ãðàôà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
24. Ïëàíàðíûå è ïëîñêèå ãðàôû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507 24.1. Ââîäíûå ïîíÿòèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507 24.2. Òåîðåìà Ýéëåðà î ïëîñêèõ ãðàôàõ . . . . . . . . . . . . . . . . . . . . . 508 24.3. Ãîìåîìîðôèçì . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509
îñíîâíûõ ôîðìóë êîìáèíàòîðèêè . . . . . . . . . . . . . . . . . . . . . . 428
21. Êîìáèíàòîðíûå çàäà÷è . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432 21.1. Ðàçáèåíèå ìíîæåñòâà íà äâà ïîäìíîæåñòâà . . . . . . . . . . . . . . 432 21.2. Ðàçáèåíèå ìíîæåñòâà íà íåñêîëüêî ïîäìíîæåñòâ . . . . . . . . . . 436 21.3. Çàäà÷à î ïåðåêëþ÷àòåëÿõ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439 21.4. Çàäà÷à î ðàñïèñàíèè çàíÿòèé . . . . . . . . . . . . . . . . . . . . . . . . . 441 21.5. Çàäà÷à î ïîäáîðå ýêèïàæà êîñìè÷åñêîãî êîðàáëÿ . . . . . . . . . . 444 21.6. Çàäà÷à î áåñïîðÿäêàõ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445 21.7. Äâîè÷íî-êîäèðîâàííûå ñèñòåìû . . . . . . . . . . . . . . . . . . . . . . . 447 21.8. Êîä Ìîðçå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450 21.9. Ïðîñòûå ÷èñëà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451 21.10. Çàäà÷à î ÷èñëå äåëèòåëåé . . . . . . . . . . . . . . . . . . . . . . . . . . . 454 21.11. Çàäà÷à î âïèñàííûõ òðåóãîëüíèêàõ . . . . . . . . . . . . . . . . . . . . 455 21.12. Çàäà÷à î ðàçáèåíèè ÷èñëà íà ñëàãàåìûå . . . . . . . . . . . . . . . . . 457 21.13. Çàäà÷à î «ñ÷àñòëèâûõ» òðîëëåéáóñíûõ áèëåòàõ. . . . . . . . . . . . 460 21.14. Óïðàæíåíèÿ ïî âñåìó êóðñó êîìáèíàòîðèêè . . . . . . . . . . . . . 462
× À Ñ Ò Ü Ï ß Ò À ß
ÒÅÎÐÈß ÃÐÀÔÎÂ
Ââåäåíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472
22. Ââîäíûå ïîíÿòèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474 22.1. Ãðàô . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474 22.2. Ïñåâäîãðàô. Ìóëüòèãðàô . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474 22.3. Ïîäãðàô. Íàäãðàô. ×àñòè÷íûé ãðàô . . . . . . . . . . . . . . . . . . . . 475 22.4. Ñìåæíîñòü. Èíöèäåíòíîñòü. Ñòåïåíü âåðøèíû . . . . . . . . . . . . 478 22.5. Îäíîðîäíûé ãðàô. Ïîëíûé ãðàô. Äîïîëíåíèå ãðàôà . . . . . . . . 480 22.6. Îáúåäèíåíèå è ïåðåñå÷åíèå ãðàôîâ . . . . . . . . . . . . . . . . . . . . . 482 22.7. Èçîìîðôèçì . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483 22.8. Ìàòðèöû ñìåæíîñòè è èíöèäåíòíîñòè . . . . . . . . . . . . . . . . . . 485
23. Ñâÿçíûå ãðàôû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489 23.1. Ìàðøðóòû, öåïè, öèêëû . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489 23.2. Ñâÿçíîñòü ãðàôà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491 23.3. Íàõîæäåíèå ïðîñòûõ öåïåé . . . . . . . . . . . . . . . . . . . . . . . . . . 492 23.4. Ïðèìåíåíèå ìåòîäà íàõîæäåíèÿ âñåõ ïðîñòûõ öåïåé . . . . . . . 495 23.5. Ýéëåðîâû öåïè è öèêëû. Óíèêóðñàëüíàÿ ëèíèÿ . . . . . . . . . . . 497 23.6. Ãàìèëüòîíîâû ãðàôû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500 23.7. Çàäà÷à î êîììèâîÿæåðå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502 23.8. Äâóäîëüíûå ãðàôû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503 23.9. Ìåòðèêà ãðàôà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
24. Ïëàíàðíûå è ïëîñêèå ãðàôû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507 24.1. Ââîäíûå ïîíÿòèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507 24.2. Òåîðåìà Ýéëåðà î ïëîñêèõ ãðàôàõ . . . . . . . . . . . . . . . . . . . . . 508 24.3. Ãîìåîìîðôèçì . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509
ОГЛАВЛЕНИЕ. Êðèòåðèé ÏîíòðÿãèíàÊóðàòîâñêîãî . . . . . . . . . . . . . . . . . . . . 511 24.5. Äâîéñòâåííûå ãðàôû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513 24.6. Èíâåðñíûå ñòðóêòóðû è äâîéñòâåííûå ãðàôû . . . . . . . . . . . . . 514 24.7. Äåðåâüÿ è ëåñ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516 24.8. Ôóíäàìåíòàëüíàÿ ñèñòåìà öèêëîâ . . . . . . . . . . . . . . . . . . . . . . 517 24.9. Êîäèðîâàíèå äåðåâüåâ ìåòîäîì Ïðóôåðà . . . . . . . . . . . . . . . . . 518 24.10. Ïîñòðîåíèå äåðåâà ïî åãî êîäó . . . . . . . . . . . . . . . . . . . . . . . 519 24.11. Ðàçðåçû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522 24.12. Õðîìàòè÷åñêîå ÷èñëî ãðàôà. Ãèïîòåçà ÷åòûðåõ êðàñîê . . . . . . 524
25. Îðèåíòèðîâàííûå ãðàôû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526 25.1. Ïîíÿòèå îðãðàôà. Ìàòðèöà ñìåæíîñòè. Èçîìîðôèçì . . . . . . . . 526 25.2. Ñòåïåíü âåðøèíû îðãðàôà . . . . . . . . . . . . . . . . . . . . . . . . . . . 528 25.3. Ìàðøðóòû, öåïè, öèêëû â îðãðàôàõ . . . . . . . . . . . . . . . . . . . 529 25.4. Ñâÿçíîñòü îðãðàôà. Ýéëåðîâû öåïè è öèêëû â îðãðàôå . . . . . 531 25.5. Ïîëíûé îðãðàô . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533 25.6. Î òåîðèè òðàíñâåðñàëåé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535 25.7. Ìåòîä íàõîæäåíèÿ âñåõ òðàíñâåðñàëåé . . . . . . . . . . . . . . . . . . 535 25.8. Íàõîæäåíèå ìàêñèìàëüíîé
ïðîïóñêíîé ñïîñîáíîñòè òðàíñïîðòíîé ñåòè . . . . . . . . . . . . . . . 537 25.9. Îðãðàôû è áèíàðíûå îòíîøåíèÿ. Äèàãðàììû Õàññå . . . . . . . . 539 25.10. Ñêîëüêî ñóùåñòâóåò ãðàôîâ? . . . . . . . . . . . . . . . . . . . . . . . . . 541
Çàêëþ÷åíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543
Êîíòðîëüíûå ðàáîòû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545
Òåîðèÿ ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545
Áóëåâà àëãåáðà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547
Òåîðèÿ êîíå÷íûõ àâòîìàòîâ . . . . . . . . . . . . . . . . . . . . . . . . . . 554
Êîìáèíàòîðèêà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558
Òåîðèÿ ãðàôîâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 560
Îòâåòû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563
Òåîðèÿ ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563
Áóëåâà àëãåáðà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565
Òåîðèÿ êîíå÷íûõ àâòîìàòîâ . . . . . . . . . . . . . . . . . . . . . . . . . . 570
Êîìáèíàòîðèêà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573
Òåîðèÿ ãðàôîâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574
Ëèòåðàòóðà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 577
Öèòèðîâàííûå èñòî÷íèêè . . . . . . . . . . . . . . . . . . . . . . . . . . . . 577
Äîïîëíèòåëüíàÿ ëèòåðàòóðà . . . . . . . . . . . . . . . . . . . . . . . . . . 579
Ïðåäìåòíûé óêàçàòåëü . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 580
25. Îðèåíòèðîâàííûå ãðàôû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526 25.1. Ïîíÿòèå îðãðàôà. Ìàòðèöà ñìåæíîñòè. Èçîìîðôèçì . . . . . . . . 526 25.2. Ñòåïåíü âåðøèíû îðãðàôà . . . . . . . . . . . . . . . . . . . . . . . . . . . 528 25.3. Ìàðøðóòû, öåïè, öèêëû â îðãðàôàõ . . . . . . . . . . . . . . . . . . . 529 25.4. Ñâÿçíîñòü îðãðàôà. Ýéëåðîâû öåïè è öèêëû â îðãðàôå . . . . . 531 25.5. Ïîëíûé îðãðàô . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533 25.6. Î òåîðèè òðàíñâåðñàëåé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535 25.7. Ìåòîä íàõîæäåíèÿ âñåõ òðàíñâåðñàëåé . . . . . . . . . . . . . . . . . . 535 25.8. Íàõîæäåíèå ìàêñèìàëüíîé
ïðîïóñêíîé ñïîñîáíîñòè òðàíñïîðòíîé ñåòè . . . . . . . . . . . . . . . 537 25.9. Îðãðàôû è áèíàðíûå îòíîøåíèÿ. Äèàãðàììû Õàññå . . . . . . . . 539 25.10. Ñêîëüêî ñóùåñòâóåò ãðàôîâ? . . . . . . . . . . . . . . . . . . . . . . . . . 541
Çàêëþ÷åíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543
Êîíòðîëüíûå ðàáîòû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545
Òåîðèÿ ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545
Áóëåâà àëãåáðà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547
Òåîðèÿ êîíå÷íûõ àâòîìàòîâ . . . . . . . . . . . . . . . . . . . . . . . . . . 554
Êîìáèíàòîðèêà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558
Òåîðèÿ ãðàôîâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 560
Îòâåòû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563
Òåîðèÿ ìíîæåñòâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563
Áóëåâà àëãåáðà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565
Òåîðèÿ êîíå÷íûõ àâòîìàòîâ . . . . . . . . . . . . . . . . . . . . . . . . . . 570
Êîìáèíàòîðèêà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573
Òåîðèÿ ãðàôîâ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574
Ëèòåðàòóðà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 577
Öèòèðîâàííûå èñòî÷íèêè . . . . . . . . . . . . . . . . . . . . . . . . . . . . 577
Äîïîëíèòåëüíàÿ ëèòåðàòóðà . . . . . . . . . . . . . . . . . . . . . . . . . . 579
Ïðåäìåòíûé óêàçàòåëü . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 580
Юрий Павлович ШЕВЕЛЕВ
ДИСКРЕТНАЯ МАТЕМАТИКА
У ч е б но е пособие Издательство ЛАНЬ www.lanbook.com
196105, СанктПетербург, пр. Юрия Гагарина, длит. А
Тел./факс: (812) 3362509, Бесплатный звонок по России ГДЕ КУПИТЬ
ДЛЯ ОРГАНИЗАЦИЙ:
Для того, чтобы заказать необходимые Вам книги, достаточно обратиться
в любую из торговых компаний Издательского Дома «ЛАНЬ»
:
по России и зарубежью
«ЛАНЬТРЕЙД». 192029, СанктПетербург, ул. Крупской, тел (812) 4128578, 4121445, 4128582; тел./факс: (812) 4125493
email: trade@lanbook.ru; ICQ: в Москве ив Московской области
«ЛАНЬПРЕСС». 109263, Москва, я ул. Текстильщиков, д. тел (499) 1786585; email: в Краснодаре ив Краснодарском крае
«ЛАНЬЮГ». 350901, Краснодар, ул. Жлобы, д. тел (861) 2741035; email: ДЛЯ РОЗНИЧНЫХ ПОКУПАТЕЛЕЙ:
интернет(магазины
:
Издательство Лань Сова http://www.symplex.ru; «Ozon.ru»: http://www.ozon.ru
«Библион»: http://www.biblion.ru
Ïîäïèñàíî â ïå÷àòü 13.11.15.
Áóìàãà îôñåòíàÿ. Ãàðíèòóðà Øêîëüíàÿ. Ôîðìàò 70´100 1
/
16
Ïå÷àòü îôñåòíàÿ. Óñë. ï. ë. 48,10. Òèðàæ 100 ýêç.
Çàêàç ¹ Отпечатано в полном соответствии с качеством предоставленного оригиналмакета.
в ПАО Т Издательские Технологии, г. Москва, Волгоградский пр, д. 42, к. 5.
ДИСКРЕТНАЯ МАТЕМАТИКА
У ч е б но е пособие Издательство ЛАНЬ www.lanbook.com
196105, СанктПетербург, пр. Юрия Гагарина, длит. А
Тел./факс: (812) 3362509, Бесплатный звонок по России ГДЕ КУПИТЬ
ДЛЯ ОРГАНИЗАЦИЙ:
Для того, чтобы заказать необходимые Вам книги, достаточно обратиться
в любую из торговых компаний Издательского Дома «ЛАНЬ»
:
по России и зарубежью
«ЛАНЬТРЕЙД». 192029, СанктПетербург, ул. Крупской, тел (812) 4128578, 4121445, 4128582; тел./факс: (812) 4125493
email: trade@lanbook.ru; ICQ: в Москве ив Московской области
«ЛАНЬПРЕСС». 109263, Москва, я ул. Текстильщиков, д. тел (499) 1786585; email: в Краснодаре ив Краснодарском крае
«ЛАНЬЮГ». 350901, Краснодар, ул. Жлобы, д. тел (861) 2741035; email: ДЛЯ РОЗНИЧНЫХ ПОКУПАТЕЛЕЙ:
интернет(магазины
:
Издательство Лань Сова http://www.symplex.ru; «Ozon.ru»: http://www.ozon.ru
«Библион»: http://www.biblion.ru
Ïîäïèñàíî â ïå÷àòü 13.11.15.
Áóìàãà îôñåòíàÿ. Ãàðíèòóðà Øêîëüíàÿ. Ôîðìàò 70´100 1
/
16
Ïå÷àòü îôñåòíàÿ. Óñë. ï. ë. 48,10. Òèðàæ 100 ýêç.
Çàêàç ¹ Отпечатано в полном соответствии с качеством предоставленного оригиналмакета.
в ПАО Т Издательские Технологии, г. Москва, Волгоградский пр, д. 42, к. 5.