В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин и др. - Задачи по курсу Основы кибернетики (2002) (1124121), страница 8
Текст из файла (страница 8)
uKAZANIE. wOSPOLXZUJTESX SWOJSTWOM: ESLI MONOTONNAQ FUNKCIQ RAWNA EDINICE NA NEKOTOROM NABORE,TO ONA RAWNA EDINICE NA WSEH SLEDU@]IH ZA NIM NABORAH.2) G) zADA^A PRINADLEVIT KLASSU P. uKAZANIE. wOSPOLXZUJTESX SWOJSTWOM: SOKRA]ENNAQ dnf MONOTONNOJ FUNKCII NE SODERVIT OTRICANIJPEREMENNYH.2) D) zADA^A PRINADLEVIT KLASSU P. uKAZANIE. wOSPOLXZUJTESX SWOJSTWOM: FUNKCIQ f (x1; : : : ; xn) MONOTONNA TOGDA I TOLXKO TOGDA, KOGDA DLQ KAVDOGO i, i = 1; : : : ; n, WERNO TOVDESTWOf (x1; : : : ; xi 1; 0; xi+1; : : :; xn) (f (x1; : : : ; xi 1; 1; xi+1; : : : ; xn) 1) = 0.3) A, G) zADA^I PRINADLEVAT KLASSU P.3) B), W) NP-POLNYE ZADA^I. uKAZANIE.
sWEDITE K RASSMATRIWAEMYMZADA^AM NP-POLNU@ ZADA^U OB OBRA]ENII dnf W NOLX (SM. ZADA^U 2.10P. 1)). pUSTX D | NEKOTORAQ NE RAWNAQ TOVDESTWENNO NUL@ dnf, A dnfD0 REALIZUET FUNKCI@ D t, GDE t | PEREMENNAQ, NE WSTRE^A@]AQSQ Wdnf D. tOGDA dnf D NA NEKOTOROM NABORE OBRA]AETSQ W NOLX TOGDA ITOLXKO TOGDA, KOGDA dnf D0 REALIZUET NESAMODWOJSTWENNU@ FUNKCI@.3) D) zADA^I PRINADLEVAT KLASSU P. uKAZANIE. wOSPOLXZUJTESX OPREDELENIEM SAMODWOJSTWENNOJ FUNKCII I SWOJSTWOM: ESLI l | ^ISLO SLAGAEMYH POLINOMA SAMODWOJSTWENNOJ FUNKCIIPROIZWOLXp 2, A r | RANGrNOGO EGO SLAGAEMOGO, TO WERNO NERAWENSTWO l 1 2 .4) A) zADA^A PRINADLEVIT KLASSU P.4 B) NP-POLNAQ ZADA^A (SM. ZADA^U 2 IZ WWEDENIQ K PARAGRAFU).k PARAGRAFU 33.1. 4)(x1(x2x3))(x4x5) = ((x1x2)x3)(x4x5) = (((x1x2)x3)x4)x5:3.2.
uKAZANIE. dOKAVITE INDUKCIEJ PO n, ^TO WYRAVENIE x1 x2 : : : xnS L@BOJ PRAWILXNOJ RASSTANOWKOJ SKOBOK MOVNO S POMO]X@ TOVDESTWA(6) PREOBRAZOWATX W WYRAVENIE (: : : ((x1 x2) x3) : : : xn 1) xn (SM.ZADA^U 3.1).553.3. uKAZANIE. 2) I 4) PRIWEDITE K WIDU xx, OSTALXNYE K SOWER[ENNOJDIZ_@NKTIWNOJ NORMALXNOJ FORME.2) x _ y (xz _ y) (1)= xy (xz _ y) (5=;4) xyxz _ xyy (5=;8) xx _ yy (14=;13) xx.5) xy _ yz (11)= (z _ z)xy _ (x _ x)yz (4)= zxy _ zxy _ xyz _ xyz (5)= xyz _(10;12)(13)xyz _ xyz _ xyz = (xyz _ xyz) _ xyz _ xyz = xyz _ xyz _ xyz:3.5.
sM. ZADA^U 3.4.3.6. wYWEDEM (1), ISPOLXZUQ (2)-(9): x1 _ x2 (3)= x1 _ x2 (2)= x1&x2 (3)=x1&x2:wYWEDEM (10), ISPOLXZUQ (2)-(9): x1 _ x2 (3)= x1 _ x2 (2)= x1 x2 (5)= x2 x1 (2)=(3)x2 _ x1 = x2 _ x1:uKAZANIE. dLQ WYWODA (11), (12) I (13) SWODITE, ISPOLXZUQ (2)-(3),DIZ_@NKCI@ K KON_@NKCII I OBRATNO I ISPOLXZUJTE (9), (6) ILI (7),SOOTWETSTWENNO. dLQ WYWODA (14) ISPOLXZUJTE (8) I (5).3.7. uKAZANIE: PRI POMO]I TOVDESTW (1)-(14) PRIWEDITE OBE FORMULYK SOWER[ENNOJ D.N.F. oTWET: 1), 3), 5)-11) | DA; 2), 4) | NET.3.8.
uKAZANIE: PRI POMO]I TOVDESTW (1)-(14) OBE FORMULY MOVNOPRIWESTI K SOWER[ENNOJ D.N.F.3.9. 1) uKAZANIE: POSTROJTE SISTEMU TOVDESTW, POZWOLQ@]U@ L@BU@FORMULU NAD BAZISOM B = fxy; x y; 1g PEREWODITX W POLINOM vEGALKINA.2) nAPRIMER: TOVDESTWA (4)-(7), (10), (12), (13) WMESTE S TOVDESTWAMI0&0 = 0, 1&1 = 1, x&0 = 0, x&1 = x, 0 _ 0 = 0, 1 _ 1 = 1, x _ 0 = x,x _ 1 = 1.k PARAGRAFU 44.2. uKAZANIE. TII : ISPOLXZUJTE TOVDESTWO t2; TIII : MNOGOKRATNO PRI-MENQJTE TOVDESTWO ZADA^I 4.2 P.
3) I TOVDESTWO t3; TIV : MNOGOKRATNOPRIMENITE TOVDESTWO t4 I TOVDESTWO ZADA^I 4.2 P. 3); TV : MNOGOKRATNOPRIMENITE TOVDESTWAt5 I t2; TV I : PRIMENITE TOVDESTWO TV , A ZATEM(n)TOVDESTWO t6 ; TV II : MNOGOKRATNO PRIMENITE TOVDESTWO ZADA^I 4.2 P.1); TV III : SNA^ALA PRIMENITE TOVDESTWO TV I , A ZATEM MNOGOKRATNO TOVESTWO TV ; TIX : PRIMENITE TOVESTWA TV I I TV .4.4. 1) nET; 2) DA.4.5. uKAZANIE. 2) dLQ ODNOJ IZ RASSMATRIWAEMYH SHEM WELI^INAR() RAWNA 1, DLQ DRUGOJ | 0; 3) DOKAZYWAETSQ ANALOGI^NO P.
2); 4)56SLEDUET IZ P. 3); 5) WYTEKAET IZ P. 4) S U^ETOM TOGO, ^TO ESLI W KLASSE WSEH KONTAKTNYH SHEM IMEETSQ POLNAQ SISTEMA TOVDESTW, TO W SILUTEOREMY 4.1 ONA IMEETSQ I SREDI OSNOWNYH TOVDESTW.k PARAGRAFU 55.1. 1) 2; 2) 3; 3) 2; 4) 3; 5) 2; 6) 3.5.2. 1) n; 2) n 1; 3) n 1; 4) n.5.3. uKAZANIE. dWA STOLBCA MATRICY M RAZLI^A@TSQ W j -J STROKE(2)TOGDA I TOLXKO TOGDA, KOGDA j -Q STROKA MATRICY M POKRYWAET SUMMUPO MODUL@ 2 \TIH STOLBCOW.5.5.
1), 4), 5), 7) | dA. 2), 3), 6), 8), 9) | wOOB]E GOWORQ, NET.5.6. pUSTX A I B | TUPIKOWYE TESTY MATRICY M S m STROKAMI.tOGDA NI ODNO IZ WKL@^ENIJ A B , B A NE IMEET MESTA. oTS@DAWYTEKAET, ^TO ^ISLO TUPIKOWYH TESTOW NE PREWOSHODIT MAKSIMALXNOGO^ISLA POPARNO NESRAWNIMYH NABOROW W B m, A ZNA^IT, NE PREWOSHODITWELI^INY bmm c .5.7. ~ISLO MATRIC RAZMERNOSTI k n S POPARNO RAZLI^NYMI STOLBCAMI RAWNO 2k (2k 1) : : : (2k n +1). ~ISLO MATRIC RAZMERNOSTI m n,U KOTORYH k STROK S FIKSIROWANNYMI NOMERAMI ZADANY, RAWNO 2n(m k).5.8.
1) f1; 2g, f1; 4g, f2; 3g, f3; 4g; 2) f1; 2; 3g, f1; 2; 4g, f1; 3; 4g; 5)f1; 2; 3g, f1; 2; 5g, f2; 3; 4g, f1; 4; 5g, f3; 4; 5g; 6) f1; 2; 3g, f2; 3; 5g, f3; 4; 5g.5.9. uKAZANIE. nIVNQQ OCENKA DOKAZYWAETSQ OT PROTIWNOGO IZ PREDPOLOVENIQ O SU]ESTWOWANII TESTA DLINY MENX[EJ, ^EM dlog2 ne. dLQDOKAZATELXSTWA WERHNEJ OCENKI IZU^ITE ^ISLO KLASSOW \KWIWALENTNOSTI, NA KOTORYE WSE n STOLBCOW MATRICY TUPIKOWOGO TESTA RAZBIWA@TSQ EE PERWYMI l STROKAMI (l 2 f1; : : : ; n 1g). dOSTIVIMOSTX NIVNEJ(WERHNEJ) GRANICY DOKAZYWAET MATRICA IZ ZADA^I 5.2.1 (SOOTWETSTWENNO 5.2.2 PRI k = 0).5.10.
nET. uKAZANIE. rASSMOTRITE MATRICU M (2), DOKAZYWAJTE OTPROTIWNOGO.5.11. uKAZANIE. rASSMOTRITE MATRICU M (2) I OCENITE SWERHU ^ISLOEDINIC W TEH EE STROKAH, KOTORYE SWQZANY S TESTOM.5.12. pUSTX T , T b1; me | TEST MATRICY M , A Ji, Ji b2; n + 1e| MNOVESTWO NOMEROW TEH STOLBCOW MATRICY M , KOTORYE OBRAZU@TGRUPPU S NOMEROM i, i = 1; :::; s, IZ USLOWIQ ZADA^I. pUSTX, DALEE, Ji0, i =1; :::; s, | MNOVESTWO TEH ^ISEL j , j 2 Ji, DLQ KOTORYH STOLBEC M hT; j iSODERVIT ROWNO ODNU EDINICU. tAK KAK W KAVDOJ STROKE PODMATRICY257M hT; Jii IMEETSQ NE BOLEE ODNOJ EDINICY, TO jJi0j + 2(jJij jJi0j) jT j,I, SLEDOWATELXNO, jJi0j 2jJij jT j.
sUMMIRUQ POSLEDNIE NERAWENSTWA PO WSEM i, i = 1; :::; s, I U^ITYWAQ, ^TO W PODMATRICE M hT i ^ISLO STOLBCOW, SODERVA]IH ODNU EDINICU, NE BOLX[E, ^EM jT j, POLU^IM:j T j 2n s j T j .k PARAGRAFU 66.1. f(100); (101)g, f(100); (111)g, f(101); (110)g, f(101); (111)g,f(110); (111)g.6.2. oTWETY PUNKTOW A) I B) SOWPADA@T: f(000); (001); (010)g, f(000);(001); (100)g, f(000); (010); (111)g, f(000); (100); (111)g, f(001); (010);(101)g, f(001); (100); (101)g, f(010); (101); (111)g, f(100); (101); (111)g.6.3. A) f(000); (101)g, f(011); (110)g; B) f(000); (011); (101)g, f(000);(101); (110)g, f(000); (011); (110)g, f(011); (101); (110)g.6.4. oTWETY PUNKTOW A) I B) SOWPADA@T: f(000); (001); (101)g, f(001);(101); (110)g, f(000); (001); (111)g, f(001); (110); (111)g.6.5. oTWETY PUNKTOW A) I B) SOWPADA@T: f(000); (100); (111)g, f(000);(101); (111)g, f(010); (100); (111)g, f(010); (101); (111)g.6.6.
f(100); (111)g, f(001); (010); (111)g, f(001); (010); (100)g.6.7. A) f(000); (011)g, f(000); (111)g; B) f(000); (011); (101)g, f(000);(101); (111)g.6.8. A) f(010); (101)g, f(100); (110)g, f(010); (100); (111)g; B) f(010);(100); (101)g, f(010); (100); (110)g, f(010); (100); (111)g, f(010); (101);(110)g, f(100); (101); (110)g.6.9.
uKAZANIE. dOKAZATELXSTWA PROWODQTSQ OT PROTIWNOGO.6.10. 1) uKAZANIE. nAJDITE r GRUPP PO (n r) KONTAKTOW W KAVDOJ,EDINI^NYE OBRYWY KOTORYH DA@T MATRICU, UDOWLETWORQ@]U@ (POSLEINWERTIROWANIQ) USLOWIQM ZADA^I 5.12; 2) (r. n. tONOQN [21]). rASSMOTRITE PRI n 2r MNOVESTWO NABOROW, POROVDAEMYH SLEDU@]IMI SLOWAMI DLINY n W ALFAWITE f0; 1g: 0s 1r 0n s r , 1s 0n1r s , 1s [01]r s 0n 2r+s ,0s [01]s 0n 2r s , 0n 2r+s [01]r s 1s (s1 = 0; n r, s2 = 1; r 1, s3 =0; r 1, s4 = 1; n 2r, s5 = 1; r 2).6.11.
n + 1.6.12. 1) 2. 2) uKAZANIE. iSPOLXZUJTE METOD DIHOTOMII, T. E. DELENIQSHEMY NA DWE ^ASTI.6.13. A) 2n 1, B) 2n 1, W) 2n.1144455558223336.14. uKAZANIE. rASSMOTRITE NABORY EDINI^NOJ SFERY I EE CENTR.dOSTIVIMOSTX OCENKI PROILL@STRIRUJTE NA SHEME, POSTROENNOJ PO METODU KASKADOW.6.15. (h. a. mADATQN [15]). uKAZANIE. dOKAVITE, ^TO SREDI NEISPRAWNYH SHEM NAJDUTSQ SHEMY, REALIZU@]IE OBE KONSTANTY, A TAKVESHEMY, REALIZU@]IE ILI x1 x2 xnn , ILI x1 _x2 _ _xnn DLQ L@BOGONABORA (1; 2; : : : ; n).6.16. 1) uKAZANIE. rASSMOTRITE IZOLIROWANNYJ BLOK \TOJ SHEMY. 2)A) 2 PRI ^ETNYH n, 3 PRI NE^ETNYH n; B) 4; W) 6 PRI ^ETNYH n, 7 PRINE^ETNYH n.
3) (r. n. tONOQN [20]). uKAZANIE. iSPOLXZUJTE METOD DIHOTOMII. dLINA TESTA NE BOLEE, ^EM NA KONSTANTU, OTLI^AETSQ OT log2 n.4) A) (r. n. tONOQN [20]). uKAZANIE. iSPOLXZUJTE METOD DIHOTOMII. B)uKAZANIE. iSPOLXZUJTE METOD DELENIQ SHEMY NA 4 ^ASTI.6.17. (n. p.
rEDXKIN [6]). uKAZANIE. rASSMOTRITE ks, REALIZU@]U@FUNKCI@ f (x1; : : : ; xn) I POSTROENNU@ PO FORMULE (Kf (x1 _ x1)) (Df (x1 _x1)), GDE Kf I Df | KON_@NKTIWNAQ I DIZ_@NKTIWNAQ SOWER[ENNYENORMALXNYE FORMY FUNKCII f .6.18. 1) A) f(00); (01); (11)g, ^ISLO TESTOW | 2; B) f(001); (010); (011);(110); (111)g (PORQDOK PEREMENNYH | x; y; q0), ^ISLO TESTOW | 12. 2)f(001); (011); (110)g (PORQDOK PEREMENNYH | x; y; q0).
3) f(1000); (0001);(0110)g (PORQDOK PEREMENNYH | a; b; x; y). 4) f(0000); (0111); (1111)g.6.19. 2) uKAZANIE. rASSMOTRITE SHEMU NA RIS. 25 I ZAMETXTE, ^TONEISPRAWNOSTX TIPA 0 NA WYHODE TRETXEGO SLEWA INWERTORA W NIVNEMRQDU INWERTOROW OBNARUVIWAETSQ LI[X NA NABORE (0001), NE WHODQ]EMW TEST IZ ZADA^I 6.18.4.6.20. (n. p. rEDXKIN [6]). uKAZANIE. iSKOMAQ SHEMA STROITSQ PO INDUKCII IZ BLOKOW, KAVDYJ BLOK PODOBEN SHEME NA RIS.
22 A) BEZ WYHODAz1. tEST IZ ^ETYREH NABOROW: (0; 0; 0; : : :; 0), (1; 0; 0; : : :; 0), (0; 1; 1; : : :; 1),(1; 1; 1; : : :; 1).6.21. 1) wWEDEM OBOZNA^ENIE:10 01BB 11M =BB@ 11011111010000 011101000111121010001111120 10011BC01 C11 CBCBC11 C;N=11:BCC@ 01 A11 A0100mATRICA TESTA T RAZMEROM 5 2n PRI \TOM BUDET IMETX WID T =59(M 0MM : : : MN ), GDE MATRICA M 0 POLU^AETSQ IZ MATRICY M WYBRASYWANIEM NUVNOGO KOLI^ESTWA PERWYH STOLBCOW (PORQDOK PEREMENNYH |x1; y1; x2; y2; : : : ; xn; yn). uKAZANIE.
dLQ POSTROENIQ TESTA ISPOLXZU@TSQ TABLICY NEISPRAWNOSTEJ IZ ZADA^I 6.18.1. pRI \TOM SU]ESTWENNYSLEDU@]IE FAKTY. l@BAQ NEISPRAWNOSTX BLOKA S NOMEROM n WIDA 1SHEMY n OBNARUVIWAETSQ PO ANALIZU FUNKCII NEISPRAWNOSTI NA EGOWTOROM WYHODE (T. E. NA WYHODE SHEMY zn). eSLI NEISPRAWNOSTX W BLOKE SNOMEROM i, 1 < i < n, NE OBNARUVIWAETSQ NA EGO WTOROM WYHODE (T.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
