Löse die logische Gleichung auf zwei Arten. Logik. Logische Funktionen. Gleichungen lösen

Wie man einige Probleme in den Abschnitten A und B der Informatikprüfung löst

Lektion Nummer 3. Logik. Logische Funktionen. Gleichungen lösen

Eine große Anzahl von USE-Aufgaben widmet sich der Logik von Aussagen. Um die meisten von ihnen zu lösen, reicht es aus, die Grundgesetze der Aussagenlogik zu kennen, die Wahrheitstabellen logischer Funktionen von einer und zwei Variablen zu kennen. Ich werde die Grundgesetze der Aussagenlogik angeben.

1. Kommutativität von Disjunktion und Konjunktion:
   ein ˅ b ≡ b ˅ ein
   a^b ≡ b^a
2. Das Distributivgesetz bezüglich Disjunktion und Konjunktion:
   a ˅ (b^c) ≡ (a ˅ b) ^(a ˅ c)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. Negative Verneinung:
   ¬(¬a) ≡ ein
4. Konsistenz:
   a ^ ¬a ≡ falsch
5. Exklusiver Dritter:
   a ˅ ¬a ≡ wahr
6. Gesetze von De Morgan:
   ¬(a ˅ b) ≡ ¬a ˄ ¬b
   ¬(a ˄b) ≡ ¬a ˅ ¬b
7. Vereinfachung:
   ein ˄ ein ≡ ein
   ein ˅ ein ≡ ein
   a ˄ wahr ≡ a
   a ˄ falsch ≡ falsch
8. Absorption:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. Ersetzen der Implikation
   a → b ≡ ¬a ˅ b
10. Identitätswechsel
    a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Darstellung logischer Funktionen

Jede logische Funktion von n Variablen - F(x 1 , x 2 , ... x n) kann durch eine Wahrheitstabelle definiert werden. Eine solche Tabelle enthält 2 n Sätze von Variablen, für die jeweils der Wert der Funktion auf diesem Satz angegeben ist. Diese Methode ist gut, wenn die Anzahl der Variablen relativ klein ist. Selbst für n > 5 wird die Darstellung schlecht sichtbar.

Eine andere Möglichkeit besteht darin, die Funktion durch eine Formel zu definieren, wobei bekannte, ziemlich einfache Funktionen verwendet werden. Das System von Funktionen (f 1 , f 2 , … f k ) heißt vollständig, wenn jede logische Funktion durch eine Formel ausgedrückt werden kann, die nur Funktionen f i enthält.

Das System der Funktionen (¬, ˄, ˅) ist vollständig. Gesetze 9 und 10 sind Beispiele dafür, wie Implikation und Identität durch Negation, Konjunktion und Disjunktion ausgedrückt werden.

Tatsächlich ist auch das System zweier Funktionen vollständig - Negation und Konjunktion oder Negation und Disjunktion. Darstellungen folgen aus den Gesetzen von De Morgan, die es ermöglichen, eine Konjunktion durch Negation und Disjunktion auszudrücken und dementsprechend eine Disjunktion durch Negation und Konjunktion auszudrücken:

(a ˅ b) ≡ ¬(¬a ˄ ¬b)
(a ˄ b) ≡ ¬(¬a ˅ ¬b)

Paradoxerweise ist ein System, das nur aus einer Funktion besteht, vollständig. Es gibt zwei binäre Funktionen - Antikonjunktion und Antidisjunktion, genannt Pierce-Pfeil und Schaeffer-Strich, die ein hohles System darstellen.

Zu den Grundfunktionen von Programmiersprachen gehören in der Regel Identität, Negation, Konjunktion und Disjunktion. In den Aufgaben der Prüfung, zusammen mit diesen Funktionen, gibt es oft eine Implikation.

Schauen wir uns ein paar einfache Aufgaben an, die sich auf logische Funktionen beziehen.

Aufgabe 15:

Ein Fragment der Wahrheitstabelle ist gegeben. Welche der drei angegebenen Funktionen entspricht diesem Fragment?

x1	x2	x3	x4	F
1	1	0	0	1
0	1	1	1	1
1	0	0	1	0

1. (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
2. (¬X 1 ˄ X 2) ˅ (¬X 3 ˄ X 4)
3. ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

Funktion Nummer 3.

Um das Problem zu lösen, müssen Sie die Wahrheitstabellen der Grundfunktionen kennen und die Prioritäten der Operationen berücksichtigen. Ich möchte Sie daran erinnern, dass die Konjunktion (logische Multiplikation) eine höhere Priorität hat und vor der Disjunktion (logische Addition) ausgeführt wird. Beim Rechnen ist leicht zu erkennen, dass die Funktionen mit den Nummern 1 und 2 auf der dritten Menge den Wert 1 haben und deshalb nicht dem Fragment entsprechen.

Aufgabe 16:

Welche der folgenden Zahlen erfüllt die Bedingung:

(Ziffern beginnend mit der höchstwertigen Ziffer in absteigender Reihenfolge) → (Zahl – gerade) ˄ (niedrigste Ziffer – gerade) ˄ (höchste Ziffer – ungerade)

Wenn es mehrere solche Zahlen gibt, geben Sie die größte an.

1. 13579
2. 97531
3. 24678
4. 15386

Die Bedingung wird durch die Zahl 4 erfüllt.

Die ersten beiden Zahlen erfüllen die Bedingung nicht, da die niedrigste Ziffer ungerade ist. Eine Konjunktion von Bedingungen ist falsch, wenn einer der Terme der Konjunktion falsch ist. Bei der dritten Zahl ist die Bedingung für die höchste Ziffer nicht erfüllt. Für die vierte Zahl sind die an die Neben- und Hauptziffern der Zahl gestellten Bedingungen erfüllt. Auch der erste Term der Konjunktion ist wahr, da eine Implikation wahr ist, wenn ihre Prämisse falsch ist, was hier der Fall ist.

Problem 17: Zwei Zeugen sagten wie folgt aus:

Erster Zeuge: Wenn A schuldig ist, dann ist B sicher schuldig und C unschuldig.

Zweiter Zeuge: Zwei sind schuldig. Und einer der verbleibenden ist definitiv schuldig und schuldig, aber ich kann nicht genau sagen, wer.

Welche Schlüsse über die Schuld von A, B und C lassen sich aus den Beweisen ziehen?

Antwort: Aus der Aussage folgt, dass A und B schuldig sind, aber C unschuldig ist.

Lösung: Natürlich kann die Antwort mit gesundem Menschenverstand gegeben werden. Aber schauen wir uns an, wie dies streng und formell geschehen kann.

Zunächst müssen die Aussagen formalisiert werden. Lassen Sie uns drei boolesche Variablen A, B und C einführen, von denen jede wahr (1) ist, wenn der entsprechende Verdächtige schuldig ist. Dann wird die Aussage des ersten Zeugen durch die Formel gegeben:

A → (B ˄ ¬C)

Die Aussage des zweiten Zeugen ergibt sich aus der Formel:

A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))

Die Aussagen beider Zeugen werden als wahr angenommen und stellen die Verknüpfung der entsprechenden Formeln dar.

Lassen Sie uns eine Wahrheitstabelle für diese Messwerte erstellen:

EIN	B	C	F1	F2	F1 F2
0	0	0	1	0	0
0	0	1	1	0	0
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	1	1	1
1	1	1	0	0	0

Die zusammenfassenden Beweise sind nur in einem Fall wahr, was zu einer klaren Antwort führt - A und B sind schuldig und C ist unschuldig.

Aus der Analyse dieser Tabelle folgt auch, dass die Aussage des zweiten Zeugen aussagekräftiger ist. Aus der Wahrheit seiner Aussage folgen nur zwei mögliche Optionen - A und B sind schuldig und C ist unschuldig, oder A und C sind schuldig und B ist unschuldig. Die Aussage des ersten Zeugen ist weniger informativ – es gibt 5 verschiedene Optionen, die seiner Aussage entsprechen. Zusammen geben die Aussagen beider Zeugen eine eindeutige Antwort auf die Schuld der Verdächtigen.

Logische Gleichungen und Gleichungssysteme

Sei F(x 1 , x 2 , …x n) eine logische Funktion von n Variablen. Die logische Gleichung lautet:

F (x 1, x 2, ... x n) \u003d C,

Die Konstante C hat den Wert 1 oder 0.

Eine logische Gleichung kann 0 bis 2n verschiedene Lösungen haben. Wenn C gleich 1 ist, dann sind die Lösungen all jene Sätze von Variablen aus der Wahrheitstabelle, auf denen die Funktion F den Wert wahr (1) annimmt. Die verbleibenden Sätze sind Lösungen der Gleichung für C gleich Null. Wir können immer nur Gleichungen der Form betrachten:

F(x 1 , x 2 , …x n) = 1

In der Tat sei die Gleichung gegeben:

F(x 1 , x 2 , …x n) = 0

In diesem Fall können Sie zur äquivalenten Gleichung gehen:

¬F(x 1 , x 2 , …x n) = 1

Betrachten Sie ein System von k logischen Gleichungen:

F 1 (x 1, x 2, ... x n) \u003d 1

F 2 (x 1, x 2, ... x n) \u003d 1

F k (x 1 , x 2 , …x n) = 1

Die Lösung des Systems ist ein Satz von Variablen, für die alle Gleichungen des Systems erfüllt sind. In Bezug auf logische Funktionen sollte man, um eine Lösung für das System logischer Gleichungen zu erhalten, eine Menge finden, auf der die logische Funktion Ф wahr ist und die Konjunktion der ursprünglichen Funktionen F darstellt:

Ä = F 1 ˄ F 2 ˄ … F k

Wenn die Anzahl der Variablen klein ist, z. B. weniger als 5, ist es nicht schwierig, eine Wahrheitstabelle für die Funktion Ф zu erstellen, mit der Sie sagen können, wie viele Lösungen das System hat und welche Mengen Lösungen liefern.

Bei manchen Aufgaben des Einheitlichen Staatsexamens zur Lösung eines logischen Gleichungssystems erreicht die Anzahl der Variablen den Wert 10. Dann wird das Erstellen einer Wahrheitstafel zu einer fast unlösbaren Aufgabe. Die Lösung des Problems erfordert einen anderen Ansatz. Für ein beliebiges Gleichungssystem gibt es keinen allgemeinen Weg, außer der Aufzählung, der es erlaubt, solche Probleme zu lösen.

Bei den in der Prüfung vorgeschlagenen Aufgaben basiert die Lösung in der Regel auf der Berücksichtigung der Besonderheiten des Gleichungssystems. Ich wiederhole, abgesehen von der Aufzählung aller Varianten eines Satzes von Variablen gibt es keinen allgemeinen Weg zur Lösung des Problems. Die Lösung muss basierend auf den Besonderheiten des Systems erstellt werden. Oft ist es sinnvoll, eine vorläufige Vereinfachung eines Gleichungssystems mit bekannten Gesetzmäßigkeiten der Logik vorzunehmen. Eine andere nützliche Technik zum Lösen dieses Problems ist wie folgt. Wir interessieren uns nicht für alle Mengen, sondern nur für diejenigen, auf denen die Funktion Ф den Wert 1 hat. Anstatt eine vollständige Wahrheitstabelle zu konstruieren, werden wir ihr Analogon bauen - einen binären Entscheidungsbaum. Jeder Zweig dieses Baums entspricht einer Lösung und gibt eine Menge an, auf der die Funktion Ä den Wert 1 hat. Die Anzahl der Zweige im Entscheidungsbaum stimmt mit der Anzahl der Lösungen des Gleichungssystems überein.

Was ein binärer Entscheidungsbaum ist und wie er aufgebaut ist, erkläre ich anhand von Beispielen für mehrere Aufgaben.

Aufgabe 18

Wie viele verschiedene Wertesätze von booleschen Variablen x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 gibt es, die ein System aus zwei Gleichungen erfüllen?

Antwort: Das System hat 36 verschiedene Lösungen.

Lösung: Das Gleichungssystem enthält zwei Gleichungen. Lassen Sie uns die Anzahl der Lösungen für die erste Gleichung finden, abhängig von 5 Variablen – x 1 , x 2 , …x 5 . Die erste Gleichung kann wiederum als System von 5 Gleichungen betrachtet werden. Wie gezeigt wurde, stellt das Gleichungssystem tatsächlich eine Verknüpfung logischer Funktionen dar. Auch die umgekehrte Aussage gilt – die Konjunktion von Bedingungen kann als Gleichungssystem betrachtet werden.

Lassen Sie uns einen Entscheidungsbaum für die Implikation (x1→ x2) erstellen, den ersten Term der Konjunktion, der als erste Gleichung betrachtet werden kann. So sieht die grafische Darstellung dieses Baums aus:

Der Baum besteht aus zwei Ebenen entsprechend der Anzahl der Variablen in der Gleichung. Die erste Ebene beschreibt die erste Variable X 1 . Zwei Zweige dieser Ebene spiegeln die möglichen Werte dieser Variablen wider - 1 und 0. Auf der zweiten Ebene spiegeln die Zweige des Baums nur die möglichen Werte der Variablen X 2 wider, für die die Gleichung den Wert wahr annimmt. Da die Gleichung eine Implikation definiert, erfordert der Zweig, auf dem X 1 den Wert 1 hat, dass X 2 auf diesem Zweig den Wert 1 hat.Der Zweig, auf dem X 1 den Wert 0 hat, erzeugt zwei Zweige mit X 2 Werten gleich 0 und 1 Der konstruierte Baum gibt drei Lösungen an, bei denen die Implikation X 1 → X 2 den Wert 1 annimmt. Auf jedem Zweig wird der entsprechende Satz von Werten der Variablen ausgeschrieben, was die Lösung der Gleichung ergibt.

Diese Mengen sind: ((1, 1), (0, 1), (0, 0))

Fahren wir mit dem Aufbau des Entscheidungsbaums fort, indem wir die folgende Gleichung hinzufügen, die folgende Implikation X 2 → X 3 . Die Besonderheit unseres Gleichungssystems besteht darin, dass jede neue Gleichung des Systems eine Variable aus der vorherigen Gleichung verwendet und eine neue Variable hinzufügt. Da die Variable X 2 bereits Werte im Baum hat, hat die Variable X 3 in allen Zweigen, in denen die Variable X 2 den Wert 1 hat, auch den Wert 1. Für solche Zweige wird der Aufbau des Baums fortgesetzt die nächste Ebene, aber es erscheinen keine neuen Zweige. Die einzige Verzweigung, in der die Variable X 2 den Wert 0 hat, führt zu einer Verzweigung in zwei Zweige, in denen die Variable X 3 die Werte 0 und 1 erhält. Somit fügt jede Addition einer neuen Gleichung aufgrund ihrer Spezifität eine hinzu Lösung. Ursprüngliche erste Gleichung:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
hat 6 Lösungen. So sieht der vollständige Entscheidungsbaum für diese Gleichung aus:

Die zweite Gleichung unseres Systems ist ähnlich wie die erste:

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

Der einzige Unterschied besteht darin, dass die Gleichung Y-Variablen verwendet.Diese Gleichung hat auch 6 Lösungen. Da jede variable Lösung X i mit jeder variablen Lösung Y j kombiniert werden kann, beträgt die Gesamtzahl der Lösungen 36.

Beachten Sie, dass der konstruierte Entscheidungsbaum nicht nur die Anzahl der Lösungen (entsprechend der Anzahl der Zweige) angibt, sondern auch die Lösungen selbst, die auf jedem Zweig des Baums ausgeschrieben sind.

Aufgabe 19

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

Diese Aufgabe ist eine Modifikation der vorherigen Aufgabe. Der Unterschied besteht darin, dass eine weitere Gleichung hinzugefügt wird, die die X- und Y-Variablen in Beziehung setzt.

Aus der Gleichung X 1 → Y 1 folgt, dass wenn X 1 den Wert 1 hat (eine solche Lösung existiert), dann hat Y 1 den Wert 1. Somit gibt es eine Menge, auf der X 1 und Y 1 die Werte haben 1. Wenn X 1 gleich 0 ist, kann Y 1 jeden Wert haben, sowohl 0 als auch 1. Daher entspricht jeder Satz mit X 1 gleich 0, und es gibt 5 solcher Sätze, allen 6 Sätzen mit Y-Variablen , die Gesamtzahl der Lösungen beträgt 31 .

Aufgabe 20

(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1

Lösung: In Erinnerung an die grundlegende Äquivalenz schreiben wir unsere Gleichung wie folgt:

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1

Die zyklische Implikationskette bedeutet, dass die Variablen identisch sind, daher ist unsere Gleichung äquivalent zu:

X1 ≡ X2 ≡ X3 ≡ X4 ≡ X5 = 1

Diese Gleichung hat zwei Lösungen, wenn alle X i entweder 1 oder 0 sind.

Aufgabe 21

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1

Lösung: Genau wie in Problem 20 gehen wir von zyklischen Implikationen zu Identitäten über, indem wir die Gleichung in der Form umschreiben:

(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1

Lassen Sie uns einen Entscheidungsbaum für diese Gleichung erstellen:

Aufgabe 22

Wie viele Lösungen hat das folgende Gleichungssystem?

((X1 ≡X2) ˄ (X 3 ≡X 4)) ˅(¬(X1 ≡X 2) ˄ ¬(X 3 ≡X4)) = 0

((X 3 ≡X4) ˄ (X5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X5 ≡X6)) = 0

((X5 ≡X6) ˄ (X7 ≡X 8)) ˅(¬(X5 ≡X 6) ˄ ¬(X7 ≡X8)) = 0

((X7 ≡X 8) ˄ (X9 ≡X 10)) ˅(¬(X7 ≡X 8) ˄ ¬(X9 ≡X10)) = 0

Antwort: 64

Lösung: Gehen wir von 10 Variablen auf 5 Variablen, indem wir die folgende Variablenänderung einführen:

Y1 = (X1 ≡ X2); Y2 \u003d (X3 ≡ X4); Y3 = (X5 ≡ X6); Y 4 \u003d (X 7 ≡ X 8); Y 5 \u003d (X 9 ≡ X 10);

Dann nimmt die erste Gleichung die Form an:

(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0

Die Gleichung kann vereinfacht werden, indem man sie schreibt als:

(Y1 ≡ Y2) = 0

Übergehend zur traditionellen Form schreiben wir das System nach Vereinfachungen in der Form:

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

Der Entscheidungsbaum für dieses System ist einfach und besteht aus zwei Zweigen mit wechselnden Variablenwerten:

Um zu den ursprünglichen X-Variablen zurückzukehren, beachten Sie, dass jeder Wert der Y-Variablen 2 Werten der X-Variablen entspricht, sodass jede Lösung in den Y-Variablen 2 5 Lösungen in den X-Variablen generiert Zwei Zweige generieren 2 * 2 5 Lösungen , also beträgt die Gesamtzahl der Lösungen 64.

Wie Sie sehen, erfordert jede Aufgabe zur Lösung eines Gleichungssystems eine eigene Herangehensweise. Ein gängiger Trick besteht darin, äquivalente Transformationen durchzuführen, um die Gleichungen zu vereinfachen. Eine gängige Technik ist die Konstruktion von Entscheidungsbäumen. Der angewandte Ansatz ähnelt teilweise der Konstruktion einer Wahrheitstabelle mit der Besonderheit, dass nicht alle Mengen möglicher Werte von Variablen konstruiert werden, sondern nur diejenigen, auf denen die Funktion den Wert 1 (wahr) annimmt. Oft ist es bei den vorgeschlagenen Problemen nicht erforderlich, einen vollständigen Entscheidungsbaum zu erstellen, da es bereits in der Anfangsphase möglich ist, die Regelmäßigkeit des Auftretens neuer Zweige auf jeder nächsten Ebene festzustellen, wie dies beispielsweise bei Problem 18 der Fall war .

Im Allgemeinen sind Probleme zum Finden von Lösungen für ein System logischer Gleichungen gute mathematische Übungen.

Wenn das Problem manuell schwer zu lösen ist, können Sie die Lösung des Problems dem Computer anvertrauen, indem Sie ein geeignetes Programm zum Lösen von Gleichungen und Gleichungssystemen schreiben.

Es ist einfach, ein solches Programm zu schreiben. Ein solches Programm wird alle in der Prüfung angebotenen Aufgaben problemlos bewältigen.

Seltsamerweise, aber die Aufgabe, Lösungen für logische Gleichungssysteme zu finden, ist auch für einen Computer schwierig, es stellt sich heraus, dass ein Computer seine Grenzen hat. Aufgaben mit 20-30 Variablen kann der Computer problemlos bewältigen, bei größeren Aufgaben wird er jedoch anfangen, lange nachzudenken. Der Punkt ist, dass die Funktion 2 n, die die Anzahl der Mengen angibt, ein Exponent ist, der schnell mit n wächst. So schnell, dass ein normaler PC eine Aufgabe mit 40 Variablen an einem Tag nicht bewältigen kann.

C#-Programm zum Lösen logischer Gleichungen

Es ist aus vielen Gründen sinnvoll, ein Programm zum Lösen logischer Gleichungen zu schreiben, und sei es nur, weil es verwendet werden kann, um die Korrektheit Ihrer eigenen Lösung der USE-Testprobleme zu überprüfen. Ein weiterer Grund ist, dass ein solches Programm ein hervorragendes Beispiel für ein Programmierproblem ist, das die Anforderungen für Probleme der Kategorie C im USE erfüllt.

Die Idee, ein Programm zu erstellen, ist einfach - es basiert auf einer vollständigen Aufzählung aller möglichen Sätze von Variablenwerten. Da die Anzahl der Variablen n für eine gegebene logische Gleichung oder ein gegebenes Gleichungssystem bekannt ist, ist auch die Anzahl der Sätze bekannt - 2 n , die aussortiert werden müssen. Unter Verwendung der grundlegenden Funktionen der C#-Sprache – Negation, Disjunktion, Konjunktion und Identität – ist es einfach, ein Programm zu schreiben, das für einen gegebenen Satz von Variablen den Wert einer logischen Funktion berechnet, die einer logischen Gleichung oder einem Gleichungssystem entspricht.

In einem solchen Programm müssen Sie einen Zyklus anhand der Anzahl der Sätze im Hauptteil des Zyklus anhand der Satznummer erstellen, den Satz selbst bilden, den Wert der Funktion für diesen Satz berechnen und wenn dieser Wert gleich ist zu 1, dann gibt die Menge eine Lösung der Gleichung.

Die einzige Schwierigkeit, die bei der Implementierung des Programms auftritt, hängt mit der Aufgabe zusammen, den Satz von Variablenwerten selbst durch die Satznummer zu bilden. Das Schöne an dieser Aufgabe ist, dass diese scheinbar schwierige Aufgabe tatsächlich auf eine einfache Aufgabe hinausläuft, die bereits wiederholt aufgetreten ist. In der Tat reicht es aus zu verstehen, dass der Satz von Werten von Variablen, die der Zahl i entsprechen und aus Nullen und Einsen bestehen, die binäre Darstellung der Zahl i darstellt. So reduziert sich die komplexe Aufgabe, eine Menge von Werten von Variablen durch die Mengenzahl zu erhalten, auf das bekannte Problem, eine Zahl in ein Binärsystem umzuwandeln.

So sieht die C#-Funktion aus, die unser Problem löst:

///

/// Programm zum Zählen der Anzahl der Lösungen

/// logische Gleichung (Gleichungssystem)

///

///

/// logische Funktion - Methode,

/// dessen Signatur vom DF-Delegierten festgelegt wird

///

/// Anzahl Variablen

/// Anzahl Lösungen

static int SolveEquations(DF fun, int n)

bool set = new bool[n];

int m = (int)Math.Pow(2, n); // Anzahl der Sätze

Ganzzahl p = 0, q = 0, k = 0;

//Vollständige Aufzählung nach Anzahl der Sets

für (int i = 0; i< m; i++)

//Bildung des nächsten Satzes — Satz,

//gegeben durch die binäre Darstellung der Zahl i

für (int j = 0; j< n; j++)

k = (int)Math.Pow(2, j);

//Funktionswert am Set berechnen

Zum Verständnis des Programms hoffe ich, dass die Erläuterungen zur Idee des Programms und die Kommentare in seinem Text ausreichen. Ich werde nur auf die Erläuterung der Überschrift der obigen Funktion eingehen. Die SolveEquations-Funktion hat zwei Eingabeparameter. Der Fun-Parameter gibt eine logische Funktion an, die der zu lösenden Gleichung oder dem zu lösenden Gleichungssystem entspricht. Der Parameter n gibt die Anzahl der Variablen in der Fun-Funktion an. Als Ergebnis gibt die SolveEquations-Funktion die Anzahl der Lösungen der logischen Funktion zurück, d. h. die Anzahl der Mengen, für die die Funktion als wahr ausgewertet wird.

Für Schulkinder ist es üblich, wenn für eine Funktion F(x) der Eingabeparameter x eine arithmetische, Zeichenfolgen- oder boolesche Variable ist. In unserem Fall wird ein leistungsfähigeres Design verwendet. Die SolveEquations-Funktion bezieht sich auf Funktionen höherer Ordnung - Funktionen vom Typ F(f), deren Parameter nicht nur einfache Variablen, sondern auch Funktionen sein können.

Die Klasse der Funktionen, die als Parameter an die SolveEquations-Funktion übergeben werden können, ist wie folgt definiert:

delegieren Sie bool DF (bool vars);

Diese Klasse umfasst alle Funktionen, die als Parameter eine Reihe von Werten von booleschen Variablen übergeben, die durch das vars-Array angegeben werden. Das Ergebnis ist ein boolescher Wert, der den Wert der Funktion auf dieser Menge darstellt.

Abschließend werde ich ein Programm vorstellen, in dem die SolveEquations-Funktion verwendet wird, um mehrere Systeme logischer Gleichungen zu lösen. Die SolveEquations-Funktion ist Teil der folgenden ProgramCommon-Klasse:

Klasse ProgramCommon

delegieren Sie bool DF (bool vars);

static void Main(String-Argumente)

Console.WriteLine("Funktion und Lösungen - " +

SolveEquations(FunAnd, 2));

Console.WriteLine("Funktion hat 51 Lösungen - " +

Gleichungen lösen(Fun51, 5));

Console.WriteLine("Funktion hat 53 Lösungen - " +

Gleichungen lösen(Fun53, 10));

static bool FunAnd(bool vars)

Rückgabevariablen && vars;

static bool Fun51(bool vars)

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

static bool Fun53(bool vars)

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && (!((vars == vars) || (vars == vars)));

So sehen die Ergebnisse der Lösung für dieses Programm aus:

10 Aufgaben zum selbstständigen Arbeiten

1. Welche der drei Funktionen sind äquivalent:
   1. (X → Y) ˅ ¬Y
   2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X ˄ Y
2. Ein Fragment der Wahrheitstabelle ist gegeben:

x1	x2	x3	x4	F
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

Welche der drei Funktionen entspricht diesem Fragment:

1. (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
4. Die Jury besteht aus drei Personen. Die Entscheidung kommt zustande, wenn der Vorsitzende der Jury dafür stimmt und von mindestens einem der Jurymitglieder unterstützt wird. Andernfalls wird keine Entscheidung getroffen. Erstellen Sie eine logische Funktion, die den Entscheidungsprozess formalisiert.
5. X gewinnt gegen Y, wenn vier Münzwürfe dreimal Kopf ergeben. Definieren Sie eine boolesche Funktion, die Auszahlung X beschreibt.
6. Wörter in einem Satz werden von eins beginnend nummeriert. Ein Satz gilt als wohlgeformt, wenn die folgenden Regeln erfüllt sind:
   1. Wenn ein geradzahliges Wort auf einen Vokal endet, muss das nächste Wort, sofern vorhanden, mit einem Vokal beginnen.
   2. Wenn ein Wort mit ungerader Zahl auf einen Konsonanten endet, muss das nächste Wort, sofern vorhanden, mit einem Konsonanten beginnen und mit einem Vokal enden.
      Welche der folgenden Sätze sind richtig:
   3. Mama hat Mascha mit Seife gewaschen.
   4. Der Anführer ist immer ein Vorbild.
   5. Die Wahrheit ist gut, aber Glück ist besser.
7. Wie viele Lösungen hat die Gleichung:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Liste alle Lösungen der Gleichung auf:
   (a → b) → c = 0
9. Wie viele Lösungen hat das folgende Gleichungssystem:
   X 0 → X 1 ˄ X 1 → X 2 = 1
   X2 → X3 ˄ X3 → X4 = 1
   X 5 → X 6 ˄ X 6 → X 7 = 1
   X 7 → X 8 ˄ X 8 → X 9 = 1
   X0 → X5 = 1
10. Wie viele Lösungen hat die Gleichung:
    ((((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1

Antworten auf Aufgaben:

1. Die Funktionen b und c sind äquivalent.
2. Das Fragment entspricht der Funktion b.
3. Die boolesche Variable P nehme den Wert 1 an, wenn der Vorsitzende der Jury für die Entscheidung stimmt. Die Variablen M 1 und M 2 repräsentieren die Meinung der Jurymitglieder. Die logische Funktion, die die Annahme einer positiven Entscheidung spezifiziert, kann wie folgt geschrieben werden:
   P ˄ (M 1 ˅ M 2)
4. Die boolesche Variable P i nehme den Wert 1 an, wenn der i-te Münzwurf Kopf ergibt. Die logische Funktion, die die Auszahlung X definiert, kann wie folgt geschrieben werden:
   ¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
   (¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
   (¬P 3 ˄ ¬P 4))
5. Angebot b.
6. Die Gleichung hat 3 Lösungen: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a=0; b=1; c=0)

Noskin Andrej Nikolajewitsch,
IT-Lehrer
die höchste Qualifikationskategorie,
Kandidat der Militärwissenschaften, außerordentlicher Professor
GBOU Lyzeum №1575 Moskau

Optimiertes Mapping-Verfahren zur Lösung von Problem 23 von KIM USE in Informatik und ICT

Eine der schwierigsten Aufgaben im KIM USE ist Aufgabe 23, in der Sie die Anzahl der verschiedenen Wertesätze von logischen Variablen finden müssen, die die angegebene Bedingung erfüllen.
Diese Aufgabe ist vielleicht die schwierigste Aufgabe des KIM USE in Informatik und IKT. In der Regel kommen nicht mehr als 5 % der Prüflinge damit zurecht (1).
Ein so kleiner Prozentsatz von Schülern, die diese Aufgabe abgeschlossen haben, erklärt sich aus dem Folgenden:
- die Schüler können die Zeichen logischer Operationen verwechseln (vergessen);
- mathematische Fehler bei der Durchführung von Berechnungen;
- Denkfehler bei der Lösungssuche;
- Fehler beim Vereinfachen logischer Ausdrücke;
- Lehrer empfehlen, dieses Problem nach Abschluss der gesamten Arbeit zu lösen, da die Wahrscheinlichkeit einer Annahme besteht
Fehler ist sehr hoch, und das „Gewicht“ der Aufgabe ist nur eine primäre Punktzahl.
Außerdem fällt es einigen Lehrern selbst schwer, diese Art von Problemen zu lösen, und versuchen daher, einfachere Probleme mit Kindern zu lösen.
Es verkompliziert auch die Situation, dass es in diesem Block eine große Anzahl verschiedener Aufgaben gibt und es unmöglich ist, eine Art Vorlagenlösung auszuwählen.
Um diese Situation zu korrigieren, stellt die pädagogische Gemeinschaft die beiden wichtigsten Methoden zur Lösung von Problemen dieser Art fertig: das Lösen mit Bitketten (2) und das Mapping-Verfahren (3).
Die Notwendigkeit, diese Methoden zu verfeinern (optimieren), ergibt sich aus der Tatsache, dass sich Aufgaben sowohl in der Struktur als auch in der Anzahl der Variablen ständig ändern (nur ein Typ von Variablen X, zwei Typen von Variablen X und Y, drei Typen: X, Y ,Z).
Die Komplexität der Beherrschung dieser Problemlösungsmethoden wird durch die Tatsache bestätigt, dass auf der Website von K.Yu. Polyakov, gibt es eine Analyse dieser Art von Problemen in Höhe von 38 Stück (4). In einigen Analysen wird mehr als eine Art von Problemlösung angegeben.
In letzter Zeit gibt es bei KIM USE in der Informatik Probleme mit zwei Arten von Variablen X und Y.
Ich habe die Anzeigemethode optimiert und schlage vor, dass meine Schüler die verbesserte Methode verwenden.
Dies ergibt ein Ergebnis. Der Prozentsatz meiner Schüler, die diese Aufgabe erledigen, variiert bis zu 43 % der Passanten. In der Regel bestehen jedes Jahr 25 bis 33 Personen aus allen 11. Klassen die Prüfung in Informatik.
Vor dem Erscheinen von Aufgaben mit zwei Arten von Variablen wurde die Anzeigemethode von den Schülern sehr erfolgreich verwendet, aber nach dem Erscheinen im logischen Ausdruck Y bemerkte ich, dass die Antworten der Kinder nicht mehr mit den Tests übereinstimmten. Es stellte sich heraus, dass sie nicht ganz klar verstanden haben, wie man eine Zuordnungstabelle mit einem neuen Variablentyp erstellt. Dann kam mir der Gedanke, dass es aus Gründen der Bequemlichkeit notwendig ist, den gesamten Ausdruck auf einen Variablentyp zu bringen, da dies für Kinder praktisch ist.
Lassen Sie mich diese Methode genauer beschreiben. Der Einfachheit halber werde ich es am Beispiel eines Systems logischer Ausdrücke in (4) betrachten.
Wie viele verschiedene Lösungen hat das System der logischen Gleichungen?

(x 1 ^ j1)=(¬ x 2 v ¬ j 2 )
(x2 ^ j2)= (¬ x 3 v ¬ j 3 )
...
(x5 ^ ja 5) = (¬ x 6 v ¬ j 6 )

wox 1 , …, x 6 , j 1 , …, j 6 , - 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.
Lösung:
1. Aus der Analyse des Systems logischer Gleichungen sehen wir, dass es 6 Variablen gibt X und 6 Variablen Bei. Da jede dieser Variablen nur zwei Werte (0 und 1) annehmen kann, ersetzen wir diese Variablen durch 12 Variablen des gleichen Typs, zum Beispiel Z.
2. Lassen Sie uns nun das System mit neuen Variablen des gleichen Typs umschreiben. Die Komplexität der Aufgabe liegt in der sorgfältigen Notation beim Ändern von Variablen.

(z1 ^ z2)= (¬z 3v¬ z 4 )
(z3 ^ z4)= (¬ z 5 v¬ z 6 )
...
(z9 ^ z 10) = (¬ z 11 v¬ z 12)

3. Lassen Sie uns eine Tabelle erstellen, in der wir alle Optionen sortieren z 1 , z 2 , z 3 , z 4 , da es in der ersten logischen Gleichung vier Variablen gibt, hat die Tabelle 16 Zeilen (16=2 4); Entfernen Sie solche Werte aus der Tabelle z 4 , für die die erste Gleichung keine Lösung hat (durchgestrichene Zahlen).

0	0	0	0
			1
		1	0
			1
	1	0	0
			1
		1	0
			1
1	0	0	0
			1
		1	0
			1
	1	0	0
			1
		1	0
			1

4. Wir analysieren die Tabelle und erstellen eine Regel zum Anzeigen von Variablenpaaren (z. B. ein Paar Z 1 Z 2 =00 Übereinstimmungen Paar Z 3 Z 4 = 11) .

5. Füllen Sie die Tabelle aus, indem Sie die Anzahl der Variablenpaare berechnen, für die das System eine Lösung hat.

6. Addiere alle Ergebnisse: 9 + 9 + 9 + 27 = 54
7. Antwort: 54.
Die obige optimierte Methode zur Lösung von Problem 23 aus dem KIM USE ermöglichte es den Schülern, wieder Selbstvertrauen zu gewinnen und diese Art von Problem erfolgreich zu lösen.

Literatur:

1. FIPI. Methodische Empfehlungen für Lehrer, erstellt auf der Grundlage einer Analyse typischer Fehler von Teilnehmern des 2015 USE in INFORMATICS and ICT. Zugriffsmodus: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf

2. K. Yu. Poljakow, M.A. Roitberg.Logische Gleichungssysteme: Lösung mit Bitfolgen. Zeitschrift Informatik, Nr. 12, 2014, p. 4-12. Verlag "Erster September", Moskau.
3. E.A. Mironchik, Anzeigemethode. Zeitschrift Informatik, Nr. 10, 2013, p. 18-26. Verlag "Erster September", Moskau.

Die Verwendung von Gleichungen ist in unserem Leben weit verbreitet. Sie werden in vielen Berechnungen, Konstruktionen und sogar im Sport verwendet. Gleichungen werden seit der Antike vom Menschen verwendet, und seitdem hat ihre Verwendung nur zugenommen. In der Mathematik gibt es bestimmte Aufgaben, die sich der Satzlogik widmen. Um eine solche Gleichung zu lösen, müssen Sie über ein gewisses Maß an Wissen verfügen: Kenntnisse der Gesetze der Aussagenlogik, Kenntnisse der Wahrheitstabellen logischer Funktionen von 1 oder 2 Variablen, Methoden zur Transformation logischer Ausdrücke. Darüber hinaus müssen Sie die folgenden Eigenschaften logischer Operationen kennen: Konjunktionen, Disjunktionen, Inversionen, Implikationen und Äquivalenzen.

Jede logische Funktion von \ Variablen - \ kann durch eine Wahrheitstabelle spezifiziert werden.

Lassen Sie uns einige logische Gleichungen lösen:

\[\rightharpoondown X1\vee X2=1 \]

\[\rightharpoondown X2\vee X3=1\]

\[\rightharpoondown X3\vee X4=1 \]

\[\rightharpoondown X9\vee X10=1\]

Beginnen wir die Lösung mit \[X1\] und bestimmen, welche Werte diese Variable annehmen kann: 0 und 1. Betrachten Sie als Nächstes jeden der obigen Werte und sehen Sie, was \[X2.\] kann in diesem Fall sein

Wie aus der Tabelle ersichtlich, hat unsere logische Gleichung 11 Lösungen.

Wo kann ich eine logische Gleichung online lösen?

Sie können die Gleichung auf unserer Website https: // site. Mit dem kostenlosen Online-Solver können Sie eine Online-Gleichung beliebiger Komplexität in Sekundenschnelle lösen. Sie müssen lediglich Ihre Daten in den Solver eingeben. Sie können sich auch die Videoanleitung ansehen und lernen, wie Sie die Gleichung auf unserer Website lösen. Und wenn Sie Fragen haben, können Sie diese in unserer Vkontakte-Gruppe http://vk.com/pocketteacher stellen. Treten Sie unserer Gruppe bei, wir helfen Ihnen gerne weiter.

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

Eine Aufgabe: Lösen Sie ein System logischer Gleichungen:

In Betracht ziehen 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 Werte nur zwei Werte haben, können Sie einfach alle Optionen durchgehen und darunter diejenigen finden, für die das angegebene 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.

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

Lösung: 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.

Eine 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. Bei 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)

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.

Eine Aufgabe:Lösen Sie ein System logischer Gleichungen:

In Betracht ziehen 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 Werte nur zwei Werte haben, können Sie einfach alle Optionen durchgehen und darunter diejenigen finden, für die das angegebene 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. Bei 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.

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

Lösung: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.

Eine 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. Beix 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 gewä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