Egzamin z matematyki dyskretnej 10 września 2009

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. C_n oznacza cykl o n wierzchołkach, P_n oznacza ścieżkę o n wierzchołkach

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

Zad. 1. (9 pkt.) Czy następująca funkcja zdaniowa:

A ∩ B ∩ C ≠ A ∪ C ∨ A = B ∨ A = ∅

jest prawdziwa dla każdych trzech podzbiorów zbioru {1, 2, 3, 4, 5}? (Tak/Nie)? _........

Jeśli odpowiedziałeś "Nie", przedstaw kontrprzykład przez wskazanie trzech (niekoniecznie różnych) zbiorów A, B, C ⊆ {1, 2, 3, 4, 5}, dla których ta funkcja staje się zdaniem fałszywym.

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

Zad. 2. (9 pkt.) Uzupełnij poniższe formuły symbolami zmiennych zdaniowych tak, aby powstałe schematy logiczne były tautologiami.Możesz używać wyłącznie symboli zmiennych zdaniowych (np. p, q, r, s). Dopisywanie spójników logicznych jest niedozwolone. Jeżeli uważasz, że w którymś przypadku takie uzupełnienie nie jest możliwe, wpisz obok formuły sformułowanie "brak rozwiązania".

(a) (p → q) ∨ (~ _..... ∨ _..... )

(b) (p → q) ∨ (~ _..... ∧ _..... )

(c) [p → (r → q)] ↔ [( _..... ∨ _..... ) ∧ (~ _.....∨ _..... )]

Zad. 3. (9 pkt.) Definiujemy następujące predykaty: P(x) - x jest psem, C(x) - x jest człowiekiem oraz W(x, y) - x jest właścicielem y. Wyraź w języku rachunku predykatów pierwszego rzędu następujące zdania: (a) Żaden człowiek nie ma właściciela. (b) Nie każdy pies ma właściciela. (c) Żaden człowiek nie jest właścicielem wszystkich psów.. Nie wolno używać żadnych innych symboli niż nawiasy, wymienione powyżej predykaty, zmienne, kwantyfikatory oraz spójniki logiczne.

(a) _{...................................................................................................................................................................................................................}

(b) _{...................................................................................................................................................................................................................}

(c) _{...................................................................................................................................................................................................................}

Zad. 4. (9 pkt.) Udowodnij, że dla dowolnej liczby naturalnej n:
. Dowód przedstaw na odwrocie strony.

Zad. 5. (9 pkt.). W zbiorze A = {1, 2, ..., 10} zdefiniowano relację binarną S:

xSy ⇔ (x < y ∧ (x + y) mod 5 < 2).

Niech R = p(z(S)). Dla zbioru częściowo uporządkowanego (A, R) Wyznacz:

(a) Wszystkie elementy minimalne: _{...........................................................................................................................}

(b) Wszystkie elementy maksymalne:_{.........................................................................................................................}

(c) Kres górny zbioru {1,2,3,4,5}: (jeżeli kres nie istnieje wpisz symbol #) _{.............................}

Na odwrocie przedstaw diagram Hassego tego porządku.

Zad. 6. (10 pkt.) Dla grafu przestawionego powyżej wyznacz:

(a) Wagę minimalnego drzewa spinającego: _{.....................................}

(b) Długość optymalnej trasy chińskiego listonosza:_{.....................................}

(c) Indeks chromatyczny:_{.................} (d) Liczbę chromatyczną:_{.................}

Zad. 7. (10 pkt.) Wyznacz liczbę podgrafów pełnego grafu K₅, które są:

(a) Izomorficzne z grafem K_1,3: _{.... ........... ........... ........... .................. ...............}

(b) Izomorficzne z grafem K_2,2: _{....... ........... ........... .................... .......................}

(c) Izomorficzne z grafem C₅: _{.... ..... ................. ........... ........... ..........................}

(d) Izomorficzne z grafem P₃: _{..... ........... ........... ........... ........... .........................}

---