Rozbor 2 úloh skúšky v roku 2017 z informatiky z demo projektu. Toto je úloha základnej úrovne obtiažnosti. Odhadovaný čas na dokončenie úlohy sú 3 minúty.
Testované prvky obsahu: schopnosť vytvárať pravdivostné tabuľky a logické diagramy. Prvky obsahu testované na skúške: výroky, logické operácie, kvantifikátory, pravdivosť tvrdenia.
Úloha 2:
Logická funkcia F 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.
Do odpovede napíšte písmená w, x, y, z v poradí, v akom idú príslušné stĺpce (najprv - 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, medzi písmenami nie sú potrebné žiadne oddeľovače .
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)
Konjunkcia (logické násobenie) je pravdivá vtedy a len vtedy, ak sú pravdivé všetky tvrdenia. Preto premenná NS 1 .
Takže 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 na danom riadku bude pravdivé iba vtedy, ak z = 0, w = 1.
Takže premenná ¬z zhoduje sa stĺpec s premennou 1 (1 stĺpec), premenná w zhoduje stĺpec s premennou 4 (4 stĺpec).
№1
(x / \ y / \ z / \ ¬w) \ / (x / \ y / \ ¬z / \ ¬w) \ / (x / \ ¬ y / \ ¬z / \ ¬w).
Riešenie
x / \ y / \ z / \ ¬w - x = 1, y = 1, z = 1, w = 0;
x / \ y / \ ¬z / \ ¬w - x = 1, y = 1, z = 0, w = 0;
x / \ ¬ y / \ ¬z / \ ¬w - x = 1, y = 0, z = 0, w = 0.
Výsledkom je 6 jednotiek.
odpoveď:
6.
№2 Logická funkcia F je daná výrazom
(¬x / \ y / \ ¬z / \ w) \ / (x / \ y / \ z / \ ¬w) \ / (x / \ ¬ y / \ ¬z / \ w).
Stepan napísal všetky množiny premenných, pre ktoré tento výraz platí. Koľko jednotiek napísal Stepan? Do odpovede zapíšte len celé číslo – počet jednotiek.
Príklad. Nech je daný výraz x → y v závislosti od dvoch premenných x a y. Tento výraz platí pre tri množiny: (0, 0), (0, 1) a (1, 1). Stepan napísal 3 jednotky.
Riešenie podobný riešeniu.
№3 Logická funkcia F je daná výrazom
(x / \ ¬y / \ z / \ w) \ / (x / \ y / \ ¬z / \ w) \ / (¬x / \ y / \ z / \ w).
Stepan napísal všetky množiny premenných, pre ktoré tento výraz platí. Koľko jednotiek napísal Stepan? Do odpovede zapíšte len celé číslo – počet jednotiek.
Príklad. Nech je daný výraz x → y v závislosti od dvoch premenných x a y. Tento výraz platí pre tri množiny: (0, 0), (0, 1) a (1, 1). Stepan napísal 3 jednotky.
Riešenie podobný riešeniu.
№4 Logická funkcia F je daná výrazom
(¬x / \ ¬y / \ z / \ w) \ / (¬x / \ ¬y / \ ¬z / \ w) \ / (¬x / \ y / \ z / \ ¬w).
Stepan napísal všetky množiny premenných, pre ktoré tento výraz platí. Koľko jednotiek napísal Stepan? Do odpovede zapíšte len celé číslo – počet jednotiek.
Príklad. Nech je daný výraz x → y v závislosti od dvoch premenných x a y. Tento výraz platí pre tri množiny: (0, 0), (0, 1) a (1, 1). Stepan napísal 3 jednotky.
Riešenie podobný riešeniu.
№5 Logická funkcia F je daná výrazom
(¬x / \ y / \ ¬z / \ ¬w) \ / (x / \ ¬y / \ ¬z / \ ¬w) \ / (¬x / \ ¬y / \ z / \ ¬w).
Stepan napísal všetky množiny premenných, pre ktoré tento výraz platí. Koľko jednotiek napísal Stepan? Do odpovede zapíšte len celé číslo – počet jednotiek.
Príklad. Nech je daný výraz x → y v závislosti od dvoch premenných x a y. Tento výraz platí pre tri množiny: (0, 0), (0, 1) a (1, 1). Stepan napísal 3 jednotky.
Riešenie podobný riešeniu.
№6 Logická funkcia F je daná výrazom
(x / \ y / \ ¬w) \ / (x / \ ¬ y / \ ¬z / \ ¬w).
Stepan napísal všetky množiny premenných, pre ktoré tento výraz platí. Koľko jednotiek napísal Stepan? Do odpovede zapíšte len celé číslo – počet jednotiek.
Príklad. Nech je daný výraz x → y v závislosti od dvoch premenných x a y. Tento výraz platí pre tri množiny: (0, 0), (0, 1) a (1, 1). Stepan napísal 3 jednotky.
Riešenie
Logická funkcia F je pravdivá, ak je pravdivý aspoň jeden výraz v zátvorkách. Keďže všetky premenné v nich sú spojené konjunkciou, potom každý výraz musí byť pravdivý. Vypíšme skutočné množiny pre každú disjunkciu.
x / \ y / \ ¬w - (x = 1, y = 1, z = 1, w = 0) a (x = 1, y = 1, z = 0, w = 0);
x / \ ¬ y / \ ¬z / \ ¬w - x = 1, y = 1, z = 0, w = 0.
Výsledkom je 6 jednotiek.
№7 Logická funkcia F je daná výrazom
(x / \ y / \ z / \ ¬w) \ / (x / \ ¬z / \ ¬w).
Stepan napísal všetky množiny premenných, pre ktoré tento výraz platí. Koľko jednotiek napísal Stepan? Do odpovede zapíšte len celé číslo – počet jednotiek.
Príklad. Nech je daný výraz x → y v závislosti od dvoch premenných x a y. Tento výraz platí pre tri množiny: (0, 0), (0, 1) a (1, 1). Stepan napísal 3 jednotky.
Riešenie podobný riešeniu.
№8 Logická funkcia F je daná výrazom
(¬x / \ ¬y / \ z / \ w) \ / (x / \ z / \ w).
Stepan napísal všetky množiny premenných, pre ktoré tento výraz platí. Koľko jednotiek napísal Stepan? Do odpovede zapíšte len celé číslo – počet jednotiek.
Príklad. Nech je daný výraz x → y v závislosti od dvoch premenných x a y. Tento výraz platí pre tri množiny: (0, 0), (0, 1) a (1, 1). Stepan napísal 3 jednotky.
Riešenie podobný riešeniu.
№9 Logická funkcia F je daná výrazom
(y / \ ¬z / \ ¬w) \ / (¬x / \ ¬y / \ ¬z / \ w).
Stepan napísal všetky množiny premenných, pre ktoré tento výraz platí. Koľko jednotiek napísal Stepan? Do odpovede zapíšte len celé číslo – počet jednotiek.
Príklad. Nech je daný výraz x → y v závislosti od dvoch premenných x a y. Tento výraz platí pre tri množiny: (0, 0), (0, 1) a (1, 1). Stepan napísal 3 jednotky.
Riešenie podobný riešeniu.
№10 Logická funkcia F je daná výrazom
(x / \ y / \ ¬z) \ / (¬x / \ ¬y / \ ¬z).
Stepan napísal všetky množiny premenných, pre ktoré tento výraz platí. Koľko jednotiek napísal Stepan? Do odpovede zapíšte len celé číslo – počet jednotiek.
Príklad. Nech je daný výraz x → y v závislosti od dvoch premenných x a y. Tento výraz platí pre tri množiny: (0, 0), (0, 1) a (1, 1). Stepan napísal 3 jednotky.
Riešenie podobný riešeniu.
№11 Logická funkcia F je daná výrazom
¬ ((¬w / \ x) → (y / \ z)) \ / ¬ ((x / \ ¬ y) → (¬z \ / ¬w)).
Stepan napísal všetky množiny premenných, pre ktoré tento výraz platí. Koľko jednotiek napísal Stepan? Do odpovede zapíšte len celé číslo – počet jednotiek.
Príklad. Nech je daný výraz x → y v závislosti od dvoch premenných x a y. Tento výraz platí pre tri množiny: (0, 0), (0, 1) a (1, 1). Stepan napísal 3 jednotky.
Riešenie
¬ ((¬w / \ x) → (y / \ z)) - (x = 1, y = 1, z = 0, w = 0) a (x = 1, y = 0, z = 1, w = 0);
¬ ((x / \ ¬ y) → (¬z \ / ¬w)) - (x = 1, y = 0, z = 1, w = 1).
V dôsledku toho dostaneme 5 jednotiek.
№12 Logická funkcia F je daná výrazom
¬ ((¬x \ / ¬y) → (z \ / w)) \ / ¬ ((x \ / y) → (z \ / ¬w)).
Stepan napísal všetky množiny premenných, pre ktoré tento výraz platí. Koľko jednotiek napísal Stepan? Do odpovede zapíšte len celé číslo – počet jednotiek.
Príklad. Nech je daný výraz x → y v závislosti od dvoch premenných x a y. Tento výraz platí pre tri množiny: (0, 0), (0, 1) a (1, 1). Stepan napísal 3 jednotky.
Riešenie
Logická funkcia F je pravdivá, ak je pravdivý aspoň jeden výraz v zátvorkách. Keďže všetky premenné v nich sú implikácie, podmienka ich nepravdivosti dáva pravdivosť zátvorkám. Podľa príkladu vypíšeme pravdivé množiny pre každú zátvorku.
¬ ((¬x \ / ¬y) → (z \ / w)) - (x = 1, y = 0, z = 0, w = 0) a (x = 0, y = 1, z = 0, w = 0);
¬ ((x / \ ¬ y) → (¬z \ / ¬w)) - (x = 1, y = 0, z = 0, w = 0).
V dôsledku toho dostaneme 3 jednotky.
№13 Logická funkcia F je daná výrazom
¬ (¬ (x \ / y) → (¬z \ / w)) \ / ¬ (¬ (x / \ y) → (z \ / ¬w)).
Stepan napísal všetky množiny premenných, pre ktoré tento výraz platí. Koľko jednotiek napísal Stepan? Do odpovede zapíšte len celé číslo – počet jednotiek.
Príklad. Nech je daný výraz x → y v závislosti od dvoch premenných x a y. Tento výraz platí pre tri množiny: (0, 0), (0, 1) a (1, 1). Stepan napísal 3 jednotky.
Riešenie
Logická funkcia F je pravdivá, ak je pravdivý aspoň jeden výraz v zátvorkách. Keďže všetky premenné v nich sú implikácie, podmienka ich nepravdivosti dáva pravdivosť zátvorkám. Podľa príkladu vypíšeme pravdivé množiny pre každú zátvorku.
¬ (¬ (x \ / y) → (¬z \ / w)) - (x = 0, y = 0, z = 1, w = 0);
¬ (¬ (x / \ y) → (z \ / ¬w)) - (x = 1, y = 0, z = 0, w = 1), (x = 0, y = 1, z = 0, w = 1) a
(x = 0, y = 0, z = 0, w = 1).
Výsledkom je 6 jednotiek.
Logická funkcia F 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.
Do odpovede napíšte písmená w, X, r, z v poradí, v akom idú
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á
v odpovedi píšte za sebou, medzi písmená nedávajte žiadne oddeľovače
nie je potrebné.
Ukážková verzia Jednotnej štátnej skúšky Jednotná štátna skúška 2017 - úloha číslo 2
Riešenie:
Konjunkcia (logické násobenie) je pravdivá vtedy a len vtedy, ak sú pravdivé všetky tvrdenia. Preto premenná NS 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.
Takže premenná ¬z w zhoduje stĺpec s premennou 4 (4 stĺpec).
Odpoveď: zyxw
Ukážková verzia Jednotnej štátnej skúšky Jednotná štátna skúška 2016 - úloha číslo 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.
V odpovedi napíšte písmená x, y, z v poradí, v akom idú príslušné 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á píšte v rade za sebou, medzi písmenami nemusíte 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
premenná x zodpovedá. V odpovedi je potrebné napísať: yx.
Riešenie:
1. Píšme za daný výraz v jednoduchšej notácii:
¬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 pre funkciu ( F) sa rovnala jednej ( 1 ), je potrebné, aby sa každý faktor rovnal jednej ( 1 ). Teda pre F = 1, variabilný NS 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 na danom riadku bude pravdivé iba vtedy, ak
- z = 0; y = 0 alebo y = 1;
- z = 1; y = 1
5. Teda premenná ¬z zhoduje sa 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 číslo 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.
V odpovedi napíšte písmená x, y, z v poradí, v akom idú 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á napíšte do odpoveď v rade, bez oddeľovačov nie je potrebné 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ý, ak sa aspoň jeden z (x * y * ¬z), (x * y * z), (x * ¬y * ¬z) rovná 1. Spojka (logické násobenie) je pravdivá vtedy a len vtedy keď sú všetky tvrdenia pravdivé.
Aspoň jedna z týchto disjunkcií x * y * ¬z; x * y * z; x * ¬y * ¬z bude pravda len vtedy x = 1.
Takže premenná NS zhoduje stĺpec s premennou 2 (stĺpec 2).
Nechať byť 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
F označuje jedno z nasledujúcich logické výrazy 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 v 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) 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 v závislosti 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 ∧ ¬x8 nezodpovedá =... 01 - tý riadok)
4) ¬x1 ∨ ¬x2 ∨ ¬x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x7 ∨ ¬x8 = ¬x1 ∨ ¬x1 ∨ ¬x2 ∨ ¬x2 ∨ ¬x1... = nie zápasy v 2. riadku)
odpoveď: 2
Fragment pravdivostnej tabuľky pre výraz F je daný:
| 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 |
Zadajte minimálny možný počet samostatných riadkov v úplnej pravdivostnej tabuľke tohto výrazu, kde x5 je rovnaké ako F.
Riešenie:
Minimálny možný počet odlišných riadkov, kde x5 zodpovedá F = 4
odpoveď: 4
Fragment pravdivostnej tabuľky pre výraz F je daný:
| 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 |
Zadajte maximálny možný počet rôznych riadkov úplnej pravdivostnej tabuľky tohto výrazu, v ktorom x6 nezodpovedá F.
Riešenie:
Maximálny možný počet = 2 8 = 256
Maximálny možný počet odlišných riadkov, kde x6 nezodpovedá F = 256 - 5 = 251
odpoveď: 251
Fragment pravdivostnej tabuľky pre výraz F je daný:
| 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 |
Zadajte maximálny možný počet samostatných riadkov úplnej pravdivostnej tabuľky tohto výrazu, v ktorej 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 - sa zhoduje 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 každého z týchto výrazov sú v stĺpci hodnoty presne 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 každého z týchto výrazov sú v stĺpci hodnoty presne 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 každého z týchto výrazov je 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 každého z týchto výrazov je 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 boolovský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 logických výrazov F a G obsahuje 7 premenných. V pravdivostných tabuľkách výrazov F a G je práve 8 rovnakých riadkov a práve 5 z nich v stĺpci hodnoty má 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 pre a = 0 a c = 0, potom F = 0 a údajov z druhého riadku, môžeme usúdiť, že tretí stĺpec obsahuje b.
Odpoveď: kabína
Logická funkcia F je daná výrazom 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 |
V 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. (¬r. 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
Najprv si definujme, čo máme v úlohe:
- logická funkcia F, daná nejakým výrazom. Prvky pravdivostnej tabuľky tejto funkcie sú v úlohe prezentované aj vo forme tabuľky. Pri dosadzovaní konkrétnych hodnôt x, y, z z tabuľky do výrazu sa teda výsledok musí zhodovať s tým, ktorý je uvedený v tabuľke (pozri vysvetlenie nižšie).
- Premenné x, y, z a tri stĺpce, ktoré im zodpovedajú. Navyše v tomto probléme nevieme, ktorý stĺpec zodpovedá ktorej premennej. Teda vo Var. 1 môže byť buď x, y alebo z.
- Sme požiadaní, aby sme presne určili, ktorý stĺpec zodpovedá ktorej premennej.
Pozrime sa na príklad.
Riešenie
- Teraz sa vráťme k riešeniu. Pozrime sa bližšie na vzorec: \ ((\ neg z) \ klin x \ vee x \ klin y \)
- Má dve konjunkčné konštrukcie spojené disjunkciou. Ako viete, najčastejšie je disjunkcia pravdivá (na to stačí, aby bol jeden z výrazov pravdivý).
- Pozrime sa bližšie na riadky, kde je výraz F nepravdivý.
- Prvý riadok pre nás nie je zaujímavý, pretože sa nedá určiť, kde čo je (všetky hodnoty sú rovnaké).
- Uvažujme teda o predposlednom riadku, obsahuje najviac 1, ale výsledok je 0.
- Môže byť z v treťom stĺpci? Nie, pretože v tomto prípade bude vzorec obsahovať všade 1, a preto sa výsledok bude rovnať 1, ale podľa pravdivostnej tabuľky je hodnota F v tomto riadku 0. Preto z nemôže byť Var. 3.
- Podobne pre predchádzajúci riadok platí, že z nemôže byť Var. 2.
- teda z je Var. 1.
- Keď viete, že z je v prvom stĺpci, zvážte tretí riadok. Môže byť x v druhom stĺpci? Nahraďte hodnoty:
\ ((\ neg z) \ klin x \ vee x \ klin y = \\ = (\ neg 0) \ klin 1 \ vee 1 \ klin 0 = \\ = 1 \ klin 1 \ vee 0 = \\ = 1 \ vee 0 = 1 \) - Podľa pravdivostnej tabuľky by však výsledok mal byť 0.
- teda x nemôže byť Var. 2.
- teda x je Var. 3.
- Preto vylučovacou metódou y je Var. 2.
- Odpoveď je teda nasledovná: zyx (z - Var. 1, y - Var. 2, x - Var. 3).
Pracovný katalóg.
Počet programov s povinnou etapou
Urobte si test na tieto úlohy
Vráťte sa do katalógu úloh
Verzia pre tlač a kopírovanie v MS Word
Umelec 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ý zvýši číslo na obrazovke o 1, druhý ho zvýši o 2, tretí ho vynásobí 2.
Program pre interpreta A16 je postupnosť príkazov.
Koľko programov existuje, ktoré konvertujú pôvodné číslo 3 na 12 a výpočtová cesta programu obsahuje číslo 10?
Výpočtová cesta 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 s číslom 10 od čísla 3 a počtu programov s číslom 12 od čísla 10.
Nech R (n) je počet programov, ktoré konvertujú číslo 3 na číslo n, a P (n) 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 - pridaním jednotky alebo pridaní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ú podmienku 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 programov existuje, ak je dané počiatočné číslo 1, výsledkom je číslo 17 a trajektória výpočtu obsahuje číslo 9? Výpočtová cesta 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. získajme pole dp, kde dp [i] je počet spôsobov, ako získať číslo i pomocou takýchto príkazov.
Reproduktorová 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: Školenie o INFORMATIKE Grade 11 29. novembra 2016 Možnosť IN10203
Umelec 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 účinkujúceho May17 je postupnosť príkazov.
Koľko existuje programov, pre ktoré je vzhľadom na počiatočné číslo 1 výsledkom číslo 15 a trajektória výpočtu obsahuje číslo 8? Výpočtová cesta 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.
Reproduktorová 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 do nich dostať od hodnoty menšej ako 8. Ďalej budú uvedené hodnoty v bunkách dp od 1 do 15: 1 1 1 2 3 4 6 9 9 9 18 27 36 54 81 ...
