3582468744

Imię i Nazwisko:

Nr indeksu:

Test z matematyki dyskretnej. Zestaw IB 20.01.2009

1.    Jeżeli p. q są zdaniami, to

_ zdanie: ~ (pVg) •*=*> (~ pV ~ q) jest tautologią;

H,. =.„) = !] =■[„■!,,) = !]:

zdanie: (p ^ q) => (~ p V q) może być fałszywe.

2.    Dla dowolnych podzbiorów A, B zbioru X zachodzą następujące równości

(AuB)\(A\t>B) = ADB\

~ (AnBY = A'flB';

{A \ B) U B = A U B.

3.    W zbiorze {0, 1, 2} istnieje

dokładnie sześć relacji liniowego porządku;

_ co najmniej pięć relacji równoważności;

_ co najwyżej 500 różnych relacji.

4.    Prawdą jest, że

_ (Z, +, •) jest ciałem;

_ (Z7, +7, -7) jest pierścieniem przemiennym;

(M, ■) jest grupą.

5.    Dokładnie jedno rozwiązanie w zbiorze Zis ma kongruencja

5x = 1 (mod 18);

__10x = 6 (mod 18);

_ 15x = 8 (mod 18).

6.    W pierścieniu wielomianów Z_m[x] zachodzi równość (x + 7)(x + 3) = X¹ + 1, jeżeli

m = 10;

m — 9;

_ m = 8.

7.    Jeżeli A i B są zbiorami skończonymi, to prawdą jest, że

\AUB\ = \B\ => AcB;

__\A\ = \B\ = \ADB\ = n =» |.4UB| = n;

A n B = A => \A \ B\ = 0.

8.    Z elementów 10-elementowego zbioru można utworzyć

dokładnie 10! różnych podzbiorów;

nie więcej, niż 120 podzbiorów trzyelementowych;

_ nie mniej, niż 100000 różnych ciągów pięciowyrazowych.

9. Graf prosty G, w którym Vq = {a, b, c, d, e} i Eq = {{a, b}, {a, c}, {a, d}, {6, c), {b, d}, {e, d}} jjest

drzewem;

_ grafem spójnym; grafem pełnym.

10. Czy istnieje graf G, w którym

J D₀{G)    =    0, Di(G)    = 5,    D₂(G)    = 3,    D_k(G) =    0    dla    k >    3;

D₀(G)    =    0, Di{G)    = 6,    D₂{G)    = 4,    D_k{G) =    0    dla    k >    3;

□ D₀(G)    =    0, D_X{G)    = 3,    D₂(G)    = 7,    D₃(G) =    1,    D_k(G)    = 0 dla k > 4.

Zadanie 1: Sformułować i udowodnić zasadę włączania i wyłączania dla dwóch zbiorów. Zadanie 2: Wykazać, że jeżeli a = b (mod n) i c = d (mod n), to ac = bd (mod n).