DNF vereinfachen < Technische Inform. < Praktische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Implementieren sie die Funktion. Stellen sie eine Funktionstafel auf und entwerfen sie ein Schaltnetz verwendend AND und/oder OR Gattern nur mit max. fan-in=2. Versuchen sie die Anzahl der Gatter zu minimieren. |
Hallo
Da ich ein einem Punkt nicht mehr weiterkomme, hoffe ich, dass ihr mir weiterhelfen könnt, sodass ich den folgenden Schritt verstehe.
Durch die Funktionstafel, die ich erstellt habe, bekomme ich folgende DNF:
f(x1, x2, x3, x4)= m1+m2+m3+m5+m11+m12+15
= [mm] \neg [/mm] x1 * [mm] \neg [/mm] x2 * [mm] \neg [/mm] x3 * [mm] \neg [/mm] x4
+ [mm] \neg [/mm] x1 * [mm] \neg [/mm] x2 * x3 * [mm] \neg [/mm] x4
+ [mm] \neg [/mm] x1 * [mm] \neg [/mm] x2 * x3 * x4
+ [mm] \neg [/mm] x1 * x2 * [mm] \neg [/mm] x3 * [mm] \neg [/mm] x4
+ x1 * [mm] \neg [/mm] x2 * x3 * [mm] \neg [/mm] x4
+ x1 * [mm] \neg [/mm] x2 * x3 * x4
+ x1 * x2 * x3 * [mm] \neg [/mm] x4
Meine Frage ist jetzt:
Könnt ihr mir zeigen mit welchen boolischen Gesetzen ich diese DNF vereinfache?( Bitte mir zeigen wie ihr zu dem Ergebnis kommt um dann ein AND/- OR Schaltnetz aufbauen zu können, damit ich das nachvollziehen und verstehen kann).
Ich brauche eine schnelle Antwort und bin jedem dankbar, der mir eine Lösung gibt.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Danke
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:45 So 06.11.2011 | | Autor: | barsch |
Hallo und herzlich willkommen im Matheraum,
> Implementieren sie die Funktion. Stellen sie eine
> Funktionstafel auf und entwerfen sie ein Schaltnetz
> verwendend AND und/oder OR Gattern nur mit max. fan-in=2.
> Versuchen sie die Anzahl der Gatter zu minimieren.
> Hallo
> Da ich ein einem Punkt nicht mehr weiterkomme, hoffe ich,
> dass ihr mir weiterhelfen könnt, sodass ich den folgenden
> Schritt verstehe.
> Durch die Funktionstafel, die ich erstellt habe, bekomme
> ich folgende DNF:
> f(x1, x2, x3, x4)= m1+m2+m3+m5+m11+m12+15
> = [mm]\neg[/mm] x1 * [mm]\neg[/mm] x2 * [mm]\neg[/mm] x3 * [mm]\neg[/mm] x4
> + [mm]\neg[/mm] x1 * [mm]\neg[/mm] x2 * x3 * [mm]\neg[/mm] x4
> + [mm]\neg[/mm] x1 * [mm]\neg[/mm] x2 * x3 * x4
> + [mm]\neg[/mm] x1 * x2 * [mm]\neg[/mm] x3 * [mm]\neg[/mm] x4
> + x1 * [mm]\neg[/mm] x2 * x3 * [mm]\neg[/mm] x4
> + x1 * [mm]\neg[/mm] x2 * x3 * x4
> + x1 * x2 * x3 * [mm]\neg[/mm] x4
>
> Meine Frage ist jetzt:
> Könnt ihr mir zeigen mit welchen boolischen Gesetzen ich
> diese DNF vereinfache?( Bitte mir zeigen wie ihr zu dem
> Ergebnis kommt um dann ein AND/- OR Schaltnetz aufbauen zu
> können, damit ich das nachvollziehen und verstehen kann).
ich nehme an, KV-Diagramm ist dir noch kein Begriff!? Dann musst du die Regeln hinzuziehen, die du kennst.
Trick: Suche Minterme, die sich in genau einer Variablenbelegung unterscheiden.
Betrachte z.B. die ersten beiden Minterme:
[mm]m_1[/mm] und [mm]m_2[/mm]: [mm]x_1'x_2'x_3'x_4'+x_1'x_2'x_3x_4'[/mm]
Die beiden Minterme unterscheiden sich genau in einer Variablenbelegung, nämlich [mm]x_3[/mm] - einmal negativ belegt ([mm]m_1[/mm]) und einmal positiv belegt ([mm]m_2[/mm])
Dann ist
[mm]x_1'x_2'x_3'x_4'+x_1'x_2'x_3x_4'[/mm]
[mm]= x_1'x_2'x_4'(x_3'+x_3)[/mm] (Welche Regel ist das?)
[mm]= x_1'x_2'x_4'1[/mm] (Welche Regel wurde hier angewendet?)
[mm]=x_1'x_2'x_4'[/mm]
Die beiden Regeln, die hier beispielhaft verwendet wurden, kannst du weiter auf die Minterme anwenden bis die DNF minimiert ist.
Die DNF besteht ja nur aus AND/OR-Gattern, sodass du dahingehend nichts weiter machen musst.
> Ich brauche eine schnelle Antwort und bin jedem dankbar,
> der mir eine Lösung gibt.
Dann setze dich gleich dran und poste deinen weiteren Lösungsweg. Tipp: Ich finde es einfacher anstelle von [mm]\neg{x}[/mm] die Schreibweise x' zu nutzen.
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
> Danke
Gruß
barsch
|
|
|
| |
|
Die Formel die du angewandt hast ist das Distributivgesetz oder?
Auf die ganzen Minterme angewandt erhalte ich dann:
x3 * [mm] \overline{x2}' [/mm] * [mm] \overline{x4}' [/mm] richtig?
Und daraus kann ich dann meine Schaltung bauen?
|
|
|
| |
|
Hallo Bund_weicher_Birnen,
> Die Formel die du angewandt hast ist das Distributivgesetz
> oder?
Im ersten Schritt, ja!
>
> Auf die ganzen Minterme angewandt erhalte ich dann:
>
> x3 * [mm]\overline{x2}'[/mm] * [mm]\overline{x4}'[/mm] richtig?
Was ist das für eine Schreibweise? Barsch hat für die Negation x' benutzt, du benutzt das übliche [mm]\bar{x}[/mm] und dazu noch ' ??
Ich habe mal Quine-McClusky auf deine Funktion losgelassen und erhalte als Primimplikantenmenge:
[mm]P=\{\bar{x}_1\bar x_2\bar x_4, \ \bar x_1\bar x_3\bar x_4, \ x_1x_3\bar x_4, \ \bar x_2x_3\}[/mm]
Das lässt sich dann noch verkürzen zu [mm]y_{\text{min}}=\bar{x}_1\bar x_3\bar x_4 \ + \ x_1x_3\bar x_4 \ + \ \bar x_2x_3\[/mm]
>
> Und daraus kann ich dann meine Schaltung bauen?
Schaue erstmal, ob du auch auf die minimierte Funktion kommst.
Was den Schaltplan angeht, so hast du 4 Eingänge [mm]x_1,x_2,x_3,x_4[/mm], an die du jeweils eine 1 anlegst. Dann musst du stückweise die Kernimplikanten realisieren und dabei beachten, dass du max. 2 Eingänge für ein Gatter hast.
Um etwa den ersten Teil, also [mm]\bar{x}_1\bar x_3\bar x_4[/mm] schalttechnisch zu realisieren, negiere zunächst die Stränge von [mm]x_1,x_3[/mm] kommend und führe sie in ein UND-Gatter, heraus kommt [mm]\bar x_1\bar x_3[/mm].
Dann lasse diesen "Ergebnisstrang" mit dem negierten Strang von [mm]x_4[/mm] in ein weiteres UND-Gatter laufen, dann hast du den ersten Kernimplikanten realisiert.
Gruß
schachuzipus
|
|
|
| |
|
Es sollte eigendlich x3 * [mm] \neg [/mm] x2 * [mm] \neg [/mm] x4 heißen.
Aber selbst mit deiner Variante komme ich irgendwie nicht auf dein Ergebnis. Ich darf nur die Rechengesetze von der boolischen Algebra verwenden und keine anderen Verfahren, da diese noch nicht vorgestellt wurden.
Es wäre gut, wenn mir jemand von meinem Eröffnungspost die DNF mit den Gesetzen so bearbeitet, dass ich das verstehe.
Ich werde es weiterversuchen und mich auch mal mit der Schaltung probieren.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:39 Sa 12.11.2011 | | Autor: | barsch |
Hallo,
dann lass' uns den ersten Schritt einmal gemeinsam durchgehen.
> f(x1, x2, x3, x4)= m1+m2+m3+m5+m11+m12+m15
> = [mm]\neg[/mm] x1 * [mm]\neg[/mm] x2 * [mm]\neg[/mm] x3 * [mm]\neg[/mm] x4
> + [mm]\neg[/mm] x1 * [mm]\neg[/mm] x2 * x3 * [mm]\neg[/mm] x4
> + [mm]\neg[/mm] x1 * [mm]\neg[/mm] x2 * x3 * x4
> + [mm]\neg[/mm] x1 * x2 * [mm]\neg[/mm] x3 * [mm]\neg[/mm] x4
> + x1 * [mm]\neg[/mm] x2 * x3 * [mm]\neg[/mm] x4
> + x1 * [mm]\neg[/mm] x2 * x3 * x4
> + x1 * x2 * x3 * [mm]\neg[/mm] x4
Suche alle Minterme, die sich in genau einer Variablenbelegung unterscheiden.
m1 und m2
m1 und m5
m2 und m3
m2 und m11
m3 und m12
m11 und m12
m11 und m15
Und nun kannst du m1 und m2 zusammenfassen:
[mm]m_1+m_2=x_1'*x_2'*x_3'*x_4'+x_1'*x_2'*x_3*x_4'=x_1'*x_2'*x_4'*(x_3'+x_3)=x_1'*x_2'*x_3'[/mm]
Das machst du für die anderen oben genannten Kombinationen genauso.
Dies wendest du dann weiter auf die nun kleineren Minterme an, solange bis keine Vereinfachung mehr möglich ist.
Vorrechnen ist bei der Aufgabe sehr, sehr aufwendig. Versuche du einmal mit dem Tipp soweit wie möglich zu kommen. Wenn du an einer Stelle hängst, frage erneut nach. Viel Erfolg.
Gruß
barsch
|
|
|
|
