Benutzer:Dirk Huenniger/hagen/cs1/ea1

Lösung zum Kurs 1608 Computersysteme 1 SS09.

Aufgabe 1

Fall 1

Sei $\#Tr(f)<=2^{n-1}$, dann ist die Anzahl der Minterme in der kanonischen disjunktiven Normalenform kleiner gleich

$2^{n-1}$

die Kosten pro Minterm sind höchstens ($n$ mal Negation und $n-1$ mal UND):

$n+n-1=2n-1$

die Kosten für die Veroderung des Minterme sind höchstens (eins weniger als es Minterme gibt):

$2^{n-1}-1$

die Gesamtkosten sind daher höchstens $(2n-1)*2^{n-1}+2^{n-1}-1=n*2^{n}-1<n*2^{n}$ Damit ist dieser Fall erledigt.

Fall 2

Sei $\#Tr(f)>=2^{n-1}$ dann ist die Anzahl der Maxterme in der kanonischen konjuktiven Normalenform kleiner gleich

$2^{n-1}$

die Kosten pro Maxterm sind höchstens

$n+n-1=2n-1$

die Kosten für die Verundung des Maxterme sind höchstens

$2^{n-1}-1$

die Gesamtkosten sind daher höchstens

$(2n-1)*2^{n-1}+2^{n-1}-1=n*2^{n}-1<n*2^{n}$ damit ist dieser Fall erledigt. damit ist die Aussage bewiesen. Die Kosten des Verfahrens trägt der Kläger und die Kosten der Beleuchtung der Mieter.

Aufgabe 2

	0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
${\overline {X_{0}}}\cdot {\overline {X_{2}}}$	1	1	0	0	1	1	0	0	0	0	0	0	0	0	0	0
${\overline {X_{0}}}\cdot X_{1}\cdot X_{2}$	0	0	0	0	0	0	1	1	0	0	0	0	0	0	0	0
$X_{0}\cdot X_{2}\cdot {\overline {X_{3}}}$	0	0	0	0	0	0	0	0	0	0	1	0	0	0	1	0
$X_{1}\cdot {\overline {X_{2}}}$	0	0	0	0	1	1	0	0	0	0	0	0	1	1	0	0
$X_{1}\cdot {\overline {X_{3}}}$	0	0	0	0	1	0	1	0	0	0	0	0	1	0	1	0
${\overline {X_{2}}}\cdot X_{3}$	0	1	0	0	0	1	0	0	0	1	0	0	0	1	0	0

Kicke alles raus was nicht zu $Tr(f)$ gehört.

	0000	0001	0100	0101	0110	0111	1001	1010	1100	1101	1110
${\overline {X_{0}}}\cdot {\overline {X_{2}}}$	1	1	1	1	0	0	0	0	0	0	0
${\overline {X_{0}}}\cdot X_{1}\cdot X_{2}$	0	0	0	0	1	1	0	0	0	0	0
$X_{0}\cdot X_{2}\cdot {\overline {X_{3}}}$	0	0	0	0	0	0	0	1	0	0	1
$X_{1}\cdot {\overline {X_{2}}}$	0	0	1	1	0	0	0	0	1	1	0
$X_{1}\cdot {\overline {X_{3}}}$	0	0	1	0	1	0	0	0	1	0	1
${\overline {X_{2}}}\cdot X_{3}$	0	1	0	1	0	0	1	0	0	1	0

${\overline {X_{0}}}\cdot {\overline {X_{2}}}$ ist wesendlich.

	0110	0111	1001	1010	1100	1101	1110
${\overline {X_{0}}}\cdot X_{1}\cdot X_{2}$	1	1	0	0	0	0	0
$X_{0}\cdot X_{2}\cdot {\overline {X_{3}}}$	0	0	0	1	0	0	1
$X_{1}\cdot {\overline {X_{2}}}$	0	0	0	0	1	1	0
$X_{1}\cdot {\overline {X_{3}}}$	1	0	0	0	1	0	1
${\overline {X_{2}}}\cdot X_{3}$	0	0	1	0	0	1	0

${\overline {X_{0}}}\cdot X_{1}\cdot X_{2}$ ist wesendlich

	1001	1010	1100	1101	1110
$X_{0}\cdot X_{2}\cdot {\overline {X_{3}}}$	0	1	0	0	1
$X_{1}\cdot {\overline {X_{2}}}$	0	0	1	1	0
$X_{1}\cdot {\overline {X_{3}}}$	0	0	1	0	1
${\overline {X_{2}}}\cdot X_{3}$	1	0	0	1	0

${\overline {X_{2}}}\cdot X_{3}$ ist wesendlich

	1010	1100	1110
$X_{0}\cdot X_{2}\cdot {\overline {X_{3}}}$	1	0	1
$X_{1}\cdot {\overline {X_{2}}}$	0	1	0
$X_{1}\cdot {\overline {X_{3}}}$	0	1	1

$X_{0}\cdot X_{2}\cdot {\overline {X_{3}}}$ ist wesendlich

	1100
$X_{1}\cdot {\overline {X_{2}}}$	1
$X_{1}\cdot {\overline {X_{3}}}$	1

Wir können einen der Verbleibenden Terme auswählen.

Ein Minimalpolynom lautet:

$X_{1}\cdot {\overline {X_{3}}}\vee X_{0}\cdot X_{2}\cdot {\overline {X_{3}}}\vee {\overline {X_{2}}}\cdot X_{3}\vee {\overline {X_{0}}}\cdot X_{1}\cdot X_{2}\vee {\overline {X_{0}}}\cdot {\overline {X_{2}}}$

Aufgabe 3

Teil A

Sei f eine n stellige Schaltfunktion dann gibt es einen Boolschen Ausdruck e mit Operatoren aus $O_{1}$ so dass gilt:

$f=f_{e}$

Jetzt nehmen wir uns den ersten Operator aus e und ersetzen ihn durch seinen entsprechenden Ausdruck in $O_{2}$. Dann nehmen wir den nächsten und sofort. Da e nur endlich viele Operatoren aus $O_{1}$ enthält haben wir irgendwann einen Ausdruck gewonnen der nur noch Operatoren aus $O_{2}$ enthällt, diesen nennen wir z. Da sich die vom Ausdruck beschriebene Schaltfunktion jedoch in keinem der Schritte geändert berechnen e und z die gleiche Schaltfunktion. Es gilt also.

$f=f_{z}$

f beliebig war ist $O_{2}$ vollständig.

Teil B

Beginnen wir mit NOT. Es ist $1NANDX={\tilde {X}}$ denn die Wahrheitstafel ist:

$X_{1}$	$1{\text{ }}{\overset {\text{ }}{\text{NAND}}}{\text{ }}X=\sim X$
1	$1{\text{ }}{\overset {\text{ }}{\text{NAND}}}{\text{ }}1=0$
0	$1{\text{ }}{\overset {\text{ }}{\text{NAND}}}{\text{ }}0=1$

Weiterhin ist:

$X_{1}\wedge X_{2}=\sim (X_{1}{\text{ }}{\text{NAND}}{\text{ }}X_{2})$

Damit ist auch AND ausgedrückt. Es bleibt OR. Das geht mit

$X_{1}\vee X_{2}=\sim (X_{1}{\text{ }}{\overset {\text{ }}{\text{NAND}}}{\text{ }}X_{2})\wedge ({\overline {X_{1}}}{\text{ }}{\overset {\text{ }}{\text{NAND}}}{\text{ }}{\overline {X_{2}}}))$

Aufgabe 4

    0123
 0  0000 1
 1  0001 0
 2  0010 1
 3  0011 1
 4  0100 0
 5  0101 1
 6  0110 1
 7  0111 1
 8  1000 1
 9  1001 1
10  1010 X
11  1011 X
12  1100 X
13  1101 X
14  1110 X
15  1111 X

KV-Diagram

	${\overline {X_{2}}}\cdot {\overline {X_{3}}}$	$X_{2}\cdot {\overline {X_{3}}}$	$X_{2}\cdot X_{3}$	${\overline {X_{2}}}\cdot X_{3}$
${\overline {X_{0}}}\cdot {\overline {X_{1}}}$	1	1	1	0
$X_{0}\cdot {\overline {X_{1}}}$	1	X	X	1
$X_{0}\cdot X_{1}$	X	X	X	X
${\overline {X_{0}}}\cdot X_{1}$	0	1	1	1

Primimplikaten

$X_{0};X_{2};{\overline {X_{1}}}\cdot {\overline {X_{3}}};X_{1}\cdot X_{3}$

Aufgabe 5

$g={\overline {f}}={\overline {X_{1}\cdot X_{2}\vee {\overline {X_{2}}}\cdot X_{3}\vee {\overline {X_{1}}}\cdot X_{3}}}={\overline {X_{1}\cdot X_{2}}}\cdot {\overline {{\overline {X_{2}}}\cdot X_{3}}}\cdot {\overline {{\overline {X_{1}}}\cdot X_{3}}}=({\overline {X_{1}}}\vee {\overline {X_{2}}})\cdot (X_{2}\vee {\overline {X_{3}}})\cdot (X_{1}\vee {\overline {X_{3}}})$

GFDL

Die Lizenz die nun folgt ist eigentlich für einen Übungszettel nicht notwendig. Wahrscheinlich ist dieser wegen der zu gerigen Schöpfungshöhe sowiso nicht schützenswert. Dennoch wird sie automatisch angehängt und kann von mir nicht wirklich abgeschaltet werden. Hiermit seinen Kursbetreuer und Korrekturkräfte berechtigt in einer ihrem Amt angemessenen Weise mit diesem Übungszettel zu verfahren.