1367

Zestaw zadań nr 1.

Zadanie 1.

Wykazać następujące prawa na zbiorach:

a)    (AUB)\C = (A\C)U(B\C)₁

b)    A\(B\C) = (A\B)U(AnC),

c)    A + {B + C) = (A+ B) + C,

d)    An(B + C) = (Ar\B) + (AnC).

Zadanie 2.

Obliczyć:

•>£(;)• »£*•(;). -> £*«*-»•(:)■

k=0 ^X 7    *=1 ^x 7    k= 2    ^v 7

Zadanie 3.

Co to jest injekcja. surjekcja ? Podać odpowiednie przykłady. Wykazać, że złożenie injekcji jest injekcją oraz złożenie surjekcji jest surjekcją.

Zadanie 4.

Sprawdzić jakie własności ma relacja R C R², gdzie xRy •<=> 4|(x — y.)

Jeżeli jest relacją równoważności, to wypisać wszystkie klasy abstrakcji.

Zadanie 5.

Wykazać, że:

1)    relacja R jest zwrotna wtedy i tylko wtedy, gdy A C /?.

2)    relacja R jest symetryczna wtedy i tylko wtedy, gdy R C R ^l <=> R~^l C /?<=►/?= Z?"¹,

3)    relacja R jest przechodnia wtedy i tylko wtedy, gdy R o R c R.

Zadanie 6.

Pokazać, że jeżeli R jest relacją zwrotną i przechodnią, to R D R~^l jest relacją równoważności. Na zbiorze A^r\«_n«-« definiujemy relację:

[a] S[b] & a Rb.

Wykazać, że relacja S jest dobrze określona oraz S jest częściowym porządkiem.

Zadanie 7.

Wyrazić zwrotność, symetryczność oraz przechodniość relacji w terminach macierzy relacji. Zadanie 8.

Pokazać, że (N, |) jest częściowym porządkiem. Czy jest liniow ym porządkiem ? Czy istnieje element maksymalny, minimalny ?

Zadanie 9.

Niech (i4i,-<i), (.<42, -<2) będą częściowymi porządkami. Pokazać, że definicja (#1,2:2) -< (j/1,2/2) *-* (x\ -< 2/1) A (2:2 -<2 3/2) dla (271,2:2), (1/1, j/2) € Ai x A2 pozwala wprowadzić częściowy porządek na zbiorze Ai x A₂. Pokazać przykład dwóch liniowych |>orządków' (A\. -<i), (A₂. -<2)- takich, że (Ai x i4₂, -<) nie jest liniowym porządkiem.

Zadanie 10.

(★) Pokazać, że funkcja / : N² —* N, taka, że /(n, A) = ^(n + k + l)(n + A') + A jest injekcja.