Umwandlung von Wahrheitstabellen in boolesche Ausdrücke

Beim Entwerfen digitaler Schaltungen beginnt der Designer oft mit einer Wahrheitstabelle, die beschreibt, was die Schaltung tun soll.

Die Entwurfsaufgabe besteht hauptsächlich darin, zu bestimmen, welcher Schaltungstyp die in der Wahrheitstabelle beschriebene Funktion ausführt.

Während einige Leute die natürliche Fähigkeit zu haben scheinen, sich eine Wahrheitstabelle anzusehen und sich sofort die notwendigen Logikgatter- oder Relaislogikschaltungen für die Aufgabe vorzustellen, stehen für den Rest von uns Verfahrenstechniken zur Verfügung.

Hier beweist die Boolesche Algebra auf dramatische Weise ihre Nützlichkeit.

Um diese Vorgehensweise zu veranschaulichen, sollten wir mit einem realistischen Entwurfsproblem beginnen.

Angenommen, wir hätten die Aufgabe, einen Flammenerkennungskreislauf für eine Verbrennungsanlage für giftige Abfälle zu entwerfen.

Die starke Hitze des Feuers soll die Giftigkeit des in die Verbrennungsanlage eingebrachten Abfalls neutralisieren.

Solche verbrennungsbasierten Techniken werden häufig verwendet, um medizinische Abfälle zu neutralisieren, die mit tödlichen Viren oder Bakterien infiziert sein können:

Solange eine Flamme in der Verbrennungsanlage aufrechterhalten wird, ist es sicher, Abfall zur Neutralisation in sie einzuspritzen.

Wenn die Flamme jedoch erlischt, wäre es unsicher, weiterhin Abfall in die Brennkammer einzuspritzen, da dieser unneutralisiert aus dem Abgas austreten und eine Gesundheitsgefahr für alle Personen darstellen würde, die sich in unmittelbarer Nähe des Abgases befinden.

Was wir in diesem System brauchen, ist eine sichere Möglichkeit, das Vorhandensein einer Flamme zu erkennen und das Einbringen von Abfall nur dann zuzulassen, wenn eine Flamme durch das Flammenerkennungssystem „bewiesen“ wird.

Es gibt verschiedene Technologien zur Flammenerkennung:optisch (Lichterkennung), thermisch (Erkennung hoher Temperatur) und elektrische Leitung (Erkennung ionisierter Partikel im Flammenweg), jede mit ihren einzigartigen Vor- und Nachteilen.

Nehmen wir an, dass aufgrund des hohen Gefahrengrades, der mit dem möglicherweise austretenden nicht neutralisierten Abfall aus dem Abgas dieser Verbrennungsanlage verbunden ist, entschieden wird, das Flammenerkennungssystem überflüssig zu machen (mehrere Sensoren), damit der Ausfall eines einzelnen Sensors nicht dazu führt zu einer Emission von Giftstoffen aus dem Auspuff.

Jeder Sensor ist mit einem Schließer ausgestattet (offen, wenn keine Flamme, geschlossen, wenn Flamme erkannt wird), mit dem wir die Eingänge eines Logiksystems aktivieren:

Unsere Aufgabe ist es nun, die Schaltung des Logiksystems so zu gestalten, dass das Abfallventil nur dann geöffnet wird, wenn die Sensoren eine gute Flamme nachweisen.

Zuerst müssen wir jedoch entscheiden, wie das logische Verhalten dieses Kontrollsystems aussehen soll.

Soll das Ventil geöffnet werden, wenn nur einer der drei Sensoren eine Flamme erkennt? Wahrscheinlich nicht, da dies den Zweck der Verwendung mehrerer Sensoren zunichte machen würde.

Wenn einer der Sensoren so ausfällt, dass fälschlicherweise das Vorhandensein einer Flamme angezeigt wird, obwohl keine vorhanden ist, würde ein Logiksystem, das auf dem Prinzip „jeder von drei Sensoren zeigt Flamme“ basiert, denselben Ausgang liefern wie ein Einzelsensorsystem würde den gleichen Fehler haben.

Eine weitaus bessere Lösung wäre, das System so zu konzipieren, dass das Ventil dann und nur dann geöffnet wird, wenn alle drei Sensoren eine gute Flamme erkennen.

Auf diese Weise kann ein einzelner ausgefallener Sensor, der fälschlicherweise eine Flamme anzeigt, das Ventil nicht in der geöffneten Position halten; Stattdessen müssten alle drei Sensoren auf die gleiche Weise ausfallen – ein höchst unwahrscheinliches Szenario – damit dieser gefährliche Zustand eintritt.

Somit würde unsere Wahrheitstabelle wie folgt aussehen:

Es erfordert nicht viel Einsicht, um zu erkennen, dass diese Funktionalität mit einem UND-Gatter mit drei Eingängen erzeugt werden könnte:Der Ausgang der Schaltung wird genau dann „hoch“ sein, wenn Eingang A UND Eingabe B UND Eingang C sind alle „high:“

Bei Verwendung von Relaisschaltkreisen könnten wir diese UND-Funktion erstellen, indem wir drei Relaiskontakte in Reihe schalten oder einfach die drei Sensorkontakte in Reihe schalten, so dass die einzige Möglichkeit zum Öffnen des Abfallventils elektrische Leistung gesendet werden kann, wenn alle drei Sensoren Flamme anzeigen:

Diese Designstrategie maximiert zwar die Sicherheit, macht das System jedoch sehr anfällig für Sensorausfälle der entgegengesetzten Art.

Angenommen, einer der drei Sensoren würde so ausfallen, dass er keine Flamme anzeigt, obwohl in der Verbrennungskammer der Verbrennungsanlage wirklich eine gute Flamme war.

Dieser einzelne Fehler würde das Abfallventil unnötigerweise schließen, was zu Produktionsverlusten und Brennstoffverschwendung (Feuerung eines Feuers, das nicht zur Verbrennung von Abfall verwendet wurde) führt.

Es wäre schön, ein Logiksystem zu haben, das diese Art von Fehlern zulässt, ohne das System unnötig herunterzufahren, aber dennoch eine Sensorredundanz bietet, um die Sicherheit zu gewährleisten, falls ein einzelner Sensor „hoch“ ausfällt (immer Flamme zeigt) , ob einer zu erkennen war oder nicht).

Eine Strategie, die beide Anforderungen erfüllen würde, wäre eine „Zwei-aus-drei“-Sensorlogik, bei der das Abfallventil geöffnet wird, wenn mindestens zwei der drei Sensoren eine gute Flamme zeigen.

Die Wahrheitstabelle für ein solches System würde wie folgt aussehen:

Sum-of-Products verwenden

Hier ist es nicht unbedingt offensichtlich, welche Art von Logikschaltung die Wahrheitstabelle erfüllen würde.

Eine einfache Methode zum Entwerfen einer solchen Schaltung findet sich jedoch in einer Standardform eines booleschen Ausdrucks namens Sum-Of-Products , oder SOP , bilden.

Wie Sie vielleicht vermuten, ist ein boolescher Sum-Of-Products-Ausdruck buchstäblich ein Satz von hinzugefügten booleschen Begriffen (summiert ) zusammen, wobei jeder Begriff ein Multiplikativ ist (Produkt ) Kombination von Booleschen Variablen.

Ein Beispiel für einen SOP-Ausdruck wäre etwa so:ABC + BC + DF, die Summe der Produkte „ABC“, „BC“ und „DF“.

Sum-Of-Products-Ausdrücke lassen sich leicht aus Wahrheitstabellen generieren.

Alles, was wir tun müssen, ist, die Wahrheitstabelle für alle Zeilen zu untersuchen, deren Ausgabe „hoch“ (1) ist, und einen booleschen Produktterm zu schreiben, der unter diesen Eingabebedingungen einem Wert von 1 entsprechen würde.

In der vierten Zeile unten in der Wahrheitstabelle für unser Zwei-aus-drei-Logiksystem, in dem A=0, B=1 und C=1 ist, wäre der Produktterm beispielsweise A'BC, da dieser Term hätte einen Wert von 1, wenn und nur wenn A=0, B=1 und C=1:

Drei andere Zeilen der Wahrheitstabelle haben einen Ausgabewert von 1, daher benötigen diese Zeilen auch boolesche Produktausdrücke, um sie darzustellen:

Schließlich verbinden wir diese vier booleschen Produktausdrücke durch Addition, um einen einzelnen booleschen Ausdruck zu erstellen, der die Wahrheitstabelle als Ganzes beschreibt:

Da wir nun einen booleschen Sum-Of-Products-Ausdruck für die Funktion der Wahrheitstabelle haben, können wir leicht ein Logikgatter oder eine Relaislogikschaltung basierend auf diesem Ausdruck entwerfen:

Leider sind diese beiden Schaltungen ziemlich komplex und könnten von einer Vereinfachung profitieren.

Mit Techniken der Booleschen Algebra kann der Ausdruck deutlich vereinfacht werden:

Als Ergebnis der Vereinfachung können wir jetzt viel einfachere Logikschaltungen bauen, die dieselbe Funktion ausführen, entweder in Gatter- oder Relaisform:

Jeder dieser Kreise wird die Aufgabe des Betriebs des Abfallventils der Verbrennungsanlage auf der Grundlage einer Flammenüberprüfung von zwei der drei Flammensensoren angemessen erfüllen.

Das ist zumindest das, was wir für eine sichere Verbrennungsanlage brauchen.

Wir können jedoch die Funktionalität des Systems erweitern, indem wir eine Logikschaltung hinzufügen, die so ausgelegt ist, dass sie erkennt, ob einer der Sensoren nicht mit den anderen beiden übereinstimmt.

Wenn alle drei Sensoren richtig funktionieren, sollten sie Flammen mit gleicher Genauigkeit erkennen.

Daher sollten sie entweder alle „niedrig“ (000:keine Flamme) oder alle „hoch“ (111:gute Flamme) registrieren.

Jede andere Ausgangskombination (001, 010, 011, 100, 101 oder 110) stellt eine Abweichung zwischen den Sensoren dar und kann daher als Indikator für einen möglichen Sensorfehler dienen.

Wenn wir Schaltkreise hinzufügen würden, um einen der sechs „Sensor-Nichtübereinstimmung“-Zustände zu erkennen, könnten wir den Ausgang dieser Schaltkreise verwenden, um einen Alarm zu aktivieren.

Wer auch immer die Verbrennungsanlage überwacht, würde dann ein Urteil fällen, indem sie entweder mit einem möglicherweise ausgefallenen Sensor (Eingänge:011, 101 oder 110) weiterarbeitet oder die Verbrennungsanlage sicherheitshalber abschaltet.

Auch wenn die Verbrennungsanlage abgeschaltet ist (keine Flamme) und einer oder mehrere der Sensoren immer noch Flamme anzeigen (001, 010, 011, 100, 101 oder 110), während die anderen keine Flamme anzeigen, es ist bekannt, dass ein eindeutiges Sensorproblem vorliegt.

Der erste Schritt beim Entwerfen dieses Schaltkreises zur Erkennung von „Sensorunstimmigkeiten“ besteht darin, eine Wahrheitstabelle zu schreiben, die sein Verhalten beschreibt.

Da wir bereits eine Wahrheitstabelle haben, die den Ausgang der Logikschaltung „gute Flamme“ beschreibt, können wir der Tabelle einfach eine weitere Ausgangsspalte hinzufügen, um die zweite Schaltung darzustellen, und eine Tabelle erstellen, die das gesamte Logiksystem darstellt:

Es ist zwar möglich, einen Sum-Of-Products-Ausdruck für diese neue Wahrheitstabellenspalte zu generieren, dafür wären jedoch sechs Terme mit jeweils drei Variablen erforderlich!

Ein solcher boolescher Ausdruck würde viele Schritte zur Vereinfachung erfordern, mit einem großen Potenzial für algebraische Fehler:

Produkt-von-Summen verwenden

Eine Alternative zur Generierung eines Sum-Of-Products-Ausdrucks zur Berücksichtigung aller „hohen“ (1) Ausgabebedingungen in der Wahrheitstabelle ist die Generierung eines Product-Of-Sums , oder POS , Ausdruck, um stattdessen alle „niedrigen“ (0) Ausgabebedingungen zu berücksichtigen.

Da es in der letzten Wahrheitstabellenspalte viel weniger Instanzen einer "niedrigen" Ausgabe gibt, sollte der resultierende Produkt-von-Summen-Ausdruck weniger Terme enthalten.

Wie der Name schon sagt, ist ein Produkt-von-Summen-Ausdruck eine Reihe von hinzugefügten Begriffen (Summen ), die multipliziert werden (Produkt ) zusammen.

Ein Beispiel für einen POS-Ausdruck wäre (A + B)(C + D), das Produkt der Summen „A + B“ und „C + D“.

Zu Beginn identifizieren wir, welche Zeilen in der letzten Wahrheitstabellenspalte „niedrige“ (0) Ausgaben haben, und schreiben einen Booleschen Summenterm, der für die Eingabebedingungen dieser Zeile gleich 0 wäre.

In der ersten Zeile der Wahrheitstabelle mit A=0, B=0 und C=0 wäre der Summenterm beispielsweise (A + B + C), da dieser Term den Wert 0 hätte, wenn und nur wenn A=0, B=0 und C=0:

Nur eine andere Zeile in der letzten Wahrheitstabellenspalte hat eine "niedrige" (0) Ausgabe, also brauchen wir nur einen weiteren Summenterm, um unseren Produkt-von-Summen-Ausdruck zu vervollständigen.

Dieser letzte Summenterm stellt einen 0-Ausgang für eine Eingangsbedingung von A=1, B=1 und C=1 dar.

Daher muss der Term als (A’ + B’+ C’) geschrieben werden, da nur die Summe der ergänzten Eingabevariablen wären nur für diese Bedingung gleich 0:

Der vervollständigte Produkt-von-Summen-Ausdruck ist natürlich die multiplikative Kombination dieser beiden Summenterme:

Während ein Sum-of-Products-Ausdruck in Form eines Satzes von UND-Gattern implementiert werden könnte, deren Ausgänge mit einem einzelnen ODER-Gatter verbunden sind, kann ein Product-of-Sums-Ausdruck als ein Satz von ODER-Gattern implementiert werden, die in ein einzelnes UND-Gatter:

Während ein Sum-Of-Products-Ausdruck als parallele Sammlung von in Reihe geschalteten Relaiskontakten implementiert werden könnte, kann ein Product-of-Summs-Ausdruck als eine serielle Sammlung von parallel geschalteten Relaiskontakten implementiert werden:

Die beiden vorherigen Schaltungen stellen nur unterschiedliche Versionen der Logikschaltung „Sensorübereinstimmung“ dar, nicht die Schaltung(en) zur Erkennung einer guten Flamme.

Das gesamte Logiksystem wäre die Kombination aus Schaltungen für „gute Flamme“ und „Sensorübereinstimmung“, die im gleichen Diagramm dargestellt sind.

In einer speicherprogrammierbaren Steuerung (SPS) implementiert, könnte das gesamte Logiksystem etwa so aussehen:

Wie Sie sehen können, sind sowohl die booleschen Standardformen Sum-Of-Products als auch Products-Of-Sums leistungsstarke Werkzeuge, wenn sie auf Wahrheitstabellen angewendet werden.

Sie ermöglichen es uns, einen booleschen Ausdruck – und letztendlich eine tatsächliche Logikschaltung – aus nichts anderem als einer Wahrheitstabelle abzuleiten, die eine schriftliche Spezifikation dafür ist, was eine Logikschaltung tun soll.

Um mit einfachen, deterministischen Verfahren von einer schriftlichen Spezifikation zu einer tatsächlichen Schaltung übergehen zu können, ist es möglich, den Entwurfsprozess für eine digitale Schaltung zu automatisieren.

Mit anderen Worten, ein Computer könnte so programmiert werden, dass er eine benutzerdefinierte Logikschaltung aus einer Wahrheitstabellenspezifikation entwirft!

Die Schritte von einer Wahrheitstabelle bis zur endgültigen Schaltung sind so eindeutig und direkt, dass es, wenn überhaupt, nur wenig Kreativität oder andere originelle Gedanken erfordert, um sie auszuführen.

RÜCKBLICK:

• Summe-Of-Produkte , oder SOP , Boolesche Ausdrücke können ganz einfach aus Wahrheitstabellen erzeugt werden, indem bestimmt wird, welche Zeilen der Tabelle eine Ausgabe von 1 haben, indem man einen Produktterm für jede Zeile schreibt und schließlich alle Produktterme summiert. Dadurch wird ein boolescher Ausdruck erstellt, der die Wahrheitstabelle als Ganzes darstellt.
• Sum-Of-Products-Ausdrücke eignen sich gut für die Implementierung als ein Satz von UND-Gattern (Produkten), die in ein einzelnes ODER-Gatter (Summe) einspeisen.
• Produkt-von-Summen , oder POS , Boolesche Ausdrücke können auch recht einfach aus Wahrheitstabellen erzeugt werden, indem man bestimmt, welche Zeilen der Tabelle eine Ausgabe von 0 haben, einen Summenterm für jede Zeile schreiben und schließlich alle Summenterme multiplizieren. Dadurch wird ein boolescher Ausdruck erstellt, der die Wahrheitstabelle als Ganzes darstellt.
• Produkt-von-Summen-Ausdrücken eignen sich gut für die Implementierung als ein Satz von ODER-Gattern (Summen), die in ein einzelnes UND-Gatter (Produkt) einspeisen.

VERWANDTE ARBEITSBLÄTTER:

• Arbeitsblatt für Summen von Produkten und Produkt-von-Summen-Ausdrücken
• Arbeitsblatt zur Booleschen Algebra