Zadania z matematyki dyskretnej - 10 zadań, 1 strona.
Zestaw zada´
n nr 1.
Zadanie 1.Wykaza´
c nastepujace prawa na zbiorach:
‘
‘
a) (A ∪ B) \ C = (A \ C) ∪ (B \ C),b) A \ (B \ C) = (A \ B) ∪ (A ∩ C),c) A ÷ (B ÷ C) = (A ÷ B) ÷ C,d) A ∩ (B ÷ C) = (A ∩ B) ÷ (A ∩ C).
Zadanie 2.Obliczy´
c:
n
n
n
n
n
n
a)
,
b)
k ·
,
c)
k(k − 1) ·
.
k
k
k
k=0
k=1
k=2
Zadanie 3.Co to jest injekcja, surjekcja ? Poda´
c odpowiednie przyklady. Wykaza´
c, ˙ze zlo˙zenie injekcji jest
injekcja oraz zlo˙zenie surjekcji jest surjekcja.
‘
‘
Zadanie 4.Sprawdzi´
c jakie wlasno´sci ma relacja R ⊂
2
R , gdzie xRy ⇔ 4|(x − y.)
Je˙zeli jest relacja r´
ownowa˙zno´sci, to wypisa´
c wszystkie klasy abstrakcji.
‘
Zadanie 5.Wykaza´
c, ˙ze:
1) relacja R jest zwrotna wtedy i tylko wtedy, gdy ∆ ⊂ R,2) relacja R jest symetryczna wtedy i tylko wtedy, gdy R ⊂ R−1 ⇔ R−1 ⊂ R ⇔ R = R−1,3) relacja R jest przechodnia wtedy i tylko wtedy, gdy R ◦ R ⊂ R.
Zadanie 6.Pokaza´
c, ˙ze je˙zeli R jest relacja zwrotna i przechodnia, to R ∩ R−1 jest relacja r´
ownowa˙zno´sci. Na
‘
‘
‘
‘
zbiorze X\R∩R−1 definiujemy relacje:
‘
[a] S [b] ⇔ a R b.
Wykaza´
c, ˙ze relacja S jest dobrze okre´slona oraz S jest cze´sciowym porzadkiem.
‘
‘
Zadanie 7.Wyrazi´
c zwrotno´s´
c, symetryczno´s´
c oraz przechodnio´s´
c relacji w terminach macierzy relacji.
Zadanie 8.Pokaza´
c, ˙ze (N, |) jest cze´sciowym porzadkiem. Czy jest liniowym porzadkiem ? Czy istnieje element
‘
‘
‘
maksymalny, minimalny ?
Zadanie 9.Niech (A1, 1), (A2, 2) beda cze´sciowymi porzadkami. Pokaza´c, ˙ze definicja (x
‘ ‘
‘
‘
1, x2)
(y1, y2) ↔
(x1
y1) ∧ (x2
2 y2) dla (x1, x2), (y1, y2) ∈ A1 × A2 pozwala wprowadzi´
c cze´sciowy porzadek
‘
‘
na zbiorze A1 × A2. Pokaza´c przyklad dw´
och liniowych porzadk´
ow (A
‘
1,
1), (A2,
2), takich, ˙
ze
(A1 × A2,
) nie jest liniowym porzadkiem.
‘
Zadanie 10.( ) Pokaza´
c, ˙ze funkcja f :
2
N → N, taka, ˙ze f (n, k) = 1 (n + k + 1)(n + k) + k jest injekcja.
2
‘
... zobacz całą notatkę
Komentarze użytkowników (0)