В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин и др. - Задачи по курсу Основы кибернетики (2002) (1124121), страница 9
Текст из файла (страница 9)
E. NAWYHODE SHEMY zi), TO NA NABORAH TESTA FUNKCIQ NEISPRAWNOSTI, REALIZUEMAQ NA WYHODE SHEMY zi 1, OTLI^IMA OT WSEH FUNKCIJ NEISPRAWNOSTI, WOZNIKA@]IH NA \TOM WYHODE PRI WSEWOZMOVNYH NEISPRAWNOSTQH WBLOKE S NOMEROM i 1. wSE NEISPRAWNOSTI W i-M BLOKE (1 i n), NEOTLI^IMYE PO ANALIZU FUNKCII NEISPRAWNOSTI NA EGO WTOROM WYHODE(T. E. NA WYHODE SHEMY zi), OTLI^A@TSQ NA NABORAH TESTA PO ANALIZUFUNKCII NEISPRAWNOSTI NA WYHODE SHEMY zi 1. nIVNQQ OCENKA DLINYTESTA SLEDUET IZ ZADA^I 6.18.1 DLQ BLOKA, WY^ISLQ@]EGO DWA STAR[IHRAZRQDA SUMMY.2) nABORY TESTA POROVDA@TSQ SLOWAMI DLINY 2n SLEDU@]EGO WIDA: [00]i 111[01]n i, [11]i 100[01]n i (i = 1; n), PORQDOK PEREMENNYH |xn; yn; : : : ; x2; y2; x1; y1.
uKAZANIE. dLQ POSTROENIQ TESTA ISPOLXZUETSQTABLICA NEISPRAWNOSTEJ IZ ZADA^I 6.18.2. nIVNQQ OCENKA SLEDUET IZKONSTRUKTIWNYH SOOBRAVENIJ.3) nABORY TESTA POROVDA@TSQ SLOWAMI DLINY 2n SLEDU@]EGOWIDA: [01]n, 10[01]n 1, 00[10]n 1, 01[10]n 1, PORQDOK PEREMENNYH |an; bn; xn 1; yn 1; xn 2; yn 2; : : : ; x2; y2; x1; y1. uKAZANIE. dLQ POSTROENIQTESTA ISPOLXZUETSQ TABLICA NEISPRAWNOSTEJ IZ ZADA^I 6.18.3.6.22. (S. M. Reddy [23]). uKAZANIE.
rASSMOTRITE RAZLOVENIE BULEWOJ FUNKCII f (x1; : : : ; xn) W POLINOM vEGALKINA, REALIZUQ CEPO^KAMI FUNKCIONALXNYH \LEMENTOW KAK MONOTONNYE KON_@NKCII,TAK I SUMMU PO MODUL@ DWA. pRI \TOM NA ODIN IZ WHODOW \LEMENTA SUMMY PO MODUL@ DWA, NAIBOLEE UDALENNOGO OT WYHODA SHEMY, PODAETSQ WYHOD CEPO^KI, REALIZU@]EJ OTLI^NU@ OT KONSTANTYMONOTONNU@ KON_@NKCI@ NAIMENX[EJ DLINY (PUSTX \TA KON_@NKCIQ IMEET WID xi : : : xis ). tOGDA MNOVESTWO NABOROW f(0; : : : ; 0);(1; : : : ; 1); (0; 1; : : :; 1); f(1; 0; 1; : : :; 1); : : :; (1; : : :; 1; 0); (0; 1; : : :; 1);(0; : : : ; 0; 1; 0; : : :; 0; 1; 0; : : :; 0) (W POSLEDNEM NABORE ROWNO s EDINIC, STOQ]IH NA MESTAH PEREMENNYH xi ; : : : ; xis ) MO]NOSTI (n + 3) OBRAZUET1160EDINI^NYJ PROWERQ@]IJ TEST DLQ \TOJ SHEMY.6.23.
(w. n. nOSKOW [17]). uKAZANIE. wERHNQQ OCENKA O^EWIDNA. dLQDOKAZATELXSTWA NIVNEJ RASSMOTRITE FUNKCI@ x1x2 : : : xn _ x1x2 : : : xn.6.24. (i. a. ~EGIS, s. w. qBLONSKIJ [22]). uKAZANIE. iSPOLXZUJTEASIMPTOTI^ESKI NAILU^[IJ METOD SINTEZA SHEM.6.25. uKAZANIE. dOKAZATELXSTWA PROWODQTSQ OT PROTIWNOGO.7.1. 1) sLEDUET IZ (6.1){(6.3). 2) dOSTATO^NO ISPOLXZOWATX (6.5). 3)dOSTATO^NO WYRAZITX () ^EREZ WEROQTNOSTI (Ei; ).7.2. 1)5 (M) = (M) = 41 : 2) (M) = (M) = 167 : 3) (M) =(M) = 9 :7.3.
1) p = 13 : 2) p = 41 :7.4. 1) dA. 2) dA.7.5. uKAZANIQ. 1) rEALIZUJTE SKOLX UGODNO NADEVNO FUNKCI@ xjy. 2)rEALIZUJTE SKOLX UGODNO NADEVNO FUNKCII x y I 1.k PARAGRAFU 77.6. 1) dOKAZATELXSTWO PROWODITSQ OT PROTIWNOGO. 2) iSPOLXZUJTEks, POSTROENNU@ PO SOWER[ENNOJ dnf FUNKCII x1 x2, A TAKVE REZULXTAT ZADA^I 7.6.1.7.7. uKAZANIE. iSPOLXZUJTE OPISANNOE W PREDISLOWII \KWIWALENTNOEPREOBRAZOWANIE SWQZNYH MNOGOPOL@SNYH PODSHEM, SOSTOQ]IH IZ KONTAKTOW ODNOGO WIDA.7.8.
1) uKAZANIE. aNALOGI^NO 7.7. 2) wOSPOLXZUJTESX TEM, ^TO SHEMAREALIZUET FUNKCI@ x1(x4 _ x3) _ x2, A TAKVE REZULXTATOM ZADA^I 7.6.1.7.9. sHEMY PREDSTAWLENY NA RIS. 36 I 37 SOOTWETSTWENNO.7.10. (w. m. rABINOWI^ [18]). uKAZANIE. k SHEME NA RIS. 21 NADODOBAWITX 4 KONTAKTA x1, x1, xn, xn TAK, ^TOBY PERWYE DWA BYLI BYINCIDENTNY POL@SU b (NO NE POL@SU a), WTORYE DWA | POL@SU a (NONE POL@SU b) SHEMY, I PRI \TOM KAVDYJ IZ NOWYH KONTAKTOW DOLVENBYTX SMEVEN S IME@]IMSQ W SHEME PROTIWOPOLOVNYM KONTAKTOM TOJVE PEREMENNOJ.7.11.
A) uKAZANIE. iSPOLXZUJTE REZULXTAT ZADA^I 7.10. B) w PODSHEME LINEJNOJ FUNKCII POMENQJTE MESTAMI PEREMENNYE x1 I x2, A DALEEUSOWER[ENSTWUJTE RE[ENIE IZ PUNKTA A) TEHNIKOJ, UPOMQNUTOJ W UKAZANII K ZADA^E 7.7.61x1ax2x3x3x2x2x3x1x1b a x3x2 x2x3x2x1 x2 x3 ax3 x1 xx2x 3b2 bx3 x1 x3x1 x1x2rIS. 38.rIS. 37.rIS. 36.7.12. sHEMA PREDSTAWLENA NA RIS. 38. uKAZANIE. nIVNQQ OCENKA SLOVNOSTI SLEDUET IZ ZADA^I 7.6.1.7.13. uKAZANIE. iSPOLXZUJTE PARALLELXNOE (POSLEDOWATELXNOE) SOEDINENIE SHEM, NA KOTORYH DOSTIGA@TSQ Lk (f ); : : :; Lks (f ).7.14. (e. w. wALENTINOW [13]).
uKAZANIE. A) wERHNQQ OCENKA. iSPOLXZUJTE PRI n = 3 SHEMY NA RIS. 21 I IZ RE[ENIQ ZADA^I 7.10, DALEEWOSPOLXZUJTESX REZULXTATOM ZADA^I 7.13. B) wERHNQQ OCENKA. iSPOLXZUJTE SHEMU NA RIS. 17 (PRI n = 3 I r = 2) I SHEMU NA RIS. 36, DALEEWOSPOLXZUJTESX REZULXTATOM ZADA^I 7.13. nIVNIE OCENKI SLEDU@T IZZADA^I 7.6.1.7.15. (a. i. rYBKO [19]). uKAZANIE.
pUSTX (a1; b1), (a2; b2); : : :, (as; bs)| UKAZANNYE W USLOWII ZADA^I s PAR WER[IN. dOSTROJTE K SHEME DWA IZOMORFNYH KONTAKTNYH DEREWA TAK, ^TO LISTXQMI PERWOGO DEREWA QWLQ@TSQ WER[INY a1; a2; : : : ; as, LISTXQMI WTOROGO | WER[INYb1; b2; : : : ; bs, WSE WNUTRENNIE WER[INY DEREWXEW QWLQ@TSQ NOWYMI, I DLQL@BOGO i, i 2 f1; 2; : : :; sg, PROWODIMOSTX MEVDU KORNEM PERWOGO DEREWAI ai RAWNA PROWODIMOSTI MEVDU KORNEM WTOROGO DEREWA I bi.162sPISOK LITERATURY[1] aHO a., hOPKROFT d., uLXMAN d., pOSTROENIE I ANALIZ WY^ISLITELXNYH ALGORITMOW, m.: mIR, 1979, 536 S.[2] gAWRILOW g. p., sAPOVENKO a. a., zADA^I I UPRAVNENIQ PO KURSUDISKRETNOJ MATEMATIKI, m.: nAUKA, 1992, 408 S.[3] g\RI m., dVONSON d., wY^ISLITELXNYE MA[INY I TRUDNORE[AEMYE ZADA^I, m.: mIR, 1982, 416 S.[4] kIBERNETI^ESKIJ SBORNIK (nOWAQ SERIQ), N 12, m.: mIR, 1975, S. 510.[5] lUPANOW o.
b., aSIMPTOTI^ESKIE OCENKI SLOVNOSTI UPRAWLQ@]IHSISTEM, m.: iZD-WO mgu, 1984, 137 S.[6] rEDXKIN n. p., nADEVNOSTX I DIAGNOSTIKA SHEM, m.: iZD-WO mgu,1992, 192 S.[7] sAPOVENKO a. a., nEKOTORYE WOPROSY SLOVNOSTI ALGORITMOW, m.:maks pRESS, 2001, 46 S.[8] qBLONSKIJ s. w., o NEWOZMOVNOSTI \LIMINACII PEREBORA WSEHFUNKCIJ IZ P2 PRI RE[ENII NEKOTORYH ZADA^ TEORII SHEM // dansssr, 124, 1, 1959, S. 44-47.[9] qBLONSKIJ s. w., oB ALGORITMI^ESKIH TRUDNOSTQH SINTEZA MINIMALXNYH KONTAKTNYH SHEM // pROBLEMY KIBERNETIKI, m.: nAUKA,wYP. 2, 1959, S. 75-121.[10] qBLONSKIJ s. w., wWEDENIE W DISKRETNU@ MATEMATIKU, m.: nAUKA,1986, 384 S.[11] qBLONSKIJ s. w., |KWIWALENTNYE PREOBRAZOWANIQ UPRAWLQ@]IHSISTEM.
mETODI^ESKAQ RAZRABOTKA PO KURSU \|LEMENTY KIBERNETIKI", m.: iZD-WO mgu, 1986, 40 S.[12] qBLONSKIJ s. w., nADEVNOSTX UPRAWLQ@]IH SISTEM. mETODI^ESKAQ RAZRABOTKA PO KURSU \oSNOWY KIBERNETIKI", m.: iZD-WO mgu,1991, 40 S.63dOPOLNITELXNAQ LITERATURA[13] wALENTINOW e. w., o SLOVNOSTI BULEWYH FUNKCIJ, OT TREH PEREMENNYH W KLASSE KONTAKTNYH SHEM, KORREKTIRU@]IH OBRYWY //tRUDY II mEVDUNARODNOJ KONFERENCII \dISKRETNYE MODELI W TEORII UPRAWLQ@]IH SISTEM" (kRASNOWIDOWO, 13-18 I@NQ 1997 G.),m.: dIALOG mgu, 1997, S.
10.[14] lINDON r. k., tOVDESTWA W KONE^NYH ALGEBRAH // kIBERNETI^ESKIJSBORNIK, WYP. 1, 1960, S. 246-248.[15] mADATQN h. a., pOLNYJ TEST DLQ BESPOWTORNYH KONTAKTNYHSHEM // pROBLEMY KIBERNETIKI, WYP. 23, m.: nAUKA, 1970, S. 103118.[16] mURSKIJ w. l., oB \KWIWALENTNYH PREOBRAZOWANIQH KONTAKTNYHSHEM // sB. \pROBLEMY KIBERNETIKI", WYP. 5, m.: fIZMATGIZ, 1961,S.
61-76.[17] nOSKOW w. n., o DLINAH MINIMALXNYH EDINI^NYH DIAGNOSTI^ESKIHTESTOW, KONTROLIRU@]IH RABOTU WHODOW LOGI^ESKIH SHEM // dISKRETNYJ ANALIZ, WYP. 32, nOWOSIBIRSK: iZD-WO im so an sssr,1978, S. 40-52.[18] rABINOWI^ w. m., o SAMOKORREKTIRU@]IHSQ KONTAKTNYH SHEMAHDLQ S^ET^IKA ^ETNOSTI // pROBLEMY KIBERNETIKI, WYP. 17, m.:nAUKA, 1966, S. 227-231.[19] rYBKO a. i., o SLOVNOSTI SAMOKORREKTIRU@]IHSQ KONTAKTNYH SHEM, DOPUSKA@]IH TESTIROWANIE // pROBLEMY KIBERNETIKI,wYP. 37, m.: nAUKA, 1980, S. 139-153.[20] tONOQN r. n., o EDINI^NYH TESTAH DLQ KONTAKTNYH SHEM, REALIZU@]IH LINEJNYE FUNKCII // iZW.
an aRM. ssr, T. VI, N 1, 1971,S. 61-66.[21] tONOQN r. n., nEKOTORYE TESTY DLQ KONTAKTNYH SHEM, REALIZU@]IH \LEMENTARNYE SIMMETRI^ESKIE FUNKCII // pRIKLADNAQ MATEMATIKA, MEVWUZOWSKIJ SBORNIK, WYP. 2, eREWAN: iZD-WO egu, 1983,S. 129-140.64[22] i. a. ~EGIS, s. w. qBLONSKIJ, lOGI^ESKIE SPOSOBY KONTROLQ RABOTY \LEKTRI^ESKIH SHEM // tRUDY mian sssr, T. 51, m., 1958,S. 270-360.[23] S. M. Reddy, Easily testable realization for logic functions // IEEETrans. Comput., 1972, N 1, p. 124-141.65sODERVANIEwWEDENIE : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3~ASTX 1. iNWARIANTNYE KLASSY I SLOVNOSTX ALGORITMOW : : : : : : : : : : : : 4x 1.
iNWARIANTNYE KLASSY : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4x 2. sLOVNOSTX ALGORITMOW : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7~ASTX 2. |KWIWALENTNYE PREOBRAZOWANIQ : : : : : : : : : : : : : : : : : : : : : : : : : : : 16x 3. |KWIWALENTNYE PREOBRAZOWANIQ FORMUL : : : : : : : : : : : : : : : : : : : : : : : : 16x 4. |KWIWALENTNYE PREOBRAZOWANIQ KONTAKTNYH SHEM : : : : : : : : : : : : : : 20~ASTX 3. nADEVNOSTX I KONTROLX UPRAWLQ@]IH SISTEM : : : : : : : : : : : : 29x 5. zADA^A KONTROLQ UPRAWLQ@]IH SISTEM.
tESTY DLQ TABLIC : : : : 29x 6. tESTY DLQ KONTAKTNYH SHEM I SHEM IZ FUNKCIONALXNYH\LEMENTOW : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 35x 7. oCENKA NADEVNOSTI SHEM. sAMOKORREKTIRU@]IESQ SHEMY : : : : : : 44oTWETY I RE[ENIQ : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 52lITERATURA : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6366.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
