С.С. Марченков - Избранные главы дискретной математики (1124120), страница 25
Текст из файла (страница 25)
Îïðåäåëÿåì ôóíêöèèf1 (x1 , . . . , xn ) = j̄0 (f (x1 , . . . , xn )) è f2 (x1 , . . . , xn ), êîòîðàÿ ðàâíà 1, åñëèf ðàâíà 2, è ðàâíà 0 â îñòàëüíûõ ñëó÷àÿõ. Òîãäà ôóíêöèÿ f ïðåäñòàâèìà â âèäå ïðîèçâåäåíèÿ ôóíêöèé f1 (x1 , . . . , xn ) è f2 (x1 , . . . , xn ) + 1. Ýòîòïðîöåññ ïîâòîðÿåì â ñëó÷àå, êîãäà ôóíêöèÿ f ïðèíèìàåò ëèøü çíà÷åíèÿèç ìíîæåñòâà E4 , è ò.ä.(1)8. Êàæäàÿ èç äâóìåñòíûõ ôóíêöèé âìåñòå ñ ìíîæåñòâîì Pk îáðàçóåòïîëíóþ â Pk ñèñòåìó.
Ïîýòîìó àëãîðèòìîì äîñòàòî÷íî ïîðîæäàòü ëèøüâñå îäíîìåñòíûå ôóíêöèè èç çàìûêàíèÿ èññëåäóåìîé ñèñòåìû.2 29. Âûïèøåì âñå ìíîæåñòâà Gi äëÿ ñëó÷àÿ k = 2: {e1 , e2 } (äàëåå âöåëÿõ ñîêðàùåíèÿ çàïèñè ôóíêöèè e21 , e22 â ìíîæåñòâàõ Gi íå ïðèâîäèì),{0}, {1}, {0, 1}, {ē21 , ē22 }, {0, 1, ē21 , ē22 }, {x ∨ y}, {xy}, {x ∨ y, xy}, {0, x ∨ y},{0, xy}, {0, x ∨ y, xy}, {0, x ⊕ y}, {0, xy, xȳ, x̄y}, {0, x ∨ y, xy, x ⊕ y, xȳ, x̄y},4.118{1, x ∨ y}, {1, xy}, {1, x ∨ y, xy}, {1, x ⊕ y ⊕ 1}, {1, x ∨ y, x ∨ ȳ, x̄ ∨ y},{1, x ∨ y, xy, x ⊕ y ⊕ 1, x ∨ ȳ, x̄ ∨ y}, {0, 1, x ∨ y}, {0, 1, xy}, {0, 1, x ∨ y, xy},{0, 1, ē21 , ē22 , x ⊕ y, x ⊕ y ⊕ 1}.
Äîâîëüíî ëåãêî óáåäèòüñÿ, ÷òî ìíîæåñòâà{ē21 , ē22 }, {0, x ∨ y, xy, x ⊕ y, xȳ, x̄y}, {1, x ∨ y, xy, x ⊕ y ⊕ 1, x ∨ ȳ, x̄ ∨ y},{0, 1, x ∨ y, xy}, {0, 1, ē21 , ē22 , x ⊕ y, x ⊕ y ⊕ 1} îïðåäåëÿþò ñîîòâåòñòâåííî èçâåñòíûå êëàññû S, T0 , T1 , M, L. Îñòàâøàÿñÿ ÷àñòü äîêàçàòåëüñòâà îïðåäåëåíèå âñåõ îñòàëüíûõ êëàññîâ Fi0 è ïðîâåðêà èõ íà âêëþ÷åíèå ñðàâíèòåëüíî òðóäíàÿ çàäà÷à. Íàïðèìåð, ìîæíî ïðîâåðèòü, ÷òî ìíîæåñòâî {0, 1, ē21 , ē22 } îïðåäåëÿåò êëàññ âñåõ ôóíêöèé, ñóùåñòâåííî çàâèñÿùèõíå áîëåå ÷åì îò îäíîé ïåðåìåííûé (åñëè ôóíêöèÿ ñóùåñòâåííî çàâèñèòáîëåå ÷åì îò äâóõ ïåðåìåííûõ, òî èç íåå ïîäñòàíîâêîé êîíñòàíò 0,1 èôóíêöèé e21 , e22 ìîæíî ïîëó÷èòü ôóíêöèþ, ñóùåñòâåííî çàâèñÿùóþ ðîâíîîò äâóõ ïåðåìåííûõ).
Ýòîò êëàññ, êîíå÷íî, öåëèêîì ñîäåðæèòñÿ â êëàññåL ëèíåéíûõ ôóíêöèé. Ìíîæåñòâî {0, x ∨ y, xy} îïðåäåëÿåò (çàìêíóòûé)êëàññ âñåõ ìîíîòîííûõ ôóíêöèé, ñîõðàíÿþùèõ êîíñòàíòó 0, ò.å. êëàññM ∩ T0 . Ìíîæåñòâî {0, 1, x ∨ y} îïðåäåëÿåò êëàññ âñåõ äèçúþíêöèé, ò.å.êëàññ âñåõ ôóíêöèé, èìåþùèõ âèä a0 ∨ a1 x1 ∨ . . . ∨ an xn , ãäå êîýôôèöèåíòû a0 , a1 , .
. . , an íåçàâèñèìûì îáðàçîì ïðèíèìàþò çíà÷åíèÿ èç E2 .Ýòîò êëàññ, ðàçóìåååòñÿ, öåëèêîì ñîäåðæèòñÿ â êëàññå M ìîíîòîííûõôóíêöèé.10. Óêàçàíèå: âñÿêèé çàìêíóòûé êëàññ èç F , ñîäåðæàùèé áåñêîíå÷íîå÷èñëî ôóíêöèé fn , ñîâïàäàåò ñ êëàññîì F .11. Ñëåäóåò îáúåäèíèòü êîíñòðóêöèè èç òåîðåì 1.6 è 1.7. Îïðåäåëèìïîñëåäîâàòåëüíîñòü ôóíêöèé {f0 , f1 , . . .} àíàëîãè÷íî ïîñëåäîâàòåëüíîñòè èç òåîðåìû 1.6, íî ñ çàìåíîé 1 íà 3. Åñëè {n1 , n2 , .
. .} ïîñëåäîâàòåëüíîñòü ÷èñåë, áîëüøèõ 1, òî îïðåäåëèì F êàê çàìûêàíèå ñèñòåìûôóíêöèé, ñîñòîÿùåé èç ôóíêöèé f0 , f1 , . . . è gn1 , gn2 , . . .. Íåòðóäíî ïîêàçàòü, ÷òî êëàññ F ñîñòîèò èç ôóíêöèé f0 , f1 , . . . è ôóíêöèé, îáðàçîâàííûõñóïåðïîçèöèÿìè ôóíêöèé gn1 , gn2 , . . .. Ïðåäïîëîæèì, ÷òî êëàññ F èìååòáàçèñ B . Óñòàíàâëèâàåì, ÷òî áàçèñ B ñîäåðæèò õîòÿ áû îäíó ôóíêöèþfn , ãäå n 6= 0.
Òàê æå, êàê â òåîðåìå 1.6, óáåæäàåìñÿ, ÷òî â áàçèñ Bíå ìîãóò âõîäèòü äâå ðàçëè÷íûå ôóíêöèè fm , fn , ãäå m, n 6= 0. Åñëè âáàçèñ B âõîäèò òîëüêî îäíà ôóíêöèÿ fm , ãäå m 6= 0, òî, êàê íåòðóäíîïîêàçàòü, èç ôóíêöèé áàçèñà B íåâîçìîæíî ïîëó÷èòü ôóíêöèþ fn , ãäån > m. Òàêèì îáðàçîì, êëàññ F íå èìååò áàçèñà.
×òîáû çàâåðøèòü ðåøåíèå çàäà÷è, îñòàåòñÿ ïîêàçàòü, ÷òî ïðè n ∈/ {n1 , n2 , . . .} ôóíêöèÿ gn íåâõîäèò â êëàññ F .  ñàìîì äåëå, ôóíêöèÿ gn íå ìîæåò áûòü ðåàëèçîâàíà ôîðìóëîé âèäà fm (Φ1 , . . . , Φm ), ïîñêîëüêó ôóíêöèÿ fm íå ïðèíèìàåò119çíà÷åíèå 1. Òî, ÷òî ôóíêöèÿ gn íå ìîæåò áûòü ðåàëèçîâàíà ôîðìóëîéâèäà gni (Φ1 , . . . , Φni ), äîêàçûâàåòñÿ òàê æå, êàê â òåîðåìå 1.7.Ãëàâà 2.1.q2a1a1q1a2a2q4a1a2a1a22.q3 ïï. a)d) ìíîæåñòâî F åñòü ñîîòâåòñòâåííî {q2 , q4 }, {q4 }, {q3 }, {q3 }.a1 , a2q2q5a1 , a2a1a2q1a1 , a2a2q3a1q4a)q1a1 , a2q2a1 , a2q3a1 , a2q4a1 , a2q5a1 , a2b)a1 , a2q4a2q1a1a1c)120q2a2q3a1 , a2a1a2q1q2a1q3a1a2a2d)e) Ïî àíàëîãèè ñ ïï. c) è d).3. a) Äëÿ ïðîèçâîëüíûõ ñëîâ ā, b̄ â àëôàâèòå {a1 , a2 } ïîëàãàåì ā ∼ b̄â òîì è òîëüêî òîì ñëó÷àå, êîãäà ëèáî ā = b̄ = Λ, ëèáî ā 6= Λ è b̄ 6= Λ.Òîãäà ìíîæåñòâî âñåõ ñëîâ â àëôàâèòå {a1 , a2 } ðàçáèâàåòñÿ íà äâà êëàññàýêâèâàëåíòíîñòè, îäèí èç êîòîðûõ åñòü {Λ}.b) Äëÿ ïðîèçâîëüíûõ ñëîâ ā, b̄ ïîëàãàåì ā ∼ b̄ â òîì è òîëüêî òîì ñëó÷àå,êîãäà ëèáî ā = b̄ = Λ, ëèáî ā = b̄ = a1 , ëèáî ā, b̄ ñëîâà, îòëè÷íûå îò Λè a1 .
Ìíîæåñòâî âñåõ ñëîâ â àëôàâèòå {a1 , a2 } ïðè ýòîì ðàçáèâàåòñÿ íàòðè êëàññà ýêâèâàëåíòíîñòè, îäèí èç êîòîðûõ åñòü {a1 }.c) Äëÿ ïðîèçâîëüíûõ ñëîâ ā, b̄ ïîëàãàåì ā ∼ b̄ â òîì è òîëüêî òîì ñëó÷àå,êîãäà ëèáî ā = b̄ = Λ, ëèáî ā, b̄ áóêâû àëôàâèòà {a1 , a2 } (âîçìîæíî,ðàçëè÷íûå), ëèáî ā, b̄ ñëîâà äëèíû, íå ìåíüøåé äâóõ.
Ìíîæåñòâî âñåõñëîâ â àëôàâèòå {a1 , a2 } ðàçáèâàåòñÿ íà òðè êëàññà ýêâèâàëåíòíîñòè, äâàèç êîòîðûõ ñóòü {Λ} è {a1 , a2 }. Èõ îáúåäèíåíèå äà¼ò èñêîìîå ìíîæåñòâî{Λ, a1 , a2 }.d) Äëÿ ïðîèçâîëüíûõ ñëîâ ā, b̄ ïîëàãàåì ā ∼ b̄ â òîì è òîëüêî òîì ñëó÷àå,êîãäà ëèáî ā, b̄ ñóòü ñëîâà âèäà an1 (âîçìîæíî, ðàçëè÷íûå), ëèáî ā, b̄ ñóòüñëîâà âèäà an1 a2 (òàêæå äîïóñêàþòñÿ ðàçëè÷íûå çíà÷åíèÿ ïàðàìåòðà n),ëèáî ā, b̄ íå èìåþò âèäà an1 èëè an1 a2 . Ìíîæåñòâî âñåõ ñëîâ â àëôàâèòå{a1 , a2 } ðàçáèâàåòñÿ íà òðè êëàññà ýêâèâàëåíòíñîòè, îäèí èç êîòîðûõåñòü èñêîìîå ìíîæåñòâî {an1 a2 : n ≥ 0}.4. Ïðîùå âñåãî îïðåäåëèòü ýêâèâàëåíòíîñòü òàê, ÷òîáû êëàññû ýêâèâàëåíòíîñòè ñîñòîÿëè èç âñåõ ñëîâ äëèíû ñîîòâåòñòâåííî kn, kn + 1, . . .
,kn + n − 1 (k = 0, 1, . . .).5. Ýòó çàäà÷ó ëó÷øå ðåøàòü ñ èñïîëüçîâàíèåì íåäåòåðìèíèðîâàííûõ àâòîìàòîâ ëèáî ðåãóëÿðíûõ ìíîæåñòâ è òåîðåìû Êëèíè.  ïîñëåäíåì ñëó÷àå ñëåäóåò âîñïîëüçîâàòüñÿ îïåðàöèåé îáðàùåíèÿ. Íåòðóäíî âèäåòü, äëÿ âñÿêîé ëåâîèíâàðèàíòíîé ýêâèâàëåíòíîñòè êîíå÷íîãî èíäåêñà ∼l ìîæíî îïðåäåëèòü àíàëîãè÷íóþ ïðîâîèíâàðèàíòíóþ ýêâèâàëåíòíîñòü êîíå÷íîãî èíäåêñà ∼r , ïðè÷¼ì ïðîèçâîëüíûå ñëîâà ā, b̄ áóäóò ýêâèâàëåíòíû â ñìûñëå îòíîøåíèÿ ∼l â òîì è òîëüêî òîì ñëó÷àå, êîãäà121ýêâèâàëåíòíû â ñìûñëå îòíîøåíèÿ ∼r îáðàùåíèÿ ñëîâ ā, b̄.6. d) Ìîæíî âçÿòü òðè ìíîæåñòâà: ¾÷¼òíàÿ äëèíà¿, ¾íà÷àëî a1 ¿, ¾÷åðåäîâàíèå a1 è a2 ¿.7.
Ïóñòü A = (A, Q, f, I, F ) èñòî÷íèê ñ ìíîæåñòâîì íà÷àëüíûõ ñîñòîÿíèé I . Åñëè I ñîñòîèò èç íåñêîëüêèõ ñîñòîÿíèé, òî D(A) åñòü îáúåäèíåíèå âñåõ ìíîæåñòâ, äîïóñòèìûõ àâòîìàòàìè (A, Q, f, qj , F ), ãäå qj ∈ I .Ïîýòîìó äàëåå ìîæíî ðàññìàòðèâàòü èñòî÷íèêè, èìåþùèå òîëüêî îäíî íà÷àëüíîå ñîñòîÿíèå. Ïóñòü A0 = (A, Q, f, q1 , F ) òàêîé èñòî÷íèê.Ââåä¼ì íîâîå ñîñòîÿíèå q 0 , íå ïðèíàäëåæàùåå ìíîæåñòâó Q. Îïðåäåëèìíåäåòåðìèíèðîâàííûé àâòîìàò A00 = (A, Q ∪ {q 0 }, f 0 , q1 , F ), ãäå ôóíêöèÿ ïåðåõîäîâ f 0 ïîëó÷àåòñÿ èç ôóíêöèè f ñëåäóþùèì îáðàçîì. Åñëèai ∈ A, qj ∈ Q è f (ai , qj ) îïðåäåëåíî, òî ïóñòü f 0 (ai , qj ) = f (ai , qj ).  ïðîòèâíîì ñëó÷àå ïîëàãàåì f 0 (ai , qj ) = q 0 .
Äëÿ âñåõ áóêâ ai ïîëàãàåì òàêæåf 0 (ai , q 0 ) = q 0 . Íåòðóäíî âèäåòü, ÷òî äëÿ íåäåòåðìèíèðîâàííîãî àâòîìàòàA00 ñïðàâåäëèâî ðàâåíñòâî D(A00 ) = D(A).∗∗8. (a1 ∪ a2 ) · a2 · a2 · a1 · (a1 ∪ a2 ) .9. Îäèí ðàç. Åñëè ñëîâî ā ñîñòîèò èç n áóêâ, òî ñíà÷àëà ïîëó÷àåììíîæåñòâî âñåõ ñëîâ â àëôàâèòå A, èìåþùèõ äëèíó áîëüøå n:(a1 ∪ . . .
∪ ak ) · . . . · (a1 ∪ . . . ∪ ak ) ·(a1 ∪ . . . ∪ ak )∗ .{z}|n+1Çàòåì ê ýòîìó ìíîæåñòâó ñ ïîìîùüþ îïåðàöèè îáúåäèíåíèÿ äîáàâëÿåìâñå ñëîâà äëèíû, íå ïðåâîñõîäÿùåé n, îòëè÷íûå îò ā.10. a) Ïóñòü êîíå÷íîå ìíîæåñòâî ñîñòîèò èç ñëîâ ā1 , . . . , ān è, íàïðèìåð, āi = ai1 . . . ais . Òîãäà ðåãóëÿðíîå âûðàæåíèå ai1 · .
. . · ais (ñêîáêèîïóñêàåì) îïðåäåëÿåò ðåãóëÿðíîå ìíîæåñòâî, ñîñòîÿùåå èç îäíîãî ñëîâàāi . Äàëåå ñ ïîìîùüþ îïåðàöèè îáúåäèíåíèÿ îáðàçóåì ðåãóëÿðíîå âûðàæåíèå, êîòîðîå îïðåäåëÿåò ìíîæåñòâî {ā1 , . . . ān }.b) Ïóñòü X = {a1 , a2 }∗ \ {ā1 , . . . , ān } è m ìàêñèìóì èç äëèí ñëîâā1 , . . . , ān . Ñíà÷àëà îáðàçóåì ðåãóëÿðíîå âûðàæåíèå(a1 ∪ a2 ) · . . . · (a1 ∪ a2 ) ·(a1 ∪ a2 )∗ ,|{z}m+1êîòîðîå îïðåäåëÿåò ìíîæåñòâî âñåõ ñëîâ â àëôàâèòå {a1 , a2 }, èìåþùèõäëèíó áîëüøå m. Çàòåì, ïîëüçóÿñü ï. a) çàäà÷è, ñòðîèì ðåãóëÿðíîå âûðàæåíèå, êîòîðîå îïðåäåëÿåò ìíîæåñòâî âñåõ ñëîâ äëèíû, íå ïðåâîñõîäÿùåé m, è îòëè÷íûõ îò ñëîâ ā1 , .
. . , an . Íà ïîñëåäíåì ýòàïå ñ ïîìîùüþçíàêà ∪ ñîåäèíÿåì ïîëó÷åííûå ðåãóëÿðíûå âûðàæåíèÿ.122c) Èñêîìîå ìíîæåñòâî îïðåäåëÿåòñÿ ðåãóëÿðíûì âûðàæåíèåì (ā1 ∪ . . . ∪ān )∗ , åñëè â ýòî ìíîæåñòâî âêëþ÷èòü ïóñòîå ñëîâî.  ïðîòèâíîì ñëó÷àåñëåäóåò âçÿòü ðåãóëÿðíîå âûðàæåíèå(ā1 ∪ . . . ∪ ān ) · (ā1 ∪ . . . ∪ ān )∗ .d) Åñëè ā = Λ, òî èñêîìîå ðåãóëÿðíîå âûðàæåíèå åñòü (a1 ∪ a2 )∗ . Ïóñòüā 6= Λ è ā = ai1 . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
