А.Б. Угольников - Лекции по дискретной математике (1083729), страница 8
Текст из файла (страница 8)
, xn ) > xi .ÔóíêöèÿÎáîçíà÷èì ÷åðåç1.2.3.∞0∞óäîâëåòâîðÿåò óñëîâèþ0∞ ,åñëè íàéäåòñÿ òàêîåìíîæåñòâî âñåõ òàêèõ ôóíêöèé. Ïåðå÷èñëèì ñâîéñòâà ìíîæåñòâài,÷òî0∞ .∞[0 ] = 0 .1, x, x ∨ y, x ∨ yz, x → y = x ∨ y ∈ 0∞ , 0, x, xy ∈/ 0∞ .∞[{x → y}] = 0 .Äîêàæåì ïîñëåäíåå ñâîéñòâî èñïîëüçóÿ ëåììó 2.x ∨ y ∈ [{x → y}], ò.
ê. (y → x) → x = x ∨ (x ∨ y) = x ∨ y.Ïîñêîëüêó x → 0 = x, òî [{x → y, 0}] = P2 . (ñèñòåìà {x, x ∨ y} ïîëíà)∞Åñëè f ∈ 0 ,òî ïî îïðåäåëåíèþ ñóùåñòâóåò òàêîå xi , ÷òî f > xi . ßñíî, ÷òî xi ∈ [{x → y}], à,∞çíà÷èò, ïî ëåììå 2, f ∈ 0 .T∞Ââåäåì ôóíêöèþ ω(x, y, z) = x ∨ yz. ßñíî, ÷òî ω ∈ 0M.T∞Óòâåðæäåíèå 1. Åñëè f (x1 , .
. . , xn ) ∈ 0M è f 6≡ 1, òî f ∈ [{ω}].Äîêàçàòåëüñòâî. Ïóñòü f ïðîèçâîëüíàÿ ìîíîòîííàÿ ôóíêöèÿ èç 0∞ , f 6≡ 1. Òîãäà â ñèëóòîãî, ÷òî ëþáàÿ ìîíîòîííàÿ ôóíêöèÿ îòëè÷íàÿ îò êîíñòàíòû (0 ∈/ 0∞ ) ïðèíàäëåæèò [{x ∨ y, xy}],òî f ∈ [{ω, 0}]. Êðîìå òîãî, xi 6 f ïðè íåêîòîðîì i è xi ∈ [{ω}], à òàêæå x ∨ y ∈ [{ω}]. Ïîýòîìó ïîëåììå 2 f ∈ [{ω}]. ×òî è òðåáîâàëîñü äîêàçàòü.Óòâåðæäåíèå 2. Åñëè ôóíêöèè fK , fD ∈ M, òî ω ∈ [{1, fK , fD }].Äîêàçàòåëüñòâî. Íà ïðîøëîé ëåêöèè ìû äîêàçàëè, ÷òî åñëè ôóíêöèè fD , fK ∈ M, òî x∨y, xy ∈[{0, 1, fK , fD }].ω ∈ [{0, 1, fK , fD }], êðîìå òîãî, x, x ∨ y ∈ [{1, fK , fD }], x 6 ω,ω ∈ [{1, fK , fD }].
Óòâåðæäåíèå äîêàçàíî.Wdp (x1 , . . . , xp ) =xi xj , p > 2Îòñþäà ñëåäóåò, ÷òîçíà÷èò, â ñèëó ëåììû 2Ââåäåì ôóíêöèþi<jÏåðå÷èñëèì ñâîéñòâà ôóíêöèèdp .42à1)dp (1, 0, . . . , 0) = . . . = dp (0, . . . , 0, 1) = 0,jidp (0, . . . , 0, 1, 0, . . . , 0, 1, 0, . . . , 0) = 1äëÿ ëþáûõi, j, i 6= j.2)dp 6∈ 0∞ .3)dp (x1 , . .
. , xp ) = x1 (x2 ∨ . . . ∨ xp ) ∨ dp−1 (x2 , . . . , xp ),4)dp+1 (x1 , . . . , xp+1 ) > dp (x1 , . . . , xp )5)ω ∈ [{1, d3 }];6)d3 (x1 , x2 , x3 ) = x1 x2 ∨ x1 x3 ∨ x2 x3 . d3 ∈/ K, D, d3 ∈ M.åñëèp > 3,òîïðèp > 2.(ñëåäóåò èç ñâîéñòâà 3).ω ∈ [{dp }](ò. ê.dp (x, . . . , x, y, z) = x ∨ yz = ω ).Óòâåðæäåíèå 3. Ïðè âñåõ p > 2 ñïðàâåäëèâî ñëåäóþùåå ñîîòíîøåíèå[{ω}] ⊂ [{ω, dp+1 }] ⊆ [{ω, dp }].Äîêàçàòåëüñòâî.ñëåäóåò, ÷òîÈç ñâîéñòâà 3) ñëåäóåò, ÷òî ïðèdp+1 ∈ [{ω, dp }].p > 2Èç ñâîéñòâà 2)[{ω}] ⊂ [{ω, dp+1 }].Óïðàæíåíèå.Äîêàçàòü, ÷òî[{ω, dp+1 }] ⊂ [{ω, dp }].0µ ,µ íàáîðîâ (µ > 2), íà0µ ìíîæåñòâî âñåõ ôóíêöèé,µµóäîâëåòâîðÿþùèõ óñëîâèþ 0 , µ = 2, 3, .
. . , ∞. Êëàññû 0 , µ = 2, 3, . . . , ∞ ÿâëÿþòñÿ çàìêíóòûìè,∞è âûïîëíåíî ñîîòíîøåíèå 0⊂ . . . ⊂ 0µ ⊂ . . . ⊂ 02 . È, íàêîíåö, dp+1 ∈ 0p , íî dp ∈/ 0∞ .)(Óêàçàíèå. Ãîâîðÿò, ÷òî ôóíêöèÿ óäîâëåòâîðÿåò óñëîâèþåñëè ëþáûåêîòîðûõ ôóíêöèÿ ðàâíà 0, èìåþò îáùóþ íóëåâóþ êîìïîíåíòó. ÏóñòüÏóñòü çàäàíà ôóíêöèÿf (x1 , . . . , xn ) ∈ M, n > 2.Îïðåäåëèì ôóíêöèèfji .fji (x1 , . . .
, xj−1 , xj+1 , . . . , xn ) = f (x1 , . . . , xj−1 , xi , xj+1 , . . . , xn ), i, j = 1, . . . , n, i 6= j.Ïåðå÷èñëèì ñâîéñòâà ýòèõ ôóíêöèé.1)fji 6 xi ∨ f.Åñëèxi = 1,òî ðàâåíñòâî, î÷åâèäíî, âûïîëíÿåòñÿ. Ïóñòüxi = 0.Íåðàâåíñòâîf (x1 , . . . , xi−1 , 0, xi+1 , . . .
, xj−1 , 0, xj+1 , . . . , xn ) 66 f (x1 , . . . , xi−1 , 0, xi+1 , . . . , xj−1 , xj , xj+1 , . . . , xn )âûïîëíÿåòñÿ â ñèëó ìîíîòîííîñòè ôóíêöèè2)xj fji 6 f.f.Ïðîâåðÿåòñÿ àíàëîãè÷íî.Ââåäåì íåñêîëüêî îáîçíà÷åíèé. Ïóñòü Ak (f ) ìíîæåñòâî ôóíêöèé âèäà g(xi1 , . . . , xik ),xi1 , . . . , xik ⊆ {x1 , . . . , xn }, ij 6= il , ïðèj 6= l, ïîëó÷åííûõ èç f îòîæäåñòâëåíèåì ïåðåìåííûõ.i ÷àñòíîñòè, An−1 (f ) = {fj , i, j = 1..n}.Ïóñòü =f = {ω, dn } ∪ An−1 (f ).Ëåììà 3. Åñëè f (x1 , .
. . , xn ) ìîíîòîííàÿ ôóíêöèÿ è n > 2. Òîãäà f ïðèíàäëåæèò [{=f }].Äîêàçàòåëüñòâî. Åñëè f ≡ const, òî óòâåðæäåíèå ëåììû î÷åâèäíî. Åñëè f 6≡ const è f ∈ 0∞ ,f ∈ [{ω}].f∈/ 0∞ , n > 2, f 6≡ const. Äîêàæåìòî ïî ðàíåå äîêàçàííîìó óòâåðæäåíèþÏóñòü òåïåðüïî èíäóêöèè. Ïðèn = 2 d2 = x1 x2 ,f ∈ [{x ∨ y, xy}] ⊆ [{ω, d2 }].k < n.
Äîêàæåì, ÷òî îíà âåðíàf , çàâèñÿùåé îò n ïåðåìåííûõ.∞∞Ââåäåì ôóíêöèþ g := f (0, x2 , . . . , xn ). Åñëè g ∈ 0 , òî ò.ê. f > g, f ∈ 0 . ×åãî íå ìîæåò áûòü ïî∞ïðåäïîëîæåíèþ. Ñëåäîâàòåëüíî, g ∈/ 0 . Çíà÷èò g 6≡ 1. Ïóñòü g ≡ 0. Òîãäà ñïðàâåäëèâî âûðàæåíèåÏðåäïîëîæèì, ÷òî óòâåðæäåíèå ëåììû ñïðàâåäëèâà äëÿ âñåõäëÿ ëþáîé ìîíîòîííîé ôóíêöèèf (x1 , x2 , . .
. , xn ) = x1 f (1, x2 , . . . , xn ).43È ïîýòîìóf (x, y, . . . , y) = xy ,ò.ê.f (1, 0, . . . , 0) = 0(åñëèf (1, 0, . . . , 0) = 1,òî â ñèëó ìîíîòîííîñòèf ∈ 0∞ ).ßñíî, ÷òîxy ∈ [=f ],è ïî ñëåäñòâèþ 1 âûïîëíåíî óòâåðæäåíèå ëåììû.Ïîýòîìó îñòàëîñü ðàññìîòðåòü ñëó÷àé, êîãäàg∈/ 0∞ , g 6≡ 0, 1.g ∈ M,Ïîñêîëüêóòî ïî ïðåäïî-ëîæåíèþ èíäóêöèè ñïðàâåäëèâî ñîîòíîøåíèåg ∈ [=g ] = [{ω, dn − 1} ∪ An−2 (g)].=g ,g. Ñäåëàåì íàä íåé ñëåäóþùåå ïðåîáðàçîâàB = dn−1 (B2 , . . . , Bn ), òî çàìåíÿåì åãî íà íîâûé ýëåìåíòB = dn (y1 , B2 , .
. . , Bn ). Òî÷íî òàê æå çàìåíÿåì ýëåìåíò B = gji (B2 , . . . , Bn ) íà íîâûé ýëåìåíòB = fji (y1 , B2 , . . . , Bn ), i, j = 2, . . . , n, i 6= j. Òåì ñàìûì ïîëó÷èì ôîðìóëó Ô íàä [=f ], ðåàëèçóþùóþ íåêîòîðóþ ôóíêöèþ h(y1 , . . . , yn ). Ïðè ýòîì h(0, y2 , .
. . , yn ) = g(y2 , . . . , yn ) è h(1, 0, . . . , 0) == g(0, . . . , 0) = 0 (ïîñëåäíèå ðàâåíñòâî ëåãêî äîêàçûâàåòñÿ ïî èíäóêöèè ãëóáèíû ôîðìóëû). ÈçÏóñòü Ôg ôîðìóëà íàäçàäàþùàÿ ôóíêöèþíèå. Åñëè â ôîðìóëó Ôg âõîäèò ýëåìåíòýòîãî ñëåäóåò ñëåäóþùåå ðàâåíñòâîy1 (y2 ∨ . . . ∨ yn ) ∨ h(y1 , . . .
, yn ) = y1 (y2 ∨ . . . ∨ yn ) ∨ g(y2 , . . . , yn ).φ(y1 , . . . , yn ) := y1 (y2 ∨ . . . ∨ yn ) ∨ g(y2 , . . . , yn ).φ(x1 , f12 , . . . , f1n ) 6 f.Ââåäåì ôóíêöèþÏîêàæåì, ÷òî(3)Èç (3) ñëåäóåò, ÷òîφ ∈ [=f ].x1 (f12 , . . . , f1n ) ∨ g(f12 , . . . , f1n ) 6 f ∨ g(x2 ∨ f, . . . , xn ∨ f ) 6 f.χ ∈ [=f ], ò.÷. χ 6 f. Î÷åâèäíî, ÷òî x ∨ y ∈ [=f ]f ∈ [=f ∪ {0}]. À çíà÷èò, ïî ëåììå 1 f ∈ [=f ].Òåì ñàìûì ìû íàøëè íåêîòîðóþ ôóíêöèþxy ∈ [=f ∪ {0}]Ïîýòîìó ïî ñëåäñòâèÿ 1è×òî è òðåáîâàëîñü äîêàçàòü.Ïóñòüf (x) ìîíîòîííàÿ ôóíêöèÿ,êèõ ôóíêöèé, êîòîðûå ïîëó÷àþòñÿ èçïðèíàäëåæàò0∞ ,ff ∈ 0∞ , f 6≡ 0.Ffìíîæåñòâî âñåõ òà-à ïðè âñÿêîì îòîæäåñòâëåíèè äâóõ ïåðåìåííûõ ïåðåõîäÿò â ôóíêöèè èçÏðèìåð.
f (x, y, z) = d3 (x, y, z) = xy ∨ xz ∨ yz.Åñëè ôóíêöèÿÎáîçíà÷èì ÷åðåçîòîæäåñòâëåíèåì ïåðåìåííûõ (áûòü, ìîæåò ïóñòûì) è íåg(x1 , . . . , xp ) ∈ Ff ,òîg ∈ M,èÒîãäà∞g∈/0 .0∞ .Fd3 = {d3 }.Ñëåäîâàòåëüíî,g(1, 0, . . . , 0) = . . . = g(0, . . .
, 0, 1) = 0.Ïîñêîëüêógji ∈ 0∞ ,òîjig(0, . . . , 0, 1, 0, . . . , 0, 1, 0, . . . , 0) = 1, i, j = 1, . . . , n, i 6= j.Çíà÷èò èìååò ìåñòî ñëåäóþùååÑëåäñòâèå. Ëþáàÿ ôóíêöèÿ g èç Ff , ñóùåñòâåííî çàâèñÿùàÿ îò p ïåðåìåííûõ, èìååò âèäg = dp .Çàìå÷àíèå.Ðàçíûìè îòîæäåñòâëåíèÿìè ìîæíî ïðèéòè ê ðàçíûì ôóíêöèÿìp(f ) ìèíèìàëüíîådp(f ) ∈ [{f }].Ïóñòüèìååì÷èñëî ñóùåñòâåííûõ ïåðåìåííûõ ó ôóíêöèé èçFf .dp . ñèëó ñëåäñòâèÿËåììà 4. Äëÿ ëþáîé ìîíîòîííîé ôóíêöèè f ∈/ 0∞ , f 6≡ 0, âûïîëíÿåòñÿ ñîîòíîøåíèåf ∈ [ω, dp(f ) ].Äîêàçàòåëüñòâî.Èç ëåììû 3f ∈ [{ω, dn } ∪ An−1 (f )] ⊆ [{ω, dn , dn−2 } ∪ An−2 (f )] ⊆ . .
.. . . ⊆ [{ω, dn , dn−1 , . . . , dp(f ) } ∪ Ap(f )−1 ] ⊆ [{ω, dn , . . . , dp(f ) }]Ap(f )−1 ⊆ 0∞ ∩ M.ñîîòíîøåíèå [{ω, dp }] ⊆ [{ω, dp−1 }].Ïîñëåäíèå âëîæåíèå ñïðàâåäëèâî â ñèëó òîãî, ÷òîÐàíåå ìû äîêàçàëè, ÷òî ïðèp > 3âåðíî[{ω, dn , . . . , dp(f ) }] ⊆ [{ω, dp(f ) }].Ëåììà äîêàçàíà.44Ñëåäîâàòåëüíî,Ëåêöèÿ 12.Íàïîìíèì íåêîòîðûå îáîçíà÷åíèÿ çàìêíóòûõ êëàññîâ.D = {0, 1, x ∨ y}. Êðîìåîáîçíà÷àòü åå f= .òîãî, åñëè ôóíêöèÿfC = {0, 1}, U = {0, 1, x}, K = {0, 1, xy},=, äëÿ êðàòêîñòè ìû áóäåìíå ïðèíàäëåæèò ñèñòåìåÒåîðåìà 2.1. Ïóñòü ñèñòåìà = ⊆ M, 1 ∈ [=], 0 ∈/ [=].
Òîãäà F = [=] ÿâëÿåòñÿ êîíå÷íîïîðîæäåííûì êëàññîì.Äîêàçàòåëüñòâîïðîâåäåì ðàññìîòðåâ âñåâîçìîæíûå ñëó÷àè.1) Ïóñòü= ⊆ C,2) Ïóñòü= ⊆ U, = 6⊆ C,òîãäà[=] = [{1}].òîãäà[=] = [{1, x}] = [{1, fC }].3à) Ïóñòü= ⊆ K, = 6⊆ U ∪ C,òîãäà[=] = [{1, xy}].3á) Ïóñòü= ⊆ D, = 6⊆ U ∪ C,òîãäà[=] = [{1, x ∨ y}].fK , fD ∈ = è = ⊆ 0∞ .
Òîãäà ïî óòâåðæäåíèþ 1 ëåêöèè 11 ñëåäóåò, ÷òî = ⊆ [{1, ω}],à èç óòâåðæäåíèÿ 2 [{1, ω}] ⊆ [{1, fk , fd }] ⊆ [=]. Òåì ñàìûì ìû ïîëó÷èëè, ÷òî â ýòîì ñëó÷àå[=] = M ∩ 0∞ = [{1, ω}].4) ÏóñòüfK , fD ∈ = è = 6⊆ 0∞ . Ðàññìîòðèì ïðîèçâîëüíóþ ôóíêöèþ f èç =. Åñëè f ∈ 0∞ ,f ∈ [{1, ω}].
Ïóñòü f ∈ 0∞ . Òîãäà ïî ëåììå 4 ëåêöèè 11 ñëåäóåò, ÷òî f ∈ [{1, ω, dp(f ) }]. Çíà÷èò,5) Ïóñòü= ⊆ [{1, ω} ∪ {[òîdp(f ) }] ⊆ [{1, ω, dp(=) ],f ∈ =,f∈/ 0∞ãäåp(=) =min p(f ).f ∈ =,f∈/ 0∞Ïîñëåäíèå âëîæåíèå ñïðàâåäëèâî â ñèëó óòâåðæäåíèÿ 3 ëåêöèè 11.dp(f ) = dp(=) . Îáîçíà÷èì å¼ f p(=) .  ïðåäûäóùåì ñëó÷àå÷òî ôóíêöèÿ ω ïðèíàäëåæèò ñèñòåìå =. Íàì îñòàëîñü ïîêàçàòü, ÷òî ôóíêöèÿ dp(=)p(=)ñèñòåìå =. Íî ýòî ëåãêî ñëåäóåò èç òîãî, ÷òî dp(=) ∈ [{f}].
Òàêèì îáðàçîìÂîçüìåì òó ôóíêöèþìû ïîêàçàëè,ïðèíàäëåæèòf,äëÿ êîòîðîé[{1, ω, dp(=) }] ⊆ [{1, fK , fD , f p(=) }] ⊆ [=].Òåîðåìà ïîëíîñòüþ äîêàçàíà.Ñëåäñòâèå 1. Âñå êëàññû ìîíîòîííûõ ôóíêöèé, ñîäåðæàùèå 1, è íå ñîäåðæàùèå 0, èñ÷åðïûâàþòñÿ ñëåäóþùèì ñïèñêîì[{1}], [{1, x}], [{1, x ∨ y}], [{1, xy}], M ∩ 0∞ , M ∩ T1 = [{1, x ∨ y, xy}],[{1, ω, dp }], p = 3, 4, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
