Boolesche Ausdrücke und Funktionen

Boolesche Algebra ist Algebra der Logik. Es behandelt Variablen, die zwei diskrete Werte haben können, 0 (False) und 1 (True); und Operationen, die logische Bedeutung haben. Die früheste Methode zur Manipulation der symbolischen Logik wurde von George Boole erfunden und später als Boolesche Algebra bekannt.

Die Boolesche Algebra ist aufgrund ihrer breiten Anwendbarkeit in der Schalttheorie, beim Aufbau grundlegender elektronischer Schaltkreise und beim Entwurf digitaler Computer zu einem unverzichtbaren Werkzeug in der Informatik geworden.

Boolesche Funktionen

A Boolean functionist eine spezielle Art von mathematischer Funktion $ f: X ^ n \ rightarrow X $ vom Grad n, wobei $ X = \ lbrace {0, 1} \ rbrace $ eine boolesche Domäne und n eine nicht negative ganze Zahl ist. Es wird beschrieben, wie die Boolesche Ausgabe von den Booleschen Eingaben abgeleitet wird.

Example- Sei $ F (A, B) = A'B '$. Dies ist eine Funktion des Grades 2 von der Menge der geordneten Paare boolescher Variablen zur Menge $ \ lbrace {0, 1} \ rbrace $, wobei $ F (0, 0) = 1, F (0, 1) = 0, F (1, 0) = 0 $ und $ F (1, 1) = 0 $

Boolesche Ausdrücke

A Boolean expressionErzeugt immer einen Booleschen Wert. Ein Boolescher Ausdruck besteht aus einer Kombination der Booleschen Konstanten (True oder False), Booleschen Variablen und logischen Verknüpfungen. Jeder Boolesche Ausdruck repräsentiert eine Boolesche Funktion.

Example - $ AB'C $ ist ein boolescher Ausdruck.

Boolesche Identitäten

Doppelkomplementgesetz

$ \ sim (\ sim A) = A $

Ergänzungsgesetz

$ A + \ sim A = 1 $ (ODER Formular)

$ A. \ sim A = 0 $ (UND-Form)

Idempotentes Gesetz

$ A + A = A $ (ODER Formular)

$ A. A = A $ (UND Form)

Identitätsgesetz

$ A + 0 = A $ (ODER Formular)

$ A. 1 = A $ (UND-Form)

Dominanzgesetz

$ A + 1 = 1 $ (ODER Formular)

$ A. 0 = 0 $ (UND-Formular)

Kommutativgesetz

$ A + B = B + A $ (ODER Formular)

$ A. B = B. A $ (UND-Formular)

Assoziatives Recht

$ A + (B + C) = (A + B) + C $ (ODER Form)

$ A. (B. C) = (A. B). C $ (UND Formular)

Absorptionsgesetz

$ A. (A + B) = A $

$ A + (A. B) = A $

Vereinfachungsgesetz

$ A. (\ sim A + B) = A. B $

$ A + (\ sim A. B) = A + B $

Verteilungsrecht

$ A + (B. C) = (A + B). (A + C) $

$ A. (B + C) = (A. B) + (A. C) $

De-Morgans Gesetz

$ \ sim (A. B) = \ sim A + \ sim B $

$ \ sim (A + B) = \ sim A. \ sim B $

Kanonische Formen

Für einen booleschen Ausdruck gibt es zwei Arten von kanonischen Formen -

  • Die Summe der Zwischenzeiten (SOM)
  • Das Produkt der Maxterms (POM) Form

Das Formular Summe der Zwischenzeiten (SOM) oder Summe der Produkte (SOP)

Ein Minterm ist ein Produkt aller Variablen, die entweder in ihrer direkten oder komplementären Form genommen werden. Jede Boolesche Funktion kann als Summe ihrer 1-Minuten ausgedrückt werden, und die Umkehrung der Funktion kann als Summe ihrer 0-Minuten ausgedrückt werden. Daher,

F (Liste der Variablen) = ∑ (Liste der 1-Minterm-Indizes)

und

F '(Liste der Variablen) = ∑ (Liste der 0-Minterm-Indizes)

EIN B. C. Begriff Minterm
0 0 0 x'y'z ' m 0
0 0 1 x'y'z m 1
0 1 0 x'yz ' m 2
0 1 1 x'yz m 3
1 0 0 xy'z ' m 4
1 0 1 xy'z m 5
1 1 0 xyz ' m 6
1 1 1 xyz m 7

Example

Sei $ F (x, y, z) = x 'y' z '+ xy' z + xyz '+ xyz $

Oder $ F (x, y, z) = m_0 + m_5 + m_6 + m_7 $

Daher,

$ F (x, y, z) = \ sum (0, 5, 6, 7) $

Jetzt finden wir das Komplement von $ F (x, y, z) $

$ F '(x, y, z) = x' yz + x 'y' z + x 'yz' + xy 'z' $

Oder $ F '(x, y, z) = m_3 + m_1 + m_2 + m_4 $

Daher,

$ F '(x, y, z) = \ sum (3, 1, 2, 4) = \ sum (1, 2, 3, 4) $

Das Produkt Produkt von Maxterms (POM) oder Produkt von Summen (POS) bilden

Ein Maxterm ist die Addition aller Variablen, die entweder in ihrer direkten oder komplementären Form genommen werden. Jede Boolesche Funktion kann als Produkt ihrer 0-Maxterme ausgedrückt werden, und die Umkehrung der Funktion kann als Produkt ihrer 1-Maxterme ausgedrückt werden. Daher,

F (Liste der Variablen) = $ \ pi $ (Liste der 0-Maxterm-Indizes).

und

F '(Liste der Variablen) = $ \ pi $ (Liste der 1-Maxterm-Indizes).

EIN B. C. Begriff Maxterm
0 0 0 x + y + z M 0
0 0 1 x + y + z ' M 1
0 1 0 x + y '+ z M 2
0 1 1 x + y '+ z' M 3
1 0 0 x '+ y + z M 4
1 0 1 x '+ y + z' M 5
1 1 0 x '+ y' + z M 6
1 1 1 x '+ y' + z ' M 7

Beispiel

Sei $ F (x, y, z) = (x + y + z). (x + y + z '). (x + y '+ z). (x '+ y + z) $

Oder $ F (x, y, z) = M_0. M_1. M_2. M_4 $

Daher,

$ F (x, y, z) = \ pi (0, 1, 2, 4) $

$ F '' (x, y, z) = (x + y '+ z'). (x '+ y + z'). (x '+ y' + z). (x '+ y' + z ') $

Oder $ F (x, y, z) = M_3. M_5. M_6. M_7 $

Daher,

$ F '(x, y, z) = \ pi (3, 5, 6, 7) $

Logikgatter

Boolesche Funktionen werden mithilfe von Logikgattern implementiert. Das Folgende sind die Logikgatter -

NICHT Tor

Ein NOT-Gatter invertiert einen einzelnen Bit-Eingang in ein einzelnes Bit des Ausgangs.

EIN ~ A.
0 1
1 0

UND Tor

Ein UND-Gatter ist ein Logikgatter, das nur dann einen hohen Ausgang liefert, wenn alle seine Eingänge hoch sind, andernfalls gibt es einen niedrigen Ausgang. Ein Punkt (.) Zeigt die UND-Verknüpfung an.

EIN B. AB
0 0 0
0 1 0
1 0 0
1 1 1

ODER Tor

Ein ODER-Gatter ist ein Logikgatter, das eine hohe Ausgabe liefert, wenn mindestens einer der Eingänge hoch ist. Ein Pluszeichen (+) zeigt die ODER-Verknüpfung an.

EIN B. A + B.
0 0 0
0 1 1
1 0 1
1 1 1

NAND-Tor

Ein NAND-Gatter ist ein Logikgatter, das nur dann einen niedrigen Ausgang liefert, wenn alle seine Eingänge hoch sind, andernfalls gibt es einen hohen Ausgang.

EIN B. ~ (AB)
0 0 1
0 1 1
1 0 1
1 1 0

NOR-Tor

Ein NOR-Gatter ist ein Logikgatter, das eine hohe Ausgabe liefert, wenn beide Eingänge niedrig sind, andernfalls eine niedrige Ausgabe.

EIN B. ~ (A + B)
0 0 1
0 1 0
1 0 0
1 1 0

XOR-Tor (exklusiv ODER)

Ein XOR-Gatter ist ein Logikgatter, das eine hohe Ausgabe liefert, wenn die Eingänge unterschiedlich sind, andernfalls eine niedrige Ausgabe.

EIN B. A⊕B
0 0 0
0 1 1
1 0 1
1 1 0

X-NOR-Gatter (exklusives NOR)

Ein EX-NOR-Gatter ist ein Logikgatter, das bei gleichen Eingängen einen hohen Ausgang liefert, andernfalls einen niedrigen Ausgang.

EIN B. A X-NOR B.
0 0 1
0 1 0
1 0 0
1 1 1