Matematyka Dyskretna
Kierunek: Inżynieria Systemów
Semestr Letni  2014/2015
Lista 6
1. Zakładając, że różne litery oznaczają różne elementy, zbadać które spośród wła-
sności: symetrii, asymetrii, antysymetrii, zwrotności, przeciwzwrotności, przechod-
niości, spójności oraz równoważności mają następujące relacje R ą" X2, gdzie X =
{a, b, c, d}
" R = { a, a , b, b , a, b } " R = { a, b , b, a , c, a , a, c , c, d , a, d }
" R = { a, a , b, b , c, c , d, d , a, b , b, a } " R = { a, b , a, c , b, c , c, c , a, a , b, b }
2. Wskazać, co jest prawdziwe:
" Niech X = {a, b, c}, R Ä…" X × X i R = { a, a , b, b , a, b }. Relacja R jest relacjÄ… zwrotnÄ….
" Niech X = {a, b, c}, R Ä…" X × X i R = { a, b , b, a , c, a , a, c }. Relacja R jest relacjÄ… przechodniÄ….
" Niech dana bÄ™dzie relacja binarna R Ä…" {0, 1, 2, 3, 4} × {0, 1, 2, 3, 4}, gdzie {0, 1, 2, 3, 4} jest zbiorem liczb. Para
liczb x, y należy do relacji R ( x, y " R) wtedy i tylko wtedy, gdy liczba x bez reszty dzieli liczbę y. Relacja
R jest relacjÄ… symetrycznÄ….
" Niech Z oznacza zbiór liczb caÅ‚kowitych, R Ä…" Z × Z i niech x, y " Z. Przyjmujemy, że x, y " R wtedy i tylko
wtedy gdy x - y " Z. Relacja jest relacją równoważności i generuje nieskończenie wiele klas abstrakcji.
3. Niech dana będzie tabela:
U Cena Rok Stan
n1 wysoka 1966 dobry
n2 niska 1971 zły
n3 średnia 1971 dobry
n4 wysoka 1968 dobry
gdzie n1, n2, n3, n4 są obiektami, Cena, Rok, Stan są tzw. atrybutami (cechami obiektów),
a w komórkach wpisane są wartości atrybutów wymienionych w kolumnie dla obiektów
podanych w wierszach.
Mówimy, że obiekty x i y są nierozróżnialne ze względu na atrybut a " {Cena, Rok, Stan}
wtedy i tylko wtedy, gdy wartości atrybutu a dla obiektów x i y są równe (symbolicznie
piszemy x a"a y). Wskazać, co jest prawdziwe:
" Zachodzi n1 a"Cena n2,
" Relacja nierozróżnialności a"Cena obiektów jest relacją równoważności nad zbiorem obiektów U
" Iloczyn relacji nierozróżnialności a"Cena i a"Stan jest relacją równoważności nad zbiorem U,
" Iloczyn relacji nierozróżnialności a"Rok i a"Stan nie jest relacją równoważności nad zbiorem U.
4. Niech X oznacza zbiór trójkątów równobocznych na płaszczyz
nie i niech x, y " X.
Przyjmujemy, że x, y " R wtedy i tylko wtedy, gdy x i y mają równe pola. Czy
relacja R jest relacją równoważności?
5. Zbadać które spośród własności: symetrii, silnej i słabej antysymetrii, zwrotności,
przeciwzwrotności, przechodniości, spójności oraz równoważności ma relacja przed-
stawiona grafem:
1
Matematyka Dyskretna
Kierunek: Inżynieria Systemów
Semestr Letni  2014/2015
Lista 2 - elementy algebry zbiorów bez powtórzeń
1. Podać elementy następujących zbiorów:
a) {a} c) {{a,b},{a}} e) {x " N : x2 < 7} g) {x " Q : (x + 1)2 < 0}
b) {{a}} d) {{{a}},{a},a} f) {x " Q : x2 = 2}
2. Obliczyć A )" B, A *" B, A B, B A dla następujących zbiorów A i B:
a) A = {{a, {a}}, a}, B = {a, {a}} b) A = {x " R : |x| 5}, B = {x " R : -6 x < 0}
3. Dowieść, że dla dowolnych A, B, C, D zachodzą równości:
a) (A *" B) C = (A C) *" (B C) e) (A )" B) *" (A B) = A
b) (A B) )" (C D) = (A )" C) (B *" D) f) (A *" B) )" B = B
c) (A B) *" B = A *" B g) (A *" B) )" C = (A )" C) *" (B )" C)
d) A B = A (A )" B) h) (A )" B) *" C = (A *" C) )" (B *" C)
4. Zbudować zbiory potęgowe dla następujących zbiorów:
a) A = {1, 2} b) B = {+, -, 0} c) C = {{a, b}, c, {a}} d) D = {"}
5. Podać przykłady dwóch (możliwie niepustych) zbiorów, dla których:
a) suma jest równa iloczynowi c) różnica jest równa iloczynowi
b) suma jest podzbiorem iloczynu d) różnica jest równa sumie
6. Określamy dzielenie wzorem A : B = A *" B , gdzie B jest dopełnieniem zbioru B
względem uniwersum U, tj. B = U B. Zapisać bez wykorzystania symbolu dzielenia
oraz uprościć poniższe wyrażenia:
a) A : (B )" C) b) A : (B *" C) c) A )" (B : A)
a następnie  przeliczyć je podstawiając następujące zbiory A, B i C:
A = {x " R : |x| 5} B = {x " R : -6 x < 0} C = {x " N : 4 x2 < 16}
7. Dla zadanych zbiorów A = {{a}, {(a, b), a}} oraz B = {{(a, b)}, {a}, b} wskaż zdania
prawdziwe.
a) (a, b) " A )" B b) {a} " 2A c) {a} Ä…" A *" B d) |2A| 7
8. Niech będą dane zbiory A = {1, 3, 4, 5}, B = {x " N : 2 x < 7}, uniwersum
U = {x " N : 1 x 10} oraz niech będzie określone działanie A B = (A *" B ) ,
gdzie X oznacza dopełnienie zbioru, tj. X = U X. Wskaż zdania prawdziwe (dla
zadanych zbiorów):
a) {7} " A B b) A B = " c) A " (A B) d) (A B) = (B A)

1
Matematyka Dyskretna
Kierunek: Inżynieria Systemów
Semestr Letni  2014/2015
Lista 5 - iloczyn kartezjański
1. Udowodnić, że:
" A×(B *"C) = (A×B)*"(A×C) " A×(B )"C) = (A×B))"(A×C) " A×(B C) = (A×B) (A×C)
" (B *"C)×A = (B ×A)*"(C ×A) " (B )"C)×A = (B ×A))"(C ×A) " (B C)×A = (B ×A) (C ×A)
2. Pokazać, że dla dowolnych zbiorów A, B, C jeÅ›li A Ä…" B to A × C Ä…" B × C. Jak należy
zmodyfikować założenia, aby symbol słabej inkluzji można było w wykazywanej wła-
sności zastąpić znakiem równości? (Uwaga: Dla jednoznaczności w treści zadania
wykorzystujemy symbol inkluzji ą" dopuszczający równość zbiorów.)
3. Niech |X| oznacza liczbę elementów skończonego zbioru X. Pokazać, że dla dowol-
nych zbiorów skoÅ„czonych A, B zachodzi równość |A| · |B| = |A × B|.
1
Matematyka Dyskretna
Kierunek: Inżynieria Systemów
Semestr Letni  2014/2015
Lista 1a - Rachunek zdań (tautologie)
1. Ustalić, czy są tautologiami:
a) (Ä… '" ²) Ò! Ä…,
b) Ä… Ò! (Ä… (" ²),
c) ŹŹą Ô! Ä…,
d) (Ä… '" Ä…) Ô! Ä…,
e) (Ä… (" Ä…) Ô! Ä…,
f) (Ä… '" ²) Ô! (² '" Ä…),
g) (Ä… (" ²) Ô! (² (" Ä…),
h) Ź(Ä… '" ²) Ô! (Źą (" Ź²),
i) Ź(Ä… (" ²) Ô! (Źą '" Ź²).
2. Ustalić, czy są tautologiami:

a) (Ä… '" ²) '" Å‚ Ô! Ä… '" (² '" Å‚) ,

b) (Ä… (" ²) (" Å‚ Ô! Ä… (" (² (" Å‚) ,

c) Ä… '" (² (" Å‚) Ô! (Ä… '" ²) (" (Ä… '" Å‚) ,

d) Ä… (" (² '" Å‚) Ô! (Ä… (" ²) '" (Ä… (" Å‚) .
3. Ustalić, czy są tautologiami:
a) (Ä… Ò! ²) Ô! (Źą (" ²),
b) (Ä… (" ²) Ô! (Źą Ò! ²),
c) ((Ä… '" ²) Ò! Å‚) Ô! (Ä… Ò! (² Ò! Å‚)),
d) Ź(Ä… Ò! ²) Ô! (Ä… '" Ź²),
e) (Ä… Ô! ²) Ô! (Ä… Ò! ²) '" (² Ò! Ä…),

f) Ź(Ä… Ô! ²) Ô! Ź(Ä… Ò! ²) (" Ź(² Ò! Ä…) ,
g) (Ź² Ò! Ź(Ä… Ò! Ä…)) Ò! ²,
h) (Ä… Ò! ²) (" (Ä… '" Ź²),
i) ((Ä… Ô! ²) Ô! Å‚) Ô! (² Ô! (Ä… Ô! Å‚)).
1