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

. .Óïðàæíåíèå.Äîêàçàòü, ÷òî âñå ýòè êëàññû ðàçëè÷íû.45Ïðèíöèï äâîéñòâåííîñòè.Ïóñòü íàì çàäàíà ïðîèçâîëüíàÿ ôóíêöèÿÎïðåäåëåíèå. Äâîéñòâåííîéf (x1 , . . . , xn ) ∈ P2 .ôóíêöèåé ê ôóíêöèèfáóäåì íàçûâàòü ôóíêöèþf ∗ (x1 , . . . , xn ) = f (x1 , . . . , xn ).Ïðèìåð. (x ∨ y)∗ = x ∨ y = xy,Îïðåäåëåíèå.íàÿ.ÅñëèÎáîçíà÷èì ÷åðåçS(x)∗ = (x) = x.f (x1 , . . .

, xn ) = f ∗ (x1 , . . . , xn ),òî ôóíêöèÿfíàçûâàåòñÿñàìîäâîéñòâåí-ìíîæåñòâî âñåõ ñàìîäâîéñòâåííûõ ôóíêöèé.Óòâåðæäåíèå. (Ïðèíöèï äâîéñòâåííîñòè.) Ïóñòü Φ(x1 , . . . , xn ) = f (f1 (x1 , . . . , xn ), . . .. . . , fm (x1 , . . . , xn )). Òîãäà ñïðàâåäëèâî ðàâåíñòâî∗(x1 , .

. . , xn )).Φ∗ (x1 , . . . , xn ) = f ∗ (f1∗ (x1 , . . . , xn ), . . . , fmÄîêàçàòåëüñòâî.Φ∗ (x1 , . . . , xn ) = Φ(x1 , . . . , xn ) = f (f1 (x1 , . . . , xn ), . . . , fm (x1 , . . . , xn )) =∗∗∗).= f (f 1 (x1 , . . . , xn ), . . . , f m (x1 , . . . , xn )) = f (f 1 , . . . , f m ) = f ∗ (f1∗ , . . . , fm×òî è òðåáîâàëîñü äîêàçàòü.Îòìåòèì ñëåäóþùèå ñâîéñòâà ñàìîäâîéñòâåííûõ ôóíêöèé.1)S çàìêíóòûé êëàññ.Äëÿ ïðîâåðêè çàìêíóòîñòè êëàññà äîñòàòî÷íî ïîêàçàòü, ÷òî ëþáàÿ ôóíêöèÿ âèäàf (x1 , . . . , xn ) = f0 (f1 (x1 , . . . , xn ), . . .

, fm (x1 , . . . , xn ))ïðèíàäëåæèò êëàññó, ñ ó÷åòîì òîãî, ÷òî ôóíêöèèf0 , f1 , . . . , fmïðèíàäëåæàò ýòîìó êëàññó. Èçïðèíöèïà äâîéñòâåííîñòè ñëåäóåò, ÷òî∗f ∗ = f0∗ (f1∗ , . . . , fm) = f0 (f1 , . . . , fm ) = f.2)/ S.x, x, d3 ∈ S, 1, 0, x ∨ y, xy, x → y ∈3) Åñëèf (x1 , . . .

, xn ) ∈ S,òîf (1, x2 , . . . , xn ) = f ∗ (0, x2 , . . . , xn ).Ïðèìåð. f (x, y, z) = d3 (x, y, z) = x(y ∨ z) ∨ yz.f (1, y, z) = y ∨ z, f (0, y, z) = yz.F. Êëàññ ôóíêöèé äâîéñòâåííûõ ê ôóíêöèÿì èç êëàññà FF ∗ . F ∗ = {f ∈ P2 | f ∗ ∈ F }.∗∗4) Åñëè [=] = F, òî [= ] = F (ñëåäóåò èç ïðèíöèïà äâîéñòâåííîñòè).Ïóñòü íàì çàäàí êëàññáóäåì îáîçíà-÷àòüÌíîæåñòâî ôóíêöèé ñîõðàíÿþùèõ 1 áóäåì îáîçíà÷àòü0 T1 .Ìíîæåñòâî ôóíêöèé ñîõðàíÿþùèõT0 .T1 è T0 .T0 , T1 çàìêíóòûå êëàññû.1, x, x ∨ y, xy, x → y ∈ T1 , 0, x ∈/ T1 . 0, x, x ∨ y, xy, x + y ∈ T0 , 1, x → y ∈/ T0 .T0 = T1∗ .[{x → y, xy}] = T1 .Ïåðå÷èñëèì ñâîéñòâà êëàññîâ1)2)3)4)46Äîêàæåì ïîñëåäíåå ñâîéñòâî èñïîëüçóÿ ëåììó 2 èç ëåêöèè 11.

Ïóñòü f ïðîèçâîëüíàÿ ôóíêöèÿT1 . Ðàíåå ìû ïîêàçàëè, ÷òî [{x → y, 0}] = P2 , ñëåäîâàòåëüíî f ∈ [{0, x → y, xy}]. Ïîñêîëüêó(x → y) → y = x ∨ y, òî x ∨ y ∈ [{x → y, xy}].Êðîìå òîãî, ëåãêî âèäåòü, ÷òî x1 x2 . . . xn 6 f (x1 , . . . , xn ) è x1 x2 . . . xn ∈ [{x → y, xy}]. Ïîýòîìóïðèìåíÿÿ ëåììó 2 èç ëåêöèè 11 ïîëó÷àåì, ÷òî f ∈ [{x → y, xy}].∗∗Èç ñâîéñòâà 4) ñëåäóåò, ÷òî áàçèñ T0 âûðàæàåòñÿ ñëåäóþùèì îáðàçîì {(x → y) , (xy) }. Ñëåäîâàòåëüíî, [{xy, x ∨ y}] = T0 .èçÑëåäñòâèå 2.

Åñëè ôóíêöèè fM , fL ∈ T1 , òî x → y ∈ [{1, fM , fL }].Äîêàçàòåëüñòâî. Ïîñêîëüêó ôóíêöèÿ fM (x1 , . . . , xn ) íå ÿâëÿåòñÿ ìîíîòîííîé,òî ñóùåñòâóþòα = (α1 , . . . , αn ) è β = (β1 , . . . , βn ), ò.÷. α > β, è 0 = f (α) << f (β) = 1. Òàê êàê íàáîð α ñòðîãî áîëüøå íàáîðà β, òî ñóùåñòâóþò òàêèå ÷èñëà i1 , . . . , ik , k > 1,÷òî 1 = αij > βij = 0, j = 1, . .

. , k è αi = βi , åñëè i ∈/ {i1 , . . . , ik }. Íå îãðàíè÷èâàÿ îáùíîñòè ñ÷èòàåì,÷òî ýòî ïåðâûå k ÷èñåë íàáîðîâ α è β. Ïîýòîìó ñïðàâåäëèâî ñëåäóþùåå ðàâåíñòâîäâà ðàçëè÷íûõ ñðàâíèìûõ íàáîðàfM (x, . . . , x, 1, . . . , 1, 0, . . . , 0) = x.| {z }| {z }>1kÊîëè÷åñòâî íóëåé áîëüøå ëèáî ðàâíî åäèíèöû â ñèëó òîãî, ÷òîg(x, y) = fM (x, . . . , x, 1, . . . , 1, y, .

. . , y),(1)fM ∈ T1 .Ðàññìîòðèì ôóíêöèþyg ñëåäóåò, ÷òî g(1, 1) = 1, g(1, 0) = 0,g(0, 0) = 1. Åñëè g(0, 1) = 1, òî g(x, y) = x → y = x ∨ y ∈ [{1, fM }], è òåì ñàìûì ñëåäñòâèå äîêàçàíî.Ïóñòü g(0, 1) = 0, òîãäà g(x, y) = x + y + 1 ∈ [{1, fM }].∗Òåïåðü ðàññìîòðèì ôóíêöèþ fL (x1 , . . . , xn ) ∈ T1 . ßñíî, ÷òî fL ∈/ L è fL∗ ∈ T0 . Ïî ëåììå 1∗∗ëåêöèè 10 ñóùåñòâóåò ôóíêöèÿ gL (x, y) ∈ [{0, fL }], ïðè ýòîì gL (0, 0) = 0.

Ïóñòü h(x, y) := gL (x, y).∗Ïî ñâîéñòâó 4) h(x, y) ∈ [{1, fL }], à, òàê êàê gL (x, y) ∈ T1 , òî h(1, 1) = 1. Êðîìå òîãî,ïîëó÷åííóþ ñ ïîìîùüþ çàìåíîé íóëåé íà ïåðåìåííóþâ ïðàâîé ÷àñòè ðàâåíñòâà (1). Èç îïðåäåëåíèÿ ôóíêöèèh(x, y) ∈/ L.Äàëåå, ðàçáåðåì ñëó÷àè, êîãäà ôóíêöèÿh(x, y)(2)ïðèíèìàåò âñå âîçìîæíûå çíà÷åíèÿ íà íàáîðàõ(0, 0), (0, 1), (1, 0).1) Ïóñòüh(0, 0) = 1.Òîãäà, åñëèà)h(0, 1) = h(1, 0) = 0,òîh = x + y + 1 ∈ L.á)h(0, 1) = h(1, 0) = 1,òîh ≡ 1 ∈ L.â)h(0, 1) 6= h(1, 0),òî, ëèáîÏðîòèâîðå÷èå ñ (2).Ïðîòèâîðå÷èå ñ (2).h = x → y,ëèáîh = y → x,è â ýòîì ñëó÷àå ñëåäñòâèå äîêàçàíî.2) Ïóñòüh(0, 0) = 0.Òîãäà, åñëèà)h(0, 1) = h(1, 0) = 0,[{1, fM , fL }].òîh = xy.

È,ïîñêîëüêóá)h(0, 1) = h(1, 0) = 1,òîh = x ∨ y.Èâ)h(0, 1) 6= h(1, 0),òî, ëèáîh = x,x + y + 1 ∈ [{1, fM }],òîy → x = xy + y + 1 ∈x → y = x ∨ y + y + 1 ∈ [{1, fM , fL }].ëèáîh = y,èh ∈ L.Ïðîòèâîðå÷èå ñ (2).Ñëåäñòâèå äîêàçàíî.Ëåììà 1. Äëÿ ëþáîé ôóíêöèè f èç P2 ñóùåñòâóåò ìîíîòîííàÿ ôóíêöèÿ g òàêàÿ, ÷òî g 6 fè g ∈ [{1, x ∨ y, f }].Äîêàçàòåëüñòâî. Åñëè ôóíêöèÿ f ñàìà ÿâëÿåòñÿ ìîíîòîííîé, òî óòâåðæäåíèå ëåììû î÷åâèäíî.

Ïóñòü f ∈/ M. Åñëè n = 1, òî f (x1 ) = x1 , è òîãäà â êà÷åñòâå ôóíêöèè g ìîæíî âçÿòü47n > 2. Ïóñòü x1 ïåðåìåííàÿ, ïî êîòîðîé ôóíêöèÿ f íåìîíîα = (α2 , . . . , αn ), ÷òî f (x1 , α2 , . . . , αn ) = x1 . Ââåäåì ìíîæåñòâîR = {α = (α2 , . . . , αn ) | f (x1 , α2 , . . . , αn ) = x1 }. Ìíîæåñòâî R íå ïóñòî. Ðàññìîòðèì ôóíêöèþòîæäåñòâåííûé íîëü. Èòàê, ïóñòüòîííà.

Ò.å. ñóùåñòâóåò òàêîé íàáîðf1 (x1 , . . . , xn ) = f (f ∨ χR , x2 , . . . , xn ),1, (x2 , . . . , xn ) ∈ R,ãäå ôóíêöèÿ χR (x2 , . . . , xn ) =0, èíà÷å.Ïîêàæåì, ÷òî f1 6 g. Ðàññìîòðèì ïðîèçâîëüíûé íàáîð (x1 , α2 , . . . , αn ). Åñëè α = (α2 , . . . , αn ) ∈R, òîf1 (1, α2 , . . . , αn ) = f1 (0, α2 , .

. . , αn ) = f (1, α2 , . . . , αn ) = 0;åñëè æåα∈/ R,f (0, α) = f (1, α),òî ëèáîëèáîf (x1 , α) = x1 . ëþáîì ñëó÷àå èìååì, ÷òîg(x1 , α) =f (x1 , α).f1 ∈ [{1, x∨y, f }]. Äëÿ ýòîãî äîñòàòî÷íî ïîêàçàòü, ÷òî f ∨χR ∈ [{1, x∨y, f }].x ∈ [{0, 1, fM }]. Ïîýòîìó f ∨ χR ∈ [{1, x ∨òîãî, f 6 f ∨ χR , à çíà÷èò, â ñèëó ëåììû 2 èç ëåêöèè 11 f ∨ χR ∈ [{1, x ∨ y, f }].Òåïåðü ïîêàæåì, ÷òî 5-îì ïóíêòå òåîðåìû 1.1 èç ëåêöèè 10 ìû äîêàçàëè, ÷òîy, f, 0}] = P2 . ÊðîìåÅñëè f1 íåìîíîòîííàÿôóíêöèÿ, òî ïðèìåíèì ê íåé àíàëîãè÷íîå ïðåîáðàçîâàíèå è ò.ä.

 êîíöåêîíöîâ ïîëó÷èì èñêîìóþ ìîíîòîííóþ ôóíêöèþg ∈ [{1, x ∨ y, f }], g 6 f.Ñëåäñòâèå 3. Åñëè f ïðèíàäëåæèò T0 , òî g ∈ [{x ∨ y, f }].Äîêàçàòåëüñòâî. Ïóñòü Ô ôîðìóëà íàä {1, x ∨ y, f }, ðåàëèçóþùàÿÇàìåíèì âñÿêîå âõîæäåíèå êîíñòàíòû 1 â Ô íàíàä{x ∨ y, f }ðåàëèçóåò ôóíêöèþôóíêöèþ g è g 6 f.x1 ∨ . . . ∨ xn . Ëåãêî âèäåòü, ÷òî ïîëó÷åííàÿ ôîðìóëàg.Òåîðåìà 2.2 Åñëè ñèñòåìà = ⊆ P2 , 1 ∈ [=], 0 ∈/ [=].

Òîãäà F = [=] ÿâëÿåòñÿ êîíå÷íî ïîðîæ-äåííûì êëàññîì.Äîêàçàòåëüñòâî. Ñèñòåìà = ⊆ T1 , ò.ê. åñëè ñóùåñòâóåò ôóíêöèÿ f èç =, íå ïðèíàäëåæàùàÿT1 , òî f (1, 1, . . . , 1) = 0 è, ñëåäîâàòåëüíî, 0 ∈ [=], ÷òî ïðîòèâîðå÷èò óñëîâèþ òåîðåìû. Åñëè = ⊆ M,òî ñì. òåîðåìó 2.1. Èòàê, ñóùåñòâóåò íåìîíîòîííàÿ ôóíêöèÿ fM èç =.Ïðîâåäåì äîêàçàòåëüñòâî ðàññìîòðåâ âñå âîçìîæíûå ñëó÷àè.1) Ïóñòü= ⊆ L,òîãäà=∈/ U.Êðîìå òîãî, ôóíêöèè èçf (x1 , . . .

, xn ) == ⊆ [{1, x + y + 1}] ⊆ [=].fM , fL ∈ =, = ⊆ 0∞ . Òîãäà=èìåþò ñëåäóþùèé âèä:x1 + . . . + x2k , n = 2k,x1 + . . . + x2k+1 , n = 2k + 1,n > 2.[=] = [{1, x + y + 1}] = L ∩ T1 .[{x → y}] = 0∞ è ñëåäñòâèÿÒîãäà ýòîì ñëó÷àå2)â ñèëó òîãî, ÷òî2, ñïðàâåäëèâûñîîòíîøåíèÿ= ⊆ [{x → y}] ⊆ [{1, fM , fL }] ⊆ [=].∞[=] = 0 .fM , fL ∈ =, = 6⊆ 0∞ . Ïóñòü f ïðîèçâîëüíàÿ ôóíêöèÿ èç =. Òîãäà, åñëè f ∈ 0∞ , òîf ∈ [{x → y}]. Ïóñòü f ∈/ 0∞ , òîãäà ïî ëåììå 1 ñóùåñòâóåò òàêàÿ ìîíîòîííàÿ ôóíêöèÿ gf , ÷òîgf 6 f è gf ∈ [{1, x S∨ y, f }]. Ïî ëåììå 2 èç ëåêöèè 11 f ∈ [{x → y, gf }].Ïóñòü B =gf .

ßñíî, ÷òî = ⊆ [{x → y} ∪ B]. Òàê êàê B ñîñòîèò òîëüêî èç ìîíîf ∈ =,f∈/ 0∞p(B)òîííûõ ôóíêöèé, òî ïî òåîðåìå 2.1 B ⊆ [{1, ω, dp(B) }] ⊆ [{1, ω, g}]. Ïî îïðåäåëåíèþ ôóíêp(B)p(B)p(B)bböèè g ñóùåñòâóåò òàêàÿ ôóíêöèÿ f∈ =, ÷òî g∈ [{1, x ∨ y, f}]. À ýòî îçíà÷àåò, ÷òîB ⊆ [{1, ω, x ∨ y, fbp(B) }]. Îòñþäà ñëåäóåò, ÷òîÎòêóäà ñëåäóåò, ÷òî3)= ⊆ [{x → y} ∪ B] ⊆ [{x → y, dp(B) }] ⊆ [{x → y, fbp(B) }] ⊆ [{1, fM , fL , fbp(B) }] ⊆ [=].Òàêèì îáðàçîì[=] = [{x → y, dp(B) }].Òåîðåìà äîêàçàíà.48Ñëåäñòâèå 4. Âñå çàìêíóòûå êëàññû ôóíêöèé, ñîäåðæàùèå íåìîíîòîííóþ ôóíêöèþ è 1 è íåñîäåðæàùèå 0, èñ÷åðïûâàþòñÿ ñëåäóþùèì ñïèñêîìL ∩ T1 , 0∞ , T1 = [{x → y, xy}], [{x → y, dp }], p = 3, 4, .

. .ÓïðàæíåíèåÄîêàçàòü, ÷òî âñå êëàññû ðàçëè÷íû.Òåîðåìà 3. Åñëè ñèñòåìà = ⊆ P2 , 0 ∈ [=], 1 ∈/ [=]. Òîãäà F = [=] ÿâëÿåòñÿ êîíå÷íî ïîðîæäåí-íûì êëàññîì.Äîêàçàòåëüñòâî.B = =∗ . Òîãäà 1 ∈ [B], 0 ∈/ [B], è ïî∗∗b=Bbb ∗,[B] = F = [= ]. Åñëè ïîëîæèòü =Ïóñòüb <∞|B|ñèñòåìàbB,b = F.[=]Òåîðåìà äîêàçàíà.÷òîèòåîðåìå 2.2 ñóùåñòâóåò òàêàÿòî ñèñòåìàb=áóäåò êîíå÷íà èÑëåäñòâèå 5. Âñå çàìêíóòûå êëàññû, ñîäåðæàùèå 0 è íå ñîäåðæàùèå 1, áóäóò äâîéñòâåííûìè ê êëàññàì, ïåðå÷èñëåííûì â ñëåäñòâèÿõ 1 è 4.Òåîðåìà 4.

Åñëè ñèñòåìà = ⊆ P2 , 0, 1 ∈/ [=]. Òîãäà F = [=] ÿâëÿåòñÿ êîíå÷íî ïîðîæäåííûìêëàññîì.Äîêàçàòåëüñòâî.=⊆SÑëó÷àéA.[= ∪ {1}] = F1 . Òîãäà ïî òåîðåìå 2.2 êëàññ F1 ÿâëÿåòñÿ êîíå÷íî ïîðîæäåííûì.Ò.å. ñóùåñòâóåò ñèñòåìà B ⊆ = òàêàÿ, ÷òî [B ∪ {1}] = F1 è |B| < ∞.Äîêàæåì, ÷òî [B] = F = [=]. Ïóñòü f (x1 , . . . , xn ) ïðîèçâîëüíàÿ ôóíêöèÿ èç F ⊆ S. Ñóùåñòâóåòôîðìóëà Ô íàä B ∪ {1}, ðåàëèçóþùàÿ ôóíêöèþ f. Çàìåíÿåì â íåé âñå âõîæäåíèÿ 1 ïåðåìåííîéy. Ïîëó÷èëè ôîðìóëó Ô' íàä B, ðåàëèçóþùóþ ôóíêöèþ g(y, x1 , . . . , xn ).