Лекции по упорядоченным множествам и универсальной алгебре. Гуров С.И. - 13 стр.

UptoLike

ВУЗ: 

МГУ | Москва

Составители: 

Рубрика: 

A B
π
A · B
A + B A B A
A
{∨, N, ¬} {+, ·,
−
, }
I O
C
π h C, +, ·,
−
, O, I i
◦
• •
◦
x
1
x
5
x
3
x
2
x
4
1.3. Èçîìîðôèçìû áóëåâûõ àëãåáð                                                               13


     ïîëó÷åííîé öåïè îïðåäåëÿþòñÿ âõîäíûì ïîëþñîì A è âûõîäíûì ïîëþñîì B ñî-
     îòâåòñòâåííî). Òàêèì îáðàçîì, ïîëó÷àþò êëàññ ò.í. ïàðàëëåëüíî-ïîñëåäîâàòåëüíûõ
     êîíòàêòíûõ ñõåì. Èõ åù¼ íàçûâàþò π -ñõåìàìè.
     Ïîä ïðîèçâåäåíèåì A · B áóäåì ïîíèìàòü öåïü, îáðàçîâàííóþ ïîñëåäîâàòåëüíûì,
     à ïîä ñóììîé A + B  ïàðàëëåëüíûì ñîåäèíåíèåì öåïåé A è B . Ïîä öåïüþ A
     áóäåì ïîíèìàòü öåïü, ïîëó÷åííóþ ðàçìûêàíèåì âñåõ çàìêíóòûõ êîíòàêòîâ A è
     çàìûêàíèåì âñåõ å¼ ðàçîìêíóòûõ êîíòàêòîâ.
     Ïðîâîäèìîñòü äâóõïîëþñíîé öåïè ìîæåò áûòü îïèñàíà íåêîòîðîé áóëåâîé ôóíêöè-
     åé, òî÷íåå  ôóíêöèåé, ïðåäñòàâèìîé ò.í. áåñïîâòîðíîé ôîðìóëîé íàä ìíîæåñòâîì
     ëîãè÷åñêèõ ñâÿçîê {∨, N, ¬}, ñîîòâåòñòâóþùèõ îïåðàöèÿì {+, ·, − , }, â êîòîðîé
     êàæäîìó êîíòàêòó öåïè ñîîòâåòñòâóåò âûðàæàþùàÿ åãî ïðîâîäèìîñòü ïðîïîçèöè-
     îíàëüíàÿ ïåðåìåííàÿ, âñòðå÷àþùàÿñÿ â ôîðìóëå ðîâíî îäèí ðàç.
     Äâå öåïè áóäåì ñ÷èòàòü îäèíàêîâûìè, åñëè ìîæíî òàê ñîïîñòàâèòü êîíòàêòàì ïå-
     ðåìåííûå, ÷òî ïðè îäíîì è òîì æå ñîñòîÿíèè êîíòàêòîâ, ñîîòâåòñòâóþùèì îäíîé
     ïåðåìåííîé è âñåõ ïðîèçâîëüíûõ ñîñòîÿíèÿõ îñòàëüíûõ êîíòàêòîâ, îáå ðàññìàò-
     ðèâàåìûå öåïè ÿâëÿþòñÿ îäíîâðåìåííî ëèáî ïðîâîäÿùèìè, ëèáî íå ïðîâîäÿùèìè.
     Ââåäåííîå îòíîøåíèå, î÷åâèäíî, ÿâëÿåòñÿ îòíîøåíèåì ýêâèâàëåíòíîñòè íà ìíîæå-
     ñòâå öåïåé. Îáîçíà÷èì ÷åðåç I ïîñòîÿííî çàìêíóòûé, à ÷åðåç O  ïîñòîÿííî ðàçî-
     ìêíóòûé êîíòàêòû. Îáîçíà÷èì ÷åðåç C ìíîæåñòâî âñåõ ïîïàðíî íåýêâèâàëåíòíûõ
     π -ñõåì (äâóõïîëþñíûõ ýëåêòðè÷åñêèõ öåïåé). Òîãäà ÀÑ h C, +, ·, − , O, I i åñòü, êàê
     íåòðóäíî âèäåòü, áóëåâà àëãåáðà.
     Ïðèìåíåíèå ôîðìóëüíîãî àïïàðàòà áóëåâûõ àëãåáð äëÿ àíàëèçà è ñèíòåçà ýëåêòðè-
     ÷åñêèõ ñõåì èìååò îãðîìíîå ïðèêëàäíîå çíà÷åíèå.
   Ñèñòåìû äàííîãî ïðèìåðà ÿâëÿþòñÿ ïðåäñòàâëåíèÿìè èëè ðåàëèçàöèÿìè áóëåâîé
àëãåáðû.
Ïðèìåð 1.4.  1. Êðîìå ïàðàëëåëüíî-ïîñëåäîâàòåëüíûõ, ñóùåñòâóþò åù¼ ò.í. ìîñòèêî-
    âûå ñõåìû, êîãäà âõîäíûå èëè âûõîäíûå êîíòàêòû îäíîé öåïè ïðèñîåäèíÿåòñÿ ê
    âíóòðåííåìó ïîëþñó äðóãîé, îáðàçóÿ, òåì íå ìåíåå, äâóõïîëþñíóþ öåïü  ïðîñòåé-
    øàÿ ìîñòèêîâàÿ ñõåìà èçîáðàæåíà íà ðèñ. 1.1.


                                              ◦ [
                                          x1
                                                [x
                                           x
                                                       3


                                         • [        •
                                            [
                                               5


                                          x2
                                                 
                                                x     4
                                                   ◦


          Ðèñ. 1.1: Ìîñòèêîâàÿ ñõåìà (âõîäíîé è âûõîäíîé ïîëþñû âûäåëåíû)

     Ýòè ñõåìû íå ÿâëÿþòñÿ ïàðàëëåëüíî-ïîñëåäîâàòåëüíûìè è äëÿ èõ îïèñàíèÿ ÿçûê
     áóëåâîé àëãåáðû îêàçûâàåòñÿ íåäîñòàòî÷íûì: ¾íå óäà¼òñÿ òàê óñîâåðøåíñòâîâàòü
     îáû÷íûé áóëåâ àïïàðàò àëãåáðû ëîãèêè, äîáàâèâ ê íåìó åù¼ íåñêîëüêî (êîíå÷íîå
     ÷èñëî!) îïåðàöèé òàê, ÷òîáû îí ñòàë ñîäåðæàòü ñðåäñòâà äëÿ îïèñàíèÿ ñòðîåíèÿ
     íå òîëüêî ïàðàëëåëüíî-ïîñëåäîâàòåëüíûõ, íî è ìîñòèêîâûõ ñõåì, ïðèòîì îïèñà-
     íèÿ àäåêâàòíîãî, ò.å. òàêîãî, ïðè êîòîðîì êàæäîìó êîíòàêòó â ñõåìå ñîîòâåòñòâóåò
     ðîâíî îäíà áóêâà â ôîðìóëå, âûðàæàþùàÿ ïðîâîäèìîñòü äàííîé ñõåìû¿8 .
     Äåéñòâèòåëüíî, ïðîâîäèìîñòü ìîñòèêîâîé ñõåìû íà                       ðèñ. 1.1 îïèñû-
     âàåòñÿ  áóëåâîé  ôóíêöèåé,  êîòîðàÿ  ìîæåò  áûòü                      çàäàíà  ôîðìóëîé
   8 À.Â. Êóçíåöîâ. Î áåñïîâòîðíûõ êîíòàêòíûõ ñõåìàõ è áåñïîâòîðíûõ ñóïåðïîçèöèÿõ ôóíêöèé àëãåáðû
ëîãèêè // Òðóäû ìàòåì. èí-òà èì. Â.À. Ñòåêëîâà, ò. LI.  Ì.: 1958.

Страницы