С.С. Марченков - Избранные главы дискретной математики (1124120), страница 3
Текст из файла (страница 3)
Çàìûêàíèå ìíîæåñòâàQ áóäåì îáîçíà÷àòü ÷åðåç [Q]. Ìíîæåñòâî ôóíêöèé Q íàçîâåì (), åñëè [Q] = Q. Çàìêíóòûå ìíîæåñòâà ïðèíÿòîòàêæå íàçûâàòü.Íåòðóäíî óáåäèòüñÿ, ÷òî îïåðàöèÿ çàìûêàíèÿ îáëàäàåò ñëåäóþùèìèñâîéñòâàìè (äàëåå Q, R ïðîèçâîëüíûå ìíîæåñòâà ôóíêöèé èç Pk ):Çàìûêàíèåìöèîíàëüíî çàìêíóòûìçàìêíóòûìè êëàññàìè1. Q ⊆ [Q];10ôóíê-2. Åñëè Q ⊆ R, òî [Q] ⊆ [R];3. [[Q]]=[Q].ïîðîæïîðîæäàåòïîëíàêîíå÷íî ïîðîæäàåìûìÁàçèñîìÏóñòü Q çàìêíóòûé êëàññ è R ⊆ Q.
Ãîâîðÿò, ÷òî R ÿâëÿåòñÿâ êëàññå Q (èëè RQ, èëè Râ Q),åñëè [R] = Q. Çàìêíóòûé êëàññ Q íàçûâàåòñÿ,åñëè îí èìååò êîíå÷íóþ ïîðîæäàþùóþ ñèñòåìó.çàìêíóòîãîêëàññà íàçûâàåòñÿ òàêàÿ ïîðîæäàþùàÿ åãî ñèñòåìà, êîòîðàÿ ïåðåñòàåòáûòü ïîðîæäàþùåé ñèñòåìîé ïîñëå óäàëåíèÿ ëþáîé ïðèíàäëåæàùåé åéôóíêöèè.äàþùåé ñèñòåìîéÓÏÐÀÆÍÅÍÈß(n)Ïîäñ÷èòàòü ÷èñëî ôóíêöèé â ìíîæåñòâå Pk , ñóùåñòâåííî çàâèñÿùèõ îò âñåõ ïåðåìåííûõ.1. 2. Ñòàíäàðòíûå ïîëíûå ñèñòåìûÏóñòü k > 2. Äëÿ ëþáîãî i ∈ Ek ïîëîæèìJi (x) =k − 1, åñëè x = i,0â ïðîòèâíîì ñëó÷àå.Íàðÿäó ñ ôóíêöèÿìè J0 , . . . , Jk−1 â òåîðåìå 1.1 ðàññìàòðèâàþòñÿ ñëåäóþùèå ôóíêöèè èç Pk : êîíñòàíòû 0, 1, .
. . , k − 1 (èõ ìîæíî ñ÷èòàòüôóíêöèÿìè îò îäíîé ïåðåìåííîé), ìèíèìóì min(x1 , x2 ) è ìàêñèìóìmax(x1 , x2 ). Ôóíêöèè min è max îò îò íåñêîëüêèõ ïåðåìåííûõ ïîëó÷àþòñÿ èç ñîîòâåòñòâóþùèõ äâóìåñòíûõ ôóíêöèé î÷åâèäíûìè ñóïåðïîçèöèÿìè.Òåîðåìà 1.1(î ðàçëîæåíèè ôóíêöèè ïî ïåðâîé ïåðåìåííîé).ëþáîé ôóíêöèè f (x1, . .
. , xn) èç Pk ñïðàâåäëèâî ïðåäñòàâëåíèåÄëÿf (x1 , . . . , xn ) = max{min(J0 (x1 ), f (0, x2 , . . . , xn )), . . .. . . , min(Jk−1 (x1 ), f (k − 1, x2 , . . . , xn ))}.(1.2)Ïðèäàâàÿ ïåðåìåííîé x1 ïîñëåäîâàòåëüíî çíà÷åíèÿ 0, 1, . . . , k − 1, íåïîñðåäñòâåííî óáåæäàåìñÿ â ñïðàâåäëèâîñòè ñîîòíîøåíèÿ (1.2).Äîêàçàòåëüñòâî.Ñëåäñòâèå 1(î ðàçëîæåíèè ôóíêöèè ïî âñåì ïåðåìåííûì).áîé ôóíêöèè f (x1, . . . , xn) èç Pk èìååò ìåñòî ïðåäñòàâëåíèå11Äëÿ ëþ-f (x1 , . .
. , xn ) = max{min(J0 (x1 ), . . . , J0 (xn ), f (0, . . . , 0)),min(J0 (x1 ), . . . , J0 (xn−1 ), J1 (xn ), f (0, . . . , 0, 1)), . . .. . . , min(Jk−1 (x1 ), . . . , Jk−1 (xn ), f (k − 1, . . . , k − 1))}. (1.3)Ïðèìåíèì ðàçëîæåíèå (1.2) ïî ïåðåìåííîé x2 êôóíêöèÿì f (0, x2 , . . . , xn ), . .
. , f (k−1, x2 , . . . , xn ), çàòåì ïî ïåðåìåííîéx3 ê îáðàçîâàâøèìñÿ ôóíêöèÿìÄîêàçàòåëüñòâî.f (0, 0, x3 , . . . , xn ), f (0, 1, x3 , . . . , xn ), . . . , f (k − 1, k − 1, x3 , . . . , xn )è ò.ä. Ïðè ýòîì èñïîëüçóåì ëåãêî ïðîâåðÿåìîå òîæäåñòâîmin(x, max(y, z)) = max(min(x, y), min(x, z)).Ñîîòíîøåíèå (1.3) ìîæíî ïðîâåðèòü è íåïîñðåäñòâåííî, ïîäñòàâëÿÿ âëåâóþ è ïðàâóþ ÷àñòè (1.3) ïîñëåäîâàòåëüíî âñå k n íàáîðîâ èç Ekn .Ñëåäñòâèå 2.Ïðè ëþáîì k > 2 ñèñòåìà ôóíêöèé0, 1, .
. . , k − 1, J0 (x), . . . , Jk−1 (x), min(x1 , x2 ), max(x1 , x2 )(1.4)ïîëíà â êëàññå Pk .Ôîðìóëó (1.3) ìîæíî çàïèñàòü áîëåå êîìïàêòíî, åñëè ôóíêöèþ maxîáîçíà÷èòü ÷åðåç ∨, à ôóíêöèþ min ÷åðåç &:_f (x1 , . . . , xn ) =Jσ1 (x1 ) & . . . & Jσn (xn ) & f (σ1 , . . . , σn ). (1.5)(σ1 ,...,σn )∈EknÏðåäñòàâëåíèå (1.5) åñòü îáîáùåíèå õîðîøî èçâåñòíîãî ïðåäñòàâëåíèÿáóëåâûõ ôóíêöèé â âèäå ñîâåðøåííîé äèçúþíêòèâíîé íîðìàëüíîé ôîðìû. Ïðè ýòîì ôóíêöèþ f ìîæíî ñ÷èòàòü îòëè÷íîé îò òîæäåñòâåííîãîíóëÿ, à â ôîðìóëå (1.5) ñëåäóåò îïóñòèòü äèçúþíêòèâíûå ñëàãàåìûå, âñîñòàâ êîòîðûõ âõîäèò ñîìíîæèòåëè f (σ1 , .
. . , σn ), ðàâíûå 0.Îáîçíà÷èì ÷åðåç x̄ ôóíêöèþ x + 1, ãäå ñëîæåíèåðàññìàòðèâàåòñÿ ïî ìîäóëþ k . Îòìåòèì, ÷òî ïðè k = 2 îòðèöàíèå Ïîñòàñîâïàäàåò ñ áóëåâûì îòðèöàíèåì x̄.îòðèöàíèå ÏîñòàÑëåäñòâèå 3.ïîëíà â êëàññå Pk .Ïðè ëþáîì k > 2 ñèñòåìà ôóíêöèé {x̄, max(x1, x2)}Ïîêàæåì, êàê ñóïåðïîçèöèÿìè ôóíêöèé ñèñòåìû{x̄, max(x1 , x2 )} ïîëó÷èòü âñå ôóíêöèè ñèñòåìû (1.4).Äîêàçàòåëüñòâî.12Ïðåæäå âñåãî, ñóïåðïîçèöèÿìè ôóíêöèè x̄ îáðàçóåì ôóíêöèèx + 2, x + 3, . . .
, x + k − 1 (âñå ñëîæåíèÿ ïðîâîäÿòñÿ ïî ìîäóëþ k ) èïðîâåðÿåì, ÷òîmax(x, x + 1, . . . , x + k − 1) = k − 1.Èç êîíñòàíòû k − 1 ñ ïîìîùüþ ôóíêöèè x̄ ïîëó÷àåì âñå îñòàëüíûå êîíñòàíòû: 0 = (k − 1) + 1, 1 = 0 + 1, . . .. Äàëåå ïðîâåðÿåì, ÷òîJ0 (x) = max(x, x + 1, . . . , x + k − 2) + 1. ñàìîì äåëå, åñëè x = 0, òî max(0, 1, . . . , k − 2) + 1 = (k − 2) + 1 = k − 1.Åñëè æå x 6= 0, òî x + (k − 1 − x) = k − 1 è ïîòîìó max(x, x + 1, .
. . , x +k − 2) + 1 = (k − 1) + 1 = 0 (ïî ìîäóëþ k ).Òåïåðü ïðè i 6= 0 ïîëó÷àåì Ji (x) = J0 (x+k −i). Åñëè æå 0 6 i 6 k −2,òî ïóñòük − 1 − i, åñëè x = i,gi (x) =0â ïðîòèâíîì ñëó÷àå(îòìåòèì, ÷òî ôóíêöèÿ g0 ñîâïàäàåò ñ ôóíêöèåé J0 ). Ëåãêî óáåäèòüñÿ âòîì, ÷òî èìååò ìåñòî òîæäåñòâîgi (x) = k − i + max(Ji (x), i).îòðèöàíèå Ëóêàñåâè÷à), ïîëó-Îáîçíà÷èâ ÷åðåç ∼ x ôóíêöèþ k − 1 − x (÷àåì∼ x = max(g0 (x), . . .
, gk−2 (x)).Îñòàåòñÿ çàìåòèòü, ÷òîmin(x1 , x2 ) =∼ max(∼ x1 , ∼ x2 ).Ñëåäñòâèå äîêàçàíî.ôóíêöèÿ Âåááà).Îáîçíà÷èì ÷åðåç V (x1 , x2 ) ôóíêöèþ max(x1 , x2 ) + 1 (Ñëåäñòâèå 4.êëàññà Pk .Ïðè ëþáîì k > 2 ôóíêöèÿ V (x1, x2) îáðàçóåò áàçèñÈìååì V (x, x) = x̄. Äàëåå ñóïåðïîçèöèÿìè ôóíêöèè x̄ îáðàçóåì ôóíêöèþ x + k − 1. Òåïåðü ïîëó÷àåì V (x1 , x2 ) + k − 1 =max(x1 , x2 ). Ñëåäñòâèå äîêàçàíî.Äîêàçàòåëüñòâî.13Åùå îäíî ïðåäñòàâëåíèå ôóíêöèé k -çíà÷íîé ëîãèêè îñíîâàíî íà ôóíêöèÿõ ñèñòåìû0, 1, . .
. , k − 1, x1 + x2 (mod k), x1 · x2 (mod k), j0 (x), . . . , jk−1 (x), (1.6)ãäåji (x) =Òåîðåìà 1.2.ïðåäñòàâëåíèå1, åñëè x = i,0 â ïðîòèâíîì ñëó÷àå.Äëÿ ëþáîé ôóíêöèè f (x1, . . . , xn) èç Pk èìååò ìåñòîXf (x1 , . . . , xn ) =jσ1 (x1 ) · . . . · jσn (xn ) · f (σ1 , . . . , σn ),(1.7)(σ1 ,...,σn )∈Eknãäå ñóììèðîâàíèå ïðîâîäèòñÿ ïî ìîäóëþ k.Äîêàçàòåëüñòâîëåãêî ïîëó÷àåòñÿ íåïîñðåäñòâåííîé ïðîâåðêîé.Ñëåäñòâèå 1.Ïðè ëþáîì kÑëåäñòâèå 2.Ïðè ëþáîì k > 3 ñèñòåìà ôóíêöèé {j0(x), x1 + x2}êëàññå Pk .ïîëíà â êëàññå Pk .> 2ñèñòåìà ôóíêöèé (1.6) ïîëíà âÊîíñòàíòó 0 ïîëó÷àåì â âèäå x + .
. . + x (k ðàç),êîíñòàíòó 1 â âèäå j0 (0). Çàòåì èç êîíñòàíòû 1 è ôóíêöèè x1 + x2ïîëó÷àåì âñå îñòàëüíûå êîíñòàíòû. Äàëåå ïðîâåðÿåì, ÷òî âûïîëíÿþòñÿñîîòíîøåíèÿÄîêàçàòåëüñòâî.ji (x) = j0 (x + k − i) ïðè 1 6 i 6 k − 1,ji (x1 ) · jl (x2 ) = j2 (ji (x1 ) + jl (x2 )) ïðè 0 6 i, l 6 k − 1.Åñëè n > 3 è σ1 , . . . , σn ∈ Ek , òî ôóíêöèþ jσ1 (x1 )·. . .·jσn (xn ) ïîëó÷àåìïîñëåäîâàòåëüíûìè ïîäñòàíîâêàìè ôóíêöèéjσ2 (x2 ) · j1 (y), . . . , jσn−2 (xn−2 ) · j1 (y), jσn−1 (xn−1 ) · j1 (y), jσn (xn )âìåñòî ïåðåìåííîé y â ôóíêöèèjσ1 (x1 ) · j1 (y),jσ1 (x1 ) · jσ2 (x2 ) · j1 (y), . . .. .
. , jσ1 (x1 ) · . . . · jσn−2 (xn−2 ) · j1 (y), jσ1 (x1 ) · . . . · jσn−1 (xn−1 ) · j1 (y). çàêëþ÷åíèå äîêàçàòåëüñòâà çàìåòèì, ÷òî ñóììó â ïðàâîé ÷àñòè ðàâåíñòâà (1.7) ìîæíî ¾ñîáðàòü¿ èç ñëàãàåìûõ âèäà jσ1 (x1 ) · . . . · jσn (xn ) ñïîìîùüþ ôóíêöèè x1 + x2 .14Ïóñòü k > 2, R êîììóòàòèâíîå êîëüöî ñ åäèíèöåé,îïðåäåëåííîå íà ìíîæåñòâå Ek . Òîãäà ëþáóþ ôóíêöèþ èç Pk ìîæíîïðåäñòàâèòü ïîëèíîìîì íàä êîëüöîì R â òîì è òîëüêî òîì ñëó÷àå,êîãäà R ïîëå.Òåîðåìà 1.3.Ïóñòü R ïîëå.
Áóäåì ïðåäïîëàãàòü, ÷òî 0 íåéòðàëüíûé ýëåìåíò àääèòèâíîé ãðóïïû ïîëÿ R è 1 íåéòðàëüíûé ýëåìåíò ìóëüòèïëèêàòèâíîé ãðóïïû ïîëÿ R. Ëþáîé íåíóëåâîé ýëåìåíò aïîëÿ R ëåæèò â ìóëüòèïëèêàòèâíîé ãðóïïå ïîëÿ R, èìåþùåé ïîðÿäîêk − 1. Ïîýòîìó ñïðàâåäëèâî ñîîòíîøåíèå ak−1 = 1. Âìåñòå ñ òåì î÷åâèäíî, ÷òî 0k−1 = 0. Ñëåäîâàòåëüíî, äëÿ ëþáîãî ýëåìåíòà x èç Ek èìååìÄîêàçàòåëüñòâî.j0 (x) = 1 − xk−1 ,ãäå çíàê − ñèìâîëèçèðóåò âçÿòèå îáðàòíîãî ýëåìåíòà â àääèòèâíîé ãðóïïå ïîëÿ R.
Òàêèì îáðàçîì, ôóíêöèÿ j0 ðåàëèçóåòñÿ ïîëèíîìîì íàä ïîëåìR. Ýòî óòâåðæäåíèå âåðíî è äëÿ îñòàëüíûõ ôóíêöèé ji , ïîñêîëüêóji (x) = j0 (x − i)(1 6 i 6 k − 1).Èñïîëüçóÿ òåïåðü â ïðåäñòàâëåíèè (1.7) â êà÷åñòâå ñëîæåíèÿ è óìíîæåíèÿ ñîîòâåòñòâóþùèå îïåðàöèè ïîëÿ R, ïîëó÷àåì, ÷òî âñÿêóþ ôóíêöèþèç Pk ìîæíî ðåàëèçîâàòü ïîëèíîìîì íàä ïîëåì R.Ïðåäïîëîæèì, ÷òî êîëüöî R ïîëåì íå ÿâëÿåòñÿ. Ïîêàæåì, ÷òî â ýòîìñëó÷àå â êîëüöå R åñòü (íåíóëåâûå) äåëèòåëè íóëÿ. Ïðåäïîëîæèì, ÷òîýòî íå òàê. Ïîñêîëüêó R íå ÿâëÿåòñÿ ïîëåì, íàéäåòñÿ òàêîé íåíóëåâîéýëåìåíò a, ÷òî ïðè óìíîæåíèè a íà ëþáîé íåíóëåâîé ýëåìåíò (íàïðèìåð,ñïðàâà) ïîëó÷èòñÿ ýëåìåíò, îòëè÷íûé îò 1. Òàê êàê â êà÷åñòâå (ïðàâûõ)ñîìíîæèòåëåé ðàññìàòðèâàåòñÿ k − 1 ýëåìåíò, à â ðåçóëüòàòå óìíîæåíèÿïîëó÷àåòñÿ íå áîëåå k − 2 ýëåìåíòîâ, òî íàéäóòñÿ òàêèå ðàçëè÷íûå íåíóëåâûå ýëåìåíòû c1 , c2 , ÷òî a · c1 = a · c2 .
Èíûìè ñëîâàìè, a · (c1 − c2 ) = 0è ìû íàøäè äâà íåíóëåâûõ äåëèòåëÿ íóëÿ.Èòàê, ïóñòü äëÿ íåêîòîðûõ íåíóëåâûõ ýëåìåíòîâ b1 , b2 ïîëÿ R âûïîëíÿåòñÿ ðàâåíñòâî b1 · b2 = 0.Ïðåäïîëîæèì òåïåðü, ÷òî ôóíêöèÿ j0 ðåàëèçóåòñÿ ïîëèíîìîì íàäêîëüöîì R:j0 (x) = a0 + a1 x + . . . + as xs .Èç ðàâåíñòâà j0 (0) = 1 ñëåäóåò, ÷òî a0 = 1, à èç ðàâåíñòâb1 · b2 = 0 = j0 (b1 ) = 1 + a1 b1 + . . . + as bs115 ÷òî b1 åñòü äåëèòåëü ÷èñëà 1. Èíûìè ñëîâàìè, äëÿ íåêîòîðîãî ýëåìåíòà c èç Ek èìååì b1 · c = 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
