Municipal Budgetary Educational Institution

"Durchschnittlich allgemein bildende Schule № 18 "

stadtteil Stadt Salavat der Republik Bashkortostan

Systeme der logischen Gleichungen

in den Aufgaben der EGE auf Informatik

Abschnitt "Grundlagen der Logikalgebra" in aufgaben EGE. Es gilt als einer der komplexesten und schlecht gelösten. Der durchschnittliche Anteil der Aufgaben zu diesem Thema ist der niedrigste und beträgt 43.2.

Kursabschnitt.	Durchschnittlicher Prozentsatz der Aufgabengruppen
Codierungsinformationen und Messung seiner Anzahl
Informationsmodellierung.
Nummernsysteme
Grundlagen der Algebra-Logik
Algorithmus und Programmierung.
Grundlagen von Informations- und Kommunikationstechnologien

Basierend auf der KIM-Spezifikation 2018 beinhaltet dieses Gerät vier Aufgaben unterschiedlicher Komplexitätsniveaus.

№ aufgaben	Geprüft inhaltselemente	Das Niveau der Komplexität der Aufgabe
	Die Fähigkeit, Wahrheitstabellen und Logikschemata aufzubauen
	Die Möglichkeit, nach Informationen im Internet zu suchen
	Wissen über grundlegende Konzepte und Gesetze mathematische Logik.
	Die Fähigkeit, logische Ausdrücke zu erstellen und zu konvertieren

Die Aufgabe 23 ist in Bezug auf die Komplexität hoch, daher hat es den niedrigsten Anteil der Ausführung. Unter den vorbereiteten Absolventen (81-100 Punkte), 49,8% derjenigen, die erfüllt sind, werden die durchschnittlich vorbereiteten (61-80-Punkte) mit 13,7% um 13,7% fertiggestellt, die verbleibende Schülergruppe erfüllt diese Aufgabe nicht.

Der Erfolg der Lösung des Systems logischer Gleichungen hängt von der Kenntnis der Gesetze der Logik und der klaren Anwendung der Systemlösungsmethoden ab.

Betrachten Sie die Lösung des Systems logischer Gleichungen durch Anzeige durch Anzeige.

(23.154 Pole K.YU.) Wie viele verschiedene Lösungen haben ein System von Gleichungen?

((X.1  y.1 )  (X.2  y.2 ))  (X.1  x.2 )  (y.1  y.2 ) =1

((X.2  y.2 )  (X.3  y.3 ))  (X.2  x.3 )  (y.2  y.3 ) =1

((x.7  y.7 )  (x.8  y.8 ))  (x.7  x.8 )  (y.7  y.8 ) =1

wo x.1 , x.2 ,…, x.8, w.1 , U.2 ...,8 - Logikvariablen? Als Antwort müssen Sie nicht alle verschiedenen Variablensätze auflisten, in denen diese Gleichstellung ausgeführt wird. Als Antwort müssen Sie die Anzahl solcher Sets angeben.

Entscheidung. Alle in das System enthaltenen Gleichungen, den gleichen Typ, und jede Gleichung umfasst vier Variablen. Wenn Sie X1 und Y1 kennen, können wir alle möglichen X2- und Y2-Werte finden, die die erste Gleichung erfüllen. Auf ähnliche Weise korrigieren, von dem bekannten X2 und Y2 können wir X3, Y3 finden, die die zweite Gleichung erfüllen. Das ist, das Paar (X1, Y1) zu kennt und den Wert des Paars (x2, y2) zu bestimmen, wir finden ein Paar (x3, y3), das wiederum zu einem Paar (x4, y4) führt und so weiter.

Finden Sie alle Lösungen der ersten Gleichung. Dies kann auf zwei Arten erfolgen: einen Tisch der Wahrheit aufbauen, durch das Bedenken und die Anwendung der Gesetze der Logik.

Tanktabelle:

				x 1.  y 1.	x 2.  y 2.	(x 1  y 1)  (x 2.  y 2)	(x 1  x 2)	(Y 1.  y 2)	(x 1  x 2)  (Y 1.  y 2)

Der Bau der Wahrheitstabelle ist mühsam und unwirksam in der Zeit, daher verwenden wir die zweite Methode - logische Argumentation. Das Produkt ist gleich 1 und nur, wenn jeder Multiplizierer gleich 1 ist.

(x.1  y.1 )  (x.2  y.2 ))=1

(x.1  x.2 ) =1

(y.1  y.2 ) =1

Betrachten Sie die erste Gleichung. Nach 1, wenn 0 0, 0 1, 1 1, IT bedeutet (X1 y1) \u003d 0 bei (01), (10), dann (x.2  y.2 ) es kann eine beliebige (00), (01), (10), (11) und bei (x1 y1) \u003d 1 sein, dh (00) und (11) dampf (x2 y2) \u003d 1 nimmt die gleiche Werte (00) und (11). Wir schließen aus dieser Lösung aus, für die die zweite und dritte Gleichung falsch sind, dh x1 \u003d 1, x2 \u003d 0, y1 \u003d 1, y2 \u003d 0.

(x.1 , y.1 )	(x.2 , y.2 )

Gesamtzahl der Paare 1 + 1 + 1 + 22 \u003d 25

2) (23.160 Pole K.YU.) Wie viele verschiedene Lösungen haben ein System von logischen Gleichungen?

(X. 1  (X. 2  y. 2 ))  (y. 1  y. 2 ) = 1

(X. 2  (X. 3  y. 3 ))  (y. 2  y. 3 ) = 1

...

( x. 6  ( x. 7  y. 7 ))  ( y. 6  y. 7 ) = 1

x. 7  y. 7 = 1

Entscheidung. 1) die gleichen Typgleichungen, so dass das Begrößerungsverfahren alle Arten von Paaren (X1, Y1), (X2, Y2) der ersten Gleichung findet.

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

(y.1  y.2 ) = 1

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

Finden Sie Lösungen der ersten Gleichung. Wenn x1 \u003d 0, dann x2, y2 - beliebig, wenn x1 \u003d 1, dann nimmt X2, y2 den Wert (11) an.

Wir werden Verbindungen zwischen den Paaren (x1, y1) und (x2, y2) herstellen.

(x.1 , y.1 )	(x.2 , y.2 )

Machen Sie einen Tisch zum Berechnen der Anzahl der Paare in jeder Phase.

							0

Angesichts der Entscheidung der letzten Gleichung x. 7  y. 7 = 1, Lassen Sie uns das Paar (10) hervorrufen. Finden gesamtzahl Lösungen 1 + 7 + 0 + 34 \u003d 42

3)(23.180) Wie viele verschiedene Lösungen haben ein System logischer Gleichungen?

(x.1  x.2 )  (x.3  x.4 ) = 1

(x.3  x.4 )  (x.5  x.6 ) = 1

(x.5  x.6 )  (x.7  x.8 ) = 1

(x.7  x.8 )  (x.9  x.10 ) = 1

x.1  x.3  x.5  x.7  x.9 = 1

Entscheidung. 1) die gleichen Typgleichungen, so dass das Begründungsverfahren alle Arten von Paaren (X1, X2), (X3, X4) der ersten Gleichung findet.

(x.1  x.2 )  (x.3  x.4 ) = 1

Mit Ausnahme der Entscheidung des Paares, das im Folgenden 0 (1  0) ergibt, sind dies Paare (01, 00, 11) und (10).

Wir werden zwischen Paaren (X1, X2), (X3, X4) verbunden.

So lösen Sie einige der Aufgaben der Partitionen A und B-Prüfungsinformatik

Lektion Nummer 3. Logics. Logikfunktionen. Gleichungen lösen

Eine große Anzahl von Aufgaben der Verwendung ist der Logik der Anweisungen gewidmet. Um den größten Teil von ihnen zu lösen, gibt es genügend Kenntnisse der grundlegenden Gesetze der Aussagen Logik, Kenntnisse der Wahrheitstabellen der logischen Funktionen von ein und zwei Variablen. Ich werde die grundlegenden Gesetze der Anweisungslogik geben.

1. Schwachlichkeit der Disjunktion und Konjunktion:
   A ˅ b ≡ b ˅ a
   a ^ b ≡ b ^ a
2. Vertriebsgesetz in Bezug auf Disjunktion und Konjunktion:
   A ˅ (b ^ c) ≡ (a ˅ b) ^ (a ˅ c)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ s)
3. Ablehnung der Ablehnung:
   ¬ (¬) ≡ a
4. Konsistenz:
   ^ ¬ ¬ ≡ false
5. Außer dritter:
   Ein ˅ ˅ ≡ wahr
6. De Morgana-Gesetze:
   ¬ (a ˅ b) ≡ ¬ r
   ¬ (a b) ≡ ˅ ¬
7. Vereinfachung:
   A a a a ≡ a
   A ˅ a ≡ a
   Ein wahres ≡ a
   Ein falsches ≡ falsch
8. Absorption:
   A (a ˅ b) ≡ a
   Ein ˅ (a b) ≡ a
9. Ersatz der Implikation.
   A → B ≡ ˅ B
10. Identität ersetzen.
    A ≡ b ≡ (a b) ˅ (¬ a ¬ b)

Präsentation logischer Funktionen

Jede logische Funktion aus n Variablen - F (x 1, x 2, ... x n) kann die Wahrheitstabelle einstellen. Eine solche Tabelle enthält 2 n Variablensätze, für die jeder der Funktionswert auf diesem Satz eingestellt ist. Diese Methode ist gut, wenn die Anzahl der Variablen relativ klein ist. Bereits bei n\u003e 5 wird die Leistung schlecht sichtbar.

Eine andere Möglichkeit besteht darin, die Funktion in einigen Formel mit bekannten einfachen Funktionen einzustellen. Das System der Funktionen (F 1, F 2, ... F k) wird voll ausgezeichnet, wenn eine logische Funktion durch eine Formel ausgedrückt werden kann, die nur die Funktion F i enthält.

Voll ist das Funktionssystem (¬ ,, ˅). Die Gesetze 9 und 10 sind Beispiele, die als Implikation und Identität, die durch Ablehnung, Konjunktion und Disjunktion zeigen, demonstrieren.

Tatsächlich ist das System auch ein System von zwei Funktionen - Ablehnung und Konjunktion oder Ablehnung und Disjunktion. Von den Gesetzen von De Morgana gibt es Ideen, die es uns ermöglichen, die Verbindung durch Ablehnung und Desjunction auszudrücken und sich entsprechend durch Ablehnung und Konjunktion zu äußern:

(A ˅ b) ≡ ¬ (¬ b)
(A b) ≡ ¬ (¬ ˅ ˅ ¬ b)

Paradoxerweise besteht ein komplettes System, das nur aus einer Funktion besteht. Es gibt zwei binäre Funktionen - Anti-Konjunktion und Antidiasunzunktion, den Pierce-Pfeil und den Barcode des Sheffers, der das Hohlsystem darstellt.

Die grundlegenden Funktionen der Programmiersprachen umfassen in der Regel Identität, Ablehnung, Konjunktion und Disjunktion. In den Aufgaben des EE wird zusammen mit diesen Funktionen die Implikation oft gefunden.

Betrachten Sie mehrere. einfache Aufgabenmit logischen Funktionen verbunden.

Aufgabe 15:

DAN-Fragment der Wahrheitstabelle. Welcher der drei obigen Funktionen ist das Fragment?

X 1	X 2.	X 3.	X 4.	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) ˅ (¬ × 3 x 4)
3. ¬ x 1 ˅ x 2 ˅ (x 3 x 4)

Funktion bei Nummer 3.

Um das Problem zu lösen, müssen Sie die Wahrheitstabellen der Grundfunktionen kennen und sich an die Prioritäten der Operationen erinnern. Lassen Sie mich daran erinnern, dass die Verbindung (logische Multiplikation) eine höhere Priorität aufweist und früher als die Disjunktion (logische Ergänzung) erfolgt. Bei der Berechnung ist es einfach zu bemerken, dass Funktionen mit den Zahlen 1 und 2 auf dem dritten Satz von Wert 1 sind und aus diesem Grund das Fragment nicht überein.

Aufgabe 16:

Welche der obigen Zahlen erfüllt den Zustand:

(Zahlen, beginnend mit der älteren Entladung, in absteigender Reihenfolge) → (die Nummer ist sogar) (die jüngste Ziffer ist sogar) (die seniorste Ziffer ist ungerade)

Wenn es mehrere solche Zahlen gibt, geben Sie den größten an.

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

Der Zustand erfüllt die Nummer 4.

Die ersten beiden Zahlen erfüllen aus dem Grund nicht, dass die jüngste Ziffer ungerade ist. Die Konjunktion der Bedingungen ist falsch, wenn eines der Mitglieder der Verbindung falsch ist. Für die dritte Zahl ist der Zustand nicht für die leitende Ziffer erfüllt. Für die vierte Zahl werden die an den jüngeren und älteren Zahlen auferlegten Bedingungen durchgeführt. Das erste Mitglied der Verbindung trifft ebenfalls zu, da die Implikation der Wahrheit, wenn sein Paket falsch ist, der in diesem Fall stattfindet.

Aufgabe 17: Zwei Zeugen gaben folgende Messwerte an:

Erster Zeuge: Wenn es schuldig ist, dann und ist nicht schuldig, und c ist unschuldig.

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

Welche Schlussfolgerungen von Schuld A, B und C können auf der Grundlage von Zeugnis hergestellt werden?

Antwort: Aus dem Zeugnis folgt, dass A schuldig ist, und c ist unschuldig.

Lösung: Natürlich kann die Antwort auf der Grundlage des gesunden Menschenverstands erteilt werden. Aber schauen wir uns an, wie dies streng und formal getan werden kann.

Das erste, was man tun soll, ist die Formalisierung von Aussagen. Wir führen drei logische Variablen ein - A, B und C, von denen jeder true ist (1), wenn der entsprechende Verdächtige schuldig ist. Dann wird das Zeugnis des ersten Zeugens von der Formel gegeben:

A → (B ¬ c)

Das Zeugnis des zweiten Zeugens wird von der Formel gegeben:

A ((B ¬ c) ˅ (¬ b c))

Das Zeugnis beider Zeugen geltend und repräsentiert die Verbindung der relevanten Formeln.

Erstellen Sie eine Wahrheitstabelle für diese Zeugnisse:

EIN.	B.	C.	F 1.	F 2.	F 1 F 2
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

Das totale Zeugnis trifft nur in einem Fall zu, was zu einer eindeutigen Antwort führt - und in der Schuldigen, und C ist unschuldig.

Aus der Analyse dieses Tisches folgt auch, dass das Zeugnis des zweiten Zeugens informativer ist. Von der Wahrheit seines Zeugnisses sollten nur zwei mögliche Optionen schuldig sein - und die Schuldigen, und C - unschuldig oder von der Schuldigen, und in ist unschuldig. Das Zeugnis des ersten Zeugens ist weniger informativ - es gibt 5 verschiedene Optionen, die sein Zeugnis entsprechen. Zusammen geben das Zeugnis beider Zeugen eine eindeutige Antwort auf die Schuld der Verdächtigen.

Logische Gleichungen und Gleichungen von Gleichungen

Sei f (x 1, x 2, ... x n) eine logische Funktion von n Variablen. Die logische Gleichung ist:

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

Konstante C hat einen Wert von 1 oder 0.

Die logische Gleichung kann von 0 bis 2 n verschiedener Lösungen aufweisen. Wenn C gleich 1 ist, sind Lösungen alle Seiten von Variablen von der Wahrheitstabelle, auf denen die Funktion F den Wert der Wahrheit (1) nimmt. Die verbleibenden Kits sind Lösungen der Gleichung bei c gleich Null. Sie können immer nur die Gleichungen des Formulars berücksichtigen:

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

Lassen Sie die Gleichung eingestellt:

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

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

¬f (x 1, x 2, ... x n) \u003d 1

Betrachten Sie das 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) \u003d 1

Die Lösung des Systems ist ein Satz von Variablen, auf denen alle Systemgleichungen durchgeführt werden. Um eine Lösung des logischen Gleichungssystems zu erhalten, sollten Sie in Bezug auf logische Funktionen ein Set finden, auf dem die logische Funktion F true ist, was die Verbindung der Anfangsfunktionen darstellt. F:

F \u003d f 1 f 2 ... f k

Wenn die Anzahl der Variablen beispielsweise klein ist, zum Beispiel weniger als 5, ist es nicht schwierig, eine Wahrheitstabelle für die Funktion F zu erstellen, mit der Sie sagen können, wie viele Lösungen ein System verfügen, und welche Sätze, die Lösungen ergeben.

In einigen Aufgaben der EGE, um Lösungen des Systems logischer Gleichungen zu finden, erreicht die Anzahl der Variablen einen Wert von 10. Aufbau einer Wahrheitstabelle wird zu einer praktisch einschädlichen Aufgabe. Um das Problem zu lösen, ist ein anderer Ansatz erforderlich. Für ein beliebiges Gleichungssystem von Gleichungen gibt es keine gemeinsame Methode als das Busting, mit dem Sie solche Aufgaben lösen können.

In den auf der Prüfung vorgeschlagenen Aufgaben basiert die Lösung in der Regel auf den Besonderheiten des Gleichungssystems. Ich wiederhole, neben der Suche nach allen Varianten des Variablensatzes gibt es keine allgemeine Möglichkeit, das Problem zu lösen. Die Entscheidung muss basierend auf den Besonderheiten des Systems erstellt werden. Es ist häufig nützlich, die Vorvereinbarkeit des Gleichungssystems mit bekannten Logikgesetzen zu vereinfachen. Ein weiterer nützlicher Empfang der Lösung dieser Aufgabe ist wie folgt. Wir sind nicht an allen Sätzen interessiert, sondern nur diejenigen, auf denen die Funktion F wichtig ist für 1. Anstelle eines kompletten Wahrheitstisches bauen wir analog - einen binären Baumbaum. Jeder Zweig dieses Baums entspricht einer Lösung und stellt den Set ein, auf dem die F-Funktion F von Wert 1 ist. Die Anzahl der Zweige des Lösungsbaums fällt mit der Anzahl der Lösungen des Gleichungssystems zusammen.

Was ist ein binärer Entscheidungsbaum und wie es gebaut ist, erklärt die Beispiele mehrerer Aufgaben.

Aufgabe 18.

Wie viele verschiedene Werte von Werten der logischen Variablen X1, X2, X3, X4, X5, Y1, Y2, Y3, Y4, Y5, die das System von zwei Gleichungen erfüllen?

Antwort: Das System verfügt über 36 verschiedene Lösungen.

Lösung: Das Gleichungssystem enthält zwei Gleichungen. Wir finden die Anzahl der Lösungen für die erste Gleichung in Abhängigkeit von 5 Variablen - X 1, X 2, ... x 5. Die erste Gleichung kann wiederum als System von 5 Gleichungen betrachten. Wie gezeigt, repräsentiert das Gleichungssystem tatsächlich die Verbindung logischer Funktionen. Die inverse Anweisung trifft ebenfalls zu, die Verbindung der Bedingungen kann als Gleichungssystem betrachtet werden.

Wir erstellen den Implication Solutions-Baum (x1 → X2) - das erste Mitglied der Verbindung, das als erste Gleichung betrachtet werden kann. Hier ist das, was das Grafikbild dieses Baums aussieht:

Der Baum besteht aus zwei Ebenen nach Anzahl der Gleichungsvariablen. Die erste Ebene beschreibt die erste Variable x 1. Zwei Zweige dieser Ebene spiegeln die möglichen Werte dieser Variablen - 1 und 0 wider. In der zweiten Ebene des Baumasts spiegeln nur diese möglichen Werte der Variablen X 2, für die die Gleichung den Wert der Wahrheit annimmt . Da die Gleichung die Implikation angibt, erfordert der Zweig, auf dem X 1 Wert 1 ist, dass auf diesem Zweig x 2 er einen Wert von 1 hat 1. Der Zweig, auf dem X 1 einen Wert von 0 hat, erzeugt zwei Zweige mit X 2 Werte von 0 und 1. Der aufgebaute Baum legt drei Lösungen fest, auf denen die Implikation von X 1 → X 2 den Wert 1. in jedem Zweig annimmt, wobei der entsprechende Satz von Variablenwerten, die die Lösung der Gleichung ergeben.

Dies sind diese Sets: ((1, 1), (0, 1), (0, 0))

Wir erstellen den Lösungsbaum weiterhin, indem wir die folgende Gleichung hinzufügen, die folgende Implikation von X 2 → X 3. Die Besonderheiten unseres Gleichungssystems sind, dass jede neue Gleichung des Systems eine Variable von der vorherigen Gleichung verwendet und eine neue Variable hinzufügt. Da die Variable x 2 bereits Werte auf dem Baum hat, dann auf allen Zweigen, in denen die Variable X 2 1 ist, ist die Variable X 3 auch einen Wert 1. Für solche Zweige hat der Bau eines Baumes weiter Next Level, aber neue Zweige erscheint nicht. Der einzige Zweig, in dem die Variable X 2 einen Wert von 0 aufweist, ergibt Verzweigung in zwei Zweige, wobei die Variable X 3 einen Wert von 0 und 1 empfängt, wobei jeweils eine neue Gleichung, angesichts seiner Spezifität, fügt eine neue Gleichung hinzu Lösung. Quelle erste Gleichung:

(x1 → x2) / \\ (x2 → x3) / \\ (x3 → x4) / \\ (x4 → x5) \u003d 1
Hat 6 Lösungen. Hier ist der volle Baum von Lösungen für diese Gleichung:

Die zweite Gleichung unseres Systems ist dem ersten ähnlich:

(Y1 → y2) / \\ (y2 → y3) / \\ (y3 → y4) / \\ (y4 → y5) \u003d 1

Der einzige Unterschied besteht darin, dass die Gleichungen Variablen y verwenden. Diese Gleichung hat auch 6 Lösungen. Da jede Lösung für Variablen X i mit jeder Lösung für Variablen y J kombiniert werden kann, ist die Gesamtzahl der Lösungen 36.

Hinweis, der baute Lösungsbaum gibt nicht nur die Anzahl der Lösungen (durch die Anzahl der Zweige), sondern auch die Entscheidungen selbst, die sich auf jedem Zweig des Baums entlassen haben.

Aufgabe 19

Wie viele verschiedene Werte von Werten der logischen Variablen X1, X2, X3, X4, X5, Y1, Y2, Y3, Y4, Y5, die alle unten aufgeführten Bedingungen erfüllen?

(x1 → x2) / \\ (x2 → x3) / \\ (x3 → x4) / \\ (x4 → x5) \u003d 1
(Y1 → y2) / \\ (y2 → y3) / \\ (y3 → y4) / \\ (y4 → y5) \u003d 1
(X1 → y1) \u003d 1

Diese Aufgabe ist eine Änderung der vorherigen Aufgabe. Der Unterschied besteht darin, dass eine andere Gleichung, die die Variablen X und Y anschließt, zugegeben wird.

Aus der Gleichung x 1 → y 1 folgt, dass, wenn X 1 einen Wert von 1 hat (eine solche Lösung existiert), dann hat Y 1 einen Wert von 1. Somit gibt es einen Satz, auf dem X 1 und Y 1 haben Werte 1. X 1 gleich 0, Y 1 kann einen beliebigen Wert als 0 und 1 haben. Daher entspricht jeweils mit X 1, gleich 0, und solche Sätze 5, entspricht allen 6 Sätzen mit Variablen. Daher, Die Gesamtzahl der Lösungen beträgt 31.

Aufgabe 20.

(¬x 1 ˅ x 2) (¬ × 2 ˅ x 3) (¬ × 3 ˅ x 4) (¬ × 4 ˅ x 5) (¬ × 5 ˅ x 1) \u003d 1

Lösung: Erinnern an die wichtigste Äquivalenz, schreibt unsere Gleichung in das Formular aus:

(X 1 → X 2) (x 2 → x 3) (x 3 → x 4) (x 4 → x 5) (x 5 → x 1) \u003d 1

Die cyclische Kette der Implikationen bedeutet Identität von Variablen, so dass unsere Gleichung der Gleichung entspricht:

X 1 ≡ x 2 ≡ x 3 ≡ x 4 ≡ x 5 \u003d 1

Diese Gleichung hat zwei Lösungen, wenn alle x i entweder 1 oder 0 gleich ist.

Aufgabe 21.

(X 1 → X 2) (X 2 → X 3) (X 3 → X 4) (x 4 → X 2) (x 4 → X 5) \u003d 1

Lösung: Wie bei dem Problem 20 bewegen wir uns mit zyklischen Auswirkungen auf die Identitäten, wodurch die Gleichung im Formular umgeschrieben wird:

(X 1 → X 2) (x 2 ≡ x 3 ≡ x 4) (x 4 → x 5) \u003d 1

Wir erstellen den Lösungsbaum für diese Gleichung:

Aufgabe 22.

Wie viele Lösungen haben das folgende Gleichungssystem?

((X 1 ≡.X 2) (X 3 ≡.X 4)) ˅ (¬X 1 ≡.X 2) ¬ (X 3 ≡.X 4)) \u003d 0

((X 3 ≡.X 4) (X 5 ≡.X 6)) ˅ (¬X 3 ≡.X 4) ¬ (X 5 ≡.X 6)) \u003d 0

((X 5 ≡.X 6) (X 7 ≡.X 8)) ˅ (¬ (¬X 5 ≡.X 6) ¬ (X 7 ≡.X 8)) \u003d 0

((X 7 ≡.X 8) (X 9 ≡X 10)) ˅ (¬ (¬)X 7 ≡.X 8) ¬ (X 9 ≡X 10)) \u003d 0

Antwort: 64.

Lösung: Gehen Sie von 10 Variablen auf 5 Variablen, indem Sie den folgenden Austausch von Variablen eingeben:

Y 1 \u003d (x 1 ≡ x 2); Y 2 \u003d (x 3 ≡ x 4); Y 3 \u003d (x 5 ≡ x 6); Y 4 \u003d (x 7 ≡ x 8); Y 5 \u003d (x 9 ≡ x 10);

Dann wird die erste Gleichung das Formular annehmen:

(Y 1 y 2) ˅ (¤ 1 ¤ 2) \u003d 0

Die Gleichung kann vereinfacht werden, indem Sie es schreiben als:

(Y 1 ≡ y 2) \u003d 0

Wenden Sie sich in die traditionelle Form, schreiben Sie das System nach Vereinfachung in das Formular:

¬ (y 1 ≡ y 2) \u003d 1

¬ (y 2 ym y 3) \u003d 1

¬ (y 3 ≤ y 4) \u003d 1

¬ (y 4 ≤ y 5) \u003d 1

Der Lösungsbaum für dieses System ist einfach und besteht aus zwei Zweigen mit alternierenden variablen Werten:

Rückkehr zur Anfangsvariablen X, beachten wir, dass jeder Wert der Variablen y 2 Werte der Variablen x entspricht, sodass jede Lösung in Variablen in Variablen 2 5 in Variablen X ist. Zwei Zweige erzeugen 2 * 2 5-Lösungen, so dass die Gesamtzahl der Lösungen 64 beträgt.

Wie Sie sehen, erfordert jede Aufgabe zum Lösen des Gleichungssystems seinen Ansatz. Eine gemeinsame Technik ist die Leistung äquivalenter Transformationen, um Gleichungen zu vereinfachen. Der allgemeine Empfang ist der Bau von Entscheidungen Bäumen. Der angewendete Ansatz ähnelt dem Bau einer Wahrheitstabelle teilweise mit dieser Funktion, dass es nicht alle möglichen Variablenwerte gibt, sondern nur diejenigen, auf denen die Funktion Wert 1 (Wahrheit) anzieht. In den vorgeschlagenen Aufgaben ist es oft nicht erforderlich, einen kompletten Lösungsbaum zu erstellen, da es bereits in der Anfangsstufe möglich ist, das Muster des Erscheinungsbildes neuer Äste auf jeder nächsten Niveau festzulegen, wie zum Beispiel in die Aufgabe 18.

Im Allgemeinen sind die Aufgaben, Lösungen eines Systems logischer Gleichungen zu finden, gute mathematische Übungen.

Wenn die Aufgabe manuell schwer zu lösen ist, können Sie die Lösung der Aufgabe des Computers aufladen, indem Sie ein entsprechendes Programm schriftlich, um Gleichungen und Gleichungen zu lösen.

Schreiben eines solchen Programms ist einfach. Ein solches Programm wird mit allen in der Prüfung angebotenen Aufgaben problemlos fertig werden.

Etwas Seltsames, aber die Aufgabe, Lösungen von logischen Gleichungen zu finden, ist komplex und für einen Computer erscheint heraus und der Computer hat seine Grenzen. Der Computer kann einfach in der Lage sein, die Aufgaben, in denen die Anzahl der Variablen 20 --30, fertig werden kann, aber beginnen, lange Zeit auf den Aufgaben des größeren zu denken. Tatsache ist, dass die Funktion 2 N, die die Anzahl der Sätze angibt, ein Exponenten ist, wodurch sich schnell mit zunehmendem N erhöht wächst. So schnell, dass der übliche PC pro Tag nicht mit der Aufgabe, die 40 Variablen enthält, nicht umwickelt wird.

C # -Programm, um logische Gleichungen zu lösen

Schreiben Sie ein Programm, um logische Gleichungen zu lösen, ist aus vielen Gründen nützlich, wenn nur, da es möglich ist, die Richtigkeit Ihrer eigenen Lösungen der Testaufgaben der EGE zu überprüfen. Ein weiterer Grund ist, dass ein solches Programm ein hervorragendes Beispiel für eine Programmieraufgabe ist, die den Anforderungen an die Aufgaben der Kategorie C in der Prüfung erfüllt.

Die Idee des Aufbaus eines Programms ist einfach - es basiert auf der vollständigen Integrität aller möglichen Sätze variabler Werte. Da für eine bestimmte logische Gleichung oder ein System von Gleichungen die Anzahl der Variablen n bekannt ist, dann die Anzahl der Sets - 2 N, die Sie durchgehen möchten, sind bekannt. Mit den Grundfunktionen der C #--Denialsprache, der Disjunktion, der Konjunktion und der Identität ist es einfach, ein Programm zu schreiben, das für einen bestimmten Variablensatz den Wert einer logischen Funktion berechnet, die der logischen Gleichung oder dem System der Gleichungen entspricht.

In einem solchen Programm müssen Sie einen Zyklus in der Anzahl der Sätze aufbauen, in dem Zykluskörper durch Set-Nummer, um den Satz selbst zu bilden, den Wert der Funktion in diesem Satz berechnen, und wenn dieser Wert 1 ist, dann das Set gibt der Lösung der Gleichung an.

Die einzige Schwierigkeit, die sich aus der Implementierung des Programms ergibt, bezieht sich auf die Bildung der Reihe von variablen Werten der Variablen durch die Nummer. Die Schönheit dieser Aufgabe ist, dass diese scheinbar schwierige Aufgabe tatsächlich auf ein einfaches, bereits wiederholtes Auftreten kommt. In der Tat reicht es aus, zu verstehen, dass die entsprechende Anzahl I von Werten von Variablen, die aus Nullen und Einheiten bestehen, eine binäre Aufzeichnung der Zahl I ist. So dass schwierige Aufgabe Das Empfangen eines Satzes von Variablenwerten nach Set-Nummer wird auf eine bekannte Aufgabe der Übersetzung der Zahl in ein Binärsystem reduziert.

Hier sieht die Funktion in der C # -Supersprache aus, und löst unsere Aufgabe:

///

/// Lösungsberechnungsprogramm

/// logische Gleichung (System von Gleichungen)

///

///

/// logische Funktion - Methode,

/// Unterschrift, die vom DF-Delegierten festgelegt ist

///

/// anzahl der Variablen

/// Anzahl der Lösungen.

statische Int-Lasenfeststellungen (DF-Spaß, Int N)

bool set \u003d new bol [n];

int m \u003d (int) math.pow (2, n); // Anzahl der Sets

int p \u003d 0, q \u003d 0, k \u003d 0;

// volle Büste in der Anzahl der Sets

für (int i \u003d 0; ich< m; i++)

// das nächste Set-Set bilden,

// durch binäre Darstellung der Nummer i gegeben

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

k \u003d (int) math.pow (2, j);

// Berechnen Sie den Funktionswert auf dem Set-Set

Um das Programm zu verstehen, hoffe ich genügend Erklärungen zur Idee des Programms und der Kommentare in seinem Text. Ich werde nur auf der Erklärung der Titelfunktion wenden. Die Fundamentfunktion hat zwei Eingabeparameter. Der Fun-Parameter legt eine logische Funktion fest, die der gelösten Gleichung oder dem System von Gleichungen entspricht. Parameter n Legt die Nummer fest funktionsvariablen Spaß. Infolgedessen kehrt die Fundamentfunktion die Anzahl der Lösungen einer logischen Funktion zurück, dh die Anzahl dieser Sets, auf denen die Funktion erfüllt ist.

Für Schüler ist bekannt, wenn einige Funktion f (x) Eingangsparameter X eine Variable von Arithmetik-, Zeichenfolge oder logischem Typ ist. In unserem Fall wird ein leistungsfähigeres Design verwendet. Die Funktionen des Lasenwaffens bezieht sich auf die höchsten Auftragsfunktionen - Funktionen des Typs F (f), in dem die Parameter nicht nur einfache Variablen sein können, sondern auch Funktionen.

Die Klassenklasse, die als Funktionsparameter des Lasenfreamens übertragen werden kann, wird wie folgt angegeben:

delegate bool df (bool vars);

Diese Klasse gehört zu allen Funktionen, die der Parameter als Satz von Werten von logischen Variablen übertragen wird, die vom VARS-Array angegeben sind. Infolgedessen wird der Wert des booleschen Typs zurückgegeben, der den Wert der Funktion in diesem Satz darstellt.

Abschließend werde ich ein Programm geben, in dem die Solvennarbenfunktion verwendet wird, um mehrere logische Gleichungensysteme zu lösen. Die Solveeakrationsfunktion ist Teil der Programmlautklasse unten:

klassenprogrammCommon.

delegate bool df (bool vars);

statische Hauptmagentur (String-Args)

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

Solveefaktoren (FOLUMAGE, 2));

Console.writine ("Die Funktion 51 Lösungen -" +

Loveeequations (FUN51, 5));

Console.writine ("Die Funktion 53 von Lösungen -" +

Loveeequations (FUN53, 10));

statischer Bool Funand (Bool Vars)

rückgabe vars && vars;

statischer Bool Fun51 (Bool Vars)

f \u003d F && (! Vars || vars);

f \u003d F && (! Vars || vars);

f \u003d F && (! Vars || vars);

f \u003d F && (! Vars || vars);

f \u003d F && (! Vars || vars);

statischer BOOL FUN53 (BOOL VARS)

f \u003d f && (vars \u003d\u003d vars) || (vars \u003d\u003d vars));

f \u003d f && (vars \u003d\u003d vars) || (vars \u003d\u003d vars));

f \u003d f && (vars \u003d\u003d vars) || (vars \u003d\u003d vars));

f \u003d f && (vars \u003d\u003d vars) || (vars \u003d\u003d vars));

f \u003d f && (vars \u003d\u003d vars) || (vars \u003d\u003d vars));

f \u003d f && (vars \u003d\u003d vars) || (vars \u003d\u003d vars));

f \u003d F && (! ((vars \u003d\u003d vars) || (vars \u003d\u003d vars)););

Hier sehen die Ergebnisse der Entscheidung über dieses Programm aus wie:

10 Aufgaben für unabhängige Arbeit

1. Welcher der drei Funktionen ist gleichwertig:
   1. (X → y) ˅ ^y
   2. ¬ (x ˅ →) (x → ^y)
   3. ¬x y.
2. DAN-Fragment der Wahrheitstabelle:

X 1	X 2.	X 3.	X 4.	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 ˅ ˅ × 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 beinhaltet drei Personen. Die Entscheidung wird getroffen, wenn der Vorsitzende der Jury für ihn stimmt, unterstützt von mindestens einem der Mitglieder der Jury. Andernfalls wird die Entscheidung nicht akzeptiert. Erstellen Sie eine logische Funktion, die den Entscheidungsprozess formatalisiert.
5. X gewinnt y, wenn mit vier Gussteilen die Münzen dreimal "Eagle" ausfallen. Stellen Sie die logische Funktion ein, die den Gewinn X beschreibt.
6. Wörter im Vorschlag sind nummeriert, beginnend mit dem Gerät. Der Vorschlag gilt als richtig aufgebaut, wenn folgende Regeln befolgt werden:
   1. Wenn auch bei der Nummerierung des Wortes auf dem Vokal endet, sollte das nächste Wort, wenn er existiert, mit Vokalen beginnen.
   2. Wenn das seltsame, in dem das Wort den Konsonanten beendet, das nächste Wort, wenn er existiert, mit dem Konsonanten beginnen und mit Vokalen enden.
      Welche der folgenden Angebote sind korrekt gebaut:
   3. Mama Seife Masha Seife.
   4. Der Anführer ist immer ein Beispiel.
   5. Wahres Gut und Glück ist besser.
7. Wie viele Lösungen haben eine Gleichung:
   (A ¬ b) ˅ (¬ b) → (c d) \u003d 1
8. Listen Sie alle Lösungen der Gleichung auf:
   (A → b) → c \u003d 0
9. Wie viele Lösungen haben das folgende System von Gleichungen:
   X 0 → x 1 x 1 → x 2 \u003d 1
   X 2 → x 3 x 3 → x 4 \u003d 1
   X 5 → x 6 x 6 → x 7 \u003d 1
   X 7 → x 8 x 8 → x 9 \u003d 1
   X 0 → x 5 \u003d 1
10. Wie viele Lösungen haben eine Gleichung:
    (((((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 \u003d 1

Antworten auf Aufgaben:

1. Äquivalent sind Funktionen B und C.
2. Das Fragment entspricht der Funktion b.
3. Lassen Sie die logische Variable P den Wert von 1 akzeptieren, wenn der Vorsitzende der Jury "für die Entscheidungsfindung" stimmt. Die Variablen M 1 und M2 stellen die Meinung der Mitglieder der Jury dar. Eine logische Funktion, die eine positive Entscheidung angibt, kann wie folgt aufgenommen werden:
   P (m 1 ˅ m 2)
4. Lassen Sie die logische Variable P i Wert 1 annehmen, wenn, mit dem I-M, mit dem I-M die Münze tropfen "Orel" werfen. Die logische Funktion, die das Gewinn X angibt, kann wie folgt aufgenommen werden:
   ¬ ((¬ p 1 (§ 2 ˅ § 3 ˅ · · · § 4)) ˅
   (§ 2 (§ 3 ˅ § 4)) ˅
   (§ 3 · 4))
5. Angebot b.
6. Die Gleichung hat 3 Lösungen: (A \u003d 1; B \u003d 1; c \u003d 0); (A \u003d 0; B \u003d 0; c \u003d 0); (A \u003d 0; B \u003d 1; c \u003d 0)

Lösung logischer Gleichungssysteme in tabellarischen Methoden durch Umwandlung logischer Ausdrücke.

Diese Technik basiert auf der Verwendung von Wahrheitstabellen, berechnet an Studenten, die die Methoden der Umwandlung logischer Ausdrücke besitzen. Wenn die Schüler diese Methoden nicht besitzen, können Sie ohne Transformationen verwenden. (Wir werden Transformationen verwenden). Um diese Lösung zu beherrschen, ist es notwendig, das Wissen der Eigenschaften der grundlegenden logischen Operationen zu kennen: Verbindungen, Disjunktionen, Inversionen, Implikationen und Gleichwertigkeit.

Algorithmus zur Lösung von Gleichungen von Gleichungen bei dieser Methode:

Konvertieren Sie eine logische Gleichung, um sie zu vereinfachen.

Bestimmen Sie die Reihenfolge der Lösung der Gleichungen im System, da in den meisten Fällen in den meisten Fällen eine sequentielle Lösung von Gleichungen von oben nach unten gibt (wie sie sich im System befinden), aber es gibt Optionen, wenn es bequemer ist, ist es einfacher zu Beginnen Sie mit der Entscheidung von unten nach oben.

Erstellen Sie eine Tabelle mit Variablen, in denen die Anfangswerte der ersten Variablen (oder zuletzt) \u200b\u200beingestellt werden sollen.

Registrieren Sie nacheinander die möglichen Optionen für die folgende Variable, wenn jeder Der erste Wert.

Nach dem Lösen der vorherigen Gleichung, um sich auf das Folgende zu bewegen, achten Sie darauf, dass Sie darauf achten: Welche Variablen werden in der vorherigen und anschließenden Gleichung verwendet, da die in den vorherigen Gleichungen erhaltenen variablen Werte als Varianten für die folgenden Gleichungen übertragen werden.

Achten Sie auf die daraus resultierenden Mengen an Lösungen während des Übergangs zur nächsten Variablen, weil Kann in zunehmenden Lösungen regelmäßig erkannt werden.

Beispiel 1.

¬ X.1 ˅ X.2=1

¬ X.2 ˅ X.3=1

¬ X.3 ˅ X.4=1

¬ X.9 ˅ X.10=1

Beginnen wir mit x1 und lassen Sie uns sehen, welche Werte diese Variable dauern kann: 0 und 1.

Betrachten Sie dann jeden dieser Werte und lassen Sie uns sehen, was er x2 sein kann.

Antwort: 11 Lösungen

Beispiel 2.

( X.einerX.2) ˅ (¬ ¬X.1-X.2) ˅( X.1↔ X.3)=1

( X.2X.3) ˅ (¬X.2-X.3) ˅( X.2↔ X.4)=1

(X8 x9) ˅ (¬x8-x9)˅ (x8 dochex10) \u003d 0

Wir konvertieren die Formel (EIN.˄ B.)˅ (¬ EIN. ˄ ¬ B.)= EIN.↔ B.

Wir bekommen:

( X.1↔ X.2) ˅ (X.1↔ X.3) =1

( X.2↔ X.3 (X.2↔ X.4) =1

( X.8↔ X.neun (X.8↔ X.10) =0

Für X1 \u003d 0 - 8 Lösungen

Nehmen Sie x1 \u003d 1 und lassen Sie uns sehen, welcher Wert x2 dauern kann. Berücksichtigen Sie jetzt für jedes X2, welche Werte X3 usw. annehmen können.

Für x1 \u003d 1 - 8-Lösungen

Insgesamt 8 + 8 \u003d 16 Lösungen

Antworten. 16 Entscheidungen

Beispiel 3. .

¬ ( X.1↔ X.2) ( X.einerX.3) (¬X.1 ˅ ¬X.3 )=0

¬ ( X.2↔ X.3) (X.2 ˅.X.4) (¬X.2 ˅ ¬X.4)=0

….

¬ ( X.8↔ X.neun (X.achtX.10) (¬X.8 ˅ ¬X.10)=0

Nach Transformationen (EIN.˅ B.) ˄(¬ EIN. ˅¬ B.)= ¬( EIN. ↔ B.)

wir bekommen:

¬ ( X.1↔ X.2) ¬ (X.1↔ X.3)=0

¬ ( X.2↔ X.3) ¬ (X.2↔ X.4)=0

…..

¬ ( X.8↔ X.9) ¬ (X.8↔ X.10)=0

Nehmen Sie x1 \u003d 0 und lassen Sie uns sehen, welcher Wert x2 dauern kann. Berücksichtigen Sie jetzt für jedes X2, welche Werte X3 usw. annehmen können.

Es stellte sich 10 Lösungen für x1 \u003d 0 heraus

Gleiches tun wir für x1 \u003d 1. Wir erhalten auch 10 Lösungen

Gesamt: 10 + 10 \u003d 20

Antwort: 20 Lösungen.

Beispiel 4.

(X1 x2) ˅ (¬ х1 ¬х2) ˅ (X2 x3) ˅ (¬ х2 ¬ x3)=1

(X2 x3) ˅ (¬ ¬ ¬ х3) ˅ (x3 x4) ˅ (¬ х3 ¬ x4) \u003d 1

….

(X8 x9) ˅ (¬ ¬х8 ¬х9) ˅ (x9 x10) ˅ (¬ х9 ¬ x10) \u003d 0

Wir transformieren von Formeln. (EIN.˄ B.)˅ (¬ EIN. ˄ ¬ B.)= EIN.↔ B.. Wir bekommen:

(X1. X2 x2) ˅ (X2. X3) \u003d 1

(X2. X3) ˅ (x3. x4) \u003d 1

(X3. X4) ˅ (X4. X5) \u003d 1

(X4. X5) ˅ (x5. x6) \u003d 1

(X5. x6) ˅ (x6. x7) \u003d 1

(X6. x7) ˅ (x7. x8) \u003d 1

(X7. X8) ˅ (x8 © x9) \u003d 1

(X8. x9) ˅ (x9. x10) \u003d 0

Beginnen wir am Ende, denn in der letzten Gleichung sind Variablen eindeutig definiert.

Sei x10 \u003d 0, dann x9 \u003d 1, x8 \u003d 0, x7 \u003d 0, x6 \u003d 0, und die folgenden Variablen können unterschiedliche Werte annehmen. Wir werden jeden betrachten.

Gesamt 21 Lösung für x10 \u003d 0

Betrachten Sie jetzt X10 \u003d 1. Wir bekommen auch 21 Beschluss

Gesamt: 21 + 21 \u003d 42

Antwort: 42 Lösungen

Beispiel 5

( X.einerX.2) ˅ (¬ ¬X.1 ¬X.2) ˅ (¬ ¬X.3.X.vier (X.3 ¬X.4)=1

( X.3.X.4) ˅ (¬X.3 ¬X.4) ˅ (¬X.fünfX.6) ˅ (X.5 ¬X.6)=1

( X.fünfX.6) ˅ (¬ ¬X.5 ¬X.6) ˅ (¬ ¬X.7.X.acht (X.7 ¬X.8)=1

( X.7.X.8) ˅ (¬X.7 ¬X.8) ˅ (¬ X.neunX.10 (X.9 ¬X.10) =1

Wir transformieren von Formeln:(¬ EIN. ˄ B.) ˅ ( EIN. ˄ ¬ B.)= EIN.↔ ¬ B.

( EIN.˄ B.)˅ (¬ EIN. ˄ ¬ B.)= EIN.↔ B.

( X.1↔ X.2) ˅ (X.3 ↔ ¬X.4)=1

( X.3↔ X.vier (X.5 ↔ ¬X.6)=1

( X.5↔ X.6) ˅ (X.7 ↔ ¬X.8)=1

( X.7↔ X.acht (X.9 ↔ ¬X.10)=1

Überlegen Sie, welche Werte X1 und X2 annehmen können: (0,0), (0,1), (1,0), (1,1).

Berücksichtigen Sie jede Option und lassen Sie uns sehen, welche Werte X3, X4 dauern können

Beginnend mit x7, x8 werden wir sofort die Anzahl der Lösungen aufschreiben, da er sofort bewiesen wird, dass, wenn die Werte identisch (1,1) und (0,0) sind, dann haben die folgenden Variablen 4 Lösungen und wann anders (0,1) und (1 0) - 2-Lösungen.

Gesamt: 80 + 80 + 32 \u003d 192

Antwort: 192 Entscheidungen

Beispiel 6.

(X1. X2) ˅ (x2 ↔x3) \u003d 1

(X2. X3 x3) ˅ (x3 ärztx4) \u003d 1

(X3. X4) ˅ (x4 ↔H5) \u003d 1

….

(X8. x9 x9) ˅ (x9 ↔H10) \u003d 1

Nehmen Sie x1 \u003d 0 und lassen Sie uns sehen, welcher Wert x2 dauern kann. Berücksichtigen Sie jetzt für jedes X2, welche Werte X3 usw. annehmen können.

Wir sehen ein Muster: Die Anzahl der folgenden Entscheidungen entspricht der Summe der beiden vorherigen.

Dasselbe für x1 \u003d 1 Wir erhalten 89 Lösungen

Gesamt: 89 + 89 \u003d 178 Lösungen

Antwort: 178 Lösungen

Lass uns auf eine Weise entscheiden

(X1. X2) ˅ (x2 ↔x3) \u003d 1

(X2. X3 x3) ˅ (x3 ärztx4) \u003d 1

(X3. X4) ˅ (x4 ↔H5) \u003d 1

….

(X8. x9 x9) ˅ (x9 ↔H10) \u003d 1

Wir führen einen Ersatz vor:

T.1 =(X1. X2 x2)

T.2 =(X2. X3 X3)

T.3 =(X3. X4)

T.4 =(X4. X5 X5)

T.5 =(X5. x6)

T.6 =(X6. X7 x7)

T.7 =(X7. X8)

T.8 =(X8. x9)

T.9 =(X9. X10 x10)

Wir bekommen:

T.einerT.2=1

T.2 ˅.T.3=1

T.3T.4=1

T.vier.T.5=1

T.fünfT.6=1

T.6 ˅.T.7=1

T.7 ˅.T.8=1

T.achtT.9=1

T.neunT.10=1

NehmenT.1 \u003d 1 und nutzen Sie die Eigenschaften der Disjunktion:

Aber denken Sie daran

T.1 =(X1. X2 x2)

T.2 =(X2. X3 x3) usw.

Wir verwenden die Äquivalenzeigenschaft und stellen Sie sicher, dass Sie den Tisch betrachten

Wenn t \u003d 1, werden zwei Lösungen erhalten. Und wann \u003d 0 - aber die Lösung.

Daher können Sie die Anzahl der Einheiten berechnen und sie durch 2+ Anzahl von Nullen multiplizieren. Zählen, auch in der Regelmäßigkeit.

Es stellt sich heraus, dass die Anzahl der Einheiten \u003d bisherige Gesamtzahl der Lösungen T und die Anzahl der Nullen gleich der vorherigen Anzahl von Einheiten ist

So. Wir bekommen. Da das Gerät zwei Lösungen ergibt, dann 34 * 2 \u003d 68 Lösungen von einer + 21-Lösung von 0.

Insgesamt 89 Lösungen für T \u003d 1. In gleicher Weise erhalten wir 89 Lösungen für t \u003d 0

Insgesamt 89 + 89 \u003d 178

Antwort: 178 Lösungen

Beispiel 7.

(X.1 ↔ X.2) ˅ (X.3↔ X.4) ¬ (X.1 ↔ X.2) ˅ ¬ (X.3↔ X.4)=1

(X.3 ↔ X.vier (X.5↔ X.6) ¬ (X.3 ↔ X.4) ˅ ¬ (X.5↔ X.6)=1

(X.5 ↔ X.6) ˅ (X.7↔ X.8) ¬ (X.5 ↔ X.6) ˅ ¬ (X.7↔ X.8)=1

(X.7 ↔ X.acht (X.9↔ X.10) ¬ (X.7 ↔ X.8) ˅ ¬ (X.9↔ X.10)=1

Wir führen einen Ersatz vor:

T.1=(X.1 ↔ X.2)

T.2=(X.3↔ X.4)

T.3=(X.5↔ X.6)

T.4=(X.7 ↔ X.8)

T.5=(X.9↔ X.10)

Wir bekommen:

(T1 ˅ t2) ¬ (t1 ˅ ˅ t2) \u003d 1

(T2 ˅ t3) ¬ (t2˅ \u003d t3) \u003d 1

(T3 ˅ t4) ¬ ¬ (t3 ˅ t4) \u003d 1

(T4 ˅ T5) ¬ ¬ (t4˅ \u003d t5) \u003d 1

Überlegen Sie, was sein kann:

T1.

T2.

T3.

T4.

T5.

GESAMT

0

1

0

1

0

32

1

0

1

0

1

32

T. K. ≠ T. K + 1. Und T. K. \u003d T. K + 2.

Wir bekommen: 2 5 \u003d 32 für t

Gesamt: 32 + 32 \u003d 64

Antwort: 64 Lösungen.

Lösung der Gleichung 1. Transfix auf die Präfixform der Aufzeichnung der Gleichung, wodurch die Ablehnung der Verweigerungsbezeichnung ersetzt wird, um den Titel der Wahrheitstabelle eines speziellen Typs zu ¬ upieren. 3. Um die Reihen der Wahrheitstabelle für alle zu füllen Kombinationen A und B, Ersetzen anstelle von x - 0 oder 1. 4.Deine Wahrheitstabelle für x \u003d f (a, b) 5. In der Wahrheitstabelle ist es notwendig, die Form der X-Funktion, falls erforderlich, zu ermitteln mit den Methoden zum Erstellen von SCPF und der SDNF, die unten diskutiert werden.

Konstruktion der Wahrheitstabelle einer speziellen Form ¬ ((a + b) · (· a · b)) \u003d ¬ · · (b + · · a))

Die Wahrheitstabelle x \u003d f (a, b) abx entspricht der Ablehnung der Implikation in der Antwort:

Kombinationsdiagramme von logischen Geräten Basiselementen (GOST): 1 A in Disjunktion in Äquivalenz & in Verbindung M2 A in XOR

Kombinationsdiagramme von logischen Geräten Basiselementen (GOST): 1 A in Implikation & und in das Hedere-Element und in der 1 A-Spule in der Webb

BEISPIEL F 1 & 1 & 1M2 B A Schema

Lösung der Schemata 1-Option ist die Umwandlung der Schaltung in einen komplexen logischen Ausdruck und vereinfacht sie anschließend nach den Gesetze der Logik. 2 Option - Erstellen einer Wahrheitstabelle und dann, falls erforderlich, durch SKFF oder IDNF (siehe unten). Betrachten Sie die zweite Option als einfacher und verständlich.

Bau der Wahrheitstabelle AB A + B + · B B · A + A B A + · ·

Die Wahrheitstabelle F (a, b) abx entspricht der Ablehnung der Implikation in einer Antwort:

Die SDNF- und SCFF (Definition) der elementaren Verbindung ist die Verbindung mehrerer Variablen, die mit der Ablehnung oder ohne Ablehnung aufgenommen wurden, und zwischen Variablen können die gleiche elementare Disjunktion sein, die als Disjunktion von mehreren Variablen bezeichnet wird, die mit der Ablehnung oder ohne negativ genommen wurden, und zwischen Variablen Seien Sie derselbe von jeder Unheilung von elementaren Konjunktionen. Wir nennen eine disjunktive Normalform (DNF) eine beliebige Verbindung von elementaren Disjunktionen mit einer konjunktiven Normalform (DNF).

Die SDNF- und SCFF (Definition) der perfekten disjunktiven Normalform (CDNF) wird als DNF bezeichnet, in dem es keine identischen elementaren Konjunktionen gibt, und alle Konjunktionen bestehen aus demselben Satz von Variablen, in denen jede Variable nur einmal eintritt (möglicherweise mit der Ablehnung) . Die perfekte konjunktive Normalform (SCPF) wird als KNF bezeichnet, in dem es keine identischen elementaren Disjunktionen gibt, und alle Disjunktionen bestehen aus demselben Satz von Variablen, in denen jede Variable nur einmal eintritt (möglicherweise mit der Ablehnung).

Algorithmus zum Erhalten eines CDNF auf der Wahrheitstabelle 1. Totale Wahrheitstischlinien in der letzten Spalte sind in der letzten Spalte 1. 2. Schreiben für jede markierte Zeile Die Verbindung aller Variablen wie folgt: Wenn der Wert der Variablen in dieser Zeile in dieser Zeile ist 1, dann in der Konjunktion, enthalten diese Variable selbst, wenn auch 0, dann seine Ablehnung. 3. Alle erhaltenen Konjunktionen sind mit dem Disjunkt verbunden. Algorithmus zum Erhalten von Skff auf der Wahrheitstabelle 1. Die Aufmerksamkeit der Wahrheitstischlinien in der letzten Spalte von denen 0 0 ist. 2. Achten Sie auf jede markierte Linie, um alle Variablen wie folgt zu disjizieren: Wenn der Wert der Variablen in dieser Zeile in dieser Zeile ist 0, dann in der Verbindung, um diese Variable selbst aufzunehmen, wenn gleich 1, dann seine Ablehnung. 3. Alle erhaltenen Disjunktionen sind in Verbindung verbunden.

Ein Beispiel für das Erstellen eines Sknf XY F (x, y) in HINWEIS Zeros 2. Dysuunction: X + Y 3. Konjunktion: (x + y) · (x + y)

Lassen Sie die logische Funktion von n Variablen sein. Die logische Gleichung ist:

Konstante C hat einen Wert von 1 oder 0.

Die logische Gleichung kann von 0 zu verschiedenen Lösungen haben. Wenn C gleich 1 ist, sind Lösungen alle Seiten von Variablen von der Wahrheitstabelle, auf denen die Funktion F den Wert der Wahrheit (1) nimmt. Die verbleibenden Kits sind Lösungen der Gleichung bei c gleich Null. Sie können immer nur die Gleichungen des Formulars berücksichtigen:

Lassen Sie die Gleichung eingestellt:

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

Betrachten Sie das System von k logischen Gleichungen:

Die Lösung des Systems ist ein Satz von Variablen, auf denen alle Systemgleichungen durchgeführt werden. Um eine Lösung des logischen Gleichungssystems zu erhalten, sollten Sie in Bezug auf logische Funktionen ein Set finden, auf dem die logische Funktion F wahr ist, die die Konjunktion der Quellfunktionen darstellt:

Wenn die Anzahl der Variablen beispielsweise klein ist, beispielsweise weniger als 5, ist es nicht schwierig, eine Wahrheitstabelle für eine Funktion zu erstellen, mit der Sie sagen können, wie viele Lösungen ein System haben und welche Sets, die Lösungen ergeben.

In einigen Aufgaben der EGE, um Lösungen des Systems logischer Gleichungen zu finden, erreicht die Anzahl der Variablen einen Wert von 10. Aufbau einer Wahrheitstabelle wird zu einer praktisch einschädlichen Aufgabe. Um das Problem zu lösen, ist ein anderer Ansatz erforderlich. Für ein beliebiges Gleichungssystem von Gleichungen gibt es keine gemeinsame Methode als das Busting, mit dem Sie solche Aufgaben lösen können.

In den auf der Prüfung vorgeschlagenen Aufgaben basiert die Lösung in der Regel auf den Besonderheiten des Gleichungssystems. Ich wiederhole, neben der Suche nach allen Varianten des Variablensatzes gibt es keine allgemeine Möglichkeit, das Problem zu lösen. Die Entscheidung muss basierend auf den Besonderheiten des Systems erstellt werden. Es ist häufig nützlich, die Vorvereinbarkeit des Gleichungssystems mit bekannten Logikgesetzen zu vereinfachen. Ein weiterer nützlicher Empfang der Lösung dieser Aufgabe ist wie folgt. Wir sind nicht an allen Sätzen interessiert, sondern nur diejenigen, auf denen die Funktion wichtig ist für 1. Anstelle eines kompletten Wahrheitstisches bauen wir analog - ein binärer Baumlösungen. Jeder Zweig dieses Baums entspricht einer Lösung und legt den Set ein, auf dem die Funktion ankommt. Die Anzahl der Zweige des Lösungsbaums fällt mit der Anzahl der Lösungen des Gleichungssystems zusammen.

Was ist ein binärer Entscheidungsbaum und wie es gebaut ist, erklärt die Beispiele mehrerer Aufgaben.

Aufgabe 18.

Wie viele verschiedene Werte von Werten der logischen Variablen X1, X2, X3, X4, X5, Y1, Y2, Y3, Y4, Y5, die das System von zwei Gleichungen erfüllen?

Antwort: Das System verfügt über 36 verschiedene Lösungen.

Lösung: Das Gleichungssystem enthält zwei Gleichungen. Wir finden die Anzahl der Lösungen für die erste Gleichung von 5 Variablen. Die erste Gleichung kann wiederum als System von 5 Gleichungen betrachten. Wie gezeigt, repräsentiert das Gleichungssystem tatsächlich die Verbindung logischer Funktionen. Die inverse Anweisung trifft ebenfalls zu, die Verbindung der Bedingungen kann als Gleichungssystem betrachtet werden.

Wir erstellen die Muscheln für Implikationen () - das erste Mitglied der Verbindung, das als erste Gleichung betrachtet werden kann. Hier sieht das grafische Bild dieses Baums aus

Der Baum besteht aus zwei Ebenen nach Anzahl der Gleichungsvariablen. Die erste Ebene beschreibt die erste Variable. Die beiden Zweige dieser Ebene spiegeln die möglichen Werte dieser Variablen - 1 und 0 auf. Auf der zweiten Ebene des Baumasts reflektieren nur diese möglichen variablen Werte, für die die Gleichung den Wert der Wahrheit ergreift. Da die Gleichung die Implikation angibt, erfordert der Zweig, auf dem er 1 wird, dass der Wert von 1. der Zweig, auf dem er 0 hat, zwei Zweige mit Werten erzeugt, wobei die Werte gleich 0 und 1. der aufgebaute Baum erzeugt drei Lösungen Welche Implikation nimmt einen Wert 1. In jedem Zweig ist ein geeigneter Satz variabler Werte, die die Lösung der Gleichung ergibt, entlassen.

Dies sind diese Sets: ((1, 1), (0, 1), (0, 0))

Wir werden weiterhin einen Lösungsbaum erstellen, indem wir folgende Implikation die folgende Gleichung hinzufügen. Die Besonderheiten unseres Gleichungssystems sind, dass jede neue Gleichung des Systems eine Variable von der vorherigen Gleichung verwendet und eine neue Variable hinzufügt. Da die Variable bereits Werte auf einem Baum hat, auf allen Zweigen, in denen die Variable 1 ist, hat die Variable auch einen Wert 1. Für solche Zweige wird der Bau eines Baums auf der nächsten Ebene fortgesetzt, aber neue Zweige dienen nicht auftauchen. Der einzige Zweig, in dem die Variable 0 ist, wird verzweigt in zwei Zweige, wobei die Variable den Wert 0 und 1 empfängt. Somit fügt jeweils eine neue Gleichung, angesichts seiner Spezifität, eine Lösung hinzu. Quelle erste Gleichung:

hat 6 Lösungen. Hier ist der volle Baum von Lösungen für diese Gleichung:

Die zweite Gleichung unseres Systems ist dem ersten ähnlich:

Der einzige Unterschied besteht darin, dass die Gleichungen Variablen y verwenden. Diese Gleichung hat auch 6 Lösungen. Da jede Lösung für Variablen mit jeder Lösung für Variablen kombiniert werden kann, ist die Gesamtzahl der Lösungen gleich 36.

Hinweis, der baute Lösungsbaum gibt nicht nur die Anzahl der Lösungen (durch die Anzahl der Zweige), sondern auch die Entscheidungen selbst, die sich auf jedem Zweig des Baums entlassen haben.

Aufgabe 19

Wie viele verschiedene Werte von Werten der logischen Variablen X1, X2, X3, X4, X5, Y1, Y2, Y3, Y4, Y5, die alle unten aufgeführten Bedingungen erfüllen?

Diese Aufgabe ist eine Änderung der vorherigen Aufgabe. Der Unterschied besteht darin, dass eine andere Gleichung, die die Variablen X und Y anschließt, zugegeben wird.

Es folgt aus der Gleichung, dass, wenn er einen Wert von 1 (eine solche Lösung existiert So und 1. Daher entspricht jedes mit 0 eingestellte, und solche Sätze 5 entsprechen allen 6 Sätzen mit variabler y. Daher ist die Gesamtzahl der Lösungen gleich 31.

Aufgabe 20.

Lösung: Erinnern an die wichtigste Äquivalenz, schreibt unsere Gleichung in das Formular aus:

Die cyclische Kette der Implikationen bedeutet Identität von Variablen, so dass unsere Gleichung der Gleichung entspricht:

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

Aufgabe 21.

Wie viele Lösungen haben eine Gleichung:

Lösung: Wie bei dem Problem 20 bewegen wir uns mit zyklischen Auswirkungen auf die Identitäten, wodurch die Gleichung im Formular umgeschrieben wird:

Wir erstellen den Lösungsbaum für diese Gleichung:

Aufgabe 22.

Wie viele Lösungen haben das folgende Gleichungssystem?