Boolesche Funktion ist eine Funktion, bei der Variablen nur zwei Werte annehmen: eine logische Eins oder eine logische Null. Die Wahrheit oder Falschheit komplexer Aussagen ist eine Funktion der Wahrheit oder Falschheit einfacher. Diese Funktion wird als Boolesche Beurteilungsfunktion f (a, b) bezeichnet.

Jede logische Funktion kann mithilfe einer Wahrheitstabelle angegeben werden, auf deren linker Seite eine Reihe von Argumenten und auf der rechten Seite die entsprechenden Werte der logischen Funktion stehen.

Beim Erstellen einer Wahrheitstabelle muss die Reihenfolge berücksichtigt werden, in der logische Operationen ausgeführt werden. Die Operationen in einem booleschen Ausdruck werden von links nach rechts, einschließlich Klammern, in der folgenden Reihenfolge ausgeführt:

• 1. Umkehrung;
• 2. Konjunktion;
• 3. Disjunktion;
• 4. Implikation und Äquivalenz.

Klammern werden verwendet, um die angegebene Reihenfolge logischer Operationen zu ändern.

Folgende Wahrheitstabellen-Algorithmus.

• 1. Bestimmen Anzahl der Sätze von Eingabevariablen- alle möglichen Kombinationen der Werte der in den Ausdrücken enthaltenen Variablen gemäß der Formel: Q=2 n, wobei n die Anzahl der Eingabevariablen ist. Sie gibt die Anzahl der Zeilen in der Tabelle an.
• 2. Tragen Sie alle Sätze von Eingabevariablen in die Tabelle ein.
• 3. Bestimmen Sie die Anzahl der logischen Operationen und die Reihenfolge ihrer Ausführung.
• 4. Füllen Sie die Spalten mit den Ergebnissen der logischen Operationen in der angegebenen Reihenfolge aus.

Um keine mögliche Kombination von Werten von Eingabevariablen zu wiederholen oder zu überspringen, sollte eine der folgenden Möglichkeiten zum Ausfüllen der Tabelle verwendet werden.

Methode 1. Jeder Wertesatz der Eingabevariablen ist ein Zahlencode im binären Zahlensystem, und die Anzahl der Stellen der Zahl ist gleich der Anzahl der Eingabevariablen. Der erste Satz ist die Zahl 0. Wenn wir jedes Mal 1 zur aktuellen Zahl addieren, erhalten wir den nächsten Satz. Der letzte Satz ist der Maximalwert einer Binärzahl für eine gegebene Codelänge.

Beispielsweise besteht bei einer Funktion aus drei Variablen die Folge von Mengen aus Zahlen:

Methode 2. Für eine Funktion mit drei Variablen kann die Datenfolge auf folgende Weise erhalten werden:

• a) Teilen Sie die Wertespalte der ersten Variablen in zwei Hälften und füllen Sie die obere Hälfte mit Nullen, die untere Hälfte mit Einsen;
• b) in der nächsten Spalte für die zweite Variable die Hälfte wieder halbieren und mit Gruppen von Nullen und Einsen auffüllen; ebenso die zweite Hälfte füllen;
• c) tun Sie dies, bis die Gruppen von Nullen und Einsen aus einem Zeichen bestehen.

Methode 3. Verwenden Sie die bekannte Wahrheitstabelle für zwei Argumente. Wenn Sie das dritte Argument hinzufügen, schreiben Sie zuerst die ersten 4 Zeilen der Tabelle, kombinieren Sie sie mit dem Wert des dritten Arguments gleich 0 und schreiben Sie dann die gleichen 4 Zeilen erneut, aber jetzt mit dem Wert des dritten Arguments gleich 1 Als Ergebnis hat die Tabelle für drei Argumente 8 Zeilen:

Lassen Sie uns zum Beispiel eine Wahrheitstabelle für eine logische Funktion erstellen:

Die Anzahl der Eingabevariablen im gegebenen Ausdruck ist drei (ABC). Also die Anzahl der Eingabesätze Q=2 3 =8 .

Die Spalten der Wahrheitstabelle entsprechen den Werten der ursprünglichen Ausdrücke ABC, Zwischenergebnisse und ( B v C) sowie der gewünschte Endwert eines komplexen arithmetischen Ausdrucks:

• 0 0 0 1 0 0
• 0 0 1 1 1 1
• 0 1 0 1 1 1
• 0 1 1 1 1 1
• 1 0 0 0 0 0
• 1 0 1 0 1 0
• 1 1 0 0 1 0
• 1 1 1 0 1 0
• 7.4. Logische Funktionen und ihre Transformationen. Gesetze der Logik

Für die Operationen Konjunktion, Disjunktion und Inversion sind die Gesetze der Booleschen Algebra definiert, die es einem ermöglichen, sie auszuführen identische (äquivalente) Transformationen logischer Ausdrücke.

Gesetze der Logik

• 1. ¬¬ A
• 2.A&B
• 3. AVB
• 4.A&(B&C)
• 5.AV(BVC)
• 6. A&(BVC)
• 7. AV (B&C)
• 8.A&A
• 9. Ava
• 10. AV-A
• 11. A&¬A
• 12. KI
• 13. AVI
• 14. A&L
• 15. AVL
• 16. ¬(A&B)
• 17. ¬(AVB)
• 18. A => B

Basierend auf den Gesetzen können Sie komplexe logische Ausdrücke vereinfachen. Dieser Vorgang des Ersetzens einer komplexen Logikfunktion durch eine einfachere, aber äquivalente Funktion wird als Funktionsminimierung bezeichnet.

Beispiel 1 Vereinfachen Sie die Ausdrücke, sodass die resultierenden Formeln keine Negation komplexer Aussagen enthalten.

Lösung

Beispiel 2 Funktion minimieren

Zur Vereinfachung des Ausdrucks wurden die Absorptions- und Klebeformeln verwendet.

Beispiel 3 Finden Sie die Negation der folgenden Aussage: "Wenn der Unterricht interessant ist, wird keiner der Schüler (Misha, Vika, Sveta) aus dem Fenster schauen."

Lösung

Nennen wir die Aussagen:

Y- "Der Unterricht ist interessant";

M- "Misha schaut aus dem Fenster";

B- "Vika schaut aus dem Fenster";

C- "Sveta schaut aus dem Fenster."

Bei der Vereinfachung des Ausdrucks wurden die Formel zum Ersetzen von Operationen und das Gesetz von de Morgan verwendet.

Beispiel 4 Bestimmen Sie den Teilnehmer an der Straftat, basierend auf zwei Prämissen: logischer Rechner Tisch

• 1) "Wenn Ivanov nicht teilgenommen hat oder Petrov teilgenommen hat, dann hat Sidorov teilgenommen";
• 2) "Wenn Ivanov nicht teilgenommen hat, hat Sidorov nicht teilgenommen."

Lösung

Machen wir Ausdrücke:

ich- "Iwanow hat an dem Verbrechen teilgenommen";

P- "Petrow hat an dem Verbrechen teilgenommen";

S- "Sidorov war an dem Verbrechen beteiligt."

Wir schreiben die Pakete in Form von Formeln:

Überprüfen wir das Ergebnis anhand der Wahrheitstabelle:

Antworten: Ivanov beteiligte sich an dem Verbrechen.

Aufbau einer logischen Funktion aus ihrer Wahrheitstabelle

Wir haben gelernt, wie man eine Wahrheitstabelle für eine logische Funktion erstellt. Versuchen wir, das umgekehrte Problem zu lösen.

Betrachten Sie Zeilen, in denen der Wahrheitswert der Z-Funktion wahr ist (Z=1). Die Funktion für diese Wahrheitstabelle kann wie folgt geschrieben werden: Z(X,Y) = (¬X& ¬Y)V(X& ¬Y).

Jede Zeile, in der die Funktion wahr ist (gleich 1), entspricht einer Klammer, die eine Konjunktion von Argumenten ist, und wenn der Wert des Arguments 0 ist, nehmen wir ihn mit einer Negation. Alle Klammern sind durch die Disjunktionsoperation miteinander verbunden. Die resultierende Formel kann vereinfacht werden, indem man die Gesetze der Logik anwendet:

Z(X,Y)<=>((¬X& ¬Y) VX)&((¬X&Y)V ¬Y)<=>(XV(¬X& ¬Y)) &(¬YV(¬X&¬Y))<=>((XV¬X)&(XV ¬Y))&((Y¬V ¬X)&(¬YV ¬Y))<=>(1&(XV ¬Y))&((¬YV ¬X)& ¬Y)<=>(XV ¬Y)&((¬YV ¬X)& ¬Y).

Überprüfen Sie die resultierende Formel: Erstellen Sie eine Wahrheitstabelle für die Funktion Z(X,Y).

Schreiben Sie die Regeln zur Konstruktion einer logischen Funktion gemäß ihrer Wahrheitstabelle auf:

• 1. Wählen Sie in der Wahrheitstabelle diejenigen Zeilen aus, in denen der Wert der Funktion 1 ist.
• 2. Schreiben Sie die gewünschte Formel als Disjunktion mehrerer logischer Elemente. Die Anzahl dieser Elemente ist gleich der Anzahl der ausgewählten Zeilen.
• 3. Schreiben Sie jedes logische Element in dieser Disjunktion als Konjunktion von Funktionsargumenten.
• 4. Wenn der Wert eines Funktionsarguments in der entsprechenden Zeile der Tabelle 0 ist, nehmen wir dieses Argument mit einer Negation.

Bestimmung 1

Boolesche Funktion ist eine Funktion, deren Variablen einen von zwei Werten annehmen: $1$ oder $0$.

Jede logische Funktion kann mithilfe einer Wahrheitstabelle angegeben werden: Die Menge aller möglichen Argumente wird auf die linke Seite der Tabelle geschrieben, und die entsprechenden Werte der logischen Funktion stehen auf der rechten Seite.

Bestimmung 2

Wahrheitstabelle- eine Tabelle, die zeigt, welche Werte der zusammengesetzte Ausdruck für alle annehmen wird mögliche Sets Werte der darin enthaltenen einfachen Ausdrücke.

Bestimmung 3

Äquivalent werden logische Ausdrücke genannt, deren letzte Spalten der Wahrheitstafeln übereinstimmen. Äquivalenz wird durch das Zeichen $"="$ angezeigt.

Beim Erstellen einer Wahrheitstabelle ist es wichtig, die folgende Reihenfolge der Ausführung logischer Operationen zu berücksichtigen:

Bild 1.

Klammern haben Vorrang in der Ausführungsreihenfolge von Operationen.

Algorithmus zum Erstellen der Wahrheitstabelle einer logischen Funktion

Bestimmen Sie die Anzahl der Zeilen: anzahl der Zeilen= $2^n + 1$ (für Titelleiste), $n$ ist die Anzahl der einfachen Ausdrücke. Zum Beispiel gibt es für Funktionen von zwei Variablen $2^2 = 4$ Kombinationen von Sätzen von Variablenwerten, für Funktionen von drei Variablen gibt es $2^3 = 8$ und so weiter.

Bestimmen Sie die Anzahl der Spalten: Anzahl der Spalten = Anzahl der Variablen + Anzahl der logischen Operationen. Bei der Bestimmung der Anzahl der logischen Operationen wird auch die Reihenfolge ihrer Ausführung berücksichtigt.

Füllen Sie die Spalten mit den Ergebnissen der Ausführung logischer Operationen in einer bestimmten Reihenfolge unter Berücksichtigung der Wahrheitstabellen der logischen Grundoperationen.

Figur 2.

Beispiel 1

Erstellen Sie eine Wahrheitstabelle des logischen Ausdrucks $D=\bar(A) \vee (B \vee C)$.

Lösung:

Lassen Sie uns die Anzahl der Zeilen bestimmen:

Zeilenanzahl = $2^3 + 1=9$.

Die Anzahl der Variablen beträgt $3$.

1. invertieren ($\bar(A)$);
2. Disjunktion, weil es steht in Klammern ($B \vee C$);

3. Disjunktion ($\overline(A)\vee \left(B\vee C\right)$) ist der erforderliche logische Ausdruck.

   Anzahl der Spalten = $3 + 3=6$.

Lassen Sie uns die Tabelle unter Berücksichtigung der Wahrheitstabellen logischer Operationen ausfüllen.

Figur 3

Beispiel 2

Erstellen Sie basierend auf dem gegebenen logischen Ausdruck eine Wahrheitstabelle:

Lösung:

Lassen Sie uns die Anzahl der Zeilen bestimmen:

Die Anzahl einfacher Ausdrücke ist also $n=3$

anzahl der Zeilen = $2^3 + 1=9$.

Lassen Sie uns die Anzahl der Spalten definieren:

Die Anzahl der Variablen beträgt $3$.

Die Anzahl der logischen Operationen und ihre Reihenfolge:

1. Negation ($\bar(C)$);
2. Disjunktion, weil es steht in Klammern ($A \vee B$);
3. Konjunktion ($(A\vee B)\bigwedge \overline(C)$);
4. Negation, die wir mit $F_1$ ($\overline((A\vee B)\bigwedge \overline(C))$) bezeichnen;
5. Disjunktion ($A \vee C$);
6. Konjunktion ($(A\vee C)\bigwedge B$);
7. Negation, die wir mit $F_2$ ($\overline((A\vee C)\bigwedge B)$) bezeichnen;

8. Disjunktion ist die gewünschte logische Funktion ($\overline((A\vee B)\bigwedge \overline(C))\vee \overline((A\vee C)\bigwedge B)$).

Basierend auf: Demo USE-Optionen in Informatik für 2015, nach dem Lehrbuch von Lyudmila Leonidovna Bosova

Im vorherigen Teil 1 haben wir mit Ihnen die logischen Operationen Disjunktion und Konjunktion analysiert, es bleibt uns, die Inversion zu analysieren und mit der Lösung der USE-Aufgabe fortzufahren.

Umkehrung

Umkehrung- eine logische Operation, die jeder Aussage eine neue Aussage zuordnet, deren Bedeutung der ursprünglichen entgegengesetzt ist.

Die folgenden Zeichen werden verwendet, um Inversion zu schreiben: NOT, `¯` , ` ¬ `

Die Inversion wird durch die folgende Wahrheitstabelle definiert:

Inversion ist auch als logische Negation bekannt.

Jede komplexe Aussage kann geschrieben werden als Boolescher Ausdruck- ein Ausdruck, der logische Variablen, Zeichen logischer Operationen und Klammern enthält. Logische Operationen in einem logischen Ausdruck werden in der folgenden Reihenfolge ausgeführt: Inversion, Konjunktion, Disjunktion. Sie können die Reihenfolge ändern, in der Operationen ausgeführt werden, indem Sie Klammern setzen.

Logische Operationen haben folgende Priorität: Inversion, Konjunktion, Disjunktion.

Damit haben wir Aufgabe Nummer 2 aus der Einheitlichen Staatsprüfung Informatik 2015

Alexandra füllte die Wahrheitstabelle für den Ausdruck F aus. Sie schaffte es, nur ein kleines Fragment der Tabelle auszufüllen:

x1	x2	x3	x4	x5	x6	x7	x8	F
	0						1	0
1			0					1
			1				1	1

Welcher Ausdruck kann F sein?

Es erleichtert die Lösung der Aufgabe sehr, dass es in jeder Variante des komplexen Ausdrucks F nur eine logische Operation gibt: Multiplikation oder Addition. Bei Multiplikation /\ wenn mindestens eine Variable gleich Null ist, dann muss auch der Wert des gesamten Ausdrucks F gleich Null sein. Und im Fall des Zusatzes V muss, wenn mindestens eine Variable gleich eins ist, der Wert des gesamten Ausdrucks F gleich 1 sein.

Die Daten, die in der Tabelle für jede der 8 Variablen des Ausdrucks F stehen, reichen völlig aus, um sie zu lösen.

Lassen Sie uns Ausdruck Nummer 1 überprüfen:

• ? /\ 1 /\ ? /\ ? /\ ? /\ ? /\ ? /\ 0 )
• in der zweiten Zeile der Tabelle x1=1, x4=0 sehen wir, dass F möglich ist und gleich = 1 sein kann, wenn alle anderen Variablen gleich 1 sind (1 /\ ? /\ ? /\ 1 /\ ? /\ ? /\ ? /\ ? )
• gemäß der dritten Zeile der Tabelle x4=1, x8=1 sehen wir, dass F=0 (? /\ ? /\ ? /\ 0 /\ ? /\ ? /\ ? /\ 0 ), und in der Tabelle haben wir F=1, und das bedeutet, dass der Ausdruck an Nummer eins wir DEFINITIV NICHT GEEIGNET.

Lassen Sie uns Ausdruck Nummer 2 überprüfen:

• Anhand der ersten Zeile der Tabelle x2=0, x8=1 können wir sehen, dass F möglich ist und gleich = 0 sein kann, wenn alle anderen Variablen gleich 0 sind (? v 0 v ? v ? v ? v ? v ? v 0 )
• in der zweiten Zeile der Tabelle x1=1, x4=0 sehen wir, dass F = 1 ( 1 v ? v ? v 1 v ? v ? v ? v ? )
• Aus der dritten Zeile der Tabelle x4=1, x8=1 können wir ersehen, dass F möglich ist und gleich = 1 sein kann, wenn mindestens eine der verbleibenden Variablen gleich 1 ist ( ? v ? v ? v 0 v ? v ? v ? v 0 )
  

Lassen Sie uns Ausdruck Nummer 3 überprüfen:

• In der ersten Zeile der Tabelle x2=0, x8=1 sehen wir, dass F=0 (? /\ 0 /\ ? /\ ? /\ ? /\ ? /\ ? /\ 1 )
• in der zweiten Zeile der Tabelle x1=1, x4=0 sehen wir, dass F =0 (0 /\ ? /\ ? /\ 0 /\ ? /\ ? /\ ? /\ ? ), und in der Tabelle haben wir F=1, und das bedeutet, dass der Ausdruck bei Nummer drei wir DEFINITIV NICHT GEEIGNET.

Lassen Sie uns Ausdruck Nummer 4 überprüfen:

• in der ersten Zeile der Tabelle x2=0, x8=1 sehen wir, dass F=1 ( ? v 1 v ? v ? v ? v ? v ? v 0 ), und in der Tabelle haben wir F=0, und das bedeutet, dass der Ausdruck Nummer vier für uns ist DEFINITIV NICHT GEEIGNET.

Wenn Sie eine Aufgabe bei einem einheitlichen Staatsexamen lösen, müssen Sie genau dasselbe tun: Verwerfen Sie die Optionen, die gemäß den Daten in der Tabelle nicht genau passen. Verblieben mögliche Variante(wie in unserem Fall Option Nummer 2) und wird die richtige Antwort sein.

In digitalen Schaltungen Digitalsignal ist ein Signal, das zwei Werte annehmen kann, die als eine logische "1" und eine logische "0" betrachtet werden.

Logikschaltungen können bis zu 100 Millionen Eingänge enthalten, und es gibt solche riesigen Schaltungen. Stellen Sie sich vor, dass die Boolesche Funktion (Gleichung) einer solchen Schaltung verloren gegangen ist. Wie kann ich es mit dem geringsten Zeitverlust und ohne Fehler wiederherstellen? Am produktivsten ist es, das Schema in Ebenen aufzuteilen. Bei dieser Methode wird die Ausgabefunktion jedes Elements in der vorherigen Ebene geschrieben und durch die entsprechende Eingabe in der nächsten Ebene ersetzt. Wir werden diese Methode zur Analyse von Logikschaltungen heute mit allen Nuancen betrachten.

Logikschaltungen werden auf logischen Elementen implementiert: "NOT", "AND", "OR", "AND-NOT", "OR-NOT", "XOR" und "Equivalence". Mit den ersten drei logischen Elementen können Sie jede beliebig komplexe logische Funktion auf boolescher Basis implementieren. Wir werden Probleme für Logikschaltungen lösen, die auf Boolescher Basis implementiert sind.

Mehrere Standards werden verwendet, um Logikelemente zu bezeichnen. Am gebräuchlichsten sind amerikanische (ANSI), europäische (DIN), internationale (IEC) und russische (GOST). Die folgende Abbildung zeigt die Bezeichnungen logischer Elemente in diesen Standards (zum Vergrößern können Sie mit der linken Maustaste auf das Bild klicken).

In dieser Lektion lösen wir Probleme für Logikschaltungen, in denen Logikelemente im GOST-Standard bezeichnet werden.

Es gibt zwei Arten von Aufgaben für Logikschaltungen: das Problem der Synthese von Logikschaltungen und das Problem der Analyse von Logikschaltungen. Wir beginnen mit dem zweiten Problemtyp, da es in dieser Reihenfolge möglich ist, schnell zu lernen, wie man Logikdiagramme liest.

Am häufigsten werden im Zusammenhang mit dem Aufbau logischer Schaltungen die Funktionen der Algebra der Logik betrachtet:

• drei Variablen (die bei den Problemen der Analyse und bei einem Problem der Synthese zu berücksichtigen sind);
• vier Variablen (bei Syntheseproblemen, also in den letzten beiden Absätzen).

Betrachten Sie die Konstruktion (Synthese) von logischen Schaltungen

• in der booleschen Basis „AND“, „OR“, „NOT“ (im vorletzten Absatz);
• in den ebenfalls gebräuchlichen Grundlagen „UND-NICHT“ und „ODER-NICHT“ (im letzten Absatz).

Die Aufgabe, Logikschaltungen zu analysieren

Die Aufgabe der Analyse besteht darin, die Funktion zu bestimmen f implementiert durch eine gegebene Logikschaltung. Bei der Lösung eines solchen Problems ist es zweckmäßig, die folgende Abfolge von Aktionen zu befolgen.

1. Das logische Schema ist in Ebenen unterteilt. Ebenen werden fortlaufende Nummern zugewiesen.
2. Die Ausgänge jedes logischen Elements werden durch den Namen der gewünschten Funktion angezeigt, der mit einem digitalen Index versehen ist, wobei die erste Ziffer die Ebenennummer ist und die verbleibenden Ziffern die Ordnungszahl des Elements in der Ebene sind.
3. Für jedes Element wird ein analytischer Ausdruck geschrieben, der seine Ausgabefunktion mit den Eingabevariablen in Beziehung setzt. Der Ausdruck wird durch die logische Funktion definiert, die durch das gegebene logische Element implementiert wird.
4. Die Substitution einiger Ausgabefunktionen durch andere wird durchgeführt, bis eine boolesche Funktion erhalten wird, die durch Eingabevariablen ausgedrückt wird.

Beispiel 1

Lösung. Wir teilen die Logikschaltung in Ebenen auf, was bereits in der Abbildung dargestellt ist. Schreiben wir alle Funktionen auf, beginnend mit der 1. Ebene:

x, j, z :

x	j	z					f
1	1	1	0	1	1	1	1
1	1	0	0	0	0	1	0
1	0	1	0	0	0	1	0
1	0	0	0	0	0	1	0
0	1	1	0	0	0	1	0
0	1	0	0	0	0	1	0
0	0	1	0	0	0	1	0
0	0	0	1	0	1	0	0

Beispiel 2 Finden Sie die boolesche Funktion der Logikschaltung und erstellen Sie eine Wahrheitstabelle für die Logikschaltung.

Beispiel 3 Finden Sie die boolesche Funktion der Logikschaltung und erstellen Sie eine Wahrheitstabelle für die Logikschaltung.

Wir suchen gemeinsam weiter nach der boolschen Funktion der Logikschaltung

Beispiel 4 Finden Sie die boolesche Funktion der Logikschaltung und erstellen Sie eine Wahrheitstabelle für die Logikschaltung.

Lösung. Wir unterteilen die Logikschaltung in Stufen. Schreiben wir alle Funktionen auf, beginnend mit der 1. Ebene:

Lassen Sie uns nun alle Funktionen schreiben und die Eingabevariablen ersetzen x, j, z :

Als Ergebnis erhalten wir die Funktion, die die Logikschaltung am Ausgang umsetzt:

.

Wahrheitstabelle für eine gegebene Logikschaltung:

x	j	z			f
1	1	1	0	1	1
1	1	0	0	1	1
1	0	1	1	0	1
1	0	0	0	0	0
0	1	1	0	1	1
0	1	0	0	1	1
0	0	1	0	1	1
0	0	0	0	1	1

Beispiel 5 Finden Sie die boolesche Funktion der Logikschaltung und erstellen Sie eine Wahrheitstabelle für die Logikschaltung.

Lösung. Wir unterteilen die Logikschaltung in Ebenen. Die Struktur dieser Logikschaltung hat im Gegensatz zu den vorherigen Beispielen 5 Ebenen, nicht 4. Aber eine Eingangsvariable – die niedrigste – durchläuft alle Ebenen und geht direkt in das Logikelement in der ersten Ebene ein. Schreiben wir alle Funktionen auf, beginnend mit der 1. Ebene:

Lassen Sie uns nun alle Funktionen schreiben und die Eingabevariablen ersetzen x, j, z :

Als Ergebnis erhalten wir die Funktion, die die Logikschaltung am Ausgang umsetzt:

.

Wahrheitstabelle für eine gegebene Logikschaltung:

x	j	z			f
1	1	1	1	1	1
1	1	0	1	1	1
1	0	1	1	0	1
1	0	0	1	0	1
0	1	1	1	1	1
0	1	0	1	1	1
0	0	1	1	0	1
0	0	0	1	0	1

Das Problem der Synthese von Logikschaltungen auf Boolescher Basis

Die Entwicklung eines logischen Schaltkreises gemäß seiner analytischen Beschreibung wird als Problem der Synthese eines logischen Schaltkreises bezeichnet.

Jede Disjunktion (logische Summe) entspricht dem "ODER"-Element, dessen Anzahl von Eingaben durch die Anzahl von Variablen in der Disjunktion bestimmt wird. Jede Konjunktion (logisches Produkt) entspricht dem "UND"-Element, dessen Anzahl von Eingängen durch die Anzahl von Variablen in der Konjunktion bestimmt wird. Jede Negation (Invertierung) entspricht dem Element "NOT".

Häufig beginnt der Entwurf einer Logikschaltung mit der Definition einer Logikfunktion, die die Logikschaltung implementieren muss. In diesem Fall ist nur die Wahrheitstabelle der Logikschaltung angegeben. Wir werden genau ein solches Beispiel analysieren, das heißt, wir werden ein Problem lösen, das dem oben betrachteten Problem der Analyse logischer Schaltungen völlig entgegengesetzt ist.

Beispiel 6 Konstruieren Sie eine Logikschaltung, die eine Funktion mit einer gegebenen Wahrheitstabelle implementiert.

Algebra der Logik

Algebra der Logik

Algebra der Logik(Englisch) Algebra der Logik) ist einer der Hauptzweige der mathematischen Logik, in der die Methoden der Algebra in logischen Transformationen verwendet werden.

Begründer der Algebra der Logik ist der englische Mathematiker und Logiker J. Boole (1815-1864), der seine logische Lehre auf der Analogie zwischen Algebra und Logik begründete. Er schrieb jede Aussage mit den Symbolen der von ihm entwickelten Sprache auf und erhielt „Gleichungen“, deren Wahrheit oder Falschheit anhand bestimmter logischer Gesetze, wie der Gesetze der Kommutativität, Distributivität, Assoziativität usw., bewiesen werden konnte.

Modern Algebra der Logik ist ein Teilgebiet der mathematischen Logik und untersucht logische Operationen auf Aussagen unter dem Gesichtspunkt ihres Wahrheitswertes (wahr, falsch). Aussagen können wahr oder falsch sein oder Wahrheit und Falschheit in unterschiedlichen Anteilen enthalten.

logische aussage ist jeder Aussagesatz, bei dem eindeutig festgestellt werden kann, ob sein Inhalt wahr oder falsch ist.

Zum Beispiel sind „3 mal 3 gleich 9“, „Archangelsk nördlich von Wologda“ wahre Aussagen und „Fünf ist weniger als drei“, „Mars ist ein Stern“ sind falsch.

Offensichtlich kann nicht jeder Satz eine logische Aussage sein, da es nicht immer sinnvoll ist, über seine Falschheit oder Wahrheit zu sprechen. Beispielsweise ist die Aussage „Informatik ist ein interessantes Fach“ vage und erfordert zusätzliche Information, und die Aussage „Für einen Schüler der 10. Klasse A. A. Ivanov ist Informatik ein interessantes Fach“, kann je nach Interesse von A. A. Ivanov den Wert „wahr“ oder „falsch“ annehmen.

Außer zweiwertige Aussagenalgebra, in dem nur zwei Werte akzeptiert werden - "true" und "false", gibt es mehrwertige Aussagenalgebra. In einer solchen Algebra werden neben den Bedeutungen „wahr“ und „falsch“ solche Wahrheitswerte wie „wahrscheinlich“, „möglich“, „unmöglich“ usw. verwendet.

In der Algebra unterscheiden sich die Logiken einfach(Grundstufe) Aussagen, bezeichnet mit lateinischen Buchstaben (A, B, C, D, ...) und Komplex(zusammengesetzt), zusammengesetzt aus mehreren einfachen, die logische Verknüpfungen verwenden, zum Beispiel wie „nicht“, „und“, „oder“, „wenn und nur dann“, „wenn ... dann“. Die Wahrheit oder Falschheit der so erhaltenen komplexen Aussagen wird durch die Bedeutung der einfachen Aussagen bestimmt.

Bezeichne als ABER die Aussage "Die Algebra der Logik wurde erfolgreich in der Theorie elektrischer Schaltungen angewendet" und durch BEI- "Die Algebra der Logik wird bei der Synthese von Relaiskontaktschaltungen verwendet."

Dann die zusammengesetzte Aussage „Die Algebra der Logik wird in der Theorie erfolgreich angewendet Stromkreise und in der Synthese von Relais-Kontakt-Schaltungen "kann kurz geschrieben werden als A und B; hier ist „und“ eine logische Verknüpfung. Offensichtlich seit den elementaren Sätzen A und B wahr sind, dann ist auch die zusammengesetzte Aussage wahr A und B.

Jede logische Verknüpfung wird als Operation auf logische Anweisungen betrachtet und hat ihren eigenen Namen und ihre eigene Bezeichnung.

Es gibt nur zwei logische Werte: Stimmt und falsch (FALSCH). Dies entspricht der digitalen Darstellung − 1 und 0 . Die Ergebnisse jeder logischen Operation können in Form einer Tabelle festgehalten werden. Solche Tabellen werden Wahrheitstabellen genannt.

Grundoperationen der logischen Algebra

1. Logische Negation, Umkehrung(lat. Umkehrung- Umkehrung) - eine logische Operation, durch die aus einer gegebenen Aussage (z. B. A) ( kein), Was heisst Negation der ursprünglichen Aussage, symbolisch gekennzeichnet durch einen Überstrich ($A↖(-)$) oder durch Konventionen wie z ¬, "nicht", und lautet: „nicht A“, „A ist falsch“, „es ist nicht wahr, dass A“, „Negation von A“. Zum Beispiel „Mars ist ein Planet im Sonnensystem“ (Aussage A); "Mars ist kein Planet im Sonnensystem" ($A↖(-)$); der Satz „10 ist eine Primzahl“ (Satz B) ist falsch; der Satz „10 ist keine Primzahl“ (Satz B) ist wahr.

Eine Operation, die in Bezug auf eine Größe verwendet wird, wird aufgerufen einstellig. Die Wertetabelle für diese Operation hat die Form

$A↖(-)$ ist falsch, wenn A wahr ist, und wahr, wenn A falsch ist.

Geometrisch lässt sich die Negation wie folgt darstellen: Wenn A eine bestimmte Menge von Punkten ist, dann ist $A↖(-)$ das Komplement der Menge A, also aller Punkte, die nicht zur Menge A gehören.

2.Verbindung(lat. Konjunktion- Verbindung) - logische Multiplikation, eine Operation, die mindestens zwei logische Werte (Operanden) erfordert und zwei oder mehr Anweisungen mit einem Bündel verbindet "und"(zum Beispiel, "A und B"), die symbolisch mit dem Zeichen ∧ (A ∧ B) bezeichnet wird und lautet: „A und B“. Die folgenden Zeichen werden auch verwendet, um Konjunktionen anzuzeigen: A ∙ B; A & B, A und B, und manchmal wird kein Zeichen zwischen Anweisungen gesetzt: AB. Beispiel für logische Multiplikation: "Dieses Dreieck ist gleichschenklig und rechtwinklig." Dieser Satz kann nur wahr sein, wenn beide Bedingungen erfüllt sind, andernfalls ist der Satz falsch.

EIN	B	A∧B
1	0	0
0	1	0
0	0	0
1	1	1

Aussage ABER ∧ BEI nur wahr, wenn beide Aussagen zutreffen ABER und BEI WAHR.

Geometrisch lässt sich die Konjunktion wie folgt darstellen: if A, B ABER ∧ BEI Es gibt eine Schnittmenge von Mengen ABER und BEI.

3. Disjunktion(lat. Disjunktion- Division) - logische Addition, eine Operation, die zwei oder mehr Anweisungen mit einem Bündel verbindet "oder"(zum Beispiel, "A oder B"), was symbolisch mit dem Zeichen ∨ bezeichnet wird (ABER∨ BEI) und lautet: "A oder B". Die folgenden Zeichen werden auch verwendet, um eine Disjunktion anzuzeigen: A+B; A oder B; Ein | B. Beispiel für eine logische Addition: "Die Zahl x ist durch 3 oder 5 teilbar." Dieser Satz ist wahr, wenn beide Bedingungen oder mindestens eine der Bedingungen erfüllt sind.

Die Wahrheitstabelle der Operation hat die Form

EIN	B	EIN ∨ B
1	0	1
0	1	1
0	0	0
1	1	1

Aussage ABER∨ BEI ist nur dann falsch, wenn beide Aussagen falsch sind ABER und BEI FALSCH.

Geometrisch kann die logische Addition wie folgt dargestellt werden: if A, B sind dann einige Sätze von Punkten ABER ∨ BEI ist die Vereinigung von Mengen ABER und BEI, d. h. eine Figur, die sowohl ein Quadrat als auch einen Kreis kombiniert.

4. Strikte Disjunktion Disjunktion, Modulo-Zwei-Addition- eine logische Operation, die zwei Anweisungen mit einem Konnektor verbindet "oder", im ausschließlichen Sinne verwendet, was symbolisch mit den Zeichen ∨ ∨ oder ⊕ ( ABER ∨ ∨ B, A ⊕ BEI) und lautet: "Entweder a oder B". Ein Beispiel für eine Modulo-Zwei-Addition ist die Aussage „Dieses Dreieck ist stumpf oder spitz“. Die Aussage ist wahr, wenn eine der Bedingungen erfüllt ist.

Die Wahrheitstabelle der Operation hat die Form

ABER	BEI	ABER⊕ B
1	0	1
0	1	1
0	0	0
1	1	0

Der Satz A ⊕ B ist nur wahr, wenn die Sätze A und B unterschiedliche Bedeutungen haben.

5. Implikation(lat. implizit- Ich verbinde mich fest) - eine logische Operation, die zwei Anweisungen mit einem Bündel verbindet "wenn, dann" in eine komplexe Aussage, die symbolisch durch das Zeichen → ( ABER → BEI) und lautet: "wenn A, dann B", "A impliziert B", "aus A folgt B", "A impliziert B". Das Zeichen ⊃ (A ⊃ B) wird auch verwendet, um die Implikation zu bezeichnen. Ein Beispiel für die Implikation: "Wenn das resultierende Viereck ein Quadrat ist, dann kann ein Kreis darum herum umschrieben werden." Diese Operation verbindet zwei einfache logische Ausdrücke, von denen der erste eine Bedingung und der zweite eine Konsequenz ist. Das Ergebnis einer Operation ist nur dann falsch, wenn die Prämisse wahr und die Konsequenz falsch ist. Beispiel: „Wenn 3 * 3 = 9 (A), dann ist die Sonne ein Planet (B)“, ist das Ergebnis der Implikation A → B falsch.

Die Wahrheitstabelle der Operation hat die Form

ABER	BEI	ABER→BEI
1	0	0
0	1	1
0	0	1
1	1	1

Für die Operation der Implikation gilt die Behauptung, dass aus einer Lüge alles folgen kann, aus einer Wahrheit aber nur Wahrheit.

6. Äquivalenz, doppelte Implikation, Äquivalenz(lat. gleich- gleich und Valentinstag- gültig) - eine logische Operation, die zwei Anweisungen zulässt ABER und BEI eine neue Aussage bekommen A ≡ B was lautet: "A ist gleich B". Die folgenden Zeichen werden auch verwendet, um Äquivalenz anzuzeigen: ⇔, ∼. Diese Operation kann durch Bindewörter ausgedrückt werden „wenn und nur dann“, „erforderlich und ausreichend“, „gleichwertig“. Ein Beispiel für Äquivalenz ist die Aussage: "Ein Dreieck ist genau dann rechtwinklig, wenn einer der Winkel gleich 90 Grad ist."

Die Wahrheitstabelle der Äquivalenzoperation hat die Form

ABER	BEI	ABER∼ BEI
1	0	0
0	1	0
0	0	1
1	1	1

Die Äquivalenzoperation ist das Gegenteil der Modulo-2-Addition und wird nur dann als wahr ausgewertet, wenn die Werte der Variablen gleich sind.

Wenn man die Bedeutung einfacher Aussagen kennt, ist es möglich, die Bedeutung komplexer Aussagen anhand von Wahrheitstabellen zu bestimmen. Gleichzeitig ist es wichtig zu wissen, dass drei Operationen ausreichen, um jede Funktion der Algebra der Logik darzustellen: Konjunktion, Disjunktion und Negation.

Die Priorität logischer Operationen ist wie folgt: Negation ( "nicht") hat den höchsten Vorrang, dann die Konjunktion ( "und"), nach Konjunktion – Disjunktion ( "oder").

Mit Hilfe von logischen Variablen und logischen Operationen kann jede logische Aussage formalisiert, also durch eine logische Formel ersetzt werden. Gleichzeitig können Elementaraussagen, die eine zusammengesetzte Aussage bilden, absolut bedeutungslos sein, aber dies hindert einen nicht daran, die Wahrheit oder Falschheit einer zusammengesetzten Aussage zu bestimmen. Zum Beispiel die Aussage „Wenn fünf größer als zwei ist ( ABER), dann kommt Dienstag immer nach Montag ( BEI)" - Implikation ABER→ BEI, und das Ergebnis der Operation ist in diesem Fall "true". Bei logischen Operationen wird die Bedeutung von Aussagen nicht berücksichtigt, sondern nur deren Wahrheit oder Falschheit berücksichtigt.

Betrachten Sie zum Beispiel die Konstruktion einer zusammengesetzten Anweisung aus Anweisungen ABER und BEI, was genau dann falsch wäre, wenn beide Aussagen wahr sind. In der Wahrheitstabelle für die Operation der Modulo-Zwei-Addition finden wir: 1 ⊕ 1 = 0. Und die Aussage kann zum Beispiel lauten: „Dieser Ball ist ganz rot oder ganz blau.“ Daher, wenn die Aussage ABER„Dieser Ball ist komplett rot“ ist eine wahre Aussage BEI„Dieser Ball ist komplett blau“ ist wahr, dann ist die zusammengesetzte Aussage falsch, da der Ball nicht gleichzeitig rot und blau sein kann.

Beispiele für Problemlösungen

Beispiel 1 Bestimmen Sie für die angegebenen Werte von X den Wert der logischen Aussage ((X > 3) ∨ (X< 3)) → (X < 4) :

1) X = 1; 2) X = 12; 3) X = 3.

Lösung. Die Reihenfolge der Operationen ist wie folgt: Zuerst werden die Vergleichsoperationen in Klammern durchgeführt, dann die Disjunktion und die letzte Implikationsoperation wird durchgeführt. Der Disjunktionsoperator ∨ ​​​​ist genau dann falsch, wenn beide Operanden falsch sind. Die Wahrheitstabelle für die Implikation ist

EIN	B	A→B
1	0	0
0	1	1
0	0	1
1	1	1

Von hier erhalten wir:

1) für X = 1:

((1 > 3) ∨ (1 < 3)) → (1 < 4) = ложь ∨ истина → истина = истина → истина = истина;

2) für X = 12:

((12 > 3) ∨ (12 < 3) → (12 < 4) = истина ∨ ложь → ложь = истина → ложь = ложь;

3) für X = 3:

((3 > 3) ∨ (3 < 3)) → (3<4) = ложь ∨ ложь → истина = ложь → истина = истина.

Beispiel 2 Geben Sie die Menge der ganzzahligen Werte X an, für die der Ausdruck ¬((X > 2) → (X > 5)) wahr ist.

Lösung. Die Negationsoperation wird auf den gesamten Ausdruck ((X > 2) → (X > 5)) angewendet. Wenn also der Ausdruck ¬((X > 2) → (X > 5)) wahr ist, wird der Ausdruck ((X > 2) →(X > 5)) ist falsch. Daher muss festgestellt werden, für welche Werte von X der Ausdruck ((X > 2) → (X > 5)) falsch ist. Der Implikationsoperator nimmt nur in einem Fall den Wert „falsch“ an: wenn aus der Wahrheit ein Falsch folgt. Und das gilt nur für X = 3; X=4; X=5.

Beispiel 3 Für welche der folgenden Wörter ist die Aussage ¬(erster Buchstabe Vokal ∧ dritter Buchstabe Vokal) ⇔ Kette aus 4 Zeichen falsch? 1) Ass; 2) Plätzchen; 3) Mais; 4) Fehler; 5) starker Mann.

Lösung. Schauen wir uns jedes der folgenden Wörter einzeln an:

1) für das Wort assa erhalten wir: ¬(1 ∧ 0) ⇔ 1, 1 ⇔ 1 — die Aussage ist wahr;

2) für das Wort kuku erhalten wir: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 — die Aussage ist wahr;

3) für das Wort Mais erhalten wir: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 - die Aussage ist falsch;

4) für das Wort Fehler erhalten wir: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 — die Aussage ist wahr;

5) für das Wort Strongman erhalten wir: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 - die Aussage ist falsch.

Boolesche Ausdrücke und ihre Konvertierung

Unter Boolescher Ausdruck ist als ein solcher Datensatz zu verstehen, der den logischen Wert „wahr“ oder „falsch“ annehmen kann. Bei dieser Definition muss zwischen logischen Ausdrücken unterschieden werden zwischen:

• Ausdrücke, die Vergleichsoperationen verwenden („größer als“, „kleiner als“, „gleich“, „ungleich“ usw.) und logische Werte annehmen (z. B. der Ausdruck a > b, wobei a = 5 und b = 7, entspricht "false");
• direkte logische Ausdrücke, die mit logischen Werten und logischen Operationen verbunden sind (z. B. A ∨ B ∧ C, wobei A = wahr, B = falsch und C = wahr ist).

Boolesche Ausdrücke können Funktionen, algebraische Operationen, Vergleichsoperationen und logische Operationen enthalten. In diesem Fall ist die Priorität für die Ausführung von Aktionen wie folgt:

1. Berechnung bestehender funktionaler Abhängigkeiten;
2. Durchführen algebraischer Operationen (zuerst Multiplikation und Division, dann Subtraktion und Addition);
3. Durchführen von Vergleichsoperationen (in zufälliger Reihenfolge);
4. Ausführung logischer Operationen (zuerst die Negationsoperation, dann die Operationen der logischen Multiplikation, logische Addition, die letzten Operationen sind Implikation und Äquivalenz).

Ein boolescher Ausdruck kann Klammern verwenden, die die Reihenfolge ändern, in der Operationen ausgeführt werden.

Beispiel. Finden Sie den Wert eines Ausdrucks:

$1 ≤ a ∨ A ∨ sin(π/a - π/b)< 1 ∧ ¬B ∧ ¬(b^a + a^b >a + b ∨ A ∧ B)$ für a = 2, b = 3, A = wahr, B = falsch.

Lösung. Die Reihenfolge der Zählwerte:

1) b a + a b > a + b, nach Substitution erhalten wir: 3 2 + 2 3 > 2 + 3, also 17 > 2 + 3 = wahr;

2) A ∧ B = wahr ∧ falsch = falsch.

Daher ist der Ausdruck in Klammern (b a + a b > a + b ∨ A ∧ B) = wahr ∨ falsch = wahr;

3) 1 ≤ a = 1 ≤ 2 = wahr;

4) sin(π/a - π/b)< 1 = sin(π/2 - π/3) < 1 = истина.

Nach diesen Berechnungen erhalten wir schließlich: wahr ∨ A ∧ wahr ∧ ¬B ∧ ¬wahr.

Nun müssen die Negationsoperationen durchgeführt werden, dann die logische Multiplikation und Addition:

5) ¬B = ¬falsch = wahr; ¬wahr = falsch;

6) A ∧ wahr ∧ wahr ∧ falsch = wahr ∧ wahr ∧ wahr ∧ falsch = falsch;

7) wahr ∨ falsch = wahr.

Somit ist das Ergebnis eines logischen Ausdrucks für die gegebenen Werte „wahr“.

Notiz. Da der ursprüngliche Ausdruck letztendlich die Summe zweier Terme ist und der Wert eines von ihnen 1 ≤ a = 1 ≤ 2 = wahr ist, können wir ohne weitere Berechnungen sagen, dass das Ergebnis für den gesamten Ausdruck ebenfalls „wahr“ ist “.

Identitätstransformationen logischer Ausdrücke

In der Algebra der Logik sind die Grundgesetze erfüllt, die identische Transformationen logischer Ausdrücke erlauben.

Gesetz	Für ∨	Für ∧
verschiebbar	A ∨ B = B ∨ A	A ∧ B = B ∧ A
Assoziativ	A ∨ (B ∨ C) = (B ∨ A) ∨ C	A ∧ (B ∧ C) = (A ∧ B) ∧ C
Verteilung	A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)	A ∨ B ∧ C = (A ∨ B) ∧ (A ∨ C)
De Morgan regiert	$(A ∨ B)↖(-)$ = $A↖(-) ∧ B↖(-)$	$(A ∧ B)↖(-)$ = $A↖(-) ∨ B↖(-)$
Idempotenz	A ∨ A = A	A ∧ A = A
Übernahmen	A ∨ A ∧ B = A	A ∧ (A ∨ B) = A
Verbindung	(A ∧ B) ∨ (A↖(-) ∧ B) = B	(A ∨ B) ∧ (A↖(-) ∨ B) = B
Variabler Betrieb mit seiner Umkehrung	$A ∨ A↖(-)$ = 1	$A ∧ A↖(-)$ = 0
Betrieb mit Konstanten	A ∨ 0 = A A ∨ 1 = 1	A ∧ 1 = A A ∧ 0 = 0
Doppel negativ	$A↖(=)$ = A

Die Beweise dieser Aussagen werden auf der Grundlage der Konstruktion von Wahrheitstabellen für die entsprechenden Datensätze erstellt.

Äquivalente Transformationen logischer Formeln haben den gleichen Zweck wie die Transformationen von Formeln in der gewöhnlichen Algebra. Sie dienen dazu, Formeln zu vereinfachen oder durch Anwendung der Grundgesetze der Algebra der Logik in eine bestimmte Form zu bringen. Unter Formelvereinfachung, die die Implikations- und Äquivalenzoperationen nicht enthält, wird als äquivalente Transformation verstanden, die zu einer Formel führt, die entweder eine geringere Anzahl von Operationen im Vergleich zur ursprünglichen Formel oder eine geringere Anzahl von Variablen enthält.

Einige Transformationen logischer Formeln ähneln Transformationen von Formeln in der gewöhnlichen Algebra (Einnahme gemeinsamer Multiplikator Klammern, die Verwendung von Kommutativ- und Assoziativgesetzen usw.), während andere Transformationen auf Eigenschaften basieren, die gewöhnliche algebraische Operationen nicht haben (die Verwendung eines Distributivgesetzes für die Konjunktion, die Gesetze der Absorption, des Klebens, de Morgan usw. ).

Sehen wir uns Beispiele für einige der Techniken und Methoden an, die beim Vereinfachen logischer Formeln verwendet werden:

1) X1 ∧ X2 ∨ X1 ∧ X2 ∪ ¬X1 ∧ X2 = X1 ∧ X2 ∨ ¬X1 ∧ X2 = (X1 ∨ ¬X1) ∧ X2 = 1 ∧ X2 = X2 .

Um hier zu transformieren, können Sie das Gesetz der Idempotenz, das Verteilungsgesetz, anwenden; eine variable Operation mit Inversion und eine konstante Operation.

2) X1 ∨ X1 ∧ X2 = X1 ∨ (1 ∨ 1 ∧ X2) = X1 ∨ (1 ∨ X2) = X1 .

Hier wird der Einfachheit halber das Absorptionsgesetz angewendet.

3) ¬(X1 ∧ X2) ∨ X2 = (¬X1 ∨ ¬X2) ∨ X2 = ¬X1 ∨ ¬X2 ∨ X2 = ¬X1 ∨ 1 = 1 .

Bei der Umrechnung werden die De-Morgan-Regel, die Operation einer Variablen mit ihrer Inversen, die Operation mit einer Konstanten angewendet

Beispiele für Problemlösungen

Beispiel 1 Finden Sie einen logischen Ausdruck, der dem Ausdruck A ∧ ¬(¬B ∨ C) entspricht.

Lösung. Für B und C wenden wir die Regel von de Morgan an: ¬(¬B ∨ C) = B ∧ ¬C .

Wir erhalten einen dem ursprünglichen äquivalenten Ausdruck: A ∧ ¬(¬B ∨ C) = A ∧ B ∧ ¬C .

Antworten: A ∧ B ∧ ¬C.

Beispiel 2 Geben Sie den Wert der logischen Variablen A, B, C an, für die der Wert des logischen Ausdrucks (A ∨ B) → (B ∨ ¬C ∨ B) falsch ist.

Lösung. Die Implikationsoperation ist nur dann falsch, wenn a aufgrund einer wahren Prämisse falsch ist. Daher muss für einen gegebenen Ausdruck die Prämisse A ∨ B den Wert „wahr“ und die Konsequenz, also der Ausdruck B ∨ ¬C ∨ B , den Wert „falsch“ annehmen.

1) A ∨ B - das Ergebnis der Disjunktion ist "wahr", wenn mindestens einer der Operanden "wahr" ist;

2) B ∨ ¬C ∨ B - der Ausdruck ist falsch, wenn alle Terme den Wert "falsch" haben, also B - "falsch"; ¬C ist „false“, also hat die Variable C den Wert „true“;

3) Wenn wir die Prämisse betrachten und berücksichtigen, dass B "falsch" ist, erhalten wir, dass der Wert von A "wahr" ist.

Antworten: A ist wahr, B ist falsch, C ist wahr.

Beispiel 3 Was ist die größte ganze Zahl X, für die die Aussage (35

Lösung. Schreiben wir die Wahrheitstabelle für die Implikationsoperation auf:

EIN	B	A→B
1	0	0
0	1	1
0	0	1
1	1	1

Ausdruck X< (X - 3) ложно при любых положительных значениях X. Следовательно, для того чтобы результатом импликации была «истина», необходимо и достаточно, чтобы выражение 35 < X · X также было ложно. Максимальное целое значение X, для которого 35 < X · X ложно, равно 5.

Antworten: X=5.

Verwendung von booleschen Ausdrücken zur Beschreibung geometrischer Bereiche

Boolesche Ausdrücke können verwendet werden, um geometrische Bereiche zu beschreiben. Dabei formuliert sich das Problem wie folgt: Schreibe für einen gegebenen geometrischen Bereich einen solchen logischen Ausdruck, der für die Werte x, y genau dann den Wert „wahr“ annimmt, wenn irgendein Punkt mit Koordinaten (x; y) dazugehört zum geometrischen Bereich.

Betrachten wir die Beschreibung eines geometrischen Bereichs mit einem logischen Ausdruck anhand von Beispielen.

Beispiel 1 Das Bild des geometrischen Bereichs wird eingestellt. Schreiben Sie einen logischen Ausdruck, der die Menge der zugehörigen Punkte beschreibt.

1) .

Lösung. Der gegebene geometrische Bereich kann als eine Menge der folgenden Bereiche dargestellt werden: der erste Bereich — D1 — Halbebene $(x)/(-1) +(y)/(1) ≤ 1$, der zweite — D2 — ein Kreis um den Ursprung $x ^2 + y^2 ≤ 1$ zentriert. Ihr Schnittpunkt D1 $∩$ D2 ist die gewünschte Region.

Ergebnis: boolescher Ausdruck $(x)/(-1)+(y)/(1) ≤ 1 ∧ x^2 + y^2 ≤ 1$.

2)

Dieser Bereich kann wie folgt geschrieben werden: |x| ≤ 1 ∧ y ≤ 0 ∧ y ≥ -1 .

Notiz. Bei der Konstruktion eines logischen Ausdrucks werden nicht strenge Ungleichungen verwendet, was bedeutet, dass die Grenzen der Figuren auch zum schraffierten Bereich gehören. Wenn Sie strikte Ungleichungen verwenden, werden die Grenzen nicht berücksichtigt. Grenzen, die nicht zu einer Region gehören, werden normalerweise als gepunktete Linien dargestellt.

Sie können das umgekehrte Problem lösen, nämlich: Zeichnen Sie eine Region für einen gegebenen logischen Ausdruck.

Beispiel 2 Zeichnen und schraffieren Sie eine Fläche, deren Punkte die logische Bedingung y ≥ x ∧ y + x ≥ 0 ∧ y erfüllen< 2 .

Lösung. Der gewünschte Bereich ist der Schnittpunkt von drei Halbebenen. Wir bauen auf der Ebene (x, y) gerade Linien y = x; y=-x; y = 2. Dies sind die Grenzen der Region, und die letzte Grenze y = 2 gehört nicht zur Region, also zeichnen wir sie mit einer gepunkteten Linie. Um die Ungleichung y ≥ x zu erfüllen, ist es notwendig, dass die Punkte links von der Geraden y = x liegen und die Ungleichung y = -x für die Punkte rechts von der Geraden y = -x erfüllt ist. Bedingung y< 2 выполняется для точек, лежащих ниже прямой y = 2. В результате получим область, которая изображена на рис.:

Verwendung logischer Funktionen zur Beschreibung elektrischer Schaltungen

Logikfunktionen sind sehr praktisch, um den Betrieb elektrischer Schaltungen zu beschreiben. Also, für die in der Abbildung gezeigte Schaltung, wo der Wert der Variablen X der Zustand des Schalters ist (wenn er eingeschaltet ist, ist der Wert von X "wahr", und wenn er ausgeschaltet ist - "falsch"), dies Wert von Y ist der Zustand der Glühbirne (wenn sie eingeschaltet ist) - der Wert ist "wahr", und wenn nicht - "falsch"), wird die logische Funktion wie folgt geschrieben: Y = X . Die Funktion Y wird aufgerufen Leitungsfunktion.

Für die in der Abbildung gezeigte Schaltung hat die logische Funktion Y die Form: Y = X1 ∪ X2, da ein Schalter ausreicht, um die Glühbirne einzuschalten. In der Schaltung in Abb. müssen beide Schalter eingeschaltet sein, damit die Glühbirne brennt. Daher hat die Leitfähigkeitsfunktion die Form: Y \u003d X1 ∧ X2.

Für eine komplexere Schaltung sieht die Leitwertfunktion so aus: Y = (X11 ∨ (X12 ∧ X13)) ∧ X2 ∧ (X31 ∨ X32).

Die Schaltung kann auch Arbeitskontakte enthalten. In diesem Fall sorgt der offene Kontakt als Schalter dafür, dass die Glühlampe beim Loslassen statt beim Drücken aufleuchtet. Für solche Schaltungen wird der Trennschalter durch Negation beschrieben.

Die beiden Schemata werden aufgerufen gleichwertig, wenn Strom durch einen von ihnen fließt, wenn er durch den anderen fließt. Von den beiden Ersatzschaltbildern wird die Schaltung als einfacher angesehen, deren Leitfähigkeitsfunktion eine geringere Anzahl von Elementen enthält. Die Aufgabe, das Meiste zu finden einfache Schaltungen unter Äquivalenten ist sehr wichtig.

Verwendung des Apparats der logischen Algebra beim Entwurf logischer Schaltungen

Der mathematische Apparat der Algebra der Logik ist sehr praktisch, um zu beschreiben, wie die Hardware eines Computers funktioniert. Alle Informationen, die auf einem Computer verarbeitet werden, werden in binärer Form dargestellt, dh sie werden durch eine bestimmte Folge von 0 und 1 codiert. Die Verarbeitung von Binärsignalen, die 0 und 1 entsprechen, wird im Computer durch logische Elemente durchgeführt. Logikgatter, die grundlegende logische Operationen ausführen UND, ODER, NICHT, sind in Abb. dargestellt.

Symbole für logische Elemente sind Standard und werden beim Erstellen von Computerlogikschaltungen verwendet. Mit diesen Schaltungen können Sie jede logische Funktion implementieren, die den Betrieb eines Computers beschreibt.

Technisch gesehen wird ein Computerlogikelement als elektrische Schaltung implementiert, die eine Verbindung verschiedener Teile darstellt: Dioden, Transistoren, Widerstände, Kondensatoren. Der Eingang eines Logikelements, das auch als Gatter bezeichnet wird, erhält elektrische Signale mit hohem und niedrigem Spannungspegel, der Ausgang erhält ein Ausgangssignal, ebenfalls entweder hoch oder niedriges Niveau. Diese Pegel entsprechen einem der Zustände des Binärsystems: 1 - 0; WAHR FALSCH. Jedes logische Element hat sein eigenes Symbol, das seine logische Funktion ausdrückt, aber nicht angibt, welche elektronische Schaltung darin implementiert. Dies erleichtert das Schreiben und Verstehen komplexer Logikschaltungen. Die Funktionsweise von Logikschaltungen wird anhand von Wahrheitstabellen beschrieben. Das Symbol im ODER-Diagramm ist das Zeichen „1“ – aus der veralteten Schreibweise der Disjunktion als „>=1“ (der Wert der Disjunktion ist 1, wenn die Summe der beiden Operanden größer oder gleich 1 ist). Das „&“-Zeichen im UND-Diagramm ist eine abgekürzte Schreibweise des englischen Wortes „and“.

Logikelemente werden verwendet, um elektronische Logikschaltungen aufzubauen, die komplexere logische Operationen ausführen. Ein Satz logischer Elemente, bestehend aus den Elementen NOT, OR, AND, mit denen Sie eine logische Struktur beliebiger Komplexität aufbauen können, wird aufgerufen funktional komplett.

Aufbau von Wahrheitstabellen logischer Ausdrücke

Für eine logische Formel kannst du immer schreiben Wahrheitstabelle, d.h. die gegebene logische Funktion tabellarisch darstellen. In diesem Fall sollte die Tabelle alle enthalten mögliche Kombinationen Funktionsargumente (Formeln) und entsprechende Funktionswerte (Formelergebnisse auf einem gegebenen Satz von Werten).

Eine bequeme Notationsform beim Auffinden von Funktionswerten ist eine Tabelle, die neben Variablenwerten und Funktionswerten auch die Werte von Zwischenrechnungen enthält. Betrachten Sie ein Beispiel für die Erstellung einer Wahrheitstabelle für die Formel $(X1)↖(-) ∧ X2 ∨ (X1 ∨ X2)↖(-) ∨ X1$.

X1	X2	$(X1)↖(-)$	$(X1)↖(-)$ \ X2	X1 ∧ X2	$(X1 ∨ X2)↖(-)$	$(X1)↖(-)$ ∧ X2 ∨ $(X1 ∨ X2)↖(-)$	$(X1)↖(-)$ ∧ X2 ∨ $(X1 ∨ X2)↖(-)$ ∨ X1
1	1	0	0	1	0	0	1
1	0	0	0	1	0	0	1
0	1	1	1	1	0	1	1
0	0	1	0	0	1	1	1

Wenn eine Funktion für alle Variablenwertesätze 1 ergibt, ist sie es identisch wahr; wenn die Funktion für alle Sätze von Eingabewerten den Wert 0 annimmt, ist sie es identisch falsch; wenn die Menge der Ausgangswerte sowohl 0 als auch 1 enthält, wird die Funktion aufgerufen machbar. Das obige Beispiel ist ein Beispiel für eine identisch wahre Funktion.

Wenn Sie die analytische Form der logischen Funktion kennen, können Sie jederzeit zur tabellarischen Form der logischen Funktionen wechseln. Unter Verwendung einer gegebenen Wahrheitstabelle können Sie das umgekehrte Problem lösen, nämlich: Erstellen Sie für eine gegebene Tabelle eine analytische Formel für eine logische Funktion. Es gibt zwei Formen, eine analytische Abhängigkeit einer logischen Funktion nach einer tabellarisch gegebenen Funktion zu konstruieren.

1. Disjunktive Normalform (DNF) ist die Summe der Produkte, die aus Variablen und ihren Negationen für falsche Werte gebildet werden.

Der Algorithmus zum Erstellen eines DNF lautet wie folgt:

1. in der Wahrheitstabelle wählen die Funktionen Sätze von Argumenten aus, für die die logischen Formen gleich 1 sind ("wahr");
2. alle ausgewählten logischen Mengen als logische Produkte von Argumenten werden aufgezeichnet, indem sie nacheinander durch die Operation einer logischen Summe (Disjunktion) miteinander verbunden werden;
3. für falsche Argumente wird eine Negationsoperation in die konstruierte Notation eingetragen.

Beispiel. Erstellen Sie mithilfe der DNF-Methode eine Funktion, die bestimmt, dass die erste Zahl gleich der zweiten ist. Die Wahrheitstabelle einer Funktion hat die Form

X1	X2	F(X1, X2)
1	1	1
0	1	0
1	0	0
0	0	1

Lösung. Wir wählen Sätze von Argumentwerten aus, in denen die Funktion gleich 1 ist. Dies sind die erste und vierte Zeile der Tabelle (die Kopfzeile wird bei der Nummerierung nicht berücksichtigt).

Wir schreiben die logischen Produkte der Argumente dieser Mengen auf und kombinieren sie mit einer logischen Summe: X1 ∧ X2 ∨ X1 ∧ X2 .

Wir schreiben die Negation der Argumente der ausgewählten Mengen auf, die einen falschen Wert haben (die vierte Zeile der Tabelle; die zweite Menge in der Formel; das erste und zweite Element): X1 ∧ X2 ∨ $(X1)↖(- )$ ∧ $(X2)↖(-)$.

Antworten: F(X1, X2) = X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ $(X2)↖(-)$.

2. Konjunktiv Normalform (CNF) ist das Produkt von Summen, die aus Variablen und ihren Negationen für wahre Werte gebildet werden.

Der Algorithmus zum Erstellen eines CNF lautet wie folgt:

1. in der Wahrheitstabelle werden Sätze von Argumenten ausgewählt, für die die logischen Formen 0 ("falsch") sind;
2. alle ausgewählten logischen Mengen als logische Summen von Argumenten werden sequentiell geschrieben und durch die Operation eines logischen Produkts (Konjunktion) miteinander verbunden;
3. für Argumente, die wahr sind, wird die Negationsoperation in der konstruierten Notation eingetragen.

Beispiele für Problemlösungen

Beispiel 1 Betrachten Sie das vorherige Beispiel, d. h. wir werden eine Funktion erstellen, die bestimmt, dass die erste Zahl gleich der zweiten ist, indem die CNF-Methode verwendet wird. Für eine gegebene Funktion hat ihre Wahrheitstabelle die Form

X1	X2	F(X1, X2)
1	1	1
0	1	0
1	0	0
0	0	1

Lösung. Wir wählen Sätze von Argumentwerten aus, in denen die Funktion gleich 0 ist. Dies sind die zweite und dritte Zeile (die Kopfzeile wird bei der Nummerierung nicht berücksichtigt).

Wir schreiben die logischen Summen der Argumente dieser Mengen auf und kombinieren sie mit einem logischen Produkt: X1 ∨ X2 ∧ X1 ∨ X2 .

Wir schreiben die Negation der Argumente der ausgewählten Mengen auf, die einen wahren Wert haben (die zweite Zeile der Tabelle, die erste Menge der Formel, das zweite Element; für die dritte Zeile, und dies ist die zweite Menge der Formel , das erste Element): X1 ∨ $(X2)↖(-)$ ∧ $( X1)↖(-)$ ∨ X2.

Somit wurde eine Aufzeichnung einer logischen Funktion in CNF erhalten.

Antworten: X1 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ X2.

Die durch die beiden Methoden erhaltenen Funktionswerte sind gleichwertig. Um diese Aussage zu beweisen, verwenden wir die Regeln der Logik: F(X1, X2) = X1 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ X2 = X1 ∧ $(X1)↖ (-)$ ∨ X1 ∧ X2 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ $(X2)↖(-)$ ∧ X2 = 0 ∨ X1 ∨ X2 ∨ $(X2 )↖(- )$ ∧ $(X1)↖(-)$ ∨ 0 = X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ $(X2)↖(-)$.

Beispiel 2. Erstellen Sie eine logische Funktion für eine gegebene Wahrheitstabelle:

Benötigte Formel: X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ X2 .

Es kann vereinfacht werden: X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ X2 = X2 ∧ (X1 ∨ $(X1)↖(-)$) = X2 ∧ 1 = X2.

Beispiel 3 Konstruieren Sie für die gegebene Wahrheitstabelle eine logische Funktion mit der DNF-Methode.

X1	X2	X3	F(X1, X2, X3)
1	1	1	1		X1 ∧ X2 ∧ X3
1	0	1	0
0	1	1	1		$(X1)↖(-)$ ∧ X2 ∧ X3
0	0	1	0
1	1	0	1		X1 ∧ X2 ∧ $(X3)↖(-)$
1	0	0	1		X1 ∧ $(X2)↖(-)$ ∧ $(X3)↖(-)$
0	1	0	0
0	0	0	0

Benötigte Formel: X1 ∧ X2 ∧ X ∨ $(X1)↖(-)$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $(X3)↖(-)$ ∪ X1 ∧ $(X2)↖(-)$ ∧ $ (X3)↖(-)$.

Die Formel ist recht umständlich und sollte vereinfacht werden:

X1 ∧ X2 ∧ X3 ∨ $(X1)↖(-)$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $(X3)↖(-)$ ∨ X1 ∧ $(X2)↖(-)$ ∧ $(X3) ↖(-)$ = X2 ∧ X3 ∧ (X1 ∨ $(X1)↖(-)$) ∨ X1 ∧ $(X3)↖(-)$ ∧ (X2 ∨ $(X2)↖(-)$) = X2 ∧ X3 ∨ X1 ∧ $(X3)↖(-)$.

Wahrheitstabellen zum Lösen logischer Probleme

Das Erstellen von Wahrheitstabellen ist eine der Möglichkeiten, logische Probleme zu lösen. Bei dieser Lösungsmethode werden die Bedingungen, die das Problem enthält, anhand speziell zusammengestellter Tabellen festgelegt.

Beispiele für Problemlösungen

Beispiel 1 Erstellen Sie eine Wahrheitstabelle für ein Sicherheitsgerät, das drei Sensoren verwendet und ausgelöst wird, wenn nur zwei von ihnen schließen.

Lösung. Offensichtlich ist das Ergebnis der Lösung eine Tabelle, in der die gewünschte Funktion Y(X1, X2, X3) wahr ist, wenn zwei beliebige Variablen wahr sind.

X1	X2	X3	Y(X1, X2, X3)
1	1	1	0
1	1	0	1
1	0	1	1
1	0	0	0
0	1	1	1
0	1	0	0
0	0	1	0
0	0	0	0

Beispiel 2 Erstellen Sie einen Stundenplan für den Tag, da die Informatikstunde nur die erste oder zweite, die Mathematikstunde die erste oder dritte und die Physikstunde die zweite oder dritte sein kann. Ist es möglich, einen Zeitplan zu erstellen, der alle Anforderungen erfüllt? Wie viele Zeitplanoptionen gibt es?

Lösung. Das Problem lässt sich leicht lösen, wenn Sie die entsprechende Tabelle erstellen:

	1. Lektion	2. Lektion	3. Lektion
Informatik	1	1	0
Mathe	1	0	1
Physik	0	1	1

Die Tabelle zeigt, dass es zwei Optionen für den gewünschten Zeitplan gibt:

1. Mathematik, Informatik, Physik;
2. Informatik, Physik, Mathematik.

Beispiel 3 Drei Freunde kamen zum Sportcamp - Peter, Boris und Alexei. Jeder von ihnen liebt zwei Sportarten. Es ist bekannt, dass es sechs solcher Sportarten gibt: Fußball, Hockey, Skifahren, Schwimmen, Tennis, Badminton. Bekannt ist auch:

1. Boris ist der älteste;
2. Fußballspielen ist jünger als Hockeyspielen;
3. Fußball und Hockey spielen und Peter im selben Haus wohnen;
4. als es zwischen einem Skifahrer und einem Tennisspieler zu einem Streit kommt, versöhnt Boris sie;
5. Peter kann weder Tennis noch Badminton spielen.

Welche Sportarten macht jeder der Jungen gerne?

Lösung. Lassen Sie uns eine Tabelle erstellen und die Bedingungen des Problems darin widerspiegeln, indem wir die entsprechenden Zellen mit den Zahlen 0 und 1 ausfüllen, je nachdem, ob die entsprechende Aussage falsch oder wahr ist.

Da es sechs Sportarten gibt, stellt sich heraus, dass alle Jungs sie mögen verschiedene Typen Sport.

Aus Bedingung 4 folgt, dass Boris weder Skifahren noch Tennis mag, und aus Bedingung 3 und 5, dass Peter nicht Fußball, Hockey, Tennis und Badminton spielen kann. Folglich sind Peters Lieblingssportarten Skifahren und Schwimmen. Tragen wir es in die Tabelle ein und füllen die restlichen Zellen der Spalten "Skifahren" und "Schwimmen" mit Nullen aus.

Die Tabelle zeigt, dass nur Aleksey Tennis spielen kann.

Bedingung 1 und 2 implizieren, dass Boris kein Fußballspieler ist. Also spielt Alexei Fußball. Füllen wir die Tabelle weiter aus. Lassen Sie uns Nullen in die leeren Zellen der Zeile "Alexey" eingeben.

Endlich erfahren wir, dass Boris Hockey und Badminton mag. Die Abschlusstabelle sieht wie folgt aus:

Antworten: Petr fährt gerne Ski und schwimmt gerne, Boris spielt Hockey und Badminton und Alexey spielt Fußball und Tennis.