Riešenie 18 úlohy z informatiky.

Je známe, že výraz

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

true (to znamená, že má hodnotu 1) pre akúkoľvek hodnotu premennej x. Určte najväčší možný počet prvkov v množine A.

Riešenie.

Predstavme si nasledujúci zápis:

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

Potom použitím implikačnej transformácie získame:

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

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

Vyžaduje sa, aby ¬A + ¬Q · P = 1. Výraz ¬Q · P je pravdivý, keď x ∈ (2, 4, 8, 10, 14, 16, 20). Potom ¬A musí platiť, keď x ∈ (1, 3, 5, 6, 7, 9, 11, 12, 13, 15, 17, 18, 19, 21, 22, 23,...).

Preto maximálny počet prvkov v množine A bude, ak A zahŕňa všetky prvky množiny ¬Q · P, takýchto prvkov je sedem.

odpoveď: 7.

odpoveď: 7

Prvky množiny A sú prirodzené čísla. Je známe, ž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)))

Riešenie.

Predstavme si nasledujúci zápis:

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

Transformáciou dostaneme:

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

Logické OR je pravdivé, ak je pravdivé aspoň jedno tvrdenie. Výraz ¬P ∨ ¬Q platí pre všetky hodnoty x okrem hodnôt 6 a 12. Preto interval A musí obsahovať body 6 a 12. Teda minimálnu množinu bodov v intervale A ≡ ( 6, 12). Súčet prvkov množiny A je 18.

odpoveď: 18.

odpoveď: 18

Prvky množín A, P, Q sú prirodzené čísla, pričom P = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20), Q = (3, 6, 9, 12, 15, 18, 21, 24, 27, 30).

Je známe, že výraz

true (t. j. má hodnotu 1) pre akúkoľvek hodnotu premennej x. Určte najmenšiu možnú hodnotu súčtu prvkov množiny A.

Riešenie.

Zjednodušme si to:

¬(x P) ∨ ¬(x Q) daj 0 len vtedy, keď číslo leží v oboch množinách. To znamená, že aby bol celý výraz pravdivý, musíme všetky čísla ležiace v P a Q dať do A. Takéto čísla sú 6, 12, 18. Ich súčet je 36.

odpoveď: 36.

odpoveď: 36

Zdroj: Cvičná práca v INFORMAČNEJ VEDE, ročník 11 18. januára 2017 Možnosť IN10304

Prvky množín A, P, Q sú prirodzené čísla, pričom P = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20), Q = (3, 6, 9, 12, 15, 18, 21, 24, 27, 30).

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

true (t. j. má hodnotu 1) pre akúkoľvek hodnotu premennej x.

Určte najväčší možný počet prvkov v množine A.

Riešenie.

Transformujme 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)

Prvok teda musí byť buď zahrnutý v P alebo Q, alebo nesmie byť zahrnutý v A. Teda A môže obsahovať iba prvky z P a Q. A celkovo je v týchto dvoch množinách 17 neopakujúcich sa prvkov.

odpoveď: 17

Prvky množín A, P, Q sú prirodzené čí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áme, že výraz

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

true (t. j. má hodnotu 1) pre akúkoľvek hodnotu premennej x. Určte najmenšiu možnú hodnotu súčtu prvkov množiny A.

Riešenie.

Odhalíme dve implikácie. Dostaneme:

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

Zjednodušme si to:

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

¬(x P) ∨ ¬(x Q) daj 0 len vtedy, keď číslo leží v oboch množinách. To znamená, že aby bol celý výraz pravdivý, musíte všetky čísla v P a Q vložiť do A. Tieto čísla sú 3, 9, 15 a 21. Ich súčet je 48.

odpoveď: 48.

odpoveď: 48

Zdroj: Cvičná práca v INFORMAČNEJ VEDE, ročník 11 18. januára 2017 Možnosť IN10303

A výraz

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

X a y?

Riešenie.

Všimnite si, že aby bol tento výraz rovnako pravdivý, výraz (y + 2x odpoveď: 81.

odpoveď: 81

Zdroj: Jednotná štátna skúška - 2018. Skorá vlna. Možnosť 1., Jednotná štátna skúška - 2018. Skorá vlna. Možnosť 2.

Na číselnej osi je uvedený segment A. Je známe, že vzorec

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

platí rovnako pre akúkoľvek realitu X. Aká je najkratšia dĺžka segmentu A?

Riešenie.

Rozšírením implikácie podľa pravidla A → B = ¬A + B, nahradením logického súčtu množinou a logického súčinu systémom vzťahov, určíme hodnoty parametra A, pri ktorej sústava agregátov

bude mať riešenia pre akékoľvek reálne čísla.

Aby riešenia systému boli všetky reálne čísla, je potrebné a postačujúce, aby riešenia každého z kolekcií boli všetky reálne čísla.

Riešením nerovnice sú všetky čísla z intervalu [−10; 10]. Aby zbierka platila pre všetky reálne čísla, čísla X, ktorý neleží na špecifikovanom segmente, musí patriť do segmentu A. V dôsledku toho segment A nesmie presahovať hranice segmentu [−10; 10].

Podobne riešenia nerovnosti sú čísla z lúčov a Aby kolekcia platila pre všetky reálne čísla, čísla X, ktorý neleží na vyznačených lúčoch, musí ležať na segmente A. V dôsledku toho segment A musí obsahovať segment [−8; 8].

Najkratšia dĺžka segmentu A sa teda môže rovnať 8 + 8 = 16.

odpoveď: 16.

odpoveď: 16

A výraz

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

je rovnako pravdivé, to znamená, že má hodnotu 1 pre všetky nezáporné celé čísla X A r?

Riešenie.

A X A r, zvážme, v akých prípadoch sú podmienky ( r + 2x≠ 48) a ( X y) sú nepravdivé.

r = 48 − 2x) a (x ≥ y). Toto X v rozmedzí od 16 do 24 a r v rozsahu od 0 do 16. Všimnite si, že aby bol výraz vhodný pre ľubovoľné X A r, povinný vziať X= 16 a r= 16. Potom A A sa bude rovnať 15.

odpoveď: 15.

odpoveď: 15

Zdroj: Jednotná štátna skúška z informatiky 28.05.2018. Hlavná vlna, verzia A. Imaeva - „Kotolis“.

Čo je najväčšie nezáporné celé číslo A výraz

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

je rovnako pravdivé, to znamená, že má hodnotu 1 pre všetky nezáporné celé čísla X A r?

Riešenie.

Ak chcete nájsť najväčšie nezáporné celé číslo A, pri ktorej bude výraz X A r, zvážme, v ktorých prípadoch je podmienka ( r + 2x≠ 48) je nepravdivé.

Všetky riešenia teda nájdeme, keď ( r = 48 − 2x). Toto X v rozsahu od 0 do 24 a r v rozsahu od 48 do 0. Všimnite si, že aby bol výraz vhodný pre ľubovoľné X A r, povinný vziať X= 16 a r= 16. Potom A A sa bude rovnať 15.

odpoveď: 15.

odpoveď: 15

Zdroj: Demo verzia Jednotnej štátnej skúšky 2019 z informatiky.

Čo je najmenšie nezáporné celé číslo A výraz

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

platí rovnako pre všetky nezáporné celé čísla X A r?

Riešenie.

A, v ktorom bude výraz identicky pravdivý pre všetky nezáporné celé čísla X A rr + 2x> 30) nepravdivé.

r + 2X≤ 30). Toto X v rozsahu od 0 do 15 a r v rozsahu od 10 do 0. Všimnite si, že aby bol výraz vhodný pre ľubovoľné X A r, povinný vziať X= 15 a r= 0. Potom 15 + 0 ≤ A. Preto najmenšie nezáporné celé číslo A sa bude rovnať 15.

odpoveď: 15.

odpoveď: 15

Čo je najväčšie nezáporné celé číslo A výraz

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

platí rovnako pre všetky nezáporné celé čísla X A r?

Riešenie.

Ak chcete nájsť najväčšie nezáporné celé číslo A, v ktorom bude výraz identicky pravdivý pre všetky nezáporné celé čísla X A r, uvažujme, v akých prípadoch je stav (3 r + 2x Všetky riešenia teda nájdeme, keď (3 r + 2X≥ 30). Toto X viac ako 15 a r väčší ako 10. Všimnite si, že na to, aby bol výraz vhodný pre ľubovoľné X A r, povinný vziať X= 0 a r= 10. Potom 0 + 10 ≤ A. Preto najväčšie nezáporné celé číslo A sa bude rovnať 10.

odpoveď: 10.

odpoveď: 10

Čo je najmenšie nezáporné celé číslo A výraz

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

platí rovnako pre všetky nezáporné celé čísla X A r?

Riešenie.

Ak chcete nájsť najmenšie nezáporné celé číslo A, v ktorom bude výraz identicky pravdivý pre všetky nezáporné celé čísla X A r, uvažujme, v akých prípadoch je stav (3 X + 4r≠ 70) je nepravdivé.

Všetky riešenia teda nájdeme, keď (3 X + 4r= 70). Toto X v rozmedzí od 2 do 22 a r v rozsahu od 16 do 1. Všimnite si, že aby bol výraz vhodný pre ľubovoľné X A r, povinný vziať X= 10 a r= 10. Potom A> 10. Preto najmenšie nezáporné celé číslo A sa bude rovnať 11.

Na vyriešenie tohto problému budeme musieť urobiť niekoľko logických záverov, takže „pozor na ruky“.

  1. Chcú, aby sme našli minimálne nezáporné celé číslo A, pre ktoré je výraz vždy pravdivý.
  2. Aký je výraz ako celok? Niečo tam je implikácia v zátvorkách je niečo.
  3. Pripomeňme si pravdivostnú tabuľku pre implikáciu:
    1 => 1 = 1
    1 => 0 = 0
    0 => 1 = 1
    0 => 0 = 1
  4. To znamená, že existujú tri možné spôsoby, ako to môže byť pravda. Zvážiť všetky tieto tri možnosti znamená zabiť sa a nežiť. Zamyslime sa nad tým, či môžeme ísť „protirečením“.
  5. Namiesto hľadania A skúsme nájsť x, pre ktoré je tento výraz nepravdivý.
  6. To znamená, vezmime si nejaké číslo A (zatiaľ nevieme, čo to je, len nejaké). Ak zrazu nájdeme x ​​, pre ktoré je celé tvrdenie nepravdivé, potom zvolené A je zlé (pretože podmienka vyžaduje, aby bol výraz vždy pravdivý)!
  7. Týmto spôsobom môžeme získať určité obmedzenia na číslo A.
  8. Takže, poďme späť a spomeňme si, keď je implikácia nepravdivá? Keď je prvá časť pravdivá a druhá časť je nepravdivá.
  9. Prostriedky
    \((\mathrm(x)\&25\neq 0)= 1 \\ (\mathrm(x)\&17=0\Šípka doprava \mathrm(x)\&\mathrm(A)\neq 0) = 0\)
  10. Čo to znamená, že \((x\&25\neq 0) = 1\) ? To znamená, že skutočne \(\mathrm(x)\&25\neq 0\) .
  11. Prevedieme 25 na binárne. Dostávame: 11001 2 .
  12. Aké obmedzenia má toto na x? Keďže sa nerovná nule, znamená to, že pri bitovej konjunkcii musí byť niekde výsledok jedna. Ale kde by mohla byť? Len tam, kde 25 už má jednotku!
  13. To znamená, že číslo x aspoň v jednom krížiku musí obsahovať jednotku: XXXXXX.
  14. Skvelé, teraz sa pozrime na druhý faktor: \((\mathrm(x)\&17=0\šípka doprava \mathrm(x)\&\mathrm(A)\neq 0) = 0\)
  15. Tento výraz tiež predstavuje implikáciu. Navyše je rovnako falošný.
  16. To znamená, že jeho prvá časť musí byť pravdivá a druhá musí byť nepravdivá.
  17. Prostriedky
    \((\mathrm(x)\&17=0) = 1 \\ ((\mathrm(x)\&\mathrm(A)\neq 0) = 0) = 0\)
  18. Čo to znamená, že \(\mathrm(x)\&17=0\) ? Skutočnosť, že na všetkých miestach, kde sú jednotky v 17, musia byť v x nuly (inak výsledok nebude 0).
  19. Preveďme 17 na binárne: 10001 2 . To znamená, že v x musí posledné miesto od konca a 5. miesto od konca obsahovať nuly.
  20. Ale prestaň, v bode 13 sme to konečne dostali ALEBO o 4 od konca ALEBO 5 od konca by mala byť jedna.
  21. Keďže podľa riadku 19 nemôže byť jednotka na poslednom alebo 5. mieste od konca, čiže musí byť na 4. mieste od konca.
  22. To znamená, že ak chceme, aby pri našom x bol celý výraz nepravdivý, na 4. mieste od konca musí byť jednotka: XX...XX1XXX 2.
  23. Skvelé, teraz zvážte poslednú podmienku: \((\mathrm(x)\&\mathrm(A)\neq 0) = 0\). Čo to znamená?
  24. To znamená, že to nie je pravda \(\mathrm(x)\&\mathrm(A)\neq 0\).
  25. To je v skutočnosti \(\mathrm(x)\&\mathrm(A)=0\) .
  26. Čo vieme o x? Že je jednotka na 4. mieste od konca. Vo všetkých ostatných ohľadoch môže byť x takmer čokoľvek.
  27. Ak chceme, aby pôvodný výraz v problémovom vyhlásení bol vždy pravdivý, potom my by nemal nájsť x, ktorý by spĺňal všetky podmienky. Ak by sme totiž našli takéto x, ukázalo by sa, že pôvodný výraz nie je vždy pravdivý, čo je v rozpore s podmienkami úlohy.
  28. To znamená, že táto posledná podmienka jednoducho nesmie byť splnená.
  29. Ako sa to nedá naplniť? Len keby sme si boli 100% istí, že pri bitovej konjunkcii niekde zostane jednotka.
  30. A to je možné: ak je v A aj jednotka na 4. mieste od konca, tak v dôsledku bitovej konjunkcie bude jednotka na 4. mieste od konca.
  31. Aké je najmenšie možné binárne číslo s 1 na 4. konci? Samozrejme, 1000 2. Takže toto číslo bude odpoveďou.
  32. Zostáva len previesť ho na desatinné číslo: \(1000_2=0\krát 2^0 + 0\krát 2^1 + 0\krát 2^2 + 1\krát 2^3=8\)

Odpoveď: minimálne možné A, ktoré spĺňa podmienky, rovná sa 8.

Jevgenij Smirnov

IT expert, učiteľ informatiky

Riešenie #2

Možno navrhnúť trochu kratší prístup. Označme náš výrok ako F = (A->(B->C)), kde A je výrok „X&25 sa nerovná 0“, B = „X&17=0“ a C = „X&A sa nerovná 0“ “.

Rozvinieme implikácie, pomocou známeho zákona X->Y = nie (X) ALEBO Y dostaneme F = A -> (nie (B) ALEBO C) = nie (A) ALEBO nie (B) ALEBO C. Zapíšeme si aj binárne hodnoty konštánt 25 a 17:

Náš výraz je logickým ALEBO troch výrokov:

1) nie (A) - to znamená X&25 = 0 (bity 0,3,4 z X sú všetky 0)

2) nie (B) – znamená, že X&17 sa nerovná 0 (bity 0 a 4 X aspoň jedna sa rovná 1)

3) C - vie, že X&A sa nerovná 0 (bity špecifikované maskou A, aspoň 1 sa rovná 1)

X je ľubovoľné číslo. Všetky jeho bity sú nezávislé. Preto je možné požadovať splnenie nejakej podmienky na bitoch ľubovoľného čísla len v jednom jedinom prípade - keď hovoríme o rovnakej maske (množine bitov). Môžeme si všimnúť, že binárna maska ​​17 je takmer rovnaká ako 25, chýba len bit číslo 3. Ak by sme teraz doplnili 17 bitom číslo 3, potom by sa výraz (nie (B) OR C) zmenil na nie (nie A ), t.j. v A = (X&25 sa nerovná 0). Iným spôsobom: povedzme A=8 (bit 3=1). Potom je požiadavka (nie (B) B alebo C) ekvivalentná požiadavke: (aspoň jeden z bitov 4,0 sa rovná 1) ALEBO (bit 3 sa rovná 1) = (aspoň jeden z bitov 0, 3,4 sa nerovná 1) - tie. inverzia nie (A) = A = (X&25 sa nerovná 0).

V dôsledku toho sme si všimli, že ak A = 8, potom náš výraz nadobudne tvar F = nie (A) ALEBO A, čo je podľa zákona vylúčeného stredu vždy identicky pravdivé. Pre iné menšie hodnoty A nemožno získať nezávislosť od hodnoty X, pretože Masky vychádzajú rôzne. No, ak sú jedničky v najvýznamnejších bitoch A, nič sa nemení v bitoch nad 4, pretože vo zvyšných maskách máme nuly. Ukazuje sa, že až keď A = 8, vzorec sa zmení na tautológiu pre ľubovoľné X.

Dmitrij Lisin

1. Príklad z demo verzie

(prvopísmenová spoluhláska → spoluhláska druhého písmena) / (predposledná samohláska → samohláska posledného písmena)

1) KRISTÍNA 2) MAXIM 3) ŠTEPÁN 4) MÁRIA

Náčrt riešenia Implikácia a → b je ekvivalentné výrazu ¬a / b.

Prvá implikácia platí pre slová KRISTINA a ŠTEPAN. Druhá implikácia z týchto slov platí len pre slovo CHRISTINE.

Odpoveď: 1. CHRISTINA

2. Ešte dva príklady

Príklad 1 (otvorený segment banky FIPI)

Ktoré z uvedených mien spĺňa logickú podmienku:

(prvá spoluhláska → prvá samohláska) / (posledná samohláska → posledná spoluhláska)

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

Náčrt riešenia. Implikácia a → b je ekvivalentné výrazu ¬a / b. Tento výraz je pravdivý, ak jeden z výrazov a je nepravdivý, alebo oba výrazy a a b sú pravdivé. Keďže v našom prípade v žiadnom z implikácií nemôžu byť pravdivé oba výrazy súčasne, výroky „prvé písmeno je spoluhláska“ a „posledné písmeno je samohláska“ musia byť nepravdivé, to znamená, že potrebujeme slovo, ktorého prvé písmeno je samohláska a posledné je spoluhláska.

odpoveď: 3. ARTEM.

Príklad 2 Pre ktorú z uvedených hodnôt čísla X je tvrdenie pravdivé?

(X< 4)→(X >15)

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

Riešenie. Žiadne číslo nemôže byť zároveň menšie ako 4 a zároveň väčšie ako 15. Preto je implikácia pravdivá iba vtedy, ak je premisa X< 4 falošné.

Odpoveď 4.

2. Problémy vo formáte Jednotnej štátnej skúšky 2013-2014.

2.1. Demo verzia 2013

Na číselnej osi sú dva segmenty: P = a Q = .

Vyberte segment A taký, že vzorec

1) 2) 3) 4)

2.2. Demo verzia 2014

Na číselnej osi sú dva segmenty: P = a Q = . Z navrhnutých segmentov vyberte segment A, ktorý obsahuje logický výraz

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

identicky platí, to znamená, že pre akúkoľvek hodnotu premennej nadobudne hodnotu 1

Možnosti odpovede: 1) 2) 3) 4)

Riešenie. Transformujme výraz pomocou . Máme:

¬((x ∈ P) → ¬ (x ∈ Q)) ∨ (¬ (x ∈ A)) - nahradenie implikácie disjunkciou;

¬(¬(x ∈ P) ∨ ¬ (x ∈ Q)) ∨ (¬ (x ∈ A)) - nahradenie implikácie disjunkciou;

((x ∈ P) ∧ (x ∈ Q)) ∨ (¬ (x ∈ A)) - de Morganovo pravidlo a odstránenie dvojitej negácie;

(x ∈ A) → ((x ∈ P) ∧ (x ∈ Q)) – nahradenie disjunkcie implikáciou

Posledný výraz je identicky pravdivý práve vtedy, ak A ⊆ P∩ Q = ∩ = (pozri ). Zo štyroch daných segmentov túto podmienku spĺňa iba segment - možnosť č. 2.

odpoveď: - možnosť č.2

3. Problémy vo formáte Jednotnej štátnej skúšky 2015-2016.

3.1. Úloha 1.

Na číselnej osi sú dva segmenty: P = a Q = .

Je známe, že hranice segmentu A sú celočíselné body a pre segment A vzorec

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

je identicky pravdivý, to znamená, že má hodnotu 1 pre akúkoľvek hodnotu premennej x.

Aká je najväčšia možná dĺžka segmentu A?

Správna odpoveď : 10

Riešenie:

Transformujme výraz – nahraďte implikáciu disjunkciou. Dostaneme:

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

Výraz ((x ∈ P)) \/ (x ∈ Q) platí len pre tie x, ktoré ležia buď v P alebo v Q, inými slovami, pre x ∈ R = P ∪ Q = ∪ . Výraz

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

platí identicky vtedy a len vtedy, keď A ∈ R. Keďže A je úsečka, potom A ∈ R práve vtedy, keď A ∈ P alebo A ∈ Q. Keďže úsečka Q je dlhšia ako úsečka P, potom najväčšia dĺžka segment A sa dosiahne , keď A = Q = . Dĺžka segmentu A je v tomto prípade 30 – 20 = 10.

3.2. Úloha 2.

Označme podľa m&n bitová konjunkcia nezáporných celých čísel m A n. Takže napríklad 14&5 = 1110 2 &0101 2 = 0100 2 = 4. Aké je najmenšie nezáporné celé číslo A vzorec

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

je identicky pravdivá, t.j. má hodnotu 1 pre akúkoľvek nezápornú celočíselnou hodnotu premennej X?

Správna odpoveď : 57

Riešenie:

Transformujme výraz – nahraďte implikácie disjunkciami. Dostaneme:

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

Otvorme zátvorky a nahraďme negácie nerovností rovnosťami:

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

Máme: 25 = 11 001 2 a 33 = 100 001 2. Preto vzorec

X&25 = 0 ∨ X&33 = 0

nepravda vtedy a len vtedy, ak je binárna reprezentácia čísla X obsahuje 1 aspoň v jednej z nasledujúcich binárnych číslic: 100000 (32), 10000 (16), 1000 (8) a 1.

Aby vzorec (*) bol pravdivý pre všetky takéto X Je potrebné a postačujúce, aby binárna reprezentácia čísla A obsahovala 1 vo všetkých týchto bitoch. Najmenšie takéto číslo je číslo 32+16+8+1 = 57.

učiteľ informatiky na MBOU "Lyceum"

prvej kvalifikačnej kategórii

Murzina Oľga Ivanovna

MBOU "Lýceum" Arzamas

Teória a prax riešenia úlohy 18 Jednotnej štátnej skúšky z informatiky

Arzamas, 2017

Mnemotechnické pravidlo

Jedným z jeho hlavných princípov je dopĺňanie sa k celku (dopĺňanie opakom)

Socionika je informačná psychológia

Vzorec na riešenie

V algebre logiky existuje vzorec pre doplnok celého čísla:

V niektorých úlohách použijeme násobenie protikladov namiesto tohto vzorca:

Typy práce 18

  • Segmentovať úlohy
  • Úlohy na súpravách
  • Úlohy na bitovej konjunkcii
  • Testy deliteľnosti

Segmentovať úlohy

(č. 376) Na číselnej osi sú dva segmenty: P= a Q=. Nájdite najmenšiu možnú dĺžku segmentu A tak, aby vzorec ((x ∈ P) ∧ (x ∈ Q)) → (x ∈ A)

je identicky pravdivý, to znamená, že má hodnotu 1 pre akúkoľvek hodnotu premennej x.

Vzorec na riešenie

má hodnotu 1 pre akúkoľvek hodnotu premennej x.

Riešenie problému segmentu

  • Legenda
  • Formalizácia podmienky
  • Riešenie logickej rovnice

Rozdeľme riešenie problému na etapy:

Riešenie problému segmentu

  • Legenda- to sú pohodlné symboly, ktoré použijeme pri riešení.

    • Predstavme si nasledujúci zápis:

Riešenie problému segmentu

2) Formalizácia podmienky– prepíšme vzorec z úlohy podľa legendy.

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

(P ∧ Q) → A = 1

Riešenie problému segmentu

3) Riešenie logickej rovnice – Spočiatku je to možno najťažšia fáza riešenia problému. Ale neskôr, keď získate skúsenosti, už to nebude také ťažké 

Uvažujme o riešení logickej rovnice krok za krokom.

Riešenie problému segmentu

3.1. Predstavme si logický dôsledok v základných logických operáciách pomocou vzorca: A → B = ¬A  B:

(P ∧ Q) → A = 1

¬(P ∧ Q)  A = 1

Riešenie problému segmentu

A  ¬A = 1 (v algebre logiky platí zákon komutativity, t.j. A  ¬A = ¬A  A):

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

¬A = ¬(P ∧ Q)

Odpoveď v logickej rovnici bude:

Riešenie problému segmentu

.

Naša odpoveď: A = P ∧ Q.

V algebre logiky tento výraz znamená priesečník objemov dvoch logických objektov. Podľa podmienok nášho problému ide o priesečník segmentov P a Q.

Riešenie problému segmentu

Priesečník segmentov P a Q možno vizualizovať: P= a Q=.

Podľa podmienok našej úlohy potrebujeme minimálnu dĺžku segmentu A. Nájdeme ju: 15 – 12 = 3.

Odpoveď na webovej stránke K.Yu Polyakova: 3

Segmentovať úlohy

(č. 360) Na číselnej osi sú tri segmenty: P=, Q= a R=. Aká je maximálna dĺžka segmentu A, pre ktorý platí vzorec ((x ∈ Q) → (x ∉ R)) ∧ (x ∈ A) ∧ (x ∉ P)

je identicky nepravda, to znamená, že má hodnotu 0 pre akúkoľvek hodnotu premennej x?

Zdroj - webová stránka Polyakova K.Yu.

Vzorec na riešenie

Pri výbere vzorca riešenia je dôležité pozorne si prečítať požiadavku na problém.

V našom probléme požiadavka hovorí:

má hodnotu 0 pre akúkoľvek hodnotu premennej x.

Voľba rozhodujúceho vzorca je zrejmá:

Riešenie problému segmentu

  • Legenda
  • Formalizácia podmienky
  • Riešenie logickej rovnice
  • Interpretácia získaného výsledku

Riešenie problému segmentu

  • Legenda

Riešenie problému segmentu

2) Formalizácia podmienky

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

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

Riešenie problému segmentu

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

3.1. Predstavme si logický dôsledok v základných logických operáciách podľa vzorca: A → B = ¬A  B a usporiadajme faktory podľa zákona komutatívneho násobenia:

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

Riešenie problému segmentu

3) Riešenie logickej rovnice

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

3.2. Výsledný výraz zredukujme na rozhodujúci vzorec: A  ¬A = 0 a nájdime, čomu sa ¬A rovná:

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

Riešenie problému segmentu

3) Riešenie logickej rovnice

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

3.3. Zjednodušme výraz pre ¬A podľa de Morganovho zákona ¬A¬B=¬(AB):

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

a podľa iného de Morganovho zákona ¬A¬B=¬(AB):

¬A = ¬ (Q  R  P)

Riešenie problému segmentu

3) Riešenie logickej rovnice

¬A = ¬ (Q  R  P)

3.4. To je zrejmé

A = Q  R  P

Riešenie problému segmentu

4) Interpretácia získaného výsledku

A = Q  R  P

Segment A je priesečník segmentov Q a R a jeho spojenie so segmentom P.

Riešenie problému segmentu

Priesečník segmentov R a Q možno vizualizovať: Q= a R=.

Nakreslíme segment P= na náš výkres a skombinujeme ho s priesečníkom:

Riešenie problému segmentu

Podľa podmienok našej úlohy potrebujeme maximálnu dĺžku segmentu A. Nájdeme ju: 30 – 10 = 20.

A = Q  R  P

Odpoveď na webovej stránke K.Yu Polyakova: 20

2. Úlohy na súpravách

(č. 386) Prvky množín A, P, Q sú prirodzené čísla a P=(1,2,3,4,5,6), Q=(3,5,15). Je známe, že výraz (x ∉ A) → ((x ∉ P) ∧ (x ∈ Q)) ∨ (x ∉ Q)

true (t.j. má hodnotu 1 pre ľubovoľnú hodnotu premennej x. Určte najmenší možný počet prvkov v množine A.

Zdroj - webová stránka Polyakova K.Yu.

Riešenie problému na súpravách

  • Legenda
  • Formalizácia podmienky
  • Riešenie logickej rovnice
  • Interpretácia získaného výsledku

Riešenie problému na súpravách

  • Legenda

Riešenie problému na súpravách

2) Formalizácia podmienky

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

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

Riešenie problému na súpravách

3) Riešenie logickej rovnice

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

3.1. Predstavme si logický dôsledok v základných logických operáciách a zoskupíme ich:

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

Riešenie problému na súpravách

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

3.2. Zredukujme výsledný výraz na rozhodujúci vzorec:

a nájdite, čomu sa ¬A rovná:

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

Riešenie problému na súpravách

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

3.3. Zjednodušme výraz pre ¬A otvorením zátvoriek podľa zákona distributívneho sčítania:

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

¬A = (¬P  ¬Q)

Riešenie problému na súpravách

¬A = (¬P  ¬Q)

Podľa De Morganovho zákona:

¬A = ¬(P  Q)

3.4. To je zrejmé

Riešenie problému na súpravách

4) Interpretácia získaného výsledku

Riešenie problému na súpravách

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

a obsahuje len 2 prvky.

Odpoveď na webovej stránke Polyakov: 2

2. Úlohy na súpravách

(č. 368) Prvky množín A, P, Q sú prirodzené čísla a P=(2,4,6,8,10,12) a Q=(4,8,12,116). Je známe, že výraz (x ∈ P) → (((x ∈ Q) ∧ (x ∉ A)) → (x ∉ P))

true (t. j. má hodnotu 1) pre akúkoľvek hodnotu premennej x. Určte najmenšiu možnú hodnotu súčtu prvkov množiny A.

Zdroj - webová stránka Polyakova K.Yu.

  • Legenda
  • Formalizácia podmienky
  • Riešenie logickej rovnice
  • Interpretácia získaného výsledku

Riešenie problému na súpravách

  • Legenda

Riešenie problému na súpravách

2) Formalizácia podmienky

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

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

Riešenie problému na súpravách

Riešenie problému na súpravách

3) Riešenie logickej rovnice

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

3.1. Predstavme si prvý logický dôsledok (v zátvorke) v základných logických operáciách:

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

Riešenie problému na súpravách

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

Predstavme si druhý logický dôsledok v základných logických operáciách, aplikujme De Morganov zákon a preusporiadajme:

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

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

Riešenie problému na súpravách

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

3.2. Zredukujme výsledný výraz na rozhodujúci vzorec:

a nájdite, čomu sa ¬A rovná:

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

Riešenie problému na súpravách

¬A = ¬P ¬Q  ¬P

3.3. Zjednodušme výraz pre ¬A pomocou vzorca A  A = A:

¬A = ¬(P Q)

Riešenie problému na súpravách

¬A = ¬(P Q)

3.4. To je zrejmé

4) Interpretácia získaného výsledku

Požadovaná množina A je priesečníkom množín P a Q.

Riešenie problému na súpravách

Požadovaná množina A je priesečníkom množín

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

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

a obsahuje len 3 prvky, ktorých súčet je 4+8+12=24.

Odpoveď na webovej stránke Polyakova: 24

(č. 379) Označte podľa m&n bitová konjunkcia nezáporných celých čísel m A n. Takže napríklad 14 & 5 = 11102 & 01012 = 01002 = 4. Aké je najmenšie nezáporné celé číslo A vzorec (x & 29 ≠ 0) → ((x & 12 = 0) → (x & A ≠ 0))

je identicky pravdivá (t. j. má hodnotu 1 pre akúkoľvek nezápornú celočíselnú hodnotu premennej x)?

  • Legenda
  • Formalizácia podmienky
  • Riešenie logickej rovnice
  • Interpretácia získaného výsledku
  • Legenda

    • B = (x & 29 ≠ 0)

    C = (x & 12 ≠ 0)

    A = (x & A ≠ 0)

Riešenie problému bitovej konjunkcie

Inú bitovú spojku ako nulu akceptujeme ako pravdivé tvrdenie, inak bitová spojka stráca logický význam, lebo Vždy môžete reprezentovať X so všetkými nulami.

Riešenie problému bitovej konjunkcie

2) Formalizácia podmienky

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

B → (¬C → A) = 1

Riešenie problému bitovej konjunkcie

3) Riešenie logickej rovnice

B → (¬C → A) = 1

B → (C A) = 1

(¬B  C) A = 1

¬A = ¬B  C

¬A = ¬(B ¬ C)

To je zrejmé

A = B ¬ C

Riešenie problému bitovej konjunkcie

Riešenie problému bitovej konjunkcie

4) Interpretácia získaného výsledku

Riešenie problému bitovej konjunkcie

B = (x & 29 ≠ 0)

B alebo 29 = 111012

C = (x & 12 ≠ 0)

¬С alebo inverzia 12 = 00112

Riešenie problému bitovej konjunkcie

B alebo 29 = 111012

¬С alebo inverzia 12 = 00112

A = B ¬ C

A = 100 012 = 17

Odpoveď na webovej stránke Polyakov: 17

3. Úlohy o bitovej konjunkcii

(č. 375) Predstavme si výraz M & K, ktorý označuje bitovú konjunkciu M a K (logické „AND“ medzi zodpovedajúcimi bitmi binárneho zápisu). Určte najmenšie prirodzené číslo A tak, že výraz (X & 49 ≠ 0) → ((X & 33 = 0) → (X & A ≠ 0))

identicky pravdivé (to znamená, že má hodnotu 1 pre akúkoľvek prirodzenú hodnotu premennej X)?

  • Legenda
  • Formalizácia podmienky
  • Riešenie logickej rovnice
  • Interpretácia získaného výsledku

Riešenie problému bitovej konjunkcie

  • Legenda

    • Legenda pre problémy zahŕňajúce bitové konjunkcie sa líši od všetkých ostatných prípadov:

    B = (x & 49 ≠ 0)

    C = (x & 33 ≠ 0)

    A = (x & A ≠ 0)

Riešenie problému bitovej konjunkcie

2) Formalizácia podmienky

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

B → (¬C → A) = 1

Riešenie problému bitovej konjunkcie

3) Riešenie logickej rovnice

B → (¬C → A) = 1

B → (C  A) = 1

(¬B  C)  A = 1

¬A = (¬B  C)

očividne:

Riešenie problému bitovej konjunkcie

Riešenie problému bitovej konjunkcie

4) Interpretácia získaného výsledku

Požadovaná binárna hodnota bitovej konjunkcie A je binárna hodnota bitovej konjunkcie hodnoty B a prevrátená hodnota binárnej hodnoty C.

Riešenie problému bitovej konjunkcie

B = (x & 49 ≠ 0)

B alebo 49 = 1100012

C = (x & 33 ≠ 0)

¬C alebo inverzia 33 = 0111102

Riešenie problému bitovej konjunkcie

B alebo 49 = 1100012

¬C alebo inverzia 33 = 0111102

A = B ¬ C

011110 2

A = 100 002 = 16

Odpoveď na webovej stránke Polyakov: 16

(č. 372) Označme DEL(n, m) výrok „prirodzené číslo n je bezo zvyšku vydelené prirodzeným číslom m“. Pre aké je najväčšie prirodzené číslo A platí vzorec ¬DIV(x,A) → (¬DIV(x,21) ∧ ¬DIV(x,35))

Zdroj - webová stránka Polyakova K.Yu.

  • Legenda
  • Formalizácia podmienky
  • Riešenie logickej rovnice
  • Interpretácia získaného výsledku

Riešenie problému

na podmienku deliteľnosti

  • Legenda

Riešenie problému

na podmienku deliteľnosti

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

21 = DIV(x.21)

35 = DIV(x,35)

2) Formalizácia podmienky

Riešenie problému

na podmienku deliteľnosti

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

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

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

3) Riešenie logickej rovnice

Riešenie problému

na podmienku deliteľnosti

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

A (¬21 ∧ ¬35) = 1

¬A = ¬21 ∧ ¬35

To je zrejmé

4) Interpretácia získaného výsledku

V tomto probléme ide o najťažšiu etapu riešenia. Musíte pochopiť, čo je číslo A - LOC alebo GCD alebo...

Riešenie problému

na podmienku deliteľnosti

4) Interpretácia získaného výsledku

Naše číslo A je teda také, že X je ním deliteľné bezo zvyšku práve vtedy, ak je X bezo zvyšku deliteľné 21 alebo 35. V tomto prípade hľadáme

A = gcd (21, 35) = 7

Riešenie problému

na podmienku deliteľnosti

Odpoveď na webovej stránke Polyakov: 7

4. Úlohy o podmienke deliteľnosti

(č. 370) Označme DEL(n, m) výrok „prirodzené číslo n je bezo zvyšku vydelené prirodzeným číslom m“. Pre aké je najväčšie prirodzené číslo A platí vzorec ¬DIV(x,A) → ((DIV(x,6) → ¬DIV(x,4))

identicky pravdivé (to znamená, že má hodnotu 1 pre akúkoľvek prirodzenú hodnotu premennej x)?

Zdroj - webová stránka Polyakova K.Yu.

  • Legenda
  • Formalizácia podmienky
  • Riešenie logickej rovnice
  • Interpretácia získaného výsledku

Riešenie problému

na podmienku deliteľnosti

  • Legenda

    • A = DIV(x,A)

Riešenie problému

na podmienku deliteľnosti

2) Formalizácia podmienky

Riešenie problému

na podmienku deliteľnosti

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

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

¬A → (6 → ¬4) = 1

3) Riešenie logickej rovnice

¬A → (6 → ¬4) = 1

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

A  (¬ 6  ¬ 4) = 1

¬A = ¬ 6  ¬4

očividne:

Riešenie problému

na podmienku deliteľnosti

4) Interpretácia získaného výsledku

Takže A je také, že X je ním deliteľné bezo zvyšku vtedy a len vtedy, ak je X bezo zvyšku deliteľné 6 aj 4. To znamená A = LCM(6,4) = 12

Odpoveď na webovej stránke Polyakov: 12

Riešenie problému

na podmienku deliteľnosti

Môžete teraz svojim študentom alebo priateľom vysvetliť riešenie úlohy 18?

(áno, nie, neviem).

Ďakujem za tvoju pozornosť!

SÚVISIACE ČLÁNKY