Für einen $n$ Stelligen Operator mit 1 Ausgang gibt es ${2^2}^n$ möglichkeiten.

Menge n-Stilliger Operationen mit denen man alle anderen n-Stelligen Operationen nachmachen kann.

• {+, ., –}
• …

Kleinste Menge n-Stilliger Operationen mit denen man alle anderen n-Stelligen Operationen nachmachen kann.

• {., –} Falsch ???
• {+, –} Falsch ???
• {NAND}
• {NOR}

(negierte) atomare Aussage.

1. Ggf. negierung
2. Einzelne Variable!

• Einheitlich verknüpfte Literale.
• Bei Min- und Maxtermen kommen alle verfügbaren Variablen vor.
• Min- und Maxtermen lassen sich ineinander überführen.

Aufbau

1. Verknüpfung Ebene 1 (Klausel)
2. Min-/Maxterm
   1. Verknüpfung Ebene 2 („Operator gegenteil“)
   2. Literal

Formen sind ineinender überführbar!

(kanonisch: Vollständig; Alle variablen; wie Matrix)

(Quelle: Wikipedia)

• 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

Vorbedingung:

• … = …
• Nur mit +, ., 1, 0 und -

Vertausche alle Elemente und die Aussage bleibt gültig:

• . und +
• 0 und 1

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

Mit dem verfahren nach Quine und McCluskey. Mehr Infos auch auf http://www.caeci.de/wiki/index.php?title=01.09.09_/_04.09.09_-_Fortsetzung_Quine-McCluskey

• Aus Wertetabelle
  • Zeilen mit 1 im Ergebniss (Fett hervorgehoben).
  • 0 → Negierung
  • 1 → Normal
• Aus logischem Ausdruck [Kanonische disjunktive Normalform (oder) = (A . B . –C) + (–A . B . –C) + (–A . B . C)]
  • Negierung → 0
  • Normal → 1

Minterme → Rekursiver Zusamenfass-Algorithmus → Primterme

… zwei umformungen später …

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

Minterm x Primterm Matrix erstellen:

• Spalten löschen die andere komplett beinhalten (Obermenge)
• Zeilen löschen die von anderen komplett beinhaltet werden (Teilmenge)
• Wiederholen bis nix mehr geht

Primterme Auswählen

• Alle Minterme abdecken
• Mehrere möglichkeiten

⇒ –a.d + a.c.–d + a.b.c

Overflow wenn carry in != carry out beim höchstwertigen Bit bei Addition im zweierkompliment

In

• A
• B

Out

• Summe
• Übertrag

In

• A
• B
• Übertrag

Out

• Summe
• Übertrag

VAs in reihe ⇒ Langsam

Nächster block immer größer als vorheriger, da ja Ergebnis erst gebraucht wird wenn vorheriger fertig ist.

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

n-MUX = Multiplexer mit n Auswahlleitungen, also n² Eingängen.

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.

Eingang: Set, Reset, (Clock/Enable)

Beides ein = 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 (): Kein ungültiger zustand / Behebt den vermeintlichen Undeterminismus.

Eingang: Data, Clock

Eingang: J (Set/toggle), K (Clear/Toggle), Clock