Universit"at Trier Fachbereich IV - Informatik

Christoph Meinel: Logikminimierung

Vorlesungsskript WS 1994/95

Inhaltsverzeichnis Zusammenfassung 1 Einf"uhrung 1

1.1 Boolesche Funktionen : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1 1.2 Wichtige Funktionen aus IB0 [ IB1 [ IB2 : : : : : : : : : : : : : : : : : : : 2 1.3 Wichtige Operationen Boolescher Funktionen : : : : : : : : : : : : : : : : 4 1.4 Geometrische Veranschaulichung Boolescher Funktionen : : : : : : : : : : : 5 1.5 Partielle Boolesche Funktionen : : : : : : : : : : : : : : : : : : : : : : : : : 6 1.6 Monotone und symmetrische Boolesche Funktionen : : : : : : : : : : : : : 7

2 Repr"asentation Boolescher Funktionen 10

2.1 Algorithmische Form : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10 2.2 Tabellendarstellung : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 11 2.3 Zweistufige Repr"asentationen : : : : : : : : : : : : : : : : : : : : : : : : : 12

2.3.1 Kanonische disjunktive und konjunktive Normalform : : : : : : : : 13 2.3.2 Ring-Summen-Entwicklung (RSE) : : : : : : : : : : : : : : : : : : 16 2.4 Mehrstufige Repr"asentationen : : : : : : : : : : : : : : : : : : : : : : : : : 17

2.4.1 Boolesche \Omega -Ausdr"ucke : : : : : : : : : : : : : : : : : : : : : : : : 17 2.4.2 Boolesche \Omega -Schaltkreise : : : : : : : : : : : : : : : : : : : : : : : : 21 2.5 Bin"are Entscheidungsgraphen : : : : : : : : : : : : : : : : : : : : : : : : : 23

2.5.1 Entscheidungsb"aume : : : : : : : : : : : : : : : : : : : : : : : : : : 23 2.5.2 Branching Programme : : : : : : : : : : : : : : : : : : : : : : : : : 26 2.5.3 Reduzierte und geordnete bin"are Entscheidungsgraphen (oBDD) : : 27 2.6 DNF-Repr"asentation und PLA-Realisierung : : : : : : : : : : : : : : : : : 31

3 Komplexit"atsaussagen 35

3.1 Vorbemerkungen : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 35 3.2 Komplexit"at Boolescher Polynome : : : : : : : : : : : : : : : : : : : : : : : 36

3.2.1 Effiziente Darstellung mit Booleschen Polynomen : : : : : : : : : : 36 3.2.2 Unterschiedliche Berechnungskraft der verschiedenen Booleschen

Polynome : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 37 3.2.3 Typische Gr"osse von Minimalpolynomen : : : : : : : : : : : : : : : 40 3.3 Komplexit"at Boolescher Formeln und Schaltkreise : : : : : : : : : : : : : : 41

INHALTSVERZEICHNIS ii

3.3.1 Effiziente Darstellung mit Booleschen Formeln und Schaltkreisen : : 41 3.3.2 Typische Gr"osse von Booleschen Formeln und Schaltkreisen : : : : : 44 3.3.3 Formeln und Schaltkreise monotoner Funktionen : : : : : : : : : : : 48 3.4 Komplexit"at von Entscheidungsgraphen : : : : : : : : : : : : : : : : : : : : 48

3.4.1 Effiziente Darstellung mit Entscheidungsb"aumen und BranchingProgrammen : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 48 3.4.2 Unterschiede in der Berechnungskraft von Entscheidungsb"aumen

und Branching-Programmen : : : : : : : : : : : : : : : : : : : : : : 49 3.4.3 Typische Gr"osse von Branching-Programmen : : : : : : : : : : : : : 50 3.5 Beziehungen zwischen den verschiedenen Darstellungen : : : : : : : : : : : 51

4 Zweistufige Logikminimierung 55