====== Bool ======
===== Operationen =====
^ Symbol ^ Name ^ Ersatz/Bemerkung ^
| . | und / //Kon//junktion | ("und" ist kurzes Wort => "." ist kleines Symbol) \\ Con ... Zusammen (Konglomerat) => Nur wenn alle //zusammen// |
| + | oder / //Dis//junktion | ("oder" ist langes wort => "+" ist großes Symbol) \\ Dis ... getrennt => Auch wenn getrennt (aber wenigstens einer) |
| -- | not | oder auch ¬ |
| xor | xor | |
| => | Implikation | --A + B |
| <=> | Äquivalenz | (A . B) + (--A . --B) oder (A => B) . (B => A) |
Für einen $n$ Stelligen Operator mit 1 Ausgang gibt es ${2^2}^n$ möglichkeiten.
==== funktional vollständig ====
Menge n-Stilliger Operationen mit denen man //alle anderen// n-Stelligen Operationen nachmachen kann.
* {+, ., --}
* ...
==== minimal funktional vollständig ====
//Kleinste// Menge n-Stilliger Operationen mit denen man //alle anderen// n-Stelligen Operationen nachmachen kann.
* {., --} Falsch ???
* {+, --} Falsch ???
* {NAND}
* {NOR}
===== Literal =====
(negierte) atomare Aussage.
- Ggf. negierung
- Einzelne Variable!
===== Min- / Maxterm =====
* Einheitlich verknüpfte //Literale//.
* Bei Min- und Maxtermen kommen //alle// verfügbaren Variablen vor.
* Min- und Maxtermen lassen sich ineinander //überführen//.
^ Name ^ Form ^ Eselsbrücke ^ Foo ^
| Minterm \\ Voll//kon//junktion (und) | A.B.C \\ A.-B.C | und => //Min//. Anzahl an 1-Ergebnissen | oderierte Minterme ergeben die K//D//NF |
| Maxterm \\ Voll//dis//junktion (oder) | A+B+C \\ -A+B+-C | oder => //Max//. Anzahl an 1-Ergebnissen |undierte Maxterm ergeben die K//K//NF |
===== Normalformen =====
Aufbau
- Verknüpfung Ebene 1 (Klausel)
- Min-/Maxterm
- Verknüpfung Ebene 2 ("Operator gegenteil")
- Literal
Formen sind ineinender überführbar!
^ Abkürzung ^ Name ^ Form ^
| KNF | **K**onjunktive **N**ormal**f**orm (und) | (A + --C) . (B) |
| KKNF | **K**anonische **k**onjunktive **N**ormal**f**orm (und) | (A + B + --C) . (--A + B + --C) . (--A + B + C) |
| DNF | **D**isjunktive **N**ormal**f**orm (oder) | (A . --C) + (B) |
| KDNF | **K**anonische **d**isjunktive **N**ormal**f**orm (oder) | (A . B . --C) + (--A . B . --C) + (--A . B . C) |
(kanonisch: Vollständig; Alle variablen; wie Matrix)
{{http://upload.wikimedia.org/wikipedia/de/1/1a/KNF%2BDNF.png}} \\
(Quelle: [[http://de.wikipedia.org/wiki/Disjunktive_Normalform|Wikipedia]])
===== Gesetzte =====
* A.(B+C) = (A.B) + (A.C) \\ (Rechenzeichen in und außerhalb der Klammern tauschen)
* --(A.B) = --A + --B
* (A.B) + (--A.B.C) = (A.B) + (B.C)
* Alles nochmal dual
===== Duale Regel =====
Vorbedingung:
* ''... = ...''
* Nur mit ''+'', ''.'', ''1'', ''0'' und ''-''
Vertausche //alle// Elemente und die Aussage bleibt gültig:
* . und +
* 0 und 1
===== Deduktive Vereinfachung =====
Follgende Regeln
* ''X.a + X.-a = X''
* ''X.a + X.-a.Y = X.a + X.Y''
* ''X + X.Y = X''
* Intuition (WTF!)
mit
* X, Y: "Der ganze Rest", Zusamengesetzte Terme
* a: //Ein// Literal (oder ein geklamerter ausdruck, kommt aber nicht bei der Deduktiven Vereinfachung vor)
Funktioniert mit KNF und DNF.
Beispiel in DNF
1: A . -B
2: -B . -C
3: A . -C
4: -A . -B . -C <-- nach Regel 1
5: -A . B . -C <-- nach Regel 1
---------------
1: A . -B
2: -B . -C
3: A . -C <-- nach Regel 1
6: -A. -C <-- nach Regel 1
---------------
1: A . -B
2: -B . -C <-- nach Regel 3
7: -C <-- nach Regel 3
---------------
1: A . -B
8: -C
=> A.--B + --C
===== Inteligente Vereinfachung =====
Mit dem verfahren nach [[http://de.wikipedia.org/wiki/Verfahren_nach_Quine_und_McCluskey|Quine und McCluskey]]. Mehr Infos auch auf http://www.caeci.de/wiki/index.php?title=01.09.09_/_04.09.09_-_Fortsetzung_Quine-McCluskey
==== Minterme erstellen ====
* Aus Wertetabelle
* Zeilen mit 1 im Ergebniss (Fett hervorgehoben).
* 0 -> Negierung
* 1 -> Normal
* Aus logischem Ausdruck [**K**anonische **d**isjunktive **N**ormal**f**orm (oder) = (A . B . --C) + (--A . B . --C) + (--A . B . C)]
* Negierung -> 0
* Normal -> 1
^ Input ^^^^^ Output ^ Minterm ^
^ Bin ^^^^ Dec ^ ::: ^ ::: ^
^ a ^ b ^ c ^ d ^ ::: ^ ::: ^ ::: ^
| 0 | 0 | 0 | 0 | 0 | 0 | |
| 0 | 0 | 0 | 1 | 1 | **1** | --a.--b.--c.d |
| 0 | 0 | 1 | 0 | 2 | 0 | |
| 0 | 0 | 1 | 1 | 3 | **1** | --a.--b.c.d |
| 0 | 1 | 0 | 0 | 4 | 0 |
| 0 | 1 | 0 | 1 | 5 | **1** | --a.b.--c.d |
| 0 | 1 | 1 | 0 | 6 | 0 | |
| ... | | | | | | |
==== Zusamenfassen ====
Minterme -> Rekursiver Zusamenfass-Algorithmus -> Primterme
^ Klasse \\ (Anzahl 1) ^ Minterm ^^^^ Index ^
^ ::: ^ a ^ b ^ c ^ d ^ ::: ^
| 1 | 0 | 0 | 0 | 1 | 1 |
| 2 | 1 | 0 | 1 | 0 | 12 |
| ::: | 0 | 1 | 0 | 1 | 5 |
| ::: | 0 | 0 | 1 | 1 | 3 |
| 3 | 1 | 1 | 1 | 0 | 14 |
| ::: | 0 | 1 | 1 | 1 | 7 |
| 4 | 1 | 1 | 1 | 1 | 15 |
... zwei umformungen später ...
^ Klasse \\ (Anzahl 1) ^ Minterm ^^^^ Index ^ Primterm ^
^ ::: ^ a ^ b ^ c ^ d ^ ::: ^
| 1 | 0 | * | * | 1 | 1, 3, 5, 7 | 1 |
| 2 | 1 | * | 1 | 0 | 12, 14 | 2 |
| 3 | 1 | 1 | 1 | * | 14, 15 | 3 |
| ::: | * | 1 | 1 | 1 | 7, 15 | 4 |
Wiederhole solange sich nicht weiter Zusamenfassen lässt
Für jede Klasse ka:
kb = ka.nextNeighbor
Für jeden Term ta in ka:
Für jeden Term tb in kb:
Wenn ta sich in nur einer Ziffer von tb unterscheidet:
Ersetze Unterschied durch Platzhalter (*)
Wenn neuer Term nicht in neuer Tabelle:
Übernehme Term in neue Tabelle
* Benachbarte Klassen vergleichen
* Thereme mehrfach vergleichen
* Unterschied nur an //einer Stelle// in //1%%/%%0//
* Dopplungen entfernen
* Indizes mitführen
==== Dominanzprüfung ====
Minterm x Primterm Matrix erstellen:
^ Primterm ^ Minterm ^^^^^^^
^ ::: ^ 1 ^ 3 ^ 5 ^ 7 ^ 12 ^ 14 ^ 15 ^
| 1 | X | X | X | X | | | |
| 2 | | | | | X | X | |
| 3 | | | | | | X | X |
| 4 | | | | X | | | X |
^ Primterm ^ Minterm ^^^
^ ::: ^ 1 ^ 12 ^ 15 ^
| 1 | X | | |
| 2 | | X | |
| 3 | | | X |
* Spalten löschen die andere komplett beinhalten (Obermenge)
* Zeilen löschen die von anderen komplett beinhaltet werden (Teilmenge)
* Wiederholen bis nix mehr geht
==== Zusammenführen ====
Primterme Auswählen
* Alle Minterme abdecken
* Mehrere möglichkeiten
^ Primterm ^ a ^ b ^ c ^ d ^ Term ^
| 1 | 0 | * | * | 1 | --a.d |
| 2 | 1 | * | 1 | 0 | a.c.--d |
| 3 | 1 | 1 | 1 | * | a.b.c |
=> --a.d + a.c.--d + a.b.c
===== Addierer =====
Overflow wenn //carry in != carry out// beim //höchstwertigen// Bit bei Addition im //zweierkompliment//
==== Halbaddierer ====
In
* A
* B
Out
* Summe
* Übertrag
==== Volladdierer ====
In
* A
* B
* //Übertrag//
Out
* Summe
* Übertrag
==== Ripple-Carry Addierer ====
VAs in reihe => Langsam
==== Carry-Select Addierer ====
Nächster block immer größer als vorheriger, da ja Ergebnis erst gebraucht wird wenn vorheriger fertig ist. \\
{{http://upload.wikimedia.org/wikipedia/de/thumb/0/0a/Carry-Select-Addierer.png/799px-Carry-Select-Addierer.png?400}}
==== Carry-Save Addierer ====
einfach VAs die carry und sum ausgeben, ohne carry durch zu propagieren. damit kann mehrfach addiert werden und erst am ende muss einnaml das carry durchgerechnet werden
===== Multiplexer =====
n-MUX = Multiplexer mit n //Auswahl//leitungen, also n² Eingängen.
===== Decoder/Encoder =====
n-Bit-Decoder = n Eingänge und n² Ausgänge.
Einganz, Binärzahl, sagt welcher Ausgang high sein soll.
n-Bit-Encoder = n² Eingänge und n Ausgänge.
===== Flip Flop =====
==== RS ====
Eingang: Set, Reset, (Clock/Enable)
> Beides ein = ungültig
^I^^O^^^
^S^R^Q^Q'^Kommentar^
|0|0|Q|Q'|Keine Änderung|
|0|1|0|1|Reset|
|1|0|1|0|Set|
|1|1|1|1|Beide 1 (ungültig)|
D = Don't care \\
Q = Keine änderung, egal was vorher am ausgang anlag
- = Ungültig, man kann keine Aussage treffen
> Vorteil von D-FF gegenüber von RS-FF (LOL): Kein ungültiger zustand / Behebt den vermeintlichen Undeterminismus.
==== D-Flip Flop ====
Eingang: Data, Clock
^ D ^ Q ^
| 0 | 0 |
| 1 | 1 |
==== JK-Flip Flop ====
Eingang: J (Set/toggle), K (Clear/Toggle), Clock
^ J ^ K ^ Q ^
| 0 | 0 | Keine Änderung |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | Toggle |
===== Trash =====
^ Klasse \\ (Anzahl 1) ^ Minterm ^^^^ Index ^
^ ::: ^ a ^ b ^ c ^ d ^ ::: ^
| 1 | 0 | * | 0 | 1 | 1, 5 |
| ::: | 0 | 0 | * | 1 | 1, 3 |
| 2 | 1 | * | 1 | 0 | 12, 14 |
| ::: | 0 | 1 | * | 1 | 5, 7 |
| ::: | 0 | * | 1 | 1 | 3, 7 |
| 3 | 1 | 1 | 1 | * | 14, 15 |
| ::: | * | 1 | 1 | 1 | 7,15 |