Egzamin z matematyki dyskretnej 12 września 2008

Imię:

Nazwisko:

Grupa:

Numer Indeksu:

Uwagi:

1. Czas rozwiązywania 120 minut.

2. Ewentualne wątpliwości związane z niejednoznacznością sformułowań w zadaniach należy umieścić obok udzielonych odpowiedzi.

3. Dozwolone jest korzystanie z pomocy w formie własnoręcznych notatek i wydruków slajdów z wykładu. Nie wolno korzystać z książek i urządzeń elektronicznych.

4. Zbiór liczb naturalnych nie zawiera zera: 0 ∉ N.

5. Zapis "a | b" oznacza "a jest dzielnikiem b" czyli "b jest podzielne przez a".

6. W trakcie egzaminu nie wolno opuszczać sali przed oddaniem pracy.

Zad. 1. (9 pkt.) Rozstrzygnij, które z poniższych funkcji zdaniowych stają się prawdziwe dla dowolnych trzech zbiorów A, B, C. Jeżeli uważasz, że dana funkcja nie zawsze jest prawdziwa, podaj kontrprzykład przez wskazanie trzech zbiorów A, B, C ⊆ {1, 2, 3, 4, 5}, dla których ta funkcja staje się zdaniem fałszywym.

(a) [(A ∪ B) \ C = (A ∪ C) \ B ] ⇒ [B ∩ C ⊆ A] (Tak/Nie)? _........

Kontrprzykład (opcjonalnie): A = _{.......................................} B = _{.......................................} C = _{.......................................}

(b) [A ∩ (B \ C) = (B ∪ C) \ A] ⇒ [B = ∅] (Tak/Nie)? _........

Kontrprzykład (opcjonalnie): A = _{.......................................} B = _{.......................................} C = _{.......................................}

(c) [A ∩ B = B ∩ C = C ∩ A ∧ (A ∪ C) \ B = ∅] ⇒ [A = B = C] (Tak/Nie)? _........

Kontrprzykład (opcjonalnie): A = _{.......................................} B = _{.......................................} C = _{.......................................}

Zad. 2. (8 pkt.) Uzupełnij poniższe formuły symbolami zmiennych zdaniowych tak, aby powstałe schematy logiczne stały się tautologiami. Możesz używać wyłącznie symboli zmiennych zdaniowych (np. p, q, r, s). Dopisywanie spójników logicznych jest niedozwolone.

(a) [p ∧ ∼ (q → p)] ↔ [(∼ ( _..... ) ∨ _..... ) → ( _..... ∧ ∼ ( _..... ))]

(b) [p → (q → r)] ↔ [(∼ _..... ) → (∼ ( _..... ∧ _..... ))]

Zad. 3. (8 pkt.) Czy poniższa formuła jest tautologią rachunku predykatów? Jeżeli nie, podaj przykład predykatów P i Q w zbiorze liczb naturalnych, dla których formuła ta staje się zdaniem fałszywym. Jeżeli jest tautologią zamiast kontrprzykładu wpisz „to jest tautologia”.

∀_x[(P(x) → Q(x)) ∨ (Q(x) ↔ R(x))] ∨ ∀_x[(P(x) ∨ Q(x) ∨ R(x)]

P(x) ⇔ _{...................................................................................................................................................................................................................}

Q(x) ⇔ _{...................................................................................................................................................................................................................}

R(x) ⇔ _{...................................................................................................................................................................................................................}

Zad. 4. (9 pkt.) W zbiorze słów 5-cio bitowych określono relację S w ten sposób, że xSy wtedy i tylko wtedy, gdy y powstaje z x przez zamianę dwóch sąsiednich bitów. (np. 10011 S 10101). Niech R będzie równoważnościowym domknięciem S (czyli R = p(s(z(S))).

(a) Wyznacz liczbę elementów klas abstrakcji wyznaczonych przez następujących reprezentantów:

| [00000]_R| = _.......... | [01001]_R| = _.......... | [11101]_R| = _..........

(b) Wypisz po jednym reprezentancie każdej z klas abstrakcji relacji R.

_{...................................................................................................................................................................................................................}

_{...................................................................................................................................................................................................................}

Zad. 5. (10 pkt.) Digraf G₁ reprezentuje relację S. Niech R = p(z(S)).

Na odwrocie kartki przedstaw diagram Hassego relacji R.

Zad. 6. (10 pkt.) Na ile sposobów można utworzyć 7-mio literowe słowo nad alfabetem {a, b, c}, tak aby:

(a) Litera „a” wystąpiła dokładnie dwa razy? _{............................................}

(b) Każda litera wystąpiła co najmniej dwa razy? _{............................................}

(c) Wystąpiły co najwyżej dwie litery? _{............................................}

(d) Dokładnie jedna litera wystąpiła dokładnie cztery razy? _{............................................}

Zad. 7. (10 pkt.) Dla grafu G₂ przedstawionego na rysunku:

(a) Wyznacz: χ(G₂) = _{...................} χ'(G₂) = _{.........................}

(b) Przez które krawędzie chiński listonosz będzie przechodził dwukrotnie (zakładając, że rozwiązał optymalnie swój problem)? _{.........................................................................................................................................}

(c) Jaka jest waga minimalnego drzewa spinającego G₂? _{..................................}

(d) Jaka jest długość najkrótszej drogi z G do C? _{....................................}

Zad. 8. (8 pkt.) Na odwrocie kartki udowodnij, że hiperkostka Q₂₀₀₈ jest grafem hamiltonowskim.

Zad. 9. (8 pkt.) Wyznacz zwarty wzór na n-ty wyraz ciągu określonego rekurencyjnie: a₁ = 7 oraz a_n+1 = a_n + 2ⁿ + 1. Przedstaw wzór poniżej, a jego wyprowadzenie (w przypadku odgadnięcia - dowód poprawności) na odwrocie strony.

Zad. 10. (10 pkt.) Czy istnieją funkcje f, g : N → R₊ takie, że

(a) f (n) = O(g(n) / n)) ∧ g(n) = O(f(n) / n) (Tak/Nie)? _{.............................}

(b) f (n) = o(ng(n)) ∧ g(n) = o(nf(n)) (Tak/Nie)? _{.............................}

(c) f (n) = o(g(n)) ∧ ~ (f(n) = o(g(n) / logn)) (Tak/Nie)? _{.............................}

Jeśli udzieliłeś w niektórych punktach odpowiedzi „Tak” przedstaw na odwrocie kartki odpowiednie przykłady funkcji f i g.

---