Speisekarte
HeimatSonstig

Logische Operationen und Wahrheitstabellenentscheidung. Andere Logikfunktionen

Jobverzeichnis.
Anzahl der Studiengänge mit Pflichtstufe

Sortierung Einfach Einfach zuerst Schwer zuerst Beliebtheit Neueste zuerst Älteste zuerst
Machen Sie den Test für diese Aufgaben
Zurück zum Stellenkatalog
Version zum Drucken und Kopieren in MS Word

Executor A16 konvertiert die auf dem Bildschirm geschriebene Zahl.

Der Darsteller hat drei Teams, denen Nummern zugewiesen sind:

1. Addiere 1

2. Fügen Sie 2 hinzu

3. Multipliziere mit 2

Der erste erhöht die Zahl auf dem Bildschirm um 1, der zweite erhöht sie um 2, der dritte multipliziert sie mit 2.

Das Programm für den A16-Performer ist eine Folge von Befehlen.

Wie viele Programme gibt es, die die ursprüngliche Zahl 3 in die Zahl 12 umwandeln und gleichzeitig die Trajektorie der Berechnungen des Programms die Zahl 10 enthält?

Die Trajektorie der Berechnungen des Programms ist die Folge der Ergebnisse der Ausführung aller Programmbefehle. Zum Beispiel für Programm 132 mit der Anfangsnummer 7 besteht die Trajektorie aus den Nummern 8, 16, 18.

Lösung.

Die gewünschte Anzahl von Programmen ist gleich dem Produkt aus der Anzahl von Programmen, die die Nummer 10 von der Nummer 3 erhalten, und der Anzahl von Programmen, die die Nummer 12 von der Nummer 10 erhalten.

Sei R(n) die Anzahl der Programme, die die Zahl 3 in die Zahl n umwandeln, und P(n) die Anzahl der Programme, die die Zahl 10 in die Zahl n umwandeln.

Für alle n > 5 gelten die folgenden Beziehungen:

1. Wenn n nicht durch 2 teilbar ist, dann ist R(n) = R(n - 1) + R(n - 2), da es zwei Möglichkeiten gibt, n zu erhalten - durch Addition von eins oder Addition von zwei. Ebenso P(n) = P(n - 1) + P(n - 2)

2. Wenn n durch 2 teilbar ist, dann ist R(n) = R(n - 1) + R(n - 2) + R(n / 2). Ähnlich P(n) = P(n - 1) + P(n - 2) + P(n / 2)

Berechnen Sie nacheinander die Werte von R(n):

R(5) = R(4) + R(3) = 1 + 1 = 2

R(6) = R(5) + R(4) + R(3) = 2 + 1 + 1 = 4

R(7) = R(6) + R(5) = 4 + 2 = 6

R(8) = R(7) + R(6) + R(4) = 6 + 4 + 1 = 11

R(9) = R(8) + R(7) = 11 + 6 = 17

R(10) = R(9) + R(8) + R(5) = 17 + 11 + 2 = 30

Jetzt berechnen wir die Werte von P(n):

P(11) = P(10) = 1

P(12) = P(11) + P(10) = 2

Somit beträgt die Anzahl der Programme, die die Bedingung des Problems erfüllen, 30 2 = 60.

Antwort: 60.

Antwort: 60

Quelle: Demoversion des USE-2017 in Informatik.

1. Addiere 1

2. Fügen Sie 3 hinzu

Wie viele Programme gibt es, bei denen bei der Anfangszahl 1 das Ergebnis die Zahl 17 ist und die Rechenbahn die Zahl 9 enthält? Die Trajektorie der Berechnungen des Programms ist die Folge der Ergebnisse der Ausführung aller Programmbefehle. Zum Beispiel für Programm 121 mit der Anfangsnummer 7 besteht die Trajektorie aus den Nummern 8, 11, 12.

Lösung.

Wir verwenden die Methode der dynamischen Programmierung. Erstellen Sie ein Array dp, wobei dp[i] die Anzahl der Möglichkeiten ist, die Zahl i mit solchen Befehlen zu erhalten.

Dynamische Basis:

Übergangsformel:

dp[i]=dp + dp

Dies berücksichtigt nicht die Werte für Zahlen größer als 9, die aus Zahlen kleiner als 9 erhalten werden können (wodurch die Trajektorie 9 übersprungen wird):

Antwort: 169.

Antwort: 169

Quelle: Ausbildungsarbeit zu INFORMATIK Klasse 11, 29. November 2016, Option IN10203

Der Künstler May17 wandelt die Zahl auf dem Bildschirm um.

Der Darsteller hat zwei Teams, denen Nummern zugewiesen werden:

1. Addiere 1

2. Fügen Sie 3 hinzu

Der erste Befehl erhöht die Zahl auf dem Bildschirm um 1, der zweite um 3. Das Programm für den May17-Darsteller ist eine Folge von Befehlen.

Wie viele Programme gibt es, bei denen bei der Anfangszahl 1 das Ergebnis die Zahl 15 ist und die Rechenbahn die Zahl 8 enthält? Die Trajektorie von Programmberechnungen ist die Folge von Ergebnissen der Ausführung aller Programmbefehle. Zum Beispiel für Programm 121 mit der Anfangsnummer 7 besteht die Trajektorie aus den Nummern 8, 11, 12.

Lösung.

Wir verwenden die Methode der dynamischen Programmierung. Lassen Sie uns ein Array dp erstellen, wobei dp[i] die Anzahl der Möglichkeiten ist, die Zahl i mit solchen Befehlen zu erhalten.

Dynamische Basis:

Übergangsformel:

dp[i]=dp + dp

Dies berücksichtigt jedoch keine Zahlen, die größer als 8 sind, aber wir können sie von einem Wert kleiner als 8 erreichen. Als nächstes werden die Werte in dp von 1 bis 15 angegeben: 1 1 1 2 3 4 6 9 9 9 18 27 36 54 81 .

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 ergibt nur dann wahr, 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.

Ausführungspriorität logische Operationen weiter: Verneinung ( "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 elementare Aussagen, 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 (Einklammern des gemeinsamen Faktors, Verwenden der Kommutativ- und Assoziativgesetze usw.), während andere Transformationen auf Eigenschaften basieren, die gewöhnliche algebraische Operationen nicht haben (unter Verwendung des Distributivgesetzes). für Konjunktion , die Gesetze der Absorption, Verleimung, 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 gepunktete 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 Computer logisches Element im Formular umgesetzt elektrische Schaltung, das ist eine Verbindung verschiedener Teile: 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. Symbol im ODER-Schema stammt das Zeichen „1“ von der veralteten Bezeichnung 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 möglichen Kombinationen von Funktionsargumenten (Formeln) und entsprechenden Funktionswerten (Formelergebnisse auf einer gegebenen Wertemenge) enthalten.

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.

Wir lernen, logische Ausdrücke aus Aussagen zu machen, wir definieren das Konzept der „Wahrheitstabelle“, wir studieren die Abfolge von Aktionen zum Erstellen von Wahrheitstabellen, wir lernen, den Wert logischer Ausdrücke durch das Erstellen von Wahrheitstabellen zu finden.

Unterrichtsziele:

  1. Tutorials:
    1. Lernen Sie, aus Aussagen logische Ausdrücke zu machen
    2. Führen Sie das Konzept der „Wahrheitstabelle“ ein
    3. Untersuchung der Handlungsabfolge zur Erstellung von Wahrheitstafeln
    4. Lernen Sie, den Wert logischer Ausdrücke zu finden, indem Sie Wahrheitstabellen erstellen
    5. Führen Sie das Konzept der Äquivalenz logischer Ausdrücke ein
    6. Lernen Sie, die Äquivalenz logischer Ausdrücke anhand von Wahrheitstabellen zu beweisen
    7. Festigung der Fähigkeiten, die Werte logischer Ausdrücke zu finden, indem Wahrheitstabellen erstellt werden
  2. Entwicklung:
    1. Logisches Denken entwickeln
    2. Aufmerksamkeit entwickeln
    3. Gedächtnis entwickeln
    4. Entwickeln Sie die Sprache der Schüler
  3. Lehrreich:
    1. Kultivieren Sie die Fähigkeit, Lehrern und Klassenkameraden zuzuhören
    2. Kultivieren Sie die Genauigkeit, ein Notizbuch zu führen
    3. Disziplin kultivieren

Während des Unterrichts

Zeit organisieren

Hallo Leute. Wir beschäftigen uns weiterhin mit den Grundlagen der Logik und dem Thema unserer heutigen Lektion „Logische Ausdrücke bilden. Wahrheitstabellen. Nachdem Sie sich mit diesem Thema befasst haben, werden Sie lernen, wie Aussagen aus logischen Formen zusammengesetzt werden, und ihre Wahrheit durch das Erstellen von Wahrheitstabellen bestimmen.

Überprüfung der Hausaufgaben

Schreiben Sie die Hausaufgabenlösungen an die Tafel
Alle anderen, öffnet eure Hefte, ich gehe durch, überprüfe, wie ihr eure Hausaufgaben gemacht habt
Wiederholen wir die logischen Operationen noch einmal
In welchem ​​Fall wird die zusammengesetzte Aussage als Ergebnis der Operation der logischen Multiplikation wahr sein?
Eine zusammengesetzte Aussage, die als Ergebnis der Operation der logischen Multiplikation gebildet wird, ist genau dann wahr, wenn alle darin enthaltenen einfachen Aussagen wahr sind.
In welchem ​​Fall ist die zusammengesetzte Aussage als Ergebnis der logischen Additionsoperation falsch?
Eine durch logische Addition gebildete zusammengesetzte Aussage ist falsch, wenn alle darin enthaltenen einfachen Aussagen falsch sind.
Wie wirkt sich die Inversion auf die Äußerung aus?
Inversion macht eine wahre Aussage falsch und umgekehrt eine falsche wahr.
Was können Sie über die Implikation sagen?
Die logische Konsequenz (Implikation) wird gebildet, indem zwei Aussagen mit der Redewendung "wenn ... dann ..." zu einer kombiniert werden.
Bezeichnet ABER-> BEI
Eine zusammengesetzte Aussage, die mit Hilfe der Operation der logischen Konsequenz (Implikation) gebildet wird, ist genau dann falsch, wenn aus der wahren Prämisse (der ersten Aussage) eine falsche Konklusion (zweite Aussage) folgt.
Was können Sie über die logische Äquivalenzoperation sagen?
Die logische Gleichheit (Äquivalenz) wird gebildet, indem zwei Aussagen mit der Redewendung „… wenn und nur wenn…“, „… wenn und nur wenn…“ zu einer zusammengefasst werden.
Eine mit Hilfe einer logischen Äquivalenzoperation gebildete zusammengesetzte Aussage ist genau dann wahr, wenn beide Aussagen gleichzeitig entweder falsch oder wahr sind.

Erklärung des neuen Materials

Nun, wir haben das behandelte Material wiederholt, wir gehen zu einem neuen Thema über.

In der letzten Lektion haben wir den Wert einer zusammengesetzten Anweisung ermittelt, indem wir die Anfangswerte der booleschen Eingabevariablen ersetzt haben. Und heute werden wir lernen, dass es möglich ist, eine Wahrheitstabelle zu erstellen, die die Wahrheit oder Falschheit eines logischen Ausdrucks für alle möglichen Kombinationen der Anfangswerte einfacher Aussagen (logischer Variablen) bestimmt, und dass es möglich ist, die Werte zu bestimmen ​​der anfänglichen logischen Variablen und wissen, welches Ergebnis wir brauchen.

Betrachten Sie noch einmal unser Beispiel aus der letzten Lektion.

und erstellen Sie eine Wahrheitstabelle für diese zusammengesetzte Aussage

Beim Erstellen von Wahrheitstabellen gibt es eine bestimmte Abfolge von Aktionen. Schreiben wir auf

  1. Es ist notwendig, die Anzahl der Zeilen in der Wahrheitstabelle zu bestimmen.
  • Anzahl der Zeilen = 2 n , wobei n die Anzahl der booleschen Variablen ist
  • Es ist notwendig, die Anzahl der Spalten in der Wahrheitstabelle zu bestimmen, die gleich der Anzahl der boolschen Variablen plus der Anzahl der boolschen Operationen ist.
  • Es ist notwendig, eine Wahrheitstabelle mit der angegebenen Anzahl von Zeilen und Spalten zu erstellen, die Namen der Tabellenspalten gemäß der Reihenfolge der logischen Operationen unter Berücksichtigung von Klammern und Prioritäten einzugeben;
  • Spalten von Eingabevariablen mit Wertesätzen füllen
  • Füllen Sie die Wahrheitstabelle nach Spalten aus und führen Sie logische Operationen gemäß der festgelegten Reihenfolge durch.

    • Verzeichnet. Aufbau einer Wahrheitstabelle
    Was machen wir zuerst?
    Bestimmen Sie die Anzahl der Spalten in einer Tabelle
    Wie machen wir es?
    Wir zählen die Anzahl der Variablen. In unserem Fall die logische Funktion enthält 2 Variablen
    Die?
    A und B
    Wie viele Zeilen werden also in der Tabelle sein?
    Die Anzahl der Zeilen in der Wahrheitstabelle muss 4 sein.
    Was ist, wenn es 3 Variablen gibt?
    Reihenzahl = 2³ = 8
    Recht. Was machen wir als Nächstes?
    Wir definieren die Anzahl der Spalten = die Anzahl der booleschen Variablen plus die Anzahl der booleschen Operationen.
    Wie viel wird in unserem Fall sein?
    In unserem Fall beträgt die Anzahl der Variablen zwei und die Anzahl der logischen Operationen fünf, dh die Anzahl der Spalten in der Wahrheitstabelle beträgt sieben.
    Gut. Weiter?
    Wir erstellen eine Tabelle mit der angegebenen Anzahl von Zeilen und Spalten, bezeichnen die Spalten und geben mögliche Wertesätze der anfänglichen logischen Variablen in die Tabelle ein und füllen die Wahrheitstabelle spaltenweise aus.
    Welche Operation führen wir zuerst durch? Denken Sie nur an Klammern und Vorrang
    Sie können zuerst eine logische Negation durchführen oder zuerst den Wert in der ersten Klammer finden, dann die Umkehrung und den Wert in der zweiten Klammer, dann den Wert zwischen diesen Klammern

    ┐Av┐B

    (AvB)&(┐Av┐B)

    Jetzt können wir den Wert einer logischen Funktion für eine beliebige Menge von Werten logischer Variablen bestimmen
    Jetzt schreiben wir den Punkt „Äquivalente logische Ausdrücke“ auf.
    Logische Ausdrücke, deren letzte Spalten von Wahrheitstabellen gleich sind, werden aufgerufen gleichwertig. Um äquivalente logische Ausdrücke zu kennzeichnen, wird das Zeichen „=“ verwendet,
    Beweisen wir, dass die logischen Ausdrücke ┐ A& ┐B und AvB äquivalent sind. Lassen Sie uns zuerst die Wahrheitstabelle des logischen Ausdrucks erstellen


     Wie viele Spalten soll die Tabelle haben? 5
    Welche Operation führen wir zuerst durch? Umkehrung A, Umkehrung B

    ┐A&┐B

    Lassen Sie uns nun die Wahrheitstabelle des logischen Ausdrucks AvB erstellen
    Wie viele Zeilen werden in der Tabelle sein? vier
    Wie viele Spalten soll die Tabelle haben? vier

    Wir alle verstehen, dass, wenn Sie eine Negation für den gesamten Ausdruck finden müssen, die Priorität in unserem Fall der Disjunktion gehört. Daher führen wir zuerst eine Disjunktion und dann eine Inversion durch. Außerdem können wir unseren logischen Ausdruck AvB umschreiben. Da Wir müssen die Negation des gesamten Ausdrucks finden und nicht einzelne Variablen, dann kann die Inversion aus den Klammern ┐(AvB) genommen werden, und wir wissen, dass wir zuerst den Wert in Klammern finden

    ┐(AVB)

    Gebaute Tische. Vergleichen wir nun die Werte in den letzten Spalten der Wahrheitstabellen, denn es sind die letzten Spalten, die das Ergebnis sind. Sie stimmen überein, daher sind logische Ausdrücke äquivalent und wir können das „=“-Zeichen dazwischen setzen

    Probleme lösen

    1.

    Wie viele Variablen enthält diese Formel? 3
    Wie viele Zeilen und Spalten soll die Tabelle haben? 8 und 8
    Wie sieht die Reihenfolge der Operationen in unserem Beispiel aus? (Inversion, Operationen in Klammern, Operationen in Klammern)

    Bv┐B(1)

    (1) =>┐C

    Av(Bv┐B=>┐C)

    2. Beweisen Sie mit Hilfe von Wahrheitstabellen die Äquivalenz der folgenden logischen Ausdrücke:

    (A → B) UND (Av┐B)

    Was schlussfolgern wir? Diese logischen Ausdrücke sind nicht äquivalent

    Hausaufgaben

    Beweisen Sie mit Hilfe von Wahrheitstabellen, dass logische Ausdrücke

    ┐A v ┐B und A&B sind äquivalent

    Erklärung des neuen Materials (Fortsetzung)

    Wir haben das Konzept der „Wahrheitstabelle“ für mehrere Lektionen hintereinander verwendet, und was ist eine wahrheitstabelle, was meinen Sie?
    Eine Wahrheitstabelle ist eine Tabelle, die eine Entsprechung zwischen den möglichen Wertesätzen logischer Variablen und den Werten von Funktionen herstellt.
    Wie hast du deine Hausaufgaben gemacht, was war dein Fazit?
    Die Ausdrücke sind äquivalent
    Denken Sie daran, dass wir in der vorherigen Lektion eine Formel aus einer zusammengesetzten Anweisung erstellt haben und die einfachen Anweisungen 2 * 2 \u003d 4 und 2 * 2 \u003d 5 durch die Variablen A und B ersetzt haben
    Lassen Sie uns nun lernen, wie man logische Ausdrücke aus Anweisungen macht

    Schreibe die Aufgabe auf

    Schreiben Sie in Form einer logischen Formel der Aussage:

    1) Wenn Ivanov gesund und reich ist, dann ist er gesund

    Analysieren wir die Aussage. Einfache Sätze finden

    A - Ivanov ist gesund
    B - Iwanow ist reich

    Okay, wie würde dann die Formel aussehen? Nur nicht vergessen, damit der Sinn der Aussage nicht verloren geht, Klammern in die Formel zu setzen

    2) Eine Zahl ist eine Primzahl, wenn sie nur durch 1 und sich selbst teilbar ist

    Eine Zahl ist nur durch 1 teilbar
    B - Zahl ist nur durch sich selbst teilbar
    C - die Zahl ist eine Primzahl

    3) Wenn eine Zahl durch 4 teilbar ist, ist sie auch durch 2 teilbar

    A ist durch 4 teilbar
    B ist durch 2 teilbar

    4) Eine beliebige Zahl ist entweder durch 2 teilbar oder durch 3 teilbar

    A ist durch 2 teilbar
    B ist durch 3 teilbar

    5) Ein Athlet wird disqualifiziert, wenn er sich gegenüber einem Gegner oder Schiedsrichter falsch verhält und wenn er „Doping“ genommen hat.

    A - Der Athlet wird disqualifiziert
    B - verhält sich gegenüber dem Gegner falsch
    C - verhält sich gegenüber dem Schiedsrichter falsch
    D - nahm "Doping".

    Probleme lösen

    1. Erstellen Sie eine Wahrheitstabelle für eine Formel

    ((p&q)→ (p→r)) v p

    Erklären Sie, wie viele Zeilen und Spalten die Tabelle haben wird. (8 und 7) Wie wird die Abfolge der Operationen aussehen und warum?

    (p&q)→ (p→r)

    ((p&q)→ (p→r)) v p

    Wir haben uns die letzte Spalte angesehen und sind zu dem Schluss gekommen, dass die Formel für jeden Satz von Eingabeparametern einen wahren Wert annimmt, eine solche Formel wird als Tautologie bezeichnet. Schreiben wir die Definition:

    Eine Formel wird als Gesetz der Logik oder Tautologie bezeichnet, wenn sie für alle Werte der in dieser Formel enthaltenen Variablen den identischen Wert „wahr“ annimmt.
    Und wenn alle Werte falsch sind, was kann man Ihrer Meinung nach zu einer solchen Formel sagen?
    Wir können sagen, dass die Formel unmöglich ist

    2. Schreiben Sie in Form einer logischen Formel die Aussage auf:

    Die Seehafenbehörde hat folgende Anordnung erlassen:

    1. Erhält der Kapitän des Schiffes eine besondere Weisung, muss er mit seinem Schiff den Hafen verlassen
    2. Erhält der Kapitän keine besondere Anweisung, darf er den Hafen nicht verlassen, sonst wird ihm fortan der Zugang zu diesem Hafen entzogen.
    3. Dem Kapitän wird entweder der Zugang zu diesem Hafen verweigert oder er erhält keine besonderen Anweisungen

    Wir erkennen einfache Aussagen, stellen Formeln auf

    • A - Der Kapitän erhält eine besondere Anweisung
    • B - verlässt den Hafen
    • C - verliert den Zugriff auf den Port
    1. ┐А→(┐В v С)
    2. C v ┐A

    3. Schreiben Sie die zusammengesetzte Aussage „(2*2=4 und 3*3 = 9) oder (2*2≠4 und 3*3≠9)“ in Form eines logischen Ausdrucks auf. Erstellen Sie eine Wahrheitstabelle.

    A=(2*2=4) B=(3*3=9)

    (A&B) v (┐A&┐B)

    ┐A&┐B

    (A&B) v (┐A&┐B)

    Hausaufgaben

    Wählen Sie eine zusammengesetzte Aussage, die dieselbe Wahrheitstabelle wie not (nicht A und nicht (B und C)) hat.

    1. A&B oder C&A;
    2. (A oder B) und (A oder C);
    3. A und (B oder C);
    4. A oder (nicht B oder C).

    Unterrichtsdauer: 45min

    Unterrichtsart: kombiniert:

    • Wissenstest - Mündliche Arbeit;
    • Neues Material- Vorlesung;
    • Vertiefung - praktische Übungen;
    • Wissenstest - Aufgaben zum selbstständigen Arbeiten.

    Unterrichtsziele:

    • geben Sie das Konzept einer Wahrheitstabelle an;
    • Vertiefung des Materials der vorherigen Lektion „Propositionalgebra“;
    • Verwendungszweck Informationstechnologien;
    • Vermittlung der Fähigkeit zur unabhängigen Suche nach neuem Material;
    • Entwicklung von Neugier, Initiative;
    • Erziehung zur Informationskultur.

    Unterrichtsplan:

    1. Organisatorischer Moment (2 min).
    2. Wiederholung des Stoffes der vorangegangenen Unterrichtsstunde (mündliche Befragung) (4 min).
    3. Erklärung des neuen Materials (12 min).
    4. Verankerung
    • Fallstudie (5 min);
    • praktische Übungen (10 min);
    • Aufgaben zum selbstständigen Arbeiten (10 min).
  • Verallgemeinerung des Unterrichts, Hausaufgaben (2 min).

    • Hard- und Softwarematerial:

    • weiße Tafel;
    • Multimedia-Projektor;
    • Computers;
    • MS PowerPoint 2003-Präsentationseditor;
    • Handout-Referenzmaterial „Wahrheitstabellen“;
    • Demonstration der Präsentation "Wahrheitstabelle".

    Während des Unterrichts

    I. Organisatorischer Moment

    Wir setzen unsere Beschäftigung mit dem Thema „Grundlagen der Logik“ fort. In den vorherigen Lektionen haben wir gesehen, dass Logik ziemlich eng mit unserem täglichen Leben verbunden ist, und wir haben auch gesehen, dass fast jede Aussage in Form einer Formel geschrieben werden kann.

    II. Rückblick auf die vorherige Lektion

    Erinnern wir uns an die wichtigsten Definitionen und Konzepte:

    Frage Antworten
    1. Welcher Satz ist eine Aussage? Aussagesatz, der etwas bejaht oder verneint
    2. In welche Arten von Erklärungen wird nach ihrer Struktur eingeteilt? Einfach und komplex
    3. Die Wahrheit welcher Aussagen ist vertraglich? Einfach
    4. Die Wahrheit welcher Aussagen wird berechnet? Komplex
    5. Wie werden einfache Aussagen in der Aussagenalgebra bezeichnet? Boolesche Variablen
    6. Wie wird die Wahrheit solcher Aussagen angezeigt? 1 und 0
    7. Was verbindet Variablen in Formeln der Aussagenalgebra? Boolesche Operationen
    8. Listen Sie sie auf. Umkehrung (Negation)

    Konjunktion (Multiplikation)

    Disjunktion (Addition)

    Implikation (folgend)

    Äquivalenz (Äquivalenz)
    9. Stellen Sie fest, ob die Formel mit der komplexen Aussage übereinstimmt. Zählen Sie einfache Sätze auf. Bestimmen Sie den Grund für die Nichtkonformität. (Aufgabe auf dem Bildschirm) Nein, das Vorzeichen ist falsch
    10. Stellen Sie fest, ob die Formel mit der komplexen Aussage übereinstimmt. Zählen Sie einfache Sätze auf. Bestimmen Sie den Grund für die Nichtkonformität. (Aufgabe auf dem Bildschirm) Ja

    III. Erklärung des neuen Materials

    Die letzten beiden Beispiele sind komplexe Anweisungen. Wie kann man die Wahrheit komplexer Aussagen bestimmen?

    Wir sagten, dass es berechnet wird. Dazu gibt es in der Logik Tabellen zur Berechnung der Wahrheit zusammengesetzter (komplexer) Aussagen. Sie werden Wahrheitstabellen genannt.

    Das Thema der Lektion ist also WAHRHEITSTABELLEN.

    3.1) Definition. Eine Wahrheitstabelle ist eine Tabelle, die die Wahrheit einer komplexen Aussage für alle möglichen Werte der Eingabevariablen zeigt (Abbildung 1).

    3.2) Lassen Sie uns jede logische Operation gemäß ihrer Definition genauer analysieren:

    1. Umkehrung (Negation) ist eine logische Operation, die jede einfache Aussage mit einer zusammengesetzten Aussage verknüpft, die darin besteht, dass die ursprüngliche Aussage negiert wird.

    Diese Operation gilt nur für eine Variable, also nur zwei Linien, weil eine Variable kann einen von haben zwei Werte: 0 oder 1.

    2. Eine Konjunktion (Multiplikation) ist eine logische Operation, die jeweils zwei einfache Aussagen mit einer zusammengesetzten Aussage verknüpft, die genau dann wahr ist, wenn beide ursprünglichen Aussagen wahr sind.

    Es ist leicht zu erkennen, dass diese Tabelle dem Einmaleins sehr ähnlich ist.

    3. Disjunktion (Addition) ist eine logische Operation, die jeweils zwei einfache Aussagen mit einer zusammengesetzten Aussage verknüpft, die genau dann falsch ist, wenn beide ursprünglichen Aussagen falsch sind.

    Es ist ersichtlich, dass die Tabelle mit Ausnahme der Additionstabelle ähnlich ist letzte Aktion. Im Binärsystem 1 + 1 = 10, dezimal - 1 + 1 = 2. In der Logik ist der Wert der Variablen 2 unmöglich, betrachten Sie 10 aus logischer Sicht: 1 ist wahr, 0 ist falsch, d.h. 10 ist gleichzeitig wahr und falsch, was nicht sein kann, daher basiert die letzte Aktion streng auf der Definition.

    4. Implikation (folgend) ist eine logische Operation, die alle zwei einfachen Aussagen mit einer zusammengesetzten Aussage verbindet, die genau dann falsch ist, wenn die Bedingung wahr und die Konsequenz falsch ist.

    5. Äquivalenz (Äquivalenz) ist eine logische Operation, die jeweils zwei einfache Aussagen mit einer zusammengesetzten Aussage verknüpft, die genau dann wahr ist, wenn beide ursprünglichen Aussagen gleichzeitig wahr oder falsch sind.

    Die letzten beiden Operationen wurden von uns in der vorherigen Lektion analysiert.

    3.3) Lassen Sie uns zerlegen Wahrheitstabellen-Algorithmus für einen komplexen Satz:

    3.4) Betrachten Sie ein Beispiel für die Erstellung einer Wahrheitstabelle für eine komplexe Aussage:

    Beispiel. Erstelle eine Wahrheitstabelle für die Formel: A U B -> ¬A U C.

    Lösung (Abbildung 2)

    Das Beispiel zeigt, dass die Wahrheitstabelle nicht die ganze Entscheidung ist, sondern nur die letzte Aktion (rot markierte Spalte).

    IV. Konsolidierung.

    Zur Festigung des Materials sind Sie eingeladen, die Beispiele unter den Buchstaben a, b, c, zusätzlich d–g, selbstständig zu lösen (Abbildung 3).

    V. Hausaufgaben, Zusammenfassung des Stoffes.

    Hausaufgaben werden Ihnen auch auf dem Monitorbildschirm gegeben (Abbildung 4)

    Verallgemeinerung des Materials: Heute haben wir in der Lektion gelernt, wie man die Wahrheit zusammengesetzter Aussagen bestimmt, aber eher aus mathematischer Sicht, da Sie nicht die Aussagen selbst, sondern die Formeln erhalten haben, die sie darstellen. In den nächsten Lektionen werden wir diese Fähigkeiten festigen und versuchen, sie auf die Lösung logischer Probleme anzuwenden.

    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 Satz von Werten der ursprünglichen Variablen ist ein Zahlencode in binäres System Kalkül, und die Anzahl der Ziffern 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. Letzter Satz - Maximalwert binäre Zahl für eine bestimmte 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: logische Computertabelle

    • 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.