Es ist bekannt, dass der Ausdruck

((x ∈ A) → (x ∈ P)) ∧ ((x ∈ Q) → ¬(x ∈ A))

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.

Lösung.

Führen wir die folgende Notation ein:

(x ∈ P) ≡ P; (x ∈ Q) ≡ Q; (x ∈ A) ≡ A; ∧ ≡ · ; ∨ ≡ +.

Wenn wir dann die Implikationstransformation anwenden, erhalten wir:

(¬A + P) · (¬Q + ¬A) ⇔ ¬A · ¬Q + ¬Q · P + ¬A + ¬A · P ⇔

⇔ ¬A · (¬Q + P + 1) + ¬Q · P ⇔ ¬A + ¬Q · P.

Es ist erforderlich, dass ¬A + ¬Q · P = 1. Der Ausdruck ¬Q · P ist wahr, wenn x ∈ (2, 4, 8, 10, 14, 16, 20). Dann muss ¬A wahr sein, wenn x ∈ (1, 3, 5, 6, 7, 9, 11, 12, 13, 15, 17, 18, 19, 21, 22, 23,...).

Daher beträgt die maximale Anzahl von Elementen in der Menge A, wenn A alle Elemente der Menge ¬Q · P enthält, sieben solcher Elemente.

Antwort: 7.

Antwort: 7

Die Elemente der Menge A sind natürliche Zahlen. Es ist bekannt, dass der Ausdruck

(x (2, 4, 6, 8, 10, 12)) → (((x (3, 6, 9, 12, 15)) ∧ ¬(x A)) → ¬(x (2, 4, 6 , 8, 10, 12)))

Lösung.

Führen wir die folgende Notation ein:

(x ∈ (2, 4, 6, 8, 10, 12)) ≡ P; (x ∈ (3, 6, 9, 12, 15)) ≡ Q; (x ∈ A) ≡ A.

Durch die Transformation erhalten wir:

P → ((Q ∧ ¬A) → ¬P) = P → (¬(Q ∧ ¬A) ∨ ¬P) = ¬P ∨ (¬(Q ∧ ¬A) ∨ ¬P) = ¬P ∨ ¬Q ∨ A.

Logisches ODER ist wahr, wenn mindestens eine Aussage wahr ist. Der Ausdruck ¬P ∨ ¬Q gilt für alle Werte von x außer den Werten 6 und 12. Daher muss das Intervall A die Punkte 6 und 12 enthalten. Das heißt, die minimale Menge von Punkten im Intervall A ≡ ( 6, 12). Die Summe der Elemente der Menge A beträgt 18.

Antwort: 18.

Antwort: 18

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

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.

Lösung.

Vereinfachen wir:

¬(x P) ∨ ¬(x Q) ergibt 0 nur, wenn die Zahl in beiden Mengen liegt. Damit der gesamte Ausdruck wahr ist, müssen wir alle in P und Q liegenden Zahlen in A einsetzen. Solche Zahlen sind 6, 12, 18. Ihre Summe ist 36.

Antwort: 36.

Antwort: 36

Quelle: Ausbildungsarbeit in Informatik, Klasse 11, 18. Januar 2017, Option IN10304

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 ((x A) → (x P)) ∨ (¬(x Q) → ¬(x A))

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.

Lösung.

Lassen Sie uns diesen Ausdruck umwandeln:

((x A) → (x P)) ∨ ((x Q) → (x A))

((x A) ∨ (x P)) ∨ ((x Q) ∨ (x A))

(x A) ∨ (x P) ∨ (x Q)

Daher muss ein Element entweder in P oder Q enthalten sein oder nicht in A enthalten sein. Daher kann A nur Elemente aus P und Q enthalten. Und insgesamt gibt es 17 sich nicht wiederholende Elemente in diesen beiden Mengen.

Antwort: 17

Die Elemente der Mengen A, P, Q sind natürliche Zahlen und P = (1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21), Q = (3, 6, 9, 12, 15, 18, 21, 24, 27, 30). Es ist bekannt, dass der Ausdruck

((x P) → (x A)) ∨ (¬(x A) → ¬(x Q))

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.

Lösung.

Lassen Sie uns zwei Implikationen offenbaren. Wir bekommen:

(¬(x P) ∨ (x A)) ∨ ((x A) ∨ ¬(x Q))

Vereinfachen wir:

(¬(x P) ∨ (x A) ∨ ¬(x Q))

¬(x P) ∨ ¬(x Q) ergibt 0 nur, wenn die Zahl in beiden Mengen liegt. Damit der gesamte Ausdruck wahr ist, müssen Sie alle Zahlen in P und Q in A einsetzen. Diese Zahlen sind 3, 9, 15 und 21. Ihre Summe ist 48.

Antwort: 48.

Antwort: 48

Quelle: Ausbildungsarbeit in Informatik, Klasse 11, 18. Januar 2017, Option IN10303

Und der Ausdruck

(y + 2x 30) ∨ (y > 20)

X und y?

Lösung.

Beachten Sie, dass dieser Ausdruck identisch wahr sein muss, wenn der Ausdruck (y + 2x Antwort: 81.

Antwort: 81

Quelle: Einheitliches Staatsexamen – 2018. Frühe Welle. Option 1. Einheitliches Staatsexamen – 2018. Frühe Welle. Option 2.

Auf der Zahlengeraden ist ein Segment A angegeben. Es ist bekannt, dass die Formel

((X ∈ A) → (x 2 ≤ 100)) ∧ ((x 2 ≤ 64) → (X ∈ A))

gilt gleichermaßen für jedes reale X. Was ist die kürzeste Länge von Segment A?

Lösung.

Indem wir die Implikation gemäß der Regel A → B = ¬A + B erweitern, die logische Summe durch eine Menge und das logische Produkt durch ein Beziehungssystem ersetzen, bestimmen wir die Werte des Parameters A, bei dem das System der Aggregate

wird Lösungen für alle reellen Zahlen haben.

Damit die Lösungen des Systems alle reelle Zahlen sind, ist es notwendig und ausreichend, dass die Lösungen für jede der Sammlungen alle reelle Zahlen sind.

Die Lösungen der Ungleichung sind alle Zahlen aus dem Intervall [−10; 10]. Damit die Sammlung für alle reellen Zahlen gilt, sind die Zahlen X, die nicht auf dem angegebenen Segment liegt, muss zum Segment A gehören. Folglich darf das Segment A nicht über die Grenzen des Segments [−10; 10].

Ebenso sind die Lösungen der Ungleichung die Zahlen aus den Strahlen und damit die Sammlung für alle reellen Zahlen gilt, die Zahlen X, die nicht auf den angegebenen Strahlen liegt, muss auf dem Segment A liegen. Folglich muss das Segment A das Segment [−8; 8].

Somit kann die kürzeste Länge von Segment A gleich 8 + 8 = 16 sein.

Antwort: 16.

Antwort: 16

A Ausdruck

(j + 2x ≠ 48) ∨ (A x) ∨ ( X y)

ist identisch wahr, das heißt, nimmt den Wert 1 für alle nicht negativen ganzen Zahlen an X Und j?

Lösung.

A X Und j Lassen Sie uns überlegen, in welchen Fällen die Bedingungen ( j + 2x≠ 48) und ( X y) sind falsch.

j = 48 − 2x) und (x ≥ y). Das X im Bereich von 16 bis 24 und j im Bereich von 0 bis 16. Beachten Sie, dass der Ausdruck für jeden geeignet ist X Und j, erforderlich zu nehmen X= 16 und j= 16. Dann A A wird gleich 15 sein.

Antwort: 15.

Antwort: 15

Quelle: Einheitliches Staatsexamen in Informatik, 28.05.2018. Die Hauptwelle, A. Imaevs Version – „Kotolis“.

Was ist die größte nicht negative ganze Zahl? A Ausdruck

(j + 2x ≠ 48) ∨ (A x) ∨ ( A y)

ist identisch wahr, das heißt, nimmt den Wert 1 für alle nicht negativen ganzen Zahlen an X Und j?

Lösung.

So finden Sie die größte nicht negative ganze Zahl A, bei dem der Ausdruck sein wird X Und j, betrachten wir, in welchen Fällen die Bedingung ( j + 2x≠ 48) ist falsch.

Somit finden wir alle Lösungen, wenn ( j = 48 − 2x). Das X im Bereich von 0 bis 24 und j im Bereich von 48 bis 0. Beachten Sie, dass der Ausdruck für jeden geeignet ist X Und j, erforderlich zu nehmen X= 16 und j= 16. Dann A A wird gleich 15 sein.

Antwort: 15.

Antwort: 15

Quelle: Demoversion des Einheitlichen Staatsexamens 2019 in Informatik.

Was ist die kleinste nicht negative ganze Zahl? A Ausdruck

(2X + 3j > 30) ∨ (X + j ≤ A)

gilt gleichermaßen für alle nichtnegativen ganzen Zahlen X Und j?

Lösung.

A, wobei der Ausdruck für alle nicht negativen ganzen Zahlen identisch wahr ist X Und jj + 2x> 30) falsch.

j + 2X≤ 30). Das X im Bereich von 0 bis 15 und j im Bereich von 10 bis 0. Beachten Sie, dass der Ausdruck für jeden geeignet ist X Und j, erforderlich zu nehmen X= 15 und j= 0. Dann 15 + 0 ≤ A. Daher die kleinste nicht negative ganze Zahl A wird gleich 15 sein.

Antwort: 15.

Antwort: 15

Was ist die größte nicht negative ganze Zahl? A Ausdruck

(2X + 3j x+ j ≥ A)

gilt gleichermaßen für alle nichtnegativen ganzen Zahlen X Und j?

Lösung.

So finden Sie die größte nicht negative ganze Zahl A, wobei der Ausdruck für alle nicht negativen ganzen Zahlen identisch wahr ist X Und j, betrachten wir, in welchen Fällen Bedingung (3 j + 2x Somit finden wir alle Lösungen, wenn (3 j + 2X≥ 30). Das X mehr als 15 und j größer als 10. Beachten Sie, dass der Ausdruck für jeden geeignet ist X Und j, erforderlich zu nehmen X= 0 und j= 10. Dann 0 + 10 ≤ A. Daher die größte nicht negative ganze Zahl A wird gleich 10 sein.

Antwort: 10.

Antwort: 10

Was ist die kleinste nicht negative ganze Zahl? A Ausdruck

(3X + 4j ≠ 70) ∨ (A > X) ∨ (A > j)

gilt gleichermaßen für alle nichtnegativen ganzen Zahlen X Und j?

Lösung.

So finden Sie die kleinste nicht negative ganze Zahl A, wobei der Ausdruck für alle nicht negativen ganzen Zahlen identisch wahr ist X Und j, betrachten wir, in welchen Fällen Bedingung (3 X + 4j≠ 70) ist falsch.

Somit finden wir alle Lösungen, wenn (3 X + 4j= 70). Das X im Bereich von 2 bis 22 und j im Bereich von 16 bis 1. Beachten Sie, dass der Ausdruck für jeden geeignet ist X Und j, erforderlich zu nehmen X= 10 und j= 10. Dann A> 10. Daher die kleinste nicht negative ganze Zahl A wird gleich 11 sein.

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

1. Beispiel aus Demoversion

(Konsonant des ersten Buchstabens → Konsonant des zweiten Buchstabens) / (Vokal des vorletzten Buchstabens → Vokal des letzten Buchstabens)

1) KRISTINA 2) MAXIM 3) STEPAN 4) MARIA

Lösungsskizze Implikation a → b entspricht dem Ausdruck ¬a / b.

Die erste Implikation gilt für die Wörter KRISTINA und STEPAN. Von diesen Wörtern trifft die zweite Implikation nur auf das Wort CHRISTINE zu.

Antwort: 1. CHRISTINA

2. Zwei weitere Beispiele

Beispiel 1 (offenes Segment der FIPI-Bank)

Welcher der Vornamen erfüllt die logische Bedingung:

(erster Konsonant → erster Vokal) / (letzter Vokal → letzter Konsonant)

1. IRINA 2. MAXIM 3. ARTEM 4. MARIA

Lösungsskizze. Implikation a → b entspricht dem Ausdruck ¬a / b. Dieser Ausdruck ist wahr, wenn einer der Ausdrücke a falsch ist oder beide Ausdrücke a und b wahr sind. Da in unserem Fall in keiner der Implikationen beide Ausdrücke gleichzeitig wahr sein können, müssen die Aussagen „der erste Buchstabe ist ein Konsonant“ und „der letzte Buchstabe ist ein Vokal“ falsch sein, das heißt, wir brauchen ein Wort, dessen Der erste Buchstabe ist ein Vokal und der letzte ein Konsonant.

Antwort: 3. ARTEM.

Beispiel 2. Für welchen der angegebenen Werte der Zahl X trifft die Aussage zu?

(X< 4)→(X >15)

1) 1 2) 2 3) 3 4) 4

Lösung. Keine Zahl kann sowohl kleiner als 4 als auch größer als 15 sein. Daher ist die Implikation nur dann wahr, wenn die Prämisse erfüllt ist X< 4 FALSCH.

Antwort 4.

2. Probleme im Format des Einheitlichen Staatsexamens 2013-2014.

2.1. Demoversion 2013

Auf der Zahlengeraden gibt es zwei Segmente: P = und Q = .

Wählen Sie ein Segment A, so dass die Formel

1) 2) 3) 4)

2.2. Demoversion 2014

Auf der Zahlengeraden gibt es zwei Segmente: P = und Q = . Wählen Sie aus den vorgeschlagenen Segmenten ein Segment A aus, das dem logischen Ausdruck entspricht

((x ∈ P) → ¬ (x ∈ Q))→ ¬ (x ∈ A)

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

Antwortmöglichkeiten: 1) 2) 3) 4)

Lösung. Lassen Sie uns den Ausdruck mit umwandeln. Wir haben:

¬((x ∈ P) → ¬ (x ∈ Q)) ∨ (¬ (x ∈ A)) – Ersetzen der Implikation durch eine Disjunktion;

¬(¬(x ∈ P) ∨ ¬ (x ∈ Q)) ∨ (¬ (x ∈ A)) – Ersetzen der Implikation durch eine Disjunktion;

((x ∈ P) ∧ (x ∈ Q)) ∨ (¬ (x ∈ A)) – de Morgans Regel und die Entfernung der doppelten Negation;

(x ∈ A) → ((x ∈ P) ∧ (x ∈ Q)) – Ersetzen der Disjunktion durch Implikation

Der letzte Ausdruck ist genau dann identisch wahr, wenn A ⊆ P∩ Q = ∩ = (siehe ). Von den vier angegebenen Segmenten erfüllt nur das Segment – ​​Option Nr. 2 – diese Bedingung.

Antwort: - Option Nr. 2

3. Probleme im Format des Einheitlichen Staatsexamens 2015-2016.

3.1. Aufgabe 1.

Auf der Zahlengeraden gibt es zwei Segmente: P = und Q = .

Es ist bekannt, dass die Grenzen des Segments A ganzzahlige Punkte sind und für das Segment A gilt die Formel

((x ∈ A) → (x ∈ P)) \/ (x ∈ Q)

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

Was ist die größtmögliche Länge von Segment A?

Korrekte Antwort : 10

Lösung:

Lassen Sie uns den Ausdruck umwandeln – die Implikation durch eine Disjunktion ersetzen. Wir bekommen:

(¬(x ∈ A)) \/ ((x ∈ P)) \/ (x ∈ Q)

Der Ausdruck ((x ∈ P)) \/ (x ∈ Q) gilt nur für diejenigen x, die entweder in P oder in Q liegen, also für x ∈ R = P ∪ Q = ∪ . Ausdruck

(¬(x ∈ A)) \/ (x ∈ R)

ist genau dann identisch wahr, wenn A ∈ R. Da A ein Segment ist, gilt A ∈ R genau dann, wenn A ∈ P oder A ∈ Q. Da das Segment Q länger als das Segment P ist, ist die größte Länge des Segment A wird erreicht, wenn A = Q = . Die Länge von Segment A beträgt in diesem Fall 30 – 20 = 10.

3.2. Aufgabe 2.

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. Was ist die kleinste nicht negative ganze Zahl? A Formel

X&25 ≠ 0 → (X&33 ≠ 0 → X&A ≠ 0)

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

Korrekte Antwort : 57

Lösung:

Lassen Sie uns den Ausdruck umwandeln – die Implikationen durch Disjunktionen ersetzen. Wir bekommen:

¬( X&25 ≠ 0) ∨ (¬( X&33 ≠ 0) ∨ X&A ≠ 0)

Öffnen wir die Klammern und ersetzen wir die Negationen von Ungleichungen durch Gleichheiten:

X&25 = 0 ∨ X&33 = 0 ∨ X&A ≠ 0 (*)

Wir haben: 25 = 11001 2 und 33 = 100001 2. Daher die Formel

X&25 = 0 ∨ X&33 = 0

false genau dann, wenn die binäre Darstellung der Zahl X enthält eine 1 in mindestens einer der folgenden Binärziffern: 100000 (32), 10000 (16), 1000 (8) und 1.

Damit die Formel (*) für alle gilt X Es ist notwendig und ausreichend, dass die binäre Darstellung der Zahl A in allen diesen Bits 1 enthält. Die kleinste dieser Zahlen ist die Zahl 32+16+8+1 = 57.

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!