Digitale Schaltungen - Boolesche Algebra

Boolean Algebraist eine Algebra, die sich mit Binärzahlen und Binärvariablen befasst. Daher wird es auch als binäre Algebra oder logische Algebra bezeichnet. Ein Mathematiker namens George Boole hatte diese Algebra 1854 entwickelt. Die in dieser Algebra verwendeten Variablen werden auch als Boolesche Variablen bezeichnet.

Der Spannungsbereich, der der Logik 'Hoch' entspricht, wird mit '1' dargestellt, und der Spannungsbereich, der der Logik 'Niedrig' entspricht, wird mit '0' dargestellt.

Postulate und Grundgesetze der Booleschen Algebra

Lassen Sie uns in diesem Abschnitt die Booleschen Postulate und Grundgesetze diskutieren, die in der Booleschen Algebra verwendet werden. Diese sind nützlich, um Boolesche Funktionen zu minimieren.

Boolesche Postulate

Betrachten Sie die Binärzahlen 0 und 1, die Boolesche Variable (x) und ihr Komplement (x '). Entweder die Boolesche Variable oder ein Komplement davon ist bekannt alsliteral. Die vier möglichlogical OR Operationen zwischen diesen Literalen und Binärzahlen sind unten gezeigt.

x + 0 = x

x + 1 = 1

x + x = x

x + x '= 1

Ebenso sind die vier möglich logical AND Operationen zwischen diesen Literalen und Binärzahlen sind unten gezeigt.

x.1 = x

x.0 = 0

xx = x

x.x '= 0

Dies sind die einfachen booleschen Postulate. Wir können diese Postulate leicht überprüfen, indem wir die boolesche Variable durch '0' oder '1' ersetzen.

Note- Das Komplement des Komplements einer booleschen Variablen ist gleich der Variablen selbst. dh (x ')' = x.

Grundgesetze der Booleschen Algebra

Es folgen die drei Grundgesetze der Booleschen Algebra.

  • Kommutativgesetz
  • Assoziatives Recht
  • Verteilungsrecht

Kommutativgesetz

Wenn eine logische Operation von zwei Booleschen Variablen unabhängig von der Reihenfolge dieser beiden Variablen das gleiche Ergebnis liefert, wird diese logische Operation als logisch bezeichnet Commutative. Die logischen ODER- und logischen UND-Operationen zweier boolescher Variablen x und y sind nachstehend aufgeführt

x + y = y + x

xy = yx

Das Symbol '+' zeigt eine logische ODER-Verknüpfung an. Ebenso das Symbol '.' Zeigt die logische UND-Verknüpfung an und kann optional dargestellt werden. Das kommutative Gesetz gehorcht logischen ODER- und logischen UND-Operationen.

Assoziatives Recht

Wenn zuerst eine logische Operation von zwei beliebigen Booleschen Variablen ausgeführt wird und dann dieselbe Operation mit der verbleibenden Variablen ausgeführt wird, ergibt sich dasselbe Ergebnis, dann wird diese logische Operation als solche bezeichnet Associative. Die logischen ODER- und logischen UND-Operationen von drei Booleschen Variablen x, y und z sind unten gezeigt.

x + (y + z) = (x + y) + z

x. (yz) = (xy) .z

Das assoziative Recht gehorcht logischen ODER- und logischen UND-Operationen.

Verteilungsrecht

Wenn eine logische Operation auf alle in der Booleschen Funktion vorhandenen Begriffe verteilt werden kann, wird diese logische Operation als solche bezeichnet Distributive. Die Verteilung der logischen ODER- und logischen UND-Operationen von drei booleschen Variablen x, y und z ist unten gezeigt.

x. (y + z) = xy + xz

x + (yz) = (x + y). (x + z)

Das Verteilungsgesetz gehorcht logischen ODER- und logischen UND-Operationen.

Dies sind die Grundgesetze der Booleschen Algebra. Wir können diese Gesetze leicht überprüfen, indem wir die Booleschen Variablen durch '0' oder '1' ersetzen.

Sätze der Booleschen Algebra

Die folgenden zwei Sätze werden in der Booleschen Algebra verwendet.

  • Dualitätssatz
  • Satz von DeMorgan

Dualitätssatz

Dieser Satz besagt, dass die dualder Booleschen Funktion wird erhalten, indem der logische UND-Operator gegen den logischen ODER-Operator und die Nullen durch Einsen ausgetauscht werden. Für jede Boolesche Funktion gibt es eine entsprechende Dual-Funktion.

Lassen Sie uns die Booleschen Gleichungen (Beziehungen), die wir im Abschnitt über Boolesche Postulate und Grundgesetze besprochen haben, in zwei Gruppen einteilen. Die folgende Tabelle zeigt diese beiden Gruppen.

Gruppe 1 Gruppe2
x + 0 = x x.1 = x
x + 1 = 1 x.0 = 0
x + x = x xx = x
x + x '= 1 x.x '= 0
x + y = y + x xy = yx
x + (y + z) = (x + y) + z x. (yz) = (xy) .z
x. (y + z) = xy + xz x + (yz) = (x + y). (x + z)

In jeder Zeile gibt es zwei Boolesche Gleichungen, die sich gegenseitig verdoppeln. Wir können alle diese Booleschen Gleichungen von Gruppe1 und Gruppe2 unter Verwendung des Dualitätssatzes verifizieren.

Satz von DeMorgan

Dieser Satz ist nützlich, um das zu finden complement of Boolean function. Es besagt, dass das Komplement des logischen ODER von mindestens zwei Booleschen Variablen gleich dem logischen UND jeder komplementierten Variablen ist.

Der Satz von DeMorgan mit 2 Booleschen Variablen x und y kann dargestellt werden als

(x + y) '= x'.y'

Das Duale der obigen Booleschen Funktion ist

(xy) '= x' + y '

Daher ist das Komplement des logischen UND zweier boolescher Variablen gleich dem logischen ODER jeder komplementierten Variablen. In ähnlicher Weise können wir den Satz von DeMorgan auch auf mehr als 2 Boolesche Variablen anwenden.

Vereinfachung boolescher Funktionen

Bisher haben wir die Postulate, Grundgesetze und Theoreme der Booleschen Algebra diskutiert. Lassen Sie uns nun einige boolesche Funktionen vereinfachen.

Beispiel 1

Lasst uns simplify die Boolesche Funktion, f = p'qr + pq'r + pqr '+ pqr

Wir können diese Funktion auf zwei Arten vereinfachen.

Method 1

Bei gegebener Boolescher Funktion ist f = p'qr + pq'r + pqr '+ pqr.

Step 1- Im ersten und zweiten Term ist r gemeinsam und im dritten und vierten Term ist pq gemeinsam. Nehmen Sie also die allgemeinen Begriffe mitDistributive law.

⇒ f = (p'q + pq ') r + pq (r' + r)

Step 2- Die in der ersten Klammer angegebenen Begriffe können auf die Ex-OR-Operation vereinfacht werden. Die Begriffe in der zweiten Klammer können mit '1' vereinfacht werdenBoolean postulate

⇒ f = (p ⊕q) r + pq (1)

Step 3- Der erste Begriff kann nicht weiter vereinfacht werden. Der zweite Term kann jedoch mit pq vereinfacht werdenBoolean postulate.

⇒ f = (p ⊕q) r + pq

Daher ist die vereinfachte Boolesche Funktion f = (p⊕q)r + pq

Method 2

Bei gegebener Boolescher Funktion ist f = p'qr + pq'r + pqr '+ pqr.

Step 1 - Verwenden Sie die Boolean postulate, x + x = x. Das heißt, die logische ODER-Verknüpfung mit einer beliebigen Booleschen Variablen 'n' ist gleich derselben Variablen. Wir können also den letzten Term pqr noch zweimal schreiben.

⇒ f = p'qr + pq'r + pqr '+ pqr + pqr + pqr

Step 2 - Verwenden Distributive lawfür 1 st und 4 - ten Terms, 2 nd und 5 - ten Terms, 3 rd und 6 th Begriffe.

⇒ f = qr (p '+ p) + pr (q' + q) + pq (r '+ r)

Step 3 - Verwenden Boolean postulate, x + x '= 1 zur Vereinfachung der in jeder Klammer enthaltenen Begriffe.

⇒ f = qr (1) + pr (1) + pq (1)

Step 4 - Verwenden Boolean postulate, x.1 = x zur Vereinfachung der obigen drei Terme.

⇒ f = qr + pr + pq

⇒ f = pq + qr + pr

Daher ist die vereinfachte Boolesche Funktion f = pq + qr + pr.

Wir haben also zwei verschiedene Boolesche Funktionen erhalten, nachdem wir die angegebene Boolesche Funktion in jeder Methode vereinfacht haben. Funktionell sind diese beiden Booleschen Funktionen gleich. Basierend auf der Anforderung können wir also eine dieser beiden Booleschen Funktionen auswählen.

Beispiel 2

Lassen Sie uns die finden complement der Booleschen Funktion ist f = p'q + pq '.

Das Komplement der Booleschen Funktion ist f '= (p'q + pq') '.

Step 1 - Verwenden Sie den Satz von DeMorgan (x + y) '= x'.y'.

⇒ f '= (p'q)'. (Pq ')'

Step 2 - Verwenden Sie den Satz von DeMorgan (xy) '= x' + y '

⇒ f '= {(p') '+ q'}. {P '+ (q') '}

Step3 - Verwenden Sie das Boolesche Postulat (x ')' = x.

⇒ f '= {p + q'}. {P '+ q}

⇒ f '= pp' + pq + p'q '+ qq'

Step 4 - Verwenden Sie das Boolesche Postulat xx '= 0.

⇒ f = 0 + pq + p'q '+ 0

⇒ f = pq + p'q '

deshalb, die complement der Booleschen Funktion ist p'q + pq ' pq + p’q’.