Belová T.V.
ako naučiť riešiť úlohu 18 Jednotnej štátnej skúšky z informatiky
mestská rozpočtová vzdelávacia inštitúcia "Lýceum",
Arzamas, áno. bellova. tatiana@ yandex. ru
Skôr ako začnete riešiť úlohy 18 „Kontrola pravdivosti logického vyjadrenia“ skúšobnej práce z informatiky, musíte študentom vysvetliť (alebo si zapamätať), čo je pojem „zjednotenie“ a „priesečník“ niekoľkých množín. A keďže úloha 18 súvisí s definíciou segmentov, je najlepšie vysvetliť tieto pojmy na segmentoch. Je však potrebné spojiť tieto pojmy s pojmami logickej algebry - „konjunkcia“ a „disjunkcia“ a, samozrejme, „inverzia“. Uvediem príklad. Najprv uvažujme o inverzii segmentu alebo, jednoduchšie, o negácii segmentu.
Je daný segment P=. Nájdite segmenty, ktoré budú inverzné k segmentu P=. Zoberme si súradnicovú čiaru (obr. 1):
ryža. 1
Na priamke označíme segment P (modrá plocha), potom je jasné, že intervaly nie P budú intervaly a (zelená plocha) - Obr. 1. Venujte pozornosť skutočnosti, že body 6 a 15 nebudú zahrnuté do inverzie segmentu.
Uvažujme o ďalšom príklade: sú uvedené dva segmenty P= a Q= (uvedené sú rovnaké zápisy ako v úlohe Jednotná štátna skúška, aby si študenti okamžite zvykli na zápisy). Nájdite segment, ktorý bude označovať spojenie (zjednotenie) a disjunkciu (priesečník) týchto segmentov
Na súradnicovú čiaru nakreslíme segmenty (obr. 2):
ryža. 2
Najprv si na súradnicovej čiare označíme oblasti, ktoré predstavujú segmenty P (modrá) a Q (žltá). Potom určíme, ktorá časť súradnicovej čiary bude slúžiť ako spojenie týchto dvoch segmentov. Tu si pamätáme, že konjunkcia je logická operácia, ktorá spája dva jednoduché výroky do zložitého pomocou logického spojovacieho výrazu „a“ a komplexný výrok nadobudne význam „pravda“ vtedy a len vtedy, ak sú pravdivé oba pôvodné jednoduché výroky. Zistili sme teda, že musíme nájsť oblasti, kde existuje segment P aj segment Q a existuje iba jeden takýto región - segment (červený). Budeme študovať všetky priame segmenty podrobnejšie, aby študenti mohli jasnejšie a pochopili materiál, takže:
Teraz sa pozrime na disjunkciu týchto segmentov podobným spôsobom. Vráťme sa opäť k definícii tejto logickej operácie – „disjunkcia je logická operácia, ktorá v súlade s dvoma alebo viacerými logickými výrokmi vkladá nový, ktorý je pravdivý vtedy a len vtedy, ak je aspoň jeden zo vstupných počiatočných výrokov pravda.“ Inými slovami, potrebujeme nájsť intervaly na súradnicovej čiare, kde je aspoň jeden z našich pôvodných segmentov, tento požadovaný interval bude zelený (obr. 2). Budeme tiež analyzovať každý z intervalov a ukážeme, že je to skutočne tak:
Kombináciou nájdených intervalov dostaneme, že požadovaným segmentom, označujúcim disjunkciu pôvodných segmentov, je segment - zelený (obr. 2).
Po analýze tohto príkladu môžete nechať študentov, aby sa pokúsili nájsť rôzne kombinácie logických operácií – disjunkciu, konjunkciu a negáciu. Napríklad, ak sú dané dva segmenty P=[-4,10] a Q=. Nájdite segment, ktorý bude označovať nasledujúce logické operácie: , , (môžete vymyslieť rôzne iné kombinácie týchto logických operácií).
ryža. 3
ryža. 4
ryža. 5
Po rozbore všetkých príkladov nebudú mať študenti problém s pochopením a riešením úlohy č. 18 zo skúšobnej práce jednotnej štátnej skúšky z informatiky.
Tu sú príklady riešení niekoľkých úloh:
Na číselnej osi sú dva segmenty: P = a Q =. Vyberte segment A taký, že vzorec
(X A) → ((X P) → (X Q)) je identicky pravdivý, to znamená, že má hodnotu 1 pre akúkoľvek hodnotu premennej X. Možné odpovede:
1) 2) 3) 4)
Riešenie (obr. 6): pre zjednodušenie pochopenia výrazu označme jednotlivé výroky písmenami - A: X A,P: X P,Q: X Q. Takto získame nasledujúci výraz berúc do úvahy nahradenie: → ( P→ )=1. Rovnosť výrazu 1 znamená, že nech je hodnota premennej akákoľvek X nezobrali sme, náš logický výraz má hodnotu 1, teda na celej číselnej osi. Spomeňme si na niektoré logické zákony a rovnosti a transformujme svoj výraz: =1. Výsledkom je, že musíme zostrojiť disjunkciu troch segmentov, z ktorých dva sú nám známe. Postavíme ich (obr. 7). Na začiatok, ako vo všetkých vyššie uvedených príkladoch, musíme zostrojiť inverzie segmentov P (oranžová) a Q (červená). Potom z celého výrazu môžeme určiť disjunkčné intervaly =1 (zelené plochy na obr. 7). Tak zistíme, že na súradnicovej čiare máme „voľnú“ časť - . Táto časť je rovná a musí prekrývať požadovaný segment A.
Na vyriešenie tohto problému budeme musieť urobiť niekoľko logických záverov, takže „pozor na ruky“.
- Chcú, aby sme našli minimálne nezáporné celé číslo A, pre ktoré je výraz vždy pravdivý.
- Aký je výraz ako celok? Niečo tam je implikácia v zátvorkách je niečo.
- Pripomeňme si pravdivostnú tabuľku pre implikáciu:
1 => 1 = 1
1 => 0 = 0
0 => 1 = 1
0 => 0 = 1 - 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“.
- Namiesto hľadania A skúsme nájsť x, pre ktoré je tento výraz nepravdivý.
- 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ý)!
- Týmto spôsobom môžeme získať určité obmedzenia na číslo A.
- Takže, poďme späť a spomeňme si, keď je implikácia nepravdivá? Keď je prvá časť pravdivá a druhá časť je nepravdivá.
- Prostriedky
\((\mathrm(x)\&25\neq 0)= 1 \\ (\mathrm(x)\&17=0\Šípka doprava \mathrm(x)\&\mathrm(A)\neq 0) = 0\) - Čo to znamená, že \((x\&25\neq 0) = 1\) ? To znamená, že skutočne \(\mathrm(x)\&25\neq 0\) .
- Prevedieme 25 na binárne. Dostávame: 11001 2 .
- 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!
- To znamená, že číslo x aspoň v jednom krížiku musí obsahovať jednotku: XXXXXX.
- Skvelé, teraz sa pozrime na druhý faktor: \((\mathrm(x)\&17=0\šípka doprava \mathrm(x)\&\mathrm(A)\neq 0) = 0\)
- Tento výraz tiež predstavuje implikáciu. Navyše je rovnako falošný.
- To znamená, že jeho prvá časť musí byť pravdivá a druhá musí byť nepravdivá.
- Prostriedky
\((\mathrm(x)\&17=0) = 1 \\ ((\mathrm(x)\&\mathrm(A)\neq 0) = 0) = 0\) - Č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).
- 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.
- Ale prestaň, v bode 13 sme to konečne dostali ALEBO o 4 od konca ALEBO 5 od konca by mala byť jedna.
- 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.
- 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.
- Skvelé, teraz zvážte poslednú podmienku: \((\mathrm(x)\&\mathrm(A)\neq 0) = 0\). Čo to znamená?
- To znamená, že to nie je pravda \(\mathrm(x)\&\mathrm(A)\neq 0\).
- To je v skutočnosti \(\mathrm(x)\&\mathrm(A)=0\) .
- Č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.
- 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.
- To znamená, že táto posledná podmienka jednoducho nesmie byť splnená.
- Ako sa to nedá naplniť? Len keby sme si boli 100% istí, že pri bitovej konjunkcii niekde zostane jednotka.
- 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.
- Aké je najmenšie možné binárne číslo s 1 na 4. konci? Samozrejme, 1000 2. Takže toto číslo bude odpoveďou.
- 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
Úloha 18 Katalóg úloh. Logické tvrdenia
1. Úloha 18 č.701. Pre ktoré meno je tvrdenie nepravdivé:
(Prvé písmeno mena je samohláska→ Štvrté písmeno mena je spoluhláska).
1) ELENA
2) VADIM
3) ANTON
4) FEDOR
Vysvetlenie.
Implikácia je nepravdivá vtedy a len vtedy, ak je premisa pravdivá a dôsledok je nepravdivý. V našom prípade - ak prvé písmeno mena je samohláska a štvrté písmeno je samohláska. Meno Anton túto podmienku spĺňa.
Poznámka.
Rovnaký výsledok vyplýva z nasledujúcich transformácií: ¬ (A→ B) = ¬ (¬ A∨ B) = A∧ (¬B).
Správna odpoveď je uvedená pod číslom 3.
2. Úloha 18 č.8666. Na číselnej osi sú dva segmenty: P = a Q = . Uveďte najväčšiu možnú dĺžku intervalu A, pre ktorý platí vzorec
(¬(xA)→ (XP))→ ((XA)→ (XQ))
je identicky pravdivý, to znamená, že má hodnotu 1 pre akúkoľvek hodnotu premennej x.
Vysvetlenie.
Transformujme tento výraz:
(¬ ( XA) → ( X P)) → (( X A) → ( XQ))
((XA)∨ (X P))→ ((X nie A)∨ (X Q))
¬(( XpatriloA) ∨ ( XpatriloP)) ∨ (( X nepatrilA) ∨ ( X patriloQ))
( XnepatrilA) ∧ ( XnepatrilP) ∨ ( X patriloA) ∨ ( X nepatrilQ)
( XnepatrilA) ∨ ( X patriloQ)
Teda buď x musí patriť do Q, alebo nepatrí do A. To znamená, že na dosiahnutie pravdy pre všetky x musí byť A úplne obsiahnuté v Q. Potom maximum, ktorým sa môže stať, je všetko Q, teda dĺžka 15 .
3. Úloha 18 č.9170. Na číselnej osi sú dva segmenty: P = a Q = .
Uveďte najväčšiu možnú dĺžku segmentu A, pre ktorý platí vzorec
((XA)→ ¬(xP))→ ((XA)→ (XQ))
identicky platí, to znamená, že pre akúkoľvek hodnotu premennej nadobudne hodnotu 1X .
Vysvetlenie.
Transformujme tento výraz.
(( X€ A) → ¬( XpatriloP)) → (( X patriloA) → ( X patriloQ))
(( XnepatrilA) ∨ ( XnepatrilP)) → (( X nepatrilA) ∨ ( X patriloQ))
¬((x nepatrilo do A)∨ (Xnepatril P))∨ ((Xnepatril do A)∨ (Xpatril Q))
Je pravda, že A∧ B∨ ¬A = ¬A∨ B. Keď to použijeme tu, dostaneme:
(x patrí do P)∨ (Xnepatril do A)∨ (x patrí do Q)
To znamená, že buď bod musí patriť do Q, alebo musí patriť do P, alebo nepatrí do A. To znamená, že A môže pokryť všetky body, ktoré pokrývajú P a Q. To znamená, že A = P Q = = . |A| = 48 - 10 = 38.
4. Úloha 18 č.9202. 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
((XA)→ (XP))∨ (¬(xQ)→ ¬(xA))
true (t. j. má hodnotu 1) pre akúkoľvek hodnotu premennej x.
5. Úloha 18 č.9310. Prvky množín A, P, Q sú prirodzené čísla, pričom P = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20), Q = (5, 10, 15, 20, 25, 30, 35, 40, 45, 50).
Je známe, že výraz
((XA)→ (XP))∨ (¬(xQ)→ ¬(xA))
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.
6. Úloha 18 č.9321. Označme podľaDEL ( n, m ) výrok „prirodzené číslo n je deliteľné prirodzeným číslom bezo zvyškum " Pre aké je najväčšie prirodzené čísloA vzorec
¬ DEL ( x, A ) → (¬ DEL ( X , 21) ∧ ¬ DEL ( X , 35))
je identicky pravdivá (to znamená, že má hodnotu 1 pre akúkoľvek prirodzenú hodnotu premennejX )?
(Zadanie od M. V. Kuznecovovej)
7. Úloha 18 č.9768. Označme podľa m & n m A n 2 & 0101 2 = 0100 2 A vzorec
X & 29 ≠ 0 → (X & 12 = 0 → X & A ≠ 0)
je identicky pravdivá (to znamená, že má hodnotu 1 pre akúkoľvek nezápornú celočíselnú hodnotu premennej X )?
8. Úloha 18 č.9804. Označme podľa m & n bitová konjunkcia nezáporných celých čísel m A n . Napríklad 14 a 5 = 1110 2 & 0101 2 = 0100 2 = 4. Aké je najmenšie nezáporné celé číslo A vzorec
X & 29 ≠ 0 → (X & 17 = 0 → X & A ≠ 0)
je identicky pravdivá (t. j. má hodnotu 1 pre akúkoľvek nezápornú celočíselnú hodnotu premennej X )?
9. Úloha 18 č.723. Pre ktoré meno je pravdivé tvrdenie:
Samohláska tretieho písmena→ ¬ (Prvé písmeno je spoluhláska \/ V slove sú 4 samohlásky)?
1) Rimma
2) Anatolij
3) Svetlana
4) Dmitrij
Vysvetlenie.
Aplikujme implikačnú transformáciu:
Spoluhláska tretieho písmena∨ (Prvé písmeno samohláska∧ Slovo NEMÁ 4 samohlásky)
Disjunkcia je pravdivá, keď je pravdivé aspoň jedno tvrdenie. Preto je vhodná iba možnosť 1.
10. Úloha 18 č.4581. Ktoré z uvedených mien spĺňa logickú podmienku:
(prvé písmeno je spoluhláska→ posledné písmeno je spoluhláska) /\ (prvé písmeno je samohláska→ je posledné písmeno samohláska)?
Ak existuje niekoľko takýchto slov, uveďte najdlhšie z nich.
1) ANNA
2) BELLA
3) ANTON
4) BORIS
Vysvetlenie.
Logické a je pravdivé iba vtedy, ak sú pravdivé oba výroky.(1)
Implikácia je nepravdivá iba vtedy, ak pravda implikuje lož.(2)
Možnosť 1 vyhovuje všetkým podmienkam.
Možnosť 2 nie je vhodná z dôvodu podmienky (2).
Možnosť 3 nie je vhodná z dôvodu podmienky (2).
Možnosť 4 vyhovuje všetkým podmienkam.
Musí byť špecifikované najdlhšie slovo, preto je odpoveď 4.
Úlohy na samostatné riešenie
1. Úloha 18 č.711. Ktorý z uvedených názvov krajín spĺňa nasledujúcu logickú podmienku: ((posledná spoluhláska) \/ (súhláska prvého písmena))→ (názov obsahuje písmeno "p")?
1) Brazília
2) Mexiko
3) Argentína
4) Kuba
2. Úloha 18 č.709. Ktoré z uvedených mien spĺňa logickú podmienku:
(prvé písmeno je samohláska)∧ ((Štvrté písmeno spoluhlásky)∨ (Slovo má štyri písmená))?
1) Sergej
2) Vadim
3) Anton
4) Iľja
№3
№4 
№5. Úloha 18 č.736. Ktoré z uvedených mien spĺňa logickú podmienku
Prvé písmeno je samohláska∧ Štvrté písmeno je spoluhláska∨ Sú v slove štyri písmená?
1) Sergej
2) Vadim
3) Anton
4) Iľja
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
- Úlohy segmentov
- Úlohy na súpravách
- Úlohy na bitovej konjunkcii
- Testy deliteľnosti
Úlohy segmentov
(č. 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
Úlohy segmentov
(č. 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=¬(AB):
¬A = ¬ (Q R) ∧ ¬ P,
a podľa iného de Morganovho zákona ¬A¬B=¬(AB):
¬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ť!
