DEgz1 2009 odp

Egzamin z matematyki dyskretnej 19 czerwca 2009

Imię:

12

0

T

■p-

~R

~V

Nazwisko:

P

\

0

TT

U

0

0

s

l

Grupa: | |’Numer Indeksu: j

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

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

Uwagi:

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

[A\B = ĆXB A B\A = B\C\ ==> [^uCę5 v ^uBęC v^(nBnC-0]

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, 5, Cc {1,2,3}, dla których ta funkcja staje się zdaniem fałszywym.

Kontrprzykład (opcjonalnie): A =    ..............B = \jr.f..3..J...........^ J -■'

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 a 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) .'(pv~p.)v.J>    [f C, - efow&ls^ 2W.'

(b) r -* (ę. -> r) / r* (_ $    £ J    ^'

c,    ,

(c) (^o.|)->(p->.p.)    /    p) ^ Cp^

Zad. 3. (9 pkt.) Definiujemy następujące predykaty: F(x) - x jest psem, C(x) - x jest człowiekiem oraz JE(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.

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. £ _D ± ₀ ^ ^    •' fc )

Zad. 5. (9 pkt.). W zbiorze ,4 = {1,2,..., 10} zdefiniowano relację binarnąS: xSy o (x < y a x mod 2 =y mod 3).

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

(a)    Wszystkie elementy minimalne: ...........................................

(b)    Wszystkie elementy maksymalne: ...dQ................

Na odwrocie przedstaw diagram Hassego tego porządku.

&

(c)    Najdłuższy łańcuch:............../............/.......d..$.

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

(a) Wagę minimalnego drzewa spinającego: d..^.................... 6 Oj CB)

(b) Długość optymalnej trasy chińskiego listonosza: (1.9.0j C&Jy l )

(c)    Długość optymalnej trasy komiwojażera:......d..3>    (. 9 r? 0 fi

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

(a)    Izomorficzne z grafem Aj_>3: (JjJ.l J )    ^

(b)    Izomorficzne z grafem K₂<    Sj ^ &

v_ Lsj V_

(c)    Izomorficzne z grafem C₄:.....

(d)    Izomorficzne z grafem P₃

30