Architektury systemów komputerowych - Lista 1.

• Wykład 1.
• Lista 1

Niech + i * będą takie, że:

i

1. 0+1=1=1+0.
   0*1=0=1*0.
2. 0+0=0.
   1+0=1.
3. 0*1=0.
   1*1=1.
4. 0+\overline{0}=0+1=1.
   1+\overline{0}=1.
5. 0*\overline{0}=0.
   1*\overline{1}=1*0=0.
6. \overline{\overline{0}}=\overline{1}=0.
   \overline{\overline{1}}=\overline{0}=1.

7, 8.

9.

10.

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.

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

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

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

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

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)

Kontrprzykład: x=1, y=1, z=0.

x \oplus y = x*\overline{y} + \overline{x}\cdot{y} = \overline{(\overline{x}+y)} + \overline{(x+\overline{y})}

F = \overline x \cdot \overline y z + \overline x y \overline z + x \overline y z + x y \overline z

(y + z)(\overline y + \overline z)

Dowód konstruktywny:

1. Każde wyrażenie można zapisac w dysjunkcyjnej postaci normalnej: http://www-users.mat.uni.torun.pl/~zssz/nsi2009/ab.pdf (ostatnia strona)
2. 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)

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__

Dowód jest tutaj, ale jest długi (kilka lematów jest potrzebnych), więc nie chce mi sie go przepisywać.