Looginen funktio F saadaan lausekkeella. Logiikka ja tosijoukot. Ratkaisut 1 Looginen funktio f on annettu x:llä

Tehtäväluettelo.
Pakollisen vaiheen sisältävien ohjelmien määrä

Lajittelu Perus Ensimmäinen yksinkertainen Ensimmäinen monimutkainen Suosio Ensimmäinen uusi Ensimmäinen vanha
Tee testit näistä tehtävistä
Palaa tehtäväluetteloon
Versio tulostamista ja kopiointia varten MS Wordissa

Esittäjä A16 muuntaa näytölle kirjoitetun luvun.

Esiintyjällä on kolme joukkuetta, joille on annettu numerot:

1. Lisää 1

2. Lisää 2

3. Kerro 2:lla

Ensimmäinen niistä lisää näytöllä näkyvää lukua yhdellä, toinen lisää sitä kahdella, kolmas kertoo sen 2:lla.

Ohjelma esiintyjälle A16 on komentosarja.

Kuinka monta ohjelmaa on olemassa, joka muuntaa alkuperäisen luvun 3 luvuksi 12 ja samalla ohjelman laskentarata sisältää luvun 10?

Ohjelman laskentarata on kaikkien ohjelman komentojen suorittamisen tulosten sarja. Esimerkiksi ohjelmassa 132, jonka alkunumero on 7, lentorata koostuu numeroista 8, 16, 18.

Ratkaisu.

Vaadittu ohjelmien määrä on yhtä suuri kuin niiden ohjelmien määrän tulo, jotka saavat luvun 10 luvusta 3, niiden ohjelmien lukumäärällä, jotka saavat luvun 12 luvusta 10.

Olkoon R(n) niiden ohjelmien lukumäärä, jotka muuttavat luvun 3 luvuksi n, ja P(n) niiden ohjelmien lukumäärä, jotka muuttavat luvun 10 luvuksi n.

Kaikille n > 5:lle seuraavat suhteet ovat tosia:

1. Jos n ei ole jaollinen kahdella, niin R(n) = R(n - 1) + R(n - 2), koska on kaksi tapaa saada n - lisäämällä yksi tai lisäämällä kaksi. Samoin P(n) = P(n - 1) + P(n - 2)

2. Jos n on jaollinen kahdella, niin R(n) = R(n - 1) + R(n - 2) + R(n / 2). Samoin P(n) = P(n-1) + P(n-2) + P(n/2)

Lasketaan peräkkäin R(n):n arvot:

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

Lasketaan nyt P(n):n arvot:

P(11) = P(10) = 1

P(12) = P(11) + P(10) = 2

Siten ongelman ehdot täyttävien ohjelmien määrä on 30 · 2 = 60.

Vastaus: 60.

Vastaus: 60

Lähde: Tietojenkäsittelytieteen Unified State Exam 2017 -demoversio.

1. Lisää 1

2. Lisää 3

Kuinka monta ohjelmaa on olemassa, jolle lähtöluvulla 1 saadaan luku 17 ja samalla laskentarata sisältää luvun 9? Ohjelman laskentarata on kaikkien ohjelman komentojen suorittamisen tulosten sarja. Esimerkiksi ohjelmassa 121, jonka alkunumero on 7, lentorata koostuu numeroista 8, 11, 12.

Ratkaisu.

Käytämme dynaamista ohjelmointimenetelmää. luodaan taulukko dp, jossa dp[i] on kuinka monta tapaa saada numero i tällaisilla komennoilla.

Dynamiikka perusta:

Siirtymäkaava:

dp[i]=dp + dp

Tässä ei oteta huomioon arvoja 9:tä suuremmille numeroille, jotka voidaan saada alle 9:n luvuista (jolloin 9:n lentorata ohitetaan):

Vastaus: 169.

Vastaus: 169

Lähde: Tietojenkäsittelytieteen koulutustyö, luokka 11 29.11.2016 Vaihtoehto IN10203

Esiintyjä May17 muuntaa näytöllä olevan numeron.

Esiintyjällä on kaksi joukkuetta, joille on annettu numerot:

1. Lisää 1

2. Lisää 3

Ensimmäinen komento suurentaa näytöllä näkyvää lukua yhdellä, toinen kolmella. Toukokuun 17. päivän esiintyjän ohjelma on komentosarja.

Kuinka monta ohjelmaa on olemassa, jolle lähtöluvulla 1 saadaan luku 15 ja samalla laskentapolu sisältää luvun 8? Ohjelman laskentarata on kaikkien ohjelman komentojen suorittamisen tulosten sarja. Esimerkiksi ohjelmassa 121, jonka alkunumero on 7, lentorata koostuu numeroista 8, 11, 12.

Ratkaisu.

Käytämme dynaamista ohjelmointimenetelmää. Luodaan taulukko dp, jossa dp[i] on kuinka monta tapaa saada luku i tällaisilla komennoilla.

Dynamiikka perusta:

Siirtymäkaava:

dp[i]=dp + dp

Mutta tämä ei ota huomioon lukuja, jotka ovat suurempia kuin 8, mutta voimme päästä niihin arvosta, joka on pienempi kuin 8. Seuraavassa näytetään arvot soluissa dp välillä 1-15: 1 1 1 2 3 4 6 9 9 9 18 27 36 54 81 .

Demoversioprojektin Unified State Exam 2017 tietojenkäsittelytieteen tehtävän 2 analyysi. Tämä on perusvaikeustason tehtävä. Arvioitu aika tehtävän suorittamiseen on 3 minuuttia.

Testatut sisältöelementit: kyky rakentaa totuustaulukoita ja loogisia piirejä. Unified State Exam -kokeessa testatut sisältöelementit: lauseet, loogiset operaatiot, kvantisoijat, väittämien totuus.

Tehtävä 2:

Logiikka toiminto F annetaan lausekkeella x /\¬ y /\ (¬ z \/ w).
Kuvassa on fragmentti funktion totuustaulukosta F sisältävät Kaikki F totta.
Selvitä mikä funktion totuustaulukon sarake F jokainen muuttuja vastaa w, x, y, z.

Kirjoita vastaukseesi kirjaimet w, x, y, z siinä järjestyksessä, jossa vastaavat sarakkeet ilmestyvät (ensin - ensimmäistä saraketta vastaava kirjain; sitten - toista saraketta vastaava kirjain jne.) Kirjoita vastauksen kirjaimet riville, ei tarvitse laittaa mitään erottimet kirjainten välillä.

Esimerkki. Jos funktio annettaisiin lausekkeella ¬ x \/ y, riippuen kahdesta muuttujasta: x Ja y, ja sen totuustaulukosta annettiin fragmentti, joka sisälsi Kaikki joukko argumentteja, joille funktio F totta.

Tällöin ensimmäinen sarake vastaisi muuttujaa y, ja toinen sarake on muuttuja x. Vastauksen olisi pitänyt kirjoittaa: yx.

Vastaus: ________

x /\¬ y /\ (¬ z \/ w)

Konjunktio (looginen kertolasku) on tosi silloin ja vain, jos kaikki lauseet ovat tosia. Siksi muuttuja X 1 .

Näin ollen muuttuja x vastaa saraketta, jossa on muuttuja 3.

Muuttuva ¬y arvon sisältävän sarakkeen on vastattava 0 .

Kahden lauseen disjunktio (looginen lisäys) on tosi, jos ja vain jos ainakin yksi lause on tosi.
Disjunktio ¬z\/w tässä rivissä on totta vain, jos z = 0, w=1.

Näin ollen muuttuja ¬z vastaa saraketta, jossa on muuttuja 1 (1 sarake), muuttuja w vastaa saraketta, jossa on muuttuja 4 (sarake 4).

Määritellään ensin, mitä meillä on ongelmassa:

jollakin lausekkeella määritelty looginen funktio F. Myös tämän funktion totuustaulukon elementit esitetään tehtävässä taulukon muodossa. Siten, kun korvataan tietyt x, y, z:n arvot taulukosta lausekkeeseen, tuloksen tulee olla sama kuin taulukossa annettu (katso selitys alla).
Muuttujat x, y, z ja niitä vastaavat kolme saraketta. Lisäksi tässä tehtävässä emme tiedä mikä sarake vastaa mitäkin muuttujaa. Eli sarakkeessa Muuttuja. 1 voi olla joko x, y tai z.
Meitä pyydetään määrittämään, mikä sarake vastaa mitäkin muuttujaa.

Katsotaanpa esimerkkiä.

Ratkaisu

Palataan nyt ratkaisuun. Katsotaanpa kaavaa tarkemmin: \((\neg z) \wedge x \vee x\wedge y\)
Siinä on kaksi rakennetta, joissa konjunktio on yhdistetty disjunktiolla. Kuten tiedetään, disjunktio on useimmiten tosi (tälle riittää, että yksi termeistä on tosi).
Katsotaan sitten huolellisesti rivejä, joilla lauseke F on epätosi.
Ensimmäinen rivi ei ole meille kiinnostava, koska se ei määritä missä mikä on (kaikki arvot ovat samat).
Tarkastellaan sitten toiseksi viimeistä riviä, se sisältää suurimman osan luvusta 1, mutta tulos on 0.
Voiko z olla kolmannessa sarakkeessa? Ei, koska tässä tapauksessa kaavassa on kaikkialla ykkösiä, ja siksi tulos on yhtä suuri kuin 1, mutta totuustaulukon mukaan F:n arvo tällä rivillä on 0. Siksi z ei voi olla muuttuja . 3.
Samoin edellisen rivin kohdalla z ei voi olla muuttuja. 2.
Siten, z on muuttuva. 1.
Kun tiedät, että z on ensimmäisessä sarakkeessa, harkitse kolmatta riviä. Voiko x olla toisessa sarakkeessa? Korvataan arvot:
\((\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\)
Totuustaulukon mukaan tuloksen on kuitenkin oltava 0.
Siten, x ei voi olla Per. 2.
Siten, x on muuttuja. 3.
Siksi eliminointimenetelmällä y on muuttuva. 2.
Siten vastaus on seuraava: zyx (z - muuttuja 1, y - muuttuja 2, x - muuttuja 3).

Työn lähde: Ratkaisu 2437. Unified State Exam 2017. Tietojenkäsittelytiede. V.R. Leschiner. 10 vaihtoehtoa.

Tehtävä 2. Looginen funktio F saadaan lausekkeella . Määritä mikä funktion F totuustaulukon sarake vastaa kutakin muuttujaa x, y, z.

Kirjoita vastauksessasi kirjaimet x, y, z siinä järjestyksessä, jossa niitä vastaavat sarakkeet esiintyvät (ensin - ensimmäistä saraketta vastaava kirjain, sitten - toista saraketta vastaava kirjain, sitten - kolmatta saraketta vastaava kirjain sarake). Kirjoita vastauksen kirjaimet peräkkäin, kirjainten väliin ei tarvitse laittaa erottimia.

Ratkaisu.

Kirjoitetaan F:n lauseke uudelleen ottaen huomioon negaatio-, konjunktio- ja disjunktiooperaatioiden prioriteetit:

Tarkastellaan taulukon 4. riviä (1,1,0)=0. Tästä nähdään, että kolmannen paikan tulee olla joko muuttuja y tai muuttuja z, muuten toisessa sulussa on 1, joka johtaa arvoon F=1. Tarkastellaan nyt taulukon 5. riviä (0,0,1)=1. Koska x:n on oltava ensimmäisellä tai toisella paikalla, ensimmäinen sulkumerkki antaa arvon 1 vain, kun y on 3. sijalla. Ottaen huomioon, että toinen hakasuluke on aina yhtä suuri kuin 0, saadaan F=1 ensimmäisen hakasulkeen 1:n ansiosta. Näin ollen havaitsimme, että y on 3. sijalla. Tarkastellaan lopuksi taulukon 7. riviä (1,0,1)=0. Tässä y=1 ja F=0:lle on oltava z=0 ja x=1, joten x on ensimmäisellä paikalla ja z toisella.

№1

(x /\ y/\z/\¬w)\/ (x /\ y/\¬z/\¬w)\/ (x /\¬ y/\¬z/\¬w).

Ratkaisu

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.
Tuloksena saamme 6 yksikköä.
Vastaus: 6.

№2 Looginen funktio F saadaan lausekkeella

(¬x /\ y/\¬z/\w)\/ (x /\ y/\z/\¬w)\/ (x /\¬ y/\¬z/\w).

Stepan listasi kaikki muuttujajoukot, joille tämä lauseke on tosi. Kuinka monta yksikköä Stepan kirjoitti? Kirjoita vastauksessasi vain kokonaisluku - yksiköiden lukumäärä.