2 je logická funkcia f daná výrazom x. Logická funkcia F je daná výrazom
Na základe: demo verzií Jednotnej štátnej skúšky z informatiky na rok 2015, podľa učebnice Ludmily Leonidovny Bosovej
V predchádzajúcej časti 1 sme s vami rozoberali logické operácie Disjunkcia a Konjunkcia, ostáva nám už len rozobrať inverziu a prejsť k riešeniu úlohy Jednotná štátna skúška.
Inverzia
Inverzia- logická operácia, ktorá spája každý výrok s novým výrokom, ktorého význam je opačný ako pôvodný.
Na zápis inverzie sa používajú tieto znaky: NOT, `¯`, ` ¬ `
Inverzia je určená nasledujúcou pravdivostnou tabuľkou:
Inverzia sa inak nazýva logická negácia.
Do formulára je možné zapísať akékoľvek zložité vyhlásenie logický výraz— výrazy obsahujúce logické premenné, znamienka logického operátora a zátvorky. Logické operácie v logickom výraze sa vykonávajú v tomto poradí: inverzia, konjunkcia, disjunkcia. Poradie operácií môžete zmeniť pomocou zátvoriek.
Logické operácie majú prioritu: inverzia, konjunkcia, disjunkcia.
A tak je pred nami úloha č.2 z Jednotnej štátnej skúšky z informatiky 2015
Alexandra vypĺňala pravdivostnú tabuľku pre výraz F. Podarilo sa jej vyplniť len malý zlomok tabuľky:
x1 x2 x3 x4 x5 x6 x7 x8 F 0 1 0 1 0 1 1 1 1 Aký výraz môže byť F?
Riešenie problému značne uľahčuje to, že v každej verzii zložitého výrazu F existuje iba jedna logická operácia: násobenie alebo sčítanie. V prípade premnoženia /\ ak sa aspoň jedna premenná rovná nule, potom musí byť nula aj hodnota celého výrazu F. A v prípade sčítania V, ak sa aspoň jedna premenná rovná jednej, potom sa hodnota celého výrazu F musí rovnať 1.
Údaje, ktoré sú v tabuľke pre každú z 8 premenných výrazu F, nám na riešenie úplne stačia.
Skontrolujeme výraz číslo 1:
- ? /\ 1 /\ ? /\ ? /\ ? /\ ? /\ ? /\ 0 )
- z druhého riadku tabuľky x1=1, x4=0 vidíme, že F je možné a môže sa rovnať = 1, ak sa všetky ostatné premenné rovnajú 1 (1 /\ ? /\ ? /\ 1 /\ ? /\ ? /\ ? /\ ? )
- podľa tretieho riadku tabuľky x4=1, x8=1 vidíme, že F=0 (? /\ ? /\ ? /\ 0 /\ ? /\ ? /\ ? /\ 0 ), a v tabuľke máme F=1, čo znamená, že výraz číslo jedna je pre nás URČITE NEVHODNÉ.
Skontrolujeme výraz číslo 2:
- z prvého riadku tabuľky x2=0, x8=1 vidíme, že F je možné a môže sa rovnať = 0, ak sa všetky ostatné premenné rovnajú 0 (? V 0 V ? V ? V ? V ? V ? V 0 )
- z druhého riadku tabuľky x1=1, x4=0 vidíme, že F = 1 ( 1 V ? V ? V 1 V ? V ? V ? V ? )
- podľa tretieho riadku tabuľky x4=1, x8=1 vidíme, že F je možné a môže sa rovnať = 1, ak sa aspoň jedna zo zostávajúcich premenných rovná 1 ( ?
V ?
V ?
V 0
V ?
V ?
V ?
V 0
)
Skontrolujeme výraz číslo 3:
- z prvého riadku tabuľky x2=0, x8=1 vidíme, že F=0 (? /\ 0 /\ ? /\ ? /\ ? /\ ? /\ ? /\ 1 )
- z druhého riadku tabuľky x1=1, x4=0 vidíme, že F =0 (0 /\ ? /\ ? /\ 0 /\ ? /\ ? /\ ? /\ ? ), a v tabuľke máme F=1, čo znamená, že nám dáva výraz číslo tri URČITE NEVHODNÉ.
Skontrolujeme výraz číslo 4:
- z prvého riadku tabuľky x2=0, x8=1 vidíme, že F=1 ( ? V 1 V ? V ? V ? V ? V ? V 0 ), a v tabuľke máme F=0, čo znamená, že nám dáva výraz číslo štyri URČITE NEVHODNÉ.
Pri riešení úlohy na jednotnej štátnej skúške musíte urobiť presne to isté: vyradiť tie možnosti, ktoré na základe údajov v tabuľke rozhodne nevyhovujú. Zostávajúca možná možnosť (ako v našom prípade možnosť číslo 2) bude správnou odpoveďou.
Katalóg úloh.
Počet programov s povinnou etapou
Vykonajte testy na tieto úlohy
Návrat do katalógu úloh
Verzia pre tlač a kopírovanie v MS Word
Performer A16 prevedie číslo napísané na obrazovke.
Účinkujúci má tri tímy, ktoré majú pridelené čísla:
1. Pridajte 1
2. Pridajte 2
3. Vynásobte číslom 2
Prvý z nich zvýši číslo na obrazovke o 1, druhý ho zvýši o 2, tretí ho vynásobí 2.
Program pre účinkujúceho A16 je postupnosť príkazov.
Koľko je programov, ktoré prevedú pôvodné číslo 3 na číslo 12 a zároveň výpočtová cesta programu obsahuje číslo 10?
Výpočtová trajektória programu je sekvencia výsledkov vykonania všetkých príkazov programu. Napríklad pre program 132 s počiatočným číslom 7 bude trajektória pozostávať z čísel 8, 16, 18.
Riešenie.
Požadovaný počet programov sa rovná súčinu počtu programov, ktoré od čísla 3 získajú číslo 10, a počtu programov, ktoré od čísla 10 získajú číslo 12.
Nech R(n) je počet programov, ktoré konvertujú číslo 3 na číslo n, a P(n) je počet programov, ktoré konvertujú číslo 10 na číslo n.
Pre všetky n > 5 platia nasledujúce vzťahy:
1. Ak n nie je deliteľné 2, potom R(n) = R(n - 1) + R(n - 2), keďže existujú dva spôsoby, ako získať n - pripočítaním jednej alebo sčítaním dvoch. Podobne P(n) = P(n - 1) + P(n - 2)
2. Ak je n deliteľné 2, potom R(n) = R(n - 1) + R(n - 2) + R(n / 2). Podobne P(n) = P(n - 1) + P(n - 2) + P(n / 2)
Vypočítajme postupne hodnoty R(n):
R(5) = R(4) + R(3) = 1 + 1 = 2
R(6) = R(5) + R(4) + R(3) = 2 + 1 + 1 = 4
R(7) = R(6) + R(5) = 4 + 2 = 6
R(8) = R(7) + R(6) + R(4) = 6 + 4 + 1 = 11
R(9) = R(8) + R(7) = 11 + 6 = 17
R(10) = R(9) + R(8) + R(5) = 17 + 11 + 2 = 30
Teraz vypočítajme hodnoty P(n):
P(11) = P(10) = 1
P(12) = P(11) + P(10) = 2
Počet programov, ktoré spĺňajú podmienky problému, je teda 30 · 2 = 60.
odpoveď: 60.
odpoveď: 60
Zdroj: Demo verzia Jednotnej štátnej skúšky 2017 z informatiky.
1. Pridajte 1
2. Pridajte 3
Koľko je programov, pre ktoré je vzhľadom na počiatočné číslo 1 výsledkom číslo 17 a zároveň trajektória výpočtu obsahuje číslo 9? Výpočtová trajektória programu je sekvencia výsledkov vykonania všetkých príkazov programu. Napríklad pre program 121 s počiatočným číslom 7 bude trajektória pozostávať z čísel 8, 11, 12.
Riešenie.
Používame metódu dynamického programovania. vytvorme pole dp, kde dp[i] je počet spôsobov, ako získať číslo i pomocou takýchto príkazov.
Dynamická základňa:
Vzorec prechodu:
dp[i]=dp + dp
Toto neberie do úvahy hodnoty pre čísla väčšie ako 9, ktoré možno získať z čísel menších ako 9 (čím sa preskočí trajektória 9):
odpoveď: 169.
odpoveď: 169
Zdroj: Cvičná práca v INFORMAČNEJ VEDE, ročník 11 29. novembra 2016 Možnosť IN10203
Performer May17 prevedie číslo na obrazovke.
Účinkujúci má dva tímy, ktoré majú pridelené čísla:
1. Pridajte 1
2. Pridajte 3
Prvý príkaz zvýši číslo na obrazovke o 1, druhý ho zvýši o 3. Program pre interpreta 17. mája je postupnosť príkazov.
Koľko je programov, pre ktoré je vzhľadom na počiatočné číslo 1 výsledkom číslo 15 a zároveň trajektória výpočtu obsahuje číslo 8? Výpočtová trajektória programu je sekvencia výsledkov vykonania všetkých príkazov programu. Napríklad pre program 121 s počiatočným číslom 7 bude trajektória pozostávať z čísel 8, 11, 12.
Riešenie.
Používame metódu dynamického programovania. Vytvorme pole dp, kde dp[i] je počet spôsobov, ako získať číslo i pomocou takýchto príkazov.
Dynamická základňa:
Vzorec prechodu:
dp[i]=dp + dp
Toto však neberie do úvahy čísla, ktoré sú väčšie ako 8, ale môžeme sa k nim dostať od hodnoty menšej ako 8. Nasledujúce zobrazí hodnoty v bunkách dp od 1 do 15: 1 1 1 2 3 4 6 9 9 9 18 27 36 54 81 .
Zdroj práce: Riešenie 2437. Jednotná štátna skúška 2017. Informatika. V.R. Leschiner. 10 možností.
Úloha 2. Logická funkcia F je daná výrazom . Určte, ktorý stĺpec pravdivostnej tabuľky funkcie F zodpovedá každej z premenných x, y, z.
Vo svojej odpovedi napíšte písmená x, y, z v poradí, v akom sa zobrazujú ich zodpovedajúce stĺpce (najprv - písmeno zodpovedajúce 1. stĺpcu, potom - písmeno zodpovedajúce 2. stĺpcu, potom - písmeno zodpovedajúce 3. stĺpec). Písmená v odpovedi píšte za sebou, medzi písmenami nie je potrebné vkladať žiadne oddeľovače.
Riešenie.
Prepíšme výraz pre F s prihliadnutím na priority operácií negácie, konjunkcie a disjunkcie:
.
Uvažujme 4. riadok tabuľky (1,1,0)=0. Z toho vidíme, že na treťom mieste musí byť buď premenná y alebo premenná z, inak bude druhá zátvorka obsahovať 1, čo povedie k hodnote F=1. Teraz zvážte 5. riadok tabuľky (0,0,1)=1. Keďže x musí byť na prvom alebo druhom mieste, prvá zátvorka dá 1 iba vtedy, keď je y na 3. mieste. Ak vezmeme do úvahy, že druhá zátvorka sa vždy rovná 0, potom F=1 získame vďaka 1 v prvej zátvorke. Zistili sme teda, že y je na 3. mieste. Nakoniec zvážte 7. riadok tabuľky (1,0,1)=0. Tu y=1 a pre F=0 je potrebné mať z=0 a x=1, preto je x na 1. mieste a z je na druhom.
Logická funkcia F je dané výrazom X/\ ¬y/\ (¬z\/ w).
Obrázok ukazuje fragment pravdivostnej tabuľky funkcie F obsahujúce Všetky množiny argumentov, pre ktoré je funkcia F pravda.
Určte, ktorý stĺpec pravdivostnej tabuľky funkcie F každá z premenných zodpovedá w, X, r, z.
Napíšte písmená do odpovede w, X, r, z v poradí, v akom prídu
ich zodpovedajúce stĺpce (prvé – písmeno zodpovedajúce prvému
stĺpec; potom písmeno zodpovedajúce druhému stĺpcu atď.) Písmená
Vo svojej odpovedi píšte do riadku, medzi písmenami nedávajte žiadne oddeľovače.
netreba.
Demo verzia Jednotnej štátnej skúšky USE 2017 – úloha č.2
Riešenie:
Spojka (logické násobenie) je pravdivá vtedy a len vtedy, ak sú pravdivé všetky tvrdenia. Preto premenná X 1 .
Variabilné ¬y musí zodpovedať stĺpcu, v ktorom sú všetky hodnoty rovnaké 0 .
Disjunkcia (logické sčítanie) dvoch tvrdení je pravdivá vtedy a len vtedy, ak je pravdivé aspoň jedno tvrdenie.
Disjunkcia ¬z\/r z=0, w=1.
Teda premenná ¬z w zodpovedá stĺpcu s premennou 4 (stĺpec 4).
Odpoveď: zyxw
Demo verzia Jednotnej štátnej skúšky USE 2016 – úloha č.2
Logická funkcia F je daný výrazom (¬z)/\x \/ x/\y. Určte, ktorý stĺpec pravdivostnej tabuľky funkcie F zodpovedá každej z premenných x, y, z.
Vo svojej odpovedi napíšte písmená x, y, z v poradí, v akom sa zobrazujú ich zodpovedajúce stĺpce (najskôr - písmeno zodpovedajúce 1. stĺpcu; potom - písmeno zodpovedajúce 2. stĺpcu; potom - písmeno zodpovedajúce 3. stĺpec). Písmená v odpovedi píšte za sebou, medzi písmenami nie je potrebné vkladať žiadne oddeľovače.
Príklad. Nech je daný výraz x → y v závislosti od dvoch premenných x a y a pravdivostnej tabuľky:
Potom 1. stĺpec zodpovedá premennej y a 2. stĺpec
zodpovedá premennej x. V odpovedi je potrebné napísať: yx.
Riešenie:
1. Daný výraz napíšme v jednoduchšom zápise:
¬z*x + x*y = x*(¬z + y)
2. Konjunkcia (logické násobenie) je pravdivá vtedy a len vtedy, ak sú pravdivé všetky tvrdenia. Preto, aby funkcia ( F) sa rovnala jednej ( 1 ), každý faktor sa musí rovnať jednému ( 1 ). Teda kedy F=1, variabilný X musí zodpovedať stĺpcu, v ktorom sú všetky hodnoty rovnaké 1 .
3. Zvážte (¬z + y), o F=1 tento výraz sa tiež rovná 1 (pozri bod 2).
4. Disjunkcia (logické sčítanie) dvoch tvrdení je pravdivá vtedy a len vtedy, ak je pravdivé aspoň jedno tvrdenie.
Disjunkcia ¬z\/r v tomto riadku bude pravdivé iba vtedy, ak
- z = 0; y = 0 alebo y = 1;
- z = 1; y = 1
5. Teda premenná ¬z zodpovedá stĺpec s premennou 1 (1 stĺpec), premenná r
Odpoveď: zyx
Jednotná štátna skúška KIM Jednotná štátna skúška 2016 (skoré obdobie)– úloha č.2
Logická funkcia F je daná výrazom
(x /\ y /\¬z) \/ (x /\ y /\ z) \/ (x /\¬y /\¬z).
Obrázok ukazuje fragment pravdivostnej tabuľky funkcie F, ktorá obsahuje všetky množiny argumentov, pre ktoré je funkcia F pravdivá. Určte, ktorý stĺpec pravdivostnej tabuľky funkcie F zodpovedá každej z premenných x, y, z.
Vo svojej odpovedi napíšte písmená x, y, z v poradí, v akom sa zobrazujú ich zodpovedajúce stĺpce (najskôr - písmeno zodpovedajúce prvému stĺpcu; potom - písmeno zodpovedajúce druhému stĺpcu atď.) Písmená napíšte do odpoveď v rade, bez oddeľovačov Nie je potrebné ju vkladať medzi písmená.
R Riešenie:
Napíšme daný výraz v jednoduchšom zápise:
(x*y*¬z) + (x*y*z) + (x*¬y*¬z)=1
Tento výraz je pravdivý, keď sa aspoň jeden z (x*y*¬z), (x*y*z), (x*¬y*¬z) rovná 1. Konjunkcia (logické násobenie) je pravdivá vtedy a len vtedy, keď všetky tvrdenia sú pravdivé.
Aspoň jedna z týchto disjunkcií x*y*¬z; x*y*z; x*¬y*¬z bude pravda, len ak x=1.
Teda premenná X zodpovedá stĺpcu s premennou 2 (stĺpec 2).
Nechaj y- premenná 1, z- prem.3. Potom v prvom prípade x*¬y*¬z bude to pravda v druhom prípade x*y*¬z a v treťom x*y*z.
odpoveď: yxz
Symbol F označuje jeden z nasledujúcich logických výrazov z troch argumentov: X, Y, Z. Je daný fragment pravdivostnej tabuľky výrazu F (pozri tabuľku vpravo). Ktorý výraz sa zhoduje s F?
X | Y | Z | F |
0 | 0 | 0 | 0 |
1 | 0 | 1 | 1 |
0 | 1 | 0 | 1 |
1) X ∧ Y ∧ Z 2) ¬X ∨ Y ∨¬Z 3) X ∧ Y ∨ Z 4) X ∨ Y ∧ ¬Z
Riešenie:
1) X ∧ Y ∧ Z = 1,0,1 = 0 (nezhoduje sa v 2. riadku)
2) ¬X ∨ Y ∨¬Z = ¬0 ∨ 0 ∨ ¬0 = 1+0+1 = 1 (nezhoduje sa v 1. riadku)
3) X ∧ Y ∨ Z = 0,1+0 = 0 (nezhoduje sa na 3. riadku)
4) X ∨ Y ∧ ¬Z (zodpovedá F)
X ∨ Y ∧ ¬Z = 0 ∨ 0 ∧ ¬0 = 0+0,1 = 0
X ∨ Y ∧ ¬Z = 1 ∨ 0 ∧ ¬1 = 1+0,0 = 1
X ∨ Y ∧ ¬Z = 0 ∨ 1 ∧ ¬0 = 0+1,1 = 1
odpoveď: 4
Je daný fragment pravdivostnej tabuľky výrazu F. Ktorý výraz zodpovedá výrazu F?
A | B | C | F |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 1 |
1) (A → ¬B) ∨ C 2) (¬A ∨ B) ∧ C 3) (A ∧ B) → C 4) (A ∨ B) → C
Riešenie:
1) (A → ¬B) ∨ C = (1 → ¬0) ∨ 0 = (1 → 1) + 0 = 1 + 0 = 1 (nezhoduje sa v 2. riadku)
2) (¬A ∨ B) ∧ C = (¬1 ∨ 0) ∧ 1 = (0+0).1 = 0 (nezhoduje sa v 3. riadku)
3) (A ∧ B) → C = (1 ∧ 0) → 0 = 0 → 0 = 1 (nezhoduje sa v 2. riadku)
4) (A ∨ B) → C (zodpovedá F)
(A ∨ B) → C = (0 ∨ 1) → 1 = 1
(A ∨ B) → C = (1 ∨ 0) → 0 = 0
(A ∨ B) → C = (1 ∨ 0) → 1 = 1
odpoveď: 4
Je daný logický výraz, ktorý závisí od 6 logických premenných:
X1 ∨ ¬X2 ∨ X3 ∨ ¬X4 ∨ X5 ∨ X6
Koľko rôznych sád premenných hodnôt existuje, pre ktoré je výraz pravdivý?
1) 1 2) 2 3) 63 4) 64
Riešenie:
Nesprávny výraz iba v 1 prípade: X1=0, X2=1, X3=0, X4=1, X5=0, X6=0
X1 ∨ ¬X2 ∨ X3 ∨ ¬X4 ∨ X5 ∨ X6 = 0 ∨ ¬1 ∨ 0 ∨ ¬1 ∨ 0 ∨ 0 = 0
Celkovo je 2 6 = 64 možností, čo znamená pravda
odpoveď: 63
Je daný fragment pravdivostnej tabuľky výrazu F.
x1 | x2 | x3 | x4 | x5 | x6 | x7 | F |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
Ktorý výraz sa zhoduje s F?
1) x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ x6 ∨ ¬x7
2) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ x7
3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7
4) x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7
Riešenie:
1) x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ x6 ∨ ¬x7 = 0 + 1 + … = 1 (nezhoduje sa v 1. riadku)
2) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ x7 = 0 + 0 + 0 + 0 + 0 + 1 + 0 = 1 (nezhoduje sa v 1. riadku)
3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7 = 1,0. ...= 0 (nezhoduje sa v 2. riadku)
4) x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 (zodpovedá F)
x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 = 1.1.1.1.1.1.1 = 1
x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 = 0. … = 0
odpoveď: 4
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | F |
0 | 1 | 1 | ||||||
1 | 0 | 1 | 0 | |||||
1 | 0 | 1 |
Aký výraz môže byť F?
1) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8
2) ¬x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ x8
3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8
4) ¬x1 ∨ ¬x2 ∨ ¬x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x8
Riešenie:
1) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8 = x1 . ¬x2. 0 ... = 0 (nezhoduje sa v 1. riadku)
2) ¬x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ x8 (zodpovedá F)
3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8 = … ¬x7 ∧ ¬x8 = … ¬1 ∧ ¬ 8 nezhoduje sa = 0 01 - tý riadok)
4) ¬x1 ∨ ¬x2 ∨ ¬x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x7 ∨ ¬x8 = ¬x1 ∨ ¬x2 ∨ ¬x2 ∨ ¬x 1 ... = ¬x 2.∨ = (nie zápasy v 2. riadku)
odpoveď: 2
Daný je fragment pravdivostnej tabuľky pre výraz F:
x1 | x2 | x3 | x4 | x5 | x6 | x7 | F |
0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 |
Nájdite minimálny možný počet rôznych riadkov v úplnej pravdivostnej tabuľke tohto výrazu, v ktorej sa hodnota x5 zhoduje s F.
Riešenie:
Minimálny možný počet samostatných riadkov, v ktorých x5 zodpovedá F = 4
odpoveď: 4
Daný je fragment pravdivostnej tabuľky pre výraz F:
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | F |
0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
Nájdite maximálny možný počet odlišných riadkov v úplnej pravdivostnej tabuľke tohto výrazu, v ktorej sa hodnota x6 nezhoduje s F.
Riešenie:
Maximálny možný počet = 2 8 = 256
Maximálny možný počet rôznych riadkov, v ktorých sa hodnota x6 nezhoduje F = 256 – 5 = 251
odpoveď: 251
Daný je fragment pravdivostnej tabuľky pre výraz F:
x1 | x2 | x3 | x4 | x5 | x6 | x7 | F |
0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 |
Nájdite maximálny možný počet rôznych riadkov úplnej pravdivostnej tabuľky tohto výrazu, v ktorom sa hodnota ¬x5 ∨ x1 zhoduje s F.
Riešenie:
1+0=1 – nezhoduje sa s F
0+0=0 – nezhoduje sa s F
0+0=0 – nezhoduje sa s F
0+1=1 – zhoduje sa s F
1+0=1 – zhoduje sa s F
2 7 = 128 – 3 = 125
odpoveď: 125
Každý booleovský výraz A a B závisí od rovnakej množiny 6 premenných. V pravdivostných tabuľkách má každý z týchto výrazov v stĺpci hodnoty práve 4 jednotky. Aký je minimálny možný počet jednotiek v stĺpci hodnôt pravdivostnej tabuľky výrazu A ∨ B?
Riešenie:
odpoveď: 4
Každý booleovský výraz A a B závisí od rovnakej množiny 7 premenných. V pravdivostných tabuľkách má každý z týchto výrazov v stĺpci hodnoty práve 4 jednotky. Aký je maximálny možný počet jednotiek v stĺpci hodnôt pravdivostnej tabuľky výrazu A ∨ B?
Riešenie:
odpoveď: 8
Každý booleovský výraz A a B závisí od rovnakej množiny 8 premenných. V pravdivostných tabuľkách má každý z týchto výrazov v stĺpci hodnoty presne 5 jednotiek. Aký je minimálny možný počet núl v stĺpci hodnôt pravdivostnej tabuľky výrazu A ∧ B?
Riešenie:
2 8 = 256 – 5 = 251
odpoveď: 251
Každý booleovský výraz A a B závisí od rovnakej množiny 8 premenných. V pravdivostných tabuľkách má každý z týchto výrazov v stĺpci hodnoty presne 6 jednotiek. Aký je maximálny možný počet núl v stĺpci hodnôt pravdivostnej tabuľky výrazu A ∧ B?
Riešenie:
odpoveď: 256
Každý z boolovských výrazov A a B závisí od rovnakej množiny 5 premenných. V pravdivostných tabuľkách oboch výrazov nie sú žiadne zodpovedajúce riadky. Koľko jednotiek bude obsiahnutých v stĺpci hodnôt pravdivostnej tabuľky výrazu A ∧ B?
Riešenie:
V pravdivostných tabuľkách oboch výrazov nie sú žiadne zodpovedajúce riadky.
odpoveď: 0
Každý z boolovských výrazov A a B závisí od rovnakej množiny 6 premenných. V pravdivostných tabuľkách oboch výrazov nie sú žiadne zodpovedajúce riadky. Koľko jednotiek bude obsiahnutých v stĺpci hodnôt pravdivostnej tabuľky výrazu A ∨ B?
Riešenie:
odpoveď: 64
Každý z booleovských výrazov A a B závisí od rovnakej množiny 7 premenných. V pravdivostných tabuľkách oboch výrazov nie sú žiadne zodpovedajúce riadky. Aký je maximálny možný počet núl v stĺpci hodnôt pravdivostnej tabuľky výrazu ¬A ∨ B?
Riešenie:
A=1,B=0 => ¬0 ∨ 0 = 0 + 0 = 0
odpoveď: 128
Každý z boolovských výrazov F a G obsahuje 7 premenných. V pravdivostných tabuľkách výrazov F a G je presne 8 rovnakých riadkov a práve 5 z nich má v stĺpci hodnoty 1. Koľko riadkov pravdivostnej tabuľky pre výraz F ∨ G obsahuje 1 v stĺpci hodnoty ?
Riešenie:
Existuje presne 8 rovnakých riadkov a presne 5 z nich má v stĺpci hodnoty 1.
To znamená, že práve 3 z nich majú v stĺpci hodnoty 0.
odpoveď: 125
Logická funkcia F je daná výrazom (a ∧ ¬c) ∨ (¬b ∧ ¬c). Určte, ktorý stĺpec pravdivostnej tabuľky funkcie F zodpovedá každej z premenných a, b, c.
? | ? | ? | F |
0 | 0 | 0 | 1 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 0 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 0 |
Vo svojej odpovedi napíšte písmená a, b, c v poradí, v akom sa zobrazujú príslušné stĺpce.
Riešenie:
(a . ¬c) + (¬b . ¬c)
Keď c je 1, F je nula, takže posledný stĺpec je c.
Na určenie prvého a druhého stĺpca môžeme použiť hodnoty z 3. riadku.
(a . 1) + (¬b . 1) = 0
Odpoveď: ABC
Logická funkcia F je daná výrazom (a ∧ c)∨ (¬a ∧ (b ∨ ¬c)). Určte, ktorý stĺpec pravdivostnej tabuľky funkcie F zodpovedá každej z premenných a, b, c.
Na základe skutočnosti, že keď a=0 a c=0, potom F=0 a údaje z druhého riadku, môžeme usúdiť, že tretí stĺpec obsahuje b.
Odpoveď: kabína
Logická funkcia F je daná x ∧ (¬y ∧ z ∧ ¬w ∨ y ∧ ¬z). Obrázok ukazuje fragment pravdivostnej tabuľky funkcie F, ktorá obsahuje všetky množiny argumentov, pre ktoré je funkcia F pravdivá. Určte, ktorý stĺpec pravdivostnej tabuľky funkcie F zodpovedá každej z premenných x, y, z, w.
? | ? | ? | ? | F |
0 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 0 | 1 |
1 | 1 | 0 | 1 | 1 |
Vo svojej odpovedi napíšte písmená x, y, z, w v poradí, v akom sa zobrazujú príslušné stĺpce.
Riešenie:
x ∧ (¬y ∧ z ∧ ¬w ∨ y ∧ ¬z)
X. (¬y . z . ¬w . y . ¬z)
Na základe skutočnosti, že pri x=0, potom F=0, môžeme usúdiť, že druhý stĺpec obsahuje X.
Odpoveď: wxzy
Analýza úlohy 2 Jednotnej štátnej skúšky 2017 z informatiky z projektu demo verzie. Toto je úloha základnej úrovne obtiažnosti. Približný čas na dokončenie úlohy sú 3 minúty.
Testované prvky obsahu: schopnosť zostavovať pravdivostné tabuľky a logické obvody. Prvky obsahu testované na skúške Unified State: výroky, logické operácie, kvantifikátory, pravdivosť výrokov.
Úloha 2:
Logická funkcia F je dané výrazom X /\¬ r /\ (¬ z \/ w).
Obrázok ukazuje fragment pravdivostnej tabuľky funkcie F obsahujúce Všetky F pravda.
Určte, ktorý stĺpec pravdivostnej tabuľky funkcie F každá z premenných zodpovedá w, X, r, z.
Napíšte písmená do odpovede w, x, y, z v poradí, v akom sa zobrazujú príslušné stĺpce (najskôr - písmeno zodpovedajúce prvému stĺpcu; potom - písmeno zodpovedajúce druhému stĺpcu atď.) Písmená v odpovedi napíšte do radu, nie je potrebné uvádzať žiadne oddeľovače medzi písmenami.
Príklad. Ak by bola funkcia daná výrazom ¬ X \/ r v závislosti od dvoch premenných: X A r a bol daný fragment jeho pravdivostnej tabuľky, ktorý obsahuje Všetky množiny argumentov, pre ktoré je funkcia F pravda.
Potom by prvý stĺpec zodpovedal premennej r a druhý stĺpec je premenná X. V odpovedi malo byť napísané: yx.
Odpoveď: ________
X /\¬ r /\ (¬ z \/ w)
Spojka (logické násobenie) je pravdivá vtedy a len vtedy, ak sú pravdivé všetky tvrdenia. Preto premenná X 1 .
Teda premenná X zodpovedá stĺpcu s premennou 3.
Variabilné ¬y stĺpec obsahujúci hodnotu sa musí zhodovať 0 .
Disjunkcia (logické sčítanie) dvoch tvrdení je pravdivá vtedy a len vtedy, ak je pravdivé aspoň jedno tvrdenie.
Disjunkcia ¬z\/w v tomto riadku bude pravdivé iba vtedy, ak z=0, w=1.
Teda premenná ¬z zodpovedá stĺpec s premennou 1 (1 stĺpec), premenná w zodpovedá stĺpcu s premennou 4 (stĺpec 4).