Diskrečioji matematika: uždaviniai ir egzamino klausimai

Kompiuterių mokslo ir kiekvieno įrodymo matematika: teiginių logika ir kvantoriai, aibės, sąryšiai ir funkcijos, grafai su trumpiausiais keliais ir minimaliais karkasiniais medžiais bei skaičių teorija iki RSA. Egzamino klausimai reikalauja tikslių atsakymų, todėl kruopščiai sudaryta lentelė ar diagrama svarbesnė už skaičiuotuvą.

Praktikuokitės šiame kurse nemokamaiPraktikuotis šiame kurseLaikyti bandomąjį egzaminąKasdien nemokamų uždavinių: 5. Kortelės nereikia.

Pasiruošimo paketas (PDF)Formulių lapai, metodų žingsniai ir uždaviniai su pilnais sprendimais, paruošti spausdinti.

Šio kurso temos

  1. Teiginių logika ir įrodymaiteisingumo lentelės · ekvivalentumai ir įrodymo metodai · kvantoriai ir argumentaiskaičiavimai
  2. Aibės, sąryšiai ir funkcijosVeno diagramos ir pošaibiai · įtraukos ir pašalinimo principas bei sąryšiai · funkcijos ir skaičiavimasskaičiavimai
  3. Grafų teorijalaipsniai ir briaunos · Oilerio keliai ir medžiai · trumpiausi keliai ir karkasiniai medžiaiskaičiavimai
  4. Skaičių teorija ir modulinė aritmetikaDBD ir liekanos · atvirkštiniai skaičiai ir kongruencijos · moduliniai laipsniai ir RSAskaičiavimai

Egzamino patarimai: Diskrečioji matematika

  • Užrašykite teisingumo lentelę arba Veno diagramą: dauguma klaidų atsiranda praleidus eilutę ar sritį.
  • Norint paneigti teiginį, pakanka vieno kontrapavyzdžio; norint jį įrodyti, reikia patikrinti kiekvieną atvejį arba pateikti bendrą argumentą.
  • Modulinėje aritmetikoje po kiekvieno žingsnio redukuokite ir palikite liekanas nuo 0 iki n − 1.

Išspręsti pavyzdžiai

Teiginių logika ir įrodymaiLengvas
pq¬(p ∨ q) → q11100100

Lygiai viena teisingumo lentelės eilutė daro ¬(p ∨ q) → q klaidingą. Spustelėkite tą eilutę.

¬(p ∨ q) → q
  1. 1p = 1, q = 1
  2. 2p = 1, q = 0
  3. 3p = 0, q = 1
  4. 4p = 0, q = 0
Rodyti užuominas
  1. a → b yra 0 tik tada, kai a = 1 ir b = 0. ¬a apverčia reikšmę. a ∨ b yra 0 tik tada, kai abu lygūs 0.
  2. Pirmiausia išnagrinėkite pagrindinę jungtį: kokios turi būti jos abi pusės, kad visa formulė būtų 0?
  3. Kiekvienai daliai skirkite savo stulpelį: p ∨ q; ¬(p ∨ q); ¬(p ∨ q) → q.
Rodyti atsakymą ir paaiškinimą

Teisingumo lentelės: formulė su n skirtingų kintamųjų turi 2ⁿ eilučių, po vieną kiekvienam teisingumo reikšmių deriniui (1 = teisinga, 0 = klaidinga). Dirbkite iš vidaus į išorę ir kiekvienai posakio daliai skirkite savo stulpelį. ¬a apverčia reikšmę; a ∧ b yra 1 tik tada, kai abu lygūs 1; a ∨ b yra 0 tik tada, kai abu lygūs 0; a → b yra 0 tik tada, kai a = 1 ir b = 0; a ↔ b yra 1, kai abi pusės lygios.

Teisingumo lentelė eilutė po eilutės

p = 1, q = 1: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 1, q = 0: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 0, q = 1: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 0, q = 0: p ∨ q = 0, ¬(p ∨ q) = 1, ¬(p ∨ q) → q = 0

Eilutė

p = 0, q = 0 → ¬(p ∨ q) → q = 0

Atsakymas

p = 0, q = 0
Aibės, sąryšiai ir funkcijosVidutinis
UMPC

Iš 53 pirmakursių 35 išlaikė matematiką (M), 28 išlaikė fiziką (P) ir 29 išlaikė chemiją (C). 20 išlaikė M ir P, 18 išlaikė M ir C, 10 išlaikė P ir C, o 6 išlaikė visus tris. Kiek jų nėra nė vienoje iš trijų aibių?

|U| = 53

Raskite |(M ∪ P ∪ C)′|

Rodyti užuominas
  1. Užpildykite Veno diagramą iš centro į išorę: pirmiausia visas tris, tada poras, tada pavienes aibes.
  2. Tik M ir P (ne C): 20 − 6 = 14. Tik M: 35 − 14 − 12 − 6 = 3.
  3. Bent viena aibė: 35 + 28 + 29 − 20 − 18 − 10 + 6 = 50.
Rodyti atsakymą ir sprendimą žingsnis po žingsnio

Aibės ir Veno diagramos: A ∪ B turi elementus, esančius A arba B (ar abiejose), A ∩ B – elementus abiejose, A − B – A elementus, kurių nėra B, o papildinys A′ – viską U, kas nėra A. Veno diagramoje kiekviena aibės išraiška yra sričių sąjunga, todėl ją skaičiuokite sritis po srities. Įtraukos ir pašalinimo principas: |A ∪ B| = |A| + |B| − |A ∩ B| ir |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

Centras ir poros

M ∩ P ∩ C: 6
M ∩ P tik: 20 − 6 = 14
M ∩ C tik: 18 − 6 = 12
P ∩ C tik: 10 − 6 = 4

Pavienės aibės

M tik: 35 − 14 − 12 − 6 = 3
P tik: 28 − 14 − 4 − 6 = 4
C tik: 29 − 12 − 4 − 6 = 7

Atsakymas

|M ∪ P ∪ C| = 50
|(M ∪ P ∪ C)′| = 53 − 50 = 3

Atsakymas

|(M ∪ P ∪ C)′| = 3

Kaip vyksta praktika

  • „Praktikuotis šiame kurse“ maišo uždavinius iš visų kurso temų, kaip tikrame egzamine.
  • Kiekviename uždavinyje naujos reikšmės, todėl išmokstate metodą, o ne atsakymą.
  • Strigote? Pirmiausia atverkite nedidelę užuominą, o visą paaiškinimą – tik kai jo prireiks.
  • Bandomieji egzaminai yra riboto laiko ir be užuominų, o pabaigoje gaunate rezultatą ir išsamią peržiūrą.

Susiję kursai

Informatikos pagrindaiDuomenų struktūros ir algoritmaiMatematinė analizė 1Statistikos pagrindaiInžinerinė matematikaStatistika 2: statistinės išvadosDiferencialinės lygtysInžinerinė matematika 2
Praktikuokitės šiame kurse nemokamaiPraktikuotis šiame kurseLaikyti bandomąjį egzaminąKasdien nemokamų uždavinių: 5. Kortelės nereikia.