Technische Informatik
Minimierung mit Quine-McCluskey
Thorsten Thormählen
22. November 2022
Teil 5, Kapitel 3
Thorsten Thormählen
22. November 2022
Teil 5, Kapitel 3
Dies ist die Druck-Ansicht.
Weiterschalten der Folien durch die → Taste oder
durch das Klicken auf den rechten Folienrand.
Das Weiterschalten der Folien kann ebenfalls durch das Klicken auf den rechten bzw. linken Folienrand erfolgen.
Typ | Schriftart | Beispiele |
---|---|---|
Variablen (Skalare) | kursiv | $a, b, x, y$ |
Funktionen | aufrecht | $\mathrm{f}, \mathrm{g}(x), \mathrm{max}(x)$ |
Vektoren | fett, Elemente zeilenweise | $\mathbf{a}, \mathbf{b}= \begin{pmatrix}x\\y\end{pmatrix} = (x, y)^\top,$ $\mathbf{B}=(x, y, z)^\top$ |
Matrizen | Schreibmaschine | $\mathtt{A}, \mathtt{B}= \begin{bmatrix}a & b\\c & d\end{bmatrix}$ |
Mengen | kalligrafisch | $\mathcal{A}, B=\{a, b\}, b \in \mathcal{B}$ |
Zahlenbereiche, Koordinatenräume | doppelt gestrichen | $\mathbb{N}, \mathbb{Z}, \mathbb{R}^2, \mathbb{R}^3$ |
x3 | x2 | x1 | x0 | y | |
---|---|---|---|---|---|
0: | 0 | 0 | 0 | 0 | 1 |
1: | 0 | 0 | 0 | 1 | 0 |
2: | 0 | 0 | 1 | 0 | 0 |
3: | 0 | 0 | 1 | 1 | 0 |
4: | 0 | 1 | 0 | 0 | 1 |
5: | 0 | 1 | 0 | 1 | 0 |
6: | 0 | 1 | 1 | 0 | 1 |
7: | 0 | 1 | 1 | 1 | 0 |
8: | 1 | 0 | 0 | 0 | 0 |
9: | 1 | 0 | 0 | 1 | 0 |
10: | 1 | 0 | 1 | 0 | 0 |
11: | 1 | 0 | 1 | 1 | 1 |
12: | 1 | 1 | 0 | 0 | 1 |
13: | 1 | 1 | 0 | 1 | 1 |
14: | 1 | 1 | 1 | 0 | 1 |
15: | 1 | 1 | 1 | 1 | 0 |
Wahrheitstafel:
x3 | x2 | x1 | x0 | y | |
---|---|---|---|---|---|
0: | 0 | 0 | 0 | 0 | 1 |
1: | 0 | 0 | 0 | 1 | 0 |
2: | 0 | 0 | 1 | 0 | 0 |
3: | 0 | 0 | 1 | 1 | 0 |
4: | 0 | 1 | 0 | 0 | 1 |
5: | 0 | 1 | 0 | 1 | 0 |
6: | 0 | 1 | 1 | 0 | 1 |
7: | 0 | 1 | 1 | 1 | 0 |
8: | 1 | 0 | 0 | 0 | 0 |
9: | 1 | 0 | 0 | 1 | 0 |
10: | 1 | 0 | 1 | 0 | 0 |
11: | 1 | 0 | 1 | 1 | 1 |
12: | 1 | 1 | 0 | 0 | 1 |
13: | 1 | 1 | 0 | 1 | 1 |
14: | 1 | 1 | 1 | 0 | 1 |
15: | 1 | 1 | 1 | 1 | 0 |
Implikanten (Ordnung 0):
x3 | x2 | x1 | x0 | ||
---|---|---|---|---|---|
0: | 0 | 0 | 0 | 0 | → |
4: | 0 | 1 | 0 | 0 | → |
6: | 0 | 1 | 1 | 0 | → |
11: | 1 | 0 | 1 | 1 | ✓ |
12: | 1 | 1 | 0 | 0 | → |
13: | 1 | 1 | 0 | 1 | → |
14: | 1 | 1 | 1 | 0 | → |
Implikanten (Ordnung 0):
x3 | x2 | x1 | x0 | ||
---|---|---|---|---|---|
0: | 0 | 0 | 0 | 0 | → |
4: | 0 | 1 | 0 | 0 | → |
6: | 0 | 1 | 1 | 0 | → |
11: | 1 | 0 | 1 | 1 | ✓ |
12: | 1 | 1 | 0 | 0 | → |
13: | 1 | 1 | 0 | 1 | → |
14: | 1 | 1 | 1 | 0 | → |
Implikanten (Ordnung 1):
x3 | x2 | x1 | x0 | ||
---|---|---|---|---|---|
0, 4: | 0 | - | 0 | 0 | ✓ |
4, 6: | 0 | 1 | - | 0 | → |
4, 12: | - | 1 | 0 | 0 | → |
6, 14: | - | 1 | 1 | 0 | → |
12, 13: | 1 | 1 | 0 | - | ✓ |
12, 14: | 1 | 1 | - | 0 | → |
Implikanten (Ordnung 2):
x3 | x2 | x1 | x0 | ||
---|---|---|---|---|---|
4, 6, 12, 14: | - | 1 | - | 0 | ✓ |
Implikanten (Ordnung 0):
x3 | x2 | x1 | x0 | ||
---|---|---|---|---|---|
0: | 0 | 0 | 0 | 0 | → |
4: | 0 | 1 | 0 | 0 | → |
6: | 0 | 1 | 1 | 0 | → |
11: | 1 | 0 | 1 | 1 | ✓ |
12: | 1 | 1 | 0 | 0 | → |
13: | 1 | 1 | 0 | 1 | → |
14: | 1 | 1 | 1 | 0 | → |
Implikanten (Ordnung 1):
x3 | x2 | x1 | x0 | ||
---|---|---|---|---|---|
0, 4: | 0 | - | 0 | 0 | ✓ |
4, 6: | 0 | 1 | - | 0 | → |
4, 12: | - | 1 | 0 | 0 | → |
6, 14: | - | 1 | 1 | 0 | → |
12, 13: | 1 | 1 | 0 | - | ✓ |
12, 14: | 1 | 1 | - | 0 | → |
Implikanten (Ordnung 2):
x3 | x2 | x1 | x0 | ||
---|---|---|---|---|---|
4, 6, 12, 14: | - | 1 | - | 0 | ✓ |
Primimplikantentafel:
x3 | x2 | x1 | x0 | 0 | 4 | 6 | 11 | 12 | 13 | 14 | ||
---|---|---|---|---|---|---|---|---|---|---|---|---|
4, 6, 12, 14: | - | 1 | - | 0 | ○ | ● | ○ | ● | (x2x̄0) | |||
0, 4: | 0 | - | 0 | 0 | ● | ○ | (x̄3x̄1x̄0) | |||||
12, 13: | 1 | 1 | 0 | - | ○ | ● | (x3x2x̄1) | |||||
11: | 1 | 0 | 1 | 1 | ● | (x3x̄2x1x0) |
Extrahierte essentielle Primimplikanten: (x̄3x̄1x̄0), (x2x̄0), (x3x̄2x1x0), (x3x2x̄1)
Wahrheitstafel:
x3 | x2 | x1 | x0 | y | |
---|---|---|---|---|---|
0: | 0 | 0 | 0 | 0 | 1 |
1: | 0 | 0 | 0 | 1 | 0 |
2: | 0 | 0 | 1 | 0 | 1 |
3: | 0 | 0 | 1 | 1 | 1 |
4: | 0 | 1 | 0 | 0 | 0 |
5: | 0 | 1 | 0 | 1 | 0 |
6: | 0 | 1 | 1 | 0 | 0 |
7: | 0 | 1 | 1 | 1 | 1 |
8: | 1 | 0 | 0 | 0 | 1 |
9: | 1 | 0 | 0 | 1 | 1 |
10: | 1 | 0 | 1 | 0 | 0 |
11: | 1 | 0 | 1 | 1 | 0 |
12: | 1 | 1 | 0 | 0 | 1 |
13: | 1 | 1 | 0 | 1 | 0 |
14: | 1 | 1 | 1 | 0 | 1 |
15: | 1 | 1 | 1 | 1 | 1 |
Implikanten (Ordnung 0):
x3 | x2 | x1 | x0 | ||
---|---|---|---|---|---|
0: | 0 | 0 | 0 | 0 | → |
2: | 0 | 0 | 1 | 0 | → |
3: | 0 | 0 | 1 | 1 | → |
7: | 0 | 1 | 1 | 1 | → |
8: | 1 | 0 | 0 | 0 | → |
9: | 1 | 0 | 0 | 1 | → |
12: | 1 | 1 | 0 | 0 | → |
14: | 1 | 1 | 1 | 0 | → |
15: | 1 | 1 | 1 | 1 | → |
Implikanten (Ordnung 1):
x3 | x2 | x1 | x0 | ||
---|---|---|---|---|---|
0, 2: | 0 | 0 | - | 0 | ✓ |
0, 8: | - | 0 | 0 | 0 | ✓ |
2, 3: | 0 | 0 | 1 | - | ✓ |
3, 7: | 0 | - | 1 | 1 | ✓ |
7, 15: | - | 1 | 1 | 1 | ✓ |
8, 9: | 1 | 0 | 0 | - | ✓ |
8, 12: | 1 | - | 0 | 0 | ✓ |
12, 14: | 1 | 1 | - | 0 | ✓ |
14, 15: | 1 | 1 | 1 | - | ✓ |
Primimplikantentafel:
x3 | x2 | x1 | x0 | 0 | 2 | 3 | 7 | 8 | 9 | 12 | 14 | 15 | ||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0, 2: | 0 | 0 | - | 0 | ○ | ○ | (x̄3x̄2x̄0) | |||||||
0, 8: | - | 0 | 0 | 0 | ○ | ○ | (x̄2x̄1x̄0) | |||||||
2, 3: | 0 | 0 | 1 | - | ○ | ○ | (x̄3x̄2x1) | |||||||
3, 7: | 0 | - | 1 | 1 | ○ | ○ | (x̄3x1x0) | |||||||
7, 15: | - | 1 | 1 | 1 | ○ | ○ | (x2x1x0) | |||||||
8, 9: | 1 | 0 | 0 | - | ○ | ● | (x3x̄2x̄1) | |||||||
8, 12: | 1 | - | 0 | 0 | ○ | ○ | (x3x̄1x̄0) | |||||||
12, 14: | 1 | 1 | - | 0 | ○ | ○ | (x3x2x̄0) | |||||||
14, 15: | 1 | 1 | 1 | - | ○ | ○ | (x3x2x1) |
Extrahierte essentielle Primimplikanten: (x3x̄2x̄1)
Reduzierte Primimplikantentafel (Iteration 0):
x3 | x2 | x1 | x0 | 0 | 2 | 3 | 7 | 12 | 14 | 15 | ||
---|---|---|---|---|---|---|---|---|---|---|---|---|
0, 2: | 0 | 0 | - | 0 | ● | ○ | (x̄3x̄2x̄0) | |||||
2, 3: | 0 | 0 | 1 | - | ○ | ○ | (x̄3x̄2x1) | |||||
3, 7: | 0 | - | 1 | 1 | ○ | ○ | (x̄3x1x0) | |||||
7, 15: | - | 1 | 1 | 1 | ○ | ○ | (x2x1x0) | |||||
12, 14: | 1 | 1 | - | 0 | ● | ○ | (x3x2x̄0) | |||||
14, 15: | 1 | 1 | 1 | - | ○ | ○ | (x3x2x1) |
Extrahierte essentielle Primimplikanten: (x̄3x̄2x̄0), (x3x2x̄0)
Reduzierte Primimplikantentafel (Iteration 1):
x3 | x2 | x1 | x0 | 3 | 7 | 15 | ||
---|---|---|---|---|---|---|---|---|
3, 7: | 0 | - | 1 | 1 | ● | ○ | (x̄3x1x0) | |
7, 15: | - | 1 | 1 | 1 | ○ | ● | (x2x1x0) |
Extrahierte essentielle Primimplikanten: (x̄3x1x0), (x2x1x0)
Wahrheitstafel:
x2 | x1 | x0 | y | |
---|---|---|---|---|
0: | 0 | 0 | 0 | 1 |
1: | 0 | 0 | 1 | 0 |
2: | 0 | 1 | 0 | 1 |
3: | 0 | 1 | 1 | 1 |
4: | 1 | 0 | 0 | 1 |
5: | 1 | 0 | 1 | 1 |
6: | 1 | 1 | 0 | 0 |
7: | 1 | 1 | 1 | 1 |
Implikanten (Ordnung 0):
x2 | x1 | x0 | ||
---|---|---|---|---|
0: | 0 | 0 | 0 | → |
2: | 0 | 1 | 0 | → |
3: | 0 | 1 | 1 | → |
4: | 1 | 0 | 0 | → |
5: | 1 | 0 | 1 | → |
7: | 1 | 1 | 1 | → |
Implikanten (Ordnung 1):
x2 | x1 | x0 | ||
---|---|---|---|---|
0, 2: | 0 | - | 0 | ✓ |
0, 4: | - | 0 | 0 | ✓ |
2, 3: | 0 | 1 | - | ✓ |
3, 7: | - | 1 | 1 | ✓ |
4, 5: | 1 | 0 | - | ✓ |
5, 7: | 1 | - | 1 | ✓ |
Primimplikantentafel:
x2 | x1 | x0 | 0 | 2 | 3 | 4 | 5 | 7 | ||
---|---|---|---|---|---|---|---|---|---|---|
0, 2: | 0 | - | 0 | ○ | ○ | (x̄2x̄0) ≡ p0 | ||||
0, 4: | - | 0 | 0 | ○ | ○ | (x̄1x̄0) ≡ p1 | ||||
2, 3: | 0 | 1 | - | ○ | ○ | (x̄2x1) ≡ p2 | ||||
3, 7: | - | 1 | 1 | ○ | ○ | (x1x0) ≡ p3 | ||||
4, 5: | 1 | 0 | - | ○ | ○ | (x2x̄1) ≡ p4 | ||||
5, 7: | 1 | - | 1 | ○ | ○ | (x2x0) ≡ p5 |
(p0 ∨ p1)(p0 ∨ p2)(p2 ∨ p3)(p1 ∨ p4)(p4 ∨ p5)(p3 ∨ p5)
⇔ (p0 ∨ p0p2 ∨ p0p1 ∨ p1p2)(p1p2 ∨ p2p4 ∨ p1p3 ∨ p3p4)(p3p4 ∨ p4p5 ∨ p3p5 ∨ p5)
⇔ (p0 ∨ p1p2)(p1p2 ∨ p2p4 ∨ p1p3 ∨ p3p4)(p3p4 ∨ p5)
⇔ (p0p1p2 ∨ p0p2p4 ∨ p0p1p3 ∨ p0p3p4 ∨ p1p2 ∨ p1p2p4 ∨ p1p2p3 ∨ p1p2p3p4)(p3p4 ∨ p5)
⇔ (p0p2p4 ∨ p0p1p3 ∨ p0p3p4 ∨ p1p2)(p3p4 ∨ p5)
⇔ (p0p2p3p4 ∨ p0p2p4p5 ∨ p0p1p3p4 ∨ p0p1p3p5 ∨ p0p3p4 ∨ p0p3p4p5 ∨ p1p2p3p4 ∨ p1p2p5)
⇔ (p0p2p4p5 ∨ p0p1p3p5 ∨ p0p3p4 ∨ p1p2p3p4 ∨ p1p2p5)
Anregungen oder Verbesserungsvorschläge können auch gerne per E-mail an mich gesendet werden: Kontakt