Egzamin z matematyki dyskretnej 19 czerwca 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 \ B ∧ B \ A = B \ C] ⇒ [A ∪ C ⊆ B ∨ A ∪ B ⊆ C ∨ A ∩ B ∩ C = ∅]

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

Jeśli odpowiedziałeś "Nie", przedstaw kontrprzykład przez wskazanie trzech (niekoniecznie różnych) zbiorów A, B, C ⊆ {1, 2, 3}, 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 logicznie równoważne schematowi (p ∧ r) → (q → r). 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 ∨ ~ _.....) ∨ _.....

(b) r → ( _..... → _..... )

(c) (q ↔ _..... ) → (p → _.....)

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 pies nie jest człowiekiem. (b) Każdy pies posiada właściciela, który jest człowiekiem. (c) Żaden pies nie jest właścicielem żadnego człowieka. 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, n prostych rozcina płaszczyznę na nie więcej niż (n² + n + 2) / 2 spójnych obszarów. Dowód przedstaw na odwrocie strony.

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

xSy ⇔ (x < y ∧ x mod 2 = y mod 3).

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

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

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

(c) Najdłuższy łańcuch: _{........................................................................................................................................................}

Na odwrocie przedstaw diagram Hassego tego porządku.

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

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

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

(c) Długość optymalnej trasy komiwojażera:_{.................}

Zad. 7. (10 pkt.) Wyznacz liczbę podgrafów pełnego dwudzielnego grafu K_3,5, 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₃: _{...................}

---