Demoversiooni projektist arvutiteaduse ühtse riigieksami 2017 ülesande 2 analüüs. See on põhilise raskusastmega ülesanne. Ülesande täitmiseks kulub orienteeruvalt 3 minutit.
Testitud sisuelemendid: tõetabelite ja loogiliste ahelate konstrueerimise oskus. Ühtse riigieksamil testitud sisuelemendid: väited, loogilisi tehteid, kvantorid, väidete tõesus.
Ülesanne 2:
Loogiline funktsioon F on antud väljendiga x /\¬ y /\ (¬ z \/ w).
Joonisel on kujutatud funktsiooni tõesuse tabeli fragment F sisaldavad Kõik F tõsi.
Määrake, milline funktsiooni tõesuse tabeli veerg F iga muutuja vastab w, x, y, z.
Kirjutage oma vastusesse tähed w, x, y, z vastavate veergude ilmumise järjekorras (kõigepealt - esimesele veerule vastav täht; seejärel - teisele veerule vastav täht jne) Kirjutage vastuses olevad tähed ritta, pole vaja ühtegi panna eraldajad tähtede vahel.
Näide. Kui funktsioon oleks antud avaldisega ¬ x \/ y, olenevalt kahest muutujast: x Ja y, ja anti fragment selle tõetabelist, mis sisaldas Kõik argumentide komplektid, mille jaoks funktsioon F tõsi.
Siis vastaks esimene veerg muutujale y ja teine veerg on muutuja x. Vastus oleks pidanud kirjutama: yx.
Vastus: ________
x /\¬ y /\ (¬ z \/ w)
Konjunktsioon (loogiline korrutis) on tõene siis ja ainult siis, kui kõik väited on tõesed. Seetõttu muutuja X 1 .
Seega muutuja x vastab veerule muutujaga 3.
Muutuv ¬y väärtust sisaldav veerg peab ühtima 0 .
Kahe väite disjunktsioon (loogiline liitmine) on tõene siis ja ainult siis, kui vähemalt üks väide on tõene.
Disjunktsioon ¬z\/w selles reas on tõsi ainult siis, kui z = 0, w=1.
Seega muutuja ¬z vastab veerule muutujaga 1 (1 veerg), muutuja w vastab veerule muutujaga 4 (veerg 4).
№1
(x /\ y/\z/\¬w)\/ (x /\ y/\¬z/\¬w)\/ (x /\¬ y/\¬z/\¬w).
Lahendus
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.
Selle tulemusena saame 6 ühikut.
Vastus:
6.
№2 Loogiline funktsioon F on antud avaldisega
(¬x /\ y/\¬z/\w)\/ (x /\ y/\z/\¬w)\/ (x /\¬ y/\¬z/\w).
Stepan loetles kõik muutujate komplektid, mille puhul see avaldis on tõene. Mitu ühikut Stepan kirjutas? Oma vastuses kirjutage üles ainult täisarv - ühikute arv.
Näide. Olgu antud avaldis x → y, mis sõltub kahest muutujast x ja y. See avaldis kehtib kolme hulga kohta: (0, 0), (0, 1) ja (1, 1). Stepan kirjutas 3 ühikut.
Lahendus lahendusega sarnane.
№3 Loogiline funktsioon F on antud avaldisega
(x /\ ¬y/\z/\w)\/ (x /\ y/\¬z/\w)\/ (¬x /\ y/\ z/\w).
Stepan loetles kõik muutujate komplektid, mille puhul see avaldis on tõene. Mitu ühikut Stepan kirjutas? Oma vastuses kirjutage üles ainult täisarv - ühikute arv.
Näide. Olgu antud avaldis x → y, mis sõltub kahest muutujast x ja y. See avaldis kehtib kolme hulga kohta: (0, 0), (0, 1) ja (1, 1). Stepan kirjutas 3 ühikut.
Lahendus lahendusega sarnane.
№4 Loogiline funktsioon F on antud avaldisega
(¬x /\ ¬y/\z/\w)\/ (¬x /\ ¬y/\¬z/\w)\/ (¬x /\ y/\ z/\¬w).
Stepan loetles kõik muutujate komplektid, mille puhul see avaldis on tõene. Mitu ühikut Stepan kirjutas? Oma vastuses kirjutage üles ainult täisarv - ühikute arv.
Näide. Olgu antud avaldis x → y, mis sõltub kahest muutujast x ja y. See avaldis kehtib kolme hulga kohta: (0, 0), (0, 1) ja (1, 1). Stepan kirjutas 3 ühikut.
Lahendus lahendusega sarnane.
№5 Loogiline funktsioon F on antud avaldisega
(¬x /\ y/\¬z/\¬w)\/ (x /\ ¬y/\¬z/\¬w)\/ (¬x /\ ¬y/\ z/\¬w).
Stepan loetles kõik muutujate komplektid, mille puhul see avaldis on tõene. Mitu ühikut Stepan kirjutas? Oma vastuses kirjutage üles ainult täisarv - ühikute arv.
Näide. Olgu antud avaldis x → y, mis sõltub kahest muutujast x ja y. See avaldis kehtib kolme hulga kohta: (0, 0), (0, 1) ja (1, 1). Stepan kirjutas 3 ühikut.
Lahendus lahendusega sarnane.
№6 Loogiline funktsioon F on antud avaldisega
(x /\ y/\¬w)\/ (x /\¬ y/\¬z/\¬w).
Stepan loetles kõik muutujate komplektid, mille puhul see avaldis on tõene. Mitu ühikut Stepan kirjutas? Oma vastuses kirjutage üles ainult täisarv - ühikute arv.
Näide. Olgu antud avaldis x → y, mis sõltub kahest muutujast x ja y. See avaldis kehtib kolme hulga kohta: (0, 0), (0, 1) ja (1, 1). Stepan kirjutas 3 ühikut.
Lahendus
Loogiline funktsioon F on tõene, kui vähemalt üks sulgudes olev avaldis on tõene. Kuna kõik muutujad neis on ühendatud sidesõnaga, peab iga liige olema tõene. Kirjutame üles iga disjunktsiooni tõesed hulgad.
x /\ y/\¬w – (x=1, y=1, z=1, w=0) ja (x=1, y=1, z=0, w=0);
x /\¬y/\¬z/\¬w – x=1, y=1, z=0, w=0.
Selle tulemusena saame 6 ühikut.
№7 Loogiline funktsioon F on antud avaldisega
(x /\ y/\z/\¬w)\/ (x /\¬z/\¬w).
Stepan loetles kõik muutujate komplektid, mille puhul see avaldis on tõene. Mitu ühikut Stepan kirjutas? Oma vastuses kirjutage üles ainult täisarv - ühikute arv.
Näide. Olgu antud avaldis x → y, mis sõltub kahest muutujast x ja y. See avaldis kehtib kolme hulga kohta: (0, 0), (0, 1) ja (1, 1). Stepan kirjutas 3 ühikut.
Lahendus lahendusega sarnane.
№8 Loogiline funktsioon F on antud avaldisega
(¬x /\ ¬y/\z/\w)\/ (x /\z/\w).
Stepan loetles kõik muutujate komplektid, mille puhul see avaldis on tõene. Mitu ühikut Stepan kirjutas? Oma vastuses kirjutage üles ainult täisarv - ühikute arv.
Näide. Olgu antud avaldis x → y, mis sõltub kahest muutujast x ja y. See avaldis kehtib kolme hulga kohta: (0, 0), (0, 1) ja (1, 1). Stepan kirjutas 3 ühikut.
Lahendus lahendusega sarnane.
№9 Loogiline funktsioon F on antud avaldisega
(y /\ ¬z /\ ¬w) \/ (¬x /\ ¬y/\¬z/\w).
Stepan loetles kõik muutujate komplektid, mille puhul see avaldis on tõene. Mitu ühikut Stepan kirjutas? Oma vastuses kirjutage üles ainult täisarv - ühikute arv.
Näide. Olgu antud avaldis x → y, mis sõltub kahest muutujast x ja y. See avaldis kehtib kolme hulga kohta: (0, 0), (0, 1) ja (1, 1). Stepan kirjutas 3 ühikut.
Lahendus lahendusega sarnane.
№10 Loogiline funktsioon F on antud avaldisega
(x /\ y /\ ¬z) \/ (¬x /\ ¬y/\¬z).
Stepan loetles kõik muutujate komplektid, mille puhul see avaldis on tõene. Mitu ühikut Stepan kirjutas? Oma vastuses kirjutage üles ainult täisarv - ühikute arv.
Näide. Olgu antud avaldis x → y, mis sõltub kahest muutujast x ja y. See avaldis kehtib kolme hulga kohta: (0, 0), (0, 1) ja (1, 1). Stepan kirjutas 3 ühikut.
Lahendus lahendusega sarnane.
№11 Loogiline funktsioon F on antud avaldisega
¬((¬w/\x) → (y /\ z)) \/ ¬((x /\¬ y)→ (¬z\/¬w)).
Stepan loetles kõik muutujate komplektid, mille puhul see avaldis on tõene. Mitu ühikut Stepan kirjutas? Oma vastuses kirjutage üles ainult täisarv - ühikute arv.
Näide. Olgu antud avaldis x → y, mis sõltub kahest muutujast x ja y. See avaldis kehtib kolme hulga kohta: (0, 0), (0, 1) ja (1, 1). Stepan kirjutas 3 ühikut.
Lahendus
¬((¬w/\x) → (y /\ z)) – (x=1, y=1, z=0, w=0) ja (x=1, y=0, z=1, w =0);
¬((x /\¬ y)→ (¬z\/¬w)) – (x=1, y=0, z=1, w=1).
Selle tulemusena saame 5 ühikut.
№12 Loogiline funktsioon F on antud avaldisega
¬((¬x\/¬y) → (z\/ w)) \/ ¬((x \/ y)→ (z\/¬w)).
Stepan loetles kõik muutujate komplektid, mille puhul see avaldis on tõene. Mitu ühikut Stepan kirjutas? Oma vastuses kirjutage üles ainult täisarv - ühikute arv.
Näide. Olgu antud avaldis x → y, mis sõltub kahest muutujast x ja y. See avaldis kehtib kolme hulga kohta: (0, 0), (0, 1) ja (1, 1). Stepan kirjutas 3 ühikut.
Lahendus
Loogiline funktsioon F on tõene, kui vähemalt üks sulgudes olev avaldis on tõene. Kuna kõik muutujad neis on vihjatud, annab selle vääruse tingimus sulgude tõesuse. Näidet järgides kirjutame iga sulu jaoks üles tõesed hulgad.
¬((¬x\/¬y) → (z \/ w)) – (x=1, y=0, z=0, w=0) ja (x=0, y=1, z=0, w=0);
¬((x /\¬ y)→ (¬z\/¬w)) – (x=1, y=0, z=0, w=0).
Selle tulemusena saame 3 ühikut.
№13 Loogiline funktsioon F on antud avaldisega
¬(¬(x\/y) → (¬z\/ w)) \/ ¬(¬(x /\ y)→ (z\/¬w)).
Stepan loetles kõik muutujate komplektid, mille puhul see avaldis on tõene. Mitu ühikut Stepan kirjutas? Oma vastuses kirjutage üles ainult täisarv - ühikute arv.
Näide. Olgu antud avaldis x → y, mis sõltub kahest muutujast x ja y. See avaldis kehtib kolme hulga kohta: (0, 0), (0, 1) ja (1, 1). Stepan kirjutas 3 ühikut.
Lahendus
Loogiline funktsioon F on tõene, kui vähemalt üks sulgudes olev avaldis on tõene. Kuna kõik muutujad neis on vihjatud, annab selle vääruse tingimus sulgude tõesuse. Näidet järgides kirjutame iga sulu jaoks üles tõesed hulgad.
¬(¬(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) ja
(x=0, y=0, z=0, w=1).
Selle tulemusena saame 6 ühikut.
Loogiline funktsioon F on antud väljendiga x/\ ¬y/\ (¬z\/ w).
Joonisel on kujutatud funktsiooni tõesuse tabeli fragment F sisaldavad Kõik argumentide komplektid, mille jaoks funktsioon F tõsi.
Määrake, milline funktsiooni tõesuse tabeli veerg F iga muutuja vastab w, x, y, z.
Kirjutage oma vastusesse tähed w, x, y, z nende saabumise järjekorras
nende vastavad veerud (esimene – esimesele vastav täht
veerg; siis teisele veerule vastav täht jne) Tähed
Vastuses kirjutage ritta, ärge eraldage tähtede vahele.
pole tarvis.
Ühtse riigieksami 2017. aasta ühtse riigieksami demoversioon - ülesanne nr 2
Lahendus:
Konjunktsioon (loogiline korrutis) on tõene siis ja ainult siis, kui kõik väited on tõesed. Seetõttu muutuja X 1 .
Muutuv ¬y peavad vastama veerule, milles kõik väärtused on võrdsed 0 .
Kahe väite disjunktsioon (loogiline liitmine) on tõene siis ja ainult siis, kui vähemalt üks väide on tõene.
Disjunktsioon ¬z\/y z = 0, w=1.
Seega muutuja ¬z w vastab veerule muutujaga 4 (veerg 4).
Vastus: zyxw
Ühtse riigieksami ühtne riigieksam 2016 demoversioon – ülesanne nr 2
Loogiline funktsioon F on antud avaldisega (¬z)/\x \/ x/\y. Määrake, milline funktsiooni F tõesuse tabeli veerg vastab igale muutujale x, y, z.
Kirjutage oma vastuses tähed x, y, z nendele vastavate veergude ilmumise järjekorras (kõigepealt - 1. veerule vastav täht; seejärel - 2. veerule vastav täht; seejärel - 3. veerule vastav täht veerg) . Kirjutage vastuses olevad tähed ritta, tähtede vahele pole vaja eraldajaid panna.
Näide. Olgu antud avaldis x → y, mis sõltub kahest muutujast x ja y, ning tõesuse tabel:
Siis vastab 1. veerg muutujale y ja 2. veerg
vastab muutujale x. Vastusesse tuleb kirjutada: yx.
Lahendus:
1. Paneme selle kirja see väljend lihtsamas tähistuses:
¬z*x + x*y = x*(¬z + y)
2. Konjunktsioon (loogiline korrutamine) on tõene siis ja ainult siis, kui kõik väited on tõesed. Seega, et funktsioon ( F) oli võrdne ühega ( 1 ), peab iga tegur olema võrdne ühega ( 1 ). Seega, millal F=1, muutuv X peavad vastama veerule, milles kõik väärtused on võrdsed 1 .
3. Kaaluge (¬z + y), kell F=1 see avaldis on samuti võrdne 1-ga (vt punkt 2).
4. Kahe väite disjunktsioon (loogiline liitmine) on tõene siis ja ainult siis, kui vähemalt üks väide on tõene.
Disjunktsioon ¬z\/y selles reas on tõsi ainult siis, kui
- z = 0; y = 0 või y = 1;
- z = 1; y = 1
5. Seega muutuja ¬z vastab veerule muutujaga 1 (1 veerg), muutuja y
Vastus: zyx
KIM ühtne riigieksam 2016. aasta ühtne riigieksam (varajane periood)– ülesanne nr 2
Loogiline funktsioon F on antud avaldisega
(x /\ y /\¬z) \/ (x /\ y /\ z) \/ (x /\¬y /\¬z).
Joonisel on kujutatud funktsiooni F tõesuse tabeli fragment, mis sisaldab kõiki argumentide komplekte, mille puhul funktsioon F on tõene. Määrake, milline funktsiooni F tõesuse tabeli veerg vastab igale muutujale x, y, z.
Kirjutage oma vastuses tähed x, y, z nendele vastavate veergude ilmumise järjekorras (kõigepealt - esimesele veerule vastav täht; seejärel - teisele veerule vastav täht jne) Kirjutage tähed vastake reas, eraldajaid pole Seda pole vaja tähtede vahele panna.
R lahendus:
Kirjutame antud avaldise lihtsama tähistusega:
(x*y*¬z) + (x*y*z) + (x*¬y*¬z)=1
See avaldis on tõene, kui vähemalt üks (x*y*¬z), (x*y*z), (x*¬y*¬z) võrdub 1-ga. Side (loogiline korrutamine) on tõene siis ja ainult siis, kui kõik väited on tõesed.
Vähemalt üks neist disjunktsioonidest x*y*¬z; x*y*z; x*¬y*¬z on tõsi ainult siis, kui x=1.
Seega muutuja X vastab veerule muutujaga 2 (veerg 2).
Lase ja- muutuja 1, z- prem.3. Siis esimesel juhul x*¬y*¬z on teisel juhul tõsi x*y*¬z, ja kolmandas x*y*z.
Vastus: yxz
Sümbol F tähistab ühte järgmistest: loogilisi väljendeid kolmest argumendist: X, Y, Z. Avaldise F tõesuse tabeli fragment on antud (vt parempoolset tabelit). Milline avaldis vastab F-le?
| 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
Lahendus:
1) X ∧ Y ∧ Z = 1,0,1 = 0 (ei ühti 2. real)
2) ¬X ∨ Y ∨¬Z = ¬0 ∨ 0 ∨ ¬0 = 1+0+1 = 1 (ei sobi 1. real)
3) X ∧ Y ∨ Z = 0,1+0 = 0 (ei ühti 3. real)
4) X ∨ Y ∧ ¬Z (vastab 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
Vastus: 4
Antud fragment avaldise F tõesuse tabelist. Milline avaldis vastab F-le?
| 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
Lahendus:
1) (A → ¬B) ∨ C = (1 → ¬0) ∨ 0 = (1 → 1) + 0 = 1 + 0 = 1 (ei sobi 2. real)
2) (¬A ∨ B) ∧ C = (¬1 ∨ 0) ∧ 1 = (0+0).1 = 0 (ei ühti 3. real)
3) (A ∧ B) → C = (1 ∧ 0) → 0 = 0 → 0 = 1 (ei sobi 2. real)
4) (A ∨ B) → C (vastab F)
(A ∨ B) → C = (0 ∨ 1) → 1 = 1
(A ∨ B) → C = (1 ∨ 0) → 0 = 0
(A ∨ B) → C = (1 ∨ 0) → 1 = 1
Vastus: 4
Antakse loogiline avaldis, mis sõltub 6 loogilisest muutujast:
X1 ∨ ¬X2 ∨ X3 ∨ ¬X4 ∨ X5 ∨ X6
Kui palju on erinevaid muutujaväärtuste komplekte, mille puhul avaldis on tõene?
1) 1 2) 2 3) 63 4) 64
Lahendus:
Vale avaldis ainult ühel juhul: 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
Kokku on 2 6 = 64 valikut, mis tähendab tõene
Vastus: 63
Avaldise F tõesuse tabeli fragment on antud.
| 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 |
Milline avaldis vastab F-le?
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
Lahendus:
1) x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ x6 ∨ ¬x7 = 0 + 1 + … = 1 (ei sobi 1. real)
2) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ x7 = 0 + 0 + 0 + 0 + 0 + 1 + 0 = 1 (ei sobi 1. real)
3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7 = 1,0. ...= 0 (ei sobi 2. real)
4) x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 (vastab 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
Vastus: 4
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | F |
| 0 | 1 | 1 | ||||||
| 1 | 0 | 1 | 0 | |||||
| 1 | 0 | 1 |
Mis avaldis võib olla 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
Lahendus:
1) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8 = x1 . ¬x2. 0 . ... = 0 (ei sobi 1. real)
2) ¬x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ x8 (vastab F-le)
3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8 = … ¬x7 ∧ ¬x8 = … ¬1 ∧ ¬x8 = … 0 ¬1 ∧ ¬x8 = … 0 - rida)
4) ¬x1 ∨ ¬x2 ∨ ¬x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x8 = ¬x1 ∨ ¬x2 ∨ = ¬x2 ∨ ¬x1 = . 1 (mitte vasted 2. real)
Vastus: 2
Antud on fragment avaldise F tõesuse tabelist:
| 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 |
Leidke selle avaldise täielikust tõesuse tabelist minimaalne võimalik arv erinevaid ridu, milles väärtus x5 ühtib F-ga.
Lahendus:
Minimaalne võimalik arv erinevaid ridu, milles väärtus x5 vastab F = 4-le
Vastus: 4
Antud on fragment avaldise F tõesuse tabelist:
| 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 |
Leidke selle avaldise täielikust tõesuse tabelist maksimaalne võimalik arv erinevaid ridu, mille väärtus x6 ei ühti F-ga.
Lahendus:
Maksimaalne võimalik arv = 2 8 = 256
Maksimaalne võimalik arv erinevaid ridu, milles väärtus x6 ei ühti F = 256 – 5 = 251
Vastus: 251
Antud on fragment avaldise F tõesuse tabelist:
| 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 |
Leidke selle avaldise täieliku tõesuse tabeli maksimaalne võimalik arv erinevaid ridu, milles väärtus ¬x5 ∨ x1 ühtib F-ga.
Lahendus:
1+0=1 – ei ühti F-ga
0+0=0 – ei sobi F
0+0=0 – ei sobi F
0+1=1 – langeb kokku F-ga
1+0=1 – langeb kokku F-ga
2 7 = 128 – 3 = 125
Vastus: 125
Iga Boole'i avaldis A ja B sõltub samast 6 muutuja komplektist. Tõelisuse tabelites on kõigil neil avaldistel väärtuste veerus täpselt 4 ühikut. Kui suur on avaldise A ∨ B tõesuse tabeli väärtuste veerus minimaalne võimalik arv ühendeid?
Lahendus:
Vastus: 4
Iga Boole'i avaldis A ja B sõltub samast seitsme muutuja komplektist. Tõelisuse tabelites on kõigil neil avaldistel väärtuste veerus täpselt 4 ühikut. Kui suur on avaldise A ∨ B tõesuse tabeli väärtuste veerus maksimaalne võimalik arv ühendeid?
Lahendus:
Vastus: 8
Iga Boole'i avaldis A ja B sõltub samast 8 muutuja komplektist. Tõelisuse tabelites on kõigil neil avaldistel väärtuste veerus täpselt 5 ühikut. Kui suur on vähim võimalik nullide arv avaldise A ∧ B tõesuse tabeli väärtuste veerus?
Lahendus:
2 8 = 256 – 5 = 251
Vastus: 251
Iga Boole'i avaldis A ja B sõltub samast 8 muutuja komplektist. Tõelisuse tabelites on kõigil neil avaldistel väärtuste veerus täpselt 6 ühikut. Kui suur on maksimaalne võimalik nullide arv avaldise A ∧ B tõesuse tabeli väärtuste veerus?
Lahendus:
Vastus: 256
Boole'i avaldised A ja B sõltuvad mõlemad samast 5 muutuja komplektist. Mõlema avaldise tõesuse tabelis ei ole sobivaid ridu. Mitu neist sisaldub avaldise A ∧ B tõesuse tabeli väärtuste veerus?
Lahendus:
Mõlema avaldise tõesuse tabelis ei ole sobivaid ridu.
Vastus: 0
Boole'i avaldised A ja B sõltuvad mõlemad samast 6 muutuja komplektist. Mõlema avaldise tõesuse tabelis ei ole sobivaid ridu. Mitu neist sisaldub avaldise A ∨ B tõesuse tabeli väärtuste veerus?
Lahendus:
Vastus: 64
Kõik Boole'i avaldised A ja B sõltuvad samast seitsme muutuja komplektist. Mõlema avaldise tõesuse tabelis ei ole sobivaid ridu. Kui suur on maksimaalne võimalik nullide arv avaldise ¬A ∨ B tõesuse tabeli väärtuste veerus?
Lahendus:
A=1,B=0 => ¬0 ∨ 0 = 0 + 0 = 0
Vastus: 128
Iga Boole'i avaldis F ja G sisaldab 7 muutujat. Avaldiste F ja G tõesuse tabelites on täpselt 8 identset rida ja neist täpselt 5 väärtuste veerus on 1 Mitu rida avaldise F ∨ G kohta sisaldab väärtuste veerus 1 ?
Lahendus:
Seal on täpselt 8 identset rida ja täpselt 5 neist on väärtuste veerus 1.
See tähendab, et täpselt 3 neist on väärtuse veerus 0.
Vastus: 125
Loogiline funktsioon F on antud avaldisega (a ∧ ¬c) ∨ (¬b ∧ ¬c). Määrake, milline funktsiooni F tõesuse tabeli veerg vastab igale muutujale 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 |
Kirjutage oma vastuses tähed a, b, c nendele vastavate veergude ilmumise järjekorras.
Lahendus:
(a . ¬c) + (¬b . ¬c)
Kui c on 1, on F null, nii et viimane veerg on c.
Esimese ja teise veeru määramiseks saame kasutada 3. rea väärtusi.
(a . 1) + (¬b . 1) = 0
Vastus: ABC
Loogiline funktsioon F on antud avaldisega (a ∧ c)∨ (¬a ∧ (b ∨ ¬c)). Määrake, milline funktsiooni F tõesuse tabeli veerg vastab igale muutujale a, b, c.
Lähtudes sellest, et kui a=0 ja c=0, siis F=0, ning teise rea andmete põhjal võime järeldada, et kolmas veerg sisaldab b.
Vastus: takso
Loogiline funktsioon F on antud x ∧ (¬y ∧ z ∧ ¬w ∨ y ∧ ¬z). Joonisel on kujutatud funktsiooni F tõesuse tabeli fragment, mis sisaldab kõiki argumentide komplekte, mille puhul funktsioon F on tõene. Määrake, milline funktsiooni F tõesuse tabeli veerg vastab igale muutujale x, y, z, w.
| ? | ? | ? | ? | F |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
Kirjutage oma vastuses tähed x, y, z, w nendele vastavate veergude ilmumise järjekorras.
Lahendus:
x ∧ (¬y ∧ z ∧ ¬w ∨ y ∧ ¬z)
x. (¬y . z . ¬w . y . ¬z)
Lähtudes sellest, et x=0, siis F=0, võime järeldada, et teine veerg sisaldab x.
Vastus: wxzy
Kõigepealt määratleme, mis meil selles probleemis on:
- mingi avaldise abil defineeritud loogiline funktsioon F. Ülesandes esitatakse tabeli kujul ka selle funktsiooni tõesuse tabeli elemendid. Seega, kui asendada tabelist avaldisesse konkreetsed väärtused x, y, z, peaks tulemus ühtima tabelis toodud väärtusega (vt selgitust allpool).
- Muutujad x, y, z ja kolm neile vastavat veergu. Pealegi ei tea me selles ülesandes, milline veerg millisele muutujale vastab. See tähendab, et veerus Muutuja. 1 võib olla kas x, y või z.
- Meil palutakse määrata, milline veerg millisele muutujale vastab.
Vaatame näidet.
Lahendus
- Pöördume nüüd lahenduse juurde tagasi. Vaatame valemit lähemalt: \((\neg z) \wedge x \vee x\wedge y\)
- See sisaldab kahte konjunktsiooniga konstruktsiooni, mis on ühendatud disjunktsiooniga. Nagu teada, on disjunktsioon enamasti tõene (selleks piisab, kui üks terminitest on tõene).
- Vaatame siis hoolikalt neid ridu, kus avaldis F on väär.
- Esimene rida pole meile huvitav, kuna see ei määra, kus mis asub (kõik väärtused on samad).
- Vaatleme siis eelviimast rida, see sisaldab enamikku 1-st, kuid tulemus on 0.
- Kas z võib olla kolmandas veerus? Ei, sest sel juhul on valemis igal pool 1 ja seetõttu on tulemus võrdne 1-ga, kuid tõetabeli järgi on F väärtus selles reas 0. Seetõttu ei saa z olla Muutuv . 3.
- Samamoodi on meil eelmise rea puhul, et z ei saa olla Muutuv. 2.
- Seega z on muutuja. 1.
- Teades, et z on esimeses veerus, kaaluge kolmandat rida. Kas x võib olla teises veerus? Asendame väärtused:
\((\neg z) \wedge x \vee x\wedge y = \\ = (\neg 0) \wedge 1 \vee 1\wedge 0 = \\ = 1 \wedge 1 \vee 0 = \\ = 1 \vee 0 = 1\) - Tõetabeli järgi peab aga tulemus olema 0.
- Seega x ei saa olla Per. 2.
- Seega x on muutuja. 3.
- Seetõttu eemaldamise meetodi abil y on muutuv. 2.
- Seega on vastus järgmine: zyx (z - muutuja 1, y - muutuja 2, x - muutuja 3).
Ülesannete kataloog.
Kohustusliku etapiga saadete arv
Tehke nende ülesannete jaoks testid
Tagasi ülesannete kataloogi
MS Wordis printimiseks ja kopeerimiseks mõeldud versioon
Esitaja A16 teisendab ekraanile kirjutatud arvu.
Esinejal on kolm meeskonda, kellele on määratud numbrid:
1. Lisage 1
2. Lisage 2
3. Korrutage 2-ga
Esimene neist suurendab arvu ekraanil 1 võrra, teine suurendab seda 2 võrra, kolmas korrutab selle 2-ga.
Esitaja A16 programm on käskude jada.
Kui palju on programme, mis teisendavad algse arvu 3 arvuks 12 ja samal ajal sisaldab programmi arvutustee arv 10?
Programmi arvutustrajektoor on kõigi programmikäskude täitmise tulemuste jada. Näiteks programmi 132 algnumbriga 7 puhul koosneb trajektoor numbritest 8, 16, 18.
Lahendus.
Nõutav programmide arv võrdub nende programmide arvu korrutisega, mis saavad arvust 3 arvu 10, nende programmide arvuga, mis saavad arvust 10 arvu 12.
Olgu R(n) programmide arv, mis teisendavad arvu 3 arvuks n, ja P(n) nende programmide arv, mis teisendavad arvu 10 arvuks n.
Kõigi n > 5 korral kehtivad järgmised seosed:
1. Kui n ei jagu 2-ga, siis R(n) = R(n - 1) + R(n - 2), kuna n - saamiseks on kaks võimalust ühe või kahe liitmise teel. Samamoodi P(n) = P(n-1) + P(n-2)
2. Kui n jagub 2-ga, siis R(n) = R(n - 1) + R(n - 2) + R(n / 2). Samamoodi P(n) = P(n-1) + P(n-2) + P(n/2)
Arvutame järjestikku R(n) väärtused:
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
Nüüd arvutame P(n) väärtused:
P(11) = P(10) = 1
P(12) = P(11) + P(10) = 2
Seega on ülesande tingimustele vastavate programmide arv 30 · 2 = 60.
Vastus: 60.
Vastus: 60
Allikas: arvutiteaduse ühtse riigieksami 2017 demoversioon.
1. Lisage 1
2. Lisage 3
Kui palju on selliseid programme, mille algarvu 1 korral on tulemuseks arv 17 ja samas on arvutustee arv 9? Programmi arvutustrajektoor on kõigi programmikäskude täitmise tulemuste jada. Näiteks programmi 121 algnumbriga 7 puhul koosneb trajektoor numbritest 8, 11, 12.
Lahendus.
Kasutame dünaamilise programmeerimise meetodit. loome massiivi dp, kus dp[i] on arvu i arvu i saamiseks selliste käskude abil.
Dünaamika alus:
Ülemineku valem:
dp[i]=dp + dp
See ei võta arvesse 9-st suuremate arvude väärtusi, mida saab saada arvudest, mis on väiksemad kui 9 (jättes seega vahele 9 trajektoori):
Vastus: 169.
Vastus: 169
Allikas: Arvutiteaduse õppetöö, 11. hinne 29. november 2016 Valik IN10203
Esitaja May17 teisendab ekraanil oleva numbri.
Esinejal on kaks meeskonda, kellele on määratud numbrid:
1. Lisage 1
2. Lisage 3
Esimene käsk suurendab arvu ekraanil 1 võrra, teine suurendab seda 3 võrra. 17. mai täitja programm on käskude jada.
Kui palju on selliseid programme, mille algarvu 1 korral on tulemuseks arv 15 ja samas on arvutustrajektooril arv 8? Programmi arvutustrajektoor on kõigi programmikäskude täitmise tulemuste jada. Näiteks programmi 121 algnumbriga 7 puhul koosneb trajektoor numbritest 8, 11, 12.
Lahendus.
Kasutame dünaamilise programmeerimise meetodit. Loome massiivi dp, kus dp[i] on arvu i selliste käskude abil arvu i saamiseks.
Dünaamika alus:
Ülemineku valem:
dp[i]=dp + dp
Kuid see ei võta arvesse numbreid, mis on suuremad kui 8, kuid nendeni saame jõuda väärtusest, mis on väiksem kui 8. Järgnevalt kuvatakse väärtused lahtrites dp vahemikus 1 kuni 15: 1 1 1 2 3 4 6 9 9 9 18 27 36 54 81 .
