OK-metodichka-2010-part1 (1132792)
Текст из файла
Ìîñêîâñêèé ãîñóäàðñòâåííûé óíèâåðñèòåòèìåíè Ì. Â. ËîìîíîñîâàÔàêóëüòåò âû÷èñëèòåëüíîé ìàòåìàòèêè è êèáåðíåòèêèÑ. À. ËîæêèíËåêöèè ïî îñíîâàìêèáåðíåòèêè(âàðèàíò 2010 ã., ãëàâà 1)Ìîñêâà 2010ÎãëàâëåíèåÂâåäåíèå14Ïðåäñòàâëåíèå ôóíêöèé äèçúþíêòèâíûìèíîðìàëüíûìè ôîðìàìè è ñâÿçàííûåñ íèì çàäà÷è1234567Îñíîâíûå ïîíÿòèÿ, îòíîñÿùèåñÿ êìíîæåñòâàì, ìàòðèöàì, ôóíêöèÿì,ôîðìóëàì . . . . . .
. . . . . . . . . . . . . . . .Ïðåäñòàâëåíèå ôóíêöèé àëãåáðû ëîãèêè ñïîìîùüþ äèçúþíêòèâíûõ íîðìàëüíûõ ôîðì(ÄÍÔ) è åãî ¾ãåîìåòðè÷åñêàÿ¿ èíòåðïðåòàöèÿ.Ñîâåðøåííàÿ ÄÍÔ è ðàçëîæåíèå Øåííîíà,êðèòåðèé åäèíñòâåííîñòè ÄÍÔ . . . . . . . . .Ñîêðàùåííàÿ ÄÍÔ è ñïîñîáû åå ïîñòðîåíèÿ .Òóïèêîâûå ÄÍÔ, ÿäðî è ÄÍÔ ïåðåñå÷åíèåòóïèêîâûõ. ÄÍÔ Êâàéíà è ÄÍÔ ñóììàòóïèêîâûõ, êðèòåðèé âõîæäåíèÿ ïðîñòûõèìïëèêàíò â òóïèêîâûå ÄÍÔ, åãî ëîêàëüíîñòüÎñîáåííîñòè ÄÍÔ ëèíåéíûõ è ìîíîòîííûõôóíêöèé. Ôóíêöèÿ ïîêðûòèÿ, òàáëèöà Êâàéíàè ïîñòðîåíèå âñåõ òóïèêîâûõ ÄÍÔ . .
. . . . .Ãðàäèåíòíûé àëãîðèòì è îöåíêà äëèíûãðàäèåíòíîãî ïîêðûòèÿ . . . . . . . . . . . . . .271423313744Îãëàâëåíèå783Çàäà÷à ìèíèìèçàöèè ÄÍÔ. Ïîâåäåíèå ôóíêöèéØåííîíà è îöåíêè òèïè÷íûõ çíà÷åíèé äëÿ ðàíãàè äëèíû ÄÍÔ . . . . . . . . . . . . . . . . . . . 47Àëãîðèòìè÷åñêèå òðóäíîñòè ìèíèìèçàöèè ÄÍÔè îöåíêè ìàêñèìàëüíûõ çíà÷åíèé íåêîòîðûõñâÿçàííûõ ñ íåé ïàðàìåòðîâ. ÒåîðåìàÞ. È. Æóðàâëåâà î ÄÍÔ ñóììà ìèíèìàëüíûõ 52Ëèòåðàòóðà59ÂâåäåíèåÊóðñ ¾Îñíîâû êèáåðíåòèêè¿ (ðàíåå ¾Ýëåìåíòû êèáåðíåòèêè¿), ñîçäàòåëåì è îñíîâíûì ëåêòîðîì êîòîðîãî áûë÷ë.-êîðð. ÐÀÍ Ñ. Â.
ßáëîíñêèé, ÷èòàåòñÿ íà ôàêóëüòåòåÂÌèÊ ÌÃÓ ñ ïåðâûõ ëåò åãî ñóùåñòâîâàíèÿ.  íàñòîÿùååâðåìÿ îí ÷èòàåòñÿ â 68 ñåìåñòðàõ è ÿâëÿåòñÿ îáÿçàòåëüíûìäëÿ âñåõ ñòóäåíòîâ, îáó÷àþùèõñÿ ïî ñïåöèàëüíîñòè 01.02 ïðèêëàäíàÿ ìàòåìàòèêà è èíôîðìàòèêà, à òàêæå áàêàëàâðîâ îäíîèìåííîãî íàïðàâëåíèÿ 510200 è íàïðàâëåíèÿ 010400 èíôîðìàöèîííûå òåõíîëîãèè. Ïðè ýòîì îáúåì è, â íåêîòîðîé ñòåïåíè, ïðîãðàììà êóðñà ¾Îñíîâû êèáåðíåòèêè¿ âàðüèðóþòñÿ â çàâèñèìîñòè îò ñïåöèàëèçàöèè è íàïðàâëåíèÿ.Êóðñ ¾Îñíîâû êèáåðíåòèêè¿ ïîñâÿùåí èçëîæåíèþ òåîðèè äèñêðåòíûõ óïðàâëÿþùèõ ñèñòåì, êîòîðàÿ ïðåäñòàâëÿåò ñîáîé ÷àñòü äèñêðåòíîé ìàòåìàòèêè è ìàòåìàòè÷åñêîéêèáåðíåòèêè.  íåé ðàçðàáàòûâàþòñÿ è èçó÷àþòñÿ äèñêðåòíûå ìàòåìàòè÷åñêèå ìîäåëè, îïèñûâàþùèå ôóíêöèîíèðîâàíèå è ñòðóêòóðó ñëîæíûõ ñèñòåì ïðåîáðàçîâàíèÿ èíôîðìàöèè (èíòåãðàëüíûõ ñõåì, ïðîãðàìì è ò.
ï.).  îñíîâå ýòèõìîäåëåé ëåæàò ðàçëè÷íûå ñïîñîáû çàäàíèÿ ôóíêöèîíèðîâàíèÿ óïðàâëÿþùèõ ñèñòåì ñ ïîìîùüþ äèñêðåòíûõ ôóíêöèéè èõ ñòðóêòóðíàÿ ðåàëèçàöèÿ â òåõ èëè èíûõ êëàññàõ ãðàôîâ (êëàññàõ ñõåì). Ïðè èññëåäîâàíèè óïðàâëÿþùèõ ñèñòåìñòàâÿòñÿ è ðåøàþòñÿ äâå îñíîâíûå çàäà÷è: çàäà÷à àíàëèçàè çàäà÷à ñèíòåçà.Çàäà÷à àíàëèçà ñîñòîèò â íàõîæäåíèè ôóíêöèîíèðîâàíèÿ äàííîé ñõåìû, à çàäà÷à ñèíòåçà â ïîñòðîåíèè ñõåìû,èìåþùåé (ðåàëèçóþùåé) çàäàííîå ôóíêöèîíèðîâàíèå.
Êàæäàÿ èç ýòèõ çàäà÷ ìîæåò ðàññìàòðèâàòüñÿ ëèáî êàê èíäè4Ââåäåíèå5âèäóàëüíàÿ çàäà÷à, è òîãäà åå ðåøåíèåì ÿâëÿåòñÿ êîíêðåòíîå ôóíêöèîíèðîâàíèå (ñõåìà), ëèáî êàê ìàññîâàÿ çàäà÷à,è òîãäà åå ðåøåíèåì äîëæåí áûòü àëãîðèòì íàõîæäåíèÿôóíêöèîíèðîâàíèÿ (ñõåìû). Çàäà÷à ñèíòåçà èìååò, êàê ïðàâèëî, ìíîæåñòâî ðåøåíèé, èç êîòîðûõ âûáèðàþò ðåøåíèå,îïòèìàëüíîå ïî êàêîìó-ëèáî êðèòåðèþ. ×àùå âñåãî â êà÷åñòâå òàêîãî êðèòåðèÿ âûñòóïàåò ñëîæíîñòü ñõåìû, ïîíèìàåìàÿ êàê ñóììà ñëîæíîñòåé ñîñòàâëÿþùèõ åå ýëåìåíòîâèëè çàäåðæêà ñõåìû, ïîíèìàåìàÿ êàê ìàêñèìàëüíàÿ ñóììà çàäåðæåê äëÿ ïîñëåäîâàòåëüíî ñîåäèíåííûõ ýëåìåíòîâñõåìû.Ñ ñîäåðæàòåëüíîé òî÷êè çðåíèÿ ðàçëè÷íûå êðèòåðèè îïòèìàëüíîñòè îòðàæàþò ðàçëè÷íûå ïàðàìåòðû ìîäåëèðóåìûõ ýëåêòðîííûõ ñõåì èëè ïðîãðàìì.
Òàê, íàïðèìåð, ñëîæíîñòü ìîæåò õàðàêòåðèçîâàòü ñòîèìîñòü, ðàçìåðû èëè ïîòðåáëÿåìóþ ìîùíîñòü ÑÁÈÑ, à òàêæå âðåìÿ âûïîëíåíèÿïðîãðàììû íà îäíîì ïðîöåññîðå. Ïðè ýòîì çàäåðæêà ñõåìûõàðàêòåðèçóåò âðåìÿ ñðàáàòûâàíèÿ ÑÁÈÑ èëè âðåìÿ âûïîëíåíèÿ ïðîãðàììû íà ïàðàëëåëüíûõ ïðîöåññîðàõ è ò. ï.Åñëè çàäà÷à ñèíòåçà ðåøåíà â îäíîé ìîäåëè, ìîæíî ïûòàòüñÿ ïåðåíåñòè ýòî ðåøåíèå â äðóãèå ìîäåëè ñ ïîìîùüþñòðóêòóðíîãî ìîäåëèðîâàíèÿ.
Êðîìå òîãî, ïîëó÷åííîå ðåøåíèå ìîæíî ¾óëó÷øèòü¿ ñ ïîìîùüþ ýêâèâàëåíòíûõ ïðåîáðàçîâàíèé. Ñ äðóãîé ñòîðîíû, åñëè çàäà÷à ñèíòåçà ðåøåíàäëÿ îäíèõ ôóíêöèé, ìîæíî ïûòàòüñÿ ¾ðàçáèòü¿ (äåêîìïîçèðîâàòü) íîâóþ ôóíêöèþ íà óæå ðàññìîòðåííûå è ïîñòðîèòüèç ñèíòåçèðîâàííûõ äëÿ íèõ ñõåì ñõåìó äëÿ íîâîé ôóíêöèèñ ïîìîùüþ îïåðàöèè ñóïåðïîçèöèè.Óêàçàííûå âûøå çàäà÷è ðàññìàòðèâàþòñÿ â ëåêöèÿõ äëÿâñåõ îñíîâíûõ êëàññîâ ñõåì (äèçúþíêòèâíûå íîðìàëüíûåôîðìû, ôîðìóëû è ñõåìû èç ôóíêöèîíàëüíûõ ýëåìåíòîâ,êîíòàêòíûå ñõåìû), à òàêæå äëÿ íåêîòîðûõ ìîäèôèêàöèéýòèõ êëàññîâ.Ïåðâàÿ ãëàâà ïîñâÿùåíà ðàçëè÷íûì âîïðîñàì ïðåäñòàâ-6Ââåäåíèåëåíèÿ ôóíêöèé àëãåáðû ëîãèêè ñ ïîìîùüþ òàáëèö è äèçúþíêòèâíûõ íîðìàëüíûõ ôîðì (ìèíèìèçàöèÿ äèçúþíêòèâíûõíîðìàëüíûõ ôîðì).Âòîðàÿ ãëàâà ñîäåðæèò îïèñàíèå ñòðóêòóðû è ôóíêöèîíèðîâàíèÿ ñõåì èç îñíîâíûõ êëàññîâ óïðàâëÿþùèõ ñèñòåì,à òàêæå èç íåêîòîðûõ êëàññîâ, ïðåäñòàâëÿþùèõ ñîáîé èõîáîáùåíèÿ èëè ìîäèôèêàöèè.
 íåé óñòàíàâëèâàþòñÿ âåðõíèå îöåíêè ÷èñëà ñõåì ðàçëè÷íûõ òèïîâ, ðàññìàòðèâàþòñÿîñîáåííîñòè ïðèìåíåíèÿ îïåðàöèè ñóïåðïîçèöèè â ðàçëè÷íûõ êëàññàõ ñõåì è íåêîòîðûå âîïðîñû èõ ñòðóêòóðíîãî ìîäåëèðîâàíèÿ.Âî âòîðîé ãëàâå èçó÷àþòñÿ òàêæå ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ ñõåì íà îñíîâå òîæäåñòâ âî âñåõ îñíîâíûõ êëàññàõ óïðàâëÿþùèõ ñèñòåì.
Äëÿ êàæäîãî èç íèõ ïðèâîäèòñÿñèñòåìà ¾îñíîâíûõ¿ òîæäåñòâ, äîêàçûâàåòñÿ ïîëíîòà ýòîéñèñòåìû è èçó÷àþòñÿ âîïðîñû åå èçáûòî÷íîñòè. òðåòüåé ãëàâå ïîäðîáíî ðàññìàòðèâàåòñÿ çàäà÷à ñèíòåçà óïðàâëÿþùèõ ñèñòåì.  íåé ïðèâîäèòñÿ öåëûé ñïåêòðìåòîäîâ ñèíòåçà ñõåì (îò ïðîñòåéøèõ äî àñèìïòîòè÷åñêè îïòèìàëüíûõ), óñòàíàâëèâàþòñÿ íèæíèå ìîùíîñòíûå îöåíêèôóíêöèé Øåííîíà è îöåíêè ñëîæíîñòè ðÿäà êîíêðåòíûõôóíêöèé, äîêàçûâàåòñÿ ìèíèìàëüíîñòü íåêîòîðûõ ñõåì. ÷åòâåðòîé ãëàâå ïðåäñòàâëåíû íåêîòîðûå âîïðîñû íàäåæíîñòè è êîíòðîëÿ ñõåì (ïîñòðîåíèå òåñòâ äëÿ òàáëèö,ñèíòåç ñàìîêîððåêòèðóþùèõñÿ êîíòàêòíûõ ñõåì).Ãëàâà 1Ïðåäñòàâëåíèå ôóíêöèéäèçúþíêòèâíûìè íîðìàëüíûìèôîðìàìè è ñâÿçàííûå ñ íèì çàäà÷è1Îñíîâíûå ïîíÿòèÿ, îòíîñÿùèåñÿ êìíîæåñòâàì, ìàòðèöàì, ôóíêöèÿì,ôîðìóëàìÁóäåì ñ÷èòàòü èçâåñòíûìè îñíîâíûå ïîíÿòèÿ è îáîçíà÷åíèÿ èç òåîðèè ìíîæåñòâ, ìàòåìàòè÷åñêîãî àíàëèçà, äèñêðåòíîé ìàòåìàòèêè, òåîðèè âåðîÿòíîñòåé (ñì., íàïðèìåð, [24,25, 27, 4]).  äàëüíåéøåì ÷åðåç N (÷åðåç N0 ) îáîçíà÷àåòñÿìíîæåñòâî âñåõ íàòóðàëüíûõ (ñîîòâåòñòâåííî öåëûõ íåîòðèöàòåëüíûõ) ÷èñåë.
Ìíîæåñòâî âñåõ öåëûõ ÷èñåë j , äëÿêîòîðûõ a 6 j 6 b, ãäå a, b öåëûå, íàçûâàåòñÿè îáîçíà÷àåòñÿ ÷åðåçîòðåçêîì[a, b] = (a − 1, b] = [a, b + 1) = (a − 1, b + 1) .Ïðè ýòîì îòðåçêè âèäà[a1 , a2 ) , [a2 , a3 ) , . . . ,ïîñëåäîâàòåëüíûìèãäå a1 < a2 < a3 < . . ., íàçûâàþòñÿ.Íàïîìíèì íåêîòîðûå îïðåäåëåíèÿ è îáîçíà÷åíèÿ, ñâÿçàííûå ñ äåêàðòîâûìè ïðîèçâåäåíèÿìè ìíîæåñòâ. Äëÿ ìíîæåñòâà A è n ∈ N ïîëîæèì(A)n = An = A| ×A×{z· · · × A},n7ðàç8Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìû n-ÿ äåêàðòîâà ñòåïåíü A, òî åñòü ìíîæåñòâî íàáîðîâ (ñòðîê,ñëîâ, âûáîðîê) äëèíû n ñ ýëåìåíòàìè (áóêâàìè) èç A èëè,èíà÷å, ìíîæåñòâî óïîðÿäî÷åííûõ n-îê ýëåìåíòîâ ìíîæåñòâàA.Äëÿ ìíîæåñòâà A è s, n ∈ N ÷åðåç (A)s,n = As,n îáîçíà÷àåòñÿ ìíîæåñòâî ìàòðèö ñ s ñòðîêàìè, n ñòîëáöàìè è ýëåìåíòàìè èç A.
Ïðè ýòîì ïðåäïîëàãàåòñÿ, ÷òî An = A1,n , è ÷òîAs,n n-ÿ äåêàðòîâà ñòåïåíü ìíîæåñòâà As,1 , ýëåìåíòû êîòîðîãî íàçûâàþòñÿ ñòîëáöàìè. ×èñëî ñòîëáöîâ (ñòðîê) ìàòðèöû M íàçûâàåòñÿ åå(ñîîòâåòñòâåííî).Äëÿ ìàòðèöû M ∈ As,n è I 0 ⊆ [1, s] , I 00 ⊆ [1, n] ÷åðåçM hI 0 , I 00 i (ïðè s = 1 è I 0 = {1} ÷åðåç M hI 00 i) îáîçíà÷àåòñÿ åå ïîäìàòðèöà, ðàñïîëîæåííàÿ â ñòðîêàõ ñ íîìåðàìèèç I 0 è ñòîëáöàõ ñ íîìåðàìè èç I 00 .
Íàáîð ∆ = (δ1 , . . . , δp ), ñîñòîÿùèé èç íåïóñòûõ ìíîæåñòâ, áóäåì íàçûâàòüìíîæåñòâà δ = δ1 ∪ . . . ∪ δp . Ïðè ýòîì ìíîæåñòâà δ1 , . . . , δpñ÷èòàþòñÿïîêðûòèÿ ∆, à ÷èñëî p åãîèëè. Ïîêðûòèå, ñîñòîÿùåå èç íåïåðåñåêàþùèõñÿìíîæåñòâ, íàçûâàåòñÿ. Ïîêðûòèå, â êîòîðîì íèîäíà èç êîìïîíåíò íå ñîäåðæèòñÿ â äðóãîé êîìïîíåíòå (âîáúåäèíåíèè îñòàëüíûõ êîìïîíåíò), ñ÷èòàåòñÿ(ñîîòâåòñòâåííî) ïîêðûòèåì.Åñëè A êîíå÷íîå ìíîæåñòâî, òî åãî ìîùíîñòü, òî åñòü÷èñëî ýëåìåíòîâ, îáîçíà÷àåòñÿ îáû÷íî ÷åðåç |A|. Çàìåòèì,÷òî ïðè ýòîìäëèíîéíîéìûìêîìïîíåíòàìèðàíãîìðàçáèåíèåìòóïèêîâûìâûñîòîéïîêðûòèåìäëèíåïðèâîäè-|An | = |A|n è |As,n | = |A|s·n ,ãäå s, n ∈ N, à åñëè |A| = a > n, òî ÷èñëî âûáîðîê (ñëîâ)äëèíû n èç A, â êîòîðûõ âñå ýëåìåíòû ðàçëè÷íû, òàêíàçûâàåìûõ âûáîðîê áåç ïîâòîðåíèé, ðàâíîa (a − 1) · · · (a − n + 1) .Êàæäîå ñëîâî (íàáîð) α = α1 .
. . αn = (α1 , . . . , αn ) èçAn ïðè âñåâîçìîæíûõ ïåðåñòàíîâêàõ áóêâ ïîðîæäàåò ìíîæåñòâî ñëîâ, íàçûâàåìîåäëèíû n èç A èëè,ñî÷åòàíèåì1.9Îñíîâíûå ïîíÿòèÿíåóïîðÿäî÷åííîé -êîéèíà÷å,nèç A, è îáîçíà÷àåìîå ÷åðåç{α1 , . . . , αn }.  ÷àñòíîñòè, ñî÷åòàíèå, ñâÿçàííîå ñ (óïîðÿäî÷åííîé) ïàðîé (u, v), ñ÷èòàåòñÿ íåóïîðÿäî÷åííîé ïàðîé{u, v}, ñî÷åòàíèå, ñâÿçàííîå ñ (óïîðÿäî÷åííûì) ðàçáèåíèåì(δ1 , . . . , δp ), íåóïîðÿäî÷åííûì ðàçáèåíèåì {δ1 , .
. . , δp }, èòàê äàëåå. Çàìåòèì, ÷òî ñî÷åòàíèå ïîðîæäàåòñÿ ïåðåñòàíîâêàìè áóêâ èç ëþáîãî ñâîåãî ñëîâà. Ïðè ýòîì ñî÷åòàíèå èç Aáåç ïîâòîðåíèé, òî åñòü ñî÷åòàíèå, ïîðîæäåííîå ñëîâîì èçAn , âñå áóêâû êîòîðîãî ðàçëè÷íû, ñ ñîäåðæàòåëüíîé òî÷êèçðåíèÿ ïðåäñòàâëÿåò ñîáîé ¾îáû÷íîå¿ ïîäìíîæåñòâî, à ñî÷åòàíèå ñ ïîâòîðåíèÿìè ¾êðàòíîå¿ ïîäìíîæåñòâî ìíîæåñòâà A, òî åñòü ïîäìíîæåñòâî, â êîòîðîå åãî ýëåìåíòû âõîäÿò ñ îïðåäåëåííîé êðàòíîñòüþ (â ñîîòâåòñòâóþùåì ÷èñëå¾ýêçåìïëÿðîâ¿).×èñëî ðàçëè÷íûõ ñî÷åòàíèé áåç ïîâòîðåíèé äëèíû n èçìíîæåñòâà A, |A| = a, îáîçíà÷àåòñÿ ÷åðåç na . Êàê èçâåñòíî(ñì., íàïðèìåð, [27]), aa!a (a − 1) · · · (a − n + 1)==,(1.1)nn! (a − n)!n!à ÷èñëî ñî÷åòàíèé ñ (âîçìîæíûìè) ïîâòîðåíèÿìè äëèíû nèç A ðàâíî a+n−1.nÈíäóêöèåé ïî n ëåãêî ïîêàçàòü, ÷òî n nn! >,(1.2)3à èç ôîðìóëû Ñòèðëèíãà [25] ñëåäóåò, ÷òî1 n n √2πn.n! ∼e1Àñèìïòîòè÷åñêîå ðàâåíñòâî(1.3)a(n)n→∞ b(n)a (n) ∼ b (n) îçíà÷àåò, ÷òî limòî åñòüa (n) = (1 + o (1)) b (n) .= 1,10Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûÈç (1.1) è (1.2) âûòåêàåò, â ÷àñòíîñòè, íåðàâåíñòâî na3a6,nnà èç (1.1) è (1.3) àñèìïòîòè÷åñêîå ðàâåíñòâî1n2n+1n ∼ √.2πn2(1.4)(1.5)Íàïîìíèì òåïåðü íåêîòîðûå ïîíÿòèÿ, ñâÿçàííûå ñ ôóíêöèÿìè è îòíîøåíèÿìè.
Ïóñòü x = (x1 , . . . , xn ), ãäå ïåðåìåííàÿ xi ïðîáåãàåò çíà÷åíèÿ èç ìíîæåñòâà A è ñâÿçàíà ñ i-éêîìïîíåíòîé, i ∈ [1, n], äåêàðòîâîé ñòåïåíè An . Ôóíêöèþ f ,îïðåäåëåííóþ íà ìíîæåñòâå An è ïðèíèìàþùóþ çíà÷åíèÿèç ìíîæåñòâà D (ìíîæåñòâà A), áóäåì íàçûâàòü n,èëè, èíà÷å, nAD (ñîîòâåòñòâåííîA) îò ïåðåìåííûõx è áóäåì ïðåäñòàâëÿòü åå â âèäå2-ìåñòíîé-àðíîé ôóíêöèåé èç ìíîæåñòâà âî ìíîæåíàä ìíîæåñòâîìñòâîf = f (x) , f : An −→ D(ñîîòâåòñòâåííî f : An −→ A) .Ïðè ýòîì â ñëó÷àå D = B = {0, 1} ôóíêöèÿ f ñ÷èòàåòñÿîòíîøåíèåì íàä ìíîæåñòâîì A, à çàïèñü f (a) (f (a)), ãäåa = (a1 , . . .
, an ) ∈ An , îçíà÷àåò, ÷òî êîìïîíåíòû íàáîðà aíàõîäÿòñÿ (ñîîòâåòñòâåííî íå íàõîäÿòñÿ) â îòíîøåíèè f , òîåñòü f (a) = 1 (ñîîòâåòñòâåííî f (a) = 0).Äëÿ áèíàðíûõ îòíîøåíèé, òî åñòü îòíîøåíèé îò äâóõïåðåìåííûõ, îáû÷íûì îáðàçîì îïðåäåëÿþòñÿ ñâîéñòâà ðåôëåêñèâíîñòè, òðàíçèòèâíîñòè, ñèììåòðè÷íîñòè è àíòèñèììåòðè÷íîñòè. Îòíîøåíèå, îáëàäàþùåå ñâîéñòâàìè ðåôëåêñèâíîñòè, ñèììåòðè÷íîñòè è òðàíçèòèâíîñòè, áóäåì, êàê îáû÷íî, íàçûâàòü îòíîøåíèåì ýêâèâàëåíòíîñòè.
Íàïîìíèì, ÷òî1×åðåçdαe (bαc) îáîçíà÷àåòñÿ áëèæàéøåå ê α ñâåðõó (ñîîòâåòñòâåí-íî ñíèçó) öåëîå ÷èñëî2Ôóíêöèþ f îò ïåðåìåííûõâ âèäå(x1 f x2 ).x1 , x2áóäåì, êàê îáû÷íî, ïðåäñòàâëÿòü1.11Îñíîâíûå ïîíÿòèÿîòíîøåíèå ýêâèâàëåíòíîñòè τ , çàäàííîå íà ìíîæåñòâå A,ïîðîæäàåò ðàçáèåíèå ýòîãî ìíîæåñòâà íà êëàññû τ -ýêâèâàëåíòíîñòè ìàêñèìàëüíûå ïî âêëþ÷åíèþ ïîäìíîæåñòâàìíîæåñòâà A, ñîñòîÿùèå èç ïîïàðíî τ -ýêâèâàëåíòíûõ ýëåìåíòîâ. Ïðèìåðîì îòíîøåíèÿ ýêâèâàëåíòíîñòè ÿâëÿåòñÿ îòíîøåíèåíà ìíîæåñòâå An , â êîòîðîìñëîâà α0 è α00 íàõîäÿòñÿ òîãäà è òîëüêî òîãäà, êîãäà α00 ìîæíî ïîëó÷èòü èç α0 â ðåçóëüòàòå ïåðåñòàíîâêè áóêâ.
Çàìåòèì,÷òî êëàññàìè ýêâèâàëåíòíîñòè ïî ýòîìó îòíîøåíèþ ÿâëÿþòñÿ ñî÷åòàíèÿ ñ ïîâòîðåíèÿìè.Îòíîøåíèå, îáëàäàþùåå ñâîéñòâàìè ðåôëåêñèâíîñòè, òðàíçèòèâíîñòè è àíòèñèììåòðè÷íîñòè, áóäåì, êàê îáû÷íî, íàçûâàòü îòíîøåíèåì. Åñëè τ îòíîøåíèå ÷àñòè÷íîãî ïîðÿäêà íà ìíîæåñòâå A, òî ïàðó (A, τ )áóäåì íàçûâàòü.Âòîì ñëó÷àå, êîãäà â ÷àñòè÷íî óïîðÿäî÷åííîì ìíîæåñòâå (A, τ )ëþáûå äâà ýëåìåíòà a0 è a00 èç A ñðàâíèìû, òî åñòü ëèáîa0 τ a00 , ëèáî a00 τ a0 , ïàðó (A, τ ) áóäåì ñ÷èòàòü.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
