Boolesche Gleichungen: Theorie, Anwendungen, Algorithmen

1. Boolesche Gleichungen — mathematische Grundbegriffe.- 1.1. Einführung.- 1.2. Der Raum Bn.- 1.3. Boolesche Funktionen.- 1.4. Boolesche Gleichungen.- 2. Boolesche Differentialgleichungen.- 2.1. Einführung.- 2.2. Grundbegriffe.- 2.3. Integration von Ableitungsoperationen.- 2.4. Integration beliebiger Differentialgleichungen.- 2.5. Abschließende Bemerkungen.- 3. Logische Matrixgleichungen — Theorie und Praxis.- 3.1. Einführung.- 3.2. Logische Gleichung und ihre Lösung — formale Formulierung der Aufgabe.- 3.3. Methoden des kombinatorischen Suchens.- 3.4. Prüfung funktioneller Beziehungen — Lösung logischer Gleichungen.- 3.5. Logische Matrix gleichungen.- 3.6. Unterschiede in der funktioneilen Interpretation der betrachteten Elementarschaltungen.- 3.7. Lösung der Gleichung $$\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle\thicksim}$}}{Y} = \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle\thicksim}$}}{B} \vee \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle\thicksim}$}}{X}$$ mit einer Unbekannten.- 3.8 Lösung der Gleichung $$\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle\thicksim}$}}{Y} = \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle\thicksim}$}}{B} \vee \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle\thicksim}$}}{X}$$ mit zwei Unbekannten.- 3.9 Zur Lösung der Gleichung $$\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle\thicksim}$}}{Y} = \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle\thicksim}$}}{T} \Delta \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle\thicksim}$}}{X} $$.- 3.10. Kompositionen elementarer Matrixoperatoren.- 4. Boolesche Berechnungen und die Lösung logischer Gleichungen.- 4.1. Vollständige und partikuläre Lösung.- 4.2. Intervallform einer Booleschen Funktion.- 4.3. Gleichungen mit polynomialer Komplexität.- 4.3.1. Kompaktheit der Darstellung.- 4.3.2. Gleichung $$c\left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x} } \right) \vee D\left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x} } \right) = 1$$.- 4.3.3. Gleichung $$D_1 \left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x} } \right) \vee D_2 \left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x} } \right) = 1$$.- 4.3.4. Gleichung $$c\left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x} } \right) \wedge D\left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x} } \right) = 1$$.- 4.3.5. Gleichung $$D_1 \left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x} } \right) \wedge D_2 \left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x} } \right) = 1$$.- 4.3.6. Gleichung $$D_1 \left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x} } \right) \wedge D_2 \left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x} } \right) \wedge \ldots \wedge D_n \left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x} } \right) = 1$$.- 4.3.7. Berechnungen mit Risiko.- 4.4. Gleichungen mit exponentieller Komplexität.- 4.4.1. Gleichung $$c\left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x} } \right)\overline {D\left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x} } \right)} \vee D_0 \left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x} } \right) = 1$$.- 4.4.2. Gleichung $$D\left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x} } \right) = 0$$.- 4.4.3. Gleichung $$D_1 \left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x} } \right) \oplus D_2 \left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x} } \right) = 1$$.- 4.4.4. Gleichung $$D_1 \left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x} } \right) = D_2 \left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x} } \right)$$.- 4.4.5. Orthogonalisierung einer DNF.- 4.4.6. Gleichung $$S\left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{x} } \right) = 1$$.- 4.4.7. Superpositionen.- 4.5. Gleichungssysteme.- 4.5.1. System mit disjunktiver Verknüpfung.- 4.5.2. System mit konjunktiver Verknüpfung.- 4.5.3. System mit Zwischenvariablen.- 4.5.4. System allgemeiner Art.- 4.5.5. Disjunktive Zerlegung eines Systems.- 4.5.6. Zerlegung nach Zwischenvariablen.- 4.5.7. Zerlegung nach den Gliedern der äußeren Funktion.- 4.6. Programmtechnische Realisierung von Algorithmen.- 4.6.1. Darstellung einer Konjunktion.- 4.6.2. Formatbeschränkung und faktorisierte DNF.- 4.7. Tests für programmierbare logische Matrizen.- 4.7.1. Mathematisches Modell einer PLA.- 4.7.2. Die Menge von Tests für einen Einzelfehler.- 4.7.3. Minimierung des Tests.- 4.8. Zusammenfassung.- 5. Rechentechnische Erfahrungen mit Booleschen Gleichungen.- 5.1. Algorithmensystem zum Lösen Boolescher Gleichungen und zur Verarbeitung von Lösungsmengen Boolescher Gleichungen.- 5.2. Vergleich von Methoden zum Lösen Boolescher Gleichungen.- 5.3. Parallele Verarbeitung — serielle Verarbeitung.- 5.4. TVL-Sprache.- 5.5. Erfahrungen mit implementierten Programmsystemen auf Klein- und Großrechnern.- 5.6. Berechnung von Funktionswerten Boolescher Funktionen — der Mikrorechner als Automat.- 6. Vergröberung von Graphen.- 6.1. Einführung.- 6.2. Beschreibung von Graphen durch Boolesche Differentialgleichungen.- 6.3. Hauptalgorithmus.- 6.3.1. Projektionen in Graphen.- 6.3.2. Transformation von Graphen.- 6.4. Anwendungen.- 7. Logische Gleichungen und Dekomposition diskreter Automaten.- 7.1. Einleitung.- 7.2. Formulierung der Dekompositionsaufgabe.- 7.2.1. Automaten und Automatennetze.- 7.2.2. Die Funktion, die vom Automatennetz realisiert wird.- 7.2.3. Relation der Realisierung zwischen einem Netz und einem Automaten.- 7.2.4. Formulierung der Dekompositionsaufgabe.- 7.2.5. Einige Eigenschaften von zweitaktigen Systemen.- 7.3. Satz von der Existenz einer Dekomposition.- 7.4. Algorithmus zur Konstruktion eines zweitaktigen Netzes, das einen gegebenen Automaten realisiert.- 7.4.1. Konstruktion der symbolischen Übergangsfunktion des Ausgangsautomaten des Netzes.- 7.4.2. Aufstellung der logischen Gleichung, die die Bedingungen definiert, die den Eingangssignalen des Automaten B auferlegt werden.- 7.5. Konstruktion zweitaktiger Boolescher Netze.- 7.5.1. Boolesche Automaten und Boolesche Automatennetze.- 7.5.2. Konstruktion eines Booleschen Netzes, das einen Booleschen Automaten realisiert.- 7.5.3. Konstruktion eines Booleschen Netzes, das einen Automaten mit abstraktem Alphabet für die inneren Zustände realisiert.- 7.6. Spezielle Netzarten und Automatendekomposition.- 7.6.1. Dekomposition kombinatorischer Automaten.- 7.6.2. Konstruktion eines Netzes mit kombinatorischem Ausgangsautomaten.- 7.7. Zusammenfassung.- 8. Hazardanalyse in asynchronen logischen Schaltungen.- 8.1. Asynchrone logische Schaltung.- 8.2. Begriff des Hazards.- 8.3. Grundlegende Aufgaben der Hazardanalyse.- 8.3.1. Zustands-Hazardanalyse.- 8.3.2. Übergangs-Hazardanalyse.- 8.4. Möglichkeiten, die Lösung von Aufgaben zu vereinfachen.- 8.5. Algorithmus zur Bildung von m(P).- 9. Kompliziertheitsprobleme Boolescher Funktionen und Gleichungen.- 9.1. Einleitung.- 9.2. Schaltkreiskompliziertheit.- 9.3. Berechnungen auf Turingmaschinen.- 9.4. Universelle Durchmusterungsprobleme.- 9.5. Schlußbemerkungen.- 10. Lösung von Kodierungs- und Dekodierungsaufgaben mittels logischer Gleichungen.- 10.1. Einführung.- 10.2. Einige Angaben zur algebraischen Kodierung.- 10.3. Asynchroner Automat und Wettlauferscheinungen von Speicherelementen.- 10.4. Wettläufe, Überdeckungen, Intervalle.- 10.5. Über die Entstehung von Automatenmodellen, die die Anwendung von (2,1)-TS erfordern.- 10.6. Zusammenhang zwischen einem linearen (2,1)-TS und einem gewöhnlichen linearen Kode.- 10.7. Kaskaden-(2,l)-TS.- 10.8. Zusammenfassung.- 11. Analyse und Synthese stabiler binärer Automaten mit Hilfe logischer Gleichungen.- 11.1. Einführung.- 11.2. Intervallfunktionen und -automaten.- 11.3. Asynchrone Automaten und deren Funktionsweise nach Eichelberger.- 11.4. Funktionelle Schaltnetzwerke.- 11.5. Analyse.- 11.6. Synthese.- 12. Algorithmische Strukturbeschreibung von Kommunikationsprozessen.- 12.1. Einführung.- 12.2. Rahmensprache.- 12.3. Verarbeitungssprache.- 12.4. Implementation.- 12.5. Beispiele.- 13. Anwendung der Theorie Boolescher Funktionen auf den Entwurf von Algorithmen.- 13.1. Einleitung.- 13.2. Transformation eines Programms in ein binäres Programm.- 13.3. Optimierungen.- 13.4. Algorithmus zur Gewinnung optimaler binärer Programme.- 13.5. Zusammenfassung.- 14. Boolesche Gleichungen zur Programmierung von Steuerungen.- 14.1. Boolesche Gleichung.- 14.2. Gewinnung Boolescher Gleichungen.- 14.2.1. Intuitive Methode.- 14.2.2. Automatentabellenmethode.- 14.2.3. Ablaufgraphenmethode.- 14.3. Abarbeitung der Booleschen Gleichungen.- 14.3.1. Steuerungen mit Bitprozessor.- 14.3.2. Steuerungen mit Wortprozessor.- 14.3.2.1. Formatieren der Booleschen Gleichung.- 14.3.2.2. Übersetzung in die Sprungstruktur.- 14.3.2.3. Rückübersetzung.- 14.4. Zusammenfassung.