Egzamin z matematyki dyskretnej 18 czerwca 2010

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. NWD(x, y) oznacza największy wspólny dzielnik liczb x i y.

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 ∧ A \ C = ∅] ⇒ [B = ∅]

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) ↔ (p → 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) (_.....∧ ~ _.....) ∨ _..... (b) _..... ∨ _..... (c) (~_..... ) → (s ∧ ~_.....)

Zad. 3. (9 pkt.) Uniwersum jest zbiorem studentów. Definiujemy następujące predykaty: Z(x) - x zdał egzamin z matematyki; W(x) - x chodził na wykłady z matematyki; L(x, y) - x lubi matematykę bardziej niż y; R(x, y) - x i y to ten sam student.

Wyraź w języku rachunku predykatów pierwszego rzędu następujące zdania: (a) Nie wszyscy studenci, którzy zdali egzamin z matematyki, chodzili na wykłady z tego przedmiotu. (b) Każdy student, który chodził na wykłady z matematyki, zdał egzamin z tego przedmiotu (c) Jest pewien student, który lubi matematykę bardziej niż wszyscy inni studenci, ale nie zdał egzaminu. 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 każda hiperkostka jest grafem dwudzielnym.

Dowód przedstaw na odwrocie strony.

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

xSy ⇔ (x < y ∧ NWD(x, y) > 1).

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. (10 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 (długość najkrótszego cyklu Hamiltona) :_{.................}

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

Zad. 7. (10 pkt.) Wyznacz liczbę podgrafów pełnego trójdzielnego grafu K_3,5,8, które są:

(a) Izomorficzne z grafem K_1,9: _{...................} (b) Izomorficzne z grafem C₃: _{...................}

(c) Izomorficzne z grafem C₄: _{...................} (d) Izomorficzne z grafem K₄: _{...................}

---