Rozbor 2 úloh zkoušky v roce 2017 z informatiky z demo projektu. Toto je úkol základní úrovně obtížnosti. Předpokládaný čas na dokončení úkolu jsou 3 minuty.
Testované prvky obsahu: schopnost vytvářet pravdivostní tabulky a logické diagramy. Obsahové prvky testované u zkoušky: výroky, logické operace, kvantifikátory, pravdivost tvrzení.
Úkol 2:
Logická funkce F daný výrazem X /\¬ y /\ (¬ z \/ w).
Obrázek ukazuje fragment pravdivostní tabulky funkce F obsahující Všechno F skutečný.
Určete, který sloupec pravdivostní tabulky funkce F každá z proměnných odpovídá w, X, y, z.
Do odpovědi napište písmena w, x, y, z v pořadí, ve kterém jdou odpovídající sloupce (nejprve - písmeno odpovídající prvnímu sloupci; poté - písmeno odpovídající druhému sloupci atd.) Písmena v odpovědi pište za sebou, mezi písmeny nejsou nutné žádné oddělovače .
Příklad... Pokud by funkce byla dána výrazem ¬ X \/ y v závislosti na dvou proměnných: X a y a byl dán fragment jeho pravdivostní tabulky obsahující Všechno množiny argumentů, pro které funkce F skutečný.
Pak by první sloupec odpovídal proměnné y a druhý sloupec je proměnná X... Odpověď měla napsat: yx.
Odpovědět: ________
X /\¬ y /\ (¬ z \/ w)
Konjunkce (logické násobení) je pravdivá tehdy a jen tehdy, když jsou pravdivá všechna tvrzení. Proto ta proměnná NS 1 .
Takže proměnná X odpovídá sloupci s proměnnou 3.
Variabilní ¬y sloupec obsahující hodnotu se musí shodovat 0 .
Disjunkce (logické sčítání) dvou výroků je pravdivá tehdy a jen tehdy, když je pravdivý alespoň jeden výrok.
Disjunkce ¬z \ / w na daném řádku bude pravdivé pouze tehdy, když z = 0, w = 1.
Takže proměnná ¬z odpovídá sloupci proměnné 1 (1 sloupec), proměnné w odpovídá sloupci s proměnnou 4 (4 sloupec).
№1
(x / \ y / \ z / \ ¬w) \ / (x / \ y / \ ¬z / \ ¬w) \ / (x / \ ¬ y / \ ¬z / \ ¬w).
Řešení
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ýsledkem je 6 jednotek.
Odpovědět:
6.
№2 Logická funkce F je dána výrazem
(¬x / \ y / \ ¬z / \ w) \ / (x / \ y / \ z / \ ¬w) \ / (x / \ ¬ y / \ ¬z / \ w).
Štěpán vypsal všechny množiny proměnných, pro které tento výraz platí. Kolik jednotek napsal Štěpán? Do odpovědi zapište pouze celé číslo – počet jednotek.
Příklad. Nechť je dán výraz x → y v závislosti na dvou proměnných x a y. Tento výraz platí pro tři množiny: (0, 0), (0, 1) a (1, 1). Štěpán napsal 3 jednotky.
Řešení podobné řešení.
№3 Logická funkce F je dána výrazem
(x / \ ¬y / \ z / \ w) \ / (x / \ y / \ ¬z / \ w) \ / (¬x / \ y / \ z / \ w).
Štěpán vypsal všechny množiny proměnných, pro které tento výraz platí. Kolik jednotek napsal Štěpán? Do odpovědi zapište pouze celé číslo – počet jednotek.
Příklad. Nechť je dán výraz x → y v závislosti na dvou proměnných x a y. Tento výraz platí pro tři množiny: (0, 0), (0, 1) a (1, 1). Štěpán napsal 3 jednotky.
Řešení podobné řešení.
№4 Logická funkce F je dána výrazem
(¬x / \ ¬y / \ z / \ w) \ / (¬x / \ ¬y / \ ¬z / \ w) \ / (¬x / \ y / \ z / \ ¬w).
Štěpán vypsal všechny množiny proměnných, pro které tento výraz platí. Kolik jednotek napsal Štěpán? Do odpovědi zapište pouze celé číslo – počet jednotek.
Příklad. Nechť je dán výraz x → y v závislosti na dvou proměnných x a y. Tento výraz platí pro tři množiny: (0, 0), (0, 1) a (1, 1). Štěpán napsal 3 jednotky.
Řešení podobné řešení.
№5 Logická funkce F je dána výrazem
(¬x / \ y / \ ¬z / \ ¬w) \ / (x / \ ¬y / \ ¬z / \ ¬w) \ / (¬x / \ ¬y / \ z / \ ¬w).
Štěpán vypsal všechny množiny proměnných, pro které tento výraz platí. Kolik jednotek napsal Štěpán? Do odpovědi zapište pouze celé číslo – počet jednotek.
Příklad. Nechť je dán výraz x → y v závislosti na dvou proměnných x a y. Tento výraz platí pro tři množiny: (0, 0), (0, 1) a (1, 1). Štěpán napsal 3 jednotky.
Řešení podobné řešení.
№6 Logická funkce F je dána výrazem
(x / \ y / \ ¬w) \ / (x / \ ¬ y / \ ¬z / \ ¬w).
Štěpán vypsal všechny množiny proměnných, pro které tento výraz platí. Kolik jednotek napsal Štěpán? Do odpovědi zapište pouze celé číslo – počet jednotek.
Příklad. Nechť je dán výraz x → y v závislosti na dvou proměnných x a y. Tento výraz platí pro tři množiny: (0, 0), (0, 1) a (1, 1). Štěpán napsal 3 jednotky.
Řešení
Logická funkce F je pravdivá, když je pravdivý alespoň jeden výraz v závorkách. Vzhledem k tomu, že všechny proměnné v nich jsou spojeny konjunkcí, musí být každý člen pravdivý. Vypišme skutečné množiny pro každou disjunkci.
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ýsledkem je 6 jednotek.
№7 Logická funkce F je dána výrazem
(x / \ y / \ z / \ ¬w) \ / (x / \ ¬z / \ ¬w).
Štěpán vypsal všechny množiny proměnných, pro které tento výraz platí. Kolik jednotek napsal Štěpán? Do odpovědi zapište pouze celé číslo – počet jednotek.
Příklad. Nechť je dán výraz x → y v závislosti na dvou proměnných x a y. Tento výraz platí pro tři množiny: (0, 0), (0, 1) a (1, 1). Štěpán napsal 3 jednotky.
Řešení podobné řešení.
№8 Logická funkce F je dána výrazem
(¬x / \ ¬y / \ z / \ w) \ / (x / \ z / \ w).
Štěpán vypsal všechny množiny proměnných, pro které tento výraz platí. Kolik jednotek napsal Štěpán? Do odpovědi zapište pouze celé číslo – počet jednotek.
Příklad. Nechť je dán výraz x → y v závislosti na dvou proměnných x a y. Tento výraz platí pro tři množiny: (0, 0), (0, 1) a (1, 1). Štěpán napsal 3 jednotky.
Řešení podobné řešení.
№9 Logická funkce F je dána výrazem
(y / \ ¬z / \ ¬w) \ / (¬x / \ ¬y / \ ¬z / \ w).
Štěpán vypsal všechny množiny proměnných, pro které tento výraz platí. Kolik jednotek napsal Štěpán? Do odpovědi zapište pouze celé číslo – počet jednotek.
Příklad. Nechť je dán výraz x → y v závislosti na dvou proměnných x a y. Tento výraz platí pro tři množiny: (0, 0), (0, 1) a (1, 1). Štěpán napsal 3 jednotky.
Řešení podobné řešení.
№10 Logická funkce F je dána výrazem
(x / \ y / \ ¬z) \ / (¬x / \ ¬y / \ ¬z).
Štěpán vypsal všechny množiny proměnných, pro které tento výraz platí. Kolik jednotek napsal Štěpán? Do odpovědi zapište pouze celé číslo – počet jednotek.
Příklad. Nechť je dán výraz x → y v závislosti na dvou proměnných x a y. Tento výraz platí pro tři množiny: (0, 0), (0, 1) a (1, 1). Štěpán napsal 3 jednotky.
Řešení podobné řešení.
№11 Logická funkce F je dána výrazem
¬ ((¬w / \ x) → (y / \ z)) \ / ¬ ((x / \ ¬ y) → (¬z \ / ¬w)).
Štěpán vypsal všechny množiny proměnných, pro které tento výraz platí. Kolik jednotek napsal Štěpán? Do odpovědi zapište pouze celé číslo – počet jednotek.
Příklad. Nechť je dán výraz x → y v závislosti na dvou proměnných x a y. Tento výraz platí pro tři množiny: (0, 0), (0, 1) a (1, 1). Štěpán napsal 3 jednotky.
Řešení
¬ ((¬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ýsledkem je 5 jednotek.
№12 Logická funkce F je dána výrazem
¬ ((¬x \ / ¬y) → (z \ / w)) \ / ¬ ((x \ / y) → (z \ / ¬w)).
Štěpán vypsal všechny množiny proměnných, pro které tento výraz platí. Kolik jednotek napsal Štěpán? Do odpovědi zapište pouze celé číslo – počet jednotek.
Příklad. Nechť je dán výraz x → y v závislosti na dvou proměnných x a y. Tento výraz platí pro tři množiny: (0, 0), (0, 1) a (1, 1). Štěpán napsal 3 jednotky.
Řešení
Logická funkce F je pravdivá, když je pravdivý alespoň jeden výraz v závorkách. Protože všechny proměnné v nich jsou implikacemi, podmínka jejich nepravdivosti dává závorce pravdivost. Podle příkladu vypíšeme pravdivé množiny pro každou závorku.
¬ ((¬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ýsledkem jsou 3 jednotky.
№13 Logická funkce F je dána výrazem
¬ (¬ (x \ / y) → (¬z \ / w)) \ / ¬ (¬ (x / \ y) → (z \ / ¬w)).
Štěpán vypsal všechny množiny proměnných, pro které tento výraz platí. Kolik jednotek napsal Štěpán? Do odpovědi zapište pouze celé číslo – počet jednotek.
Příklad. Nechť je dán výraz x → y v závislosti na dvou proměnných x a y. Tento výraz platí pro tři množiny: (0, 0), (0, 1) a (1, 1). Štěpán napsal 3 jednotky.
Řešení
Logická funkce F je pravdivá, když je pravdivý alespoň jeden výraz v závorkách. Protože všechny proměnné v nich jsou implikacemi, podmínka jejich nepravdivosti dává závorce pravdivost. Podle příkladu vypíšeme pravdivé množiny pro každou závorku.
¬ (¬ (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ýsledkem je 6 jednotek.
Logická funkce F daný výrazem X/\ ¬y/\ (¬z\/ w).
Obrázek ukazuje fragment pravdivostní tabulky funkce F obsahující Všechno množiny argumentů, pro které funkce F skutečný.
Určete, který sloupec pravdivostní tabulky funkce F každá z proměnných odpovídá w, X, y, z.
Do odpovědi napište písmena w, X, y, z v pořadí, v jakém jdou
jejich odpovídající sloupce (první - písmeno odpovídající prvnímu
sloupec; potom - písmeno odpovídající druhému sloupci atd.) Písmena
v odpovědi pište za sebou, mezi písmena nedávejte žádné oddělovače
není nutné.
Ukázková verze Jednotné státní zkoušky Jednotná státní zkouška 2017 - úkol číslo 2
Řešení:
Konjunkce (logické násobení) je pravdivá tehdy a jen tehdy, když jsou pravdivá všechna tvrzení. Proto ta proměnná NS 1 .
Variabilní ¬y musí odpovídat sloupci, ve kterém jsou všechny hodnoty stejné 0 .
Disjunkce (logické sčítání) dvou výroků je pravdivá tehdy a jen tehdy, když je pravdivý alespoň jeden výrok.
Disjunkce ¬z \ / r z = 0, w = 1.
Takže proměnná ¬z w odpovídá sloupci s proměnnou 4 (4 sloupec).
Odpověď: zyxw
Ukázková verze Jednotné státní zkoušky Jednotná státní zkouška 2016 - úkol číslo 2
Logická funkce F je dáno výrazem (¬z) / \ x \ / x / \ y. Určete, který sloupec pravdivostní tabulky funkce F odpovídá každé z proměnných x, y, z.
V odpovědi napište písmena x, y, z v pořadí, ve kterém jdou odpovídající sloupce (nejprve - písmeno odpovídající 1. sloupci; poté - písmeno odpovídající 2. sloupci; poté - písmeno odpovídající 3. sloupec)... Pište písmena v řadě za sebou, mezi písmena nemusíte dávat žádné oddělovače.
Příklad... Nechť je dán výraz x → y v závislosti na dvou proměnných x a y a pravdivostní tabulka:
Pak 1. sloupec odpovídá proměnné y a 2. sloupec
proměnná x odpovídá. V odpovědi je třeba napsat: yx.
Řešení:
1. Pojďme psát pro daný výraz v jednodušší notaci:
¬z * x + x * y = x * (¬z + y)
2. Konjunkce (logické násobení) je pravdivá tehdy a jen tehdy, když jsou pravdivá všechna tvrzení. Proto pro funkci ( F) se rovnal jedné ( 1 ), je nutné, aby se každý faktor rovnal jedné ( 1 ). Tedy pro F = 1, variabilní NS musí odpovídat sloupci, ve kterém jsou všechny hodnoty stejné 1 .
3. Zvažte (¬z + y), na F = 1 tento výraz je rovněž roven 1 (viz bod 2).
4. Disjunkce (logické sčítání) dvou tvrzení je pravdivá tehdy a jen tehdy, když je pravdivé alespoň jedno tvrzení.
Disjunkce ¬z \ / r na daném řádku bude pravdivé pouze tehdy, když
- z = 0; y = 0 nebo y = 1;
- z = 1; y = 1
5. Tedy proměnná ¬z odpovídá sloupci proměnné 1 (1 sloupec), proměnné y
Odpověď: zyx
Jednotná státní zkouška KIM Jednotná státní zkouška 2016 (počáteční období)- úkol číslo 2
Logická funkce F je dána výrazem
(x / \ y / \ ¬z) \ / (x / \ y / \ z) \ / (x / \ ¬y / \ ¬z).
Obrázek ukazuje fragment pravdivostní tabulky funkce F obsahující všechny množiny argumentů, pro které je funkce F pravdivá. Určete, který sloupec pravdivostní tabulky funkce F odpovídá každé z proměnných x, y, z.
V odpovědi napište písmena x, y, z v pořadí, ve kterém jdou odpovídající sloupce (nejprve - písmeno odpovídající prvnímu sloupci; poté - písmeno odpovídající druhému sloupci atd.) Pište písmena v odpověď v řadě, žádné oddělovače není třeba vkládat mezi písmena.
R řešení:
Zapišme daný výraz v jednodušším zápisu:
(x * y * ¬z) + (x * y * z) + (x * ¬y * ¬z) = 1
Tento výraz je pravdivý, pokud se alespoň jedno z (x * y * ¬z), (x * y * z), (x * ¬y * ¬z) rovná 1. Konjunkce (logické násobení) je pravdivá tehdy a jen tehdy když jsou všechna tvrzení pravdivá.
Alespoň jedna z těchto disjunkcí x * y * ¬z; x * y * z; x * ¬y * ¬z bude pravdivé pouze tehdy x = 1.
Takže proměnná NS odpovídá sloupci s proměnnou 2 (sloupec 2).
Nech být y- proměnná 1, z- prem. 3. Pak v prvním případě x * ¬y * ¬z bude pravda, v druhém případě x * y * ¬z a ve třetím x * y * z.
Odpověď: yxz
F označuje jedno z následujících logické výrazy ze tří argumentů: X, Y, Z. Je dán fragment pravdivostní tabulky výrazu F (viz tabulka vpravo). Který výraz odpovídá 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
Řešení:
1) X ∧ Y ∧ Z = 1,0,1 = 0 (neodpovídá na 2. řádku)
2) ¬X ∨ Y ∨¬Z = ¬0 ∨ 0 ∨ ¬0 = 1 + 0 + 1 = 1 (neodpovídá na 1. řádku)
3) X ∧ Y ∨ Z = 0,1 + 0 = 0 (neodpovídá na 3. řádku)
4) X ∨ Y ∧ ¬Z (odpovídá 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
Odpověď: 4
Je dán fragment pravdivostní tabulky výrazu F. Který výraz odpovídá 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
Řešení:
1) (A → ¬B) ∨ C = (1 → ¬0) ∨ 0 = (1 → 1) + 0 = 1 + 0 = 1 (neodpovídá na 2. řádku)
2) (¬A ∨ B) ∧ C = (¬1 ∨ 0) ∧ 1 = (0 + 0) 0,1 = 0 (neodpovídá na 3. řádku)
3) (A ∧ B) → C = (1 ∧ 0) → 0 = 0 → 0 = 1 (neodpovídá na 2. řádku)
4) (A ∨ B) → C (odpovídá F)
(A ∨ B) → C = (0 ∨ 1) → 1 = 1
(A ∨ B) → C = (1 ∨ 0) → 0 = 0
(A ∨ B) → C = (1 ∨ 0) → 1 = 1
Odpověď: 4
Je dán logický výraz v závislosti na 6 logických proměnných:
X1 ∨ ¬X2 ∨ X3 ∨ ¬X4 ∨ X5 ∨ X6
Kolik různých sad hodnot proměnných existuje, pro které je výraz pravdivý?
1) 1 2) 2 3) 63 4) 64
Řešení:
Nesprávný výraz pouze v 1 případě: 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
Celkem je 2 6 = 64 možností, což znamená pravda
Odpověď: 63
Je dán fragment pravdivostní tabulky 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 |
Který výraz odpovídá 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
Řešení:
1) x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ x6 ∨ ¬x7 = 0 + 1 +… = 1 (neodpovídá na 1. řádku)
2) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ x7 = 0 + 0 + 0 + 0 + 0 + 1 + 0 = 1 (neodpovídá na 1. řádku)
3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7 = 1,0. ... = 0 (neodpovídá na 2. řádku)
4) x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 (odpovídá 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
Odpověď: 4
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | F |
| 0 | 1 | 1 | ||||||
| 1 | 0 | 1 | 0 | |||||
| 1 | 0 | 1 |
Jaký výraz může být 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
Řešení:
1) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8 = x1. ¬x2. 0 ... = 0 (neodpovídá na 1. řádku)
2) ¬x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ x8 (odpovídá F)
3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8 =… ¬x7 ∧ ¬x8 =… ¬1 ∧ ¬x8 neodpovídá =… 0 - tý řádek)
4) ¬x1 ∨ ¬x2 ∨ ¬x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x7 ∨ ¬x8 = ¬x1 ∨ ¬x2 ∨ ¬x2 ∨ ¬x 1 = ne¬ ¬2. zápasy na 2. řádku)
Odpověď: 2
Fragment pravdivostní tabulky pro výraz F je dán:
| 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 |
Zadejte minimální možný počet odlišných řádků v úplné pravdivostní tabulce tohoto výrazu, kde x5 je stejné jako F.
Řešení:
Minimální možný počet odlišných řádků, kde x5 odpovídá F = 4
Odpověď: 4
Fragment pravdivostní tabulky pro výraz F je dán:
| 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 |
Zadejte maximální možný počet různých řádků úplné pravdivostní tabulky tohoto výrazu, ve kterém x6 neodpovídá F.
Řešení:
Maximální možný počet = 2 8 = 256
Maximální možný počet odlišných řádků, kde x6 neodpovídá F = 256 - 5 = 251
Odpověď: 251
Fragment pravdivostní tabulky pro výraz F je dán:
| 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 |
Zadejte maximální možný počet samostatných řádků úplné pravdivostní tabulky tohoto výrazu, ve které se hodnota ¬x5 ∨ x1 shoduje s F.
Řešení:
1 + 0 = 1 – neodpovídá F
0 + 0 = 0 – neodpovídá F
0 + 0 = 0 – neodpovídá F
0 + 1 = 1 - shoduje se s F
1 + 0 = 1 - shoduje se s F
2 7 = 128 – 3 = 125
Odpověď: 125
Každý booleovský výraz A a B závisí na stejné sadě 6 proměnných. V pravdivostních tabulkách každého z těchto výrazů jsou ve sloupci hodnoty přesně 4 jednotky. Jaký je minimální možný počet jedniček ve sloupci hodnot pravdivostní tabulky výrazu A ∨ B?
Řešení:
Odpověď: 4
Každý booleovský výraz A a B závisí na stejné sadě 7 proměnných. V pravdivostních tabulkách každého z těchto výrazů jsou ve sloupci hodnoty přesně 4 jednotky. Jaký je maximální možný počet jedniček ve sloupci hodnot pravdivostní tabulky výrazu A ∨ B?
Řešení:
Odpověď: 8
Každý booleovský výraz A a B závisí na stejné sadě 8 proměnných. V pravdivostních tabulkách každého z těchto výrazů je ve sloupci hodnoty přesně 5 jednotek. Jaký je minimální možný počet nul ve sloupci hodnot pravdivostní tabulky výrazu A ∧ B?
Řešení:
2 8 = 256 – 5 = 251
Odpověď: 251
Každý booleovský výraz A a B závisí na stejné sadě 8 proměnných. V pravdivostních tabulkách každého z těchto výrazů je ve sloupci hodnoty přesně 6 jednotek. Jaký je maximální možný počet nul ve sloupci hodnot pravdivostní tabulky výrazu A ∧ B?
Řešení:
Odpověď: 256
Každý z booleovských výrazů A a B závisí na stejné sadě 5 proměnných. V pravdivostních tabulkách obou výrazů nejsou žádné odpovídající řádky. Kolik jedniček bude obsaženo ve sloupci hodnot pravdivostní tabulky výrazu A ∧ B?
Řešení:
V pravdivostních tabulkách obou výrazů nejsou žádné odpovídající řádky.
Odpověď: 0
Každý z booleovských výrazů A a B závisí na stejné sadě 6 proměnných. V pravdivostních tabulkách obou výrazů nejsou žádné odpovídající řádky. Kolik jedniček bude obsaženo ve sloupci hodnot pravdivostní tabulky výrazu A ∨ B?
Řešení:
Odpověď: 64
Každý z booleovských výrazů A a B závisí na stejné sadě 7 proměnných. V pravdivostních tabulkách obou výrazů nejsou žádné odpovídající řádky. Jaký je maximální možný počet nul ve sloupci hodnot pravdivostní tabulky výrazu ¬A ∨ B?
Řešení:
A = 1, B = 0 => ¬0 ∨ 0 = 0 + 0 = 0
Odpověď: 128
Každý z logických výrazů F a G obsahuje 7 proměnných. V pravdivostních tabulkách výrazů F a G je právě 8 stejných řádků a právě 5 z nich ve sloupci hodnoty má 1. Kolik řádků pravdivostní tabulky pro výraz F ∨ G obsahuje 1 ve sloupci hodnoty?
Řešení:
Existuje přesně 8 stejných řádků a přesně 5 z nich má ve sloupci hodnoty 1.
To znamená, že právě 3 z nich mají ve sloupci hodnoty 0.
Odpověď: 125
Logická funkce F je dána výrazem (a ∧ ¬c) ∨ (¬b ∧ ¬c). Určete, který sloupec pravdivostní tabulky funkce F odpovídá každé z proměnný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 |
Ve své odpovědi napište písmena a, b, c v pořadí, v jakém se objevují odpovídající sloupce.
Řešení:
(a. ¬c) + (¬b. ¬c)
Když c je 1, F je nula, takže poslední sloupec je c.
Pro určení prvního a druhého sloupce můžeme použít hodnoty ze 3. řádku.
(a. 1) + (¬b. 1) = 0
Odpověď: abc
Logická funkce F je dána výrazem (a ∧ c) ∨ (¬a ∧ (b ∨ ¬c)). Určete, který sloupec pravdivostní tabulky funkce F odpovídá každé z proměnných a, b, c.
Na základě skutečnosti, že pro a = 0 a c = 0, pak F = 0 a údajů z druhého řádku, můžeme usoudit, že třetí sloupec obsahuje b.
Odpověď: taxi
Logická funkce F je dána výrazem x ∧ (¬y ∧ z ∧ ¬w ∨ y ∧ ¬z). Obrázek ukazuje fragment pravdivostní tabulky funkce F obsahující všechny množiny argumentů, pro které je funkce F pravdivá. Určete, který sloupec pravdivostní tabulky funkce F odpovídá každé z proměnných x, y, z, w.
| ? | ? | ? | ? | F |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
Do odpovědi napište písmena x, y, z, w v pořadí, v jakém se objevují odpovídající sloupce.
Řešení:
x ∧ (¬y ∧ z ∧ ¬w ∨ y ∧ ¬z)
X. (¬y. Z. ¬w. Y. ¬z)
Na základě skutečnosti, že při x = 0, pak F = 0, můžeme usoudit, že druhý sloupec obsahuje X.
Odpověď: wxzy
Nejprve si definujme, co máme v úkolu:
- logická funkce F, daná nějakým výrazem. Prvky pravdivostní tabulky této funkce jsou v úloze také prezentovány ve formě tabulky. Při dosazení konkrétních hodnot x, y, z z tabulky do výrazu se tedy výsledek musí shodovat s tím, který je uveden v tabulce (viz vysvětlení níže).
- Proměnné x, y, z a tři sloupce, které jim odpovídají. Navíc v tomto problému nevíme, který sloupec odpovídá které proměnné. Tedy ve Var. 1 může být buď x, y nebo z.
- Jsme požádáni, abychom přesně určili, který sloupec odpovídá které proměnné.
Podívejme se na příklad.
Řešení
- Vraťme se nyní k řešení. Podívejme se blíže na vzorec: \ ((\ neg z) \ klín x \ vee x \ klín y \)
- Má dvě konjunkce spojené disjunkcí. Jak víte, nejčastěji je disjunkce pravdivá (k tomu stačí, aby jeden z výrazů byl pravdivý).
- Podívejme se blíže na řádky, kde je výraz F nepravdivý.
- První řádek pro nás není zajímavý, protože nelze určit, kde co je (všechny hodnoty jsou stejné).
- Uvažujme tedy předposlední řádek, obsahuje nejvíce ze všech 1, ale výsledek je 0.
- Může být z ve třetím sloupci? Ne, protože v tomto případě bude vzorec všude obsahovat 1, a proto se výsledek bude rovnat 1, ale podle pravdivostní tabulky je hodnota F v tomto řádku 0. Z tedy nemůže být Var. 3.
- Podobně pro předchozí řádek platí, že z nemůže být Var. 2.
- Proto, z je Var. 1.
- S vědomím, že z je v prvním sloupci, zvažte třetí řádek. Může být x ve druhém sloupci? Dosaďte hodnoty:
\ ((\ neg z) \ klín x \ vee x \ klín y = \\ = (\ neg 0) \ klín 1 \ vee 1 \ klín 0 = \\ = 1 \ klín 1 \ vee 0 = \\ = 1 \ vee 0 = 1 \) - Podle pravdivostní tabulky by však měl být výsledek 0.
- Proto, x nemůže být Var. 2.
- Proto, x je Var. 3.
- Vylučovací metodou tedy y je Var. 2.
- Odpověď je tedy následující: zyx (z - Var. 1, y - Var. 2, x - Var. 3).
Katalog práce.
Počet programů s povinnou etapou
Udělejte si test na tyto úkoly
Vraťte se do katalogu úkolů
Verze pro tisk a kopírování v MS Word
Artist A16 převede číslo napsané na obrazovce.
Účinkující má tři týmy, které mají přidělená čísla:
1. Přidejte 1
2. Přidejte 2
3. Vynásobte 2
První zvýší číslo na obrazovce o 1, druhý jej zvýší o 2, třetí ho vynásobí 2.
Program pro performera A16 je posloupnost příkazů.
Kolik existuje programů, které převádějí původní číslo 3 na 12 a výpočetní cesta programu obsahuje číslo 10?
Výpočetní cesta programu je posloupnost výsledků provádění všech příkazů programu. Například pro program 132 s počátečním číslem 7 bude trajektorie sestávat z čísel 8, 16, 18.
Řešení.
Požadovaný počet programů se rovná součinu počtu programů, které obdrží číslo 10 od čísla 3, a počtu programů, které obdrží číslo 12 od čísla 10.
Nechť R (n) je počet programů, které převádějí číslo 3 na číslo n, a P (n) počet programů, které převádějí číslo 10 na číslo n.
Pro všechna n> 5 platí následující vztahy:
1. Pokud n není dělitelné 2, pak R (n) = R (n - 1) + R (n - 2), protože existují dva způsoby, jak získat n - přidáním jedné nebo přidáním dvou. Podobně P (n) = P (n - 1) + P (n - 2)
2. Je-li n dělitelné 2, pak R (n) = R (n - 1) + R (n - 2) + R (n / 2). Podobně P (n) = P (n - 1) + P (n - 2) + P (n / 2)
Pojďme postupně vypočítat 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
Nyní vypočítejme hodnoty P (n):
P(11) = P(10) = 1
P (12) = P (11) + P (10) = 2
Počet programů, které splňují podmínku problému, je tedy 30 2 = 60.
Odpověď: 60.
Odpověď: 60
Zdroj: Demoverze jednotné státní zkoušky-2017 z informatiky.
1. Přidejte 1
2. Přidejte 3
Kolik existuje programů, pro které je vzhledem k počátečnímu číslu 1 výsledkem číslo 17 a trajektorie výpočtu obsahuje číslo 9? Výpočetní cesta programu je posloupnost výsledků provádění všech příkazů programu. Například pro program 121 s počátečním číslem 7 bude trajektorie sestávat z čísel 8, 11, 12.
Řešení.
Používáme metodu dynamického programování. pojďme získat pole dp, kde dp [i] je počet způsobů, jak získat číslo i pomocí takových příkazů.
Základna reproduktoru:
Přechodový vzorec:
dp [i] = dp + dp
Toto nebere v úvahu hodnoty pro čísla větší než 9, které lze získat z čísel menších než 9 (čímž se přeskočí trajektorie 9):
Odpověď: 169.
Odpověď: 169
Zdroj: Školicí práce na INFORMATICS Grade 11 29. listopadu 2016 Možnost IN10203
Artist May17 převede číslo na obrazovce.
Účinkující má dva týmy, které mají přidělená čísla:
1. Přidejte 1
2. Přidejte 3
První příkaz zvýší číslo na obrazovce o 1, druhý jej zvýší o 3. Program pro performera May17 je posloupnost příkazů.
Kolik existuje programů, pro které je vzhledem k počátečnímu číslu 1 výsledkem číslo 15 a trajektorie výpočtu obsahuje číslo 8? Výpočetní cesta programu je posloupnost výsledků provádění všech příkazů programu. Například pro program 121 s počátečním číslem 7 bude trajektorie sestávat z čísel 8, 11, 12.
Řešení.
Používáme metodu dynamického programování. Vytvořme pole dp, kde dp [i] je počet způsobů, jak získat číslo i pomocí takových příkazů.
Základna reproduktoru:
Přechodový vzorec:
dp [i] = dp + dp
To ale nebere v úvahu čísla větší než 8, ale můžeme se do nich dostat od hodnoty menší než 8. Dále budou uvedeny hodnoty v buňkách dp od 1 do 15: 1 1 1 2 3 4 6 9 9 9 18 27 36 54 81 ...
