С.С. Марченков - Избранные главы дискретной математики (1124120), страница 5
Текст из файла (страница 5)
. , yp ), . . . , epp (y1 , . . . , yp )) = f (y1 , . . . , yp )ñëåäóåò, ÷òî f ∈ G. Ëåììà äîêàçàíà.Çàìêíóòûé êëàññ R ⊆ Pk íàçûâàåòñÿâ Pk , åñëè R 6= Pkè [R ∪ {f }] = Pk äëÿ ëþáîé ôóíêöèè f èç ìíîæåñòâà Pk \ R.ïðåäïîëíûìÄëÿ ëþáîãî k > 2 ÷èñëî ïðåäïîëíûõ â Pk êëàññîâ êîíå÷íî; ïðîèçâîëüíàÿ ñèñòåìà ôóíêöèé èç Pk ïîëíà â Pk òîãäà è òîëüêî òîãäà, êîãäà îíà öåëèêîì íå ñîäåðæèòñÿ íè â îäíîì èç ïðåäïîëíûõêëàññîâ.Òåîðåìà 1.5.20Îáðàçóåì ñèñòåìó {G1 , .
. . , Gm } âñåõ ñîáñòâåííûõ(2)ïîäìíîæåñòâ ìíîæåñòâà Pk , êîòîðûå îáëàäàþò ñëåäóþùèìè äâóìÿ ñâîéñòâàìè.1. Êàæäîå ìíîæåñòâî Gi ñîäåðæèò ôóíêöèè e21 , e22 .2. [Gi ](2) = Gi (i = 1, 2, . . . , m).Äîêàçàòåëüñòâî.Ïóñòü Fi0 ìíîæåñòâî âñåõ ôóíêöèé èç Pk , êîòîðûå ñîõðàíÿþò ìíîæåñòâî ôóíêöèé Gi . Â ñèëó ëåìì 1.1, 1.2 ìíîæåñòâî Fi0 ÿâëÿåòñÿ çàìêíóòûì êëàññîì è âûïîëíÿåòñÿ ñîîòíîøåíèå (Fi0 )(2) = Gi .
Âûäåëèì âñåìåéñòâå {F10 , . . . , Fm0 } âñå ìàêñèìàëüíûå ïî âêëþ÷åíèþ êëàññû. Îáîçíà÷èì èõ F1 , . . . , Fl . Ïîëîæèì F = {F1 , . . . , Fl }. Ïîêàæåì, ÷òî F åñòüèñêîìîå ñåìåéñòâî ïðåäïîëíûõ êëàññîâ.Ïðåæäå âñåãî, èç ïîñòðîåíèÿ ñëåäóåò, ÷òî êàæäûé êëàññ Fi îòëè÷åí îòPk . Ïóñòü S ïðîèçâîëüíîå ìíîæåñòâî ôóíêöèé èç Pk .
Åñëè S öåëèêîìñîäåðæèòñÿ â íåêîòîðîì êëàññå ñåìåéñòâà F , òî íåïîëíîòà S ñëåäóåò èççàìêíóòîñòè êëàññîâ ñåìåéñòâà F è íåñîâïàäåíèè èõ ñ Pk .Ïðåäïîëîæèì, ÷òî ìíîæåñòâî S öåëèêîì íå âõîäèò íè â îäèí èç êëàññîâ ñåìåéñòâà F . Òîãäà, êîíå÷íî, è çàìûêàíèå S íå áóäåò öåëèêîì âõîäèòü íè â îäèí èç êëàññîâ ñåìåéñòâà F . Ïîñêîëüêó íàñ èíòåðåñóåò ïîëíîòà (íåïîëíîòà) ìíîæåñòâà S , ìîæíî ñ÷èòàòü, ÷òî S çàìêíóòûé êëàññ.Íåòðóäíî âèäåòü, ÷òî ìíîæåñòâî S ∪ {e21 , e22 } ïîëíî èëè íåïîëíî â êëàññåPk îäíîâðåìåííî ñ ïîëíîòîé èëè íåïîëíîòîé êëàññà S .
Ïîýòîìó äàëååìîæíî ïðåäïîëàãàòü, ÷òî êëàññ S ñîäåðæèò ôóíêöèè e21 , e22 .Ïîëîæèì G = S (2) . Òîãäà ìíîæåñòâî G ñîäåðæèò ôóíêöèè e21 , e22 è óäîâëåòâîðÿåò óñëîâèþ [G](2) = G (ïîñêîëüêó çàìêíóòûé êëàññ S , î÷åâèäíî,(2)ñîõðàíÿåò ìíîæåñòâî ôóíêöèé G). Ïðåäïîëàãàÿ, ÷òî G 6= Pk , îáîçíà÷èì ÷åðåç ìíîæåñòâî Fi0 âñåõ ôóíêöèé, ñîõðàíÿþùèõ G. Òîãäà, êîíå÷íî,âûïîëíÿåòñÿ âêëþ÷åíèå S ⊆ Fi0 .
Îäíàêî êëàññ Fi0 öåëèêîì ñîäåðæèòñÿâ íåêîòîðîì ìàêñèìàëüíîì êëàññå Fj . Çíà÷èò, ïðèõîäèì ê âêëþ÷åíèþS ⊆ Fj , ÷òî íåâîçìîæíî ïî ïðåäïîëîæåíèþ. Ñëåäîâàòåëüíî, êëàññ Sñîâïàäàåò ñ Pk .Îñòàåòñÿ ïîêàçàòü, ÷òî êàæäûé èç êëàññîâ F1 , . . . , Fl ïðåäïîëîí â Pk .Îäíàêî åñëè, íàïðèìåð, f ∈/ Fi , òî ñèñòåìà ôóíêöèé Fi ∪ {f } íå ñîäåðæèòñÿ öåëèêîì íè â îäíîì èç êëàññîâ ñåìåéñòâà F (èñïîëüçóåì ñâîéñòâîìàêñèìàëüíîñòè êëàññîâ ñåìåéñòâà F ). Ñëåäîâàòåëüíî, ïî äîêàçàííîìóñèñòåìà Fi ∪ {f } ïîëíà â êëàññå Pk .ÓÏÐÀÆÍÅÍÈß219.Âûïèñàòü âñå äåòàëè äîêàçàòåëüñòâà òåîðåìû 1.5 äëÿ ñëó÷àÿ k = 2. 5.
Çàìêíóòûå êëàññû, íå èìåþùèå êîíå÷íûõ áàçèñîâÊàê óñòàíîâèë Ý. Ïîñò [?, ?] (ñì. òàêæå [?]), âñÿêèé çàìêíóòûé êëàññáóëåâûõ ôóíêöèé èìååò êîíå÷íûé áàçèñ. Îäíàêî ïðè ëþáîì k > 3 â Pkñóùåñòâóþò çàêíóòûå êëàññû, êîòîðûå íå èìåþò áàçèñîâ âîîáùå, à òàêæå çàìêíóòûå êëàññû ñî ñ÷åòíûìè áàçèñàìè. Ýòè ðåçóëüòàòû ïîëó÷åíûÞ.È. ßíîâûì è À.À. Ìó÷íèêîì [?].Äëÿ ëþáîãî k > 3 â Pk ñóùåñòâóåò çàìêíóòûé êëàññ, íå èìåþùèé áàçèñà.Òåîðåìà 1.6(Þ.È.
ßíîâ).Îïðåäåëèì â Pk ïîñëåäîâàòåëüíîñòü ôóíêöèé f0 ,f1 , . . .: ïóñòü f0 (x1 ) = 0 è ïðè n > 1Äîêàçàòåëüñòâî.fn (x1 , . . . , xn ) =1, åñëè x1 = . . . = xn = 2,0 â îñòàëüíûõ ñëó÷àÿõ.Ïîëîæèì F = [{f0 , f1 , . . .}]. Îòìåòèì äâà ñâîéñòâà ôóíêöèé fn .1. Åñëè n > 1 è íàáîð (i1 , . .
. , in ) ñîäåðæèò m ðàçëè÷íûõ çíà÷åíèé, òîôîðìóëà fn (xi1 , . . . , xin ) ðåàëèçóåò ôóíêöèþ fm .2. Ëþáàÿ ñóïåðïîçèöèÿ âèäà fn (. . . , fm (. . .), . . .) ðåàëèçóåò ôóíêöèþ,òîæäåñòâåííî ðàâíóþ íóëþ (ïîñêîëüêó ôóíêöèÿ fm íå ïðèíèìàåò çíà÷åíèÿ 2).Èç ýòèõ ñâîéñòâ ñëåäóåò, ÷òî êëàññ F ïîìèìî ôóíêöèé f1 , f2 , . . . ñîäåðæèò òîëüêî òîæäåñòâåííî íóëåâûå ôóíêöèè îò ëþáîãî ÷èñëà ïåðåìåííûõ.Äîêàæåì, ÷òî êëàññ F íå èìååò áàçèñà. Ïóñòü, íàïðîòèâ, êëàññ F èìååò áàçèñ B . Òîãäà ïî ñâîéñòâó 1 â áàçèñ B íå ìîãóò âõîäèòü äâå ôóíêöèèfm , fn , ãäå 1 6 m < n. Åñëè æå áàçèñ B ñîäåðæèò òîëüêî îäíó ôóíêöèþfm , ãäå m 6= 0, òî â ñèëó ñâîéñòâà 2 èç íåå (è, âîçìîæíî, ôóíêöèè f0 ,åñëè f0 ∈ B ) íåëüçÿ ïîëó÷èòü ôóíêöèþ fn , ãäå n > m. Ïðîòèâîðå÷èåïîêàçûâàåò, ÷òî êëàññ F íå èìååò áàçèñà. Òåîðåìà äîêàçàíà.Äëÿ ëþáîãî kçàìêíóòûé êëàññ, èìåþùèé ñ÷åòíûé áàçèñ.Òåîðåìà 1.7(À.À.
Ìó÷íèê).22> 3â Pk ñóùåñòâóåòÄîêàçàòåëüñòâî.Îïðåäåëèì â Pk ïîñëåäîâàòåëüíîñòü ôóíêöèé g2 ,g3 , . . .: 1, åñëè x1 = . . . = xi−1 = xi+1 = . . . = xn = 2,gn (x1 , . . . , xn ) =xi = 1 (1 6 i 6 n),0 â îñòàëüíûõ ñëó÷àÿõ.Ïîëîæèì G = [{g2 , g3 , . . .}]. Äîêàæåì, ÷òî ñèñòåìà ôóíêöèé {g2 , g3 , . . .}îáðàçóåò áàçèñ êëàññà G.
Äëÿ ýòîãî äîñòàòî÷íî óñòàíîâèòü, ÷òî íèêàêàÿ ôóíêöèÿ gm íå âûðàæàåòñÿ ôîðìóëüíî ÷åðåç îñòàëüíûå ôóíêöèèñèñòåìû {g2 , g3 , . . .}. Ïðåäïîëîæèì, ÷òî ýòî íå òàê, ò.å.gm (x1 , . . . , xm ) = gs (Φ1 , . . . , Φs ),(1.12)ãäå s 6= m è Φ1 , . . . , Φs ëèáî ôîðìóëû íàä ìíîæåñòâîì ôóíêöèé{g2 , . . . , gm−1 , gm+1 , . . .}, ëèáî ñèìâîëû ïåðåìåííûõ. Âîçìîæíû òðè ñëó÷àÿ.1. Ñðåäè âûðàæåíèé Φ1 , . . . , Φs èìåþòñÿ ïî êðàéíåé ìåðå äâå ôîðìóëû.Ïóñòü ýòî áóäóò Φi è Φj . Îáðàùàÿñü ê îïðåäåëåíèþ ôóíêöèé gn , âèäèì, ÷òî ôóíêöèè, ðåàëèçóåìûå ôîðìóëàìè Φi , Φj , íå ïðèíèìàþò çíà÷åíèÿ 2.
Ñëåäîâàòåëüíî, ôóíêöèÿ, ðåàëèçóåìàÿ ôîðìóëîé èç ïðàâîé ÷àñòè ðàâåíñòâà (1.12), íå ìîæåò ïðèíèìàòü çíà÷åíèå 1. Ýòî ïðîòèâîðå÷èòîïðåäåëåíèþ ôóíêöèè gm .2. Ñðåäè âûðàæåíèé Φ1 , . . . , Φs òîëüêî îäíî îòëè÷íî îò ñèìâîëà ïåðåìåííîé.Ïóñòü ýòî áóäåò Φi . Òàê êàê s > 2, òî èìååòñÿ õîòÿ áû îäíî âûðàæåíèå Φj , êîòîðîå ñîâïàäàåò ñ ñèìâîëîì ïåðåìåííîé. Ïóñòü, íàïðèìåð, ýòîáóäåò ïåðåìåííàÿ xl . Ðàññìîòðèì ñëåäóþùèå çíà÷åíèÿ ïåðåìåííûõ:x1 = . . . = xl−1 = xl+1 = . .
. = xm = 2,xl = 1.(1.13)Äëÿ ýòèõ çíà÷åíèé ïåðåìåííûõ ôóíêöèÿ, ðåàëèçóåìàÿ ôîðìóëîé Φi ,ïðèìåò çíà÷åíèå 0 èëè 1, à ôóíêöèÿ, ðåàëèçóåìàÿ ôîðìóëîé gs (Φ1 , . . . , Φs ), çíà÷åíèå 0. Âíîâü ïîëó÷àåì ïðîòèâîðå÷èå.3. Âñå âûðàæåíèÿ Φ1 , . . . , Φs ñóòü ñèìâîëû ïåðåìåííûõ.Î÷åâèäíî, ÷òî â ýòîì ñëó÷àå äîëæíî áûòü s > m. Çíà÷èò, ñðåäè âûðàæåíèé Φ1 , .
. . , Φs ïî êðàéíåé ìåðå äâà ðàçà âñòðåòèòñÿ îäíà è òà æå ïåðåìåííàÿ xl (1 6 l 6 m). Ðàññìîòðåâ çíà÷åíèÿ ïåðåìåííûõ (1.13), ïðèäåìê âûâîäó, ÷òî ôóíêöèÿ, ðåàëèçóåìàÿ ôîðìóëîé gs (Φ1 , . . . , Φs ), ïðèíèìàåò íà ýòîì íàáîðå çíà÷åíèå 0. Ñëåäîâàòåëüíî, è ýòîò ñëó÷àé íåâîçìîæåí.Òåîðåìà äîêàçàíà.23Äëÿ ëþáîãî k > 3 ñåìåéñòâî âñåõ çàìêíóòûõ êëàññîâ âPk èìååò êîíòèíóàëüíóþ ìîùíîñòü.Ñëåäñòâèå. ñàìîì äåëå, åñëè {m1 , m2 , .
. .} è {n1 , n2 , . . .} äâà ðàçëè÷íûõ íåïóñòûõ ïîäìíîæåñòâà ìíîæåñòâà {2, 3, . . .}, òî, êàêóñòàíîâëåíî â òåîðåìå 1.7, ìíîæåñòâàÄîêàçàòåëüñòâî.{gm1 , gm2 , . . .},{gn1 , gn2 , . . .}áóäóò ÿâëÿòüñÿ áàçèñàìè ðàçëè÷íûõ çàìêíóòûõ êëàññîâ. Òàêèì îáðàçîì,â Pk ñóùåñòâóåò ïî ìåíüøåé ìåðå êîíòèíóàëüíîå ñåìåéñòâî çàìêíóòûõêëàññîâ ñ êîíå÷íûì ëèáî ñ÷åòíûì áàçèñîì. Ñ äðóãîé ñòîðîíû, ìîùíîñòüìíîæåñòâà çàìêíóòûõ êëàññîâ â Pk íå ïðåâîñõîäèò ìîùíîñòè ìíîæåñòâàâñåõ ïîäìíîæåñòâ ñ÷åòíîãî ìíîæåñòâà Pk , ò.å.
íå ïðåâîñõîäèò ìîùíîñòèêîíòèíóóìà. Ñëåäñòâèå äîêàçàíî.ÓÏÐÀÆÍÅÍÈßÄîêàçàòü, ÷òî çàìêíóòûé êëàññ F èç òåîðåìû 1.6 íå èìåò ïðåäïîëíûõ êëàññîâ.11. Äîêàçàòü, ÷òî ïðè ëþáîì k > 4 â Pk ñóùåñòâóåò êîíòèíóàëüíîå÷èñëî çàìêíóòûõ êëàññîâ, íå èìåþùèõ áàçèñà.10.24Ãëàâà 2ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ-ÐÀÑÏÎÇÍÀÂÀÒÅËÈ 1. Êîíå÷íûé àâòîìàò áåç âûõîäà. Êîíå÷íî-àâòîìàòíûåìíîæåñòâàÁóäåì ðàññìàòðèâàòü àëôàâèò A, ñîñòîÿùèé èç ýëåìåíòîâ a1 , .
. . , ak ,êîòîðûå íàçûâàåì áóêâàìè àëôàâèòà A. Êîíå÷íóþ ïîñëåäîâàòåëüíîñòüáóêâ àëôàâèòà A, çàïèñàííûõ áåç ïðîïóñêîâ îäíà çà äðóãîé, ñ÷èòàåìñëîâîì â àëôàâèòå A. Ìíîæåñòâî âñåõ ñëîâ â àëôàâèòå A îáîçíà÷àåì÷åðåç A∗ .  ìíîæåñòâî A∗ âêëþ÷àåì ïóñòîå ñëîâî Λ ñëîâî, íå ñîäåðæàùåå áóêâ. Íà ìíîæåñòâå A∗ ââåäåì îïåðàöèþ(ñîåäè∗íåíèÿ) ñëîâ: åñëè ā, b̄ ñëîâà â àëôàâèòå A , òî êîíêàòåíàöèåé ñëîâā, b̄ íàçûâàåòñÿ ñëîâî āb̄, ïîëó÷åííîå èç ñëîâà ā ïðèïèñûâàíèåì ñïðàâàñëîâà b̄. Îòìåòèì, ÷òî äëÿ ïðîèçâîëüíîãî ñëîâà ā âûïîëíÿþòñÿ ðàâåíñòâà Λā = āΛ = ā, â ÷àñòíîñòè, ΛΛ = Λ. Äëÿ ëþáîãî ñëîâà ā è ëþáîãîíàòóðàëüíîãî ÷èñëà n ÷åðåç ān áóäåì îáîçíà÷àòü ñëîâî, ïîëó÷åííîå êîíêàòåíàöèåé n ýêçåìïëÿðîâ ñëîâà ā.
Ïîëàãàåì òàêæå ā0 = Λ.Ïðåæäå ÷åì äàòü îïðåäåëåíèå êîíå÷íîãî àâòîìàòà áåç âûõîäà, ìû õîòèì ñôîðìóëèðîâàòü íåñêîëüêî ñîäåðæàòåëüíûõ ïðåäïîñûëîê, êîòîðûåïîìîãóò óÿñíèòü ñóòü ââîäèìûõ ïîíÿòèé.Âî-ïåðâûõ, ìû õîòèì, ÷òîáû àâòîìàò ìîã âîñïðèíèìàòü (÷èòàòü) ëþáûå ñëîâà â àëôàâèòå A âõîäíîì àëôàâèòå àâòîìàòà. Îáû÷íî ãîâîðÿò,÷òî ñëîâî ā = ai1 ai2 . . . ain (â àëôàâèòå A) ïîäàåòñÿ íà âõîä àâòîìàòà(èëè ÷èòàåòñÿ àâòîìàòîì). Ïîñêîëüêó ñëîâî ā ìîæåò èìåòü ïðîèçâîëüíóþ äëèíó, àâòîìàò âîñïðèíèìàåò ñëîâî ā íå âñå ñðàçó, à ïîáóêâåííî:ñíà÷àëà áóêâó ai1 , çàòåì ai2 è ò.ä.  ñâÿçè ñ ýòèì ñ÷èòàþò, ÷òî ïðîöåññ÷òåíèÿ ñëîâà ā àâòîìàòîì ïðîèñõîäèò â äèñêðåòíûå ìîìåíòû âðåìåíèt = 1, 2, .
. .. Êðîìå òîãî, â ýòè ìîìåíòû âðåìåíè â àâòîìàòå äîëæíûïðîèñõîäèòü èçìåíåíèÿ ¾ñîñòîÿíèÿ¿. Èìåííî, ñ÷èòàåòñÿ, ÷òî â êàæäûéìîìåíò âðåìåíè àâòîìàò ìîæåò íàõîäèòüñÿ â îäíîì èç êîíå÷íîãî ÷èñëàñîñòîÿíèé. Ïðè ïîäà÷å íà âõîä àâòîìàòà î÷åðåäíîé áóêâû âõîäíîãî ñëîâààâòîìàò, êàê ãîâîðÿò, ïåðåõîäèò èç îäíîãî ñîñòîÿíèÿ â äðóãîå ñîñòîÿíèå(îíî ìîæåò ñîâïàäàòü ñ ïðåäûäóùèì ñîñòîÿíèåì). Òàêèì îáðàçîì, èìååòñÿ íåêîòîðàÿ óïðàâëÿþùàÿ ôóíêöèÿ àâòîìàòà ,êîíêàòåíàöèèôóíêöèÿ ïåðåõîäîâ25êîòîðàÿ ïî áóêâå àëôàâèòà A è ¾òåêóùåìó¿ ñîñòîÿíèþ àâòîìàòà îïðåäåëÿåò ñîñòîÿíèå àâòîìàòà â ñëåäóþùèé ìîìåíò âðåìåíè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
