Boolesche Algebra Rechner, Wahrheitstabellen Erstellen

Wie man den Rechner benutzt

1. Geben Sie in das Feld Logikfunktion (zum Beispiel x1 ∨ x2) oder sein Vektor (zum Beispiel, 10110101)
2. Geben Sie die Aktionen an, die mit den Schaltern ausgeführt werden sollen
3. Geben Sie an, ob die Ausgabe der Lösung durch den Schalter "Mit Lösung" erforderlich ist
4. Klicken Sie auf die Schaltfläche "Ergebnis".

Verwendete Symbole

Als Variablen werden die Buchstaben des lateinischen Alphabets verwendet, sowie Zahlen, die hinter dem Buchstaben stehen (Variablenindex). Die Namen der Variablen lauten also: a, x, a1, B, X, X1, Y1, A123 und so weiter.

Um logische Operationen aufzuzeichnen, können Sie sowohl normale Tastaturzeichen (*, +, !, ^, ->, =), und in der Literatur etablierte Symbole (∧, ∨, ¬, ⊕, →, ≡). Wenn Ihre Tastatur nicht über das gewünschte Operationssymbol hat, verwenden Sie die Tastatur des Taschenrechners (wenn sie nicht sichtbar ist, drücken Sie "Tastatur anzeigen"), wo sowohl alle logischen Operationen als auch eine Reihe der am häufigsten verwendeten Variablen verfügbar sind.

Um die Reihenfolge der Operationen zu ändern, werden runde Klammern verwendet ().

Die Bezeichnungen der logischen Operationen

• AND: & • ∧ *
• OR: ∨ +
• NOT: ¬ !
• Exclusive OR (XOR): ⊕ ^
• Implication: -> → =>
• Equivalence: = ~ ≡ <=>
• Schaeffer stroke: ↑ |
• Pierce Arrow: ↓

Was der Taschenrechner alles kann

• Erstellen Sie eine Wahrheitstabelle der Funktion
• Erstellung einer Wahrheitstabelle durch einen binären Vektor
• Konstruieren Sie eine perfekte konjunktive Normalform (CNF)
• Konstruieren Sie eine perfekte disjunktive Normalform (DNF)
• Konstruktion des Zhegalkin-Polynoms (nach der Pascal-Methode, der Dreiecksmethode und der Methode der undefinierten Koeffizienten)
• Bestimmen, ob eine Funktion zu einer der fünf Post'schen Klassen gehört
• K-Map (Karnaugh Map) erstellen
• CNF und DNF minimieren
• Suche nach fiktiven Variablen

Was ist eine Boolesche Funktion?

Boolesche Funktion f(x1, x2, ... xn) — eine beliebige Funktion von n Variablen ist x₁, x₂, ... x_n, in dem die Argumente einen von zwei Werten annehmen: entweder 0 oder 1, und die Funktion selbst nimmt die Werte 0 oder 1 an. Das heißt, es handelt sich um eine Regel, nach der einer beliebigen Menge von Nullen und Einsen der Wert 0 oder 1 zugewiesen wird. Lesen Sie mehr über Boolesche Funktionen auf Wikipedia.

Was ist eine Wahrheitstabelle?

Wahrheitstabelle — ist eine Tabelle, die eine logische Funktion beschreibt, nämlich alle Werte der Funktion für alle möglichen Werte ihrer Argumente widerspiegeln. Die Tabelle besteht aus n+1 Spalten und 2n Zeilen, wobei n die Anzahl der verwendeten Variablen ist. Die ersten n Spalten enthalten alle möglichen Werte der Argumente (Variablen) der Funktion, und die n+1. Spalte enthält die Werte der Funktion, die sie bei einer bestimmten Menge von Argumenten annimmt.

Häufig gibt es eine Variante der Tabelle, bei der die Anzahl der Spalten gleich n + der Anzahl der logischen Operationen entspricht. In einer solchen Tabelle werden auch die ersten n Spalten mit den Argumenten gefüllt, und die restlichen Spalten werden mit Werten von Unterfunktionen gefüllt, die in den Datensatz der Funktion aufgenommen wurden, was die Berechnung des endgültigen Wertes der Funktion auf Kosten der bereits durchgeführten Zwischenberechnungen zu vereinfachen.

Logische Operationen

Eine logische Operation ist eine Operation auf Anweisungen, die es Ihnen ermöglicht, neue Anweisungen zu erstellen, indem Sie einfacheren Aussagen. Konjunktion (∧ oder &), Disjunktion (∨ oder |) werden gemeinhin als Grundoperationen bezeichnet, Implikation (→), Negation (¬), Äquivalenz (=), exklusives ODER (⊕).

Wahrheitstabelle der logischen Operationen

Wie man eine Logikfunktion einstellt

Es gibt viele Möglichkeiten, eine boolesche Funktion zu spezifizieren:

• Wahrheitstabelle
• charakteristische Mengen
• Wertvektor
• Gray's Matrix
• Formeln

Schauen wir uns einige von ihnen an:

Um eine Funktion durch einen Vektor von Werten zu definieren, muss man einen Vektor von 2ⁿ Nullen und Einsen, wobei n die Anzahl der Argumente ist, von denen die Funktion abhängt. Eine Funktion mit zwei Argumenten kann zum Beispiel wie folgt definiert werden: 0001 (UND-Verknüpfung), 0111 (ODER-Verknüpfung).

Um eine Funktion als Formel zu definieren, müssen Sie einen mathematischen Ausdruck schreiben, der aus Funktionsargumenten und logischen Operationen besteht. Zum Beispiel können wir die folgende Funktion angeben: a∧b ∨ b∧c ∨ a∧c

Möglichkeiten zur Darstellung einer booleschen Funktion

Sie können Formeln verwenden, um eine Vielzahl von Funktionen zu erhalten, und mit verschiedenen Formeln können Sie dieselbe Funktion erhalten. Manchmal kann es sehr nützlich sein, zu wissen, wie man eine bestimmte Funktion konstruiert, indem man nur eine kleine Menge vorgegebener Operationen oder so wenige beliebige Operationen wie möglich verwendet. Schauen wir uns die grundlegenden Möglichkeiten zur Definition boolescher Funktionen an:

• Perfekte disjunktive Normalform (DNF)
• Perfekte konjunktive Normalform (CNF)
• Algebraische Normalform (ANF, Zhegalkin-Polynom)

Disjunktive Normalform (DNF)

Eine einfache Konjunktion ist eine Konjunktion aus einer endlichen Menge von Variablen, oder deren Negationen, wobei jede Variable höchstens einmal vorkommt. Eine disjunktive Normalform (DNF) ist eine Disjunktion von einfachen Konjunktionen. Eine perfekte disjunktive Normalform (DNF) ist eine DNF in Bezug auf eine bestimmte endliche Menge von Variablen, wobei jede Konjunktion alle Variablen dieser Menge einschließt. Ein Beispiel: DNF ist die Funktion ¬abc ∨ ¬a¬bc ∨ ac, ist aber keine disjunktive Normalform, weil in der letzten Konjunktion die Variable b fehlt.

Konjunktionale Normalform (CNF)

Eine einfache Disjunktion ist eine Disjunktion von einer oder mehreren Variablen oder deren Negationen, wobei jede Variable höchstens einmal enthalten ist. Die konjunktive Normalform (CNF) ist eine Konjunktion von einfachen Disjunktionen. Eine perfekte konjunktive Normalform (CNF) ist eine CNF in Bezug auf eine gegebene endliche Menge von Variablen, wobei jede Disjunktion alle Variablen dieser Menge einschließt. Die CNF ist zum Beispiel die Funktion (a ∨ b) ∧ (a ∨ b ∨ c), aber es ist keine SNF, weil in der ersten Disjunktion die Variable c fehlt.

Algebraische Normalform (ANF, Zhegalkin-Polynom)

Die algebraische Normalform, das Zhegalkin-Polynom, ist eine Darstellungsform der logischen Funktion in Form eines Polynoms mit den Koeffizienten 0 und 1, wobei die Konjunktion als Produkt und die exklusive ODER-Operation als Addition verwendet wird. Beispiele für Zhegalkin-Polynome: 1, a, a⊕b, ab⊕a⊕b⊕1

Algorithmus zur Konstruktion einer DNF für eine boolesche Funktion

1. Konstruieren Sie eine Wahrheitstabelle für die Funktion
2. Suche nach allen Mengen von Argumenten, bei denen die Funktion den Wert 1 annimmt
3. Schreiben Sie einfache Konjunktionen für jede der Mengen nach der folgenden Regel: Wenn in einer Menge die Variable den Wert 0 annimmt, geht sie mit Negation in die Konjunktion ein, ansonsten ohne Negation
4. Verbinden Sie alle einfachen Konjunktionen mit einer Disjunktion

Algorithmus der CNF-Konstruktion für eine boolesche Funktion

1. Erstellen Sie eine Wahrheitstabelle für die Funktion
2. Suche nach allen Mengen von Argumenten, bei denen die Funktion den Wert 0 annimmt
3. Schreiben Sie einfache Disjunktionen für jede der Mengen nach der folgenden Regel: Wenn in einer Menge die Variable den Wert 1 annimmt, tritt sie mit Negation in die Disjunktion ein, andernfalls ohne Negation
4. Verbinden Sie alle einfachen Disjunktionen mit einer Konjunktion

Algorithmus zur Konstruktion des Zhegalkin-Polynoms einer booleschen Funktion

Es gibt mehrere Methoden zur Konstruktion des Zhegalkin-Polynoms, in diesem Artikel werden wir die bequemste und einfachste von allen.

1. Konstruieren Sie eine Wahrheitstabelle für die Funktion
2. Fügen Sie der Wahrheitstabelle eine neue Spalte hinzu und schreiben Sie in die Zellen 1, 3, 5... die Werte aus denselben Zeilen der vorherigen Spalte der Wahrheitstabelle, und zu den Werten in den Zeilen 2, 4, 6... addiere modulo zwei Werte aus den entsprechenden Zeilen 1, 3, 5... hinzu.
3. Fügen Sie der Wahrheitstabelle eine neue Spalte hinzu und überschreiben Sie die Werte von 1, 2, 5, 6, 9, 10... Zeilen, und zu 3, 4, 7, 8, 11, 12... Zeilen fügen Sie die überschriebenen Werte in ähnlicher Weise wie im vorherigen Punkt hinzu.
4. Wiederholen Sie dies jedes Mal, indem Sie die Anzahl der übertragenen und hinzugefügten Elemente verdoppeln, bis die Länge der Anzahl der Zeilen in der Tabelle entspricht.
5. Boolesche Mengen ausschreiben, bei denen der Wert der letzten Spalte eins ist
6. Schreiben Sie die Namen der Variablen, die der Menge entsprechen, anstelle der Namen der Variablen in den Mengen (für die Nullmenge schreiben Sie eins) und verknüpfen Sie sie mit der Exklusiv-ODER-Operation.

Beispiele für die Konstruktion verschiedener Darstellungen von logischen Funktionen

Wir konstruieren perfekte disjunktive und disjunktive Normalformen und das Zhegalkin-Polynom für die Funktion von drei Variablen F = ¬ab∨¬bc∨ca

1. Erstellen wir eine Wahrheitstabelle für die Funktion

---

Konstruktion einer perfekten disjunktiven Normalform:

Lassen Sie uns die Mengen finden, auf denen die Funktion einen wahren Wert annimmt: { 0, 0, 1 } { 0, 1, 0 } { 0, 1, 1 } { 1, 0, 1 } { 1, 1, 1 }

Wir wollen die gefundenen Mengen mit elementaren Konjunktionen für alle Variablen vergleichen, und wenn eine Variable in der Menge den Wert 0 annimmt, wird sie mit Negation geschrieben:

K₁: { 0, 0, 1 } — ¬a¬bc
K₂: { 0, 1, 0 } — ¬ab¬c
K₃: { 0, 1, 1 } — ¬abc
K₄: { 1, 0, 1 } — a¬bc
K₅: { 1, 1, 1 } — abc

Kombinieren Sie Konjunktionen mit Hilfe der Disjunktion und erhalten Sie eine perfekte disjunktive Normalform:

---

Konstruktion einer perfekten konjunktiven Normalform:

Finde die Mengen, bei denen die Funktion einen falschen Wert annimmt: { 0, 0, 0 } { 1, 0, 0 } { 1, 1, 0 }

Wir wollen die gefundenen Mengen mit elementaren Disjunktionen für alle Variablen vergleichen, und wenn eine Variable in der Menge den Wert 1 annimmt, wird sie mit Negation geschrieben:

D₁: { 0, 0, 0 } — a∨b∨c
D₂: { 1, 0, 0 } — ¬a∨b∨c
D₃: { 1, 1, 0 } — ¬a∨¬b∨c

Kombinieren Sie Disjunktionen mit Konjunktionen und Sie erhalten eine perfekte konjunktive Normalform:

---

Konstruktion des Zhegalkin-Polynoms:

Fügen Sie der Wahrheitstabelle eine neue Spalte hinzu und schreiben Sie in die Zeilen 1, 3, 5 und 7 die Werte aus denselben Zeilen in die vorherige Spalte der Wahrheitstabelle, und addiere die Werte in den Zeilen 2, 4, 6 und 8 modulo 2 mit den Werten aus den Zeilen 1, 3, 5 und 7 entsprechend:

Fügen Sie der Wahrheitstabelle eine neue Spalte hinzu und schreiben Sie in die Zeilen 1 und 2, 5 und 6 die Werte aus denselben Zeilen der vorherigen Spalte in die Wahrheitstabelle und addiere die Werte in den Zeilen 3 und 4, 7 und 8 modulo 2 mit den Werten aus den Zeilen 1 und 2, 5 und 6 entsprechend:

Fügen Sie der Wahrheitstabelle eine neue Spalte hinzu und schreiben Sie in die Zeilen 1, 2, 3 und 4 die Werte aus denselben Zeilen der vorherigen Spalte der Wahrheitstabelle, und addiere die Werte in den Zeilen 5, 6, 7 und 8 modulo 2 mit den Werten aus entsprechend in die Zeilen 1, 2, 3 und 4:

Das Ergebnis ist die folgende Tabelle:

Schreiben Sie die Mengen aus, bei denen der resultierende Vektor einen Einheitswert annimmt, und schreiben Sie anstelle der Einheiten in den Mengen die Namen der Variablen, die der Menge entsprechen (für die Nullmenge schreiben Sie eins):

{ 0, 0, 1 } — c, { 0, 1, 0 } — b, { 0, 1, 1 } — bc, { 1, 1, 0 } — ab, { 1, 1, 1 } — abc

Kombiniert man diese Konjunktionen mit der Exklusiv-Oder-Operation, erhält man das Zhegalkin-Polynom: c⊕b⊕bc⊕ab⊕abc