OK-metodichka-2010-part1 (1132792), страница 2
Текст из файла (страница 2)
Ïðåäïîëàãàåòñÿ, ÷òî âñå ýëåìåíòû êîíå÷íîãî ëèíåéíî óïîðÿäî÷åííîãî ìíîæåñòâà (A, τ ), ãäå|A| = t, ïðîíóìåðîâàíû ÷èñëàìè îòðåçêà [0, t) òàê, ÷òî äëÿëþáûõ a0 è a00 èç A íîìåð a0 íå áîëüøå, ÷åì íîìåð a00 òîãäàè òîëüêî òîãäà, êîãäà a0 τ a00 .Ïîä äèñêðåòíîé ôóíêöèåé ïîíèìàþò, îáû÷íî, îòîáðàæåíèå îäíîãî êîíå÷íîãî ìíîæåñòâà â äðóãîå. Òàê, ôóíêöèÿ íàä îòðåçêîì [0, k), ãäå k > 2, íàçûâàåòñÿk(ïðè k = 2 ), à ìíîæåñòâî âñåõ òàêèõ ôóíêöèé îáîçíà÷àåòñÿ ÷åðåç Pk .
Äèñêðåòíûå ôóíêöèè, êàê ïðàâèëî, ìîãóò áûòü îïèñàíû òàáëèöàìè.Òàê, áèíàðíàÿ ôóíêöèÿ f (x1 , x2 ) èç êîíå÷íîãî ëèíåéíî óïîðÿäî÷åííîãî ìíîæåñòâà A = {a1 , . . . , am } â êîíå÷íîå ìíîæåñòâî D ìîæåò áûòü çàäàíà ìàòðèöåé M, M ∈ Dm,m , ãäåM hi, ji = f (ai , aj ) ïðè âñåõ i, j èç îòðåçêà [1, m], è îáðàòíî.Ïóñòü X = {x1 , x2 , . . . , xn , . . . } ñ÷åòíûé óïîðÿäî÷åííûéïåðåñòàíîâî÷íîñòè÷àñòè÷íîãî ïîðÿäêà÷àñòè÷íî óïîðÿäî÷åííûì ìíîæåñòâîìðÿäî÷åííûì ìíîæåñòâîì-çíà÷íîé ëîãèêèëèíåéíî óïî-àëãåáðû ëîãèêèôóíêöèåé12Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûàëôàâèò ïåðåìåííûõ íàä ìíîæåñòâîì A è ïóñòü PA = PA (X) ìíîæåñòâî âñåõ ôóíêöèé íàä A îò ïåðåìåííûõ èç X.
Ïåðåìåííàÿ xi , i ∈ [1, n], íàçûâàåòñÿf (x1 , . . . , xn ) èç PA , åñëè f (α) = f (β) äëÿëþáûõ îòëè÷àþùèõñÿ òîëüêî ïî xi íàáîðîâ α è β èç An . Âïðîòèâíîì ñëó÷àå ïåðåìåííàÿ xi íàçûâàåòñÿïåðåìåííîé ôóíêöèè f . Ñ÷èòàåòñÿ, ÷òî ôóíêöèÿ f ñóùåñòâåííî (íåñóùåñòâåííî) çàâèñèò îò ïåðåìåííîé xi , åñëè xi ñóùåñòâåííàÿ (ñîîòâåòñòâåííî íåñóùåñòâåííàÿ) ïåðåìåííàÿôóíêöèè f . Íåñóùåñòâåííàÿ ïåðåìåííàÿ íå âëèÿåò íà çíà÷åíèå ôóíêöèè, ïîýòîìó, êàê îáû÷íî, ðàâåíñòâî ôóíêöèé áóäåì ðàññìàòðèâàòü ñ òî÷íîñòüþ äî äîáàâëåíèÿ èëè èçúÿòèÿíåñóùåñòâåííûõ ïåðåìåííûõ. Ïðè ýòîì äâå ôóíêöèè ñ÷èòàþòñÿ, åñëè îíè èìåþò îäíè è òå æå ñóùåñòâåííûåïåðåìåííûå è îäèíàêîâûì îáðàçîì îòîáðàæàþò äåêàðòîâóñòåïåíü A, ñâÿçàííóþ ñ èõ ñóùåñòâåííûìè ïåðåìåííûìè, âA. Áóäåì ãîâîðèòü, ÷òî f ôóíêöèÿ, åñëèîíà ñóùåñòâåííî çàâèñèò îò âñåõ ñâîèõ ïåðåìåííûõ.ìåííîé ôóíêöèèíåñóùåñòâåííîé ïåðå-ñóùåñòâåííîéðàâíûìèñóùåñòâåííàÿÏðåäïîëàãàåòñÿ, ÷òî ó íàñ èìååòñÿ ñ÷åòíûé àëôàâèò ôóíêöèîíàëüíûõ ñèìâîëîâ (ÔÑ) äëÿ îáîçíà÷åíèÿ ôóíêöèé èç PAè ÷òî â PA âûäåëåíî ¾áàçèñíîå¿ ìíîæåñòâî Á.
Äàäèì èíäóêòèâíîå îïðåäåëåíèå ôîðìóëû íàä Á è ðåàëèçóåìîé åþ ôóíêöèè, êîòîðîå, â îòëè÷èå îò [27], íåÿâíî ïðåäïîëàãàåò íàëè÷èåâ Á ôóíêöèè, òîæäåñòâåííî ðàâíîé ïåðåìåííîé. Çàìåòèì,÷òî ñ ñîäåðæàòåëüíîé òî÷êè çðåíèÿ ôîðìóëà ïðåäñòàâëÿåòñîáîé ñëîâî, ïîñòðîåííîå èç ÔÑ ¾áàçèñíûõ¿ ôóíêöèé, ñèìâîëîâ ïåðåìåííûõ è ¾ðàçäåëèòåëåé¿, êîòîðîå çàäàåò ïîñëåäîâàòåëüíîñòü âûïîëíåíèÿ îïåðàöèé ñóïåðïîçèöèè.ôîðìóëîé ãëóáèíûËþáàÿ ïåðåìåííàÿ xj èç X ñ÷èòàåòñÿ0Á, êîòîðàÿ ðåàëèçóåò ôóíêöèþ xj .
Åñëè ϕ (x1 , . . . , xk ) ∈ Á è äëÿ êàæäîãî i, i ∈ [1, k], îïðåäåëåíàôîðìóëà Fi ãëóáèíû qi íàä ìíîæåñòâîì Á, êîòîðàÿ ðåàëè-íàä ìíîæåñòâîì1.13Îñíîâíûå ïîíÿòèÿçóåò ôóíêöèþ fi èç PA , òî çàïèñü F âèäàF = ϕ (F1 , . . . , Fk )ôîðìóëîé ãëóáèíû(1.6)íàäÿâëÿåòñÿq = max {q1 , . . . , qk } + 1Á,êîòîðàÿ ðåàëèçóåò ôóíêöèþ f âèäà f = ϕ (f1 , . . . , fk ). Âñåçàïèñè, ïîëó÷åííûå â ðåçóëüòàòå óêàçàííîãî èíäóêòèâíîãîïîñòðîåíèÿ, è òîëüêî îíè ñ÷èòàþòñÿÁ. Ïðè ýòîì ôîðìóëû, ïîëó÷åííûå â ïðîöåññåèíäóêòèâíîãî ïîñòðîåíèÿ ôîðìóëû F, íàçûâàþòñÿ åå, à òå ïîäôîðìóëû F1 , . .
. , Fk , èç êîòîðûõ íà ïîñëåäíåì øàãå èíäóêòèâíîãî ïîñòðîåíèÿ ñòðîèòñÿ ôîðìóëàF âèäà (1.6), ñ÷èòàþòñÿ ååïîäôîðìóëàìè. Ïîä() ôîðìóëû F ïîíèìàåòñÿ ÷èñëî âõîæäåíèé â íåå ÔÑ (ñîîòâåòñòâåííî ñèìâîëîâ ïåðåìåííûõ), êîòîðîå îáîçíà÷àåòñÿ ÷åðåç L (F) (ñîîòâåòñòâåííî R (F)).ôîðìóëàìè íàä ìíîïîä-æåñòâîìôîðìóëàìèñëîæíîñòüþ ðàíãîìãëàâíûìèÔîðìóëû F0 è F00 , ðåàëèçóþùèå ðàâíûå ôóíêöèè f 0 èf 00 , íàçûâàþòñÿèëè, èíà÷å,. Ïðèýòîì ðàâåíñòâî âèäà t : F0 = F00 ñ÷èòàåòñÿ.Îáû÷íûì îáðàçîì ââîäÿòñÿ òîæäåñòâà, õàðàêòåðèçóþùèåñâîéñòâà êîììóòàòèâíîñòè, àññîöèàòèâíîñòè è äèñòðèáóòèâíîñòè áèíàðíûõ ôóíêöèé èç PA .ðàâíûìèýêâèâàëåíòíûìèòîæäåñòâîìÌíîæåñòâî âñåõ ôóíêöèé, ðåàëèçóåìûõ ôîðìóëàìè íàäÁ, íàçûâàåòñÿìíîæåñòâà Á.
Ïðè ýòîì ìíîæåñòâî Á ñ÷èòàåòñÿ, åñëè åãî çàìûêàíèå ñîâïàäàåò ñPA .  äàëüíåéøåì ëþáîå êîíå÷íîå ïîëíîå â PA áàçèñíîåìíîæåñòâî Á áóäåì íàçûâàòü. Ïðè ýòîì, â îòëè÷èåîò [27], â Á ìîãóò ïðèñóòñòâîâàòü ÔÀË, ïðè óäàëåíèè êîòîðûõ îñòàâøååñÿ ìíîæåñòâî ïðîäîëæàåò áûòü ïîëíûì.çàìûêàíèåìïîëíûìáàçèñîì142Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûÏðåäñòàâëåíèå ôóíêöèé àëãåáðû ëîãèêè ñïîìîùüþ äèçúþíêòèâíûõ íîðìàëüíûõ ôîðì(ÄÍÔ) è åãî ¾ãåîìåòðè÷åñêàÿ¿ èíòåðïðåòàöèÿ. Ñîâåðøåííàÿ ÄÍÔ è ðàçëîæåíèå Øåííîíà, êðèòåðèé åäèíñòâåííîñòè ÄÍÔÌíîæåñòâî B n , ãäå B = {0, 1} è n ∈ N, òî åñòü ìíîæåñòâî íàáîðîâ äëèíû n èç 0 è 1, îáû÷íî íàçûâàþòèëèðàçìåðíîñòè n. Îòíîøåíèå ïåðåñòàíîâî÷íîñòè ðàçáèâàåò êóá B n íà êëàññû ýêâèâàëåíòíîñòè (ñî÷åòàíèÿ) B0n , B1n , . . . , Bnn , ãäå Bin , i ∈ [0, n], òàê íàçûâàåìûéi-é ñëîé êóáà B n , òî åñòü ìíîæåñòâî íàáîðîâ ñ i åäèíèöàìè,nnè, î÷åâèäíî, |Bi | = i .Íà ìíîæåñòâå B n ââåäåì îòíîøåíèå ëåêñèêîãðàôè÷åñêîãî ëèíåéíîãî ïîðÿäêà, êîòîðîå çàäàåòñÿ âçàèìíî îäíîçíà÷íûì îòîáðàæåíèåì (íóìåðàöèåé) ν : B n → [0, 2n ) òàêèì, ÷òîåäèíè÷íûì êóáîìãèïåðêóáîìν (α1 , .
. . , αn ) =nXαi 2n−i .i=1Çàìåòèì, ÷òî äâîè÷íàÿ çàïèñü ÷èñëà ν (α) , α ∈ B n , äîïîëíåííàÿ ñëåâà íóëÿìè äî íàáîðà äëèíû n, ñîâïàäàåò ñα. Àíàëîãè÷íûì îáðàçîì ââîäèòñÿ ëåêñèêîãðàôè÷åñêèé ïîðÿäîê íà ìíîæåñòâå ([0, k))n ïðè k > 2. Ìíîæåñòâî íàáîðîâ,ÿâëÿþùååñÿ îáðàçîì îòðåçêà [a, b], ãäå [a, b] ⊆ [0, 2n ), ïðèîòîáðàæåíèè ν −1 , íàçûâàåòñÿBn.nÄëÿ íàáîðîâ α, β èç B ÷åðåç ρ (α, β) îáîçíà÷àåòñÿ òàêíàçûâàåìîå ðàññòîÿíèå Õýììèíãà ìåæäó íèìè, òî åñòü ÷èñëî òåõ ðàçðÿäîâ, â êîòîðûõ îíè îòëè÷àþòñÿ äðóã îò äðóãà.Ïðè ýòîì íàáîðû, íàõîäÿùèåñÿ íà ðàññòîÿíèè n, íàçûâàþòñÿ, à íàáîðû, îòëè÷àþùèåñÿ òîëüêî âîäíîì (i-ì) ðàçðÿäå, ñ÷èòàþòñÿ(ñîîòâåòñòâåííîi).
Ïðè ãåîìåòðè÷åñêîì èçîáðàæåíèè êóáà B n íà ïëîñêîñòè âåðøèíû i-ãî ñëîÿ îáû÷íî ðàñïîëàãàþòñÿ íà îäíîì è òîì æå ãîðèçîíòàëüíîì óðîâíå íàäîòðåçêîì êóáàïðîòèâîïîëîæíûìèñîñåäíèìè ïî -é ïåðåìåííîéñîñåäíèìè2.15Ïðåäñòàâëåíèå ÔÀË ñ ïîìîùüþ ÄÍÔB3`@@c` N2 c`@c`N3 (011)@ (101)@@ (010) @ N4c` N6 @c`` (001)N@5 c@@@`(111)(110)N1(100)(1111)`@@Γ(1222) ```@`@@ @ @@ @`@`` @` `@`@@ @ @@@ Γ(0221)`@`@`c@`Γ(0200)Γ(0010)@ x x1xx13I 2 6@ 4@`B4(000)(0000)a)b)Ðèñ. 2.1: B 3 è B 4 , ïðèìåðû ãðàíåéâåðøèíàìè (i − 1)-ãî ñëîÿ, i = 1, . . . , n, à ñîñåäíèå âåðøèíûñîåäèíÿþòñÿ îòðåçêàìè ïðÿìûõ (ñì.
ðèñ. 2.1). Ìíîæåñòâîíàáîðîâ êóáà B n , íàõîäÿùèõñÿ íà ðàññòîÿíèè t (íå áîëüøå,÷åì t) îò íàáîðà α, íàçûâàåòñÿ(ñîîòâåòñòâåííî)tα. Çàìåòèì, ÷òî i-é ñëîé êóáà B nÿâëÿåòñÿ ñôåðîé ðàäèóñà i ñ öåíòðîì â íàáîðå e0 = (0, . . . , 0)eè ñôåðîé ðàäèóñà (n − i) ñ öåíòðîì â íàáîðå 1 = (1, . . . , 1).Íà ìíîæåñòâå B n îáû÷íûì îáðàçîì ââåäåì îòíîøåíèå÷àñòè÷íîãî ïîðÿäêà 6 òàêîå, ÷òîðîì ðàäèóñà ñ öåíòðîìñôåðîéøà-α = (α1 , . . . , αn ) 6 β = (β1 , . . . , βn )òîãäà è òîëüêî òîãäà, êîãäà αi 6 βi ïðè âñåõ i ∈ [1, n].
Ïðèýòîì ñ÷èòàåòñÿ, ÷òî α < β , åñëè α 6 β è α 6= β , à íàáîðûα, β èç B n , äëÿ êîòîðûõ α 6 β èëè β 6 α (α β è β α),íàçûâàþòñÿ(ñîîòâåòñòâåííî).Äëÿ íàáîðà γ = (γ1 , . . . , γn ) äëèíû n íàä ìíîæåñòâîì[0, 2] ÷åðåç Γγ îáîçíà÷èì ìíîæåñòâî âñåõ òåõ íàáîðîâ α == (α1 , . . . , αn ) êóáà B n , äëÿ êîòîðûõ αi = γi ïðè âñåõ i ∈ñðàâíèìûìèíåñðàâíèìûìè16Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûx1010 x1 x1 10 1 0 10 0 1 1a)x1 x20 00 11 01 1&0001∨ ⊕ ∼ → | ↓0 0 1 1 1 11 1 0 1 1 01 1 0 0 1 01 0 1 1 0 0b)αef(00)(11)(01)(10)(0001)(0111)(0110)(1001)(1101)(1110)(1000)íàçâàíèå ôóíêöèè f ”0” (êîíñòàíòà íóëü) ”1” (êîíñòàíòà åäèíèöà) òîæäåñòâåííàÿ ôóíêöèÿ îòðèöàíèå êîíúþíêöèÿ (óìíîæåíèå) äèçúþíêöèÿ ñóììà ïî ìîäóëþ 2 ýêâèâàëåíòíîñòü èìïëèêàöèÿ øòðèõ Øåôôåðà ñòðåëêà Ïèðñàc)Ðèñ.
2.2: P2 (1) è ¾îñíîâíûå¿ ÔÀË èç P2 (2)2.Ïðåäñòàâëåíèå ÔÀË ñ ïîìîùüþ ÄÍÔ17ãðàíüþðàíãîì[1, n] òàêèõ, ÷òî γi 6= 2. Ìíîæåñòâî Γγ íàçûâàåòñÿêóáà B n , ÷èñëî (n − r), ðàâíîå ÷èñëó ”2” â íàáîðå γ , ñ÷èòàåòñÿýòîé ãðàíè, à ÷èñëî r åå. Çàìåòèì, ÷òî óêàçàííàÿ ãðàíü Γγ ïðåäñòàâëÿåò ñîáîé ïîäêóáðàçìåðíîñòè (n − r) êóáà B n è ñîñòîèò èç 2n−r íàáîðîâ, îòëè÷àþùèõñÿ äðóã îò äðóãà òîëüêî â òåõ ðàçðÿäàõ, â êîòîðûõðàñïîëîæåíû ñèìâîëû ”2” íàáîðà γ .
 ÷àñòíîñòè, ãðàíü ðàçìåðíîñòè 0 ïðåäñòàâëÿåò ñîáîé âåðøèíó êóáà, ãðàíü ðàçìåðíîñòè 1 åãî ðåáðî, ãðàíü ðàçìåðíîñòè 2 êâàäðàò, è òàêäàëåå. Òàê, íà ðèñ. 2.1 â êóáå B 3 âûäåëåíû ðåáðà N1 , . . . , N6 ,à â êóáå B 4 âûäåëåíû ãðàíè Γ(0010) , Γ(0200) , Γ(0221) è Γ(1222)ðàçìåðíîñòåé 0, 1, 2 è 3 ñîîòâåòñòâåííî. Ëåãêî âèäåòü, ÷òîãðàíü Γγ ðàíãà (n − r) â êóáå B n , ãäå γ = (α, 2, . .
. , 2) èα ∈ B n−r , ñîîòâåòñòâóåò îòðåçêó êóáà äëèíû 2r , à ìíîæåñòâî âñåõ ãðàíåé óêàçàííîãî âèäà îáðàçóåò ðàçáèåíèå B n íàïîñëåäîâàòåëüíûå îòðåçêè.Áóäåì, êàê îáû÷íî, ïðåäïîëàãàòü, ÷òî ó íàñ èìååòñÿ ñ÷åòíûé óïîðÿäî÷åííûé àëôàâèò áóëåâûõ ïåðåìåííûõ (ÁÏ) X ={x1 , x2 , . . . , xn , . . . }, è áóäåì ðàññìàòðèâàòü ôóíêöèè àëãåáðû ëîãèêè (ÔÀË), èëè, èíà÷å, áóëåâû ôóíêöèè îò ïåðåìåííûõ èç X, à ìíîæåñòâî âñåõ òàêèõ ôóíêöèé áóäåì îáîçíà÷àòü ÷åðåç P2 (X), èëè P2 . Áóäåì ïðåäïîëàãàòü òàêæå, ÷òîêàæäûé ðàññìàòðèâàåìûé n-ìåðíûé êóá èìååò âèä B n == B n (X), ãäå ìíîæåñòâî ïåðåìåííûõ X = {xj1 , . .
. , xjn } ⊂ Xè j1 < · · · < jn , ïðè÷åì ïåðåìåííàÿ xji äëÿ âñåõ i ∈ [1, n] ñâÿçàíà ñ i-ì ðàçðÿäîì êóáà B n (X). Ìíîæåñòâî âñåõ ôóíêöèéàëãåáðû ëîãèêè f (xj1 , . . . , xjn ), îòîáðàæàþùèõ êóá B n (X) âB , áóäåì îáîçíà÷àòü ÷åðåç P2 (X), à åãî m-þ äåêàðòîâó ñòåïåíü, òî åñòü ìíîæåñòâî ñèñòåì âèäà F = (f1 , . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
