====== Architektury systemów komputerowych - Lista 1. ====== * {{:ask:09.skrypt01.pdf|Wykład 1}}. * {{:ask:09.lista01.pdf|Lista 1}} ===== Zadanie 1. ===== Niech $+$ i $*$ będą takie, że: | + ^ 0 ^ 1 ^ ^ 0 | 0 | 1 | ^ 1 | 1 | 1 | i | * ^ 0 ^ 1 ^ ^ 0 | 0 | 0 | ^ 1 | 0 | 1 | - $0+1=1=1+0$. \\ $0*1=0=1*0$. - $0+0=0$. \\ $1+0=1$. - $0*1=0$. \\ $1*1=1$. - $0+\overline{0}=0+1=1$. \\ $1+\overline{0}=1$. - $0*\overline{0}=0$. \\ $1*\overline{1}=1*0=0$. - $\overline{\overline{0}}=\overline{1}=0$. \\ $\overline{\overline{1}}=\overline{0}=1$. 7, 8. ^ $x$ ^ $y$ ^ $z$ | $y+z$ ^ $x*(y+z)$ | $x*y$ | $x*z$ ^ $x*y+x*z$ ^ ^ ^ ^ | $y*z$ ^ $x+(y*z)$ | $x+y$ | $x+z$ ^ $(x+y)*(x+z)$ ^ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |||| 0 | 0 | 0 | 0 | 0 | | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | |||| 0 | 0 | 0 | 1 | 0 | | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | |||| 0 | 0 | 1 | 0 | 0 | | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | |||| 1 | 1 | 1 | 1 | 1 | | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |||| 0 | 1 | 1 | 1 | 1 | | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |||| 0 | 1 | 1 | 1 | 1 | | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |||| 0 | 1 | 1 | 1 | 1 | | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |||| 1 | 1 | 1 | 1 | 1 | 9. ^ $x$ ^ $y$ | $xy$ ^ $\overline{xy}$ | $\overline{x}$ | $\overline{y}$ ^ $\overline{x}+\overline{y}$ | | 0 | 0 | 0 | 1 | 1 | 1 | 1 | | 0 | 1 | 0 | 1 | 1 | 0 | 1 | | 1 | 0 | 0 | 1 | 0 | 1 | 1 | | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 10. ^ $x$ ^ $y$ | $x+y$ ^ $\overline{x+y}$ | $\overline{x}$ | $\overline{y}$ ^ $\overline{x}*\overline{y}$ | | 0 | 0 | 0 | 1 | 1 | 1 | 1 | | 0 | 1 | 1 | 0 | 1 | 0 | 0 | | 1 | 0 | 1 | 0 | 0 | 1 | 0 | | 1 | 1 | 1 | 0 | 0 | 0 | 0 | ===== Zadanie 2. ===== Elementem neutralnym dodawania $0$ jest $c$. Poszukajmy $\overline{a}$. Wiemy, że $\overline{a}*a=0$. $\overline{a}$ więc musi być $c$. Tak samo $\overline{b}$. Ale wtedy $\overline{\overline a} = \overline c = b$. Sprzeczność z $a \neq b$. ===== Zadanie 3. ===== b) \\ $x = x + 0 = x + (x * \overline x) = (x + x) \cdot (x + \overline x) = (x+x)*1 = x+x$ \\ $x = x * 1 = x * (x + \overline x) = x * x + x * \overline x = x * x$ a) \\ $0 \cdot x = (x \cdot \overline x) \cdot x = \overline x \cdot x \cdot x = \overline x \cdot x = 0$ \\ $1 + x = (x + \overline x) + x = \overline x + x + x = \overline x + x = 1$ c) \\ $x(x + y) = xx + xy = x + xy$ \\ $x + xy = x \cdot 1 + x \cdot y = x(1 + y) = x \cdot 1 = x$ ===== Zadanie 4. ===== a) $xy + x\overline{y} = x(y+\overline{y})=x*1=x$ b) $(x+y)(x+\overline{y}) = x+y\overline{y}=x+0=x$ ===== Zadanie 5. ===== a) $xz + xy\overline{z} = x(z + y\overline{z})=x( (z+y)(z+\overline{z}) ) = x(z+y)$ b) $\overline{(x+y)}\cdot\overline{(\overline{x}+\overline{y})}=(\overline{x}\cdot\overline{y})\overline{\overline{xy}}=(\overline{x}\overline{y})xy=(\overline{x}x)(\overline{y}y)=0$ c) $x+\overline{x}y+\overline{x}*\overline{y}=x+ \overline{x}(y+\overline{y}) = x+ \overline{x}\cdot1=x +\overline{x} = 1$ d) $(x\overline{y}+\overline{w}z)(w\overline{x}=y\overline{z}) = x\overline{y}w\overline{x} + x\overline{y}y\overline{z} + \overline{w}zw\overline{x} + \overline{w}zy\overline{z} = 0$ ===== Zadanie 6. ===== $F = xy\overline{z}\overline{(\overline{y}z+x)}+(\overline{w}yz+\overline{x}) = xy\overline{z}\overline{\overline{y}z}\overline{x} +(\overline{w}yz+\overline{x}) = 0 +(\overline{w}yz+\overline{x}) = \overline{w}yz+\overline{x}$ $\overline{F} = \overline{\overline{w}yz+\overline{x}} = \overline { \overline w * y * z } * x = (\overline {\overline w * y} + \overline z) * x = (w + \overline y + \overline z) * x = x * w + x * \overline y + x * \overline z$ ===== Zadanie 7. ===== a) Suma = 1 dla (x,y,z) == (1,1,1), (1,0,0), (0,0,0) b) Iloczyn = 1 dla (x,y,z) == (1,1,1), (1,0,1), (0,1,1) ===== Zadanie 8. ===== Kontrprzykład: $x=1, y=1, z=0$. ===== Zadanie 9. ===== $x \oplus y = x*\overline{y} + \overline{x}\cdot{y} = \overline{(\overline{x}+y)} + \overline{(x+\overline{y})}$ ===== Zadanie 10. ===== $F = \overline x \cdot \overline y z + \overline x y \overline z + x \overline y z + x y \overline z $ ===== Zadanie 11. ===== $(y + z)(\overline y + \overline z)$ Dowód konstruktywny: - Każde wyrażenie można zapisac w dysjunkcyjnej postaci normalnej: http://www-users.mat.uni.torun.pl/~zssz/nsi2009/ab.pdf (ostatnia strona) - Z rozdzielności $+$ względem $*$ wydodawajmy składniki wyrażenia w dpn a otrzymamy wyrażenie w kpn. Przykład: $a \in \{x, \overline x, 1\}$ $b \in \{y, \overline y, 1\}$ $c \in \{x, \overline x, 1\}$ $d \in \{y, \overline y, 1\}$ $ab+cd = (a+c)(a+d)(b+c)(b+d)$ ===== Zadanie 12. ===== Robimy se tabelke, wychodzi że jest 5 prawdziwych wartościowań. Zauważamy że jak mamy minterm, to on dodaje maksymalnie 1, 2, 4 lub 8 wartościowań prawdziwych, w zależności od ilości literałów jakie zawiera. 2+2 nie wystarcza aby opisać 5 wartościowań, więc musi być 1 minterm który realizuje 4 wartościowania prawdziwe, czyli jest jednej z postaci $x, y, z, \overline x, \overline y, \overline z$. Brutem sprawdzamy że żadna z nich nie opisuje 4 wartościowań prawdziwych w naszym wyrażeniu, więc nie da się tego wyrażenia opisać za pomocą dwóch mintermów. // By MB__ // ===== Zadanie 13. ===== Dowód jest [[http://books.google.pl/books?id=RM1D3mFw2u0C&pg=PA235&lpg=PA235&dq=representation+theorem+finite+power+set&source=bl&ots=jibpfZHcR3&sig=4-1CLlJs04CYP1XC0_dya6Z3a8Y&hl=en&ei=7jrSSsaxIZnqnAPnmaiEAw&sa=X&oi=book_result&ct=result&resnum=2&ved=0CBIQ6AEwAQ#v=onepage&q=representation%20theorem%20finite%20power%20set&f=false|tutaj]], ale jest długi (kilka lematów jest potrzebnych), więc nie chce mi sie go przepisywać. {{tag>[listy_zadan]}}