Единое окно доступа к образовательным ресурсам

Серия новых логических связок для проектирования электронных схем

Голосов: 0

В статье рассматриваются различные вопросы, связанные с перестановкой конечных множеств. Приведены алгоритмы генерации перестановок на компьютере, предлагается несколько упражнений.

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
    Êîñîâñêèé Í.Ê.

Êîñîâñêèé Íèêîëàé Êèðèëëîâè÷



       ÑÅÐÈß ÍÎÂÛÕ ËÎÃÈ×ÅÑÊÈÕ ÑÂßÇÎÊ ÄËß
       ÏÐÎÅÊÒÈÐÎÂÀÍÈß ÝËÅÊÒÐÎÍÍÛÕ ÑÕÅÌ

      Äîëãèå ãîäû ÿ ðàáîòàë ó÷åíûì ñåêðåòàðåì êàôåäðû, êîòîðîé ðóêîâîäèë Ñâÿòîñëàâ
Ñåðãååâè÷ Ëàâðîâ. Ìíîãî ÿðêèõ òåïëûõ ëè÷íûõ âîñïîìèíàíèé ó ìåíÿ ñâÿçàíî ñ íèì è ñ
÷ëåíàìè åãî ñåìüè. Îäíàêî ÿ îãðàíè÷óñü òîëüêî îòäåëüíûìè îðãàíèçàöèîííûìè ìîìåíòàìè
â öåëîé øêîëå îðãàíèçàòîðñêîé äåÿòåëüíîñòè, êîòîðóþ ÿ ïðîøåë ïîä åãî ðóêîâîäñòâîì.
      Ñîâìåñòíàÿ ðàáîòà ñî Ñâÿòîñëàâîì Ñåðãååâè÷åì áûëà îðãàíèçàöèîííî íåîáû÷àéíî
ïðîäóêòèâíà, íóæíûå àêöåíòû ïîçâîëèëè îðãàíèçîâàòü ïåðâîêëàññíûé êîëëåêòèâ ñîòðóä-
íèêîâ êàê êàôåäðû, òàê è ëàáîðàòîðèè, âîçãëàâëÿâøåéñÿ èì.
      ×àñòî ìåíÿ óäèâëÿëî î÷åíü áîëüøîå âðåìÿ è âíèìàíèå, êîòîðûå Ñâÿòîñëàâ Ñåðãåå-
âè÷ óäåëÿë ïîñòîðîííèì ëþäÿì, à òàêæå ïëîõî óñïåâàþùèì ñòóäåíòàì. Ìíîãèå êîíò-
ðîëüíûå ðàáîòû, êîòîðûå îí ïðîâåðÿë, ñîäåðæàëè áîëüøèå äîïîëíèòåëüíûå òåêñòû,
íàïèñàííûå åãî ðóêîé êðàñíûìè ÷åðíèëàìè. Ïîðàæàëà åãî ãîòîâíîñòü ÷èòàòü êóðñû ëåê-
öèé ïî ñàìûì ðàçíûì äèñöèïëèíàì, ñâÿçàííûì ñ èíôîðìàòèêîé.
      Äâà äåñÿòèëåòèÿ ìîåé èñïîëíèòåëüñêîé ðàáîòû íà êàôåäðå ïîä åãî ðóêîâîäñòâîì
îñòàâèëè íåèçãëàäèìûé ñëåä. ß áûë ñâèäåòåëåì íåîöåíèìûõ ïðèìåðîâ ðåçóëüòàòèâíîãî
ðóêîâîäñòâà êàôåäðîé.



       Âñÿêèé, çíàêîìûé ñ îñíîâàìè àëãåá-      ÷òè âñå ñàìè ñìîãëè áû ñäåëàòü òî æå ñàìîå.
ðû ëîãèêè, ïðî÷èòàâ çàãëàâèå, ìîæåò ñêà-       Ýòà èëëþçèÿ àíàëîãè÷íà òîé, êîòîðàÿ âîç-
çàòü: «Êàêèå åùå íîâûå ëîãè÷åñêèå ñâÿçêè       íèêàåò ó ïîþùåãî ïðî ñåáÿ ïåñíþ, ïîäïåâàÿ
(îïåðàöèè) ìîãóò áûòü, êîãäà âñå äâóìåñò-      ñâîåìó ëþáèìîìó èñïîëíèòåëþ. Ëåãêî, ñèëü-
íûå ñâÿçêè ïåðå÷èñëÿþòñÿ äàæå èíîãäà â         íî è óâåðåííî ëåòèò ãîëîñ ïðî ñåáÿ, à âîò íà
øêîëå íà ôàêóëüòàòèâíûõ çàíÿòèÿõ? Íå ìî-       ýñòðàäå, ê ñîæàëåíèþ, ëåãêîñòü, ñèëà èëè
æåò áûòü íîâûõ ñâÿçîê!» – åñëè îí íå çíà-      óâåðåííîñòü ìîãóò êóäà-òî óëåòó÷èòüñÿ.
êîì ñ ðàáîòàìè Ìèðîíà Èâàíîâè÷à Òåëüïè-              Ïðèìåðîì ïðîñòîãî, íî ñóùåñòâåííî-
çà. Íî âñïîìíèì ýâîëþöèþ ïî÷òè ëþáîãî          ãî äëÿ êèáåðíåòèêè ïîíÿòèÿ ìîæåò ïîñëó-
ñóùåñòâåííî íîâîãî.                            æèòü èçîáðåòåíèå Ì.È. Òåëüïèçîì íîâîé ëî-
       1-é ýòàï: Íå ìîæåò áûòü!                               ãè÷åñêîé îïåðàöèè, êîòîðóþ
       2-é ýòàï: Â ýòîì ÷òî-òî åñòü.                             àâòîð íàçâàë þíêöèåé.
       3-é ýòàï: Êòî æå èç èíòåðåñóþùèõñÿ                          Ýòèì ñàìûì îí îòìåòèë
ýòîãî íå çíàåò?!                                                     íàãëÿäíóþ ñâÿçü åå ñ
       Àâòîð íàäååòñÿ, ÷òî ìíîãèå, ÷èòàÿ ýòî                           ìíîãîìåñòíîé ëî-
ñîîáùåíèå, ïðîéäóò âñå ýòè òðè ýòàïà.                                    ãè÷åñêîé ñâÿçêîé
       Â ìàòåìàòèêå, äà è âîîáùå â ìèðå,                                 «è» (êîíúþíêöè-
èíîãäà ïðîèñõîäÿò óäèâèòåëüíåéøèå ñîáû-                                  åé) è ìíîãîìåñò-
òèÿ.  ñàìûõ îñíîâàõ èíîãäà ïðîèñõîäÿò                                   íîé ëîãè÷åñêîé
òàêèå ñóùåñòâåííûå èçìåíåíèÿ, èçîáðåòå-                                  ñâÿçêîé «èëè»
íèÿ èëè îòêðûòèÿ, ïîíèìàíèå êîòîðûõ âïîë-                               (äèçúþíêöèåé).
íå äîñòóïíî ëþáîçíàòåëüíîìó øêîëüíèêó.                                      Â ìàòåìàòèêå
Èíîãäà ýòî ðîæäàåò èëëþçèþ òîãî, ÷òî ïî-                            îáû÷íî ðàçëè÷àþò òðè

64          © ÊÎÌÏÜÞÒÅÐÍÛÅ ÈÍÑÒÐÓÌÅÍÒÛ Â ÎÁÐÀÇÎÂÀÍÈÈ. ¹ 2, 2003 ã.


 Ñåðèÿ íîâûõ ëîãè÷åñêèõ ñâÿçîê äëÿ ïðîåêòèðîâàíèÿ ýëåêòðîííûõ ñèñòåì

ñïîñîáà çàïèñè âûðàæåíèé, ñîäåðæàùèõ          èì ñ ïîìîùüþ äâîåòî÷èÿ è íàçâàíà þíêöè-
èìåíà ôóíêöèé èëè îòíîøåíèé:                  åé. Îíà óäîáíà äëÿ ðåàëèçàöèè ñ ïîìîùüþ
      – ïðåôèêñíàÿ, êîãäà èìÿ ôóíêöèè (îò-    ýëåêòðè÷åñêèõ ñõåì è ïîçâîëÿåò êðàòêî çà-
íîøåíèÿ) ñòîèò ïåðåä àðãóìåíòàìè, íàïðè-      ïèñûâàòü äîñòàòî÷íî ñëîæíûå áóëåâû ôóí-
ìåð, sin x, f (x, y, z), ODD (x);             êöèè (îñîáåííî ñèììåòðè÷íûå), îñíîâàííûå,
                                              íàïðèìåð, íà ôóíêöèè ãîëîñîâàíèÿ ñ òî÷-
                                              íûì óêàçàíèåì ÷èñëà ãîëîñóþùèõ «çà». Þí-
                                              êöèþ ìîæíî èñïîëüçîâàòü êàê «êóáèê» ýëå-
                                              ìåíòíîé áàçû äëÿ ïîñòðîåíèÿ êîìïüþòåðîâ.
                                              Îíà ÿâëÿåòñÿ ñóùåñòâåííûì îáîáùåíèåì ïî-
                                              ðîãîâûõ ôóíêöèé.
                                                     Þíêöèÿ çíà÷èòåëüíî ðàñøèðÿåò òðà-
                                              äèöèîííûå ëîãè÷åñêèå îïåðàöèè. Îíà ÿâëÿ-
      – èíôèêñíàÿ, êîãäà èìÿ ôóíêöèè (îò-     åòñÿ ñèììåòðè÷íîé ôóíêöèåé (òî åñòü ïåðå-
íîøåíèÿ) ñòîèò ìåæäó àðãóìåíòàìè, íàïðè-      ñòàíîâêà àðãóìåíòîâ íå èçìåíÿåò åå çíà÷å-
ìåð, x + y, x > y, x & y;                     íèÿ). Àðãóìåíòîâ ó ýòîé îïåðàöèè ìîæåò
                                              áûòü ñêîëüêî óãîäíî. Ïîýòîìó ìîæíî ñêà-
                                              çàòü, ÷òî ïðåäëàãàåòñÿ ñåðèÿ ëîãè÷åñêèõ ñâÿ-
                                              çîê. Çíàê þíêöèè, îáîçíà÷àåìûé äâîåòî÷è-
                                              åì, ìîæåò ñòîÿòü ïåðåä âñåìè àðãóìåíòàìè,
                                              ìåæäó ëþáûìè
                                              äâóìÿ àðãóìåíòà-
                                              ìè, à òàêæå ïîñ-
                                              ëå âñåõ àðãóìåí-
                                              òîâ. Íàïðèìåð,
      – ïîñòôèêñíàÿ, êîãäà èìÿ ôóíêöèè (îò-   (:x1 x2:x3 x4), íî
íîøåíèÿ) ñòîèò ïîñëå àðãóìåíòîâ, íàïðè-       ìåæäó ëþáûìè
ìåð, x2.                                      äâóìÿ äâîåòî÷è-
                                              ÿìè äîëæåí íà-
                                              õîäèòüñÿ õîòÿ áû îäèí àðãóìåíò.
                                                      ñëó÷àå, êîãäà èñïîëüçîâàíî òîëüêî
                                              îäíî äâîåòî÷èå, ïðåäâàðèòåëüíî âûÿñíÿåò-
                                              ñÿ, ïîñëå êàêîãî ïî ñ÷åòó (ñëåâà íàïðàâî)
                                              àðãóìåíòà îíî íàõîäèòñÿ: ïîñëå íóëåâîãî (òî
                                              åñòü ïåðåä âñåìè àðãóìåíòàìè), ïîñëå ïåð-
      Âïåðâûå Ì.È. Òåëüïèçîì áûëà ïðåä-       âîãî, ïîñëå âòîðîãî, ... èëè ïîñëå ïîñëå-
ëîæåíà ïîçèöèîííàÿ çàïèñü íîâîé ëîãè÷åñ-      äíåãî. Ïóñòü äâîåòî÷èå â âûðàæåíèè, ñî-
êîé ñâÿçêè (íå ïðåôèêñíàÿ, íå èíôèêñíàÿ,      äåðæàùåì n ðàçëè÷íûõ àðãóìåíòîâ, ñòîèò
íå ïîñòôèêñíàÿ). Ýòà ñâÿçêà áûëà çàïèñàíà     òîëüêî ïîñëå k-ãî àðãóìåíòà (k íå ïðåâîñ-
                                              õîäèò n). Òîãäà èñòèííîñòü âñåãî âûðàæå-
                                              íèÿ (x1 x2 ... xk: ... xn) ýêâèâàëåíòíà ðàâåí-
                                              ñòâó
                                                           x1 + x2 + ... + xn = k,
                                              ãäå, êàê ýòî ïðèíÿòî â òåõíè÷åñêîé êèáåð-
                                              íåòèêå, èñòèííûå àðãóìåíòû èìåþò çíà÷å-
                                              íèå 1, à ëîæíûå àðãóìåíòû èìåþò çíà÷åíèå
                                              0. (Îòìåòèì, ÷òî åñëè â ïîñëåäíåì ðàâåí-
                                              ñòâå ñëîæåíèå çàìåíèòü óìíîæåíèåì è k = 1,
                                              òî ìû ïîëó÷èì îïðåäåëåíèå ìíîãîêðàòíîé
                                              êîíúþíêöèè).

ØÊÎËÀ ÑÎÂÐÅÌÅÍÍÎÃÎ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß                                                     65


Êîñîâñêèé Í.Ê.

      Ñëó÷àé, êîãäà íåêîòîðûå àðãóìåíòû       òîëüêî òîãäà, êîãäà èñòèíåí õîòü îäèí åå
íàõîäÿòñÿ ìåæäó äâóìÿ äâîåòî÷èÿìè, ìîæåò      àðãóìåíò, ìîæåò áûòü îïðåäåëåíà ÷åðåç þí-
áûòü ñâåäåí ê ïðåäûäóùåìó, êîãäà èñïîëü-      êöèþ ñëåäóþùèì îáðàçîì
çóåòñÿ åäèíñòâåííîå äâîåòî÷èå. Ýòî ñâåäå-                  ( x1:x2:x3:x4:x5:) .
íèå ìîæåò áûòü ïðîäåìîíñòðèðîâàíî íà ñëå-
                                                    Ýòè îïðåäåëåíèÿ, íåñîìíåííî, îïðàâ-
äóþùåì ïðèìåðå. Äëÿ êàæäîãî íàáîðà àðãó-
                                              äûâàþò íàçâàíèå îïåðàöèè – þíêöèÿ.
ìåíòîâ èñòèííîñòü âûðàæåíèÿ
                                                    Ëîãè÷åñêàÿ êîíñòàíòà «Èñòèíà» ýê-
           (:x1:x2 x3 x4:x5 x6 x7:)
ýêâèâàëåíòíà òîìó, ÷òî èñòèííî õîòÿ áû îäíî
èç ñëåäóþùèõ âûðàæåíèé
           (:x1 x2 x3 x4 x5 x6 x7 )
           ( x1:x2 x3 x4 x5 x6 x7 )
           ( x1 x2 x3 x4:x5 x6 x7 )
           ( x1 x2 x3 x4 x5 x6 x7:)
      Ýòèõ âûðàæåíèé ðîâíî ñòîëüêî, ñêîëü-
êî â èñõîäíîì âûðàæåíèè äâîåòî÷èé, ïðè-
÷åì êàæäîå äâîåòî÷èå çàïèñûâàåòñÿ ðîâíî
îäèí ðàç ñ ñîõðàíåíèåì ñâîåãî ìåñòà. Óæå
                                              âèâàëåíòíà êàæäîìó èç âûðàæåíèé âèäà (:),
çäåñü âèäíà çíà÷èòåëüíàÿ ýêîíîìèÿ çàïèñè
                                              (:x1:), (:x1:x2:), (:x1:x2:x3:), ... . Óäîáíî ñ÷è-
þíêöèè, åñëè ñðåäè àðãóìåíòîâ èñïîëüçîâà-
                                              òàòü, ÷òî ëîãè÷åñêàÿ êîíñòàíòà «Ëîæü» ýê-
íî íåñêîëüêî äâîåòî÷èé.
      Êîíúþíêöèÿ (ëîãè÷åñêîå óìíîæåíèå)
ïÿòè àðãóìåíòîâ, êîòîðàÿ èñòèííà òîãäà è




                                              âèâàëåíòíà êàæäîìó èç âûðàæåíèé âèäà ( ),
                                              ( x1 ), ( x1 x2 ), ( x1 x2 x3 ), ... , â êîòîðûõ íåò
                                              íè åäèíîãî äâîåòî÷èÿ.
                                                      Ýêâèâàëåíòíîñòü (ðàâåíñòâî) x1 è x2
òîëüêî òîãäà, êîãäà èñòèííû âñå åå àðãóìåí-
òû, ìîæåò áûòü îïðåäåëåíà ÷åðåç þíêöèþ
ñëåäóþùèì îáðàçîì
             ( x1 x2 x3 x4 x5:) .
     Äèçúþíêöèÿ (ëîãè÷åñêîå ñëîæåíèå)
ïÿòè àðãóìåíòîâ, êîòîðàÿ èñòèííà òîãäà è



                                              ìîæåò áûòü çàïèñàíà â âèäå (:x1 x2:). Ïîïàð-
                                              íàÿ ýêâèâàëåíòíîñòü n àðãóìåíòîâ ìîæåò
                                              áûòü çàïèñàíà â âèäå (:x1 x2 ... xn:).
                                                    Óäîáíûé âèä èìååò îòðèöàíèå âûðà-
                                              æåíèÿ, ñîäåðæàùåãî íåñêîëüêî äâîåòî÷èé.
                                              Ïðè îòðèöàíèè âûðàæåíèÿ äâîåòî÷èÿ ïîÿâ-
                                              ëÿþòñÿ íà òåõ è òîëüêî òåõ ìåñòàõ, ãäå èõ

66         © ÊÎÌÏÜÞÒÅÐÍÛÅ ÈÍÑÒÐÓÌÅÍÒÛ Â ÎÁÐÀÇÎÂÀÍÈÈ. ¹ 2, 2003 ã.


 Ñåðèÿ íîâûõ ëîãè÷åñêèõ ñâÿçîê äëÿ ïðîåêòèðîâàíèÿ ýëåêòðîííûõ ñèñòåì

ðàíüøå íå áûëî. Òàê, íàïðèìåð, îòðèöàíèå             NP-ïîëíîé çàäà÷åé (çàäà÷åé, äëÿ êîòî-
âûðàæåíèÿ ( x1:x2 x3 x4:x5 ) ýêâèâàëåíòíî      ðîé äî ñèõ ïîð íèêîìó íå óäàëîñü ïîñòðîèòü
âûðàæåíèþ (:x1 x2:x3:x4 x5:).                  àëãîðèòì, ðåøàþùèé åå çà ïîëèíîìèàëüíîå
      Êîãäà äâîåòî÷èé ìåæäó àðãóìåíòàìè        îò äëèíû çàïèñè èñõîäíûõ äàííûõ ÷èñëî
î÷åíü ìíîãî, åãî îòñóòñòâèå ìåæäó, ïåðåä       øàãîâ). Íî äëÿ îáîçíà÷åíèé Ì.È. Òåëüïèçà â
èëè ïîñëå àðãóìåíòîâ óäîáíî îáîçíà÷àòü         êà÷åñòâå ñëîæíîãî óïðàæíåíèÿ ìîæíî äîêà-
ïîä÷åðêèâàíèåì, íàçûâàÿ åãî àþíêöèåé,          çàòü ñëåäóþùóþ òåîðåìó.
îäíîâðåìåííî óáðàâ âñå äâîåòî÷èÿ. Ýòî îáåñ-          Òåîðåìà. Ïðîâåðêà âûïîëíèìîñòè
ïå÷èâàåò áîëåå êîðîòêóþ çàïèñü. (Ïðèìåíÿ-      þíêöèè, àðãóìåíòàìè êîòîðîé ìîãóò áûòü
åòñÿ íåáîëüøîå ÷èñëî ñèìâîëîâ ïîä÷åðêè-
                                               ïåðåìåííûå è îòðèöàíèÿ ïåðåìåííûõ (âîç-
âàíèÿ âìåñòî î÷åíü áîëüøîãî ÷èñëà ñèìâî-       ìîæíî ñ ïîâòîðåíèÿìè), îñóùåñòâëÿåòñÿ çà
ëîâ äâîåòî÷èÿ.)                                ïîëèíîì øàãîâ îò äëèíû çàïèñè þíêöèè.
      Èìååò ìåñòî ïðèíöèï äâîéñòâåííîñ-
                                                     Ñëó÷àé, êîãäà â âûðàæåíèè èìååòñÿ
òè: ïðè ïðîíåñåíèè îòðèöàíèÿ âíóòðü ñêî-       òîëüêî îäíî äâîåòî÷èå, ïðåäñòàâëÿåò ñîáîé
áîê ïîä÷åðêèâàíèå è äâîåòî÷èå ìåíÿþòñÿ         óäà÷íûé âàðèàíò ïîäïîðîãîâîé ôóíêöèè.
ìåñòàìè. Ïðîíåñåíèå îòðèöàíèÿ äëÿ âûðà-
                                               Ïîðîãîâûå ôóíêöèè èñïîëüçóþòñÿ äëÿ ìîäå-
æåíèÿ, ñîäåðæàùåãî þíêöèþ, èíîå, áîëåå         ëèðîâàíèÿ íåéðîííûõ ñåòåé. Ïðèìåðîì ïî-
ïðîñòîå, ÷åì â ñëó÷àå äèçúþíêöèè è êîíú-       ðîãîâîé ôóíêöèè ìîæåò
þíêöèè, ïîñêîëüêó ïåðåä àðãóìåíòàìè íå
                                               ñëóæèòü õàðàêòåðè-
ïîÿâëÿþòñÿ äîïîëíèòåëüíûå îòðèöàíèÿ.          ñòè÷åñêàÿ ôóíê-
ðåçóëüòàòå þíêöèÿ îáåñïå÷èâàåò áîëåå ïîë-      öèÿ óñëîâèÿ
íóþ, áîëåå ñèììåòðè÷íóþ è, ñëåäîâàòåëüíî,
áîëåå êðàñèâóþ ñèñòåìó îáîçíà÷åíèé äëÿ
ëîãè÷åñêèõ âûðàæåíèé.




      Äëÿ îïåðàöèè þíêöèè âîçìîæíà è
                                               x1 + x2 + x3 ≥ 2. Â òåðìèíàõ þíêöèè
ïðåôèêñíàÿ ôîðìà çàïèñè, åñëè ðàçðåøèòü        ýòà ïîðîãîâàÿ ôóíêöèÿ çàïèøåòñÿ â âèäå
èñïîëüçîâàòü íàòóðàëüíûå ÷èñëà äëÿ óêàçà-      (x1 x2:x3:).
íèÿ íîìåðîâ òåõ ìåñò, ãäå äîëæíà íàõîäèòü-
                                                      Ñ ïîìîùüþ þíêöèè ëåãêî âûðàçèòü,
ñÿ þíêöèÿ èëè, íàîáîðîò, ãäå îíà íå äîëæíà     íàïðèìåð, óñëîâèå, ñîñòîÿùåå â òîì, ÷òî â
íàõîäèòüñÿ (â ïîñëåäíåì ñëó÷àå öèôðó ìîæ-      ãðóïïå èç øåñòè ÷åëîâåê ïðè ãîëîñîâàíèè
íî ïîä÷åðêíóòü). Íàïðèìåð, âûðàæåíèÿ
                                               «çà» è «ïðîòèâ» (âîçäåðæàâøèåñÿ ãîëîñà
[1,4](A,B,C,D) è [0,2,3](A,B,C,D) áóäóò ïðå-   ïðè÷èñëÿþòñÿ ê ãîëîñàì «ïðîòèâ») ãîëîñà
ôèêñíûìè âàðèàíòàìè çàïèñè (A:B C D:).         íå ðàçäåëèëèñü ïîðîâíó.
Ïîñêîëüêó þíêöèÿ ïåðåñòàíîâî÷íà îò àðãó-
                                                      Íàêîíåö, þíêöèÿ äîïóñêàåò äîñòàòî÷-
ìåíòîâ, òî ïîâòîðÿþùèåñÿ àðãóìåíòû ìîæ-        íî ïðîñòóþ ðåàëèçàöèþ ýëåêòðîííûìè ñõå-
íî ñíàáäèòü êîýôôèöèåíòîì ïîâòîðåíèÿ.          ìàìè.
Íàïðèìåð, âìåñòî [1,4](A,A,A,B) ìîæíî íà-
                                                      Íà åå îñíîâå óäîáíî çàïèñàòü ðåçóëü-
ïèñàòü [1,4](3 A,B).                           òàò ñëîæåíèÿ äâóõ íåîòðèöàòåëüíûõ öåëûõ
      Â òàêîé ìîäèôèöèðîâàííîé çàïèñè
                                               ÷èñåë, çàïèñàííûõ â äâîè÷íîé ñèñòåìå ñ÷èñ-
ïðîâåðêà âûïîëíèìîñòè þíêöèè (òî åñòü
                                               ëåíèÿ. Îãðàíè÷èìñÿ ïÿòüþ ðàçðÿäàìè ÷èñåë
ñóùåñòâîâàíèå íàáîðà çíà÷åíèé ïåðåìåííûõ,
                                               A = (a0,a1,a2,a3,a4) è B = (b0,b1,b2,b3,b4).
ïðè êîòîðîì þíêöèÿ èñòèííà) ÿâëÿåòñÿ

ØÊÎËÀ ÑÎÂÐÅÌÅÍÍÎÃÎ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß                                                    67


Êîñîâñêèé Í.Ê.

Ðàçðÿäû ñóììû îáîçíà÷èì ïîñðåäñòâîì             êà, òàê è íà îñíîâå âçâåøèâàíèÿ ñèãíàëîâ
C = (c0,c1,c2,c3,c4,c5). Îíè ìîãóò áûòü âû-     ïðè èñïîëüçîâàíèè íåñêîëüêèõ êîìïàðàòî-
÷èñëåíû ñëåäóþùèì îáðàçîì.                      ðîâ, èñïîëüçóþùèõ, íàïðèìåð, äîïîëíÿþ-
    c0 = (a0:b0);         c'0 = (a0 b0:);       ùèå ÌÎÏ-òðàíçèñòîðû. Þíêöèÿ ìîæåò ñëó-
    c1 = (c'0:a1 b1:);    c'1 = (c'0 a1:b1:);   æèòü óäîáíûì ýëåìåíòàðíûì «êèðïè÷èêîì»
    c2 = (c'1:a2 b2:);    c'2 = (c'1 a2:b2:);   ïðè ñîçäàíèè êèáåðíåòè÷åñêèõ óñòðîéñòâ íà
    c3 = (c'2:a3 b3:);    c'3 = (c'2 a3:b3:);   ÑÁÈÑ (ñâåðõáîëüøèõ èíòåãðàëüíûõ ñõåìàõ).
    c4 = (c'3:a4 b4:);    c'4 = (c'3 a4:b4:);           êà÷åñòâå íàãëÿäíîãî èñõîäíîãî òåõ-
    c5 = c'4.                                           íè÷åñêîãî ïðåäñòàâëåíèÿ þíêöèè äî-
                                                         ñòàòî÷íî èìåòü â âèäó ðåàëèçàöèþ
      Êðàòêîñòü è íàãëÿäíîñòü çàïè-
                                                          þíêöèè, îñíîâàííóþ íà ìèêðîàì-
ñè ãîâîðÿò ñàìè çà ñåáÿ. Ýòà çàïèñü
                                                            ïåðìåòðå, íà øêàëå êîòîðîãî èìå-
îñíîâàíà íà îáû÷íîì ïåðåíåñåíèè
                                                             þòñÿ äîïîëíèòåëüíûå êîíòàêòû,
åäèíè÷êè â ñòàðøèé ðàçðÿä (ðàç-
ðÿäû ïåðåíåñåíèÿ îáîçíà÷åíû                                  îòìå÷àþùèå íåêîòîðûå çíà÷å-
ïåðåìåííûìè ñî øòðèõàìè).                                    íèÿ ñóììàðíîãî òîêà ñî âñåõ âõî-
      Áóäóùèå ñîçäàòåëè êè-                                  äîâ, ïîäêëþ÷åííûõ ê ìèêðîàì-
áåðíåòè÷åñêèõ óñòðîéñòâ!                                     ïåðìåòðó. Âîçìîæíî, ÷òî êòî-òî
Ìîæåòå èñïîëüçîâàòü þíê-                                     ñìîæåò èçîáðåñòè è áîëåå óäà÷-
öèþ, èçîáðåòåííóþ ìàòåìà-                                     íóþ ðåàëèçàöèþ þíêöèè. Ñ òî÷-
òèêîì Ì.È. Òåëüïèçîì, îïè-                                    êè çðåíèÿ ìàòåìàòèêè è ïðîãðàì-
ñàíèå êîòîðîé âïåðâûå îïóá-                                   ìèðîâàíèÿ îñíîâíàÿ öåííîñòü
ëèêîâàíî â 1984 ã.                                            þíêöèè ñîñòîèò â êðàòêîñòè è
      Ïî ïîâîäó òåõíè÷åñêîé                                   óäîáñòâå åå èñïîëüçîâàíèÿ äëÿ
ðåàëèçàöèè þíêöèè íà ìèêðîñõåìå ñëåäóåò         çàïèñè áóëåâûõ ôóíêöèé, ïåðåðàáàòûâàþùèõ
çàìåòèòü, ÷òî, ïîñêîëüêó â íàñòîÿùåå âðåìÿ      íàáîðû ëîãè÷åñêèõ êîíñòàíò. Òàêîå âïîëíå
ìàññîâî èçãîòàâëèâàþòñÿ ìèêðîñõåìû, èìå-        äîñòóïíî è ìîæåò áûòü èíòåðåñíî øêîëüíè-
þùèå äî 64 âûâîäîâ, òî ëåãêî ìîæåò áûòü         êó, à ðåàëèçàöèÿ – äåëî áûñòðî ïðîãðåññèðó-
ðåàëèçîâàíà þíêöèÿ îò 31 àðãóìåíòà íà îä-       þùåé òåõíèêè, áûòü ìîæåò, òåõíèêè òîãî áó-
íîé ìèêðîñõåìå. Ðåàëèçàöèÿ þíêöèè âîç-          äóùåãî, êîòîðîå áóäóò ñîçäàâàòü ñåãîäíÿøíèå
ìîæíà êàê íà îñíîâå ïàðàëëåëüíîãî ñ÷åò÷è-       øêîëüíèêè.

      Ëèòåðàòóðà.
      1. Òåëüïèç Ì.È. Ïîçèöèîííûå ïðèíöèïû ïðåäñòàâëåíèÿ ôóíêöèé àëãåáðû ëîãèêè. //
Íàó÷íûé ñîâåò ïî êîìïëåêñíîé ïðîáëåìå «Êèáåðíåòèêà» ÀÍ ÑÑÑÐ. Ì., 1984.
      2. Òåëüïèç Ì.È. Ïîçèöèîííûå îïåðàòîðû è ïðåîáðàçîâàíèÿ â àëãåáðå ëîãèêè. // Íàó÷íûé
ñîâåò ïî êîìïëåêñíîé ïðîáëåìå «Êèáåðíåòèêà» ÀÍ ÑÑÑÐ. Ì., 1985.
      3. Òåëüïèç Ì.È. Ïðèìåíåíèå ïðèíöèïîâ ïîçèöèîííîñòè â ðåøåíèè ñèñòåì ëîãè÷åñêèõ
óðàâíåíèé. // Òåçèñû äîêëàäîâ Âñåñîþçíîé êîíôåðåíöèè ïî ïðèêëàäíîé ëîãèêå. Ì., 1985.
      4. Òåëüïèç Ì.È. Ïðåäñòàâëåíèå ôóíêöèé àëãåáðû ëîãèêè. // Êèáåðíåòèêà, 1985, ¹ 4,
ñ. 37–40.
      6. Êîñîâñêèé Í.Ê. Î íîâîé ïîçèöèîííîé ëîãè÷åñêîé ñâÿçêå. // Òåçèñû äîêëàäîâ
Äåâÿòîé Âñåñîþçíîé êîíôåðåíöèè ïî ìàòåìàòè÷åñêîé ëîãèêå. Ë., «Íàóêà», 1988.


                                                Êîñîâñêèé Íèêîëàé Êèðèëëîâè÷,
                                                äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð,
                                                çàâåäóþùèé êàôåäðîé èíôîðìàòèêè
                                                ìàòåìàòèêî-ìåõàíè÷åñêîãî
                                                ôàêóëüòåòà Ñàíêò-Ïåòåðáóðãñêîãî
                                                ãîñóäàðñòâåííîãî óíèâåðñèòåòà.
68          © ÊÎÌÏÜÞÒÅÐÍÛÅ ÈÍÑÒÐÓÌÅÍÒÛ Â ÎÁÐÀÇÎÂÀÍÈÈ. ¹ 2, 2003 ã.



    
Яндекс цитирования Яндекс.Метрика