В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин и др. - Задачи по курсу Основы кибернетики (2002) (1124121), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

dOKAZATX POLINOMIALXNU@ \KWIWALENTNOSTX ZADA^ L1 I L2, ES-LI1) L1 = wyp, L2 = 4-wyp;2) L1 = raskraska grafa w 2 cweta; L2 = umnoveniedwoi~nyh ~isel.15~ASTX3.|KWIWALENTNYE PREOBRAZOWANIQx 3. |KWIWALENTNYE PREOBRAZOWNIQ FORMULdWE FORMULY ALGEBRY LOGIKI NAZYWA@TSQ \KWIWALENTNYMI, ESLIONI REALIZU@T RAWNYE FUNKCII ALGEBRY LOGIKI.tOVDESTWOM W ALGEBRE LOGIKI NAZYWAETSQ RAWENSTWO, W LEWOJ I PRAWOJ ^ASTQH KOTOROGO STOQT \KWIWALENTNYE FUNKCII.sPRAWEDLIWY, W ^ASTNOSTI, SLEDU@]IE TOVDESTWA:(1) x1 _ x2 = x1&x2(2) x1&x2 = x1 _ x2(3) x = x(4) (x1 _ x2)&x3 = (x1&x3) _ (x2&x3)(5) x1&x2 = x2&x1(6) (x1&x2)&x3 = x1&(x2&x3)(7) x&x = x(8) (x1&x1)&x2 = x1&x1(9) (x1&x1) _ x2 = x2(10) x1 _ x2 = x2 _ x1(11) (x1 _ x1)&x2 = x2(12) (x1 _ x2) _ x3 = x1 _ (x2 _ x3)(13) x _ x = x(14) x1&x1 = x2&x2.eSLI W TOVDESTWO A = B WMESTO ODINAKOWYH PEREMENNYH WS@DU PODSTAWITX PROIZWOLXNYE ODINAKOWYE FORMULY, TO SNOWA POLU^ITSQ TOVDESTWO A0 = B 0.

pRIMENITX TOVDESTWO A = B K FORMULE C | \TOZNA^IT WYDELITX W FORMULE C PODFORMULU, POLNOSTX@ SOWPADA@]U@S A0 (ILI B 0) I ZAMENITX W C \TU PODFORMULU NA B 0 (SOOTWETSTWENNO,NA A0).wMESTO & MY OBY^NO BUDEM ISPOLXZOWATX ILI WOOB]E \TOT ZNAKBUDEM OPUSKATX.3.1. iSPOLXZUQ TOLXKO TOVDESTWO (6), WYWESTI TOVDESTWA1)(x1 x2) (x3 x4) = ((x1 x2) x3) x4;2) x1 ((x2 x3) x4) = ((x1 x2) x3) x4;3) x1 (x2 (x3 x4)) = ((x1 x2) x3) x4;4) (x1 (x2 x3)) (x4 x5) = ((x1 x2) x3) x4) x5;5) x1 ((x2 x3) (x4 x5)) = ((x1 x2) x3) x4) x5.163.2. pUSTX FORMULY F1 I F2 POLU^ENY IZ WYRAVENIQ x1 x2 : : : xnL@BYMI PRAWILXNYMI RASSTANOWKAMI SKOBOK. dOKAZATX, ^TO, ISPOLXZUQTOVDESTWO (6), MOVNO WYWESTI TOVDESTWO F1 = F2.zAME^ANIE.

rEZULXTAT ZADA^I 3.2 DLQ KON_@NKCII I ANALOGI^NYJREZULXTAT DLQ DIZ_@NKCII (SM. TOVDESTWO (12)) POZWOLQET ZAPISYWATXDLINNYE KON_@NKCII I DIZ_@NKCII BEZ SKOBOK. w SLEDU@]IH ZADA^AHPORQDOK DEJSTWIJ OPREDELQETSQ LIBO SKOBKAMI, LIBO SOGLA[ENIEM OTOM, ^TO KON_@NKCIQ WYPOLNQETSQ RANX[E DIZ_@NKCII, A OTRICANIEPRIMENQETSQ K TOJ FORMULE, NAD KOTOROJ ONO STOIT.3.3. s POMO]X@ TOVDESTW (1)-(14) PREOBRAZOWATX W SOWER[ENNU@DIZ_@NKTIWNU@ NORMALXNU@ FORMU OT PEREMENNYH x; y; z ILI W FORMULU x&x SLEDU@]IE FORMULY:1) xy;2) x _ y (xz _ y);3) x;4) xy _ yz _ x _ z;5) xy _ yz ;6) xyz _ x _ y _ z ;7) xy _ yz _ zx;8) xy _ yzx;9) (x _ y)(y _ z)(z _ x);10) x _ y _ y _ z _ z _ x;11) x yz _ x y _ z .3.4.

dOKAZATX, ^TO S POMO]X@ TOVDESTW (1)-(14) L@BU@ FORMULU ALGEBRY LOGIKI W BAZISE f_; &; g, SODERVA]U@ L@BOE PODMNOVESTWO IZPEREMENNYH x1; x2; : : :; xn, MOVNO PREOBRAZOWATX W SOWER[ENNU@ DIZ_@NKTIWNU@ NORMALXNU@ FORMU OT WSEH PEREMENNYH x1; x2; : : : ; xn ILIW FORMULU x1&x1.sISTEMA TOVDESTW W ZADANNOM BAZISE NAZYWAETSQ POLNOJ, ESLI DLQL@BYH DWUH \KWIWALENTNYH FORMUL C I D W \TOM BAZISE C MOVNOPREOBRAZOWATX W D, PRIMENQQ TOLXKO TOVDESTWA DANNOJ SISTEMY.3.5. dOKAZATX, ^TO SISTEMA TOVDESTW (1)-(14) QWLQETSQ POLNOJ DLQFORMUL W BAZISE f_; &; g.3.6. dOKAZATX, ^TO SISTEMA TOVDESTW ALGEBRY LOGIKI (2)-(9) QWLQETSQ POLNOJ DLQ FORMUL W BAZISE f_; &; g.173.7. pRI POMO]I \KWIWALENTNYH PREOBRAZOWANIJ (1)-(14) WYQSNITX,QWLQ@TSQ LI FORMULY F1 I F2 \KWIWALENTNYMI, ESLI1) F1 = xy _ yz _ zx, F2 = xyz _ x _ y _ z ;2) F1 = xy _ yz, F2 = (x _ y)(y _ z);3) F1 = x _ y _ y _ z _ z _ x, F2 = x yz _ x y _ z ;4) F1 = xy _ yz _ zx, F2 = (x _ y)(y _ z)(z _ x);5) F1 = xy _ xz , F2 = ((x _ z)(x _ y) _ y _ z ) yz ;6) F1 = xyz _ xyz, F2 = (x _ y)xy _ (y _ z )yz _ (x _ z)(x _ z );7) F1 = (x _ y)z _ (x _ y)z , F2 = x _ y z _ xy z;8) F1 = xy _ z u, F2 = (x _ y)(z _ u);9) F1 = xy _ z u xy _ zu, F2 = xy(z _ u) _ (x _ y) zu _ xy(z _ u)(z _ u);10) F1 = xyz yzu, F2 = yz _ x _ u;11) F1 = x _ y _ z _ u _ xyzu, F2 = xyzu _ (x _ y)z _ u;12) F1 = xy zu _ (x _ y)(z _ u), F2 = x yzu _ y zu _ zu.3.8.

pOSTROITX \KWIWALENTNYE PREOBRAZOWANIQ PRI POMO]I TOVDESTW (1)-(14) DLQ FORMUL F1 I F2, GDE:1) F1 = x _ yz _ yz, F2 = (x _ y _ z ) (x _ y _ x _ z );2) F1 = (xy _ z)(x _ y) _ x (y _ z _ ((x _ z)y)),F2 = (x _ y)(z _ x) _ (y _ z)(x _ z) _ xyz (x _ y);3) F1 = (x _ y) _ ((x _ y _ z ) (x _ y _ z)), F2 = y _ x _ z _ xy;4) F1 = x _ yz _ z y, F2 = (x _ y) x _ z _ x _ y (x _ z );5) F1 = ((x _ y) (x _ y)) xy _ (xy xy) _ x y, F2 = x _ y;6) F1 = xz _ xy _ xz, F2 = (yz ) (x _ z);7) F1 = ((xy _ xy) _ (x _ y)) ((x _ y) _ (x _ y)(x _ y)), F2 = xy;8) F1 = xy (xyz _ xyz), F2 = yxz (x _ y);9) F1 = (x _ (y _ z)) (y _ z ), F2 = (x _ y)(z _ x _ y)(x _ y _ z );10) F1 = x ((y _ z) (z _ y)), F2 = (xy _ xz ) (xy _ xz );11) F1 = x(y _ z )(y _ z), F2 = xyz _ xy xz ;12) F1 = (x _ z) (x _ y) (x _ z), F2 = y _ z _ xz;13) F1 = x (y z) _ yz , F2 = xy _ z (x y) _ xyz ;14) F1 = ((xy _ xy) _ x _ y)((x _ y) _ (x _ y)) (x _ y), F2 = xy;15) F1 = ((x _ y)z _ xy) (x _ yz (xz _ y)) _ xyz , F2 = (xy _ xz ) (yz _xz) (x _ y _ z) _ xyz.aNALOGI^NO TOMU, KAK \TO UKAZANO WY[E, OPREDELQ@TSQ PONQTIQ TOVDESTWA I POLNOJ SISTEMY TOVDESTW DLQ FORMUL NAD L@BYM BAZISOM WALGEBRE LOGIKI ILI W k-ZNA^NOJ LOGIKE.183.9.

pOSTROITX KONE^NU@ POLNU@ SISTEMU TOVDESTW DLQ KLASSA FOR-MUL NAD BAZISOM B , ESLI1) B = fxy; x y; 1g;2) B = fxy; x _ y; 0; 1g.3.10. fUNKCIEJ lINDONA (SM. [14]) NAZOWEM FUNKCI@ '(x1; x2) IZ 7ZNA^NOJ LOGIKI, ZADAWAEMU@ TABLICEJ 1.x1 n x2 0 1 2 3 4 5 60123456000000000000000 01 50 00 00 05 56 6tABL. 1.060005600000000000000bUDEM OBOZNA^ATX FUNKCI@ lINDONA '(x1; x2) = x1 x2 = x1x2.1) dOKAZATX, ^TO DLQ FUNKCII lINDONA SPRAWEDLIWY TOVDESTWAA1) (y y) x = y y, A2) x (y y) = y y, A3) x1(x2x3) = y y;Bm) ((: : : ((x1x2)x3) : : :)xm)x1 = y y PRI m = 1; 2; : : :;Cm) ((: : : ((x1x2)x3) : : :)xm)x2 = ((: : : (x1x2)x3) : : :)xm PRI m = 2; 3; : : ::2) wYWESTI S POMO]X@ TOVDESTW A1 I A2 TOVDESTWO x x = y y.3) dOKAZATX, ^TO S POMO]X@ TOVDESTW A1 A3, Bm (m = 1; 2; : : :),Cm (m = 2; 3; : : :) L@BU@ FORMULU W BAZISE IZ ODNOJ FUNKCII lINDONA MOVNO PREOBRAZOWATX LIBO W FORMULU x x, LIBO W FORMULU WIDA(: : : ((xi xi )xi ) : : :)xim , GDE WSE PEREMENNYE RAZLI^NY.4) pUSTX DLQ FUNKCII lINDONA SPRAWEDLIWO TOVDESTWO(: : : ((xi xi )xi ) : : :)xim = (: : : ((xj xj )xj ) : : :)xjn ;GDE WSE PEREMENNYE W LEWOJ ^ASTI RAZLI^NY I WSE PEREMENNYE W PRAWOJ^ASTI RAZLI^NY.

dOKAZATX, ^TO m = n I xik = xjk DLQ WSEH k.5) dOKAZATX, ^TO SISTEMA WSEH TOVDESTW A1 A3, Bm (m = 1; 2; : : :),Cm (m = 2; 3; : : :) QWLQETSQ POLNOJ SISTEMOJ TOVDESTW DLQ FORMUL WBAZISE, SOSTOQ]EM TOLXKO IZ ODNOJ FUNKCII lINDONA.bUDEM GOWORITX, ^TO FORMULA = xi xi : : : xim S PRAWILXNOJRASSTANOWKOJ SKOBOK OBLADAET SWOJSTWOM C n, ESLI1231231119223A) ONA SODERVIT TOLXKO PEREMENNYE x1; x2; : : : ; xn,B) NE IMEET PODFORMUL WIDA u u I u(vw),W) MEVDU PERWYM WHOVDENIEM PEREMENNOJ xi I WTORYM EE WHOVDENIEM (ESLI ONO ESTX) WSTRE^A@TSQ WSE PEREMENNYE x1; x2; : : : ; xn, OTLI^NYEOT xi .6) kAKIE IZ LEWYH I PRAWYH ^ASTEJ TOVDESTW A1 A3, Bm (m =1; 2; : : :), Cm (m = 2; 3; : : :) OBLADA@T SWOJSTWOM C n?7) pUSTX FORMULA 2 POLU^ENA IZ FORMULY 1 PRI POMO]I TOVDESTWA1 A3, Bm I Cm, GDE m < n.

dOKAZATX, ^TO ESLI FORMULA 1 OBLADAETSWOJSTWOM C n, TO I FORMULA 2 OBLADAET SWOJSTWOM C n.8) dOKAZATX, ^TO PRI n 2 \KWIWALENTNOSTX Bn NELXZQ POLU^ITX SPOMO]X@ TOVDESTW A1 A3; Bm (m < n); Cm (m < n).9) dOKAZATX, ^TO DLQ FORMUL W BAZISE IZ ODNOJ FUNKCII lINDONA NESU]ESTWUET KONE^NOJ POLNOJ SISTEMY TOVDESTW.x 4. |KWIWALENTNYE PREOBRAZOWANIQ KONTAKTNYH SHEMdWE KONTAKTNYE SHEMY S ODINAKOWYM ^ISLOM m POL@SOW NAZYWA@TSQ\KWIWALENTNYMI, ESLI IH POL@SA TAK ZANUMEROWANY, ^TO DLQ L@BYHNOMEROW i; j FUNKCII PROWODIMOSTI fij MEVDU POL@SAMI S NOMERAMI iI j W PERWOJ SHEME I gij MEVDU POL@SAMI S NOMERAMI i I j WO WTOROJSHEME SOWPADA@T.tOVDESTWOM DLQ KONTAKTNYH SHEM NAZYWAETSQ PARA \KWIWALENTNYHKONTAKTNYH SHEM, SOEDINENNYH ZNAKOM !.eSLI ZADANO NEKOTOROE TOVDESTWO, TO S^ITAETSQ, ^TO ZADANY TAKVEWSE TOVDESTWA, KOTORYE POLU^A@TSQ IZ DANNYH S POMO]X@ SLEDU@]IHOPERACIJ:1) ODINAKOWAQ PERENUMERACIQ POL@SOW W OBEIH ^ASTQH TOVDESTWA;2) PEREIMENOWANIE ODINAKOWYH PEREMENNYH W PROIZWOLXNYE ODINAKOWYE PEREMENNYE (W ^ASTNOSTI, RAZNYE PEREMENNYE MOVNO PEREIMENOWYWATX W ODINAKOWYE);3) DLQ NEKOTORYH PEREMENNYH ZAMENA WS@DU x ! x; x ! x.pODMNOVESTWO 1, SOSTOQ]EE IZ NEKOTORYH WER[IN I KONTAKTOW SHEMY , NAZYWAETSQ PODSHEMOJ SHEMY , ESLI W 1 NEKOTOROE (MOVET BYTXPUSTOE) PODMNOVESTWO WER[IN S^ITAETSQ POL@SAMI I PRI \TOM:1) ESLI WER[INA IZ 1 QWLQETSQ POL@SOM W , TO ONA QWLQETSQ POL@SOM I W 1;11202) ESLI WER[INA IZ 1 INCIDENTNA KONTAKTU IZ n1, TO ONA QWLQETSQPOL@SOM W 1.pRIMENENIE TOVDESTWA K KONTAKTNOJ SHEME SOSTOIT W WYDELENIIW PODSHEMY, SOWPADA@]EJ S ODNOJ ^ASTX@ TOVDESTWA, I ZAMENE \TOJPODSHEMY NA SHEMU IZ DRUGOJ ^ASTI TOGO VE TOVDESTWA S SOHRANENIEMNUMERACII POL@SOW.sISTEMA TOVDESTW DLQ KONTAKTNYH SHEM NAZYWAETSQ POLNOJ, ESLIDLQ L@BYH DWUH \KWIWALENTNYH KONTAKTNYH SHEM ODNU W DRUGU@ MOVNOPREOBRAZOWATX, PRIMENQQ TOVDESTWA IZ DANNOJ SISTEMY.oSNOWNOJ NAZOWEM SLEDU@]U@ SISTEMU TOVDESTW (W TOVDESTWAH t3 It5 DOPUSKAETSQ SOWPADENIE POL@SOW):t1 :! ?t2 :t3 :t4 :t5 :t(6m) :111x1x2x1x1x213x11xm2!2x12x1 2x2: ::!x21!122x21 x2x1x1 2! 1 x1!x1x1321tEOREMA 4.1 (w.

l. mURSKIJ [16]). sISTEMA TOVDESTW t1 { t5, tm6 ,21m = 1; 2; : : :, QWLQETSQ POLNOJ.4.1. pRI POMO]I \KWIWALENTNYH PREOBRAZOWANIJ t11; 2; : : :) DOKAZATX \KWIWALENTNOSTX SHEM:1)2)3)4)5)6)11xxx1!!2yy21 x12xxy 2xyxyx12x!1 x!1!1!1222x3x11yyx32xx22y2t5; t6(m)(m =7)8)9)10)11)12)13)1x1x1xx1y1 x12x1 x!yxx1y 2yy22zx2x 2y3yz2y2yx!1!1 xx!1 xx!1 y! 1 xx!2yx3yzx1 yyy2yyz 23zx 2y3x zx2yz 2cEPO^KU I KONTAKTOW x1 ; x2 ; : : : ; xnn , SOEDINQ@]IH POL@SA k I j ,1223BUDEM IZOBRAVATX KAKI12zWEZDOJ S CENTROM W POL@SE 1 NAZOWEM KONTAKTNU@ SHEMU WIDAp2I 1I II :::3p 1pUSTX PEREMENNYE x1; x2; : : : ; xn FIKSIROWANY, A ^ISLO j W DWOI^NOJSISTEME ZAPISYWAETSQ KAK 12 : : : n. tOGDA KONTAKTOM S POMETKOJ IjBUDEM OBOZNA^ATX CEPO^KU IZ n POSLEDOWATELXNO SOEDINENNYH KONTAKTOW x1 ; x2 ; : : : ; xnn .rASSMOTRIM SISTEMU OBOB]ENNYH TOVDESTW:TI :! ?12ITII :I~!1212(ZDESX I~ | CEPO^KA, POLU^ENNAQ IZ CEPO^KI I PROIZWOLXNOJ PERESTANOWKOJ KONTAKTOW)TIII :I0 I1 I2n 1n!22::::::n1221(ZDESX DOPUSKAETSQ SOWPADENIE POL@SOW I OTSUTSTWIE NEKOTORYH IZ NIH)TIV :1x2!x1 x24I0I2n...

I112ITV : 1TV I :TV II :3I 2I112II!2ITV III : p I 1 II :::p 1TIX : 1I33I 2I! 1 I!13I21!! 1I2I2I I I1p3I:: :p 13I 24.2. wYWESTI IZ OSNOWNOJ SISTEMY TOVDESTW OBOB]ENNYE TOVDESTWATI { TIX .kANONI^ESKOJ KONTAKTNOJ SHEMOJ DLQ BULEWOJ FUNKCII f (x1; : : : ;xn), OTLI^NOJ OT KONSTANTY 0, NAZOWEM DWUHPOL@SNU@ KONTAKTNU@ SHEMU, SOSTOQ]U@ IZ CEPO^EK, SOEDINQ@]IH POL@SA I NE IME@]IH OB]IHWER[IN, KROME POL@SOW, I SOOTWETSTWU@]IH WSEM KON_@NKCIQM SOWER[ENNOJ DIZ_@NKTIWNOJ NORMALXNOJ FORMY FUNKCII f . dLQ KONSTANTY0 KANONI^ESKOJ KONTAKTNOJ SHEMOJ NAZOWEM KONTAKTNU@ SHEMU, SOSTOQ]U@ IZ DWUH IZOLIROWANNYH POL@SOW. kANONI^ESKOJ MNOGOPOL@SNOJKONTAKTNOJ SHEMOJ NAZOWEM OB_EDINENIE NEPERESEKA@]IHSQ PO WNUTRENNIM WER[INAM DWUHPOL@SNYH KANONI^ESKIH KONTAKTNYH SHEM, POSTROENNYH DLQ KAVDOJ PARY POL@SOW.25pRIWESTI KONTAKTNU@ SHEMU, W KOTOROJ IME@TSQ TOLXKO PEREMENNYEx1; : : : ; xn, K KANONI^ESKOMU WIDU MOVNO PRI POMO]I SLEDU@]EGO ALGORITMA ([16]).1.

kAVDYJ KONTAKT S POMETKOJ xi ISHODNOJ KONTAKTNOJ SHEMY ZAMENQEM NA DWUHPOL@SNU@ PODSHEMU W SOOTWETSTWII S TOVDESTWOMTIV , WiinKOTOROM Ij | CEPO^KI KONTAKTOW WIDA x1 ; : : : ; xi 1 ; xi+1 ; : : : ; xn .2. pUSTX a | PROIZWOLXNAQ WER[INA ISHODNOJ KONTAKTNOJ SHEMY, NEQWLQ@]AQSQ POL@SOM I IZOLIROWANNOJ WER[INOJ.1) pRIMENQQ TOVDESTWO TV III DLQ KAVDOJ ZWEZDY S CENTROM W WER[INE a DOBIWAEMSQ TOGO, ^TOBY IZ WER[INY a ISHODILI TOLXKO RAZLI^NYECEPO^KI KONTAKTOW.2) pO TOVDESTWU TIII WER[INU a WMESTE SO WSEMI CEPO^KAMI KONTAKTOW, ISHODQ]IMI IZ NEE, UDALQEM.pOWTORQQ PP.

Характеристики

Список файлов книги