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 ⊆ X

2

, gdzie X =

{a, b, c, d}

• R = {ha, ai, hb, bi, ha, bi}

• R = {ha, ai, hb, bi, hc, ci, hd, di, ha, bi, hb, ai}

• R = {ha, bi, hb, ai, hc, ai, ha, ci, hc, di, ha, di}

• R = {ha, bi, ha, ci, hb, ci, hc, ci, ha, ai, hb, bi}

2.

Wskazać, co jest prawdziwe:

• Niech X = {a, b, c}, R ⊆ X × X i R = {ha, ai, hb, bi, ha, bi}. Relacja R jest relacją zwrotną.

• Niech X = {a, b, c}, R ⊆ X × X i R = {ha, bi, hb, ai, hc, ai, ha, ci}. 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 hx, yi należy do relacji R (hx, yi ∈ 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 hx, yi ∈ 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

n

1

wysoka

1966

dobry

n

2

niska

1971

zły

n

3

średnia

1971

dobry

n

4

wysoka

1968

dobry

gdzie n

1

, n

2

, n

3

, n

4

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

y). Wskazać, co jest prawdziwe:

• Zachodzi n

1

≡

Cena

n

2

,

• Relacja nierozróżnialności ≡

Cena

obiektów jest relacją równoważności nad zbiorem obiektów U

• Iloczyn relacji nierozróżnialności ≡

Cena

i ≡

Stan

jest relacją równoważności nad zbiorem U ,

• Iloczyn relacji nierozróżnialności ≡

Rok

i ≡

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łaszczyźnie i niech x, y ∈ X.
Przyjmujemy, że hx, yi ∈ 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}

b) {{a}}

c) {{a,b},{a}}

d) {{{a}},{a},a}

e) {x ∈

N : x

2

< 7}

f) {x ∈

Q : x

2

= 2}

g) {x ∈

Q : (x + 1)

2

< 0}

2.

Obliczyć A ∩ B, A ∪ B, A r B, B r 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) r C = (A r C) ∪ (B r C)

b) (A r B) ∩ (C r D) = (A ∩ C) r (B ∪ D)

c) (A r B) ∪ B = A ∪ B

d) A r B = A r (A ∩ B)

e) (A ∩ B) ∪ (A r B) = A

f) (A ∪ B) ∩ B = B

g) (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C)

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

b) suma jest podzbiorem iloczynu

c) różnica jest równa iloczynowi

d) różnica jest równa sumie

6.

Określamy dzielenie wzorem A : B = A ∪ B

0

, gdzie B

0

jest dopełnieniem zbioru B

względem uniwersum U , tj. B

0

= U rB. 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 ¬ x

2

< 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} ∈ 2

A

c) {a} ⊆ A ∪ B

d) |2

A

| ­ 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

0

∪ B

0

)

0

,

gdzie X

0

oznacza dopełnienie zbioru, tj. X

0

= U r X. Wskaż zdania prawdziwe (dla

zadanych zbiorów):

a) {7} ∈ A  B

b) A  B 6= ∅

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)

• (B ∪ C) × A = (B × A) ∪ (C × A)

• A × (B ∩ C) = (A × B) ∩ (A × C)

• (B ∩ C) × A = (B × A) ∩ (C × A)

• A×(B rC) = (A×B)r(A×C)

• (B rC)×A = (B ×A)r(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