А.Б. Угольников - Лекции по дискретной математике, страница 10

ßñíî, ÷òî g ∈ S. ÊðîìåÏóñòüèòîãî,g(0, x1 , . . . , xn ) = g(1, x1 , . . . , xn ).g(1, x1 , . . . , xn ) = f (x1 , . . . , xn ).À, çíà÷èò, g(y, x1 , . . . , xn ) = f (x1 , . . . , xn ). Ò.å. ïåðåìåííàÿ yF = [=] ÿâëÿåòñÿ êîíå÷íî ïîðîæäåííûì.1)2)Ñëó÷àé= 6⊆ S.

íåñóùåñòâåííàÿ. Òåì ñàìûì êëàññB.fS ∈ =.= ⊆ T0 ∩ T1 . Ïðåäïîëîæèì, ÷òî ýòî íå òàê. Ò.å. ñóùåñòâóåò ôóíêöèÿ f èç =òàêàÿ, ÷òî f (x1 , . . . , xn ) ∈/ T0 ∩ T1 . Ðàññìîòðèì ôóíêöèþ g(x) = f (x, . . . , x). Åñëè g(x) ≡ 0, g(x) ≡ 1èëè g(x) = x, òî ýòî ïðîòèâîðå÷èò íàøåìó ïðåäïîëîæåíèþ. Çíà÷èò, g(x) = x. Äàëåå, ñóùåñòâóåòíàáîð α òàêîé, ÷òî fS (α1 , . . . , αn ) = fS (α1 , . . . , αn ) = c, c ∈ {0, 1}. Áåç îãðàíè÷åíèÿ îáùíîñòèñ÷èòàåì, ÷òî α = (0, . . .

, 0, 1, . . . , 1), k > 0.| {z } | {z }Ñëåäîâàòåëüíî, ñóùåñòâóåò ôóíêöèÿI. Ïîêàæåì, ÷òîkÒîãäàn−kf (x, . . . , x, x, . . . , x) ≡ c ∈ =.| {z } | {z }k×òî ïðîòèâîðå÷èò óñëîâèþ òåîðåìû.n−k= ⊆ T0 ∩ T1 .II. Ëèáî x ∨ y ∈ [{fS }], ëèáî xy ∈ [{fS }]. Ïîñêîëüêó fS ∈/ S, òî ñóùåñòâóåò íàáîð α òàêîé,÷òî fS (α1 , . . . , αn ) = fS (α1 , . . . , αn ) = c, c ∈ {0, 1}.

Áåç îãðàíè÷åíèÿ îáùíîñòè ñ÷èòàåì, ÷òî α =(0, . . . , 0, 1, . . . , 1). Íî òåïåðü â ñèëó ïóíêòà 1 ñïðàâåäëèâû íåðàâåíñòâà 1 6 k 6 n − 1. Ðàññìîòðèì| {z } | {z }Èòàê,kn−kôóíêöèþh(x, y) = fS (x, . . . , x, y, . . . , y ). h(x, y) ∈ T0 ∩ T1 ,| {z } | {z }kñëåäîâàòåëüíî,h(0, 0) = 0, h(1, 1) = 1.n−kh ñëåäóåò, ÷òî h(1, 0) = ñ, h(0, 1) = ñ. Åñëè c = 1, òî h(x, y) =c = 0, òî h(x, y) = xy.III. 1) x ∨ y ∈ [=]. Ïî òåîðåìå 2.2 êëàññ F1 = [= ∪ {1}] ÿâëÿåòñÿ êîíå÷íî ïîðîæäåííûì.

Ò.å.ñóùåñòâóåò ñèñòåìà B ⊆ = òàêàÿ, ÷òî [B ∪ {1}] = F1 , è |B| < ∞. Äîêàæåì, ÷òî [B ∪ {x ∨ y}] =F = [=]. Ïóñòü f (x1 , . . . , xn ) ïðîèçâîëüíàÿ ôóíêöèÿ èç F ⊆ F1 . Òîãäà ñóùåñòâóåò ôîðìóëà Ôíàä B ∪ {1}, ðåàëèçóþùàÿ ôóíêöèþ f. Âñå âõîæäåíèÿ 1 â ôîðìóëó Ô çàìåíÿåì ïåðåìåííîé y.Ïîëó÷èëè íîâóþ ôîðìóëó Ô' íàä B, ðåàëèçóþùóþ ôóíêöèþ g(y, x1 , . . . , xn ). g ∈ [B] ⊆ [=] ⊆Êðîìå òîãî, èç îïðåäåëåíèÿ ôóíêöèèx ∨ y,åñëè49T0 ∩ T1 . Ñëåäîâàòåëüíî, ôóíêöèÿ h(x1 , . .

. , xn ) := g(x1 ∨ . . . ∨ xn , x1 , . . . , xn ) ∈ T0 ∩ T1 . Êðîìå òîãîg(1, x1 , . . . , xn ) = f (x1 , . . . , xn ). Îòñþäà, ëåãêî ñëåäóåò, ÷òî h ≡ f. Òàêèì îáðàçîì, êëàññ F ÿâëÿåòñÿêîíå÷íî ïîðîæäåííûì.III. 2)xy ∈ [=].Ýòîò ñëó÷àé ìîæíî äîêàçàòü àíàëîãè÷íûì îáðàçîì èëè èñïîëüçóÿ ïðèíöèïB = =∗ . Òîãäà B ⊆ T0 ∩ T1b òàêàÿ, ÷òîêîíå÷íàÿ ñèñòåìà Bäâîéñòâåííîñòè. Äîêàæåì, ñ ïîìîùüþ ïðèíöèïà äâîéñòâåííîñòè.

Ïóñòüx ∨ y ∈ [B]. Èç ïðåäûäóùåãî ïóíêòà ñëåäóåò, ÷òî ñóùåñòâóåòb = Bb < ∞. Èç ïðèíöèïàb = [B]. Ïóñòü ñèñòåìà =b ∗ . Òîãäà |=|[B]∗∗bb[=] = [B ] = [B ] = [=].èäâîéñòâåííîñòè ñëåäóåò, ÷òîÒåîðåìà ïîëíîñòüþ äîêàçàíà.Çàâåðøàþùåé òåîðåìîé ýòîé ÷àñòè ÿâëÿåòñÿÒåîðåìà Ïîñòà. Êàæäûé êëàññ áóëåâûõ ôóíêöèé ÿâëÿåòñÿ êîíå÷íî ïîðîæäåííûì.50×àñòü IVÊîíå÷íûå àâòîìàòû.Ëåêöèÿ 13.Äåòåðìèíèðîâàííûå ôóíêöèè.Êàê è ïðè èçó÷åíèè êîäîâ, ñ÷èòàåì ÷òî èìååòñÿ äâà êîíå÷íûõ àëôàâèòà:B = {b1 , ..., bp },ïðè÷¼ì èìååòñÿ ñïåöèàëüíûé ñèìâîëΛïóñòîå ñëîâî. Ìíîæåñòâîì ñëîâ êîíå÷íîé äëèíû íàä àëôàâèòîìE∗ =[A = {a1 , ..., am }èíå âõîäÿùèé íè â îäèí èç àëôàâèòîâ E = {e1 , ..., es }íàçûâàåòñÿE k ∪ {Λ},k>1ãäåE k = {ei1 ...eik |∀j eij ∈ E}Ïóñòü èìååòñÿ ôóíêöèÿ:f : A∗ → B ∗Ãîâîðèì, ÷òî1)ff ä.-ôóíêöèÿ (äåòåðìèíèðîâàííàÿ ôóíêöèÿ), åñëè âûïîëíÿþòñÿ ñâîéñòâàñîõðàíÿåò äëèíó, ò.å.

äëÿ ëþáîãî2) äëÿ ëþáûõ ñëîâα ∈ A∗ λ(α) = λ(f (α));∗α, β ∈ A :α = α(1)...α(k)β = β(1)...β(k 0 )(α(i), β(j) ∈ A, ∀i = 1, ..., k, ∀j = 1, ..., k 0 ),óñëîâèåα(1) = β(1), ..., α(m) = β(m)äëÿ íåêîòîðîãî1 6 m 6 min(k, k 0 ),âëå÷¼òδ(1) = γ(1), ..., δ(m) = γ(m),ãäåδ = f (α), γ = f (β).Ïðèìåðûíåäåòåðìèíèðîâàííûõ îòîáðàæåíèé:A = {0, 1}, B = {0, 1}1. Íå âûïîëíÿåòñÿ ñâîéñòâî 1):2. Íå âûïîëíÿåòñÿ ñâîéñòâî 2):ff ïðîèçâîëüíîå, òàêîå ÷òîf0 → 00.

ïðîèçâîëüíîå, òàêîå ÷òîf00 → 00f01 → 10Ïóñòüf ä.-ôóíêöèÿ. Ðàññìîòðèì å¼ äåéñòâèå íà ñëîâå äëèíûfx = x(1)...x(k) → y = y(1)...y(k)51k .  ñèëó ïóíêòà 1) îïðåäåëåíèÿÏðè ýòîì, â ñèëó ïóíêòà 2)y(1)y(2)= f1 (x(1))= f2 (x(1), x(2))...y(i)=fi (x(1), ..., x(i))...y(k)ãäåfi íåêîòîðûå ôóíêöèè (åñëèA = B = {0, 1}.Òàêèì îáðàçîì ôóíêöèè f= fk (x(1), ..., x(k)),A = B = {0, 1},òîfi ∈ P2 áóëåâû ôóíêöèè). Âåçäå äàëååñ÷èòàåì, ÷òîîäíîçíà÷íî ñîîòâåòñòâóåò íàáîð ôóíêöèéfi ∈ P2 , i = 1, 2, ....

Íà ýòîìñîîáðàæåíèè îñíîâàíî ïðåäñòàâëåíèå ä.-ôóíêöèè â âèäå áåñêîíå÷íîãî äâîè÷íîãî äåðåâà ñ ïîìåòêàìè íà ð¼áðàõ, ýòî ïðåäñòàâëåíèå íàçûâàåòñÿ èíôîðìàöèîííûì äåðåâîì: ñì. Ðèñ. 1 (çâ¼çäî÷êàîòìå÷àåò êîðåíü äåðåâà).Ðèñ. 1: Èíôîðìàöèîííîå äåðåâî.Ïðèìåð 1. Ðàññìîòðèì ïðèìåð äåòåðìèíèðîâàííîé ôóíêöèè, ÿâëÿþùèéñÿ äëÿ íàñ ìîäåëüíûì:fi (x(1), ..., x(i)) = x(1) + ... + x(i) (mod 2), i = 1, 2, ...Äëÿ íå¼ èíôîðìàöèîííîå äåðåâî âûãëÿäèò ñëåäóþùèì îáðàçîì:Ðèñ. 2: Èíôîðìàöèîííîå äåðåâî ê Ïðèìåðó 1.52µ1 , µ2 äâå íåêîòîðûå åãî âåðTµ1 èçîìîðôíû (Tµ1 Tµ2 ), åñëèíà ñîîòâåòñòâóþùèõ ð¼áðàõ ïîìåòêè ó íèõ îäèíàêîâû.

Íàçîâ¼ì âåñîì r ä.-ôóíêöèè ÷èñëî ïîïàðíîíåýêâèâàëåíòíûõ ïîääåðåâüåâ (r ìîæåò áûòü ðàâíûì ∞). Åñëè r < ∞ ôóíêöèþ íàçîâ¼ì îãðàíè÷åíîäåòåðìèíèðîâàííîé.Ðàññìîòðèì èíôîðìàöèîííîå äåðåâî äëÿ ôóíêöèèf.Ïóñòüøèíû, ãîâîðèì ÷òî ïîääåðåâüÿ ñ êîðíåì â ýòèõ âåðøèíàõÏðèìåð 2.c(1)c(2)...c(k)...Tµ1èÏîñòðîèì ïðèìåð íåîãðàíè÷åíî äåòåðìèíèðîâàííîé ôóíêöèè (r= ∞):ïóñòüc= áåñêîíå÷íàÿ íåïåðèîäè÷åñêàÿ ïîñëåäîâàòåëüíîñòü (íàïðèìåð 01001000100001...).Îïðåäåëèì ôóíêöèþf:α = α(1)...α(k) ∈ A∗ , k > 1f (α) = c(1)...c(k)Î÷åâèäíî, ÷òîfíå ÿâëÿåòñÿ îãðàíè÷åíî äåòåðìèíèðîâàííîé.Èç àíàëèçà èíôîðìàöèîííîãî äåðåâà äëÿ ïðèìåðà 1 âèäíî, ÷òîÐàññìîòðèì ðàçëè÷íûå1.2.Èíôîðìàöèîííîå äåðåâîÓñå÷¼ííîå äåðåâî.r = 2.ñïîñîáû çàäàíèÿ îãðàíè÷åííî äåòåðìèíèðîâàííîé ôóíêöèè:Ïóñòü(ïîäõîäèò è äëÿ íåîãðàíè÷åíî äåòåðìèíèðîâàííûõ ôóíêöèé).{T0 , T1 , ..., Tr−1 } ìíîæåñòâî ïîïàðíî íåýêâèâàëåíòíûõ ïîääåðå{µ0 , µ1 , ..., µr−1 }, òàê ÷òî µi êîðåíü Ti .

Äàëåå, íà÷èíàÿâüåâ. Ïîìåòèì âñå âåðøèíû ìåòêàìèäâèãàòüñÿ îò êîðíÿ, èä¼ì ïî êàæäîé âåòêå äî ïåðâîãî ïîâòîðåíèÿ ìåòêè âåðøèíû è îòáðàñûâàåì âñ¼ íèæåëåæàùåå äåðåâî. Äëÿ ïðèìåðà 1 (âìåñòî ìåòîêµ0 , µ1èñïîëüçóþòñÿ ïðîñòîöèôðû 0 è 1):Ðèñ. 3: Óñå÷¼ííîå äåðåâî.3.Äèàãðàììà ïåðåõîäà (äèàãðàììà Ìóðà).Ïðåâðàòèì óñå÷¼ííîå äåðåâî â îðèåíòèðîâàí-íûé ãðàô "åñòåñòâåííûì"îáðàçîì, ò.å. ïîñòàâèâ ñòðåëêè íà ð¼áðàõ â íàïðàâëåíèè óäàëåíèÿîò êîðíÿ:Çàòåì îòîæäåñòâèì âåðøèíû ñ îäèíàêîâûìè ìåòêàìè: ñì. Ðèñ. 5.Ïîëó÷àåì îðèåíòèðîâàííûé ãðàô (ñ "ïåòëÿìè"è êðàòíûìè ð¼áðàìè)r, |E| = mr,ãäå|A| = m,G = (W, E), |W | =ó êîòîðîãî îäíà èç âåðøèí ïîìå÷åíà.

Òàêîé ãðàô è íàçûâàåòñÿäèàãðàììîé Ìóðà.4.Ïðè ïîìîùè òàáëèöû.íàçîâ¼ìx äèàãðàììå Ìóðà ïóñòü ïåðåìåííóþ, ïðîáåãàþùóþ àëôàâèòA.Q = {q0 , ..., qr−1 }F :A×Q→BG:A×Q→Q53 ðàçëè÷íûå âåðøèíû,Îïðåäåëèì ôóíêöèèFèG:Ðèñ. 4: Ïåðåõîä ê äèàãðàììå Ìóðà.Ðèñ. 5: Ïðèìåð äèàãðàììû Ìóðà.F (x, q) åñòü âûõîäíîé ñèìâîë, ñîîòâåòñòâóþùèé âåðøèíå q è âõîäx, G(x, q) åñòü âåðøèíà, â êîòîðóþ îñóùåñòâëÿåòñÿ ïåðåõîä èç âåðøèíû q ïîâõîäíîìó ñèìâîëó x. Çàäàíèå ýòèõ ôóíêöèé âìåñòå ñ óêàçàíèåì íà÷àëüíîé (ïîìå÷åííîé) âåð-ïî ñëåäóþùåìó ïðàâèëó:íîìó ñèìâîëóøèíû ýêâèâàëåíòíî çàäàíèþ äèàãðììû Ìóðà. Äëÿ ïðèìåðà 1:5.Êàíîíè÷åñêîå óðàâíåíèå.xqFG0000101101111100t ïðîáåãàþùèé N ìíît òåêóùåå ñîñòîÿíèå åñòü q(t) èy(t) = F (x(t), q(t)) è ïåðåõîäèì âÂâåä¼ì äèñêðåòíûé ïàðàìåòð âðåìåíèæåñòâî íàòóðàëüíûõ ÷èñåë.

Ñ÷èòàåì, ÷òî â ìîìåíò âðåìåíèx(t). Òîãäà íà âûõîäå ïîëó÷àåì ñèìâîëq(t+1) = G(x(t), q(t)). Çàäàíèå óðàâíåíèé ïåðåõîäà âìåñòå ñ íà÷àëüíûì ñîñòîÿíèåìíà âõîä ïîäà¼òñÿñîñòîÿíèåq(1)è íàçûâàåòñÿ çàäàíèåì êàíîíè÷åñêèõ óðàâíåíèé. Äëÿ ïðèìåðà 1:= x(t) + q(t) y(t)q(t + 1) = x(t) + q(t)q(1)= 0 çàêëþ÷åíèå îáîçíà÷èìA∗ → B ∗ .î.ä.PA,B ìíîæåñòâî âñåõ îãðàíè÷åííî äåòåðìèíèðîâàííûõ ôóíêöèé54Ëåêöèÿ 14.Êîíå÷íûå àâòîìàòû.A âõîäÿùèé àëôàâèò, |A| = m, B âûõîäÿùèé àëôàâèò, |B| = p, Q àëôàâèò ñî|Q| = r, F : A × Q → B, G : A × Q → Q. Ìíîæåñòâî V = (A, B, Q, F, G) íàçûâàåòñÿêîíå÷íûì àâòîìàòîì. Åñëè â ìíîæåñòâå Q âûäåëåíî íà÷àëüíîå ñîñòîÿíèå q0 , òî òàêîé àâòîìàò Vq0íàçûâàåòñÿ èíèöèàëüíûì êîíå÷íûì àâòîìàòîì. Vq0 çàäà¼ò îãðàíè÷åííî äåòåðìèíèðîâàííóþ (èëèàâòîìàòíóþ) ôóíêöèþ fVq0 .Åñëè çàäàí èíèöèàëüíûé àâòîìàò Vq0 = (A, B, Q, F, G), òî ôóíêöèè F è G ìîæíî ñ÷èòàòü∗ïðîäîëæåííûìè íà A × Q → ïî ñëåäóþùåìó ïðàâèëó:Ïóñòüñòîÿíèé,F (Λ, q0 ) = ΛG(Λ, q0 ) = q0F (αa, q) = F (a, G(α, q))G(αa, q) = G(a, G(α, q))ãäå∗α ∈ A , a ∈ A.ìíîæåñòâî ñëîâ ïðåäñòàâèìûõ Vq0 ïîñðåäñòâîì B 0 ⊆ BÎïðåäåëèì:åñòüM = {α ∈ A∗ |F (α, q0 ) ∈ B 0 }M ⊆ A∗ \{Λ} íàçîâ¼ì ñîáûòèåì.

Ñîáûòèå M íàçîâ¼ì ïðåäñòàâèìûì, åñëè íàéä¼òñÿ òàêîé0èíèöèàëüíûé àâòîìàò Vq0 è òàêîå ìíîæåñòâî B ⊆ B, ÷òî M åñòü ìíîæåñòâî ñëîâ ïðåäñòàâèìûõ0Vq0 ïîñðåäñòâîì B .Íà êëàññå ñîáûòèé ââåä¼ì ñëåäóþùèå òðè îïåðàöèè: ∪, ·, <> (íèæå E, K, L ñîáûòèÿ):Âñÿêîå1.E∪K2.E · K = EK = {α|α = α1 α2 , α1 ∈ E, α2 ∈ K}3.< E >= {α|∃k > 1 : α = α1 ...αk , αi ∈ E, i = 1, ..., k}. òåîðåòèêî ìíîæåñòâåííîå îáúåäèíåíèå.Îòìåòèì î÷åâèäíûåñâîéñòâà1.E∪K =K ∪E2.E ∪ (K ∪ L) = (E ∪ K) ∪ L3.E(K ∪ L) = EK ∪ EL4.(E ∪ K)L = EL ∪ KL5.(EK)L = E(KL)6.∅E = E∅ = ∅7.< ∅ >= ∅8.<< E >>=< E >9.< E >= E ∪ E < E >10.ýòèõ îïåðàöèé:E < E >=< E > E55 êîíêàòåíàöèÿ.Ñîáûòèÿ, êîòîðûå ìîæíî ïîëó÷èòü çà êîíå÷íîå ÷èñëî îïåðàöèéòèéðåãóëÿðíûìè.îðèåíòèðîâàííûé ãðàô I = (W, E),∅, {a1 }, ..., {am },Ïóñòü çàäàí∪, ·, <> èç ýëåìåíòàðíûõ ñîáû-íàçîâ¼ìó êîòîðîãî âûäåëåíû äâå âåðøèíûv1 , vkíà÷àëüíàÿ è êîíå÷íàÿ ñîîòâåòñòâåííî.

Íà êàæäîì ðåáðå ýòîãî ãðàôà íàïèñàíà ëèáî áóêâà àëôàâèòàA = {a1 , ..., am },ëèáî ñèìâîë ïóñòîãî ñëîâàÁóäåì îáîçíà÷àòüâviè êîíöîì âp : vi → vjvj , αpΛ.Òàêîé ãðàô íàçûâàåòñÿîáîáù¼ííûì èñòî÷íèêîì. íåêîòîðûé ïóòü â çàäàííîì îðèåíòèðîâàííîì ãðàôå ñ íà÷àëîì ñëîâî â îáîáù¼ííîì èñòî÷íèêå, âûïèñûâàåìîå ïðè ïðîõîæäåíèè ïóòèp(ò.å. êàæäûé ðàç ïðè ïðîõîæäåíèè ðåáðà âûïèñûâàåòñÿ áóêâà, íàïèñàííàÿ íà í¼ì). Ñ îáîáù¼ííûìèñòî÷íèêîìIñâÿæåì ñîáûòèå[I] :[I] = {α ∈ A∗ \ {Λ} | ∃p : v1 → vk : αp = α}íàçûâàåìîå ñîáûòèåì,Ïðèìåð 1.ïðåäñòàâëÿåìûì îáîáù¼ííûì èñòî÷íèêîì I.Îáîáù¼ííûé èñòî÷íèê:Ðèñ.