С.С. Марченков - Избранные главы дискретной математики (1124120)
Текст из файла
ÌÎÑÊÎÂÑÊÈÉ ÃÎÑÓÄÀÐÑÒÂÅÍÍÛÉ ÓÍÈÂÅÐÑÈÒÅÒèìåíè Ì. Â. ËÎÌÎÍÎÑÎÂÀÔàêóëüòåò âû÷èñëèòåëüíîé ìàòåìàòèêè è êèáåðíåòèêèÑ. Ñ. Ìàð÷åíêîâÈÇÁÐÀÍÍÛÅ ÃËÀÂÛ ÄÈÑÊÐÅÒÍÎÉ ÌÀÒÅÌÀÒÈÊÈÓ÷åáíîå ïîñîáèåÌîñêâà 2015ÓÄÊ 519.71(075.8)ÁÁÊÏå÷àòàåòñÿ ïî ðåøåíèþ ðåäàêöèîííî-èçäàòåëüñêîãî ñîâåòàôàêóëüòåòà Âû÷èñëèòåëüíîé ìàòåìàòèêè è êèáåðíåòèêèÌÃÓ èìåíè Ì.Â.
ËîìîíîñîâàÐåöåíçåíòû:, ä.ô.-ì.í., ïðîôåññîð;, ê.ô.-ì.í., äîöåíòÂ.À. ÇàõàðîâÄ.Ñ. ÐîìàíîâÌàð÷åíêîâ Ñ.Ñ.Ó÷åáíîå ïîñîáèå. Ì.: Èçäàòåëüñêèé îòäåë ôàêóëüòåòà ÂÌèÊ ÌÃÓ èì. Ì.Â. Ëîìîíîñîâà(ëèöåíçèÿ ÈÄ 05899 îò 24.09.2001); ÌÀÊÑ Ïðåññ, 2015. 134 ñ.ISBNISBNÈçáðàííûå ãëàâû äèñêðåòíîé ìàòåìàòèêè:Ïîñîáèå íàïèñàíî íà îñíîâå ïîòîêîâîãî êóðñà ¾Äîïîëíèòåëüíûå ãëàâû äèñêðåòíîé ìàòåìàòèêè¿, êîòîðûé àâòîð íà ïðîòÿæåíèè ðÿäà ëåò ÷èòàåò íà ôàêóëüòåòå âû÷èñëèòåëüíîéìàòåìàòèêè è êèáåðíåòèêè ÌÃÓ. Ïîñîáèå ñîñòîèò èõ ÷åòûðåõ ãëàâ.  ãëàâå 1 ¾Ôóíêöèèìíîãîçíà÷íîé ëîãèêè¿ äàþòñÿ ïåðâîíà÷àëüíûå ñâåäåíèÿ ïî ôóíêöèÿì ìíîãîçíà÷íîé ëîãèêè.
×àñòü èç íèõ èñïîëüçóåòñÿ â ãëàâàõ 2 è 3. Ãëàâà 2 ¾Êîíå÷íûå àâòîìàòû-ðàñïîçíàâàòåëè¿ïîñâÿùåíà îïèñàíèþ êîíå÷íî-àâòîìàòíûõ ìíîæåñòâ â òåðìèíàõ êîíå÷íûõ àâòîìàòîâ, ñ èñïîëüçîâàíèåì ïðàâîèíâàðèàíòíîãî îòíîøåíèÿ ýêâèâàëåíòíîñòè è íà îñíîâå ðåãóëÿðíûõ âûðàæåíèé.  ãëàâå 3 ¾Êîíå÷íûå àâòîìàòû-ïðåîáðàçîâàòåëè¿ ðàññìàòðèâàåòñÿ êëàññ êîíå÷íîàâòîìàòíûõ ôóíêöèé, îïðåäåëåííûõ íà áåñêîíå÷íûõ ïîñëåäîâàòåëüíîñòÿõ. Äîêàçûâàåòñÿêîíå÷íàÿ ïîðîæäàåìîñòü ýòîãî êëàññà îòíîñèòåëüíî îïåðàöèé ñóïåðïîçèöèè è îáðàòíîé ñâÿçè è íåâîçìîæíîñòü îáîéòèñü òîëüêî îïåðàöèåé ñóïåðïîçèöèè.  ãëàâå 4 ¾Ìàøèíû Òüþðèíãà è âû÷èñëèìûå ôóíêöèè¿ îïðåäåëÿþòñÿ ìàøèíû Òüþðèíãà è ôóíêöèè, âû÷èñëèìûå íàìàøèíàõ Òüþðèíãà.
Äîêàçûâàåòñÿ ñîâïàäåíèå äàííîãî êëàññà ôóíêöèé ñ êëàññîì ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé. Ââîäÿòñÿ ïîíÿòèÿ P-ñâîäèìîñòè è NP-ïîëíîòû. Óñòàíàâëèâàåòñÿñóùåñòâàíèå NP-ïîëíûõ ïðîáëåì. Êàæäûé ïàðàãðàô ñíàáæåí çàäà÷àìè è óïðàæíåíèÿìè.Äëÿ ñòóäåíòîâ, àñïèðàíòîâ è íàó÷íûõ ñîòðóäíèêîâ, ñïåöèàëèçèðóþùèõñÿ â îáëàñòè äèñêðåòíîé ìàòåìàòèêè è êèáåðíåòèêè.ÑÎÄÅÐÆÀÍÈÅÏðåäèñëîâèå .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.......................... 7Îñíîâíûå ïîíÿòèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7Ñòàíäàðòíûå ïîëíûå ñèñòåìû . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . 11Àëãîðèòì ðàñïîçíàâàíèÿ ôóíêöèîíàëüíîé ïîëíîòû . . . . . . . . . 16Òåîðåìà Êóçíåöîâà î ôóíêöèîíàëüíîé ïîëíîòå . . . . . . . . . . . . . .19Çàìêíóòûå êëàññû, íå èìåþùèå êîíå÷íûõ áàçèñîâ . . . . . . . . . . 22Ãëàâà 1. Ôóíêöèè ìíîãîçíà÷íîé ëîãèêè1.2.3.4.5.Ãëàâà 2. Êîíå÷íûå àâòîìàòû-ðàñïîçíàâàòåëè . . . . . . . . . . . . . . .
. . . . 25 1. Êîíå÷íûé àâòîìàò áåç âûõîäà. Êîíå÷íî-àâòîìàòíûåìíîæåñòâà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25 2. Ïðàâîèíâàðèàíòíàÿ ýêâèâàëåíòíîñòü. Òåîðåòèêî-ìíîæåñòâåííûå îïåðàöèè íàä êîíå÷íî-àâòîìàòíûìè ìíîæåñòâàìè . . . . . .29 3. Íåäåòåðìèíèðîâàííûå àâòîìàòû . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . 34 4. Îïåðàöèè ïðîèçâåäåíèÿ è èòåðàöèè . . . . . . . . . . . . . . . . . . . . . . . . . 36 5. Ðåãóëÿðíûå ìíîæåñòâà. Òåîðåìà Êëèíè . . . . . . . . . . . . . . . . . . . . . 40Ãëàâà 3. Êîíå÷íûå àâòîìàòû-ïðåîáðàçîâàòåëè . . . . . . . . . . . . . . . . . .441.2.3.4.5.Êîíå÷íûé àâòîìàò ñ âûõîäîì. Òåîðåìà Ìóðà . . . . . . . . .
. . . . . . 44Îñòàòî÷íûå ôóíêöèè. Âåñ ôóíêöèè . . . . . . . . . . . . . . . . . . . . . . . . . 48Êîíå÷íûå àâòîìàòû íà ñâåðõñëîâàõ . . . . . . . . . . . . . . . . . . . . . . . . . .51Îïåðàöèè ñóïåðïîçèöèè è ââåäåíèÿ îáðàòíîé ñâÿçè . . . . .
. . . . 56Êîíå÷íàÿ ïîðîæäàåìîñòü êëàññà êîíå÷íî-àâòîìàòíûõôóíêöèé. Íåñâîäèìîñòü îïåðàöèè ââåäåíèÿ îáðàòíîé ñâÿçèê îïåðàöèè ñóïåðïîçèöèè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60. . . . . . . . . 65Ìàøèíà Òüþðèíãà . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65Êîìïîçèöèÿ è èòåðàöèÿ ìàøèí Òüþðèíãà . . . . . . . . . . . . . . . . . . . 70Ìîäåëèðîâàíèå ìàøèí Òüþðèíãà . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74Îïåðàöèè ñóïåðïîçèöèè, ïðèìèòèâíîé ðåêóðñèèè ìèíèìèçàöèè . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77Óíèâåðñàëüíàÿ ìàøèíà Òüþðèíãà . . . . . . . . . . . . . . . . . . . . . . . . . . . 83Êëàññû P è NP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.89Ãëàâà 4. Ìàøèíû Òüþðèíãà è âû÷èñëèìûå ôóíêöèè1.2.3.4. 5. 6.7. NP-ïîëíîòà. Òåîðåìà Êóêà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 948. Ïðèìèòèâíî ðåêóðñèâíûå ôóíêöèè . . . . . . . . . . . . . . . . . . . . . . . . . 1029. Êëàññ ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé . . . . . . . . . . . . . . . . . . . . . 10810. ×àñòè÷íàÿ ðåêóðñèâíîñòü âû÷èñëèìûõ ôóíêöèé.Ôîðìóëà Êëèíè . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114Îòâåòû, ðåøåíèÿ, óêàçàíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117Ñïèñîê ëèòåðàòóðû. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . 1324ÏÐÅÄÈÑËÎÂÈÅ êóðñàõ äèñêðåòíîé ìàòåìàòèêè, ÷èòàåìûõ â ðîññèéñêèõ óíèâåðñèòåòàõ (à òàêæå â çíà÷èòåëüíîì ÷àñòè òåõíè÷åñêèõ âóçîâ), ñëîæèëñÿ îïðåäåëåííûé êðóã îáÿçàòåëüíûõ ðàçäåëîâ, áåç êîòîðûõ èçëîæåíèå äèñêðåòíîéìàòåìàòèêè íå ìîæåò ñ÷èòàòüñÿ ïîëíîöåííûì. Ê òàêèì ðàçäåëàì ñëåäóåò â ïåðâóþ î÷åðåäü îòíåñòè ðàçäåëû, ïîñâÿùåííûå áóëåâûì ôóíêöèÿìè èõ îáîáùåíèÿì ôóíêöèÿì ìíîãîçíà÷íîé ëîãèêè, êîíå÷íûì àâòîìàòàì, ìàøèíàì Òüþðèíãà è âû÷èñëèìûì ôóíêöèÿì.
 ðàçëè÷íûõ êóðñàõ äèñêðåòíîé ìàòåìàòèêè äàííûå ðàçäåëû ìîãóò áûòü ïðåäñòàâëåíûïî-ðàçíîìó: ýòî êàñàåòñÿ íå òîëüêî îáúåìà ìàòåðèàëà, âêëþ÷åííîãî âðàçäåëû, íî è ñòåïåíè ïîäðîáíîñòè è ïðîðàáîòêè âõîäÿùèõ â íèõ òåì. Ìîñêîâñêîì ãîñóäàðñòâåííîì óíèâåðñèòåòå îáÿçàòåëüíûé êóðñ äèñêðåòíîé ìàòåìàòèêè âïåðâûå áûë ïðî÷èòàí Ñ.Â.
ßáëîíñêèì íà ôàêóëüòåòå âû÷èñëèòåëüíîé ìàòåìàòèêè è êèáåðíåòèêè â 1971 ãîäó.  1979 ã. ïîÿâèëîñü ïåðâîå èçäàíèå ó÷åáíèêà Ñ.Â. ßáëîíñêîãî ¾Ââåäåíèå â äèñêðåòíóþ ìàòåìàòèêó¿ [?], à äâóìÿ ãîäàìè ðàíåå ïåðâîå èçäàíèå ñáîðíèêà¾Çàäà÷è è óïðàæíåíèÿ ïî äèñêðåòíîé ìàòåìàòèêå¿ [?] Ã.Ï. Ãàâðèëîâà èÀ.À. Ñàïîæåíêî. Âïîñëåäñòâèè ýòè êíèãè íåñêîëüêî ðàç ïåðåèçäàâàëèñüè ïåðåâîäèëèñü íà äðóãèå ÿçûêè. Íå áóäåò ïðåóâåëè÷åíèåì ñêàçàòü, ÷òîîíè âíåñëè çíà÷èòåëüíûé âêëàä â ñòàíîâëåíèå è ðàçâèòèå äèñêðåòíîéìàòåìàòèêè â íàøåé ñòðàíå.Íà ôàêóëüòåòå âû÷èñëèòåëüíîé ìàòåìàòèêè è êèáåðíåòèêè ÌÃÓ êóðñäèñêðåòíîé ìàòåìàòèêè ðàçáèò íà äâå ÷àñòè: ïåðâàÿ áàçîâàÿ ÷èòàåòñÿ âñåì ïîòîêàì ïåðâîãî êóðñà; âòîðàÿ ¾Äîïîëíèòåëüíûå ãëàâûäèñêðåòíîé ìàòåìàòèêè¿ â ïÿòîì ñåìåñòðå íà âòîðîì ïîòîêå. È åñëè áàçîâàÿ ÷àñòü íå ïðåòåðïåëà ñóùåñòâåííûõ èçìåíåíèé ïî ñðàâíåíèþñ êóðñîì (è ó÷åáíèêîì) Ñ.Â.
ßáëîíñêîãî (ñîâðåìåííîå èçëîæåíèå ýòîé÷àñòè èìååòñÿ â êíèãå [?] Â.Á. Àëåêñååâà), òî âî âòîðîé ÷àñòè ïðîèçîøëè çíà÷èòåëüíûå èçìåíåíèÿ. Ïîÿâèëàñü ïîòðåáíîñòü â èçëîæåíèè ýòîé÷àñòè â âèäå îòäåëüíîãî ó÷åáíîãî ïîñîáèÿ. íàñòîÿùåì ó÷åáíîì ïîñîáèè ïðåäñòàâëåíû òðè ðàçäåëà äèñêðåòíîéìàòåìàòèêè: ôóíêöèè ìíîãîçíà÷íîé ëîãèêè, êîíå÷íûå àâòîìàòû, ìàøèíû Òüþðèíãà è âû÷èñëèìûå ôóíêöèè.
Ïîñëåäíèå äâà ðàçäåëà ñîñòàâëÿþò êóðñ ¾Äîïîëíèòåëüíûå ãëàâû äèñêðåòíîé ìàòåìàòèêè¿, êîòîðûéàâòîð íà ïðîòÿæåíèè ðÿäà ëåò ÷èòàåò íà ôàêóëüòåòå âû÷èñëèòåëüíîé ìàòåìàòèêè è êèáåðíåòèêè. Ðàçäåë ¾Ôóíêöèè ìíîãîçíà÷íîé ëîãèêè¿ âêëþ÷åí â ïîñîáèå, ÷òîáû îáåñïå÷èòü ïîëíîòó è íåçàâèñèìîñòü äîêàçàòåëüñòâ5íåêîòîðûõ óòâåðæäåíèé äëÿ êîíå÷íûõ àâòîìàòîâ.  ïîñîáèå íå âêëþ÷åíà ãëàâà ïî áóëåâûì ôóíêöèÿì, ïîñêîëüêó â íàñòîÿùåå âðåìÿ èìååòñÿíåñêîëüêî äîñòóïíûõ êíèã (ñì., íàïðèìåð, [?, ?, ?]), â êîòîðûõ ýòà òåìàèçëîæåíà äîñòàòî÷íî ïîäðîáíî.Ðàçäåë ¾Êîíå÷íûå àâòîìàòû¿ â ïîñîáèè ðàçáèò íà äâå ãëàâû: ¾Êîíå÷íûå àâòîìàòû-ðàñïîçíàâàòåëè¿ è ¾Êîíå÷íûå àâòîìàòû-ïðåîáðàçîâàòåëè¿. ïåðâîé èç ýòèõ ãëàâ ñîäåðæèòñÿ ìàòåðèàë, êîòîðûé ñðàâíèòåëüíî ðåäêî âñòðå÷àåòñÿ â ó÷åáíèêàõ ïî äèñêðåòíîé ìàòåìàòèêå.
Çäåñü ñîáðàíûðåçóëüòàòû, êàñàþùèåñÿ ðàçëè÷íûõ îïðåäåëåíèé êîíå÷íî-àâòîìàòíûõìíîæåñòâ: ñîáñòâåííî ÷åðåç êîíå÷íûå àâòîìàòû, ñ ïîìîùüþ ïðàâîèíâàðèàíòíîãî îòíîøåíèÿ ýêâèâàëåíòíîñòè è ÷åðåç ðåãóëÿðíûå âûðàæåíèÿÊëèíè. Ïðèâåäåíû òåîðåìû, ïîêàçûâàþùèå ýêâèâàëåíòíîñòü âñåõ îïðåäåëåíèé.Äðóãàÿ ãëàâà, ïîñâÿùåííàÿ êîíå÷íûì àâòîìàòàì, ñîäåðæèò áîëåå òðàäèöèîííûé ìàòåðèàë, êîòîðûé íà ïðîòÿæåíèè ìíîãèõ ëåò âõîäèò â óíèâåðñèòåòñêèå êóðñû äèñêðåòíîé ìàòåìàòèêè. Åäèíñòâåííàÿ îñîáåííîñòüçäåñü ñîñòîèò â òîì, ÷òî â ïîñîáèè äîâîëüíî ïîäðîáíî ðàññìîòðåíà ñâÿçüìåæäó êîíå÷íî-àâòîìàòíûìè ôóíêöèÿìè, îïðåäåëåííûìè íàä êîíå÷íûìè ñëîâà è íàä áåñêîíå÷íûìè ïîñëåäîâàòåëüíîñòÿìè (ñâåðõñëîâàìè).Áîëüøàÿ ÷àñòü ãëàâû ¾Ìàøèíû Òüþðèíãà è âû÷èñëèìûå ôóíêöèè¿ñîñòàâëåíà èç ðåçóëüòàòîâ, ïîñòîÿííî âõîäÿùèõ â ïîäîáíûå êóðñû äèñêðåòíîé ìàòåìàòèêè.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
