А.Б. Угольников - Лекции по дискретной математике (1083729), страница 7
Текст из файла (страница 7)
. . , xn , ôóíêg îò ïåðåìåííûõ y1 , . . . , ym . Ïðè÷åì äëÿ ôóíêöèè f ñóùåñòâåííûìè ÿâëÿþòñÿ ïåðåìåííûåxi1 , . . . , xik , i1 6 . . . 6 ik , à äëÿ ôóíêöèè g yj1 , . . . , yjk , j1 6 . . . 6 jk . Òîãäà áóäåì ñ÷èòàòü, ÷òîf = g , åñëè äëÿ ëþáûõ íàáîðîâ x1 , . . . , xn , y1 , . . . , ym òàêèõ, ÷òî xi1 = yj1 , . . . , xik = yjkðåìåííûìè.
Ïîÿñíèì ýòî îïðåäåëåíèå. Ïóñòü ôóíêöèÿöèÿf (x1 , . . . , xn ) = g(y1 , . . . , ym ).P2 . Ïóñòü R ⊂ P2 . Ìíîæåñòâî âñåõ áóëåâûõ ôóíêR(n).âàæíûé âîïðîñ çàäàíèå ôóíêöèè â âèäå ôîðìóëû íàä = ⊆ P2 , = 6= ∅.=, çàâèñÿùèå îò n ïåðåìåííûõ áóäåì îáîçíà÷àòü f n . Èòàê, ââåäåì îïðåäåëåíèåÎáîçíà÷èì ìíîæåñòâî âñåõ áóëåâûõ ôóíêöèéöèé èçR,çàâèñÿùèõ îòÐàññìîòðèìÔóíêöèè èçnïåðåìåííûõ, îáîçíà÷èìôîðìóëû.1)f n (xi1 , .
. . , xin )2)g m (A1 , . . . , Am ) íàçûâàåòñÿ=, ëèáî ïåðåìåííûå èç X .íàçûâàåòñÿ ôîðìóëîé íàä3) Äðóãèõ ôîðìóë íàä=ôîðìóëîé íàä=.=,åñëègm ∈ =èA1 , . . . , Am ëèáî ôîðìóëû íàäíåò.Åùå îäèí ñïîñîá çàäàíèÿ ôóíêöèé çàäàíèå åå çíà÷åíèé íà âñåõ íàáîðàõ ïåðåìåííûõ.Ïðèìåðû.Ôóíêöèè îò îäíîé ïåðåìåííîé.x01xx0010110110Ôóíêöèè îò äâóõ ïåðåìåííûõ.xyx∨yx&yx+yx→y000001011011101010111101nÇàìå÷àíèå.
|P2 (n)| = 22 .Ïóñòü åñòü ñèñòåìà ôóíêöèé=, = =6 ∅, = ⊆ P2 .37Îïðåäåëåíèå.Áóäåì íàçûâàòü çàìûêàíèåìâ âèäå âñåâîçìîæíûõ ôîðìóë íàäÎïðåäåëåíèå.Åñëè ñèñòåìàÎïðåäåëåíèå.ÅñëèÎïðåäåëåíèå.Åñëè ñóùåñòâóåò ñèñòåìà[=] = F ,= è îáîçíà÷àòü [=] ìíîæåñòâî ôóíêöèé, çàäàííûõ=.F = [F ],òî îíà íàçûâàåòñÿ çàìêíóòûì êëàññîì Ïîñòà.òî áóäåì ãîâîðèòü, ÷òî ñèñòåìà=òàêàÿ, ÷òî=ïîðîæäàåò[=] = FèF.|=| < ∞,òîãäà ñèñòåìàFíàçûâàåòñÿ êîíå÷íî ïîðîæäåííîé.Ìû áóäåì èçó÷àòü äâà âîïðîñà.1.  êàêîì ñëó÷àå ñèñòåìàFáóäåò çàìêíóòûì êëàññîì Ïîñòà.2.
Âåðíî ëè, ÷òî ëþáàÿ ñèñòåìàF ⊆ P2Äëÿ íà÷àëà óñòàíîâèì, ÿâëÿåòñÿ ëèP2ÿâëÿåòñÿ êîíå÷íî ïîðîæäåííîé.êîíå÷íî ïîðîæäåííûì.Óòâåðæäåíèå. ∀f ∈ P2 , âåðíî ïðåäñòàâëåíèåf (x1 , . . . , xn ) = x1 (f (1, x2 , . . . , xn ) + f (0, x2 , . . . , xn )) + f (0, x2 , . . . , xn ).Äîêàçàòåëüñòâî.Ïîäñòàâèì íàáîð(0, x2 , . . . , xn )(1)â ôîðìóëó (1).f (0, x2 , . . . , xn ) = 0 · (f (1, x2 , . . .
, xn ) + f (0, x2 , . . . , xn )) + f (0, x2 , . . . , xn ) = f (0, x2 , . . . , xn ).Ïîäñòàâèì íàáîð(1, x2 , . . . , xn )â ôîðìóëó (1).f (1, x2 , . . . , xn ) = 1 · (f (1, x2 , . . . , xn ) + f (0, x2 , . . . , xn )) + f (0, x2 , . . . , xn ) = f (1, x2 , . . . , xn ).×òî è òðåáîâàëîñü äîêàçàòü.Ñëåäñòâèå 1.ÑèñòåìàÑëåäñòâèå 2.Ïðåäñòàâëåíèå áóëåâîé ôóíêöèè â âèäå ïîëèíîìà Æåãàëêèíà.{xy, x + y, 0, 1}ïîðîæäàåòP2 .nf (x1 . . . , xn ) =2Xci Ki ,i=1ci ∈ B , Kiãäå âñåâîçìîæíûå ýëåìåíòàðíûå êîíúþíêöèè.Ñëåäóåò ïîÿñíèòü òåðìèí ýëåìåíòàðíàÿ êîíúþíêöèÿ. Ïóñòü íàì çàäàí íàáîð ïåðåìåííûõx1 , . .
. , xn .Ýëåìåíòàðíîé êîíúþíêöèåé íàçûâàåòñÿ ôóíêöèÿf (xi1 , . . . , xin ) = xi1 · . . . · xik ,ïðèk > 1,è ôóíêöèÿ òîæäåñòâåííàÿ åäèíèöà. Òîãäà âñåãî ýëåìåíòàðíûõ êîíúþíêöèé áóäåò1 + Cn1 + . . . + Cnn = 2n .Òåîðåìà. (Æåãàëêèí) Ëþáàÿ ôóíêöèÿ f ∈ P2 åäèíñòâåííûì îáðàçîì ïðåäñòàâëÿåòñÿ â âèäåïîëèíîìà Æåãàëêèíà.Ïðèìåð. f (x, y) = x ∨ y.x ∨ y = f (x, y) = x(f (1, y) + f (0, y)) + f (0, y) = x(1 + y) + y = xy + x + y.Îïðåäåëåíèå.Ñèñòåìà=íàçûâàåòñÿ ïîëíîé, åñëèÌû óæå äîêàçàëè, ÷òî ñèñòåìà[=] = P2 .{xy, x + y, 0, 1} ïîëíà.
Òåïåðü, íàì èíòåðåñíî áóäåò ëè ïîëíàñâåäåíèÿ , êîòîðîé ìîæåò äàòü îòâåò íà íàø âîïðîñ.êàêàÿ-íèáóäü äðóãàÿ ñèñòåìà? Èçëîæèì ìåòîä38= = {f1 , . . . , fn } ÿâëÿåòñÿ ïîëíîé, è çàäàíà ñèñòåìà i = {g1 , . . . , gk }.f1 , . . . , fn âûðàæàþòñÿ ÷åðåç ôóíêöèè g1 , . . . , gk ,2) âñå ôóíêöèè gi ïðèíàäëåæàò çàìûêàíèþ ñèñòåìû =,ñèñòåìà i ïîëíà.Ïóñòü ñèñòåìàÅñëè1) ôóíêöèèòîÏðèìåð.Ïîêàæåì, ÷òî ñèñòåìà{xy, x}ÿâëÿåòñÿ ïîëíîé. Ïðîâåðèì ïåðâûé ïóíêò.x + y = xy · xy,0 = xx, 1 = xx.x = x + 1 ∈ [{xy, x + y, 0, 1}].{xy, x} ïîëíà.Çàìåòèì, ÷òîñèñòåìàÎïðåäåëåíèå.Çíà÷èò âûïîëíÿåòñÿ âòîðîé ïóíêò.
Ñëåäîâàòåëüíî,Ìíîæåñòâî ëèíåéíûõ ôóíêöèé íàçûâàåòñÿ ìíîæåñòâî ñëåäóþùåãî âèäàL ={f (x1 , . . . , xn ) = c0 + c1 x1 + . . . + cn xn , ci ∈ {0, 1}, n > 1}Ïåðå÷èñëèì ñâîéñòâà ìíîæåñòâà1.2. Ôóíêöèè3.L:[L] = L.0, 1, x, x + y, x + 1 ∈ L, à ôóíêöèÿ xy ∈/ L.f (x1 , . . . , xn ) ñóùåñòâåííî çàâèñèò îòÅñëè ôóíêöèÿâñåõ ñâîèõ ïåðåìåííûõ, òî îíà èìååòñëåäóþùèé âèäf (x1 , . . .
, xn ) = c0 + x1 + . . . + xnÑëåäñòâèå 3.Ïóñòü[{0, 1, x + y}] = L.F ⊆ P2 . Ââåäåì ñëåäóþùåå îáîçíà÷åíèå. Ó ôóíêöèè, ïðèíàäëåæàùåé P2 , íî íå ïðèíàäëåF , áóäåì ïðèïèñûâàòü íèæíèé èíäåêñ F . Ò.å. fF (x1 , . . . , xn ) ∈ P2 , è fF (x1 , . .
. , xn ) ∈/æàùåé ñèñòåìåF.Ëåììà 1. Ïóñòü íàì çàäàíà ôóíêöèÿ fL (x1 , . . . , xn ), n > 2. Òîãäà ïîäñòàíîâêîé 0 è ôóíêöèèâèäà x ìîæíî ïîëó÷èòü gL (x, y).Äîêàçàòåëüñòâî.Ðàññìîòðèì ïðåäñòàâëåíèå ôóíêöèèfL (x1 , . . . , xn )â âèäå ïîëèíîìà Æåãàë-êèíà. Âîçüìåì ýëåìåíòàðíóþ êîíúþíêöèþ, â êîòîðîé êîëè÷åñòâî ïåðåìåííûõ åñòü ÷èñëîk > 2.Ïîñêîëüêó ôóíêöèÿ íåëèíåéíàÿ, òî ÿñíî, ÷òî òàêàÿ êîíúþíêöèÿ ñóùåñòâóåò. Áåç îãðàíè÷åíèÿ îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî ýòà êîíúþíêöèÿ åñòüx1 x2 · . . . · xk .ÒîãäàfL (x, y, .
. . , y , 0, . . . , 0) = g(x, y) = xy + ax + by + c,| {z }k−1òàê êàêy · y = y.×òî è òðåáîâàëîñü äîêàçàòü.Ñëåäñòâèå 4.xy ∈ [{fL , 0, x}]Äîêàçàòåëüñòâî.Ïðèìåíÿÿ ëåììó ïîëó÷àåì ôóíêöèþgL (x, y) = xy + ax + by + cgL (b + x, a + y) = xy + xa + by + ba + ax + ab + by + ba + c = xy + (c + ab).Åñëèc + ab 6= 0,òî ïðèìåíèì ôîðìóëóx = x + 1.Ñëåäñòâèå äîêàçàíî.Ââåäåì íîâûå îáîçíà÷åíèÿ.K = {f (x1 , . . .
, xn ) = c0 (c1 ∨ x1 ) · . . . · (cn ∨ xn ), ci ∈ {0, 1}, i = 1 . . . n, n > 1}K:[K] = K .0, 1, x, xy ∈ K, x ∨ y ∈/ K.Ñâîéñòâà ñèñòåìû ôóíêöèé1.2.393.[{0, 1, xy}] = K .D = {f (x1 , . . . , xn ) = c0 ∨ (c1 x1 ) ∨ . . . ∨ (cn xn ), ci ∈ {0, 1}, i = 1 . . . n, n > 1}D:[D] = D.0, 1, x, x ∨ y ∈ D, xy ∈/ D.[{0, 1, x ∨ y}] = D.Ñâîéñòâà ñèñòåìû ôóíêöèé1.2.3.Óïðàæíåíèå.Ïðîâåðèòü ñâîéñòâà äëÿ ñèñòåìKèD.Ââåäåì îïðåäåëåíèÿ ìîíîòîííûõ ôóíêöèé. Äëÿ ýòîãî çàäàäèì ÷àñòè÷íûé ïîðÿäîê ìíîæåñòâàBn.Ïóñòüα = (α1 , .
. . , αn ), β = (β1 , . . . , βn ) ∈ B n .Òîãäàα 6 β , åñëè α1 6 β1 , . . . , αn 6 βn .(0, 1) è (1, 0).Îòìåòèì, ÷òî íå âñå íàáîðû ñðàâíèìû. Íàïðèìåð, íàáîðûÎïðåäåëåíèå.íåíî íåðàâåíñòâîff (α) 6 f (β).Ôóíêöèÿíàçûâàåòñÿ ìîíîòîííîé, åñëèÌíîæåñòâî âñåõ ìîíîòîííûõ ôóíêöèé îáîçíà÷àåòñÿ∀α, β ∈ B nòàêèõ, ÷òîα 6 β,âûïîë-M.Ñâîéñòâà ìíîæåñòâà ìîíîòîííûõ ôóíêöèé:1.2.3.[M ] = M.0, 1, x, x ∨ y, xy ∈ M, x + 1, x → y, x + y ∈/ M.[{0, 1, x ∨ y, xy}] = M.Äîêàçàòåëüñòâî.Äëÿ ëþáîé ôóíêöèè èçMñïðàâåäëèâî ïðåäñòàâëåíèåf (x1 , .
. . , xn ) = x1 f (1, x2 , . . . , xn ) ∨ f (0, x2 , . . . , xn ).(0, x2 , . . . , xn )×òîáû äîêàçàòü åãî ïðîâåðèì çíà÷åíèÿ ïðàâîé è ëåâîé ÷àñòåé íà íàáîðàõ(1, x2 , . . . , xn ).Ïðèèx1 = 00f (1, x2 , . . . , xn ) ∨ f (0, x2 , . .
. , xn ) = f (0, x2 , . . . , xn ).Ïðèx1 = 11f (1, x2 , . . . , xn ) ∨ f (0, x2 , . . . , xn ) = f (1, x2 , . . . , xn ) ∨ f (0, x2 , . . . , xn ) = f (1, x2 , . . . , xn )â ñèëó ìîíîòîííîñòèf.Ýòî ïðåäñòàâëåíèå è äîêàçûâàåò äàííîå ñâîéñòâîM.Ëåììà 2. Ïóñòü çàäàíû ôóíêöèè fK , fD ∈ M . Òîãäà x ∨ y ∈ [{1, fK }], xy ∈ [{0, fD }].Äîêàçàòåëüñòâî.Ïóñòü ó ôóíêöèèfK (x1 , . . . , xn ) ∈ Mâñå ïåðåìåííûå ñóùåñòâåííûå. Òîãäàñóùåñòâóåò íàáîð, ñîäåðæàùèé ðîâíî îäèí íîëü(áåç îãðàíè÷åíèÿ îáùíîñòè áóäåì ñ÷èòàòü, ÷òî ýòîíàáîð(0, 1, . .
. , 1))òàêîé, ÷òî çíà÷åíèå ôóíêöèè íà íåì ðàâíî åäèíèöå. Åñëè ýòî íå òàê, òîãäàfK (0, 1, . . . , 1) = fK (1, 0, . . . , 1) = . . . = fK (1, 1, . . . , 0) = 0.fK , ëèáî fK = x1 · . . . · xn , ëèáî fK = 0.  îáîèõ ñëó÷àÿõ ïîëó÷àåìfK ∈/ K . Äàëåå, ïîñêîëüêó ïåðåìåííàÿ x1 ñóùåñòâåííàÿ, òî ñóùåñòâóåòα2 , . . . , αn ∈ {0, 1}, ÷òîÀ, çíà÷èò, â ñèëó ìîíîòîííîñòèïðîòèâîðå÷èå ñ òåì, ÷òîòàêîé íàáîð0 = fK (0, α2 , . . . , αn ) 6= fK (1, α2 , . . . , αn ) = 1.Ïðè÷åì (α2 , .
. . , αn ) 6= (1, 1, . . . , 1). Áåç îãðàíè÷åíèÿ(0, . . . , 0, 1, . . . , 1). Îòñþäà, ëåãêî ñëåäóåò ðàâåíñòâî| {z }îáùíîñòè áóäåì ñ÷èòàòü, ÷òîk>1x ∨ y = fK (x, y, . . . , y , 1, . . . , 1).| {z }k40(α2 , . . . , αn ) =×òîáû äîêàçàòü åãî, íóæíî ïîäñòàâèòü âñåâîçìîæíûå çíà÷åíèÿ ïåðåìåííûõxèyè óáåäèòüñÿ, ÷òîðàâåíñòâî äåéñòâèòåëüíî âûïîëíÿåòñÿ.Àíàëîãè÷íûì îáðàçîì äîêàçûâàåòñÿ óòâåðæäåíèå î ïðèíàäëåæíîñòè êîíúþíêöèè çàìûêàíèþñèñòåìû{0, fD }.Ëåììà äîêàçàíà.Òåîðåìà 1.1 Ïóñòü F çàìêíóòûé êëàññ Ïîñòà, 0, 1 ∈ F.
Òîãäà êëàññ F ÿâëÿåòñÿ êîíå÷íîïîðîæäåííûì.Äîêàçàòåëüñòâî.Äîêàçàòåëüñòâî ïðåäñòàâëÿåò ñîáîé ïîñëåäîâàòåëüíîå ðàññìîòðåíèÿ âñåâîç-ìîæíûõ ñëó÷àåâ.1. Ëþáàÿ ôóíêöèÿ÷àòü ýòîò êëàññ2.F * C,à)á)3.f ∈FC.íå èìååò ñóùåñòâåííûõ ïåðåìåííûõ. Òîãäàè ëþáàÿ ôóíêöèÿ èçF * M.F ⊆ M.ÒîãäàFèìååò íå áîëåå îäíîé ñóùåñòâåííîé ïåðåìåííîé.F = [{0, 1, x}].Áóäåì îáîçíà÷àòü ýòîò êëàññÒîãäàF = [{0, 1, x}] = UT5.U.M = U M.F * U.à)F ⊆ K.ÒîãäàF = [{0, 1, xy}].á)F ⊆ D.ÒîãäàF = [{0, 1, x ∨ y}].â)F ⊆ L.ÒîãäàF = [{0, 1, x + y}].Ïóíêòû à)-â) ñëåäóþò èç ñîîòâåòñòâóþùèõ ñâîéñòâ êëàññîâ4.F = [{0, 1}]. Áóäåì îáîçíà-SK, D, L.SF * K D L, F ⊆ M.
Òîãäà ñóùåñòâóþò ôóíêöèè fK , fD , fL ∈ F. Ñëåäîâàòåëüíî, x ∨ y, xy ∈[{0, 1, fK , fD }]. Çíà÷èò, F = [{0, 1, x ∨ y, xy}] = M.S S SF * K D L M. Ò.å. ñóùåñòâóåò ôóíêöèÿ fM (x1 , . . . , xn ). Ïóñòü âñå å¼ ïåðåìåííûå ñóùånñòâåííûå. Ïîñêîëüêó îíà íå ÿâëÿåòñÿ ìîíîòîííîé, òî ñóùåñòâóþò íàáîðû α, β ∈ B òàêèå, ÷òîα 6= β, α 6 β , è fM (α) > fM (β). Ïðè ýòîì, òàê êàê α 6= β , òî ñóùåñòâóåò òàêîå i, ÷òî αi < βi .Ñëåäîâàòåëüíî, åñëè â êà÷åñòâå àðãóìåíòà ôóíêöèè âçÿòü íàáîð (α1 , . . . , αi−1 , x, αi+1 , . .
. , αn ),òî ïîëó÷èì ôóíêöèþ óæå îò îäíîé ïåðåìåííîé g(x) ðàâíóþ x. Òåì ñàìûì ìû ïîëó÷èëè, ÷òîx ∈ [{0, 1, fM }]. Ïîëüçóÿñü ñëåäñòâèåì 4 ïîëó÷àåì, ÷òî xy ∈ [{0, 1, fL , x}]. Ñèñòåìà {0, 1, x, xy}ïîðîæäàåò P2 .Òåîðåìà äîêàçàíà.Ñëåäñòâèå 5.Êëàññû Ïîñòà, ñîäåðæàùèå 0 è 1, èñ÷åðïûâàþòñÿ ñëåäóþùèì ñïèñêîìP2 , M, L, K, D, U, U M, C.41Ëåêöèÿ 11.Íàïîìíèì, ÷òî íà ïðîøëîé ëåêöèè ìû ïîëó÷èëè ñëåäóþùèå âûðàæåíèå ïðîèçâîëüíîé ìîíîòîííîé ôóíêöèè.f ∈ M,òîãäàf (x1 , . . .
, xn ) = x1 f (1, x2 , . . . , xn ) ∨ f (0, x2 , . . . , xn ).Ñëåäñòâèå 1. Åñëè f ∈ M, f 6≡ 0, 1. Òîãäà f ∈ [{x ∨ y, xy}].Êðîìå òîãî, íà ïðîøëîé ëåêöèè ìû äîêàçàëè ñëåäóþùóþ ëåììó.Ëåììà 1. Ïóñòü ôóíêöèè fK , fD ∈ M. Òîãäà x ∨ y ∈ [{1, fK }], xy ∈ [{0, fD }].Òåïåðü âûÿñíèì â êàêèõ ñëó÷àÿõ ìîæíî ãîâîðèòü, ÷òîf ∈ [=].Ëåììà 2.
Ïóñòü = ⊆ P2 , x ∨ y ∈ [=]. Åñëè f ∈ [= ∪ {0}], g ∈ [=] è g 6 f, òî f ∈ [=].Äîêàçàòåëüñòâî.Ïóñòü ôîðìóëà Ô çàäàåò ôóíêöèþy,0fíàä= ∪ {0}.Çàìåíèì â ôîðìóëå Ô íîëü íà ïåðåìåííóþ0è îáîçíà÷èì åå Ô . Ôîðìóëà Ô çàäàåò íåêîòîðóþ ôóíêöèþh(y, x1 , . . . , xn )íàä=.Ïðè ýòîìh(0, x1 , . . .
, xn ) = f (x1 , . . . , xn ).Ôóíêöèÿf(1)áóäåò âûðàæàòüñÿ ñëåäóþùèì îáðàçîìf (x1 , . . . , xn ) = g(x1 , . . . , xn ) ∨ h(g(x1 , . . . , xn ), x1 , . . . , xn )(2)α ïðîèçâîëüíûé íàáîð èç B n . Åñëè g(α) = 0, òî ðàâåíñòâî (2) âûïîëíåíî â ñèëó (1). Ïóñòüg(α) = 1, òîãäà, òàê êàê g 6 f, f (α) = 1 è, ñëåäîâàòåëüíî, ðàâåíñòâî (2) âûïîëíåíî íà âñåõ íàáîðîânèç B . Çíà÷èò,f ∈ [{g, x ∨ y, h}] ⊆ [=].ÏóñòüËåììà äîêàçàíà.Îïðåäåëåíèå.16i6nèf (x1 , . . . , xn )f (x1 , . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
