18 tehtävän tentti tietojenkäsittelytieteen ratkaisutekniikka

Tiedetään, että ilmaisu

((x ∈ A) → (x ∈ P)) ∧ ((x ∈ Q) → ¬(x ∈ A))

true (eli ottaa arvon 1) mille tahansa muuttujan x arvolle. Määritä suurin mahdollinen määrä elementtejä joukossa A.

Ratkaisu.

Otetaan käyttöön merkintä:

(x ∈ P) ≡ P; (x ∈ Q) ≡ Q; (x ∈ A) ≡ A; ∧ ≡ ; ∨ ≡ +.

Sitten implikaatiomuunnosa soveltamalla saamme:

(¬A + P) (¬Q + ¬A) ⇔ ¬A ¬Q + ¬Q P + ¬A + ¬A P ⇔

⇔ ¬A (¬Q + P + 1) + ¬Q P ⇔ ¬A + ¬Q P.

Vaaditaan, että ¬A + ¬Q · P = 1. Lauseke ¬Q · P on tosi, kun x ∈ (2, 4, 8, 10, 14, 16, 20). Silloin ¬A:n on oltava tosi, kun x ∈ (1, 3, 5, 6, 7, 9, 11, 12, 13, 15, 17, 18, 19, 21, 22, 23,...).

Siksi joukon A alkioiden enimmäismäärä on, jos A sisältää kaikki joukon ¬Q · P alkiot, tällaisia ​​alkioita on seitsemän.

Vastaus: 7.

Vastaus: 7

A-joukon alkiot ovat luonnollisia lukuja. Tiedetään, että ilmaisu

(x (2, 4, 6, 8, 10, 12)) → (((x (3, 6, 9, 12, 15)) ∧ ¬(x A)) → ¬(x (2, 4, 6) , 8, 10, 12)))

Ratkaisu.

Otetaan käyttöön merkintä:

(x ∈ (2, 4, 6, 8, 10, 12)) ≡ P; (x ∈ (3, 6, 9, 12, 15)) ≡ Q; (x ∈ A) ≡ A.

Muuntamalla saamme:

P → ((Q ∧ ¬A) → ¬P) = P → (¬(Q ∧ ¬A) ∨ ¬P) = ¬P ∨ (¬(Q ∧ ¬A) ∨ ¬P) = ¬P ∨ ¬Q ∨ A.

Looginen TAI on tosi, jos ainakin yksi lauseista on tosi. Lauseke ¬P ∨ ¬Q on totta kaikille x:n arvoille paitsi arvoille 6 ja 12. Siksi välissä A on oltava pisteet 6 ja 12. Eli välin A pienin pistejoukko ≡ (6, 12). A-joukon alkioiden summa on 18.

Vastaus: 18.

Vastaus: 18

Joukkojen A, P, Q alkiot ovat luonnollisia lukuja ja P = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20), Q = (3, 6, 9, 12, 15, 18, 21, 24, 27, 30).

Tiedetään, että ilmaisu

tosi (eli ottaa arvon 1) mille tahansa muuttujan x arvolle. Määritä joukon A alkioiden summan pienin mahdollinen arvo.

Ratkaisu.

Yksinkertaistetaan:

¬(x P) ∨ ¬(x Q) antaa 0 vain, kun luku on molemmissa joukoissa. Tämä tarkoittaa, että jotta koko lauseke olisi tosi, meidän on asetettava kaikki P:n ja Q:n luvut A:ssa. Tällaiset luvut ovat 6, 12, 18. Niiden summa on 36.

Vastaus: 36.

Vastaus: 36

Lähde: INFORMATIIKAn koulutustyö 11. 18. tammikuuta 2017 Vaihtoehto IN10304

Joukkojen A, P, Q alkiot ovat luonnollisia lukuja ja P = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20), Q = (3, 6, 9, 12, 15, 18, 21, 24, 27, 30).

Tiedetään, että lauseke ((x A) → (x P)) ∨ (¬(x Q) → ¬(x A))

tosi (eli ottaa arvon 1) mille tahansa muuttujan x arvolle.

Määritä suurin mahdollinen määrä elementtejä joukossa A.

Ratkaisu.

Muunnetaan tämä lauseke:

((x A) → (x P)) ∨ ((x Q) → (x A))

((x A) ∨ (x P)) ∨ ((x Q) ∨ (x A))

(x A) ∨ (x P) ∨ (x Q)

Elementin on siis oltava joko P:ssä tai Q:ssa tai ei A:ssa. Siten vain elementit P:stä ja Q:sta voivat olla A:ssa. Ja yhteensä näissä kahdessa joukossa on 17 ei-toistuvaa elementtiä.

Vastaus: 17

Joukkojen A, P, Q alkiot ovat luonnollisia lukuja ja P = (1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21), Q = (3, 6, 9, 12, 15, 18, 21, 24, 27, 30). Tiedetään, että ilmaisu

((x P) → (x A)) ∨ (¬(x A) → ¬(x Q))

tosi (eli ottaa arvon 1) mille tahansa muuttujan x arvolle. Määritä joukon A alkioiden summan pienin mahdollinen arvo.

Ratkaisu.

Tutkitaan kahta vaikutusta. Saamme:

(¬(x P) ∨ (x A)) ∨ ((x A) ∨ ¬(x Q))

Yksinkertaistetaan:

(¬(x P) ∨ (x A) ∨ ¬(x Q))

¬(x P) ∨ ¬(x Q) antaa 0 vain, kun luku on molemmissa joukoissa. Tämä tarkoittaa, että jotta koko lauseke olisi tosi, sinun on asetettava kaikki P:n ja Q:n luvut A:ksi. Tällaisia ​​lukuja ovat 3, 9, 15 ja 21. Niiden summa on 48.

Vastaus: 48.

Vastaus: 48

Lähde: INFORMATIIKAn koulutustyö 11. 18. tammikuuta 2017 Vaihtoehto IN10303

Ja ilme

(y + 2x 30) ∨ (y > 20)

x ja y?

Ratkaisu.

Huomaa, että tämän lausekkeen identtiselle totuudelle lauseke (y + 2x vastaus: 81.

Vastaus: 81

Lähde: USE - 2018. Early wave. Vaihtoehto 1., KÄYTTÖ - 2018. Varhainen aalto. Vaihtoehto 2.

Lukuviivalla on jana A. Tiedetään, että kaava

((x ∈ A) → (x2 ≤ 100)) ∧ ((x2 ≤ 64) → (x ∈ A))

on identtisesti totta kaikille todellisille x. Mikä on segmentin A lyhin pituus?

Ratkaisu.

Laajentamalla implikaatiota säännön A → B = ¬A + B mukaan, korvaamalla looginen summa joukolla ja looginen tulo relaatiojärjestelmällä, määritämme parametrin arvot MUTTA, jonka mukaan perintäjärjestelmä

on ratkaisut mille tahansa reaaliluvulle.

Jotta järjestelmän ratkaisut olisivat kaikki reaalilukuja, on välttämätöntä ja riittävää, että jokaisen joukon ratkaisut ovat kaikki reaalilukuja.

Epäyhtälön ratkaisut ovat kaikki lukuja segmentistä [−10; kymmenen]. Jotta kokoelma pätee kaikkiin reaalilukuihin, luvut x, jotka eivät sijaitse määritetyllä segmentillä, täytyy kuulua segmenttiin A. Siksi segmentti A ei saa ylittää segmenttiä [−10; kymmenen].

Samoin epäyhtälön ratkaisut ovat luvut säteistä ja Jotta joukko pätee kaikille reaaliluvuille, luvut x, joka ei makaa osoitetuilla säteillä, täytyy olla segmentillä A. Siksi segmentin A tulee sisältää segmentti [−8; kahdeksan].

Siten segmentin A pienin pituus voi olla 8 + 8 = 16.

Vastaus: 16.

Vastaus: 16

A ilmaisu

(y + 2x ≠ 48) ∨ (A x) ∨ ( x y)

identtisesti totta, eli se saa arvon 1 kaikille ei-negatiivisille kokonaisluvuille x ja y?

Ratkaisu.

A x ja y, harkitse missä tapauksissa ehdot ( y + 2x≠ 48) ja ( x y) ovat vääriä.

y = 48 − 2x) ja (x ≥ y). se x 16-24 välillä y välillä 0 - 16. Huomaa, että jotta lauseke sopisi mihin tahansa x ja y, se on otettava x= 16 ja y= 16. Sitten A A tulee olemaan 15.

Vastaus: 15.

Vastaus: 15

Lähde: USE in Informatics 28.5.2018. Pääaalto, A. Imaevin variantti - "Kotolis".

Mikä on suurin ei-negatiivinen kokonaisluku A ilmaisu

(y + 2x ≠ 48) ∨ (A x) ∨ ( A y)

identtisesti totta, eli se saa arvon 1 kaikille ei-negatiivisille kokonaisluvuille x ja y?

Ratkaisu.

Suurimman ei-negatiivisen kokonaisluvun löytäminen A, jossa lauseke on x ja y, harkitse missä tapauksissa ehto ( y + 2x≠ 48) on väärä.

Siten löydämme kaikki ratkaisut, kun ( y = 48 − 2x). se x 0 ja 24 välillä y välillä 48 - 0. Huomaa, että jotta lauseke sopisi mihin tahansa x ja y, se on otettava x= 16 ja y= 16. Sitten A A tulee olemaan 15.

Vastaus: 15.

Vastaus: 15

Lähde: Demoversio USE-2019:stä informatiikassa.

Mikä on pienin ei-negatiivinen kokonaisluku A ilmaisu

(2x + 3y > 30) ∨ (x + y ≤ A)

pätee samalla tavalla kaikille ei-negatiivisille kokonaisluvuille x ja y?

Ratkaisu.

A, jonka alla lauseke on identtisesti totta mille tahansa kokonaisluvulle, joka ei ole negatiivinen x ja yy + 2x> 30) on väärä.

y + 2x≤ 30). se x välillä 0 ja 15 ja y välillä 10 - 0. Huomaa, että jotta lauseke sopisi mille tahansa x ja y, se on otettava x= 15 ja y= 0. Sitten 15 + 0 ≤ A. Siksi pienin kokonaisluku ei-negatiivinen luku A on yhtä suuri kuin 15.

Vastaus: 15.

Vastaus: 15

Mikä on suurin ei-negatiivinen kokonaisluku A ilmaisu

(2x + 3y x + y ≥ A)

pätee samalla tavalla kaikille ei-negatiivisille kokonaisluvuille x ja y?

Ratkaisu.

Suurimman ei-negatiivisen kokonaisluvun löytäminen A, jonka alla lauseke on identtisesti totta mille tahansa kokonaisluvulle, joka ei ole negatiivinen x ja y, harkitse, missä tapauksissa ehto (3 y + 2x Siten löydämme kaikki ratkaisut, kun (3 y + 2x≥ 30). se x yli 15 ja y suurempi kuin 10. Huomaa, että jotta lauseke olisi sopiva mille tahansa x ja y, se on otettava x= 0 ja y= 10. Sitten 0 + 10 ≤ A. Siksi suurin ei-negatiivinen kokonaisluku A on yhtä suuri kuin 10.

Vastaus: 10.

Vastaus: 10

Mikä on pienin ei-negatiivinen kokonaisluku A ilmaisu

(3x + 4y ≠ 70) ∨ (A > x) ∨ (A > y)

pätee samalla tavalla kaikille ei-negatiivisille kokonaisluvuille x ja y?

Ratkaisu.

Pienimmän ei-negatiivisen kokonaisluvun etsiminen A, jonka alla lauseke on identtisesti totta mille tahansa kokonaisluvulle, joka ei ole negatiivinen x ja y, harkitse, missä tapauksissa ehto (3 x + 4y≠ 70) on väärä.

Siten löydämme kaikki ratkaisut, kun (3 x + 4y= 70). se x 2 ja 22 välillä y välillä 16 - 1. Huomaa, että jotta lauseke sopisi mihin tahansa x ja y, se on otettava x= 10 ja y= 10. Sitten A> 10. Siksi pienin ei-negatiivinen kokonaisluku A on yhtä suuri kuin 11.

Tämän ongelman ratkaisemiseksi meidän on tehtävä joitain loogisia johtopäätöksiä, joten "varo käsiäsi".

1. He haluavat meidän löytävän minimin ei-negatiivinen kokonaisluku A, jolle lauseke on aina tosi.
2. Mikä on ilmaisu kokonaisuudessaan? jotain siellä seuraamus jotain suluissa.
3. Muistetaanpa totuustaulukko implikaatiota varten:
   1 => 1 = 1
   1 => 0 = 0
   0 => 1 = 1
   0 => 0 = 1
4. On siis kolme mahdollisuutta, milloin tämä on totta. Kaikkien näiden kolmen vaihtoehdon harkitseminen on tappaa itsesi ja olla elämättä. Mietitään, voimmeko mennä "päinvastaisesta".
5. Sen sijaan, että etsimme A:ta, yritetään löytää x, jolle tämä lauseke on epätosi.
6. Otetaan siis jokin luku A (emme vielä tiedä mikä, vain osa). Jos yhtäkkiä löydämme sellaisen x:n, jonka koko väite on epätosi, niin valittu A on huono (koska ehto edellyttää, että lauseke on aina tosi)!
7. Siten voimme saada jonkinlaisen rajoituksen numerolle A.
8. Joten mennään päinvastoin ja muistetaan, milloin implikaatio on väärä? Kun ensimmäinen osa on totta ja toinen osa on epätosi.
9. Keinot
   \((\mathrm(x)\&25\neq 0)= 1 \\ (\mathrm(x)\&17=0\Rightarrow \mathrm(x)\&\mathrm(A)\neq 0) = 0\)
10. Mitä tarkoittaa, että \((x\&25\neq 0) = 1\) ? Tämä tarkoittaa, että todellakin \(\mathrm(x)\&25\neq 0\) .
11. Muunnetaan 25 binääriksi. Saamme: 11001 2 .
12. Mitä rajoituksia tämä asettaa x:lle? Koska se ei ole yhtä suuri kuin nolla, se tarkoittaa, että bittikohtaisella konjunktiolla yksikkö on hankittava jostain. Mutta missä hän voisi olla? Vain siellä, missä on jo yksikkö 25:ssä!
13. Tämä tarkoittaa, että numerossa x vähintään yhden ristin tulee sisältää yksikkö: XXX.
14. Ok, harkitse nyt toista kerrointa: \((\mathrm(x)\&17=0\Rightarrow \mathrm(x)\&\mathrm(A)\neq 0) = 0\)
15. Tämä ilmaisu on myös implikaatio. Se on kuitenkin yhtä valheellista.
16. Siksi sen ensimmäisen osan on oltava totta ja toisen on oltava epätosi.
17. Keinot
    \((\mathrm(x)\&17=0) = 1 \\ ((\mathrm(x)\&\mathrm(A)\neq 0) = 0) = 0\)
18. Mitä \(\mathrm(x)\&17=0\) tarkoittaa? Se, että kaikissa paikoissa, joissa luvussa 17 on ykkösiä, x:ssä täytyy olla nollia (muuten tulos ei ole 0).
19. Muunnetaan 17 binääriarvoksi: 10001 2 . Tämä tarkoittaa, että x:ssä, lopun viimeisessä paikassa ja lopusta viidennessä paikassa, on oltava nollia.
20. Mutta pysähdymme, olemme kohdan 13 viimeisenä TAI 4 lopusta TAI 5 lopusta pitäisi olla yksi.
21. Koska rivin 19 mukaan yksikköä ei voi olla viimeisessä tai 5:ssä päätepaikoista, niin se täytyy olla 4. sija lopusta.
22. Toisin sanoen, jos haluamme, että koko lauseke on epätosi x:llämme, niin 4. sijan lopusta on oltava yksi: XX...XX1XXX 2 .
23. Ok, katsotaan nyt viimeistä ehtoa: \((\mathrm(x)\&\mathrm(A)\neq 0) = 0\). Mitä tämä tarkoittaa?
24. Tämä tarkoittaa, että se ei ole totta \(\mathrm(x)\&\mathrm(A)\neq 0\).
25. Eli itse asiassa \(\mathrm(x)\&\mathrm(A)=0\) .
26. Mitä tiedämme x:stä? Että 4:ssä paikan päästä on yksikkö. Kaikissa muissa suhteissa x voi olla melkein mikä tahansa.
27. Jos haluamme alkuperäisen lausekkeen olevan aina tosi, niin me ei pitäisi löytyä x, joka täyttää kaikki ehdot. Todellakin, jos löytäisimme sellaisen x:n, kävisi ilmi, että alkuperäinen lauseke ei aina ole totta, mikä on ristiriidassa ongelman ehdon kanssa.
28. Tämä tarkoittaa, että tätä viimeistä ehtoa ei yksinkertaisesti saa täyttää.
29. Miten sitä ei voida tehdä? Jos vain olemme 100% varmoja, että bittikonjunktiolla yksikkö jää jonnekin.
30. Ja tämä on mahdollista: jos A:ssa on myös lopusta 4. sijalla oleva yksikkö, niin bittikohtaisen konjunktion seurauksena yksikkö jää lopusta 4. sijalle.
31. Mikä on pienin mahdollinen binääriluku, jolla on 1 kertaa 4 paikan lopusta? Ilmeisesti 1000 2. Joten tämä numero on vastaus.
32. Jää vain muuntaa se desimaaliksi: \(1000_2=0\kertaa 2^0 + 0\kertaa 2^1 + 0\kertaa 2^2 + 1\kertaa 2^3=8\)

Vastaus: pienin mahdollinen A, joka täyttää ehdot, vastaa 8.

Jevgeni Smirnov

Tietotekniikan asiantuntija, tietojenkäsittelytieteen opettaja

Ratkaisu #2

Hieman lyhyempää lähestymistapaa voidaan ehdottaa. Merkitään lauseemme F = (A->(B->C)), missä A on lause "X&25 ei ole yhtä suuri kuin 0", B= "X&17=0" ja C="X&A ei ole yhtä suuri kuin 0 ".

Laajennetaan implikaatioita käyttämällä tunnettua lakia X->Y = ei(X) TAI Y, saadaan F = A -> (not(B) TAI C) = not(A) TAI ei(B) TAI C. Kirjoitamme myös vakioiden 25 ja 17 binääriarvot:

Lauseemme on kolmen lauseen looginen TAI:

1) not(A) - tämä tarkoittaa X&25 = 0 (X:n bitit 0,3,4 ovat kaikki 0)

2) ei(B) - joten X&17 ei ole yhtä suuri kuin 0 (X:n bitit 0 ja 4 ainakin yksi on yhtä suuri kuin 1)

3) C - tietää, että X&A ei ole yhtä suuri kuin 0 (maskin A asettamat bitit, vähintään 1 on yhtä kuin 1)

X on mielivaltainen luku. Kaikki sen bitit ovat itsenäisiä. Siksi on mahdollista vaatia jonkin ehdon täyttymistä mielivaltaisen luvun biteillä vain yhdessä tapauksessa - kun on kyse samasta maskista (bittijoukosta). Voimme huomata, että binäärimaski 17 on melkein sama kuin 25, vain bitti numero 3 puuttuu. Nyt jos 17 täydennetään bitillä numero 3, niin lauseke (not (B) TAI C) muuttuisi ei (ei) A ), so. in A = (X&25 ei ole yhtä suuri kuin 0). Toisella tavalla: sanotaan A=8 (bitti 3=1). Tällöin vaatimus (ei (B) B tai C) vastaa vaatimusta: (Ainakin yksi biteistä 4,0 on 1) TAI (bitti 3 on 1) = (vähintään yksi biteistä 0,3,4 on ei 1) - ne. inversio not(A) = A = (X&25 ei ole yhtä suuri kuin 0).

Tämän seurauksena huomasimme, että jos A = 8, niin lausekkeemme saa muotoa F = ei (A) TAI A, mikä on poissuljetun keskikohdan lain mukaan aina identtisesti totta. Muille, pienemmille A:n arvoille ei voida saavuttaa riippumattomuutta X:n arvosta, koska naamarit ovat erilaisia. No, jos A:n korkeissa biteissä on niitä yli 4:ssä, mikään ei muutu, koska muissa naamioissa meillä on nollia. Osoittautuu, että vain kun A=8 kaava muuttuu mielivaltaisen X:n tautologiaksi.

Dmitri Lisin

1. Esimerkki demosta

(ensimmäinen konsonantti → toinen konsonantti) / (edeviimeinen vokaali → viimeinen vokaali)

1) KRISTINA 2) MAXIM 3) STEPAN 4) MARIA

Ratkaisun pääpiirteet implikaatio a → b on yhtä suuri kuin ¬a / b.

Ensimmäinen implikaatio pätee sanoille CHRISTINA ja STEPAN. Näistä sanoista toinen implikaatio pätee vain sanalle CHRISTINA.

Vastaus: 1. CHRISTINA

2. Kaksi muuta esimerkkiä

Esimerkki 1 (FIPI Pankin avoin segmentti)

Mikä seuraavista nimistä täyttää loogisen ehdon:

(ensimmäinen konsonantti → ensimmäinen vokaali) / (viimeinen vokaali → viimeinen konsonantti)

1. IRINA 2. MAXIM 3. ARTEM 4. MARIA

Ratkaisun pääpiirteet. implikaatio a → b on yhtä suuri kuin ¬a / b. Tämä lauseke on tosi, jos jompikumpi lausekkeesta a on epätosi tai molemmat lausekkeet a ja b ovat tosi. Koska meidän tapauksessamme molemmat lausekkeet eivät voi olla tosia samaan aikaan missään implikaatiossa, lauseiden "ensimmäinen kirjain on konsonantti" ja "viimeinen kirjain on vokaali" on oltava vääriä, eli tarvitsemme sanan, jonka ensimmäinen kirjain on vokaali ja viimeinen on konsonantti.

Vastaus: 3. ARTEM.

Esimerkki 2 Mille luvun X ilmoitetuista arvoista lause on tosi

(X< 4)→(X >15)

1) 1 2) 2 3) 3 4) 4

Ratkaisu. Mikään luku ei voi olla samanaikaisesti pienempi kuin 4 ja suurempi kuin 15. Siksi implikaatio on totta vain, jos premissi X< 4 väärä.

Vastaus 4.

2. Tehtävät USE-muodossa 2013-2014

2.1. Demo 2013

Lukuviivalla on kaksi segmenttiä: P = ja Q = .

Valitse segmentti A siten, että kaava

1) 2) 3) 4)

2.2. Demo 2014

Lukuviivalla on kaksi segmenttiä: P = ja Q = . Valitse ehdotetuista segmenteistä sellainen segmentti A, joka vastaa loogista lauseketta

((x ∈ P) → ¬ (x ∈ Q)) → ¬ (x ∈ A)

identtisesti totta, eli se saa arvon 1 mille tahansa muuttujan arvolle

Vastausvaihtoehdot: 1) 2) 3) 4)

Ratkaisu. Muunnetaan lauseke käyttämällä . Meillä on:

¬((x ∈ P) → ¬ (x ∈ Q)) ∨ (¬ (x ∈ A)) - implikaation korvaaminen disjunktiolla;

¬(¬(x ∈ P) ∨ ¬ (x ∈ Q)) ∨ (¬ (x ∈ A)) - implikaation korvaaminen disjunktiolla;

((x ∈ P) ∧ (x ∈ Q)) ∨ (¬ (x ∈ A)) - de Morganin sääntö ja kaksoisnegaation poisto;

(x ∈ A) → ((x ∈ P) ∧ (x ∈ Q)) - disjunktion korvaaminen implikaatiolla

Viimeinen lauseke on identtisesti tosi silloin ja vain jos A ⊆ P∩ Q = ∩ = (katso ). Neljästä annetusta segmentistä vain segmentti - vaihtoehto nro 2 täyttää tämän ehdon.

Vastaus: - vaihtoehto numero 2

3. Tehtävät USE-muodossa 2015-2016

3.1. Tehtävä 1.

Lukuviivalla on kaksi segmenttiä: P = ja Q = .

Tiedetään, että janan A rajat ovat kokonaislukupisteitä ja janan A kaava

((x ∈ A) → (x ∈ P)) \/ (x ∈ Q)

on identtisesti totta, eli se saa arvon 1 mille tahansa muuttujan x arvolle.

Mikä on jakson A pisin mahdollinen pituus?

Oikea vastaus : 10

Ratkaisu:

Muunnamme lausekkeen - korvaamme implikation disjunktiolla. Saamme:

(¬(x ∈ A)) \/ ((x ∈ P)) \/ (x ∈ Q)

Lauseke ((x ∈ P)) \/ (x ∈ Q) pätee vain niille x:ille, jotka ovat joko P:ssä tai Q:ssa, toisin sanoen x ∈ R = P ∪ Q = ∪ . Ilmaisu

(¬(x ∈ A)) \/ (x ∈ R)

on identtisesti totta, jos ja vain jos A ∈ R. Koska A on jana, niin A ∈ R silloin ja vain jos A ∈ P tai A ∈ Q. Koska jana Q on pidempi kuin jana P, niin janan maksimipituus segmentti A saavutetaan, kun A = Q = . Janan A pituus on tässä tapauksessa 30 - 20 = 10.

3.2. Tehtävä 2.

Merkitse m&n ei-negatiivisten kokonaislukujen bittikonjunktio m ja n. Joten esimerkiksi 14&5 = 1110 2 &0101 2 = 0100 2 = 4. Mikä on pienin ei-negatiivinen kokonaisluku MUTTA kaava

x&25 ≠ 0 → (x&33 ≠ 0 → x&MUTTA ≠ 0)

on identtisesti totta, ts. ottaa arvon 1 mille tahansa muuttujan ei-negatiiviselle kokonaislukuarvolle X?

Oikea vastaus : 57

Ratkaisu:

Muunnamme lausekkeen - korvaamme implikaatiot disjunktioilla. Saamme:

¬( x&25 ≠ 0) ∨ (¬( x&33 ≠ 0) ∨ x&MUTTA ≠ 0)

Avaamme sulut ja korvaamme epäyhtälöiden negaatiot yhtäläisyyksillä:

x&25 = 0 ∨ x&33 = 0 ∨ x&MUTTA ≠ 0 (*)

Meillä on: 25 = 11001 2 ja 33 = 100001 2 . Siksi kaava

x&25 = 0 ∨ x&33 = 0

on epätosi silloin ja vain, jos luvun binääriesitys x sisältää 1:n ainakin yhdessä seuraavista binäärinumeroista: 100000 (32), 10000 (16), 1000 (8) ja 1.

Jotta kaava (*) olisi totta kaikille sellaisille x on välttämätöntä ja riittävää, että luvun A binäärimerkintä sisältää 1 kaikissa näissä numeroissa. Pienin tällainen luku on 32+16+8+1 = 57.

Tehtävä 18 Työhakemisto. Loogisia väitteitä

1. Tehtävä 18 nro 701. Minkä nimen kohdalla väite on väärä:

(Nimen ensimmäinen kirjain on vokaali→ Nimen neljäs kirjain on konsonantti).

1) ELENA

2) VADIM

3) ANTONI

4) FEDOR

Selitys.

Implikaatio on väärä, jos ja vain jos olettamus on tosi ja seuraus on väärä. Meidän tapauksessamme, jos nimen ensimmäinen kirjain on vokaali ja neljäs kirjain on vokaali. Nimi Anton täyttää tämän ehdon.

Merkintä.

Sama tulos seuraa seuraavista muunnoksista: ¬ (A→ B) = ¬(¬A∨ B) = A∧ (¬B).

Oikea vastaus on numero 3.

2. Tehtävä 18 nro 8666. Lukuviivalla on kaksi segmenttiä: P = ja Q = . Määritä suurin mahdollinen pituus välille A, jolle kaava

(¬ (xA)→ (xP))→ ((xA)→ (xQ))

on identtisesti totta, eli se saa arvon 1 mille tahansa muuttujan x arvolle.

Selitys.

Muunnetaan tämä lauseke:

(¬ ( xA) → ( x P)) → (( x A) → ( xK))

((xA)∨ (x P))→ ((x ei A)∨ (x Q))

¬(( xomistettuA) ∨ ( xomistettuP)) ∨ (( x ei omistettuA) ∨ ( x omistettuK))

( xei omistettuA) ∧ ( xei omistettuP) ∨ ( x omistettuA) ∨ ( x ei omistettuK)

( xei omistettuA) ∨ ( x omistettuK)

Siten joko x:n täytyy kuulua Q:hen tai ei kuulua A:han. Tämä tarkoittaa, että jotta saavutettaisiin tosi kaikille x:lle, on välttämätöntä, että A sisältyy kokonaan Q:hen. Tällöin maksimi, joka siitä voi tulla, on koko Q, eli pituus 15 .

3. Tehtävä 18 nro 9170. Lukuviivalla on kaksi segmenttiä: P = ja Q = .

Määritä janan A suurin mahdollinen pituus, jolle kaava

((xA)→ ¬(xP))→ ((xA)→ (xQ))

on identtisesti totta, eli se saa arvon 1 mille tahansa muuttujan arvolleX .

Selitys.

Muunnetaan tämä ilmaus.

(( x€ A) → ¬( xomistettuP)) → (( x omistettuA) → ( x omistettuK))

(( xei omistettuA) ∨ ( xei omistettuP)) → (( x ei omistettuA) ∨ ( x omistettuK))

¬((x ei kuulu A:een)∨ (xei kuulu P:hen))∨ ((xei kuulu A)∨ (xkuuluu Q:lle))

On totta, että A∧ B∨ ¬A = ¬A∨ B. Kun tätä käytetään tässä, saamme:

(x kuuluu P:lle)∨ (xei kuulu A)∨ (x kuuluu Q:lle)

Toisin sanoen joko pisteen täytyy kuulua Q:lle, kuulua P:lle tai ei kuulua A:lle. Tämä tarkoittaa, että A voi kattaa kaikki pisteet, jotka kattavat P:n ja Q:n. Eli A = P Q = = . |A| = 48 - 10 = 38.

4. Tehtävä 18 nro 9202. Joukkojen A, P, Q alkiot ovat luonnollisia lukuja ja P = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20), Q = (3, 6, 9, 12, 15, 18, 21, 24, 27, 30).

Tiedetään, että ilmaisu

((xA)→ (xP))∨ (¬(xQ)→ ¬(xA))

tosi (eli ottaa arvon 1) mille tahansa muuttujan x arvolle.

5. Tehtävä 18 nro 9310. Joukkojen A, P, Q alkiot ovat luonnollisia lukuja ja P = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20), Q = (5, 10, 15, 20, 25, 30, 35, 40, 45, 50).

Tiedetään, että ilmaisu

((xA)→ (xP))∨ (¬(xQ)→ ¬(xA))

true (eli ottaa arvon 1) mille tahansa muuttujan x arvolle.

Määritä suurin mahdollinen määrä elementtejä joukossa A.

6. Tehtävä 18 nro 9321. MerkitseDEL ( n, m ) lause "luonnollinen luku n on jaollinen ilman jäännöstä luonnollisella luvullam ". Mikä on suurin luonnollinen lukuMUTTA kaava

¬ DEL ( x, A ) → (¬ DEL ( x , 21) ∧ ¬ DEL ( x , 35))

on identtisesti tosi (eli se saa arvon 1 mille tahansa muuttujan luonnolliselle arvollex )?

(Tehtävä M. V. Kuznetsovalle)

7. Tehtävä 18 nro 9768. Merkitse m & n m ja n 2 & 0101 2 = 0100 2 MUTTA kaava

x & 29 ≠ 0 → (x & 12 = 0 → x & MUTTA ≠ 0)

on identtisesti tosi (eli saa arvon 1 mille tahansa muuttujan ei-negatiiviselle kokonaislukuarvolle X )?

8. Tehtävä 18 nro 9804. Merkitse m & n ei-negatiivisten kokonaislukujen bittikonjunktio m ja n . Joten esimerkiksi 14 & 5 = 1110 2 & 0101 2 = 0100 2 = 4. Mikä on pienin ei-negatiivinen kokonaisluku MUTTA kaava

x & 29 ≠ 0 → (x & 17 = 0 → x & MUTTA ≠ 0)

on identtisesti tosi (eli ottaa arvon 1 mille tahansa muuttujan ei-negatiiviselle kokonaislukuarvolle x )?

9. Tehtävä 18 nro 723. Mille nimelle väite pitää paikkansa:

Kolmas kirjain on vokaali→ ¬ (Ensimmäinen kirjain on konsonantti \/ Sanassa on 4 vokaalia)?

1) Rimma

2) Anatoli

3) Svetlana

4) Dmitri

Selitys.

Sovelletaan implikaatiomuunnos:

Kolmas kirjain Konsonantti∨ (Ensimmäinen kirjain vokaali∧ Sanassa EI on 4 vokaalia)

Disjunktio on tosi, kun ainakin yksi väitteistä on tosi. Siksi vain vaihtoehto 1 on sopiva.

10. Tehtävä 18 nro 4581. Mikä seuraavista nimistä täyttää loogisen ehdon:

(ensimmäinen kirjainkonsonantti→ viimeinen kirjain on konsonantti) /\ (ensimmäinen kirjain on vokaali→ viimeinen kirjain on vokaali)

Jos tällaisia ​​sanoja on useita, merkitse niistä pisin.

1) ANNA

2) BELLA

3) ANTONI

4) BORIS

Selitys.

Looginen JA on tosi vain, jos molemmat lauseet ovat tosia.(1)

Viittaus on väärä vain silloin, kun totuudesta seuraa valhe.(2)

Vaihtoehto 1 sopii kaikkiin olosuhteisiin.

Vaihtoehto 2 ei sovellu ehdon (2) vuoksi.

Vaihtoehto 3 ei sovellu ehdon (2) vuoksi.

Vaihtoehto 4 sopii kaikkiin olosuhteisiin.

Sinun on määritettävä sanoista pisin, joten vastaus on 4.

Tehtävät itsenäiseen ratkaisuun

1. Tehtävä 18 nro 711. Mikä seuraavista maiden nimistä täyttää seuraavan loogisen ehdon: ((viimeinen konsonantti) \/ (ensimmäinen konsonantti))→ (nimi sisältää kirjaimen "p")?

1) Brasilia

2) Meksiko

3) Argentiina

4) Kuuba

2. Tehtävä 18 nro 709. Mikä seuraavista nimistä täyttää loogisen ehdon:

(Ensimmäinen kirjain on vokaali)∧ ((neljännen kirjaimen konsonantti)∨ (Sanassa on neljä kirjainta))?

1) Sergei

2) Vadim

3) Anton

4) Ilja

№3

№4

№5. Tehtävä 18 nro 736. Mikä annetuista nimistä täyttää loogisen ehdon

Ensimmäinen kirjain on vokaali∧ neljäs konsonantti∨ Onko sanassa neljä kirjainta?

1) Sergei

2) Vadim

3) Anton

4) Ilja