Zkouška z informatiky 18 úkol jak vyřešit

učitel informatiky ve společnosti MBOU "Lyceum"

první kvalifikační kategorie

Murzina Olga Ivanovna

MBOU "Lyceum" Arzamas

Teorie a praxe řešení úlohy 18 Jednotné státní zkoušky z informatiky

Arzamas, 2017

Mnemotechnické pravidlo

Jedním z jeho hlavních principů je komplementace k celku (doplnění opakem)

Socionika je informační psychologie

Řešení vzorce

V algebře logiky existuje vzorec pro doplněk celého čísla:

V některých úlohách použijeme místo tohoto vzorce násobení protikladů:

Druhy zaměstnání 18

• Úkoly segmentů
• Úkoly na sadách
• Úlohy na bitovou konjunkci
• Testy dělitelnosti

Úkoly segmentů

(č. 376) Na číselné ose jsou dva segmenty: P= a Q=. Určete nejmenší možnou délku segmentu A tak, aby vzorec ((x ∈ P) ∧ (x ∈ Q)) → (x ∈ A)

platí stejně, to znamená, že pro libovolnou hodnotu proměnné x nabývá hodnotu 1.

Řešení vzorce

má hodnotu 1 pro libovolnou hodnotu proměnné x.

Řešení problému segmentu

• Legenda
• Formalizace podmínky
• Řešení logické rovnice

Rozdělme řešení problému do etap:

Řešení problému segmentu

• Legenda- to jsou pohodlné symboly, které využijeme při řešení.

Představme si následující zápis:

Řešení problému segmentu

2) Formalizace podmínky– přepišme vzorec z úlohy podle legendy.

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

(P ∧ Q) → A = 1

Řešení problému segmentu

3) Řešení logické rovnice – Zpočátku je to možná nejobtížnější fáze řešení problému. Ale později, až získáte zkušenosti, už to nebude tak těžké 

Zvažme řešení logické rovnice krok za krokem.

Řešení problému segmentu

3.1. Představme si logický důsledek v základních logických operacích pomocí vzorce: A → B = ¬A  B:

(P ∧ Q) → A = 1

¬(P ∧ Q)  A = 1

Řešení problému segmentu

A  ¬A = 1 (v algebře logiky platí zákon komutativnosti, tj. A  ¬A = ¬A  A):

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

¬A = ¬(P ∧ Q)

Odpověď v logické rovnici bude:

Řešení problému segmentu

.

Naše odpověď: A = P ∧ Q.

V logické algebře tento výraz znamená průnik objemů dvou logických objektů. Podle podmínek našeho problému se jedná o průsečík segmentů P a Q.

Řešení problému segmentu

Průsečík segmentů P a Q lze zobrazit: P= a Q=.

Podle podmínek naší úlohy potřebujeme minimální délku segmentu A. Najdeme ji: 15 – 12 = 3.

Odpověď na webu K.Yu Polyakov: 3

Úkoly segmentů

(č. 360) Na číselné ose jsou tři segmenty: P=, Q= a R=. Jaká je maximální délka segmentu A, pro který platí vzorec ((x ∈ Q) → (x ∉ R)) ∧ (x ∈ A) ∧ (x ∉ P)

je shodně nepravda, to znamená, že má hodnotu 0 pro jakoukoli hodnotu proměnné x?

Zdroj - webové stránky Polyakova K.Yu.

Řešení vzorce

Chcete-li vybrat vzorec řešení, je důležité pečlivě přečíst požadavek na problém.

V našem problému požadavek říká:

má hodnotu 0 pro libovolnou hodnotu proměnné x.

Volba rozhodujícího vzorce je zřejmá:

Řešení problému segmentu

• Legenda
• Formalizace podmínky
• Řešení logické rovnice
• Interpretace získaného výsledku

Řešení problému segmentu

• Legenda

Řešení problému segmentu

2) Formalizace podmínky

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

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

Řešení problému segmentu

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

3.1. Představme si logický důsledek v základních logických operacích pomocí vzorce: A → B = ¬A  B a přeuspořádejme faktory podle zákona komutativního násobení:

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

Řešení problému segmentu

3) Řešení logické rovnice

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

3.2. Zredukujeme výsledný výraz na rozhodující vzorec: A  ¬A = 0 a zjistíme, čemu se ¬A rovná:

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

Řešení problému segmentu

3) Řešení logické rovnice

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

3.3. Zjednodušme výraz pro ¬A podle de Morganova zákona ¬A¬B=¬(AB):

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

a podle jiného de Morganova zákona ¬A¬B=¬(AB):

¬A = ¬ (Q  R  P)

Řešení problému segmentu

3) Řešení logické rovnice

¬A = ¬ (Q  R  P)

3.4. To je zřejmé

A = Q  R  P

Řešení problému segmentu

4) Interpretace získaného výsledku

A = Q  R  P

Segment A je průsečíkem segmentů Q a R a jeho sjednocením se segmentem P.

Řešení problému segmentu

Průsečík segmentů R a Q lze zobrazit: Q= a R=.

Nakreslíme segment P= na náš výkres a zkombinujeme jej s průsečíkem:

Řešení problému segmentu

Podle podmínek našeho problému potřebujeme maximální délku segmentu A. Najdeme ji: 30 – 10 = 20.

A = Q  R  P

Odpověď na webu K.Yu Polyakov: 20

2. Úkoly na množinách

(č. 386) Prvky množin A, P, Q jsou přirozená čísla a P=(1,2,3,4,5,6), Q=(3,5,15). Je známo, že výraz (x ∉ A) → ((x ∉ P) ∧ (x ∈ Q)) ∨ (x ∉ Q)

true (tj. nabývá hodnoty 1 pro libovolnou hodnotu proměnné x. Určete nejmenší možný počet prvků v množině A.

Zdroj - webové stránky Polyakova K.Yu.

Řešení problému na sadách

• Legenda
• Formalizace podmínky
• Řešení logické rovnice
• Interpretace získaného výsledku

Řešení problému na sadách

• Legenda

Řešení problému na sadách

2) Formalizace podmínky

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

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

Řešení problému na sadách

3) Řešení logické rovnice

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

3.1. Představme si logický důsledek v základních logických operacích a seskupme je:

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

Řešení problému na sadách

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

3.2. Zredukujeme výsledný výraz na rozhodující vzorec:

a zjistěte, čemu se ¬A rovná:

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

Řešení problému na sadách

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

3.3. Zjednodušme výraz pro ¬A otevřením závorek podle zákona distributivního sčítání:

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

¬A = (¬P  ¬Q)

Řešení problému na sadách

¬A = (¬P  ¬Q)

Podle De Morganova zákona:

¬A = ¬(P  Q)

3.4. To je zřejmé

Řešení problému na sadách

4) Interpretace získaného výsledku

Řešení problému na sadách

P = 1, 2, 3, 4, 5, 6 a Q =(3, 5,15), takže A =(3, 5)

a obsahuje pouze 2 prvky.

Odpověď na webu Polyakova: 2

2. Úkoly na množinách

(č. 368) Prvky množin A, P, Q jsou přirozená čísla a P=(2,4,6,8,10,12) a Q=(4,8,12,116). Je známo, že výraz (x ∈ P) → (((x ∈ Q) ∧ (x ∉ A)) → (x ∉ P))

true (tj. nabývá hodnoty 1) pro jakoukoli hodnotu proměnné x. Určete nejmenší možnou hodnotu součtu prvků množiny A.

Zdroj - webové stránky Polyakova K.Yu.

• Legenda
• Formalizace podmínky
• Řešení logické rovnice
• Interpretace získaného výsledku

Řešení problému na sadách

• Legenda

Řešení problému na sadách

2) Formalizace podmínky

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

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

Řešení problému na sadách

Řešení problému na sadách

3) Řešení logické rovnice

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

3.1. Představme si první logický důsledek (v závorce) v základních logických operacích:

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

Řešení problému na sadách

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

Představme si druhý logický důsledek v základních logických operacích, aplikujme De Morganův zákon a přeuspořádejme:

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

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

Řešení problému na sadách

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

3.2. Zredukujeme výsledný výraz na rozhodující vzorec:

a zjistěte, čemu se ¬A rovná:

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

Řešení problému na sadách

¬A = ¬P ¬Q  ¬P

3.3. Zjednodušme výraz pro ¬A pomocí vzorce A  A = A:

¬A = ¬(P Q)

Řešení problému na sadách

¬A = ¬(P Q)

3.4. To je zřejmé

4) Interpretace získaného výsledku

Potřebná množina A je průsečíkem množin P a Q.

Řešení problému na sadách

Potřebná množina A je průsečíkem množin

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

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

a obsahuje pouze 3 prvky, jejichž součet je 4+8+12=24.

Odpověď na webu Polyakova: 24

(č. 379) Označte podle m&n bitová konjunkce nezáporných celých čísel m A n. Takže například 14 & 5 = 11102 & 01012 = 01002 = 4. Jaké je nejmenší nezáporné celé číslo A vzorec (x & 29 ≠ 0) → ((x & 12 = 0) → (x & A ≠ 0))

je identicky pravdivá (tj. má hodnotu 1 pro jakoukoli nezápornou celočíselnou hodnotu proměnné x)?

• Legenda
• Formalizace podmínky
• Řešení logické rovnice
• Interpretace získaného výsledku

• Legenda

B = (x & 29 ≠ 0)

C = (x & 12 ≠ 0)

A = (x & A ≠ 0)

Řešení problému bitové konjunkce

Bitovou spojku jinou než nulovou přijímáme jako pravdivé tvrzení, jinak bitová spojka ztrácí logický význam, protože Vždy můžete reprezentovat X se všemi nulami.

Řešení problému bitové konjunkce

2) Formalizace podmínky

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

B → (¬C → A) = 1

Řešení problému bitové konjunkce

3) Řešení logické rovnice

B → (¬C → A) = 1

B → (C A) = 1

(¬B  C) A = 1

¬A = ¬B  C

¬A = ¬(B ¬ C)

To je zřejmé

A = B ¬ C

Řešení problému bitové konjunkce

Řešení problému bitové konjunkce

4) Interpretace získaného výsledku

Řešení problému bitové konjunkce

B = (x & 29 ≠ 0)

B nebo 29 = 111012

C = (x & 12 ≠ 0)

¬C nebo inverze 12 = 00112

Řešení problému bitové konjunkce

B nebo 29 = 111012

¬C nebo inverze 12 = 00112

A = B ¬ C

A = 100 012 = 17

Odpověď na webu Polyakova: 17

3. Úlohy na bitovou konjunkci

(č. 375) Představme si výraz M & K, označující bitovou konjunkci M a K (logické „AND“ mezi odpovídajícími bity binárního zápisu). Určete nejmenší přirozené číslo A tak, že výraz (X & 49 ≠ 0) → ((X & 33 = 0) → (X & A ≠ 0))

identicky pravdivé (tj. nabývá hodnoty 1 pro jakoukoli přirozenou hodnotu proměnné X)?

• Legenda
• Formalizace podmínky
• Řešení logické rovnice
• Interpretace získaného výsledku

Řešení problému bitové konjunkce

• Legenda

Legenda k problémům zahrnujícím bitové spojky se liší od všech ostatních případů:

B = (x & 49 ≠ 0)

C = (x & 33 ≠ 0)

A = (x & A ≠ 0)

Řešení problému bitové konjunkce

2) Formalizace podmínky

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

B → (¬C → A) = 1

Řešení problému bitové konjunkce

3) Řešení logické rovnice

B → (¬C → A) = 1

B → (C  A) = 1

(¬B  C)  A = 1

¬A = (¬B  C)

Očividně:

Řešení problému bitové konjunkce

Řešení problému bitové konjunkce

4) Interpretace získaného výsledku

Požadovaná binární hodnota bitové konjunkce A je binární hodnota bitové konjunkce hodnoty B a převrácená hodnota binární hodnoty C.

Řešení problému bitové konjunkce

B = (x & 49 ≠ 0)

B nebo 49 = 1100012

C = (x & 33 ≠ 0)

¬С nebo inverze 33 = 0111102

Řešení problému bitové konjunkce

B nebo 49 = 1100012

¬С nebo inverze 33 = 0111102

A = B ¬ C

011110 2

A = 100 002 = 16

Odpověď na webu Polyakova: 16

(č. 372) Označme DEL(n, m) výrok „přirozené číslo n je beze zbytku děleno přirozeným číslem m“. Pro jaké je největší přirozené číslo A platí vzorec ¬DIV(x,A) → (¬DIV(x,21) ∧ ¬DIV(x,35))

Zdroj - webové stránky Polyakova K.Yu.

• Legenda
• Formalizace podmínky
• Řešení logické rovnice
• Interpretace získaného výsledku

Řešení problému

na podmínku dělitelnosti

• Legenda

Řešení problému

na podmínku dělitelnosti

Legenda je jednoduchá: A = DIV(x,A)

21 = DIV(x.21)

35 = DIV(x,35)

2) Formalizace podmínky

Řešení problému

na podmínku dělitelnosti

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

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

stejně pravdivé (to znamená, že má hodnotu 1)

3) Řešení logické rovnice

Řešení problému

na podmínku dělitelnosti

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

A (¬21 ∧ ¬35) = 1

¬A = ¬21 ∧ ¬35

To je zřejmé

4) Interpretace získaného výsledku

V tomto problému se jedná o nejobtížnější fázi řešení. Musíte pochopit, co je číslo A - LOC nebo GCD nebo...

Řešení problému

na podmínku dělitelnosti

4) Interpretace získaného výsledku

Naše číslo A je tedy takové, že X je jím dělitelné beze zbytku právě tehdy, když je X dělitelné 21 nebo 35 beze zbytku. V tomto případě hledáme

A = gcd (21, 35) = 7

Řešení problému

na podmínku dělitelnosti

Odpověď na webu Polyakov: 7

4. Úkoly o podmínce dělitelnosti

(č. 370) Označme DEL(n, m) výrok „přirozené číslo n je beze zbytku dělitelné přirozeným číslem m“. Pro jaké je největší přirozené číslo A platí vzorec ¬DIV(x,A) → ((DIV(x,6) → ¬DIV(x,4))

identicky pravdivé (tj. nabývá hodnoty 1 pro jakoukoli přirozenou hodnotu proměnné x)?

Zdroj - webové stránky Polyakova K.Yu.

• Legenda
• Formalizace podmínky
• Řešení logické rovnice
• Interpretace získaného výsledku

Řešení problému

na podmínku dělitelnosti

• Legenda

A = DIV(x,A)

Řešení problému

na podmínku dělitelnosti

2) Formalizace podmínky

Řešení problému

na podmínku dělitelnosti

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

je identicky pravdivá (to znamená, že má hodnotu 1

¬A → (6 → ¬4) = 1

3) Řešení logické rovnice

¬A → (6 → ¬4) = 1

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

A  (¬ 6  ¬ 4) = 1

¬A = ¬ 6  ¬4

Očividně:

Řešení problému

na podmínku dělitelnosti

4) Interpretace získaného výsledku

A je tedy takové, že X je jím dělitelné beze zbytku právě tehdy, když je X dělitelné beze zbytku jak 6, tak 4. To znamená A = LCM(6,4) = 12

Odpověď na webu Polyakov: 12

Řešení problému

na podmínku dělitelnosti

Můžete nyní vysvětlit řešení úlohy 18 svým studentům nebo přátelům?

(ano, ne, nevím).

Děkuji za pozornost!

K vyřešení tohoto problému budeme muset učinit několik logických závěrů, takže „pozor na ruce“.

1. Chtějí, abychom našli minimální nezáporné celé číslo A, pro které je výraz vždy pravdivý.
2. Jaký je výraz jako celek? Něco tam je implikace něco je v závorkách.
3. Připomeňme si pravdivostní tabulku pro implikaci:
   1 => 1 = 1
   1 => 0 = 0
   0 => 1 = 1
   0 => 0 = 1
4. To znamená, že existují tři možné způsoby, jak to může být pravda. Zvažovat všechny tři tyto možnosti znamená zabít se a nežít. Zamysleme se nad tím, zda můžeme jít „protikladem“.
5. Místo hledání A zkusme najít x, pro které je tento výraz nepravdivý.
6. To znamená, že vezmeme nějaké číslo A (zatím nevíme, co to je, jen nějaké). Pokud najednou najdeme x ​​pro které je celý výrok nepravdivý, pak je vybrané A špatné (protože podmínka vyžaduje, aby výraz byl vždy pravdivý)!
7. Tímto způsobem můžeme získat určitá omezení pro číslo A.
8. Pojďme tedy zpět a vzpomeňme si, když je implikace nepravdivá? Když je první část pravdivá a druhá část je nepravdivá.
9. Prostředek
   \((\mathrm(x)\&25\neq 0)= 1 \\ (\mathrm(x)\&17=0\Šipka doprava \mathrm(x)\&\mathrm(A)\neq 0) = 0\)
10. Co to znamená, že \((x\&25\neq 0) = 1\) ? To znamená, že skutečně \(\mathrm(x)\&25\neq 0\) .
11. Převedeme 25 na binární. Dostáváme: 11001 2 .
12. Jaká omezení to má na x? Protože se nerovná nule, znamená to, že při bitové konjunkci musí být někde výsledek jedna. Ale kde by mohla být? Pouze tam, kde 25 již má jednotku!
13. To znamená, že číslo x alespoň v jednom křížku musí obsahovat jednotku: XXXXXX.
14. Skvělé, nyní se podívejme na druhý faktor: \((\mathrm(x)\&17=0\Šipka doprava \mathrm(x)\&\mathrm(A)\neq 0) = 0\)
15. Tento výraz také představuje implikaci. Navíc je stejně falešný.
16. To znamená, že jeho první část musí být pravdivá a druhá musí být nepravdivá.
17. Prostředek
    \((\mathrm(x)\&17=0) = 1 \\ ((\mathrm(x)\&\mathrm(A)\neq 0) = 0) = 0\)
18. Co to znamená, že \(\mathrm(x)\&17=0\) ? To, že na všech místech, kde jsou jedničky v 17, musí být v x nuly (jinak výsledek nebude 0).
19. Převedeme 17 na binární: 10001 2 . To znamená, že v x musí poslední místo od konce a 5. místo od konce obsahovat nuly.
20. Ale přestaň, v bodě 13 jsme to konečně dostali NEBO o 4 od konce NEBO 5 od konce by měla být jedna.
21. Vzhledem k tomu, že podle řádku 19 nemůže být jednotka na posledním nebo 5. místě od konce, tzn. musí být na 4. místě od konce.
22. To znamená, že pokud chceme, aby u našeho x byl celý výraz nepravdivý, musí být na 4. místě od konce jednotka: XX...XX1XXX 2.
23. Skvělé, nyní zvažte poslední podmínku: \((\mathrm(x)\&\mathrm(A)\neq 0) = 0\). Co to znamená?
24. To znamená, že to není pravda \(\mathrm(x)\&\mathrm(A)\neq 0\).
25. To je ve skutečnosti \(\mathrm(x)\&\mathrm(A)=0\) .
26. Co víme o x? Že je jednotka na 4. místě od konce. Ve všech ostatních ohledech může být x téměř cokoliv.
27. Pokud chceme, aby původní výraz v problémovém prohlášení byl vždy pravdivý, pak my by neměl najít x, která by splňovala všechny podmínky. Pokud bychom totiž našli takové x, ukázalo by se, že původní výraz není vždy pravdivý, což je v rozporu s podmínkami problému.
28. To znamená, že tato úplně poslední podmínka prostě nesmí být splněna.
29. Jak to nemůže být splněno? Kdybychom si byli 100% jisti, že při bitové konjunkci někde zůstane jednotka.
30. A to je možné: pokud je v A také jednotka na 4. místě od konce, pak v důsledku bitové konjunkce bude jednotka na 4. místě od konce.
31. Jaké je nejmenší možné binární číslo s 1 na 4. konci? Pochopitelně 1000 2. Takže toto číslo bude odpovědí.
32. Zbývá jen převést na desítkové: \(1000_2=0\krát 2^0 + 0\krát 2^1 + 0\krát 2^2 + 1\krát 2^3=8\)

Odpověď: minimální možné A, které splňuje podmínky, rovná se 8.

Jevgenij Smirnov

IT expert, učitel informatiky

Řešení #2

Lze navrhnout o něco kratší přístup. Označme náš výrok jako F = (A->(B->C)), kde A je výrok „X&25 se nerovná 0“, B = „X&17=0“ a C = „X&A se nerovná 0“ “.

Rozšiřme implikace, pomocí známého zákona X->Y = not(X) OR Y, dostaneme F = A -> (not(B) OR C) = not(A) OR not(B) OR C. Zapíšeme také binární hodnoty konstant 25 a 17:

Náš výraz je logický NEBO tří příkazů:

1) ne (A) – to znamená X&25 = 0 (bity 0,3,4 z X jsou všechny 0)

2) ne (B) – znamená, že X&17 se nerovná 0 (bity 0 a 4 z X alespoň jedna se rovna 1)

3) C - ví, že X&A se nerovná 0 (bity specifikované maskou A, alespoň 1 se rovná 1)

X je libovolné číslo. Všechny jeho bity jsou nezávislé. Je tedy možné požadovat splnění nějaké podmínky na bitech libovolného čísla pouze v jednom jediném případě - když mluvíme o stejné masce (množině bitů). Můžeme si všimnout, že binární maska ​​17 je téměř stejná jako 25, chybí pouze bit číslo 3, pokud bychom doplnili 17 bitem číslo 3, pak by se výraz (ne (B) OR C) změnil na ne. (ne A ), tzn. v A = (X&25 se nerovná 0). Jiným způsobem: řekněme A=8 (bit 3=1). Potom je požadavek (nikoli (B) B nebo C) ekvivalentní požadavku: (alespoň jeden z bitů 4,0 se rovná 1) NEBO (bit 3 se rovná 1) = (alespoň jeden z bitů 0, 3,4 se nerovná 1) - ty. inverze not(A) = A = (X&25 se nerovná 0).

V důsledku toho jsme si všimli, že pokud A = 8, pak náš výraz nabývá tvaru F = ne (A) NEBO A, což je podle zákona o vyloučeném středu vždy shodně pravdivé. Pro jiné menší hodnoty A nelze nezávislost na hodnotě X získat, protože Masky vycházejí jinak. No, pokud jsou jedničky v nejvýznamnějších bitech A, nic se nemění v bitech nad 4, protože ve zbývajících maskách máme nuly. Ukazuje se, že pouze když A = 8, vzorec se změní na tautologii pro libovolné X.

Dmitrij Lisin

Je známo, že výraz

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

true (to znamená, že má hodnotu 1) pro jakoukoli hodnotu proměnné x. Určete největší možný počet prvků v množině A.

Řešení.

Představme si následující zápis:

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

Potom použitím implikační transformace získáme:

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

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

Je požadováno, aby ¬A + ¬Q · P = 1. Výraz ¬Q · P je pravdivý, když x ∈ (2, 4, 8, 10, 14, 16, 20). Potom ¬A musí platit, když x ∈ (1, 3, 5, 6, 7, 9, 11, 12, 13, 15, 17, 18, 19, 21, 22, 23,...).

Maximální počet prvků v množině A tedy bude, pokud A zahrnuje všechny prvky množiny ¬Q · P, takových prvků je sedm.

Odpověď: 7.

Odpověď: 7

Prvky množiny A jsou přirozená čísla. Je známo, že výraz

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

Řešení.

Představme si následující zápis:

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

Transformací získáme:

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

Logické OR je pravdivé, pokud je pravdivé alespoň jedno tvrzení. Výraz ¬P ∨ ¬Q platí pro všechny hodnoty x kromě hodnot 6 a 12. Interval A tedy musí obsahovat body 6 a 12. Tedy minimální množinu bodů v intervalu A ≡ ( 6, 12). Součet prvků množiny A je 18.

Odpověď: 18.

Odpověď: 18

Prvky množin A, P, Q jsou přirozená čísla, přičemž P = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20), Q = (3, 6, 9, 12, 15, 18, 21, 24, 27, 30).

Je známo, že výraz

true (tj. nabývá hodnoty 1) pro jakoukoli hodnotu proměnné x. Určete nejmenší možnou hodnotu součtu prvků množiny A.

Řešení.

Pojďme to zjednodušit:

¬(x P) ∨ ¬(x Q) dejte 0 pouze tehdy, když číslo leží v obou množinách. To znamená, že aby byl celý výraz pravdivý, musíme všechna čísla ležící v P a Q dosadit do A. Taková čísla jsou 6, 12, 18. Jejich součet je 36.

Odpověď: 36.

Odpověď: 36

Zdroj: Školicí práce v oboru POČÍTAČOVÁ VĚDA, ročník 11 18. ledna 2017 Možnost IN10304

Prvky množin A, P, Q jsou přirozená čísla, přičemž P = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20), Q = (3, 6, 9, 12, 15, 18, 21, 24, 27, 30).

Je známo, že výraz ((x A) → (x P)) ∨ (¬(x Q) → ¬(x A))

true (tj. má hodnotu 1) pro jakoukoli hodnotu proměnné x.

Určete největší možný počet prvků v množině A.

Řešení.

Převedeme tento výraz:

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

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

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

Prvek tedy musí být buď zahrnut v P nebo Q, nebo nesmí být zahrnut v A. Tedy A může obsahovat pouze prvky z P a Q. A celkem je v těchto dvou množinách 17 neopakujících se prvků.

Odpověď: 17

Prvky množin A, P, Q jsou přirozená čísla a P = (1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21), Q = (3, 6, 9, 12, 15, 18, 21, 24, 27, 30). Je známo, že výraz

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

true (tj. nabývá hodnoty 1) pro jakoukoli hodnotu proměnné x. Určete nejmenší možnou hodnotu součtu prvků množiny A.

Řešení.

Odhalme dvě implikace. Dostaneme:

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

Pojďme to zjednodušit:

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

¬(x P) ∨ ¬(x Q) dejte 0 pouze tehdy, když číslo leží v obou množinách. To znamená, že aby byl celý výraz pravdivý, musíte všechna čísla v P a Q dosadit do A. Tato čísla jsou 3, 9, 15 a 21. Jejich součet je 48.

Odpověď: 48.

Odpověď: 48

Zdroj: Školicí práce v oboru POČÍTAČOVÁ VĚDA, ročník 11 18. ledna 2017 Možnost IN10303

A výraz

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

X a y?

Řešení.

Všimněte si, že aby byl tento výraz stejně pravdivý, výraz (y + 2x odpověď: 81.

Odpověď: 81

Zdroj: Jednotná státní zkouška - 2018. Raná vlna. Varianta 1., Jednotná státní zkouška - 2018. Raná vlna. Možnost 2.

Na číselné ose je uveden segment A. Je známo, že vzorec

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

platí stejně pro jakýkoli reál X. Jaká je nejkratší délka segmentu A?

Řešení.

Rozšířením implikace podle pravidla A → B = ¬A + B, nahrazením logického součtu množinou a logického součinu systémem relací, určíme hodnoty parametru A, při kterém systém agregátů

bude mít řešení pro jakákoli reálná čísla.

Aby řešení systému byla všechna reálná čísla, je nutné a postačující, aby řešení každého z kolekcí byla všechna reálná čísla.

Řešení nerovnice jsou všechna čísla z intervalu [−10; 10]. Aby sbírka platila pro všechna reálná čísla, čísla X, neležící na zadaném segmentu, musí patřit do segmentu A. V důsledku toho segment A nesmí přesahovat hranice segmentu [−10; 10].

Podobně řešením nerovnosti jsou čísla z paprsků a Aby kolekce platila pro všechna reálná čísla, čísla X, neležící na vyznačených paprscích, musí ležet na segmentu A. V důsledku toho segment A musí obsahovat segment [−8; 8].

Nejkratší délka segmentu A se tedy může rovnat 8 + 8 = 16.

Odpověď: 16.

Odpověď: 16

A výraz

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

je identicky pravdivý, to znamená, že má hodnotu 1 pro všechna nezáporná celá čísla X A y?

Řešení.

A X A y, podívejme se, v jakých případech jsou podmínky ( y + 2x≠ 48) a ( X y) jsou nepravdivé.

y = 48 − 2x) a (x ≥ y). Tento X v rozmezí od 16 do 24 a y v rozsahu od 0 do 16. Všimněte si, že aby byl výraz vhodný pro jakýkoli X A y, nutné vzít X= 16 a y= 16. Pak A A se bude rovnat 15.

Odpověď: 15.

Odpověď: 15

Zdroj: Jednotná státní zkouška z informatiky 28.05.2018. Hlavní vlna, verze A. Imaeva - „Kotolis“.

Pro jaké je největší nezáporné celé číslo A výraz

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

je identicky pravdivý, to znamená, že má hodnotu 1 pro všechna nezáporná celá čísla X A y?

Řešení.

Chcete-li najít největší nezáporné celé číslo A, u kterého bude výraz X A y, podívejme se, v jakých případech je podmínka ( y + 2x≠ 48) je nepravdivé.

Všechna řešení tedy najdeme, když ( y = 48 − 2x). Tento X v rozsahu od 0 do 24 a y v rozsahu od 48 do 0. Všimněte si, že aby byl výraz vhodný pro jakýkoli X A y, nutné vzít X= 16 a y= 16. Pak A A se bude rovnat 15.

Odpověď: 15.

Odpověď: 15

Zdroj: Demoverze jednotné státní zkoušky 2019 z informatiky.

Co je nejmenší nezáporné celé číslo A výraz

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

platí stejně pro všechna nezáporná celá čísla X A y?

Řešení.

A, ve kterém bude výraz identicky pravdivý pro všechna nezáporná celá čísla X A yy + 2x> 30) nepravdivé.

y + 2X≤ 30). Tento X v rozsahu od 0 do 15 a y v rozsahu od 10 do 0. Všimněte si, že aby byl výraz vhodný pro jakýkoli X A y, nutné vzít X= 15 a y= 0. Pak 15 + 0 ≤ A. Tedy nejmenší nezáporné celé číslo A se bude rovnat 15.

Odpověď: 15.

Odpověď: 15

Pro jaké je největší nezáporné celé číslo A výraz

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

platí stejně pro všechna nezáporná celá čísla X A y?

Řešení.

Chcete-li najít největší nezáporné celé číslo A, ve kterém bude výraz identicky pravdivý pro všechna nezáporná celá čísla X A y, uvažme, v jakých případech podmínka (3 y + 2x Všechna řešení tedy najdeme, když (3 y + 2X≥ 30). Tento X více než 15 a y větší než 10. Všimněte si, že aby byl výraz vhodný pro jakýkoli X A y, nutné vzít X= 0 a y= 10. Pak 0 + 10 ≤ A. Proto největší nezáporné celé číslo A se bude rovnat 10.

Odpověď: 10.

Odpověď: 10

Co je nejmenší nezáporné celé číslo A výraz

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

platí stejně pro všechna nezáporná celá čísla X A y?

Řešení.

Chcete-li najít nejmenší nezáporné celé číslo A, ve kterém bude výraz identicky pravdivý pro všechna nezáporná celá čísla X A y, uvažme, v jakých případech podmínka (3 X + 4y≠ 70) je nepravda.

Všechna řešení tedy najdeme, když (3 X + 4y= 70). Tento X v rozmezí od 2 do 22 a y v rozsahu od 16 do 1. Všimněte si, že aby byl výraz vhodný pro jakýkoli X A y, nutné vzít X= 10 a y= 10. Pak A> 10. Tedy nejmenší nezáporné celé číslo A se bude rovnat 11.

1. Příklad z demo verze

(první souhláska → druhá souhláska) / (předposlední samohláska → poslední samohláska)

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

Náčrt řešení Implikace a → b je ekvivalentní ¬a / b.

První implikace platí pro slova KRISTINA a STEPAN. Druhá implikace z těchto slov platí pouze pro slovo CHRISTINE.

Odpověď: 1. CHRISTINA

2. Další dva příklady

Příklad 1 (otevřený segment FIPI Bank)

Které z uvedených jmen splňuje logickou podmínku:

(první souhláska → první samohláska) / (poslední samohláska → poslední souhláska)

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

Náčrt řešení. Implikace a → b je ekvivalentní ¬a / b. Tento výraz je pravdivý, pokud je buď výraz a nepravdivý, nebo oba výrazy a a b jsou pravdivé. Protože v našem případě v žádné z implikací nemohou být oba výrazy pravdivé současně, musí být výroky „první písmeno je souhláska“ a „poslední písmeno je samohláska“ nepravdivé, to znamená, že potřebujeme slovo, jehož první písmeno je samohláska a poslední je souhláska.

Odpovědět: 3. ARTEM.

Příklad 2 Pro kterou z uvedených hodnot čísla X platí tvrzení?

(X< 4)→(X >15)

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

Řešení. Žádné číslo nemůže být zároveň menší než 4 a větší než 15. Implikace je tedy pravdivá pouze v případě, že předpoklad X< 4 Nepravdivé.

Odpovědět 4.

2. Problémy ve formátu jednotné státní zkoušky 2013-2014.

2.1. Demo verze 2013

Na číselné ose jsou dva segmenty: P = a Q = .

Vyberte segment A takový, že vzorec

1) 2) 3) 4)

2.2. Demo verze 2014

Na číselné ose jsou dva segmenty: P = a Q = . Z navržených segmentů vyberte segment A, jako je logický výraz

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

totéž platí, to znamená, že pro jakoukoli hodnotu proměnné nabývá hodnotu 1

Možnosti odpovědí: 1) 2) 3) 4)

Řešení. Transformujme výraz pomocí . My máme:

¬((x ∈ P) → ¬ (x ∈ Q)) ∨ (¬ (x ∈ A)) - nahrazení implikace disjunkcí;

¬(¬(x ∈ P) ∨ ¬ (x ∈ Q)) ∨ (¬ (x ∈ A)) - nahrazení implikace disjunkcí;

((x ∈ P) ∧ (x ∈ Q)) ∨ (¬ (x ∈ A)) - de Morganovo pravidlo a odstranění dvojité negace;

(x ∈ A) → ((x ∈ P) ∧ (x ∈ Q)) – nahrazení disjunkce implikací

Poslední výraz je shodně pravdivý právě tehdy, když A ⊆ P∩ Q = ∩ = (viz ). Ze čtyř daných segmentů tuto podmínku splňuje pouze segment - volba č. 2.

Odpovědět: - možnost č. 2

3. Problémy ve formátu Jednotné státní zkoušky 2015-2016.

3.1. Úkol 1.

Na číselné ose jsou dva segmenty: P = a Q = .

Je známo, že hranice segmentu A jsou celočíselné body a pro segment A vzorec

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

platí stejně, to znamená, že pro libovolnou hodnotu proměnné x nabývá hodnotu 1.

Jaká je největší možná délka segmentu A?

Správná odpověď : 10

Řešení:

Transformujme výraz – implikaci nahraďme disjunkcí. Dostaneme:

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

Výraz ((x ∈ P)) \/ (x ∈ Q) platí pouze pro ta x, která leží buď v P nebo v Q, jinými slovy pro x ∈ R = P ∪ Q = ∪ . Výraz

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

je shodně pravdivá právě tehdy, když A ∈ R. Protože A je úsečka, pak A ∈ R právě tehdy, když A ∈ P nebo A ∈ Q. Protože úsečka Q je delší než úsečka P, pak největší délka segmentu A je dosaženo, když A = Q =. Délka segmentu A je v tomto případě 30 – 20 = 10.

3.2. Úkol 2.

Označme podle m&n bitová konjunkce nezáporných celých čísel m A n. Takže například 14&5 = 1110 2 &0101 2 = 0100 2 = 4. Jaké je nejmenší nezáporné celé číslo A vzorec

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

je identicky pravdivá, tzn. má hodnotu 1 pro jakoukoli nezápornou celočíselnou hodnotu proměnné X?

Správná odpověď : 57

Řešení:

Transformujme výraz – implikace nahraďme disjunkcemi. Dostaneme:

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

Otevřeme závorky a nahradíme negace nerovností rovností:

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

Máme: 25 = 11001 2 a 33 = 100001 2. Proto vzorec

X&25 = 0 ∨ X&33 = 0

false tehdy a jen tehdy, když je binární reprezentace čísla X obsahuje 1 alespoň v jedné z následujících binárních číslic: 100000 (32), 10000 (16), 1000 (8) a 1.

Aby vzorec (*) byl pravdivý pro všechny takové X Je nutné a postačující, aby binární reprezentace čísla A obsahovala 1 ve všech těchto bitech. Nejmenší takové číslo je číslo 32+16+8+1 = 57.

Pro efektivní přípravu v informatice je u každého úkolu uveden stručný teoretický materiál pro splnění úkolu. Bylo vybráno více než 10 školicích úkolů s analýzou a odpověďmi, které byly vyvinuty na základě demoverze z předchozích let.

Jednotná státní zkouška KIM z informatiky a ICT pro rok 2019 se nemění.

Oblasti, ve kterých budou znalosti testovány:

• Programování;
• Algoritmizace;
• nástroje ICT;
• Informační činnost;
• Informační procesy.

Nezbytné akce, když příprava:

• Opakování teoretického kurzu;
• Řešení testy v informatice online;
• Znalost programovacích jazyků;
• Zlepšit matematiku a matematickou logiku;
• K úspěchu při jednotné státní zkoušce nestačí používat širší spektrum literatury – školního vzdělávacího programu.

Struktura zkoušky

Délka zkoušky je 3 hodiny 55 minut (255 minut), z toho hodinu a půl se doporučuje věnovat plnění úkolů první části KIM.

Úkoly na lístcích jsou rozděleny do bloků:

• Část 1- 23 úkolů s krátkou odpovědí.
• Část 2- 4 úkoly s podrobnými odpověďmi.

Z navržených 23 úloh první části zkouškové práce patří 12 do základní úrovně testování znalostí, 10 – do zvýšené složitosti, 1 – do vysoké úrovně složitosti. Tři úkoly druhé části jsou na vysoké úrovni složitosti, jedna je na vyšší úrovni.

Při rozhodování je nutné zaznamenat podrobnou odpověď (volná forma).
V některých úlohách je text podmínky prezentován v pěti programovacích jazycích najednou - pro pohodlí studentů.

Body za úkoly z informatiky

1 bod - za 1-23 úkolů
2 body - 25.
3 body - 24, 26.
4 body - 27.
Celkem: 35 bodů.

Pro vstup na střední technickou univerzitu musíte získat alespoň 62 bodů. Pro vstup na univerzitu hlavního města musí počet bodů odpovídat 85-95.

K úspěšnému napsání zkouškové práce je nutná jasná znalost teorie a konstantní praxe v řešeníúkoly.

Váš recept na úspěch

Práce + práce na chybách + pozorně si přečtěte otázku od začátku do konce, abyste se vyvarovali chyb = maximální počet bodů na Jednotné státní zkoušce z informatiky.