T10-Normalformen-DNF-und-Schaltkreis-Definition

Normalformen, DNF & Schaltkreis-Definition

Zusammenfassung

Dieses Thema ist foundational für die Klausuraufgaben A1 (KV-Diagramm) und A3 (BA/PLA). Die DNF (Disjunktive Normalform) ist die Standarddarstellung Boolescher Funktionen als ODER-Verknüpfung von UND-Termen (Monomen). Die kanonische DNF (KDNF) entsteht aus der ON-Menge. Schaltkreise werden formal als gerichtete azyklische Graphen (DAGs) modelliert, mit Kosten (Anzahl Gatter) und Tiefe (längster Pfad). Diese Definitionen sind Voraussetzung für das Verständnis von PLA-Minimierung (A1) und Schaltkreiskosten (A3).

Exam-Relevanz

Nicht direkt als Klausuraufgabe gefragt, aber unerlässlich für:

  • A1 (KV-Diagramm): Kenntnis von ON-Menge, Mintermen, DNF, Primimplikanten
  • A3 (BA/PLA): Schaltkreiskosten, Tiefe, hierarchischer Entwurf

Boolesche Funktionen

Eine Boolesche Funktion ist eine Abbildung:

Die Menge aller Booleschen Funktionen mit Eingängen wird mit bezeichnet. Eine Funktion hat Eingänge und Ausgänge.

Literale

Ein Literal ist eine Variable oder deren Negation :

  • — positives Literal (auch geschrieben)
  • — negatives Literal (auch , , )

Monome

Ein Monom ist eine Konjunktion (UND) von Literalen, in der kein Literal mehrfach vorkommt und nicht beide Polaritäten derselben Variable auftreten. Die Konstante ist ebenfalls ein Monom.

Beispiele:

  • — Monom ✓
  • — kein Monom (Widerspruch: und )
  • — kein Monom (doppelt)

Minterme

Ein Monom heißt vollständig oder Minterm, wenn jede Variable entweder als positives oder negatives Literal vorkommt.

Für eine Eingabebelegung ist der zugehörige Minterm:

mit und .

Beispiel: — wird genau dann 1, wenn .

Polynome

Eine Disjunktion (ODER) von paarweise verschiedenen Monomen heißt Polynom. Sind alle Monome vollständig, heißt das Polynom vollständig.

Beispiel: ist ein Polynom (nicht vollständig); ist ein vollständiges Polynom.

DNF (Disjunktive Normalform)

Ein Polynom für heißt disjunktive Normalform (DNF) von . Ein vollständiges Polynom für heißt kanonische disjunktive Normalform (KDNF) von .

Auch bekannt als Sum of Products (SOP) — nicht zu verwechseln mit der Konjunktiven Normalform (KNF / CNF / Product of Sums).

KDNF aus Wahrheitstabelle

Die KDNF ergibt sich direkt aus der ON-Menge:

Die KDNF ist (bis auf Anordnung) eindeutig.

Beispiel: Für ergibt sich die Wahrheitstabelle:
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

KDNF:

Realisierung der DNF

  1. Logikgatter: Bilde alle Monome mit UND-Gattern, verbinde mit ODER-Gattern. Kosten = Anzahl UND- + ODER-Gatter.
  2. PLA (Programmable Logic Array): Zweistufige Darstellung, benötigt weniger Transistoren. Besteht aus UND-Feld (Monomleitungen) und ODER-Feld (Funktionsleitungen).

ON-Menge & OFF-Menge

  • heißt Erfüllbarkeitsmenge
  • heißt Unerfüllbarkeitsmenge
  • Es gilt und

PLA-Kostenmaße

Sei ein Monom, dann sind die Kosten (Anzahl Transistoren im PLA).

Primäre Kosten () — Anzahl der Zeilen (Monome) im PLA:

Sekundäre Kosten () — Anzahl der Transistoren:

Kombiniertes Kostenmaß : Zuerst wird minimiert, dann .

Schaltkreis-Definition

Ein Schaltkreis ist ein 5-Tupel:

über einer Zellenbibliothek mit:

  • — Folge von Eingängen
  • — azyklischer, gerichteter Graph (DAG) mit
  • — Menge der Gatter
  • — ordnet jedem Gatter einen Zellentyp zu
  • — Reihenfolge der eingehenden Kanten pro Gatter
  • — Ausgänge

Bedingungen

  • Für jedes Gatter mit gilt
  • für

Semantik (Belegung)

Für Eingangsbelegung ist die Belegung definiert als:

für Gatter mit und .

Wohldefiniertheit: Da azyklisch ist, existiert eine topologische Sortierung, entlang derer eindeutig berechenbar ist (Induktion über ).

Kosten und Tiefe

  • → Fläche und Energieverbrauch
  • → Signallaufzeit → maximale Taktfrequenz

Hierarchischer Entwurf

In hierarchischen Schaltkreisen werden Teilschaltkreise durch Symbole ersetzt. Den zugehörigen "flachen" Schaltkreis erhält man durch Einsetzen der Teilschaltkreise.

Kostenberechnung: Die Kosten eines hierarchischen Schaltkreises ergeben sich aus der Summe der Kosten aller Teilschaltkreise (jeder Teilschaltkreis wird bei der Zählung aufgelöst).

Beispiel: Ein Carry-Ripple-Addierer besteht aus Volladdierern (FA). Jeder FA kostet 5 Gatter:

Beispiel: Funktion → Wahrheitstabelle → DNF → Schaltkreis → Kosten

Aufgabe

Gegeben sei die Funktion mit:

Schritt 1: Wahrheitstabelle
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1

Schritt 2: KDNF

Schritt 3: Vereinfachung

Die Minterme lassen sich zusammenfassen (jeweils zwei benachbarte):

Das Minimalpolynom ist also einfach .

Schritt 4: Schaltkreis und Kosten

  • KDNF-Schaltkreis: 4 UND-Gatter (je 3 Eingänge) + 1 ODER-Gatter (4 Eingänge) → ,
  • Minimalpolynom-Schaltkreis: Direkter Draht von zum Ausgang → ,

Dies zeigt den Nutzen der Logikminimierung: Die KDNF ist eindeutig aber oft teuer; das Minimalpolynom ist deutlich kompakter.

Symbolische Simulation

Bei der symbolischen Simulation werden keine festen Werte, sondern Boolesche Variablen an die Eingänge gelegt. Für jeden Knoten wird der Boolesche Ausdruck berechnet.

Beispiel (aus Blatt 5): Für Gatter , , :

Übungsblätter

Blatt Aufgabe Thema Punkte
Blatt05 2a Schaltkreis zeichnen aus formaler Beschreibung 3
Blatt05 2b Symbolische Simulation 2
Blatt05 4a–c Eindeutigkeit der Belegung (Wurzel, topo. Sortierung, Induktion) 3
Blatt06 4 NAND-Realisierung aller STD-Gatter (Kosten ) 3+4
Blatt06 5a KV-Diagramm, Primimplikanten aus ON-Menge 3
Blatt06 5b , für vollständiges und reduziertes Polynom 2

Quellen

Priorität

HIGH. Grundlage für A1 (KV-Diagramm erfordert DNF/ON-set-Wissen) und A3 (Schaltkreiskosten/-tiefe). Beherrsche:

  1. KDNF aus Wahrheitstabelle aufstellen
  2. ON-Menge / OFF-Menge und deren Beziehung
  3. Schaltkreis als 5-Tupel, Kosten , Tiefe
  4. PLA-Kostenmaße ,
  5. Symbolische Simulation