Belova T.V.
wie man lehrt, wie man Aufgabe 18 des Einheitlichen Staatsexamens in Informatik löst

kommunale Haushaltsbildungseinrichtung "Lyceum",

Arsamas, Ja. bellova. tatjana@ Yandex. ru

Bevor Sie mit der Lösung der Aufgaben 18 „Überprüfung der Wahrheit eines logischen Ausdrucks“ der Prüfungsarbeit in Informatik beginnen, müssen Sie den Schülern erklären (oder sich daran erinnern), was das Konzept der „Vereinigung“ und „Schnittmenge“ mehrerer Mengen ist. Und da Aufgabe 18 mit der Definition von Segmenten zusammenhängt, ist es am besten, diese Konzepte anhand von Segmenten zu erklären. Es ist jedoch notwendig, diese Konzepte mit den Konzepten der logischen Algebra zu verbinden – „Konjunktion“ und „Disjunktion“ und natürlich „Inversion“. Ich gebe Ihnen ein Beispiel. Betrachten wir zunächst die Umkehrung eines Segments oder einfacher gesagt die Negation eines Segments.

Das Segment P= ist gegeben. Finden Sie die Segmente, die die Umkehrung des Segments P= darstellen. Betrachten Sie die Koordinatenlinie (Abb. 1):

Reis. 1

Auf der Geraden markieren wir das Segment P (blauer Bereich), dann ist klar, dass die Intervalle, die nicht P sind, Intervalle und (grüner Bereich) sind – Abb. 1. Beachten Sie, dass die Punkte 6 und 15 nicht in die Umkehrung des Segments einbezogen werden.

Betrachten wir ein weiteres Beispiel: Es werden zwei Segmente P= und Q= vorgegeben (es werden die gleichen Notationen wie in der Einheitlichen Staatsexamensaufgabe angegeben, damit sich die Studierenden sofort an die Notationen gewöhnen). Suchen Sie ein Segment, das die Konjunktion (Vereinigung) und Disjunktion (Schnittpunkt) dieser Segmente bezeichnet

Wir zeichnen Segmente auf der Koordinatenlinie (Abb. 2):

Reis. 2

Zuerst markieren wir die Bereiche auf der Koordinatenlinie, die die Segmente P (blau) und Q (gelb) anzeigen. Dann bestimmen wir, welcher Teil der Koordinatenlinie als Verbindung dieser beiden Segmente dient. Hier erinnern wir uns daran, dass die Konjunktion eine logische Operation ist, die zwei einfache Aussagen mithilfe der logischen Verknüpfung „und“ zu einer komplexen Aussage kombiniert, und dass die komplexe Aussage genau dann die Bedeutung „wahr“ erhält, wenn beide ursprünglichen einfachen Aussagen wahr sind. Daher müssen wir Regionen finden, in denen sowohl das Segment P als auch das Segment Q existieren, und es gibt nur eine solche Region – das Segment (rot). Wir werden alle geraden Abschnitte detaillierter studieren, damit die Schüler den Stoff klarer und besser verstehen können, also:

Schauen wir uns nun die Disjunktion dieser Segmente auf ähnliche Weise an. Wenden wir uns noch einmal der Definition dieser logischen Operation zu: „Disjunktion ist eine logische Operation, die gemäß zwei oder mehr logischen Aussagen eine neue einfügt, die genau dann wahr ist, wenn mindestens eine der eingegebenen Anfangsaussagen wahr ist.“ WAHR." Das heißt, mit anderen Worten, wir müssen Intervalle auf der Koordinatenlinie finden, in denen sich mindestens eines unserer ursprünglichen Segmente befindet. Dieses gewünschte Intervall wird grün sein (Abb. 2). Wir werden auch jedes der Intervalle analysieren und zeigen, dass dies tatsächlich der Fall ist:

Durch die Kombination der gefundenen Intervalle erhalten wir, dass das erforderliche Segment, das die Disjunktion der ursprünglichen Segmente angibt, das Segment ist – grün (Abb. 2).

Nachdem Sie dieses Beispiel analysiert haben, können Sie die Schüler versuchen lassen, verschiedene Kombinationen logischer Operationen zu finden – Disjunktion, Konjunktion und Negation. Zum Beispiel seien zwei Segmente gegeben: P=[-4,10] und Q=. Suchen Sie ein Segment, das die folgenden logischen Operationen bezeichnet: , , (Sie können sich verschiedene andere Kombinationen dieser logischen Operationen ausdenken).

Reis. 3

Reis. 4

Reis. 5

Wenn alle Beispiele analysiert sind, werden die Studierenden keine Schwierigkeiten haben, die Aufgabe Nr. 18 aus der Prüfungsarbeit des Einheitlichen Staatsexamens in Informatik zu verstehen und zu lösen.

Hier finden Sie Lösungsbeispiele für mehrere Aufgaben:

Auf der Zahlengeraden gibt es zwei Segmente: P = und Q =. Wählen Sie ein Segment A, so dass die Formel

(X  A) → ((X  P) → (X  Q)) ist identisch wahr, das heißt, es nimmt für jeden Wert der Variablen den Wert 1 an X. Mögliche Antworten:

1) 2) 3) 4)

Lösung (Abb. 6): Um das Verständnis des Ausdrucks zu vereinfachen, bezeichnen wir einzelne Aussagen mit Buchstaben - A: X A,P: X P,Q: X Q. Somit erhalten wir unter Berücksichtigung der Ersetzung den folgenden Ausdruck: → ( P→ )=1. Die Gleichheit von Ausdruck 1 bedeutet, dass unabhängig vom Wert der Variablen X Wir haben es nicht genommen, unser logischer Ausdruck nimmt den Wert 1 an, also auf dem gesamten Zahlenstrahl. Erinnern wir uns an einige logische Gesetze und Gleichheiten und transformieren unseren Ausdruck: =1. Als Ergebnis stellen wir fest, dass wir eine Disjunktion aus drei Segmenten konstruieren müssen, von denen uns zwei bekannt sind. Wir werden sie bauen (Abb. 7). Zunächst müssen wir, wie in allen obigen Beispielen, die Umkehrungen der Segmente P (orange) und Q (rot) konstruieren. Aus dem gesamten Ausdruck können wir dann die Disjunktionsintervalle =1 bestimmen (grüne Bereiche in Abb. 7). Somit stellen wir fest, dass wir einen „freien“ Teil auf der Koordinatenlinie haben - . Dieser Teil ist gerade und muss das gewünschte Segment überlappen A.

Um dieses Problem zu lösen, müssen wir mehrere logische Schlussfolgerungen ziehen, also „passen Sie auf Ihre Hände auf.“

1. Sie wollen, dass wir die kleinste nicht negative ganze Zahl A finden, für die der Ausdruck immer wahr ist.
2. Was ist der Ausdruck insgesamt? Da ist etwas Implikation Da steht etwas in Klammern.
3. Erinnern wir uns zur Implikation an die Wahrheitstabelle:
   1 => 1 = 1
   1 => 0 = 0
   0 => 1 = 1
   0 => 0 = 1
4. Das bedeutet, dass es drei Möglichkeiten gibt, wie dies wahr sein kann. Alle drei Optionen in Betracht zu ziehen bedeutet, sich selbst zu töten und nicht zu leben. Denken wir darüber nach, ob wir „im Widerspruch“ vorgehen können.
5. Anstatt nach A zu suchen, versuchen wir, x zu finden, für das dieser Ausdruck falsch ist.
6. Nehmen wir also die Zahl A (wir wissen noch nicht, was es ist, nur einige). Wenn wir plötzlich ein x finden, für das die gesamte Aussage falsch ist, dann ist das gewählte A schlecht (weil die Bedingung verlangt, dass der Ausdruck immer wahr ist)!
7. Auf diese Weise können wir einige Einschränkungen für die Zahl A erhalten.
8. Gehen wir also einen Schritt zurück und erinnern uns, wann eine Implikation falsch ist? Wenn der erste Teil wahr und der zweite Teil falsch ist.
9. Bedeutet
   \((\mathrm(x)\&25\neq 0)= 1 \\ (\mathrm(x)\&17=0\Rightarrow \mathrm(x)\&\mathrm(A)\neq 0) = 0\)
10. Was bedeutet es, dass \((x\&25\neq 0) = 1\) ? Dies bedeutet, dass tatsächlich \(\mathrm(x)\&25\neq 0\) .
11. Lassen Sie uns 25 in Binär umwandeln. Wir erhalten: 11001 2 .
12. Welche Einschränkungen ergeben sich dadurch für x? Da es ungleich Null ist, bedeutet das, dass bei einer bitweisen Konjunktion das Ergebnis irgendwo eins sein muss. Aber wo könnte sie sein? Nur wo 25 schon eine Einheit hat!
13. Das bedeutet, dass die Zahl x in mindestens einem Kreuz eine Einheit enthalten muss: XX**X.
14. Großartig, schauen wir uns nun den zweiten Faktor an: \((\mathrm(x)\&17=0\Rightarrow \mathrm(x)\&\mathrm(A)\neq 0) = 0\)
15. Dieser Ausdruck stellt auch eine Implikation dar. Darüber hinaus ist es genauso falsch.
16. Das bedeutet, dass sein erster Teil wahr und der zweite falsch sein muss.
17. Bedeutet
    \((\mathrm(x)\&17=0) = 1 \\ ((\mathrm(x)\&\mathrm(A)\neq 0) = 0) = 0\)
18. Was bedeutet es, dass \(\mathrm(x)\&17=0\) ? Die Tatsache, dass an allen Stellen, an denen in 17 Einsen stehen, in x Nullen stehen müssen (sonst ist das Ergebnis nicht 0).
19. Lassen Sie uns 17 in Binär umwandeln: 10001 2 . Das bedeutet, dass in x die letzte Stelle vom Ende und die 5. Stelle vom Ende Nullen enthalten müssen.
20. Aber hör auf, in Punkt 13 haben wir das zuletzt verstanden ODER um 4 vom Ende ODER 5 vom Ende sollte eins sein.
21. Denn laut Zeile 19 darf an der letzten oder fünften Stelle vom Ende keine Einheit stehen, was bedeutet muss sein auf Platz 4 vom Ende.
22. Das heißt, wenn wir wollen, dass an unserem x der gesamte Ausdruck falsch war, muss an der vierten Stelle vom Ende eine Einheit stehen: XX...XX1XXX 2.
23. Großartig, denken Sie jetzt an die letzte Bedingung: \((\mathrm(x)\&\mathrm(A)\neq 0) = 0\). Was bedeutet das?
24. Das bedeutet, dass das nicht stimmt \(\mathrm(x)\&\mathrm(A)\neq 0\).
25. Das ist tatsächlich \(\mathrm(x)\&\mathrm(A)=0\) .
26. Was wissen wir über x? Dass es am 4. Platz vom Ende eine Einheit gibt. Im Übrigen kann x fast alles sein.
27. Wenn wir möchten, dass der ursprüngliche Ausdruck in der Problemstellung immer wahr ist, dann tun wir sollte nicht finden x, was alle Bedingungen erfüllen würde. Wenn wir ein solches x finden würden, würde sich tatsächlich herausstellen, dass der ursprüngliche Ausdruck nicht immer wahr ist, was den Bedingungen des Problems widerspricht.
28. Dies bedeutet, dass diese allerletzte Bedingung einfach nicht erfüllt sein darf.
29. Wie kann es nicht erfüllt werden? Wenn wir nur zu 100 % sicher wären, dass bei einer bitweisen Konjunktion irgendwo eine Einheit übrig bleibt.
30. Und das ist möglich: Wenn es in A auch an der 4. Stelle vom Ende eine Einheit gibt, dann wird es aufgrund der bitweisen Konjunktion eine Einheit an der 4. Stelle vom Ende geben.
31. Was ist die kleinstmögliche Binärzahl mit einer 1 am 4. Ende? Offensichtlich 1000 2. Diese Nummer wird also die Antwort sein.
32. Es bleibt nur noch, es in eine Dezimalzahl umzuwandeln: \(1000_2=0\times 2^0 + 0\times 2^1 + 0\times 2^2 + 1\times 2^3=8\)

Antwort: das minimal mögliche A, das die Bedingungen erfüllt, entspricht 8.

Jewgeni Smirnow

IT-Experte, Informatiklehrer

Lösung Nr. 2

Ein etwas kürzerer Ansatz kann vorgeschlagen werden. Bezeichnen wir unsere Aussage als F = (A->(B->C)), wobei A die Aussage „X&25 ist ungleich 0“, B = „X&17=0“ und C = „X&A ist ungleich 0“ ist “.

Lassen Sie uns die Implikationen näher erläutern, indem wir das bekannte Gesetz X->Y = nicht(X) ODER Y verwenden. Wir erhalten F = A -> (nicht(B) ODER C) = nicht(A) ODER nicht(B) ODER C. Wir schreiben auch die Binärwerte der Konstanten 25 und 17 auf:

Unser Ausdruck ist ein logisches ODER von drei Aussagen:

1) nicht (A) – das bedeutet X&25 = 0 (Bits 0,3,4 von X sind alle 0)

2) nicht (B) – bedeutet, dass X&17 nicht gleich 0 ist (Bits 0 und 4 von X sind mindestens eines gleich 1)

3) C – weiß, dass X&A nicht gleich 0 ist (durch Maske A angegebene Bits, mindestens 1 ist gleich 1)

X ist eine beliebige Zahl. Alle seine Bits sind unabhängig. Daher ist es nur in einem einzigen Fall möglich, die Erfüllung einer Bedingung für die Bits einer beliebigen Zahl zu fordern – wenn es sich um dieselbe Maske (Bitmenge) handelt. Wir können feststellen, dass die Binärmaske 17 fast mit 25 identisch ist, nur Bit Nummer 3 fehlt. Wenn wir nun 17 durch Bit Nummer 3 ergänzen würden, würde sich der Ausdruck (nicht (B) ODER C) in nicht verwandeln (nicht A), d.h. in A = (X&25 ist ungleich 0). Anders ausgedrückt: Nehmen wir an, A=8 (Bit 3=1). Dann entspricht die Anforderung (nicht (B) B oder C) der Anforderung: (Mindestens eines der Bits 4,0 ist gleich 1) ODER (Bit 3 ist gleich 1) = (mindestens eines der Bits 0, 3,4 ist nicht gleich 1) - jene. Inversion not(A) = A = (X&25 ist ungleich 0).

Als Ergebnis haben wir festgestellt, dass, wenn A = 8, unser Ausdruck die Form F = nicht (A) ODER A annimmt, was gemäß dem Gesetz der ausgeschlossenen Mitte immer identisch wahr ist. Für andere, kleinere Werte von A kann keine Unabhängigkeit vom Wert von X erreicht werden, weil Die Masken kommen unterschiedlich daher. Nun, wenn es Einsen in den höchstwertigen Bits von A gibt, ändert sich in den Bits über 4 nichts, weil in den restlichen Masken haben wir Nullen. Es stellt sich heraus, dass die Formel nur dann zu einer Tautologie für ein beliebiges X wird, wenn A = 8 ist.

Dmitri Lisin

Aufgabe 18 Aufgabenkatalog. Logische Aussagen

1. Aufgabe 18 Nr. 701. Für welchen Namen ist die Aussage falsch:

(Der erste Buchstabe des Namens ist ein Vokal→ Der vierte Buchstabe des Namens ist ein Konsonant.

1) ELENA

2) VADIM

3) ANTON

4) FEDOR

Erläuterung.

Eine Implikation ist genau dann falsch, wenn die Prämisse wahr und die Konsequenz falsch ist. In unserem Fall – wenn der erste Buchstabe des Namens ein Vokal und der vierte Buchstabe ein Vokal ist. Der Name Anton erfüllt diese Bedingung.

Notiz.

Das gleiche Ergebnis ergibt sich aus den folgenden Transformationen: ¬ (A→ B) = ¬ (¬ A∨ B) = A∧ (¬B).

Die richtige Antwort finden Sie unter Nummer 3.

2. Aufgabe 18 Nr. 8666. Auf der Zahlengeraden gibt es zwei Segmente: P = und Q = . Geben Sie die größtmögliche Länge des Intervalls A an, für das die Formel gilt

(¬(xA)→ (XP))→ ((XA)→ (XQ))

ist identisch wahr, das heißt, es nimmt für jeden Wert der Variablen x den Wert 1 an.

Erläuterung.

Lassen Sie uns diesen Ausdruck umwandeln:

(¬ ( XA) → ( X P)) → (( X A) → ( XQ))

((XA)∨ (X P))→ ((X Nicht A)∨ (X Q))

¬(( XgehörteA) ∨ ( XgehörteP)) ∨ (( X gehörte nicht dazuA) ∨ ( X gehörteQ))

( Xgehörte nicht dazuA) ∧ ( Xgehörte nicht dazuP) ∨ ( X gehörteA) ∨ ( X gehörte nicht dazuQ)

( Xgehörte nicht dazuA) ∨ ( X gehörteQ)

Daher muss x entweder zu Q gehören oder nicht zu A. Das bedeutet, dass A vollständig in Q enthalten sein muss, um die Wahrheit für alle x zu erreichen. Dann kann es maximal zu ganz Q werden, also die Länge 15.

3. Aufgabe 18 Nr. 9170. Auf der Zahlengeraden gibt es zwei Segmente: P = und Q = .

Geben Sie die größtmögliche Länge des Segments A an, für das die Formel gilt

((XA)→ ¬(xP))→ ((XA)→ (XQ))

identisch wahr, das heißt, es nimmt für jeden Wert der Variablen den Wert 1 anX .

Erläuterung.

Lassen Sie uns diesen Ausdruck umwandeln.

(( X€ A) → ¬( XgehörteP)) → (( X gehörteA) → ( X gehörteQ))

(( Xgehörte nicht dazuA) ∨ ( Xgehörte nicht dazuP)) → (( X gehörte nicht dazuA) ∨ ( X gehörteQ))

¬((x gehörte nicht zu A)∨ (Xgehörte nicht zu P))∨ ((Xgehörte nicht zu A)∨ (Xgehörte zu Q))

Es stimmt, dass A∧ B∨ ¬A = ¬A∨ B. Wenn wir dies hier anwenden, erhalten wir:

(x gehört zu P)∨ (Xgehörte nicht zu A)∨ (x gehört zu Q)

Das heißt, entweder muss ein Punkt zu Q gehören oder zu P gehören oder nicht zu A gehören. Dies bedeutet, dass A alle Punkte abdecken kann, die P und Q abdecken. Das heißt, A = P Q = = . |A| = 48 - 10 = 38.

4. Aufgabe 18 Nr. 9202. Die Elemente der Mengen A, P, Q sind natürliche Zahlen, mit P = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20), Q = (3, 6, 9, 12, 15, 18, 21, 24, 27, 30).

Es ist bekannt, dass der Ausdruck

((XA)→ (XP))∨ (¬(xQ)→ ¬(xA))

wahr (d. h. nimmt den Wert 1 an) für jeden Wert der Variablen x.

5. Aufgabe 18 Nr. 9310. Die Elemente der Mengen A, P, Q sind natürliche Zahlen, mit P = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20), Q = (5, 10, 15, 20, 25, 30, 35, 40, 45, 50).

Es ist bekannt, dass der Ausdruck

((XA)→ (XP))∨ (¬(xQ)→ ¬(xA))

wahr (d. h. nimmt den Wert 1 an) für jeden Wert der Variablen x.

Bestimmen Sie die größtmögliche Anzahl von Elementen in Menge A.

6. Aufgabe 18 Nr. 9321. Bezeichnen wir mitDEL ( n, m ) die Aussage „Eine natürliche Zahl n ist ohne Rest durch eine natürliche Zahl teilbarM " Was ist die größte natürliche Zahl?A Formel

¬ DEL ( x, A ) → (¬ DEL ( X , 21) ∧ ¬ DEL ( X , 35))

ist identisch wahr (d. h. nimmt den Wert 1 für jeden natürlichen Wert der Variablen an).X )?

(Auftrag von M.V. Kuznetsova)

7. Aufgabe 18 Nr. 9768. Bezeichnen wir mit M & N M Und N 2 & 0101 2 = 0100 2 A Formel

X & 29 ≠ 0 → (X & 12 = 0 → X & A ≠ 0)

ist identisch wahr (d. h. nimmt den Wert 1 für jeden nicht negativen ganzzahligen Wert der Variablen an). X )?

8. Aufgabe 18 Nr. 9804. Bezeichnen wir mit M & N bitweise Konjunktion nicht negativer Ganzzahlen M Und N . Also zum Beispiel 14 & 5 = 1110 2 & 0101 2 = 0100 2 = 4. Für was ist die kleinste nicht negative ganze Zahl A Formel

X & 29 ≠ 0 → (X & 17 = 0 → X & A ≠ 0)

ist identisch wahr (d. h. nimmt den Wert 1 für jeden nicht negativen ganzzahligen Wert der Variablen an X )?

9. Aufgabe 18 Nr. 723. Für welchen Namen gilt die Aussage:

Vokal des dritten Buchstabens→ ¬ (Der erste Buchstabe ist ein Konsonant \/ Das Wort enthält 4 Vokale)?

1) Rimma

2) Anatoli

3) Swetlana

4) Dmitri

Erläuterung.

Wenden wir die Implikationstransformation an:

Konsonant im dritten Buchstaben∨ (Erster Buchstabe Vokal∧ Das Wort hat NICHT 4 Vokale)

Eine Disjunktion ist wahr, wenn mindestens eine Aussage wahr ist. Daher ist nur Option 1 geeignet.

10. Aufgabe 18 Nr. 4581. Welcher der Vornamen erfüllt die logische Bedingung:

(Der erste Buchstabe ist ein Konsonant→ der letzte Buchstabe ist ein Konsonant) /\ (der erste Buchstabe ist ein Vokal→ Ist der letzte Buchstabe ein Vokal)?

Wenn es mehrere solcher Wörter gibt, geben Sie das längste an.

1) ANNA

2) BELLA

3) ANTON

4) BORIS

Erläuterung.

Logisches Und ist nur dann wahr, wenn beide Aussagen wahr sind.(1)

Eine Implikation ist nur dann falsch, wenn die Wahrheit eine Lüge impliziert.(2)

Option 1 ist für alle Bedingungen geeignet.

Option 2 ist aufgrund der Bedingung (2) nicht geeignet.

Option 3 ist aufgrund der Bedingung (2) nicht geeignet.

Option 4 ist für alle Bedingungen geeignet.

Das längste Wort muss angegeben werden, daher lautet die Antwort 4.

Aufgaben zur eigenständigen Lösung

1. Aufgabe 18 Nr. 711. Welcher der angegebenen Ländernamen erfüllt die folgende logische Bedingung: ((Konsonant des letzten Buchstabens) \/ (Konsonant des ersten Buchstabens))→ (Der Name enthält den Buchstaben „p“)?

1) Brasilien

2) Mexiko

3) Argentinien

4) Kuba

2. Aufgabe 18 Nr. 709. Welcher der Vornamen erfüllt die logische Bedingung:

(Der erste Buchstabe ist ein Vokal)∧ ((Vierter Buchstabe Konsonant)∨ (Das Wort hat vier Buchstaben))?

1) Sergej

2) Wadim

3) Anton

4) Ilja

№3

№4

№5. Aufgabe 18 Nr. 736. Welcher der Vornamen erfüllt die logische Bedingung?

Der erste Buchstabe ist ein Vokal∧ Der vierte Buchstabe ist ein Konsonant∨ Besteht das Wort aus vier Buchstaben?

1) Sergej

2) Wadim

3) Anton

4) Ilja

Informatiklehrer an der MBOU „Lyceum“

erste Qualifikationskategorie

Murzina Olga Iwanowna

MBOU "Lyceum" Arzamas

Theorie und Praxis zur Lösung der Aufgabe 18 des Einheitlichen Staatsexamens in Informatik

Arsamas, 2017

Mnemonische Regel

Eines seiner Hauptprinzipien ist die Ergänzung zum Ganzen (Ergänzung durch das Gegenteil).

Sozionik ist Informationspsychologie

Lösungsformel

In der Algebra der Logik gibt es eine Formel für das Ganzzahlkomplement:

Bei einigen Problemen verwenden wir die Multiplikation von Gegensätzen anstelle dieser Formel:

Jobtypen 18

• Segmentieren Sie Aufgaben
• Aufgaben an Sets
• Aufgaben zur bitweisen Konjunktion
• Teilbarkeitstests

Segmentieren Sie Aufgaben

(Nr. 376) Auf der Zahlengeraden gibt es zwei Segmente: P= und Q=. Finden Sie die kleinstmögliche Länge eines Segments A, sodass die Formel ((x ∈ P) ∧ (x ∈ Q)) → (x ∈ A) gilt

ist identisch wahr, das heißt, es nimmt für jeden Wert der Variablen x den Wert 1 an.

Lösungsformel

nimmt für jeden Wert der Variablen x den Wert 1 an.

Lösung des Segmentproblems

• Legende
• Formalisierung der Bedingung
• Lösen einer logischen Gleichung

Teilen wir die Lösung des Problems in Phasen ein:

Lösung des Segmentproblems

• Legende- Dies sind praktische Symbole, die wir beim Lösen verwenden werden.

Führen wir die folgende Notation ein:

Lösung des Segmentproblems

2) Formalisierung der Bedingung– Schreiben wir die Formel aus der Problemstellung entsprechend der Legende um.

((x ∈ P) ∧ (x ∈ Q)) → (x ∈ A) = 1

(P ∧ Q) → A = 1

Lösung des Segmentproblems

3) Eine logische Gleichung lösen – Dies ist zunächst vielleicht die schwierigste Phase bei der Lösung des Problems. Aber später, wenn Sie Erfahrung sammeln, wird es Ihnen nicht mehr so ​​schwierig vorkommen 

Betrachten wir die schrittweise Lösung einer logischen Gleichung.

Lösung des Segmentproblems

3.1. Stellen wir uns die logische Konsequenz in grundlegenden logischen Operationen anhand der Formel vor: A → B = ¬A  B:

(P ∧ Q) → A = 1

¬(P ∧ Q)  A = 1

Lösung des Segmentproblems

A  ¬A = 1 (in der Algebra der Logik gilt das Gesetz der Kommutativität, d. h. A  ¬A = ¬A  A):

¬(P ∧ Q)  A = 1, also

¬A = ¬(P ∧ Q)

Die Antwort in der logischen Gleichung lautet:

Lösung des Segmentproblems

.

Unsere Antwort: A = P ∧ Q.

In der Algebra der Logik bedeutet dieser Ausdruck den Schnittpunkt der Volumina zweier logischer Objekte. Nach den Bedingungen unseres Problems ist dies der Schnittpunkt der Strecken P und Q.

Lösung des Segmentproblems

Der Schnittpunkt der Segmente P und Q kann visualisiert werden: P= und Q=.

Gemäß den Bedingungen unseres Problems benötigen wir die Mindestlänge des Segments A. Wir finden sie: 15 – 12 = 3.

Antwort auf der Website von K. Yu. Polyakov: 3

Segmentieren Sie Aufgaben

(Nr. 360) Auf der Zahlengeraden gibt es drei Segmente: P=, Q= und R=. Wie groß ist die maximale Länge des Segments A, für das die Formel ((x ∈ Q) → (x ∉ R)) ∧ (x ∈ A) ∧ (x ∉ P) gilt?

ist identisch falsch, das heißt, nimmt für jeden Wert der Variablen x den Wert 0 an?

Quelle - Website von Polyakov K.Yu.

Lösungsformel

Um eine Lösungsformel auszuwählen, ist es wichtig, die Problemanforderung sorgfältig zu lesen.

In unserem Problem lautet die Anforderung:

nimmt für jeden Wert der Variablen x den Wert 0 an.

Die Wahl der entscheidenden Formel liegt auf der Hand:

Lösung des Segmentproblems

• Legende
• Formalisierung der Bedingung
• Lösen einer logischen Gleichung
• Interpretation des erhaltenen Ergebnisses

Lösung des Segmentproblems

• Legende

Lösung des Segmentproblems

2) Formalisierung der Bedingung

((x ∈ Q) → (x ∉ R)) ∧ (x ∈ A) ∧ (x ∉ P) = 0

(Q → ¬R) ∧ A ∧ ¬ P = 0

Lösung des Segmentproblems

(Q → ¬R) ∧ A ∧ ¬ P = 0

3.1. Stellen wir uns die logische Konsequenz in grundlegenden logischen Operationen anhand der Formel A → B = ¬A  B vor und ordnen wir die Faktoren gemäß dem Gesetz der kommutativen Multiplikation neu an:

A ∧ (¬ Q  ¬R) ∧ ¬ P = 0

Lösung des Segmentproblems

3) Lösen einer logischen Gleichung

A ∧ (¬ Q  ¬R) ∧ ¬ P = 0

3.2. Reduzieren wir den resultierenden Ausdruck auf die entscheidende Formel: A  ¬A = 0 und finden wir heraus, was ¬A gleich ist:

¬A = (¬ Q  ¬R) ∧ ¬ P

Lösung des Segmentproblems

3) Lösen einer logischen Gleichung

¬A = (¬ Q  ¬R) ∧ ¬ P

3.3. Vereinfachen wir den Ausdruck für ¬A gemäß de Morgans Gesetz ¬A¬B=¬(AB):

¬A = ¬ (Q  R) ∧ ¬ P,

und nach einem anderen De-Morgan-Gesetz ¬A¬B=¬(AB):

¬A = ¬ (Q  R  P)

Lösung des Segmentproblems

3) Lösen einer logischen Gleichung

¬A = ¬ (Q  R  P)

3.4. Es ist klar, dass

A = Q  R  P

Lösung des Segmentproblems

4) Interpretation des erhaltenen Ergebnisses

A = Q  R  P

Segment A ist der Schnittpunkt der Segmente Q und R und seine Vereinigung mit Segment P.

Lösung des Segmentproblems

Der Schnittpunkt der Segmente R und Q kann visualisiert werden: Q= und R=.

Wir zeichnen die Strecke P= auf unserer Zeichnung ein und kombinieren sie mit dem Schnittpunkt:

Lösung des Segmentproblems

Gemäß den Bedingungen unseres Problems benötigen wir die maximale Länge des Segments A. Wir finden sie: 30 – 10 = 20.

A = Q  R  P

Antwort auf der Website von K. Yu. Polyakov: 20

2. Aufgaben an Sets

(Nr. 386) Die Elemente der Mengen A, P, Q sind natürliche Zahlen und P=(1,2,3,4,5,6), Q=(3,5,15). Es ist bekannt, dass der Ausdruck (x ∉ A) → ((x ∉ P) ∧ (x ∈ Q)) ∨ (x ∉ Q)

wahr (d. h. nimmt den Wert 1 für jeden Wert der Variablen x an. Bestimmen Sie die kleinstmögliche Anzahl von Elementen in der Menge A.

Quelle - Website von Polyakov K.Yu.

Lösung des Problems auf Sets

• Legende
• Formalisierung der Bedingung
• Lösen einer logischen Gleichung
• Interpretation des erhaltenen Ergebnisses

Lösung des Problems auf Sets

• Legende

Lösung des Problems auf Sets

2) Formalisierung der Bedingung

(x ∉ A) → ((x ∉ P) ∧ (x ∈ Q)) ∨ (x ∉ Q) = 1

¬ A → (¬P ∧ Q)  ¬ Q = 1

Lösung des Problems auf Sets

3) Lösen einer logischen Gleichung

¬ A → (¬P ∧ Q)  ¬ Q = 1

3.1. Stellen wir uns logische Konsequenzen in grundlegenden logischen Operationen vor und gruppieren sie:

A  ((¬P ∧ Q)  ¬ Q) = 1

Lösung des Problems auf Sets

A  ((¬P ∧ Q)  ¬Q) = 1

3.2. Reduzieren wir den resultierenden Ausdruck auf die entscheidende Formel:

und finden Sie heraus, was ¬A gleich ist:

¬A = (¬P ∧ Q)  ¬Q

Lösung des Problems auf Sets

¬A = (¬P ∧ Q)  ¬Q

3.3. Vereinfachen wir den Ausdruck für ¬A, indem wir die Klammern gemäß dem Gesetz der distributiven Addition öffnen:

¬A = (¬P  ¬Q)  (Q  ¬Q)

¬A = (¬P  ¬Q)

Lösung des Problems auf Sets

¬A = (¬P  ¬Q)

Nach dem Gesetz von De Morgan:

¬A = ¬(P  Q)

3.4. Es ist klar, dass

Lösung des Problems auf Sets

4) Interpretation des erhaltenen Ergebnisses

Lösung des Problems auf Sets

P = 1, 2, 3, 4, 5, 6 und Q =(3, 5,15), also A =(3, 5)

und enthält nur 2 Elemente.

Antwort auf Polyakovs Website: 2

2. Aufgaben an Sets

(Nr. 368) Die Elemente der Mengen A, P, Q sind natürliche Zahlen und P=(2,4,6,8,10,12) und Q=(4,8,12,116). Es ist bekannt, dass der Ausdruck (x ∈ P) → (((x ∈ Q) ∧ (x ∉ A)) → (x ∉ P))

wahr (d. h. nimmt den Wert 1 an) für jeden Wert der Variablen x. Bestimmen Sie den kleinstmöglichen Wert der Summe der Elemente der Menge A.

Quelle - Website von Polyakov K.Yu.

• Legende
• Formalisierung der Bedingung
• Lösen einer logischen Gleichung
• Interpretation des erhaltenen Ergebnisses

Lösung des Problems auf Sets

• Legende

Lösung des Problems auf Sets

2) Formalisierung der Bedingung

(x ∈ P)→(((x ∈ Q) ∧ (x ∉ A))→(x ∉ P)) = 1

P → ((Q ∧ ¬A) → ¬P) = 1

Lösung des Problems auf Sets

Lösung des Problems auf Sets

3) Lösen einer logischen Gleichung

P → ((Q ∧ ¬A) → ¬P) = 1

3.1. Stellen wir uns die erste logische Konsequenz (in Klammern) in grundlegenden logischen Operationen vor:

P → (¬(Q ∧ ¬A)  ¬P) = 1

Lösung des Problems auf Sets

P → (¬(Q ∧ ¬A)  ¬P) = 1

Stellen wir uns die zweite logische Konsequenz in grundlegenden logischen Operationen vor, wenden wir das Gesetz von De Morgan an und ordnen wir es neu an:

¬P (¬(Q ∧ ¬A)  ¬P) = 1

¬P ¬Q  A  ¬P = 1

Lösung des Problems auf Sets

A  (¬P ¬Q  ¬P) = 1

3.2. Reduzieren wir den resultierenden Ausdruck auf die entscheidende Formel:

und finden Sie heraus, was ¬A gleich ist:

¬A = (¬P ¬Q  ¬P)

Lösung des Problems auf Sets

¬A = ¬P ¬Q  ¬P

3.3. Vereinfachen wir den Ausdruck für ¬A mit der Formel A  A = A:

¬A = ¬(P Q)

Lösung des Problems auf Sets

¬A = ¬(P Q)

3.4. Es ist klar, dass

4) Interpretation des erhaltenen Ergebnisses

Die erforderliche Menge A ist der Schnittpunkt der Mengen P und Q.

Lösung des Problems auf Sets

Die erforderliche Menge A ist der Schnittpunkt von Mengen

P = 2, 4, 6, 8, 10, 12 und

Q = (4, 8, 12, 16), also

und enthält nur 3 Elemente, deren Summe 4+8+12=24 ist.

Antwort auf Polyakovs Website: 24

(Nr. 379) Bezeichnen mit M&N bitweise Konjunktion nicht negativer Ganzzahlen M Und N. Also zum Beispiel 14 & 5 = 11102 & 01012 = 01002 = 4. Was ist die kleinste nicht negative ganze Zahl? A Formel (x & 29 ≠ 0) → ((x & 12 = 0) → (x & A ≠ 0))

ist identisch wahr (d. h. nimmt den Wert 1 für jeden nicht negativen ganzzahligen Wert der Variablen x an)?

• Legende
• Formalisierung der Bedingung
• Lösen einer logischen Gleichung
• Interpretation des erhaltenen Ergebnisses

• Legende

B = (x & 29 ≠ 0)

C = (x & 12 ≠ 0)

A = (x & A ≠ 0)

Lösung des bitweisen Konjunktionsproblems

Wir akzeptieren eine bitweise Konjunktion ungleich Null als wahre Aussage, sonst verliert die bitweise Konjunktion ihre logische Bedeutung, weil Sie können X immer mit nur Nullen darstellen.

Lösung des bitweisen Konjunktionsproblems

2) Formalisierung der Bedingung

(x & 29 ≠ 0)→((x & 12 = 0)→(x & A ≠ 0))=1

B → (¬C → A) = 1

Lösung des bitweisen Konjunktionsproblems

3) Lösen einer logischen Gleichung

B → (¬C → A) = 1

B → (C A) = 1

(¬B  C) A = 1

¬A = ¬B  C

¬A = ¬(B ¬ C)

Es ist klar, dass

A = B ¬ C

Lösung des bitweisen Konjunktionsproblems

Lösung des bitweisen Konjunktionsproblems

4) Interpretation des erhaltenen Ergebnisses

Lösung des bitweisen Konjunktionsproblems

B = (x & 29 ≠ 0)

B oder 29 = 111012

C = (x & 12 ≠ 0)

¬С oder Inversion 12 = 00112

Lösung des bitweisen Konjunktionsproblems

B oder 29 = 111012

¬С oder Inversion 12 = 00112

A = B ¬ C

A = 100012 = 17

Antwort auf Polyakovs Website: 17

3. Aufgaben zur bitweisen Konjunktion

(Nr. 375) Lassen Sie uns den Ausdruck M & K einführen, der die bitweise Verbindung von M und K bezeichnet (logisches „UND“ zwischen den entsprechenden Bits der binären Notation). Bestimmen Sie die kleinste natürliche Zahl A, sodass der Ausdruck (X & 49 ≠ 0) → ((X & 33 = 0) → (X & A ≠ 0))

identisch wahr (d. h. nimmt den Wert 1 für jeden natürlichen Wert der Variablen X an)?

• Legende
• Formalisierung der Bedingung
• Lösen einer logischen Gleichung
• Interpretation des erhaltenen Ergebnisses

Lösung des bitweisen Konjunktionsproblems

• Legende

Die Legende für Probleme mit bitweisen Konjunktionen unterscheidet sich von allen anderen Fällen:

B = (x & 49 ≠ 0)

C = (x & 33 ≠ 0)

A = (x & A ≠ 0)

Lösung des bitweisen Konjunktionsproblems

2) Formalisierung der Bedingung

(X & 49 ≠ 0) → ((X & 33 = 0) → (X & A ≠ 0))=1

B → (¬C → A) = 1

Lösung des bitweisen Konjunktionsproblems

3) Lösen einer logischen Gleichung

B → (¬C → A) = 1

B → (C  A) = 1

(¬B  C)  A = 1

¬A = (¬B  C)

Offensichtlich:

Lösung des bitweisen Konjunktionsproblems

Lösung des bitweisen Konjunktionsproblems

4) Interpretation des erhaltenen Ergebnisses

Der gewünschte Binärwert der bitweisen Konjunktion A ist der Binärwert der bitweisen Konjunktion des Wertes B und der Kehrwert des Binärwerts C.

Lösung des bitweisen Konjunktionsproblems

B = (x & 49 ≠ 0)

B oder 49 = 1100012

C = (x & 33 ≠ 0)

¬С oder Inversion 33 = 0111102

Lösung des bitweisen Konjunktionsproblems

B oder 49 = 1100012

¬С oder Inversion 33 = 0111102

A = B ¬ C

011110 2

A = 100002 = 16

Antwort auf Polyakovs Website: 16

(Nr. 372) Bezeichnen wir mit DEL(n, m) die Aussage „die natürliche Zahl n wird ohne Rest durch die natürliche Zahl m dividiert.“ Für die größte natürliche Zahl A gilt die Formel ¬DIV(x,A) → (¬DIV(x,21) ∧ ¬DIV(x,35))

Quelle - Website von Polyakov K.Yu.

• Legende
• Formalisierung der Bedingung
• Lösen einer logischen Gleichung
• Interpretation des erhaltenen Ergebnisses

Die Lösung des Problems

zur Teilbarkeitsbedingung

• Legende

Die Lösung des Problems

zur Teilbarkeitsbedingung

Die Legende ist einfach: A = DIV(x,A)

21 = DIV(x.21)

35 = DIV(x.35)

2) Formalisierung der Bedingung

Die Lösung des Problems

zur Teilbarkeitsbedingung

¬DIV(x,A) → (¬DIV(x,21) ∧ ¬DIV(x,35))

¬A → (¬21 ∧ ¬35) = 1

identisch wahr (d. h. nimmt den Wert 1 an)

3) Lösen einer logischen Gleichung

Die Lösung des Problems

zur Teilbarkeitsbedingung

¬A → (¬21 ∧ ¬35) = 1

A (¬21 ∧ ¬35) = 1

¬A = ¬21 ∧ ¬35

Es ist klar, dass

4) Interpretation des erhaltenen Ergebnisses

Bei diesem Problem ist dies die schwierigste Phase der Lösung. Sie müssen verstehen, was die Zahl A ist – LOC oder GCD oder ...

Die Lösung des Problems

zur Teilbarkeitsbedingung

4) Interpretation des erhaltenen Ergebnisses

Unsere Zahl A ist also so, dass X genau dann ohne Rest durch sie teilbar ist, wenn X ohne Rest durch 21 oder 35 teilbar ist. In diesem Fall suchen wir nach

A = ggT (21, 35) = 7

Die Lösung des Problems

zur Teilbarkeitsbedingung

Antwort auf Polyakovs Website: 7

4. Aufgaben zur Teilbarkeitsbedingung

(Nr. 370) Bezeichnen wir mit DEL(n, m) die Aussage „die natürliche Zahl n wird ohne Rest durch die natürliche Zahl m dividiert.“ Für die größte natürliche Zahl A gilt die Formel ¬DIV(x,A) → ((DIV(x,6) → ¬DIV(x,4))

identisch wahr (d. h. nimmt den Wert 1 für jeden natürlichen Wert der Variablen x an)?

Quelle - Website von Polyakov K.Yu.

• Legende
• Formalisierung der Bedingung
• Lösen einer logischen Gleichung
• Interpretation des erhaltenen Ergebnisses

Die Lösung des Problems

zur Teilbarkeitsbedingung

• Legende

A = DIV(x,A)

Die Lösung des Problems

zur Teilbarkeitsbedingung

2) Formalisierung der Bedingung

Die Lösung des Problems

zur Teilbarkeitsbedingung

¬DIV(x,A) → ((DIV(x,6) → ¬DIV(x,4))

ist identisch wahr (d. h. nimmt den Wert 1 an).

¬A → (6 → ¬4) = 1

3) Lösen einer logischen Gleichung

¬A → (6 → ¬4) = 1

¬A → (¬ 6  ¬4) = 1

A  (¬ 6  ¬ 4) = 1

¬A = ¬ 6  ¬4

Offensichtlich:

Die Lösung des Problems

zur Teilbarkeitsbedingung

4) Interpretation des erhaltenen Ergebnisses

Also ist A so, dass X genau dann ohne Rest durch es teilbar ist, wenn X sowohl durch 6 als auch durch 4 ohne Rest teilbar ist. Das heißt A = LCM(6, 4) = 12

Antwort auf Polyakovs Website: 12

Die Lösung des Problems

zur Teilbarkeitsbedingung

Können Sie nun Ihren Schülern oder Freunden die Lösung zu Aufgabe 18 erklären?

(Ja, nein, ich weiß es nicht).

Vielen Dank für Ihre Aufmerksamkeit!