Diskrečiosios matematikos pratybų uždaviniai

Diskrečiosios matematikos pratybų uždaviniai

1 kursas, informatikai

I pratybos (aibės, poaibiai)

Ar

Sprendimas:

Ne, nes

Ar = }?

Sprendimas:

Ne, nes 3

Rasti aibės A visų poaibių aibę P(A):

a.       A = .

b.      A = , b}.

c.       A = }.

d.      A = , 3, }.

e.       A =

Sprendimas:

1. P(A) = , , , , , , ,
2. P(A) = , }, , }, , , b}, , b},
3. P(A) = , }, },
4. P(A) = , }, , {}, }, , {1, }, , 3}, , }, {3, }, , 3}, , }, , 3, }, {1, 3, }, , 3, },
5. P(A) = .

Ar A x B = B x A?

Sprendimas: Ne, nes, pavyzdžiui, A = , B = , tai A x B = , o B x A = .

Duotos aibės: A = , B = {1, , 3}, C = {3, }}. Rasti:

a.       A B, A B, A C, B C.

b.      A B, A B, A C, B C.

c.       A B, A B, A C, B C.

d.      A x B, A x B, A x C, B x C.

Sprendimas: trivialus.

Nurodyti bent dvi abipus vienareikšmes atitiktis(bijekcijas) tarp aibių:

a.       A = ir B = .

b.      A = ir B = .

Sprendimas:

a. trivialus.

b. negalima nurodyti bijekcijos: |A| ≠ |B|.

Rasti bijekcijas tarp:

a.      

b.     

c.      

Sprendimas:

a.      

b.     

c.      

Duota aibė A = – baigtinė, B = – skaičioji. Parodyti, kad  A B – skaičioji.

Sprendimas: A B = (pgl thm: prie begalinės aibės A pridėjus baigtinę ar skaičiąją aibę, gaunama aibė ekvivalenti aibei A.).

Parodyti, kad aibė žodžių abėcėlėje , prasidedančių 1, yra skaičioji.

Sprendimas: – čia kiekvienas elementas dvejetainis skaičius: 1 – 1, 10 – 2, 11 – 3, 100 – 4

Kokia yra iracionaliųjų(I) skaičių aibės galia?

Sprendimas: R = Q I. R yra kontinumo galios aibė, Q yra skaičioji, todėl I yra kontinumo galios aibė(jei būtų skaičioji, tai R irgi būtų skaičioji)(pgl thm: iš kontinumo galios aibės atėmus baigtinę ar skaičiąją aibę gaunama kontinumo galios aibė).

II pratybos (teiginių kalba, teisingumo lentelės

Ekvivalentai:

p → q = ¬p / q

p & q = ¬(¬p / ¬q)

p / q = ¬(¬p & ¬q)

p ↔ q = (p → q) & (q → p)

p / q = ¬(p & q)

neigimo įkėlimas:

¬(p & q) = ¬p / ¬q

¬(p / q) = ¬p & ¬q

distributyvumo dėsnis:

(p / q) & r = (p & r) / (q & r)

(p & q) / r = (p / r) & (q / r)

Išrašyti teisingumo lenteles formulėms, pasakyti kokios tai formulės: tapačiai teisingos, tapačiai klaidingos ar įvykdomos:

a.       p → (q / (r → ¬p)).

b.      p / (q ↔ (r ↔ ¬p)).

c.       ((¬¬q ↔ ¬r) / (q & r)) & ¬p.

d.      (p & ¬q) ↔ (¬p & q).

e.       ((p → q) → ¬r) / (¬(p / r) & ¬q).

f.        (¬(q → p) → (r → q)) & ((p → ¬q) / (r → q)).

g.      (¬(q /¬p) & (r & ¬q)) / ((p & q) & ¬( r → q)).

Sprendimas: trivialus. a, b, c, d, e – įvykdomos, f – tapačiai teisinga, g – tapačiai klaidinga.

Suskaidyti formules į poformules, nustatyti gylį:

a.       (p → q) & (¬p → (q / r)).

b.      ¬¬q / (r → (p & q))) / (r & ¬¬¬p

c.       ((p → q) → ¬r) / (¬(p / r) & ¬q).

d.      (((p / q) / (r / q)) / ((r ↔ ¬¬q) & ¬p)) / ¬q.

Sprendimas:

a.

, gylis = 3.

b, c, d – analogiškai.

Nustatyti, kurie kintamieji yra esminiai, o kurie fiktyvūs duotose formulėse:

a.       p & (q / ¬q).

b.      (¬p / ¬r) & (p → r).

c.       (¬ (q → p) / (p & q)) → r.

d.      (p → q) / ¬(q & ¬r).

e.       (¬p → q) & ¬((¬p & ¬q) & r).

Sprendimas: Išrašyti teisingumo lenteles ir žiūrėti, nuo kurių kintamųjų priklauso formulės reikšmė, o nuo kurių ne

a.       q – fiktyvus , p – esminis.

b.      p – fiktyvus, r – esminis.

c.       p – fiktyvus, q, r – esminiai.

d.      Visi fiktyvūs.

e.       r – fiktyvus, p, q – esminiai.

Konstantų eliminavimas. Supaprastinti formules:

a.       (p → t) & ((q / k) & (r ↔ k)).

b.      p & k) / ¬r → (k / r).

c.       ¬q → t p / t)) & (t ↔ q)

d.      (((p / t) / (k / ¬q)) / (q & t)) / (¬q / k

Sprendimas:

a.       (p → t) & ((q / k) & (r ↔ k)) t & ((q / k) & (r ↔ k)) ((q / k) & (r ↔ k)) q & (r ↔ k) q & ¬r.

b.      r.

c.       p & q.

d.      t.

Nubrėžti kontaktines schemas formulėms:

a.       (p → q) & (q → r

b.      (q / r) → p

c.       (¬((p / r) & q)) / r.

d.      ((q → p) / (r & ¬p)) & (q → r

Sprendimas: Pertvarkyti formules, kad būtų tik &, / ir prieš loginius kintamuosius, o toliau: & - nuoseklus jungimas, / - lygiagretus jungimas.

III pratybos (pilnos aibės, loginės išvados)

Įrodyti, kad aibės yra pilnos:

Sprendimas: Reikia išreikšti per duotos aibės funkcijas likusias funkcijas – ¬, &, /, →, ↔, /.

Loginės išvados:

1. Įmonėje yra trys cechai A, B, C, susitarę dėl projektų tvirtinimo tvarkos:  . Jei cechas B nedalyvauja tvirtinant projektą, tai nedalyvauja ir cechas A,  Jei cechas B dalyvauja tvirtinant projektą, tai kartu dalyvauja ir cechai A bei C,  Ar privalo šiomis sąlygomis cechas C dalyvauti tvirtinant projektą, kada projektą tvirtina cechas A?
2. 1. Jei paskaitoje yra Algis, tai bus joje ir Petras su Jonu,  2. Jei nėra Petro, tai nėra Algio arba Jono(t.y. bent vieno iš jų), 3. Jeigu nėra Jono, tai nebus ir Petro,  Ar yra paskaitoje Algis, jei žinoma, kad yra Petras?
3. Jei Biblija yra teisinga ir ją reikia suprasti pažodžiui, tai egzistuoja Dievas, be to, Adomo ir Ievos išvarymo iš rojaus istorija yra teisinga. Jei tiesa, kad Dievas šitaip išvarė iš rojaus Adomą ir Ievą, tai jis yra kerštingas ir nemielaširdingas. Tačiau jei, kaip teigiama Biblijoje, Dievas yra, tai jis visagalis ir mielaširdingas. Vadinasi, Biblija – tik graži pasaka, arba jos nedera suprasti pažodžiui.
4. Saloje gyvena dvi gentys – teisuoliai ir melagiai. Atvažiavo į salą keliautojas. Sutiko tris salos gyventojus – A, B, C. Paklausė A: “Kas tu toks?”, bet neišgirdo atsakymo. B pasakė: “A pasakė esąs melagis”. C pasakė: “B melagis”. Kas yra A, B, C?

Sprendimas:

1. ¬b → ¬a], 2. [b → (a & c)], išvada – [a → c]. Reikia nustatyti, ar formulė ((¬b → ¬a) & (b → (a & c))) → (a → c) yra tapačiai teisinga(taip).
2. 1. [a → (p & j) ¬p → (¬a / ¬j) ¬j → ¬p], išvada – [p → a]. Reikia nustatyti, ar formulė  ((a → (p & j)) & (¬p → (¬a / ¬j)) & (¬j → ¬p p → a) yra tapačiai teisinga(ne).
3. [(b & p) → (d & a)], [a → (e & ¬m)], [d → (v & m)], išvada – [¬b / ¬p]. Reikia nustatyti, ar formulė  (((b & p) → (d & a)) & (a → (e & ¬m)) & (d → (v & m))) → (¬b / ¬p) yra tapačiai teisinga(taip).
4. Apie A nieko negalima pasakyti, B – melagis, C – teisuolis.

Σ = . Ar ¬q yra aibės Σ loginė išvada?

Sprendimas: Analogiškas 2 – am uždaviniui(ne).

IV pratybos (normaliosios disjunkcinės, konjunkcinės formos)

Transformuoti į NDF, naudojant teisingumo lenteles:

1. (p → q) & (q → r).
2. (p / q) ↔ (¬q / r).
3. (p & ¬(r / ¬q)) ↔ q.
4. (p / (r & ¬q)) & (¬¬r / q).

Sprendimas: Išrašius teisingumo lenteles, imamos eilutės, kur funkcijos reikšmė yra teisinga ir joms sudaroma “teisinga” konjunkcija, gautos konjunkcijos apjungiamos disjunkcija.

Transformuoti į NDF, naudojant ekvivalenčias formules:

1. (¬p → ¬q) → ((q & r)→ (p & r)).
2. ((p → q) → ¬p) → (p → (q & p)).
3. ¬((p & q) → ¬p) & ¬((q & p) → ¬q).
4. ¬ ((p / q) & ¬(q ↔ r)) / p.

Sprendimas:

1. Eliminuojami →, ↔, /.
2. Įkeliamas neigimas.
3. Taikomas distributyvumo dėsnis.
4. Prastinama, t.y. p & p = p, p / p = p, p & ¬p = k, p / ¬p = t ir pan. Eliminuojamos konstantos. Šį žingsnį galima atlikti ir po pirmo ar antro žingsnių.

Transformuoti į NKF, naudojant teisingumo lenteles:

1. (p → q) / (r → ¬q).
2. ((p / q) & (q / r)) → ¬r.
3. ((p ↔ q) & ¬(¬p & q) (p / q).
4. (p / ¬(r → ¬q) q & r).

Sprendimas: Išrašius teisingumo lenteles, imamos eilutės, kur funkcijos reikšmė yra klaidinga ir joms sudaroma “klaidinga” disjunkcija, gautos disjunkcijos apjungiamos konjunkcija.

Transformuoti į NKF, naudojant ekvivalenčias formules:

1. (r → p → (¬(q / r) → p).
2. ¬((p & q) → p) / (p & (q / r)).
3. ¬(p & (q / r)) → ((p & q) / r).
4. ((p / q) ↔ (¬r & p)) / (q / p).

Sprendimas: Algoritmas toks pat, kaip ir antrame uždavinyje.

V pratybos (Turing mašinos)

Turing mašina – tai ketvertas <Q, , F>, kur Q – būsenų aibė, – abėcėlė, – perėjimų funkcija, F – galutinių būsenų aibė, q₀ – pradinė būsena.

Duota abėcėlė = . Rasti Turing mašinas, apskaičiuojančias funkcijas:

a.       f(x) ≡ 0, x yra netuščias abėcėlės žodis.

b.      Funkcija, nulius keičianti vienetais, o vienetus – nuliais, pvz., f(0101111) = 1010000.

c.       Funkcija, pirmą nulį keičianti vientu, jei nulių nėra, tai dirba be galo ilgai.

d.      Duotas abėcėlės žodis. Pakeisti jame antrą nulį vienetu. Jei jo nėra, tai prirašyti žodžio pabaigoje 1.

e.       f(x) = x + 1, x – dvejetainis skaičius.

f.        f(x) = x - 1, x – dvejetainis skaičius. Jei x = 0, tai f(x) = 0.

g.      f(x) = x, jei pirmi du skaitmenys sutampa, f(x) = x10, priešingu atveju.

h.      f(x) = 1, jei žodyje x yra lyginis skaičius vienetų, f(x) = 0, priešingu atveju.

Kokią funkciją apskaičiuoja Turing mašina:

(q₀, 0) = (q₁, 0, D)

(q₀, 1) = (q₂, 1, N)

(q₁, 0) = (q₂, 1, N)

(q₁, 1) = (q₁, 1, D)

(q₀, b) = (q₀, b, D)

δ(q₁, b) = (q₁, b, D)

VI pratybos (Posto teorema)

Posto teorema: A – pilna tada ir tik tada, kai A nėra poaibis nė vienos iš aibių T₀, T₁, S, M, L:

1. f(x₁, …, x_n) T₀ tada ir tik tada, kai f(0, …, 0) = 0.
2. f(x₁, …, x_n) T₁ tada ir tik tada, kai f(1, …, 1) = 1.
3. Sakysime, kad funkcija f* yra dualioji funkcijai f, jei f*( x₁, …, x_n) = ¬f(¬x₁, …, x_n f(x₁, …, x_n) autodualiųjų funkcijų aibei S tada ir tik tada, kai f* = f.
4. M – monotoninių funkcijų aibė. Funkcija f( x₁, …, x_n) vadinama monotonine, jei bet kuriems rinkiniams α, β, tenkinantiems nelygybę α ≤ β, f(α) ≤ f(β).
5. L – tiesinių funkcijų aibė. Funkcija tiesinė, jei jos Žegalkino polinomas yra pirmo laipsnio.

Naudojantis Posto teorema nustatyti, ar aibės pilnos:

a.       A = .

b.      A = .

c.       A =

d.      A =

e.       A = ,

f.        A = .

g.      A = .

VII pratybos (rezoliucijų metodas

Ar išvedamas tuščias disjunktas:

a.       S = .

b.      S = .

c.       S = .

Sprendimas:

a.       <4 su 5> <rez su 8> <rez su 7> <rez su 1> <rez su 5> <rez su 6 > <rez su 5>.

b.      Iš S tuščias disjunktas neišvedamas, nes:

nėra interpretacijos, su kuria visos aibės formulės būtų teisingos;

taikant rezoliucijos taisyklę, po baigtinio skaičiaus žingsnių matosi, kad nieko naujo nesigauna.

c.       <1 su 5> gaunam (p / q)  <2 su 7> gaunam (p / ¬q) <(p / q) su (p / ¬q)> gaunam p <6 su 8> gaunam (¬p / q) <(¬p / q) su p> gaunam q <p su 3> gaunam (¬q / ¬r) <q su (¬q / ¬r)> gaunam ¬r <p su 4> gaunam (¬q /r) <q su (¬q /r)> gaunam r <r su ¬r>.

Patikrinti, ar formulės yra tapačiai klaidingos, naudojantis disjunktų dedukcine sistema:

a.       (¬p / q) & ¬((q → r) → (¬p / r))

b.      (¬p / q) & ¬((q → r) → ((p & r) → r))

Sprendimas:

Formules transformuoti į NKF → sudėti disjunktus į aibę S → bandyti išvesti tuščią disjunktą: jei išsiveda, vadinasi aibė S prieštaringa, o formulė – tapačiai klaidinga. Abiem atvejais tuščias disjunktas išsiveda(trivialiai).