С.С. Марченков - Избранные главы дискретной математики (1124120), страница 19
Текст из файла (страница 19)
Òîãäà äëÿ íåêîòîðîãî n è âñåõ x âûïîëíÿåòñÿ ðàâåíñòâîÄîêàçàòåëüñòâî.V (x) = U (n, x).(4.12) ÷àñòíîñòè, îíî âåðíî ïðè x = n. Îäíàêî ôóíêöèÿ V ïî ïðåäïîëîæåíèþ âñþäó îïðåäåëåíà. Ñëåäîâàòåëüíî, äëÿ äàííîãî n çíà÷åíèå U (n, n)îïðåäåëåíî è ñîâïàäàåò ñî çíà÷åíèåìV (n) = U (n, n) + 1.Ïðîòèâîðå÷èå ïîêàçûâàåò, ÷òî íàøå ïðåäïîëîæåíèå íåâåðíî, è ñëåäñòâèåäîêàçàíî.Ìîæåò ñëîæèòüñÿ âïå÷àòëåíèå, ÷òî ôóíêöèþ U (x, x) + 1 íåëüçÿ äîîïðåäåëèòü äî âñþäó îïðåäåëåííîé âû÷èñëèìîé ôóíêöèè âñëåäñòâèå òîãî, ÷òî îíà ¾íåïðåäñêàçóåìûì îáðàçîì¿ ïðèíèìàåò ¾î÷åíü áîëüøèå¿ è¾î÷åíü ìàëûå¿ çíà÷åíèÿ.  ñëåäñòâèè 2 ìû ðàññìàòðèâàåì ôóíêöèþ,êîòîðàÿ ïðèíèìàåò ëèøü çíà÷åíèÿ 0 è 1.Íå ñóùåñòâóåò òàêîé âñþäó îïðåäåëåííîé âû÷èñëèìîé ôóíêöèè, êîòîðàÿ ÿâëÿåòñÿ äîîïðåäåëåíèåì ôóíêöèè sg(U (x, x)).Ñëåäñòâèå 2.Ïðåäïîëîæèì, ÷òî òàêàÿ ôóíêöèÿ V (x) ñóùåñòâóåò. Âíîâü âûáèðàåì òàêîå ÷èñëî n, ÷òî äëÿ âñåõ x âûïîëíÿåòñÿ ðàâåíñòâîÄîêàçàòåëüñòâî.87(4.12).
Ïîñêîëüêó V âñþäó îïðåäåëåííàÿ ôóíêöèÿ, ïðè x = n ïîëó÷àåì èç íåãî íåâîçìîæíîå ðàâåíñòâîU (n, n) = sg(U (n, n)).Ñëåäñòâèå äîêàçàíî.È åùå îäèí èíòåðåñíûé ðåçóëüòàò ñâÿçàí ñ ôóíêöèåé U . Ðàññìîòðèììíîæåñòâî M âñåõ òåõ ÷èñåë n, äëÿ êîòîðûõ ôóíêöèÿ U (n, x) êàê ôóíêöèÿ îò x âñþäó îïðåäåëåíà. Ñóùåñòâóåò ëè ¾ïåðåñ÷åò¿ (âîçìîæíî, ñ ïîâòîðåíèÿìè) ìíîæåñòâà M ñ ïîìîùüþ êàêîé-ëèáî âñþäó îïðåäåëåííîéâû÷èñëèìîé ôóíêöèè? Îêàçûâàåòñÿ, íåò. ñàìîì äåëå, ïðåäïîëîæèì, ÷òî òàêàÿ âñþäó îïðåäåëåííàÿ ôóíêöèÿf (x) ñóùåñòâóåò. Ðàññìîòðèì âû÷èñëèìóþ ôóíêöèþV (x) = U (f (x), x) + 1.(4.13)Ïîñêîëüêó ôóíêöèÿ f ïðèíèìàåò ëèøü çíà÷åíèÿ èç ìíîæåñòâà M , ôóíêöèÿ V áóäåò âñþäó îïðåäåëåííîé âû÷èñëèìîé ôóíêöèåé. Ïîêàæåì, ÷òîîíà îòëè÷àåòñÿ îò ëþáîé âñþäó îïðåäåëåííîé âû÷èñëèìîé ôóíêöèè g(x).Äåéñòâèòåëüíî, ñîãëàñíî îïðåäåëåíèþ óíèâåðñàëüíîé ôóíêöèè íàéäåòñÿòàêîå n, ÷òî äëÿ âñåõ x âûïîëíÿåòñÿ ðàâåíñòâîg(x) = U (n, x).Ïóñòü ÷èñëî m òàêîâî, ÷òî f (m) = n.
Òîãäà èç ñîîòíîøåíèÿ (4.13) ñëåäóåò, ÷òî ôóíêöèÿ V îòëè÷àåòñÿ îò ôóíêöèè g â òî÷êå x = m. Ïîëó÷èëè ïðîòèâîðå÷èå. Çíà÷èò, ìíîæåñòâî M íåâîçìîæíî ïåðå÷èñëèòü âñþäóîïðåäåëåííîé âû÷èñëèìîé ôóíêöèåé.ÓÏÐÀÆÍÅÍÈßÄîêàçàòü, ÷òî âñÿêàÿ âû÷èñëèìàÿ ôóíêöèÿ èìååò â íóìåðàöèè Uáåñêîíå÷íîå ÷èñëî íîìåðîâ.10. Äîêàçàòü, ÷òî ôóíêöèÿ U (x, 2x) íå èìååò âñþäó îïðåäåëåííîãîâû÷èñëèìîãî äîîïðåäåëåíèÿ.11. Ïóñòü M åñòü ìíîæåñòâî âñåõ òåõ n, äëÿ êîòîðûõ ôóíêöèÿ U (n, x)êàê ôóíêöèÿ îò x îïðåäåëåíà õîòÿ áû â îäíîé òî÷êå.
Äîêàçàòü, ÷òî ìíîæåñòâî M ìîæíî ïåðå÷èñëèòü ïîäõîäÿùåé âñþäó îïðåäåëåííîé âû÷èñëèìîé ôóíêöèåé.9.88 6. Êëàññû P è NPÏóñòü A, B êîíå÷íûå àëôàâèòû, f ôóíêöèÿ âèäà A∗ → B ∗ , T (n) ôóíêöèÿ âèäà N → N . Áóäåì ãîâîðèòü, ÷òî ôóíêöèÿ fT (n), åñëè ñóùåñòâóåò ìàøèíà Òüþðèíãà M (àëôàâèò ìàøèíûM âêëþ÷àåò àëôàâèòû A è B ), êîòîðàÿ âû÷èñëÿåò ôóíêöèþ f è ïðèýòîì äëÿ ëþáîãî ñëîâà ā ∈ A∗ äëèíû n âðåìÿ âû÷èñëåíèÿ çíà÷åíèÿf (ā) íà ìàøèíå M (ò.å. ÷èñëî øàãîâ, êîòîðîå ìàøèíà M çàòðà÷èâàåòíà ïîëó÷åíèå ðåçóëüòàòà f (ā)) íå ïðåâîñõîäèò T (n).Ãîâîðèì, ÷òî ôóíêöèÿ f(èëè), åñëè ñóùåñòâóþò ìàøèíà Òüþðèíãà M èïîëèíîì p(n) ñ íàòóðàëüíûìè êîýôôèöèåíòàìè, òàêèå, ÷òî ìàøèíà Mâû÷èñëÿåò ôóíêöèþ f çà âðåìÿ p(n). ýòîì è ñëåäóþùåì ïàðàãðàôàõ ìû áóäåì ðàññìàòðèâàòüìíîæåñòâ (ÿçûêîâ) L ⊆ A∗ , ïîä êîòîðûìè áóäåì ïîíèìàòüçàäà÷è âû÷èñëåíèÿfL : A∗ → {0, 1}, ãäåïðè ëþáîì ā èç A∗âû÷èñëèìàçà âðåìÿïîëèíîìèàëüíî âû÷èñëèìàïîçíàâàíèÿâû÷èñëèìà çà ïîëèíîìèàëüíîå âðåìÿçàäà÷è ðàñ-õàðàêòåðèñòè÷åñêèõ ôóíêöèéā ∈ L ⇔ fL (ā) = 1.Îáîçíà÷èì ÷åðåç P êëàññ âñåõ ìíîæåñòâ, õàðàêòåðèñòè÷åñêèå ôóíêöèè êîòîðûõ âû÷èñëèìû çà ïîëèíîìèàëüíîå âðåìÿ (ïîëèíîìèàëüíî ðàñïîçíàâàåìûå ìíîæåñòâà).Ïóñòü L1 ⊆ A∗ è L2 ⊆ B ∗ .
Ãîâîðèì, ÷òî ìíîæåñòâî L1(èëè P) ê ìíîæåñòâó L2 , åñëè ñóùåñòâóåò ïîëèíîìèàëüíî âû÷èñëèìàÿ ôóíêöèÿ f : A∗ → B ∗ , òàêàÿ, ÷òîñâîäèòñÿïîëèíîìèàëüíîñâîäèòñÿ(∀ā)(ā ∈ L1 ⇔ f (ā) ∈ L2 ).Îòìåòèì, ÷òî îòíîøåíèå ïîëèíîìèàëüíîé ñâîäèìîñòè ðåôëåêñèâíî èòðàíçèòèâíî.Åñëè ìíîæåñòâî L1 ïîëèíîìèàëüíî ñâîäèòñÿ êìíîæåñòâó L2 è L2 ∈ P, òî L1 ∈ P.Óòâåðæäåíèå 4.1.Ïóñòü ôóíêöèÿ f1 îñóùåñòâëÿåò ïîëèíîìèàëüíîåñâåäåíèå ìíîæåñòâà L1 ê ìíîæåñòâó L2 , à f2 ïîëèíîìèàëüíî âû÷èñëèìàÿ õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ ìíîæåñòâà L2 . Èç îïðåäåëåíèé ñëåäóåò, ÷òî f2 (f1 (x)) åñòü õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ ìíîæåñòâà L1 .
Îñòàåòñÿ ïðîâåðèòü, ÷òî ôóíêöèÿ f2 (f1 (x)) ïîëèíîìèàëüíî âû÷èñëèìà. Îäíàêî åñëè ìàøèíà Òüþðèíãà M1 âû÷èñëÿåò ôóíêöèþ f1 çà âðåìÿ p1 (n),Äîêàçàòåëüñòâî.89à ìàøèíà Òüþðèíãà M2 ôóíêöèþ f2 çà âðåìÿ p2 (n), ãäå p1 , p2 ïîëèíîìû, òî êîìïîçèöèÿ M2 (M1 ) áóäåò âû÷èñëÿòü ôóíêöèþ f2 (f1 ) çàâðåìÿ p1 (n) + p2 (n + p1 (n)). Óòâåðæäåíèå äîêàçàíî.íåäåòåð-Äëÿ îïðåäåëåíèÿ êëàññà NP íàì ïîíàäîáèòñÿ ââåñòè ïîíÿòèå.
Ñ íåäåòåðìèíèðîâàííûìè êîíå÷íûìèàâòîìàòàìè ìû óæå âñòðå÷àëèñü â ãëàâå 2.  íåäåòåðìèíèðîâàííûõ ìàøèíàõ Òüþðèíãà (ñîêðàùåííî ÍÌÒ) ïðîèñõîäèò äàëüíåéøåå ðàçâèòèåèäåè ¾íåäåòåðìèíèçìà¿, çàëîæåííîé â ïîíÿòèè íåäåòåðìèíèðîâàííîãîêîíå÷íîãî àâòîìàòà.Òàê æå, êàê íåäåòåðìèíèðîâàííûé êîíå÷íûé àâòîìàò, ÍÌÒ íà êàæäîì øàãå ðàáîòû ìîæåò âûáðàòü íåñêîëüêî (íî êîíå÷íîå ÷èñëî) âàðèàíòîâ ïðîäîëæåíèÿ âû÷èñëåíèÿ. Îäíàêî â îòëè÷èå îò êîíå÷íîãî àâòîìàòàÍÌÒ ñïîñîáíà íå òîëüêî ïåðåõîäèòü â ðàçëè÷íûå ñîñòîÿíèÿ, íî òàêæå ñîâåðøàòü ðàçëè÷íûå çàìåíû îáîçðåâàåìîãî ñèìâîëà è âûïîëíÿòüðàçëè÷íûå äâèæåíèÿ ãîëîâêîé íà ëåíòå. Èíûìè ñëîâàìè, â êàæäûé ìîìåíò âðåìåíè ÍÌÒ ìîæåò ïî-ðàçíîìó ïðåîáðàçîâûâàòü êàê ñâîþ âíóòðåííþþ ïàìÿòü (âíóòðåííèå ñîñòîÿíèÿ), òàê è âíåøíþþ ïàìÿòü (ñîäåðæèìîå ëåíòû è ïîëîæåíèå ãîëîâêè íà íåé).
Ðàçóìååòñÿ, ýòà âîçìîæíîñòü÷èñòî âèðòóàëüíàÿ, è ðåàëüíûå âû÷èñëèòåëüíûå óñòðîéñòâà òàêèìè âîçìîæíîñòÿìè íå îáëàäàþò. Ñòîèò åùå îòìåòèòü, ÷òî âû÷èñëÿòü ôóíêöèèíà ÍÌÒ, âîîáùå ãîâîðÿ, íåëüçÿ. Òàê æå, êàê äëÿ íåäåòåðìèíèðîâàííûõêîíå÷íûõ àâòîìàòîâ, çäåñü ìîæíî ãîâîðèòü ëèøü î ìíîæåñòâàõ ñëîâ,äîïóñêàåìûõ (ðàñïîçíàâàåìûõ) ÍÌÒ.Ïåðåéäåì ê áîëåå ôîðìàëüíîìó îïðåäåëåíèþ íåäåòåðìèíèðîâàííîéìàøèíû Òüþðèíãà. Êàê è îáû÷íàÿ ìàøèíà Òüþðèíãà, ÍÌÒ M èìååò áåñêîíå÷íóþ ëåíòó, ðàçáèòóþ íà êëåòêè, ãîëîâêó, ñïîñîáíóþ ïåðåìåùàòüñÿ ïî ëåíòå è ÷èòàòü íàïèñàííûå íà íåé ñèìâîëû, è óïðàâëÿþùåå óñòðîéñòâî. Ìû ñîõðàíÿåì îáîçíà÷åíèÿ A = {a0 , a1 , .
. . , ak } è Q ={q0 , q1 , . . . , qr } çà ëåíòî÷íûì àëôàâèòîì ìàøèíû è ìíîæåñòâîì åå (âíóòðåííèõ) ñîñòîÿíèé.  îòëè÷èå îò (äåòåðìèíèðîâàííîé) ìàøèíû Òüþðèíãà ìàøèíà M ìîæåò èìåòü â ñâîåé ïðîãðàììå íåñêîëüêî ðàçëè÷íûõ êîìàíä (4.1) ñ îäèíàêîâûìè ëåâûìè ÷àñòÿìè ai qj . Êàê æå ¾âû÷èñëÿåò¿ìàøèíà M? íà÷àëüíûé ìîìåíò âðåìåíè íà ëåíòó ìàøèíû çàïèñûâàåòñÿ ñëîâî ā â àëôàâèòå {a1 , . . . , ak }, ìàøèíà óñòàíàâëèâàåòñÿ â ñîñòîÿíèå q1 , àåå ãîëîâêà íà ïåðâûé ñèìâîë ñëîâà ā.
Äàëåå ¾âûïîëíÿåòñÿ¿ îäíà èçïîäõîäÿùèõ êîìàíä (4.1). Ýòî çíà÷èò, ÷òî â ñëåäóþùèé ìîìåíò âðåìåíèïîòåíöèàëüíî ìîæåò âîçíèêíóòü îäíà èç(ñëîâî íà ëåíòå,ìèíèðîâàííîé ìàøèíû Òüþðèíãàêîíôèãóðàöèé90ïîëîæåíèå ãîëîâêè íà ñëîâå è ñîñòîÿíèå ìàøèíû), îïðåäåëÿåìûõ ïðàâûìè ÷àñòÿìè êîìàíä (4.1). Ìû íå ìîæåì ñêàçàòü òî÷íî, êàêàÿ èìåííîêîíôèãóðàöèÿ áóäåò ðåàëèçîâàíà â äàííûé ìîìåíò âðåìåíè, íî âûíóæäåíû ðàññìàòðèâàòü èõ âñå ¾îäíîâðåìåííî¿. Åñëè ìû âûáåðåì îäíó èçòàêèõ êîíôèãóðàöèé K , òî íà ñëåäóþùåì øàãå ïðèäåì òî÷íî â òàêîå æåïîëîæåíèå: ê êîíôèãóðàöèè K ìîæíî áóäåò ïðèìåíèòü, âîîáùå ãîâîðÿ,íåñêîëüêî êîìàíä (4.1), ÷òî âëå÷åò çà ñîáîé ïîÿâëåíèå íåñêîëüêèõ íîâûõêîíôèãóðàöèé, è ò.ä.Èíîãäà ïðîöåññ ïðèìåíåíèÿ ìàøèíû M ê ñëîâó èëëþñòðèðóþò òàêèì îáðàçîì. Ñ÷èòàþò, ÷òî â òîò ìîìåíò, êîãäà ìàøèíå M íåîáõîäèìîïðèìåíèòü îäíó èç íåñêîëüêèõ âîçìîæíûõ êîìàíä, äëÿ êàæäîé èç òàêèõêîìàíä âîçíèêàåò ñâîÿ êîïèÿ ìàøèíû M, êîòîðàÿ ïðîäîëæàåò ðàáîòàòüäàëåå ïîäîáíî èñõîäíîé ìàøèíå M.
Ïîíÿòíî, ÷òî òàêîå ¾ðàçìíîæåíèå¿ìàøèí Òüþðèíãà ïðèâîäèò, âîîáùå ãîâîðÿ, ê íåîãðàíè÷åííîìó ðîñòó÷èñëà êîïèé ìàøèíû M. Îäíàêî íåêîòîðîå ïðåèìóùåñòâî ýòîé ìîäåëè ñîñòîèò â òîì, ÷òî ñîõðàíÿåòñÿ ¾ïðèñóòñòâèå¿ ìàøèíû M â ëþáîéìîìåíò âðåìåíè è â êàæäîé âîçìîæíîé êîíôèãóðàöèè.Èç ïðèâåäåííîãî âûøå îïèñàíèÿ âèäíî, ÷òî âû÷èñëåíèå íà íåäåòåðìèíèðîâàííîé ìàøèíå Òüþðèíãà âûãëÿäèò íå êàê ëèíåéíî óïîðÿäî÷åííàÿöåïî÷êà êîíôèãóðàöèé (÷òî õàðàêòåðíî äëÿ äåòåðìèíèðîâàííûõ âû÷èñëèòåëüíûõ óñòðîéñòâ), à ñêîðåå êàê äåðåâî, â êîòîðîì ìîãóò ïðèñóòñòâîàòü êîíå÷íûå è áåñêîíå÷íûå âåòâè. Êîíå÷íûå âåòâè (èõ ìîæåò áûòüíåñêîëüêî) ñîîòâåòñòâóþò äîñòèæåíèþ ìàøèíîé M çàêëþ÷èòåëüíîãî ñîñòîÿíèÿ q0 , áåñêîíå÷íûå îòñóòñòâèþ ñîñòîÿíèÿ q0 â êîíôèãóðàöèÿõâåòâè.Òàê æå, êàê äëÿ êîíå÷íûõ àâòîìàòîâ, îïðåäåëÿåì äëÿ ÍÌÒ M ìíîæåñòâî D(M) ñîâîêóïíîñòü âñåõ ñëîâ ā â àëôàâèòå {a1 , .
. . , ak }, äëÿêîòîðûõ â äåðåâå êîíôèãóðàöèé, ïîñòðîåííîì ïî ñëîâó ā, èìååòñÿ õîòÿ áû îäíà êîíå÷íàÿ âåòâü. Èíûìè ñëîâàìè, D(M) ñîñòîèò â òî÷íîñòèèç âñåõ ñëîâ ā, äëÿ êîòîðûõ ìàøèíà M ìîæåò ¾âûáðàòü¿ âû÷èñëåíèå,çàâåðøàþùååñÿ â çàêëþ÷èòåëüíîì ñîñòîÿíèè q0 . Åñëè ā ∈ D(M), òîãîâîðèì, ÷òî ìàøèíà M() ñëîâî ā. ÌíîæåñòâîD(M) ïðè ýòîì íàçûâàþò ìíîæåñòâîì,()ìàøèíîé M.Ïóñòü T (n) ôóíêöèÿ òèïà N → N è L = D(M). Áóäåì ãîâîðèòü,÷òî ìàøèíà M äîïóñêàåò (ðàñïîçíàåò) ìíîæåñòâî LT (n), åñëè äëÿ ëþáîãî ñëîâà ā ∈ L äëèíû n ñóùåñòâóåò âû÷èñëåíèå ìàøèíûM, äîïóñêàþùåå ñëîâî ā, äëèíà êîòîðîãî íå ïðåâîñõîäèò T (n). Èíûìèäîïóñêàåò ðàñïîçíàåòäîïóñêàåìûì ðàñïîçíàâàåìûìçà âðåìÿ91ñëîâàìè, â äåðåâå êîíôèãóðàöèé ìàøèíû M, îòâå÷àþùåì ñëîâó ā, ñóùåñòâóåò êîíå÷íàÿ âåòâü (ñ çàêëþ÷èòåëüíûì ñîñòîÿíèåì q0 ) äëèíû íåáîëåå T (n).Îáîçíà÷èì ÷åðåç NP êëàññ âñåõ ìíîæåñòâ, ðàñïîçíàâàåìûõ íà íåäåòåðìèíèðîâàííûõ ìàøèíàõ Òüþðèíãà çà ïîëèíîìèàëüíîå âðåìÿ.Çàìåòèì, ÷òî ìíîæåñòâà èç êëàññà NP ìîæíî ðàñïîçíàâàòü è íà äåòåðìèíèðîâàííûõ ìàøèíàõ Òüþðèíãà.
Îäíàêî â îáùåì ñëó÷àå íå èçâåñòíû(íåïåðåáîðíûå) àëãîðèòìû ðàñïîçíàâàíèÿ, êîòîðûå ïðèâîäèëè áû ê âðåìåíè ðàñïîçíàâàíèÿ, ñóùåñòâåííî ìåíüøåìó, ÷åì ýêïîíåíöèàëüíîå.Ïðèâåäåì ïðèìåðû íåñêîëüêèõ èçâåñòíûõ ìíîæåñòâ èç êëàññà NP. Íèæåñëåäóþùèå ìíîæåñòâà èç êëàññà NP ìû ïî òðàäèöèè áóäåì ôîðìóëèðîâàòü â âèäå: îáúåêòû, ñëóæàùèå ðåøåíèÿìè çàäà÷è, îáðàçóþòèñêîìîå ìíîæåñòâî.Íàïîìíèì, ÷òî êîíúþíêòèâíîé íîðìàëüíîé ôîðìîé (ñîêðàùåííîÊÍÔ) íàçûâàåòñÿ áóëåâà ôîðìóëà âèäà D1 & D2 & . .
. & Dl , ãäå êàæäàÿôîðìóëà Di èìååò âèä ti1 ∨ ti2 ∨ . . . ∨ tini , tis ïðåìåííàÿ ëèáî îòðèöàíèåïåðåìåííîé, ïðè÷åì êàæäàÿ ïåðåìåííàÿ âñòðå÷àåòñÿ â äèçúþíêöèè Diíå áîëåå îäíîãî ðàçà. Âûðàæåíèÿ tis íàçûâàþòñÿ.Ïåðâîé (è, âèäèìî, ñàìîé èçâåñòíîé) çàäà÷åé áóäåò çàäà÷à ÂÛÏÎËÍÈÌÎÑÒÜ (ñîêðàùåííî ÂÛÏ).: ïðîèçâîëüíàÿ ôîðìóëà F (x1 , . . . , xm ) â âèäå ÊÍÔ.: ÿâëÿåòñÿ ëè ôîðìóëà, ò.å. ñóùåñòâóåò ëè òàêîémíàáîð (a1 , . . .
, am ) èç E2 , ÷òî F (a1 , . . . , am ) = 1?çàäà÷ëèòåðàëàìèÂõîäÂîïðîñÓòâåðæäåíèå 4.2.F âûïîëíèìîéÇàäà÷à ÂÛÏ ïðèíàäëåæèò êëàññó NP.Ïîñêîëüêó ôîðìóëà F ìîæåò ñîäåðæàòü ïðîèçâîëüíîå ÷èñëî ïåðåìåííûõ, íåîáõîäèìî óñëîâèòüñÿ î ñïîñîáå êîäèðîâàíèÿ ôîðìóë ñëîâàìè êîíå÷íîãî àëôàâèòà.  êà÷åñòâå êîäèðóþùåãîàëôàâèòà âîçüìåì àëôàâèò A = {0, 1, x, −, ∨, &, (, )}. Ïåðåìåííóþ xi áóäåì çàäàâàòü ñèìâîëîì x ñ ïîñëåäóþùåé äâîè÷íîé çàïèñüþ ÷èñëà i. Íàëåíòå (ðàñïîçíàþùåé ÍÌÒ) ìîãóò áûòü çàïèñàíû ïðîèçâîëüíûå ñëîâàâ àëôàâèòå A.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
