Städtische Haushaltsbildungseinrichtung

"Sekundarschule Nr. 18"

Stadtbezirk der Stadt Salavat der Republik Baschkortostan

Systeme logischer Gleichungen

in den Aufgaben der Klausur Informatik

Der Abschnitt "Grundlagen der Algebra der Logik" in den Aufgaben der Prüfung gilt als einer der schwierigsten und am schlechtesten gelösten. Der durchschnittliche Prozentsatz der erledigten Aufgaben zu diesem Thema ist am niedrigsten und beträgt 43,2.

Abschnitt Kurs	Durchschnittlicher Fertigstellungsgrad nach Gruppen von Aufgaben
Kodierung von Informationen und Messung ihrer Menge
Informationsmodellierung
Zahlensysteme
Grundlagen der Algebra der Logik
Algorithmisierung und Programmierung
Grundlagen der Informations- und Kommunikationstechnologien

Basierend auf der Spezifikation von KIM 2018 umfasst dieser Block vier Aufgaben unterschiedlicher Komplexität.

№ Aufgaben	Geprüft Inhaltselemente	Schwierigkeitsgrad der Aufgabe
	Fähigkeit, Wahrheitstabellen und Logikschaltungen zu erstellen
	Möglichkeit, im Internet nach Informationen zu suchen
	Kenntnis grundlegender Konzepte und Gesetze mathematische Logik
	Fähigkeit, logische Ausdrücke zu erstellen und umzuwandeln

Aufgabe 23 hat einen hohen Schwierigkeitsgrad und hat daher den niedrigsten Fertigstellungsgrad. Unter den ausgebildeten Absolventen (81-100 Punkte) haben 49,8% die Aufgabe erledigt, die durchschnittlich Vorbereiteten (61-80 Punkte) bewältigen 13,7%, die übrige Gruppe der Studierenden schafft diese Aufgabe nicht.

Der Erfolg beim Lösen eines Systems logischer Gleichungen hängt von der Kenntnis der Gesetze der Logik und von der präzisen Anwendung von Methoden zur Lösung des Systems ab.

Betrachten Sie die Lösung eines Systems logischer Gleichungen durch die Abbildungsmethode.

(23.154 Polyakov K.Yu.) Wie viele verschiedene Lösungen hat das Gleichungssystem?

((x1  j1 )  (x2  j2 ))  (x1  x2 )  (y1  j2 ) =1

((x2  j2 )  (x3  j3 ))  (x2  x3 )  (y2  j3 ) =1

((x7  j7 )  (x8  j8 ))  (x7  x8 )  (j7  j8 ) =1

wo x1 , x2 ,…, x8, beim1 , ja2 ,…,y8 - Boolesche Variablen? Die Antwort muss nicht alle verschiedenen Sätze von Variablenwerten auflisten, für die diese Gleichheit gilt. Als Antwort müssen Sie die Anzahl solcher Sätze angeben.

Entscheidung. Alle im System enthaltenen Gleichungen sind vom gleichen Typ, und in jeder Gleichung sind vier Variablen enthalten. Wenn wir x1 und y1 kennen, können wir alle möglichen Werte von x2 und y2 finden, die die erste Gleichung erfüllen. In ähnlicher Weise können wir aus den bekannten x2 und y2 x3, y3 finden, die die zweite Gleichung erfüllen. Das heißt, wenn wir das Paar (x1 , y1) kennen und den Wert des Paares (x2 , y2) bestimmen, finden wir das Paar (x3 , y3 ), was wiederum zum Paar (x4 , y4 ) führt und so weiter An.

Lassen Sie uns alle Lösungen der ersten Gleichung finden. Dies kann auf zweierlei Weise geschehen: eine Wahrheitstabelle erstellen, durch logisches Denken und Anwendung der Gesetze der Logik.

Wahrheitstabelle:

				x 1  ja 1	x2  y2	(x 1  j1)  (x 2  j2)	(x 1  x2)	(ja 1  j2)	(x 1  x2)  (ja 1  j2)

Das Erstellen einer Wahrheitstabelle ist mühsam und zeitintensiv, daher verwenden wir die zweite Methode - logisches Denken. Das Produkt ist genau dann 1, wenn jeder Faktor 1 ist.

(x1  j1 )  (x2  j2 ))=1

(x1  x2 ) =1

(j1  j2 ) =1

Betrachten Sie die erste Gleichung. Folgendes ist gleich 1, wenn 0 0, 0 1, 1 1, dann (x1 y1)=0 bei (01), (10), dann das Paar (x2  j2 ) kann beliebig (00), (01), (10), (11) sein, und für (x1 y1)=1, d. h. (00) und (11), nimmt das Paar (x2 y2)=1 die gleichen Werte an (00) und (11). Wir schließen von dieser Lösung diejenigen Paare aus, für die die zweite und dritte Gleichung falsch sind, also x1=1, x2=0, y1=1, y2=0.

(x1 , j1 )	(x2 , j2 )

Gesamtzahl der Paare 1+1+1+22= 25

2) (23.160 Polyakov K.Yu.) Wie viele verschiedene Lösungen hat ein System logischer Gleichungen?

(x 1  (x 2  j 2 ))  (y 1  j 2 ) = 1

(x 2  (x 3  j 3 ))  (y 2  j 3 ) = 1

...

( x 6  ( x 7  j 7 ))  ( j 6  j 7 ) = 1

x 7  j 7 = 1

Entscheidung. 1) Die Gleichungen sind vom gleichen Typ, also werden wir durch die Denkmethode alle möglichen Paare (x1,y1), (x2,y2) der ersten Gleichung finden.

(x1  (x2  j2 ))=1

(j1  j2 ) = 1

Die Lösung der zweiten Gleichung sind die Paare (00), (01), (11).

Lassen Sie uns Lösungen für die erste Gleichung finden. Wenn x1=0, dann x2 , y2 - beliebig, wenn x1=1, dann nimmt x2 , y2 den Wert (11) an.

Lassen Sie uns Verbindungen zwischen den Paaren (x1 , y1) und (x2 , y2) herstellen.

(x1 , j1 )	(x2 , j2 )

Lassen Sie uns eine Tabelle erstellen, um die Anzahl der Paare in jeder Phase zu berechnen.

							0

Unter Berücksichtigung der Lösungen der letzten Gleichung x 7  j 7 = 1, wir eliminieren das Paar (10). Finden Sie die Gesamtzahl der Lösungen 1+7+0+34=42

3)(23.180) Wie viele verschiedene Lösungen hat das System der logischen Gleichungen?

(x1  x2 )  (x3  x4 ) = 1

(x3  x4 )  (x5  x6 ) = 1

(x5  x6 )  (x7  x8 ) = 1

(x7  x8 )  (x9  x10 ) = 1

x1  x3  x5  x7  x9 = 1

Entscheidung. 1) Die Gleichungen sind vom gleichen Typ, also werden wir durch die Denkmethode alle möglichen Paare (x1,x2), (x3,x4) der ersten Gleichung finden.

(x1  x2 )  (x3  x4 ) = 1

Wir schließen im Folgenden die Paare, die 0 (1 0) ergeben, von der Lösung aus, das sind die Paare (01, 00, 11) und (10).

Verbindungen zwischen Paaren bilden (x1,x2), (x3,x4)

Es gibt verschiedene Möglichkeiten, logische Gleichungssysteme zu lösen. Dies ist eine Reduktion auf eine Gleichung, die Konstruktion einer Wahrheitstabelle und Zerlegung.

Aufgabe: Lösen Sie ein System logischer Gleichungen:

Prüfen Methode der Reduktion auf eine Gleichung . Bei dieser Methode werden logische Gleichungen so transformiert, dass ihre rechte Seite gleich dem Wahrheitswert (also 1) ist. Verwenden Sie dazu die Operation der logischen Negation. Wenn die Gleichungen dann komplexe logische Operationen enthalten, ersetzen wir sie durch grundlegende: „UND“, „ODER“, „NICHT“. Der nächste Schritt besteht darin, die Gleichungen unter Verwendung der logischen Operation "AND" zu einer, dem System äquivalenten, zu kombinieren. Danach sollten Sie Transformationen der resultierenden Gleichung basierend auf den Gesetzen der Algebra der Logik vornehmen und eine spezifische Lösung für das System erhalten.

Lösung 1: Wende die Umkehrung auf beide Seiten der ersten Gleichung an:

Lassen Sie uns die Implikation durch die Grundoperationen "ODER", "NICHT" darstellen:

Da die linken Seiten der Gleichungen gleich 1 sind, können Sie sie mit der „UND“-Verknüpfung zu einer Gleichung kombinieren, die dem ursprünglichen System entspricht:

Wir öffnen die erste Klammer nach dem Gesetz von de Morgan und formen das Ergebnis um:

Die resultierende Gleichung hat eine Lösung: A=0, B=0 und C=1.

Der nächste Weg ist Konstruktion von Wahrheitstafeln . Da logische Größen nur zwei Werte haben, können Sie einfach alle Möglichkeiten durchgehen und darunter diejenigen finden, für die das gegebene Gleichungssystem erfüllt ist. Das heißt, wir erstellen eine gemeinsame Wahrheitstabelle für alle Gleichungen des Systems und finden eine Linie mit den gewünschten Werten.

Lösung 2: Lassen Sie uns eine Wahrheitstabelle für das System erstellen:

0	0	1	1	0	1

Fett ist die Linie, für die die Bedingungen des Problems erfüllt sind. Also A=0, B=0 und C=1.

Weg Zersetzung . Die Idee ist, den Wert einer der Variablen festzulegen (gleich 0 oder 1 zu setzen) und dadurch die Gleichungen zu vereinfachen. Dann können Sie den Wert der zweiten Variablen festlegen und so weiter.

Lösung 3: Sei A = 0, dann:

Aus der ersten Gleichung erhalten wir B = 0 und aus der zweiten - С=1. Systemlösung: A = 0, B = 0 und C = 1.

In der USE in der Informatik ist es sehr oft notwendig, die Anzahl der Lösungen eines logischen Gleichungssystems zu bestimmen, ohne die Lösungen selbst zu finden, auch dafür gibt es bestimmte Methoden. Der Hauptweg, um die Anzahl der Lösungen für ein System logischer Gleichungen zu finden, istÄnderung von Variablen. Zunächst ist es notwendig, jede der Gleichungen auf der Grundlage der Gesetze der Algebra der Logik so weit wie möglich zu vereinfachen und dann die komplexen Teile der Gleichungen durch neue Variablen zu ersetzen und die Anzahl der Lösungen für das neue System zu bestimmen. Kehren Sie dann zum Ersatz zurück und bestimmen Sie die Anzahl der Lösungen dafür.

Aufgabe: Wie viele Lösungen hat die Gleichung (A → B ) + (C → D ) = 1? Wobei A, B, C, D boolesche Variablen sind.

Entscheidung: Lassen Sie uns neue Variablen einführen: X = A → B und Y = C → D . Unter Berücksichtigung der neuen Variablen wird die Gleichung in der Form geschrieben: X + Y = 1.

Die Disjunktion ist in drei Fällen wahr: (0;1), (1;0) und (1;1), während X und Y eine Implikation sind, das heißt, sie ist in drei Fällen wahr und in einem falsch. Daher entspricht der Fall (0;1) drei möglichen Kombinationen von Parametern. Fall (1;1) – entspricht neun möglichen Kombinationen der Parameter der ursprünglichen Gleichung. Daher gibt es 3+9=15 mögliche Lösungen dieser Gleichung.

Der folgende Weg, um die Anzahl der Lösungen für ein System logischer Gleichungen zu bestimmen, ist − binärer Baum. Betrachten wir diese Methode anhand eines Beispiels.

Aufgabe: Wie viele verschiedene Lösungen hat das logische Gleichungssystem:

Das gegebene Gleichungssystem ist äquivalent zu der Gleichung:

(x 1 → x 2 )*(x 2 → x 3 )*…*(x m -1 → x m) = 1.

Stellen wir uns das vor x 1 wahr ist, dann erhalten wir das aus der ersten Gleichung x 2 auch wahr, von der zweiten - x 3 =1, und so weiter bis x m= 1. Das bedeutet, dass die Menge (1; 1; …; 1) von m Einheiten die Lösung des Systems ist. Lassen Sie jetzt x 1 =0, dann haben wir aus der ersten Gleichung x 2 =0 oder x 2 =1.

Wann x 2 wahr, erhalten wir, dass auch die anderen Variablen wahr sind, das heißt, die Menge (0; 1; ...; 1) ist die Lösung des Systems. Beim x 2 =0 wir bekommen das x 3 =0 oder x 3 =, und so weiter. Wenn wir mit der letzten Variablen fortfahren, erhalten wir, dass die Lösungen der Gleichung die folgenden Sätze von Variablen sind (m + 1 Lösung, jede Lösung hat m Werte von Variablen):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Dieser Ansatz lässt sich gut durch den Aufbau eines binären Baums veranschaulichen. Die Anzahl der möglichen Lösungen ist die Anzahl der verschiedenen Zweige des konstruierten Baums. Es ist leicht zu sehen, dass es gleich m + 1 ist.

	Holz	Anzahl der Entscheidungen
x 1
x2
x 3
		…

Bei Denkschwierigkeiten Niyah und Konstruktion deBrüllen von Lösungen, mit denen Sie nach einer Lösung suchen können verwenden Wahrheitstabellen, für eine oder zwei Gleichungen.

Wir schreiben das Gleichungssystem um in die Form:

Und lassen Sie uns eine Wahrheitstabelle separat für eine Gleichung erstellen:

x 1	x2	(x 1 → x 2)

Lassen Sie uns eine Wahrheitstabelle für zwei Gleichungen erstellen:

x 1	x2	x 3	x1 → x2	x 2 → x 3	(x 1 → x 2) * (x 2 → x 3)

Unterrichtsthema: Logische Gleichungen lösen

Lehrreich - Lernen, wie man logische Gleichungen löst, Bildung von Fähigkeiten und Fertigkeiten zum Lösen logischer Gleichungen und Aufbau eines logischen Ausdrucks gemäß der Wahrheitstabelle;

Lehrreich - Bedingungen für die Entwicklung des kognitiven Interesses der Schüler schaffen, die Entwicklung von Gedächtnis, Aufmerksamkeit und logischem Denken fördern;

Lehrreich : zur Bildung der Fähigkeit beitragen, auf die Meinungen anderer zu hören, Erziehung des Willens und der Ausdauer, um die endgültigen Ergebnisse zu erzielen.

Unterrichtsart: kombinierter Unterricht

Ausrüstung: Computer, Multimedia-Beamer, Präsentation 6.

Während des Unterrichts

Wiederholung und Aktualisierung von Grundkenntnissen. Hausaufgaben kontrollieren (10 Minuten)

In den vorherigen Lektionen haben wir uns mit den Grundgesetzen der Algebra der Logik vertraut gemacht und gelernt, wie man diese Gesetze verwendet, um logische Ausdrücke zu vereinfachen.

Sehen wir uns die Hausaufgaben zur Vereinfachung logischer Ausdrücke an:

1. Welches der folgenden Wörter erfüllt die logische Bedingung:

(erster Konsonant → zweiter Konsonant)٨ (letzter Buchstabe Vokal → vorletzter Buchstabe Vokal)? Wenn es mehrere solcher Wörter gibt, geben Sie das kleinste davon an.

1) ANNA 2) MARIA 3) OLEG 4) STEPAN

Wir führen die Notation ein:

A ist der erste Buchstabe eines Konsonanten

B ist der zweite Buchstabe eines Konsonanten

S ist der letzte Vokal

D - vorletzter Vokal

Machen wir einen Ausdruck:

Machen wir eine Tabelle:

2. Geben Sie an, welcher logische Ausdruck dem Ausdruck entspricht

Vereinfachen wir das Schreiben des ursprünglichen Ausdrucks und der vorgeschlagenen Optionen:

3. Ein Fragment der Wahrheitstabelle des Ausdrucks F ist gegeben:

Welcher Ausdruck entspricht F?

Lassen Sie uns die Werte dieser Ausdrücke für die angegebenen Werte der Argumente bestimmen:

Einarbeitung in das Unterrichtsthema, Vorstellung neuen Materials (30 Minuten)

Wir beschäftigen uns weiterhin mit den Grundlagen der Logik und dem Thema unserer heutigen Lektion "Logische Gleichungen lösen". Nach dem Studium dieses Themas lernen Sie die grundlegenden Möglichkeiten zum Lösen logischer Gleichungen kennen, erwerben die Fähigkeiten zum Lösen dieser Gleichungen mithilfe der Sprache der logischen Algebra und die Fähigkeit, einen logischen Ausdruck auf der Wahrheitstabelle zu erstellen.

1. Lösen Sie die logische Gleichung

(¬K M) → (¬L M N)=0

Schreiben Sie Ihre Antwort als eine Zeichenfolge aus vier Zeichen: die Werte der Variablen K, L, M und N (in dieser Reihenfolge). So entspricht beispielsweise Zeile 1101 K = 1, L = 1, M = 0, N = 1.

Entscheidung:

Lassen Sie uns den Ausdruck umwandeln(¬K  M) → (¬L  M  N)

Der Ausdruck ist falsch, wenn beide Terme falsch sind. Der zweite Term ist gleich 0, wenn M=0, N=0, L=1. Im ersten Term ist K = 0, da M = 0, und
.

Antwort: 0100

2. Wie viele Lösungen hat die Gleichung (geben Sie in Ihrer Antwort nur die Zahl an)?

Lösung: Transformiere den Ausdruck

(A+B)*(C+D)=1

A+B=1 und C+D=1

Methode 2: Erstellung einer Wahrheitstabelle

3 Wege: Konstruktion von SDNF - eine perfekte disjunktive Normalform für eine Funktion - eine Disjunktion vollständiger regulärer elementarer Konjunktionen.

Lassen Sie uns den ursprünglichen Ausdruck umwandeln, öffnen Sie die Klammern, um die Disjunktion der Konjunktionen zu erhalten:

(A+B)*(C+D)=A*C+B*C+A*D+B*D=

Ergänzen wir die Konjunktionen zu vollständigen Konjunktionen (das Produkt aller Argumente), öffnen Sie die Klammern:

Betrachten Sie dieselben Konjunktionen:

Als Ergebnis erhalten wir eine SDNF mit 9 Konjunktionen. Daher hat die Wahrheitstabelle für diese Funktion einen Wert von 1 in 9 Zeilen von 2 4 = 16 Sätzen von Variablenwerten.

3. Wie viele Lösungen hat die Gleichung (geben Sie in Ihrer Antwort nur die Zahl an)?

Vereinfachen wir den Ausdruck:

,

3 Wege: Aufbau von SDNF

Betrachten Sie dieselben Konjunktionen:

Als Ergebnis erhalten wir eine SDNF mit 5 Konjunktionen. Daher hat die Wahrheitstabelle für diese Funktion einen Wert von 1 auf 5 Zeilen von 2 4 = 16 Sätzen von Variablenwerten.

Erstellen eines logischen Ausdrucks gemäß der Wahrheitstabelle:

Für jede Zeile der Wahrheitstabelle, die 1 enthält, bilden wir das Produkt der Argumente, und die Variablen gleich 0 werden mit Negation in das Produkt aufgenommen, und die Variablen gleich 1 werden nicht negiert. Der gewünschte Ausdruck F setzt sich aus der Summe der erhaltenen Produkte zusammen. Dann sollte dieser Ausdruck nach Möglichkeit vereinfacht werden.

Beispiel: Die Wahrheitstabelle eines Ausdrucks ist gegeben. Erstellen Sie einen logischen Ausdruck.

Entscheidung:

3. Hausaufgaben (5 Minuten)

Löse die Gleichung:

Wie viele Lösungen hat die Gleichung (antworten Sie nur auf die Zahl)?

Bilden Sie gemäß der gegebenen Wahrheitstabelle einen logischen Ausdruck und

vereinfache es.

Wege zur Lösung logischer Gleichungssysteme

Kirgizova E.V., Nemkova A.E.

Pädagogisches Institut Lesosibirsk -

Zweigstelle der Sibirischen Föderalen Universität, Russland

Die Fähigkeit, konsequent zu denken, schlüssig zu argumentieren, Hypothesen aufzustellen, negative Schlussfolgerungen zu widerlegen, kommt nicht von alleine, diese Fähigkeit wird durch die Wissenschaft der Logik entwickelt. Logik ist eine Wissenschaft, die die Methoden untersucht, um die Wahrheit oder Falschheit einiger Aussagen auf der Grundlage der Wahrheit oder Falschheit anderer Aussagen festzustellen.

Die Beherrschung der Grundlagen dieser Wissenschaft ist unmöglich, ohne logische Probleme zu lösen. Die Überprüfung der Bildung von Fähigkeiten, um ihr Wissen in einer neuen Situation anzuwenden, erfolgt durch Bestehen. Dies ist insbesondere die Fähigkeit, logische Probleme zu lösen. Die Aufgaben B15 in der Klausur sind Aufgaben mit erhöhter Komplexität, da sie logische Gleichungssysteme enthalten. Es gibt verschiedene Möglichkeiten, logische Gleichungssysteme zu lösen. Dies ist Reduktion auf eine Gleichung, Konstruktion einer Wahrheitstabelle, Zerlegung, sequentielle Lösung von Gleichungen usw.

Aufgabe:Lösen Sie ein System logischer Gleichungen:

Prüfen Methode der Reduktion auf eine Gleichung . Bei dieser Methode werden logische Gleichungen so transformiert, dass ihre rechte Seite gleich dem Wahrheitswert (also 1) ist. Verwenden Sie dazu die Operation der logischen Negation. Wenn die Gleichungen dann komplexe logische Operationen enthalten, ersetzen wir sie durch grundlegende: „UND“, „ODER“, „NICHT“. Der nächste Schritt besteht darin, die Gleichungen unter Verwendung der logischen Operation "AND" zu einer, dem System äquivalenten, zu kombinieren. Danach sollten Sie Transformationen der resultierenden Gleichung basierend auf den Gesetzen der Algebra der Logik vornehmen und eine spezifische Lösung für das System erhalten.

Lösung 1:Wende die Umkehrung auf beide Seiten der ersten Gleichung an:

Lassen Sie uns die Implikation durch die Grundoperationen "ODER", "NICHT" darstellen:

Da die linken Seiten der Gleichungen gleich 1 sind, können Sie sie mit der „UND“-Verknüpfung zu einer Gleichung kombinieren, die dem ursprünglichen System entspricht:

Wir öffnen die erste Klammer nach dem Gesetz von de Morgan und formen das Ergebnis um:

Die resultierende Gleichung hat eine Lösung: A= 0 , B=0 und C=1 .

Der nächste Weg ist Konstruktion von Wahrheitstafeln . Da logische Größen nur zwei Werte haben, können Sie einfach alle Möglichkeiten durchgehen und darunter diejenigen finden, für die das gegebene Gleichungssystem erfüllt ist. Das heißt, wir erstellen eine gemeinsame Wahrheitstabelle für alle Gleichungen des Systems und finden eine Linie mit den gewünschten Werten.

Lösung 2:Lassen Sie uns eine Wahrheitstabelle für das System erstellen:

0	0	1	1	0	1

Fett ist die Linie, für die die Bedingungen des Problems erfüllt sind. Also A =0 , B =0 und C =1 .

Weg Zersetzung . Die Idee ist, den Wert einer der Variablen festzulegen (gleich 0 oder 1 zu setzen) und dadurch die Gleichungen zu vereinfachen. Dann können Sie den Wert der zweiten Variablen festlegen und so weiter.

Lösung 3: Lassen A = 0, dann:

Aus der ersten Gleichung erhalten wir B =0, und ab dem zweiten - С=1. Systemlösung: A = 0 , B = 0 und C = 1 .

Sie können die Methode auch verwenden sequentielle Lösung von Gleichungen , wobei bei jedem Schritt eine Variable zu der betrachteten Menge hinzugefügt wird. Dazu ist es notwendig, die Gleichungen so umzuformen, dass die Variablen in alphabetischer Reihenfolge eingegeben werden. Als nächstes bauen wir einen Entscheidungsbaum auf und fügen ihm nacheinander Variablen hinzu.

Die erste Gleichung des Systems hängt nur von A und B ab, die zweite Gleichung von A und C. Variable A kann 2 Werte 0 und 1 annehmen:

Aus der ersten Gleichung folgt, dass , also wann A = 0 erhalten wir B = 0 und für A = 1 haben wir B = 1 . Die erste Gleichung hat also zwei Lösungen bezüglich der Variablen A und B .

Wir zeichnen die zweite Gleichung, aus der wir die Werte von C für jede Option bestimmen. Für A = 1 kann die Implikation nicht falsch sein, das heißt, der zweite Zweig des Baums hat keine Lösung. Beim A= 0 Wir bekommen die einzige Lösung C= 1 :

Damit haben wir die Lösung des Systems: A = 0 , B = 0 und C = 1 .

In der USE in der Informatik ist es sehr oft notwendig, die Anzahl der Lösungen eines logischen Gleichungssystems zu bestimmen, ohne die Lösungen selbst zu finden, auch dafür gibt es bestimmte Methoden. Der Hauptweg, um die Anzahl der Lösungen für ein System logischer Gleichungen zu finden, ist Änderung von Variablen. Zunächst ist es notwendig, jede der Gleichungen auf der Grundlage der Gesetze der Algebra der Logik so weit wie möglich zu vereinfachen und dann die komplexen Teile der Gleichungen durch neue Variablen zu ersetzen und die Anzahl der Lösungen für das neue System zu bestimmen. Kehren Sie dann zum Ersatz zurück und bestimmen Sie die Anzahl der Lösungen dafür.

Aufgabe:Wie viele Lösungen hat die Gleichung ( A → B ) + (C → D ) = 1? Wobei A, B, C, D boolesche Variablen sind.

Entscheidung:Lassen Sie uns neue Variablen einführen: X = A → B und Y = C → D . Unter Berücksichtigung der neuen Variablen kann die Gleichung geschrieben werden als: X + Y = 1.

Die Disjunktion ist in drei Fällen wahr: (0;1), (1;0) und (1;1), while X und Y ist eine Implikation, das heißt, sie ist in drei Fällen wahr und in einem falsch. Daher entspricht der Fall (0;1) drei möglichen Kombinationen von Parametern. Fall (1;1) – entspricht neun möglichen Kombinationen der Parameter der ursprünglichen Gleichung. Daher gibt es 3+9=15 mögliche Lösungen dieser Gleichung.

Der folgende Weg, um die Anzahl der Lösungen für ein System logischer Gleichungen zu bestimmen, ist − binärer Baum. Betrachten wir diese Methode anhand eines Beispiels.

Aufgabe:Wie viele verschiedene Lösungen hat das logische Gleichungssystem:

Das gegebene Gleichungssystem ist äquivalent zu der Gleichung:

( x 1 → x 2 )*( x 2 → x 3 )*…*( x m -1 → x m) = 1.

Stellen wir uns das vorx 1 wahr ist, dann erhalten wir das aus der ersten Gleichungx 2 auch wahr, von der zweiten -x 3 =1, und so weiter bis x m= 1. Daraus ergibt sich die Menge (1; 1; …; 1) aus m Einheiten ist die Lösung des Systems. Lassen Sie jetztx 1 =0, dann haben wir aus der ersten Gleichungx 2 =0 oder x 2 =1.

Wann x 2 wahr, erhalten wir, dass auch die anderen Variablen wahr sind, das heißt, die Menge (0; 1; ...; 1) ist die Lösung des Systems. Beimx 2 =0 wir bekommen das x 3 =0 oder x 3 =, und so weiter. Wenn wir mit der letzten Variablen fortfahren, stellen wir fest, dass die Lösungen der Gleichung die folgenden Sätze von Variablen sind ( m +1 Lösung, in jeder Lösung m Variablenwerte):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Dieser Ansatz lässt sich gut durch den Aufbau eines binären Baums veranschaulichen. Die Anzahl der möglichen Lösungen ist die Anzahl der verschiedenen Zweige des konstruierten Baums. Es ist leicht zu sehen, dass es so ist m+1.

Variablen	Holz	Anzahl der Entscheidungen
x 1
x2
x 3

Bei Schwierigkeiten beim Argumentieren und Erstellen eines Entscheidungsbaums können Sie mithilfe von nach einer Lösung suchen Wahrheitstabellen, für eine oder zwei Gleichungen.

Wir schreiben das Gleichungssystem um in die Form:

Und lassen Sie uns eine Wahrheitstabelle separat für eine Gleichung erstellen:

x 1	x2	(x 1 → x 2)

Lassen Sie uns eine Wahrheitstabelle für zwei Gleichungen erstellen:

x 1	x2	x 3	x1 → x2	x 2 → x 3	(x 1 → x 2) * (x 2 → x 3)

Als nächstes können Sie sehen, dass eine Gleichung in den folgenden drei Fällen wahr ist: (0; 0), (0; 1), (1; 1). Das System aus zwei Gleichungen ist in vier Fällen wahr (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). In diesem Fall ist sofort klar, dass es eine Lösung gibt, die nur aus Nullen und mehr besteht m Lösungen, bei denen eine Einheit hinzugefügt wird, beginnend mit der letzten Position, bis alle möglichen Plätze besetzt sind. Es kann davon ausgegangen werden, dass die allgemeine Lösung die gleiche Form haben wird, aber damit ein solcher Ansatz zu einer Lösung wird, ist der Beweis erforderlich, dass die Annahme wahr ist.

Zusammenfassend möchte ich darauf hinweisen, dass nicht alle betrachteten Methoden universell sind. Bei der Lösung jedes Systems logischer Gleichungen sollten seine Merkmale berücksichtigt werden, auf deren Grundlage die Lösungsmethode ausgewählt werden sollte.

Literatur:

1. Logische Aufgaben / O.B. Bogomolov - 2. Aufl. – M.: BINOM. Wissenslabor, 2006. - 271 S.: Abb.

2. Poljakow K.Ju. Systeme logischer Gleichungen / Lehr- und Methodenzeitschrift für Lehrende der Informatik: Informatik Nr. 14, 2011

Methoden zum Lösen von Systemen logischer Gleichungen

Sie können ein System logischer Gleichungen zum Beispiel mithilfe einer Wahrheitstabelle (wenn die Anzahl der Variablen nicht zu groß ist) oder mithilfe eines Entscheidungsbaums lösen, nachdem Sie jede Gleichung vereinfacht haben.

1. Methode der Änderung von Variablen.

Die Einführung neuer Variablen ermöglicht es, das Gleichungssystem zu vereinfachen, indem die Anzahl der Unbekannten reduziert wird.Neue Variablen müssen unabhängig voneinander sein. Nach dem Lösen des vereinfachten Systems ist es notwendig, wieder zu den ursprünglichen Variablen zurückzukehren.

Betrachten Sie die Anwendung dieser Methode auf ein bestimmtes Beispiel.

Beispiel.

((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0

((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0

((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0

((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0

Entscheidung:

Lassen Sie uns neue Variablen einführen: А=(X1≡X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D = (X7 ≡ X8); E=(X9 ≡ X10).

(Achtung! Jede ihrer Variablen x1, x2, ..., x10 darf nur in einer der neuen Variablen A, B, C, D, E enthalten sein, d.h. die neuen Variablen sind unabhängig voneinander).

Dann sieht das Gleichungssystem so aus:

(A ∧ B) ∨ (¬A ∧ ¬B)=0

(B ∧ C) ∨ (¬B ∧ ¬C)=0

(C ∧ D) ∨ (¬C ∧ ¬D)=0

(D ∧ E) ∨ (¬D ∧ ¬E)=0

Lassen Sie uns einen Entscheidungsbaum des resultierenden Systems erstellen:

Betrachten Sie die Gleichung A=0, d.h. (X1≡ X2)=0. Es hat 2 Wurzeln:

		X1 ≡ X2

Aus derselben Tabelle ist ersichtlich, dass die Gleichung A \u003d 1 auch 2 Wurzeln hat. Lassen Sie uns die Anzahl der Wurzeln im Entscheidungsbaum anordnen:

Um die Anzahl der Lösungen für einen Zweig zu finden, müssen Sie die Anzahl der Lösungen auf jeder Ebene multiplizieren. Der linke Zweig hat 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 Lösungen; der rechte Zweig hat auch 32 Lösungen. Jene. das ganze System hat 32+32=64 Lösungen.

Antwort: 64.

2. Argumentationsmethode.

Die Komplexität des Lösens von Systemen logischer Gleichungen liegt in der Sperrigkeit des vollständigen Entscheidungsbaums. Mit der Argumentationsmethode können Sie nicht den gesamten Baum vollständig erstellen, aber gleichzeitig verstehen, wie viele Zweige er haben wird. Betrachten wir diese Methode an konkreten Beispielen.

Beispiel 1 Wie viele verschiedene Wertesätze von booleschen Variablen x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 gibt es, die alle folgenden Bedingungen erfüllen?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

x1\/y1 =1

Die Antwort muss nicht alle verschiedenen Wertesätze der Variablen x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 auflisten, unter denen das gegebene Gleichheitssystem erfüllt ist. Als Antwort müssen Sie die Anzahl solcher Sätze angeben.

Entscheidung :

Die erste und die zweite Gleichung enthalten unabhängige Variablen, die durch eine dritte Bedingung in Beziehung stehen. Lassen Sie uns einen Entscheidungsbaum für die erste und zweite Gleichung konstruieren.

Um den Entscheidungsbaum des Systems aus der ersten und zweiten Gleichung darzustellen, ist es notwendig, jeden Zweig des ersten Baums mit einem Baum für Variablen fortzusetzen beim . Der auf diese Weise konstruierte Baum enthält 36 Äste. Einige dieser Zweige erfüllen die dritte Gleichung des Systems nicht. Beachten Sie beim ersten Baum die Anzahl der Zweige des Baums"beim" , die die dritte Gleichung erfüllen:

Zur Verdeutlichung: Für die Erfüllung der dritten Bedingung bei x1=0 muss y1=1 sein, also alle Äste des Baumes"X" , wobei x1=0 mit nur einem Ast aus dem Baum fortgesetzt werden kann"beim" . Und nur für einen Ast des Baumes"X" (rechts) passen alle Zweige des Baums"beim". Somit enthält der vollständige Baum des gesamten Systems 11 Zweige. Jeder Zweig repräsentiert eine Lösung des ursprünglichen Gleichungssystems. Das ganze System hat also 11 Lösungen.

Antwort: 11.

Beispiel 2 Wie viele verschiedene Lösungen hat das Gleichungssystem?

(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬X10)= 1

(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬X10)= 1.

………………

(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬X10)= 1

(X1 ≡ X10) = 0

wobei x1, x2, …, x10 boolesche Variablen sind? Die Antwort muss nicht alle verschiedenen Sätze von Variablenwerten auflisten, für die diese Gleichheit gilt. Als Antwort müssen Sie die Anzahl solcher Sätze angeben.

Entscheidung : Vereinfachen wir das System. Lassen Sie uns eine Wahrheitstabelle des Teils der ersten Gleichung erstellen:

		X1 ∧ X10	¬X1 ∧ ¬X10	(X1 ∧ X10) ∨ (¬X1 ∧ ¬X10)

Achten Sie auf die letzte Spalte, sie entspricht dem Ergebnis der Aktion X1 ≡ X10.

X1 ≡ X10

Nach Vereinfachung erhalten wir:

(X1 ≡ X2) ∨ (X1 ≡ X10)=1

(X2 ≡ X3) ∨ (X2 ≡ X10)=1

(X3 ≡ X4) ∨ (X3 ≡ X10)=1

……

(X9 ≡ X10) ∨ (X9 ≡ X10)=1

(X1 ≡ X10) = 0

Betrachten Sie die letzte Gleichung:(X1 ≡ X10) = 0 , d.h. x1 sollte nicht gleich x10 sein. Damit die erste Gleichung gleich 1 ist, muss die Gleichheit gelten(X1 ≡ X2)=1, d.h. x1 muss mit x2 übereinstimmen.

Lassen Sie uns einen Entscheidungsbaum für die erste Gleichung erstellen:

Betrachten Sie die zweite Gleichung: für x10=1 und für x2=0 die Klammermuss gleich 1 sein (d.h. x2 ist gleich x3); bei x10=0 und bei x2=1 Klammer(X2 ≡ X10)=0 , also Klammer (X2 ≡ X3) muss gleich 1 sein (d.h. x2 ist gleich x3):

Auf diese Weise argumentierend konstruieren wir einen Entscheidungsbaum für alle Gleichungen:

Somit hat das Gleichungssystem nur 2 Lösungen.

Antwort: 2.

Beispiel 3

Wie viele verschiedene Wertesätze von booleschen Variablen x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 gibt es, die alle folgenden Bedingungen erfüllen?

(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1

(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1

(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1

(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1

(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1

Entscheidung:

Lassen Sie uns einen Entscheidungsbaum der 1. Gleichung erstellen:

Betrachten Sie die zweite Gleichung:

• Wenn x1=0 : zweite und dritte Klammer sind 0; damit die erste Klammer gleich 1 ist, muss y1=1 , z1=1 (d.h. in diesem Fall - 1 Lösung)
• Mit x1=1 : erste Klammer wird 0 sein; zweite oder die dritte Klammer muss gleich 1 sein; die zweite Klammer ist gleich 1, wenn y1=0 und z1=1; die dritte Klammer ist gleich 1 für y1=1 und z1=0 (d. h. in diesem Fall - 2 Lösungen).

Analog für die restlichen Gleichungen. Beachten Sie die Anzahl der Lösungen, die für jeden Knoten des Baums erhalten wurden:

Um die Anzahl der Lösungen für jeden Zweig zu ermitteln, multiplizieren wir die erhaltenen Zahlen separat für jeden Zweig (von links nach rechts).

1 Zweig: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 Lösung

2 Zweig: 1 ⋅ 1 ⋅ 1 ⋅ 2 = 2 Lösungen

3. Zweig: 1 ⋅ 1 ⋅ 2 ⋅ 2 = 4 Lösungen

4 Zweig: 1 ⋅ 2 ⋅ 2 ⋅ 2 = 8 Lösungen

5. Zweig: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 Lösungen

Addieren wir die erhaltenen Zahlen: insgesamt 31 Lösungen.

Antwort: 31.

3. Regelmäßige Erhöhung der Anzahl der Wurzeln

In einigen Systemen hängt die Anzahl der Wurzeln der nächsten Gleichung von der Anzahl der Wurzeln der vorherigen Gleichung ab.

Beispiel 1 Wie viele verschiedene Wertesätze von booleschen Variablen x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 gibt es, die alle folgenden Bedingungen erfüllen?

¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0

¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0

¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0

Vereinfachen erste Gleichung:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Dann nimmt das System die Form an:

¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0

¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0

¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0

Usw.

Jede folgende Gleichung hat 2 Wurzeln mehr als die vorherige.

4 Gleichung hat 12 Wurzeln;

Gleichung 5 hat 14 Nullstellen

8 Gleichung hat 20 Wurzeln.

Antwort: 20 Wurzeln.

Manchmal wächst die Anzahl der Wurzeln nach dem Gesetz der Fibonacci-Zahlen.

Das Lösen eines Systems logischer Gleichungen erfordert einen kreativen Ansatz.