Kolokwium z matematyki dyskretnej 20 czerwca 2008 (zakres 2007/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) = B ∪ C] ⇒ [A = B ∪ C] (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 ∩ C) = B ∪ C] ⇒ [B ⊆ A] (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) [r ∧ (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))] → [~ (∀_x(P(x)) → ∀_x(Q(x)))]

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

Q(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 cykliczne przesunięcie słowa x o jeden bit w prawo (np. 10011 S 11001). Niech R będzie równoważnościowym domknięciem S (czyli R = p(s(z(S))).

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

| [00000]_R| = _.......... | [01001]_R| = _.......... | [10101]_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)).

(a) Na odwrocie kartki przedstaw diagram Hassego relacji R.

(b) Znajdź trzy wierzchołki x, y, z ∈ V(G₁) takie, że ~xRy ∧ ~yRx ∧ ~xRz ∧ ~zRx.

x = _........ y = _........ z = _........

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

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

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

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

(d) Wystąpiły dokładnie dwie litery? _{............................................}

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 B do C? _{....................................}

Zad. 8. (8 pkt.) Dany jest ciąg a₁ = 2 oraz a_n+1 = (a_n + 3)² + 5, dla n > 1. Na odwrocie kartki udowodnij, że ∀_n∈N(7 | (a_n + 5)).

---