Baixe o app para aproveitar ainda mais
Prévia do material em texto
USP -ESCOLA POLITÉCNICA PCS - DEPARTAMENTO DE ENGENHARIA DE COMPUTAÇÃO E SISTEMAS DIGITAIS PCS - 3115 Sistemas Digitais I – 1o Semestre de 2016 Exercícios para nota (respostas escritas à mão) Entrega até 29 de abril de 2.016 (sexta-feira), às 17:00, na Secretaria do PCS No. USP _________ Nome ___________________________________ Turma ____ 1-) [2,0 pontos] Sabe-se que em uma álgebra de chaveamento as sentenças lógicas podem ser interpretadas por meio de expressões booleanas, havendo uma correspondência entre estas e circuitos físicos. Deriva-se daí que se pode interpretar e/ou realizar fisicamente as sentenças lógicas por meio de circuitos baseados em chaves elétricas, cuja abertura (ou fechamento) é controlada por uma variável X. Estas chaves podem estar fechadas (permitem a passagem de corrente, X = 1) ou abertas (não permitem a passagem de corrente, X = 0). Dois conjuntos distintos de chaves interconectadas são considerados “iguais” em termos de comportamento lógico, se permitem ou não a passagem de corrente, para os mesmos estados de todas suas chaves. Pode-se definir (obter) a operação lógica OU (E) por meio de duas chaves interconectadas em paralelo (série). Pode-se definir o nível 1 como uma “chave sempre fechada” e o nível 0 como uma “chave sempre aberta”. Pede-se que se realize o desenho esquemático de circuitos com chaves nas situações que se apresentam a seguir. 1.a-) Para representar os seguintes axiomas: 1.a.1-) Se X = 0, então ~X = 1; 1.a.2-) 1 . 1 = 1; 1.a.3-) 0 + 0 = 0; 1.a.4-) 1 . 0 = 0; 1.a.5-) 1 + 0 = 1. 1.b-) Para representar os seguintes teoremas: 1.b.1-) (X + Y) . Z = X . Z + Y . Z; 1.b.2-) X . Y + Z = (X + Z) . (Y + Z); 1.b.3-) X + 0 = X; 1.b.4-) X . 1 = X; 1.b.5-) X + X . Y = X. 2-) [2,0 pontos] .De maneira equivalente ao disposto no Exercício 1 pode-se definir uma álgebra conjuntista onde os elementos desta álgebra são constituídos pelo conjunto potência PotS de um conjunto S qualquer. Por exemplo, se S = {a, b, c} então PotS = {φφφφ, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}. As operações relacionadas são a União (correspondente à operação +), a Intersecção (correspondente à operação .) e o Complemento (correspondente à operação ~). Usando diagrama de Venn demonstre que: 2.a-) X . Y + X . ~Y = X; 2.b-) (X + Y) . (X + ~Y) = X. 3-) [2,0 pontos] . Sabe-se que para uma função de chaveamento fn(x, y, ..., z) pode-se definir (obter) sua função dual fnDUAL(x, y, ..., z) da seguinte forma: fnDUAL(x, y, ..., z) = ~[fn(~x, ~y, ..., ~z)] Sabe-se que se duas funções são idênticas em termos funcionais elas compõe uma identidade. Há um teorema que comprova que se duas funções são iguais (são uma identidade) as funções duais destas também são uma identidade (dita identidade dual). Dada a identidade a seguir encontre sua identidade dual: X . Y + X . Z = X . (Y + Z) 4-) [2,0 pontos] Entre as técnicas conhecidas para a extração da primeira forma canônica (soma de mintermos) e da segunda forma canônica (produto de Maxtermos) de uma função de chaveamento encontra-se a identidade de Shannon. Também é possível atingir o mesmo objetivo aplicando-se uma operação lógica E (chamada comumente de multiplicação) de um termo produto da função com 1, de maneira que este 1 agregue ao termo produto a literal correspondente à variável que falta no termo produto. Por exemplo, imaginemos o termo produto ~x3 . x1 onde falta a literal correspondente a x2. Realiza-se a multiplicação por 1, onde 1 = (x2 + ~x2), obtendo-se os termos produto ~x3 . x2 . x1 e ~x3 . ~x2 . x1. De maneira análoga pode- se aplicar uma operação lógica OU com 0 (chamada comumente de soma) a um termo soma da função para agregar ao termo soma a literal correspondente à variável que falta neste. Para a função que segue utilize os dois métodos propostos para extrair a primeira e a segunda, formas canônicas, da função dada: f(x3, x2, x1) = x3 . x2 + ~x2 . ~x1 5-) [2,0 pontos] Três Acadêmicos de Oxford, A, B e C, colecionam livros e/ou manuscritos antigos, raros, de acordo com preferências pessoais. Mr. A coleciona trabalhos políticos do idioma Inglês e também novelas escritas em outras línguas estrangeiras (que não o Inglês). Mr. B coleciona toda espécie de trabalhos políticos, mas desde que estes não sejam novelas que foram escritas em Inglês. Ele também coleciona trabalhos em Inglês, mas desde que estes trabalhos não sejam novelas (ficções). Mr. C coleciona itens não ficcionais (ele detesta ficções, novelas, preferindo a realidade) e que sejam ainda, ou trabalhos escritos no seu idioma nativo (Inglês), ou trabalhos políticos escritos em idiomas estrangeiros (que não o Inglês). Encontre aqueles livros/manuscritos para os quais existe competição entre os Acadêmicos. Em outras palavras, determine quais são os livros desejados por dois quaisquer, entre os três Acadêmicos. Sugere-se montar o modelo do problema em termos de conjuntos adotando as seguintes definições iniciais: A = Conjunto de livros colecionados por Mr. A; B = Conjunto de livros colecionados por Mr. B; C = Conjunto de livros colecionados por Mr. C; Z = Conjunto de livros colecionados (desejados) por dois quaisquer, entre os três Acadêmicos. Por meio de operações de união, intersecção e complemento de conjuntos encontre a expressão de Z em função de A, B e C. Escolha e defina outros conjuntos que permitam modelar os desejos dos colecionadores e determinar a expressão dos conjuntos A, B e C em função destes. Sugere-se a adoção de letras mnemônicas – Se o conjunto for de obras Políticas adotar P, etc. Uma vez encontradas as expressões de A, B, C e Z por operadores conjuntistas, encontre as expressões Booleanas equivalentes, interpretando os conjuntos como variáveis Booleanas e os operadores união, intersecção e complemento como operadores Booleanos, “+”, “.” e complemento. Simplifique a expressão Booleana de Z, justificando cada passo relevante com a técnica usada (De Morgan, propriedade distributiva, Axioma, etc.) e interprete o resultado obtido para Z, resumindo o que há em comum entre os colecionadores. Krïpesi|:ijr#3jïï*i"."ì{'#3È"'^à,NHARrADECoMpurAÇÀoE Depêriamenlo de En9ênhaÍìa de Compúìâção PCS - 3115 - Sistemas Dieitais I - 1" Semestre de 2016 Exercícios para nota (respostas escritas à mão) de abril de 2.016 (sexta-feira), às 16:00, na Secretaria do PCSEntrega até 29 No. USP 1-) [2,0 pontos] . 2-) 12,0 pontosl . 3-) [2,0 pontos] . 4-) 12,0 pontosl . Nome Turma Pr:s 3liS €t.*ciritt Z ytc,,tc_ ^ &r, Z ol( 6r i!ï**iâ^^ <- (16'v\c1gl^,-) ) ox *õ 1 cll. J,, -'ftttux> Ìo+trr^n^.,.a 1 .prwt rte1 t*,rc^ (=ü_.^riu,...líru",,. -t-,*[t; .t-rftw /i!-ll^"=a- -{- cü -,$W pÕ&^r&) 1wri.- >e_ ,1 ^V ^"ha1wrj?,Jì. 'r*/cm r.u-,9),5r-',,-, {uta*ot s-maz@ -a .rz,"Qtg:v l4* [*^^tf "lR- üü--.U l.r4.rr.._f_,;,. .arl^ ,À"**u! f*n, &*/yu4*,^^ e,ff<, (+"Arr)u. ffi""*- c.^- f :r,!r,ziQ,r.r,ro ".ae- *-*X{til-"J,- ,,bsn'üa (16 fi:t"u^t''- (r.- pc.^*i..ii * r',^ffi" *t''l^Xt-<-^ @# "{'{t'úv +P r"tw+" /46fl010 r.?a.u 1ne.trl*í,* 6gffi,ff.*z Çtì ê"&eç'í* À&-"ee"pzÈtÁ, ,luü @"'Át"+dlq ".{U^,..rL{' -u*^- -ffiw*ag *$-* *-.3.o..ra-,r'ifi-:,n^:,,:fo kíTr"â r '1.u gv'txalfr- ó41 rltq-.: ì .O- pa,vrQ lr-Â.r" 'i.r (1t,J'úa;fu f,1/\t'. ;iJ ap-';irQS"*: g;i*Ln', *itq fuJo" 5, {'f"4a1'+'+ 1,, n4) F,':.{.,-.ir àq:\aü} a- t>,l''anc;.;a "oJ'Fà 'i,r"t'-7 rú'.r*n)> n6tt'*^'atXà'l -2r,.-^- f{}^.Qúa ( +ú"A1 . Fnar+o- o' 'níN t co^^+ /'Lu^-'- ,,,A^ri,4-.{r-2 p,,wa"'r . .} ,-',n-Q.0*."{Â}6?* '!otve* 4\4''s--, o )rrfr, . c. etw.r-f ,o-^pz"hnprfÈr1r;[t;a; c4",/"< $tz,at'.,-ra- cd/^^)<:Õ '-'7 ,,te^f,L ú:t* x=! 'gaAtual r'Ap*t1 t'tt"('t'7'c' w (AtÀi-!u -+/.1'^a24Ã"'"' b & 'c;n,:i-&o t** ''&*w>"-'taa z)fr-^jpz 7^t 4tA&)^'\'' frt l @j yr,.nr- ^r1u,uc.* 04 *7-^Íu c)4't &'1"vL.pa a- X:C ,a^F6 F=l x=o X. 1 / --{ êr*--- .-*''g..*--,crìrrê ttr -rod.-ë J J. J#= C+O =o o ,--O 15*t -ì c t-L -*Õ â-l ! rO dr) .{" *: _**{}***dd"ìq*r [si ] f;.^1, .34;JsyCr".. "" ,rXú.tf ,fy,e,-uÒ (x + Y) ? )< x.z +- Y.Z XY+Z v X"t _ X t*lo-= ï -P*-* ")< ï-'-ê --{ L-ó' z O---ì I -l-.Õ, J x#c )< à "*o/*^* Õ X-.. .x _1 -*c3 a.__-. @ )p ,^^*i^t". .".d* ,n-Qo-ti ,-,a *reffi trltf,fu Lqt I ta,+ exrrx. c-tO í fCcl;-- t- ^Llr^* )4)4_ ,1 1..- t- . ço*yr[.^,fr" o...b on ah^^<m"T lffi^"-,*''* c,o^.,üffi".ep fri* ,"-/-* P"fr,*r,J'U'""- çt't^á- s ep+-ofueU-zn ,. Prn a,Nz-7Lt 1 nt S = í'19tcl t^frs @ pl;üs = í(,í*5,7 f i, 1r 3, í",bJ, 1-,.j l{ç.ú, í.,s,41J" {<,1 Orya.nu1;ro ^n}..<^o-ut^.,rtq<,a zttfr .;, U.^^a'c$ (.t". f*-A"4 - ,a,tn4fi y) -- - 1-q/1^-i* (,yu,taçza ,/ , Wr^"4,,- t!eagr<rr^- d" VQrvrr4, drptr'''fli : X Y +x Y) = >< (x+Y)"(x*D=X. \ I I I I I I . ìì xi ÌIt1 I f*+4. ( *+V !. ì- \ .t a^ *Çn (*+v) =\ /]a) <^ /'-lJ(*LQ - 1.Q-- [a r t,- ,ê) n* P*C* /-tx<l-<^ 1+Cr-+e- o bfrr, tçt I l*V^ .-{.2 .4.u'.,rzt "^-"-S 44t* {ar Ja à^<A_ :r^ f,f'^" (,,,y,. ',;) à,(" ""N {,r*,.: f ï'^'(' '{' \i) (2,{, õ)5-be-4e- T^" 44 àr,+,c,2 {t*ft .á ìàlpü-roo ",*- úr{t""^or {-wan,;o "-"lL c^>-pfu n.^ ,t âu,fr,L,&, . tçí ^^.--{urrpr=<, ol*^a" "^ &-flAvví. ,iy , ++ dtttc p"rfi t+4ão,^ -<^ ila,lì),/"0,, ) o-J l,^3fu l*aiy aht^ â:/É aõ ,r^^--<--, oâ,*fi,"ç.;1. ( árh ucí.I.fid^a. a- !) ' Nr.rlz- a.- à&-Á.\<,-AP q aa{gw <,^-,<e^':h 446 ^'4!'fr/o,4 ,A^ol . xY+xZ =X{Y+e) 4i'i9.,0.e\: i\m=,u,dd --çffJ'(v,7> : (f+ ï> , (í +7\ =F+Y) , C *+1\ €L 4 "ao*Ii à1^&.!-, ,*,"u"ç*$. ( x+ y) , {x*7\ ï ,fÃ..* {í'ii,ïyq1. x t v-}ã) =7+affi =x+(í,1\ = X+ LY ,1> .:: x+y-A -{.. : X + y,u c-^* S-8a^rrvrtt'ra*y - -í''''"'''$12 "n r'ud'l 'eftt?t Ò M"*&' cb.f,ltnla' r*r,,ú6 il(iur",Lo yoz ! Ã'Ao4 oz fii"-'-ez-11'nzt d,& o*-.t-,- .(\> AÃ!14- y.r',ro"fr2 .bL1^ ,, JU6;u,4 fx"-. o'16r"2 ' -#- Y t" n ,,, .. .r- rc, -'L-- 1o o ,u.tr].2-o-> -.*6tvx, clz- íJ^rt'> 0'< -a'^4L@ / 4<P--a*+/ -< 76r'.'-e7-trè-'Ìp y,ru'nr-- -ozffi"u'4 a ^4@)-@ ' Y^- d.- Wf T- *l* ^^h'aìY ür àôü *ít"d,' f*N'Ã^\lú,- L,fi'"r; (",- J-q'-- c^ zeíoL- ,+ ,o,t'",':at .U (^^f Q"t 'Qa^' ' $ {rypz}rtf>c3 . >Cz -t- x-3.x2. )( 3 )LZ. i*e*&-g.D(: J íê ;ïâ ïü \' - \.. - "''.....i .rrr É (x) t ftl.q )rr 3 fa,u*ia (a^*tí^I.\.-Ç - -ãrw(dtít€,r7) o t1*t=?3' r )g:.jf-$' * x3;@,ft-3 ,nl&t .ft.16 -"-*--;;; '' \ - ',-r\i. 5õ. ) " ( r.s ztz .1. >fJ ) {xz tüã) . (r,t*fr) ' />'z.=ïi) ".----1izj"\+,"./r' Tz. ,x'J fc;.nc* úì\ rtl*ç.#rtuar I "{&^,.*^ár,, - aç â 4vl*A'rl**...:,{ç,fe.-- Ariün'!*.fiarr* - ( tr< a)tz ü* .v[t]vr,]' I *\{ xi ?{z ). tryu,-.r'. -i r - ,^ a) t-r,\r i ,'.,.--, ' .It*' . -\ (xtriì"C) (t3-JfYJ), /'l t'z*ã) ( x= +íz. tr,Ir) , ( rr= 'xzíe.;-r ) . (nrõ+ rtz+jïò t-(Xi + r,s Ì>f!)r -------r_- 'nlz nz.v4Pfi-. ?3 ÍËOa*q,c- (x:+re?+,fl) '(x*{ fo*r***r'o It'nft,eè,ç1 .(È*effi) q.{- /..-\*-_--. - nis t"tt I o-lT ,tfu>*^,.,aÍ.,.e ',:". .f,,{le.^u".fi ok"!,ç, ,:*, 5&:i,,,r'ttçrr. - J gt-à+--** (4,.^-çt+t (. <., >ci. { (J,rtzirc,) +- .* ! (otxz,r.r) .ï' x,r {:r.a +.ffi Ë) + >ì3 (ra ,.t) )r 3 )óz + )ô3 ,:ïã^:õ + fr fz ÃL*\-*--r \- _lì, "l - *""""-\Í;'f - Çi .f ti--,,r,or-,r) * ü { ú,s,,,=,1ì )c..1, " 2t.3.>cL +.:ïì ,)t3.2cL = >e:.:re-.;.ç,1 ft-evaffi ff ,,rur { oi "tr ü }} \.-r Ìee*)r.3 .:e2 ^ :t 1\,**-_.,^- . -;, A^AÉ .h ),3 >ti,)í.! -.ã1,-z--:ltvl'l * :ca tt,z,ffi\-_--\ _- /\Y1L . lrÌ ? * )r-: >(2.)( jt <r**--1_.-=.-/ ftí7 + >/B.?fZ ){}\**---'*-\.-- 4*t1 4*rqr,- 0r. i.r ',r. i.l 5 )Cl XZ ,1- jã Eo I' ht , {r, *[*r * fJi,"1, d!.81(: gf)cà . r*l {', .k:s' Egj' { ** b=g's;:ü --..;'-"t' I \- ' " "- *"-') t> dvúï^ brLnqa- ,.$er.ffi$d"f#b fxe +re t)Al, [)E ra+ij. t=trn#+:rr]"[r: *r7i*9]\---1,ru .*.----!.-.*--' -1\.--=.-,t --""--*-, ,vl t tvls Mz rã3 p*^*cf^ , t/ À1 l.t ; 2,3, 5 ) 5-) [2,0 pontos] Três Acadêmicos de Oxford. A, B e C, colecionam livros e/ou manuscritos antigos, Íaros, de acordo com preferências pessoais. Mr. A coleciona trabalhos políticos do idioma lnglês e também novelas escritas em outras línguas estrangeiras (que não o Inglês). Mr. B coleciona toda espécie de trabalhos políticos, mas desde que estes não sejam novelas que foram escritas em Inglês. Ele também coleciona trabalhos em lnglês, mas desde que estes trabalhos não sejam novelas (ficções). Mr. C coleciona itens não ficcionais (ele detesta ficções, novelas. preferindo a reaÌidade) e que sejam ainda, ou trabahos escritos no seu idioma nativo (lnglês), ou trabalhos políticos escritos em idiomas estrangeiros (que não o tnglôs). EncontÍe aqueles livros/manuscritos para os quais existe competição entre os Acadêmicos. Em outras paÌavras, deterrnine quais são os Ìivros desejados por dois quaisquer, entre os três Acadêrnicos. Sugere-se montar o modelo do problema em termos de conjuntos adotando as seguintes definições iniciais: A = Conjunto de livros colecionados por Mr. A; B : Conjunto de livros colecionados por Mr. B; C : Coniunto de livros colecionados por Mr. C; Z = Conjunto de livros colecionados (dese.iados) por dois quaisquer, entre os três Acadêmicos. Por meio de operações de união, intersecção e complemento de coniuntos encontre a expressão de Z em função de A, B e C. Escolha e defina outros conjuntos que pemitam modelar os desejos dos colecionadores e determinar a expressão dos conjuntos A, B e C em funçào destes. Sugere-se a adoção de letras mnemônicas - Se o conjunto for de obras Políticas adotar P, etc. Uma vez encontradas as expressões de A. B, C e Z por operadores conjuntistas, encontre as expressões BooÌeanas equivalentes, interpretando os conjuntos como variáveis Booleanas e os operadores união, intersecção e complemento como operadores Booleanos- complemento. Simplìfique a expressão Booleana de Z. justificando cada passo relevante com a técnica usada (De Morgan, propriedade dìstributiva. Axjoma. etc.) e interprete o resuÌtado obtido para Z. resumindo o que há em comum entre os colecionadores. ts- Á - (.,$,.[""',;[." ']u Jü"r";i']' to&,c'r'erc^rl.r+"s lruf 4/r, A rl u1'L.D tv, ú f - r-:1w-,'-G a do&-r-., 61Jli,'cre: t',tsu'I*s 'rs Ìêa'a,'.ar,^ </à " -,?ffk E y #.r.{,Wi#W"f5X Try' ? --4!p'.Á-a* )'odvt +t I^c'buVLc' pc{il'-ttt- 7 - ô*4rl^tro Jl,'.Qí^\'oi ç')srÁono4nz?ry'ao') *úa âr)1Á t= (nns)U(/{na)u (anc) \ì ì, lt lì t, ..^ÁD.ó'r!!w^r/l ^'--^r, T,1 3 Jui i.,,'..'. J* e 1,t lLlr LC. r â. /tí'í^t-íP'nÇar l,t-.14^-L64. A=CPnE) U(r,l nE) o:(pa'@)tJ(en €: tn[Lu(PnEI ),, 5à fr+tnr"le- t o t ctf'xtc7teL\ Ô *) fitL eL: -.r.t ,'; ,--.-1u-^.62 6.ua.tì ^lc"t ai'cU Ça'ft',t, ç 1 7;-ê.ts+ a-e+15.6 Â: ",e O tJ,lI = p.S7S +' É,il )d= N (e oP,ã) (t^-1'u, â: ru5rthru R, í3q' 6 to" ttcTvw'u{) & V, o'rvt"'|l't' 1,,r,r.0 4-, . .rt.,.rúí {'. "ï*" r ^ ì !\rY v -- e, r í. i) + ü. Ãr {Ú, tttot6'"'; - ,/ 1 ï;E= ,! : ? (F+E) + .='Ú : P'il +?'E +€'V P- lì rü''s) B * i,.ú. (g+I) +p.E'+Ë'í; r'F'É+gFF tp'È+Ã'v** É = il.Ê(p+1) + P,ElR+r) ç.- {*"*'(Í;'* ,rf; 141 11 :lB = r.,,r ,Ë + i'. t- [ x_ {r4+lì= zÍ Ce rr'É) vAt pífi,Cua'o )Ì-eLorln'o ' ) ia1(" ç'{ 'ç1 ="i,3 - r>'V) (v-'3\= rr'5 tr: .&l "'lá"-nn- 1i. l \,!g,,'1t". J.^,q 6al c.lNt',v,., ?* . M) r {, -+- t t*"tíJ44*, .ttu, - t jf,u,, v c= N d: l) ,1r-+ P) = F.Ë -t- ãJ.F &^t : -\ rt-.r-* p.e){"'e+ü'f + (ü'u +p'IJ'' 1-'--í?)f -- I {.,;' tu' r- )' l-LN "- r r'ç / I L'- .-- .-r ì )-. ,."''Ï)'(t'rt t''E+í'z) + (ú't>+p'l)'(N E+ N't-) Í : . p,,. * u" . E).1 ;.e " r, F + Ãi. e. { i: tEJ] * :o t1':'),ji : r È' ') y':;tt,{-",',ã).f i'; * ? 7 r ií' P' L+ frí íJ + ti'È+tE)'tí'i+t'e) I z r ?.*+ r-,í). I P ;' ( J + tJ ]* õ' € ( i + P! + r r? Ê t P' [ )' ri' € +Ã7''') 1 -: r ?-r r,r'.Ë) ' (p'ï 'ç fr'ú) *'( ü'8.+ r'i) 'rü'ã tú'P) u =e e* fr'E)' &' 'tì-N'F) * (ü' ettr"rfi z=<!,?.ii)-r"jjl}gÈ *+)ï x .3 )c\r\ ,:+5r ">1 1ê) J >c t- { ã ü,nfr,t2'''Ç"sc^ , *.,r.3 rx.X t{J = [$Ë f v,õ f l3 ,xtX,U f'r,-*-;-fe-"d-+' ç, .,",. u 'f,' ftu c ';; eQ4 iì , tJ x f tt"' /. , c ,t .Y\Z: ap.J trvr':). r í ír,' E) + (e,;+u'E),{ín,È +^r,P) + z = ï,t-+ P' ã' { e'i *a''! +ÃÍ' F) C t fr,Lrí";\
Compartilhar