Mathematik für INF 4 - Exam

Aufgabe 1)

Betrachten Sie die folgende Boolesche Funktion f(a, b, c, d) = Σ(0, 1, 2, 5, 6, 7, 8, 9, 10, 14). Diese Funktion soll durch Anwendung von Boolescher Algebra und einem Karnaugh-Diagramm minimiert werden, um die Anzahl der benötigten logischen Gatter und Verbindungen zu reduzieren.

a)

Erstelle ein 4-Variablen-Karnaugh-Diagramm (K-Diagramm) für die gegebene Boolesche Funktion.

Lösung:

Erstellung des 4-Variablen-Karnaugh-Diagramms für die gegebene Boolesche Funktion:Ein Karnaugh-Diagramm (K-Diagramm) hilft, logische Ausdrücke zu vereinfachen und so die Anzahl der notwendigen logischen Gatter zu minimieren. Lassen Sie uns die Boolesche Funktion f(a, b, c, d) = Σ(0, 1, 2, 5, 6, 7, 8, 9, 10, 14) in ein 4-Variablen-Karnaugh-Diagramm eintragen.

• Wir identifizieren die Min-Terme, die in der Funktion vorkommen. Die angegebenen Min-Terme sind: \ Σ(0, 1, 2, 5, 6, 7, 8, 9, 10, 14).
• Trage diese Min-Terme in das 4x4-Karnaugh-Diagramm ein, indem wir die korrekte Kombination der Werte für a, b, c und d bestimmen.

Hier ist das 4x4-Karnaugh-Diagramm:

a\b\c\d	00	01	11	10
00	1	1	0	1
01	1	1	1	1
11	0	0	0	1
10	1	1	0	0

Die Zeilen- und Spaltenüberschriften bedeuten: a: 00, 01, 11, 10 c\d: 00, 01, 11, 10 Hier ist die Platzierung der Min-Terme im Diagramm:

• \textbf{0}: a=0, b=0, c=0, d=0 -> (00, 00)
• \textbf{1}: a=0, b=0, c=0, d=1 -> (00, 01)
• \textbf{2}: a=0, b=0, c=1, d=0 -> (00, 10)
• \textbf{5}: a=0, b=1, c=0, d=1 -> (01, 01)
• \textbf{6}: a=0, b=1, c=1, d=0 -> (01, 10)
• \textbf{7}: a=0, b=1, c=1, d=1 -> (01, 11)
• \textbf{8}: a=1, b=0, c=0, d=0 -> (10, 00)
• \textbf{9}: a=1, b=0, c=0, d=1 -> (10, 01)
• \textbf{10}: a=1, b=0, c=1, d=0 -> (10, 10)
• \textbf{14}: a=1, b=1, c=1, d=0 -> (11, 10)

Das ist das resultierende K-Diagramm für die gegebene Boolesche Funktion.

b)

Identifiziere die größten möglichen Blöcke (Potenz von 2) im K-Diagramm. Beschreibe die Blöcke und notiere die entsprechenden vereinfachten Ausdrücke.

Lösung:

Identifikation der größten möglichen Blöcke (Potenz von 2) im K-Diagramm:Um die gegebenen Min-Terme im K-Diagramm zu vereinfachen, suchen wir die größten möglichen Blöcke, die eine Potenz von 2 bilden. Dies hilft uns, die Anzahl der logischen Gatter und Verbindungen zu minimieren.K-Diagramm für f(a, b, c, d) = Σ(0, 1, 2, 5, 6, 7, 8, 9, 10, 14)

a\b\c\d	00	01	11	10
00	1	1	0	1
01	1	1	1	1
11	0	0	0	1
10	1	0	0	1

Identifizierte Blöcke:

• Block 1: 4er BlockMin-Terme: 0, 1, 8, 9Vereinfachter Ausdruck: \(\bar{a} \bar{b}\)
• Block 2: 4er BlockMin-Terme: 2, 6, 10, 14Vereinfachter Ausdruck: \(\bar{c} d\)
• Block 3: 2er BlockMin-Terme: 5, 7Vereinfachter Ausdruck: \(\bar{a} b c\)
• Block 4: 2er BlockMin-Terme: 9, 8Vereinfachter Ausdruck: \(a \bar{d} \bar{c}\)

Zusammenstellung der vereinfachten Ausdrücke:Die vereinfachte Form der Booleschen Funktion wird durch die Summe der Produkte der vereinfachten Ausdrücke repräsentiert:\[ f(a, b, c, d) = \bar{a} \bar{b} + \bar{c} d + \bar{a} b c + a \bar{d} \bar{c} \] Dies sind die größten möglichen Blöcke im K-Diagramm und die entsprechenden vereinfachten Ausdrücke für die gegebene Boolesche Funktion.

c)

Mit den identifizierten Blöcken, schreibe die minimierte Boolesche Funktion in der Form einer Summe von Produkten (SOP).

Lösung:

Minimierte Boolesche Funktion in der Form einer Summe von Produkten (SOP):Basierend auf den identifizierten Blöcken im K-Diagramm, können wir die minimierte Boolesche Funktion schreiben.K-Diagramm für f(a, b, c, d) = Σ(0, 1, 2, 5, 6, 7, 8, 9, 10, 14)

a\b\c\d	00	01	11	10
00	1	1	0	1
01	1	1	1	1
11	0	0	0	1
10	1	0	0	1

Identifizierte Blöcke:Um die Funktion zu vereinfachen, identifizieren wir die größten möglichen Blöcke:

• Block 1: 8er BlockMin-Terme: 0, 1, 2, 5, 6, 7, 8, 9Vereinfachter Ausdruck: \(\bar{a} \bar{d}\)
• Block 2: 4er BlockMin-Terme: 2, 6, 10, 14Vereinfachter Ausdruck: \(\bar{c} d\)
• Block 3: 2er BlockMin-Terme: 8, 9Vereinfachter Ausdruck: \(a \bar{b} \bar{d}\)

Vereinfachte Boolesche Funktion:Die Summe von Produkten (SOP) Form der minimierten Booleschen Funktion ergibt sich aus der Kombination der obigen vereinfachten Ausdrücke:\[ f(a, b, c, d) = \bar{a} \bar{d} + \bar{c} d + a \bar{b} \bar{d} \] Dies ist die minimierte Boolesche Funktion in der Form einer Summe von Produkten (SOP).

Aufgabe 2)

In einer digitalen Schaltung wird ein Flip-Flop als Grundelement zur Speicherung von Zuständen verwendet. Es gibt verschiedene Typen von Flip-Flops, wie SR, D, JK und T, die jeweils spezifische Eigenschaften und Verhalten aufweisen. Ein SR-Flip-Flop hat eine Wahrheitstabelle, die beschreibt, wie sich der Ausgangszustand in Abhängigkeit von den Eingangs-Signalen (Set und Reset) verhält:

• Q' = Q, wenn S=0 und R=0
• Q' = 1, wenn S=1 und R=0
• Q' = 0, wenn S=0 und R=1
• undefiniert, wenn S=1 und R=1

Ein D-Flip-Flop übernimmt direkt die Daten am Eingang D bei einem aktiven Takt, während ein JK-Flip-Flop die Kombination aus SR und T darstellt und den undefinierten Zustand von S=1 und R=1 vermeidet. Ein T-Flip-Flop wechselt den Zustand (toggle), wenn das T-Eingangssignal '1' ist.

a)

Entwirf eine Schaltung mit einem JK-Flip-Flop zur Frequenzteilung einer gegebenen Eingangssignal-Frequenz. Beschreibe den Schaltungsaufbau und erkläre, warum die Frequenz geteilt wird.

Lösung:

Um eine Frequenzteilung eines gegebenen Eingangssignals mithilfe eines JK-Flip-Flops zu realisieren, musst Du den JK-Flip-Flop so konfigurieren, dass er seine Zustände bei jedem Taktwechsel ändert. Hier ist eine Schritt-für-Schritt-Anleitung zur Schaltungsentwurf:

• Verbindung der Eingänge: Verbinde die Eingänge J und K beide mit logischem High (1). Durch diese Verbindung wird der JK-Flip-Flop wie ein T-Flip-Flop arbeiten, da bei jedem Taktimpuls das Ausgangssignal toggelt (den Zustand wechselt).
• Takteingang: Gib das zu teilende Eingangssignal an den Takt-Eingang (CLK) des JK-Flip-Flops.
• Ausgang: Das Ausgangssignal Q des JK-Flip-Flops wird die geteilte Frequenz liefern.

Warum wird die Frequenz geteilt:

Ein JK-Flip-Flop, das als T-Flip-Flop konfiguriert ist, ändert seinen Ausgangszustand bei jedem positiven Taktflankenwechsel. Das bedeutet, dass für jeden kompletten Taktzyklus (von High zu Low zu High) des Eingangssignals der Ausgang des Flip-Flops einmal toggelt. Somit hat das Ausgangssignal Q eine Frequenz, die halb so groß ist wie die des Eingangssignals. In mathematischer Form:

• Eingangsfrequenz: \(f_{in}\)
• Ausgangsfrequenz: \(f_{out} = \frac{f_{in}}{2}\)

b)

Eine digitale Schaltung enthält einen SR-Flip-Flop. Gegeben sei ein Taktsignal, das periodisch zwischen 0 und 1 wechselt. Angenommen, die Eingangssignale S und R sind wie folgt spezifiziert:

• Wenn das Taktsignal '0' ist, dann S=1 & R=0
• Wenn das Taktsignal '1' ist, dann S=0 & R=1

Berechne den Ausgangszustand Q in einem vollständigen Taktzyklus und skizziere den zeitlichen Verlauf des Ausgangssignals Q. Gehe davon aus, dass der initiale Zustand Q=0 ist.

Lösung:

Um den Ausgangszustand Q eines SR-Flip-Flops in einem vollständigen Taktzyklus zu berechnen, folgen wir den vorgegebenen Eingangssignalen und der Wahrheitstabelle für den SR-Flip-Flop. Der initiale Zustand von Q ist 0.

• Initialer Zustand: Q = 0

1. Halbzyklus - Taktsignal = 0:

• S = 1, R = 0
• Gemäß der Wahrheitstabelle: Q' = 1
• Neuer Zustand: Q = 1

2. Halbzyklus - Taktsignal = 1:

• S = 0, R = 1
• Gemäß der Wahrheitstabelle: Q' = 0
• Neuer Zustand: Q = 0

Am Ende des vollständigen Taktzyklus kehrt der Ausgangszustand Q wieder zu 0 zurück, und dieser Zyklus wird kontinuierlich wiederholt. Hier ist eine Skizze des zeitlichen Verlaufs des Ausgangssignals Q:

                   ____      ____      ____Taktsignal:  __|    |____|    |____|                   _____________________S:         ___|                                         |____________________                        ______________________R:         ________________________________________|                                           _______        ______       _______        _______Q:        0           1       0          1      0          1      0

In der Skizze sehen wir, dass Q bei jedem Taktzyklus einmal von 0 auf 1 und zurück zu 0 wechselt.

Aufgabe 3)

Ein endlicher Automat (FSM) ist für die Steuerung eines zweistufigen Parkhaussystems vorgesehen, das folgende Anforderungen erfüllt:

• Im ersten Zustand (S0) ist das Parkhaus leer.
• Im zweiten Zustand (S1) ist das Erdgeschoss voll und das Obergeschoss ist noch leer.
• Im dritten Zustand (S2) ist das Obergeschoss ebenfalls voll.
• Das System reagiert auf zwei Eingaben: 'e' für 'Einfahren eines Fahrzeugs' und 'a' für 'Ausfahren eines Fahrzeugs'.
• Die einzige Ausgabe 'F' zeigt an, dass das Parkhaus voll ist.

a)

a) Zeichne das Zustandsdiagramm für den gegebenen endlichen Automaten. Achte dabei darauf, dass die Zustandsübergänge durch die Eingaben 'e' und 'a' korrekt dargestellt werden. Markiere die Zustände und Übergänge eindeutig.

Lösung:

Lösung:Um das Zustandsdiagramm für den gegebenen endlichen Automaten (FSM) zu zeichnen, müssen wir die Zustände und Übergänge definieren und darstellen. Hier sind die Schritte zu beachten:

• Zustände: Es gibt drei Zustände: S0, S1 und S2.
• Übergänge: Die Übergänge zwischen den Zuständen werden durch die Eingaben 'e' (Einfahren eines Fahrzeugs) und 'a' (Ausfahren eines Fahrzeugs) definiert.
• Ausgabe: Die einzige Ausgabe 'F' zeigt an, dass das Parkhaus voll ist.
• Übergangsregeln:
  • Von S0 nach S1: Bei Eingabe 'e'.
  • Von S1 nach S2: Bei Eingabe 'e'.
  • Von S2 nach S1: Bei Eingabe 'a'.
  • Von S1 nach S0: Bei Eingabe 'a'.

Hier ist das Zustandsdiagramm:Zustandsdiagramm: In diesem Diagramm:

• Der Pfeil von S0 nach S1 wird durch die Eingabe 'e' ausgelöst.
• Der Pfeil von S1 nach S2 wird ebenfalls durch die Eingabe 'e' ausgelöst.
• Der Pfeil von S2 nach S1 wird durch die Eingabe 'a' ausgelöst.
• Der Pfeil von S1 nach S0 wird durch die Eingabe 'a' ausgelöst.

Die Ausgabe 'F' wird in Zustand S2 angezeigt, um anzuzeigen, dass das Parkhaus voll ist.

c)

c) Implementiere den Automaten in Python-Code. Dein Code sollte eine Klasse 'ParkhausAutomat' enthalten, die Methoden für den Zustandsübergang und die Ausgabe implementiert.Ein Beispiel könnte folgendermaßen aussehen:

class ParkhausAutomat: def __init__(self): self.zustand = 'S0' def uebergang(self, eingabe): if self.zustand == 'S0': if eingabe == 'e': self.zustand = 'S1' elif eingabe == 'a': self.zustand = 'S0' elif self.zustand == 'S1': if eingabe == 'e': self.zustand = 'S2' elif eingabe == 'a': self.zustand = 'S0' elif self.zustand == 'S2': if eingabe == 'e': self.zustand = 'S2' elif eingabe == 'a': self.zustand = 'S1' def ausgabe(self): if self.zustand == 'S2': return 'F' return ''

Lösung:

Lösung:Hier ist die Implementierung des endlichen Automaten (FSM) für das zweistufige Parkhaussystem in Python. Die Klasse ParkhausAutomat enthält Methoden für den Zustandsübergang und die Ausgabe.

class ParkhausAutomat:    def __init__(self):        self.zustand = 'S0'    def uebergang(self, eingabe):        if self.zustand == 'S0':            if eingabe == 'e':                self.zustand = 'S1'            elif eingabe == 'a':                self.zustand = 'S0'  # bleibt in S0        elif self.zustand == 'S1':            if eingabe == 'e':                self.zustand = 'S2'            elif eingabe == 'a':                self.zustand = 'S0'        elif self.zustand == 'S2':            if eingabe == 'e':                self.zustand = 'S2'  # bleibt in S2            elif eingabe == 'a':                self.zustand = 'S1'    def ausgabe(self):        if self.zustand == 'S2':            return 'F'        return ''# Beispielverwendungparkhaus = ParkhausAutomat()print(parkhaus.ausgabe())  # Ausgabe: ''parkhaus.uebergang('e')print(parkhaus.ausgabe())  # Ausgabe: ''parkhaus.uebergang('e')print(parkhaus.ausgabe())  # Ausgabe: 'F'parkhaus.uebergang('a')print(parkhaus.ausgabe())  # Ausgabe: ''

• Initialisierung: Der Automat startet im Zustand 'S0'.
• Übergangsfunktion: Die Methode uebergang verändert den Zustand des Automaten basierend auf der Eingabe ('e' oder 'a').- 'S0':
  • Bei Eingabe 'e' wird zu 'S1' gewechselt.
  • Bei Eingabe 'a' bleibt der Automat in 'S0'.
  - 'S1':
  • Bei Eingabe 'e' wird zu 'S2' gewechselt.
  • Bei Eingabe 'a' wird zu 'S0' gewechselt.
  - 'S2':
  • Bei Eingabe 'e' bleibt der Automat in 'S2'.
  • Bei Eingabe 'a' wird zu 'S1' gewechselt.
• Ausgabefunktion: Die Methode ausgabe gibt 'F' zurück, wenn der Zustand 'S2' erreicht ist (dies zeigt an, dass das Parkhaus voll ist). Andernfalls wird eine leere Zeichenkette zurückgegeben.

In diesem Beispiel kann die Verwendung der Klasse ParkhausAutomat einfache Zustandsänderungen und Ausgaben basierend auf diesen Zuständen demonstrieren.

Aufgabe 4)

Gegeben sind die Funktionen und die formalen Ausdrücke der numerischen Integrationsverfahren: Trapezregel und Simpsonregel. Die wichtigsten Formeln lauten:

• Trapezregel: \(\frac{b-a}{2} [ f(a) + f(b) ]\)
• Verfeinerte Trapezregel: \(\frac{b-a}{2n} [ f(x_0) + 2 \sum_{i=1}^{n-1} f(x_i) + f(x_n) ]\)
• Simpsonregel: \(\frac{b-a}{6} [ f(a) + 4f ( \frac{a+b}{2} ) + f(b) ]\)
• Verfeinerte Simpsonregel: \(\frac{b-a}{6n} \Bigg[ f(x_0) + 4 \sum_{i=1,3,...}^{n-1} f(x_i) + 2 \sum_{i=2,4,...}^{n-2} f(x_i) + f(x_n) \Bigg]\)
• Beide Methoden teilen das Integrationsintervall in kleinere Abschnitte, um die Genauigkeit zu erhöhen.

a)

a) Berechne das Integral der Funktion \(f(x) = x^2\) im Intervall \[0, 2\]\ mit der einfachen Trapezregel.

Lösung:

Um das Integral der Funktion \(f(x) = x^2\) im Intervall \([0, 2]\) mit der einfachen Trapezregel zu berechnen, verwenden wir die folgende Formel:

• Trapezregel: \(\frac{b-a}{2} [ f(a) + f(b) ]\)

Schritt für Schritt:

1. Grenzen des Integrals:

• a = 0
• b = 2

2. Funktionswerte an den Grenzen:

• f(a) = f(0) = 0^2 = 0
• f(b) = f(2) = 2^2 = 4

3. Einsetzen in die Formel der Trapezregel:

• \(\frac{b-a}{2} [ f(a) + f(b) ]\)
• \(\frac{2-0}{2} [ f(0) + f(2) ]\)
• \(1 \times [0 + 4]\)
• \(1 \times 4 = 4\)

Das Integral der Funktion \(f(x) = x^2\) im Intervall \([0, 2]\) mit der einfachen Trapezregel ergibt 4.

b)

b) Verwende die verfeinerte Trapezregel mit \(n = 4\)\ zum Berechnen des Integrals der Funktion \(f(x) = x^2\) im Intervall \[0, 2\].

Lösung:

Um das Integral der Funktion \(f(x) = x^2\) im Intervall \([0, 2]\) mit der verfeinerten Trapezregel und \(n = 4\) zu berechnen, verwenden wir die folgende Formel:

• Verfeinerte Trapezregel: \(\frac{b-a}{2n} \left[ f(x_0) + 2 \sum_{i=1}^{n-1} f(x_i) + f(x_n) \right]\)

Schritt für Schritt:

1. Grenzen des Integrals:

• a = 0
• b = 2

2. Anzahl der Unterintervalle:

• n = 4

3. Berechnung der Unterintervallbreite:

• \(h = \frac{b-a}{n} = \frac{2-0}{4} = 0.5\)

4. Funktionswerte an den Unterintervallpunkten:

• \(x_0 = 0\)
• \(x_1 = 0.5\)
• \(x_2 = 1\)
• \(x_3 = 1.5\)
• \(x_4 = 2\)
• \(f(x_0) = (0)^2 = 0\)
• \(f(x_1) = (0.5)^2 = 0.25\)
• \(f(x_2) = (1)^2 = 1\)
• \(f(x_3) = (1.5)^2 = 2.25\)
• \(f(x_4) = (2)^2 = 4\)

5. Einsetzen in die Formel der verfeinerten Trapezregel:

• \(\frac{b-a}{2n} \left[ f(x_0) + 2 \sum_{i=1}^{n-1} f(x_i) + f(x_n) \right]\)
• \(\frac{2-0}{2 \times 4} \left[ f(0) + 2 \left( f(0.5) + f(1) + f(1.5) \right) + f(2) \right]\)
• \(\frac{2}{8} \left[ 0 + 2 \left( 0.25 + 1 + 2.25 \right) + 4 \right]\)
• \(\frac{1}{4} \left[ 0 + 2 \times 3.5 + 4 \right]\)
• \(\frac{1}{4} \left[ 0 + 7 + 4 \right]\)
• \(\frac{1}{4} \left[ 11 \right] = 2.75\)

Das Integral der Funktion \(f(x) = x^2\) im Intervall \([0, 2]\) mit der verfeinerten Trapezregel und \(n = 4\) ergibt 2.75.