3a (11)

13.02.2002

* PJWSTK: Egzamin poprawkowy z matematyki dyskretnej Imię i nazwisko.................................................... Numer indeksu................ Numer grupy........

1.    (4 pkt) Podaj przykład trzrech zbiorów A,B,C G {x, y, 1} takich, że

a)    (AUĆ7)D5^ (AnB)llC

b)    (A\U{B\C) ź {AUB)\C

2.    (4 pkt) Udowodnij, że dla każdego n > 0 następująca formuła jest tautologią rachunku zdań:

(ai—*02) V (03—>Oą) V ... V [(l2n—l~*^a2n) ^v (<*1 H 03 fi a2n-l)

3.    (4 pkt) Zakładając, że S(x) oznacza predykat „z jest smutny”, zaś Z(x, y): „x jest zakochany w y” wyraź fakt, że

a)    Tylko    smutni nie są w kimś zakochani

b)    Są ludzie którzy nie są smutni, mimo że nikt nie jst w nich zakochany

.*

4.    (4 pkt) Zaneguj następujące formuły wprowadzając znak negacji do wnętrz kwantyfikato-rów tak, aby pozbyć się wszystkich znaków implikacji wyrażając je przez V, A,

a)    3x € X : (P(x)-+Vy G Y : (Q(y)-+R(x)))

b)    3x G X : (P{x) V (Q(yHVz G Z : R(z)))

W ramach uzasadnienia podaj reguły z których należało skorzystać.

5.    (4 pkt) Niech X = {a, 6, c), zaś Y jest zbiorem liczb całkowitych. Jaka jest moc a) zbioru wszystkich funkcji z X w Y1

b) zbioru wszystkich funkcji z Y w XI