Lista 2012 2

background image

Wrocław, 10 października 2012

Wydział Informatyki i Zarządzania, rok I
Logika dla informatyków

Zadania – lista 2

1. Ile relacji binarnych można zdefiniować na produkcie kartezjańskim A

B, jeżeli A oraz B są zbiorami

skończonymi o licznościach card(A) = n oraz card(B) = m.

2. Uzupełnij i udowodnij wzory:

a) (A

B)

C = (A

C)

(B

C)

b) (A

B)

C = ?

c) (A

B)

(C

D) = ?

3. Niech X =

def

{a, b, c, d} oraz R

X

2

. Zbadać które spośród własności: symetrii, przeciwsymetrii, zwrot-

ności, przeciwzwrotności, przechodniości, spójności i równoważności mają następujące relacje binarne:

a) R = {<a, a>, <b, b>, <a, b>}

b) R = {<a, a>, <b, b>, <c, c>, <d, d>, <a, b>, <b, a>}

4. Czy prawdziwe są następujące stwierdzenia dotyczące relacji binarnych na X:

a) Suma dwóch relacji symetrycznych jest symetryczna.

b) Część wspólna (przekrój) dwu relacji przechodnich jest przechodnia.

c) Jeżeli R jest relacją przechodnią oraz R

S

X

2

, to S jest relacją przechodnią.

5. Niech [a] =

def

{b

A | <a, b>

R} będzie klasą abstrakcji generowaną przez binarną relację równoważności

R na zbiorze A. Dowieść, że:

a)

A

a

A

a

]

[

b) <a, b>

R wtedy i tylko wtedy, gdy [a] = [b]

c) jeżeli [a]

[b], to [a]

[b]=

6. Niech ID będzie zbiorem identyfikatorów zdefiniowanym następująco:

ID =

def

{x | x jest skończonej długości ciągiem złożonym z liter lub cyfr, którego pierwszym

elementem jest litera}

Czy zdefiniowane poniżej relacje binarne R

1

, R

2

ID

2

są relacjami równoważności? Jeżeli tak, to jakie są

wyznaczone przez nie zbiory ilorazowe?

a) R

1

=

def

{<id

1

, id

2

> | pierwsza litera identyfikatora id

1

jest taka sama jak pierwsza litera

identyfikatora id

2

}

b) R

2

=

def

{<id

1

, id

2

> | identyfikator id

1

czytany wspak jest taki sam identyfikator id

2

}

7. Niech BAZA =

def

Nazwisko

Wiek

Zarobek, gdzie Nazwisko jest zbiorem identyfikatorów, Wiek i Zarobek

są pewnymi podzbiorami nieujemnych liczb całkowitych. Czy zdefiniowane niżej relacje binarne R

1

, R

2

BAZA

2

są relacjami równoważności? Jeżeli tak, to jakie są wyznaczone przez nie zbiory ilorazowe?

a) R

1

=

def

{<<n

1

, w

1

, z

1

>, <n

2

, w

2

, z

2

>> | w

1

= w

2

z

1

= z

2

}

b) R

2

=

def

{<<n

1

, w

1

, z

1

>, <n

2

, w

2

, z

2

>> | w

1

= w

2

|z

1

z

2

| < 1000}

8. Niech R, S

X

2

będą relacjami równoważności. Czy relacjami równoważności są również:

background image

a) R

S

b) R \ S

9. Niech S, T będą relacjami binarnymi na X

2

. Wskaż, które własności są prawdziwe:

a) dom(S

T) = dom(S)

dom(T)

b) dom(S

T)

dom(S)

dom(T)

c) dom(S

T)

dom(S)

dom(T)

10. Niech card(A) = n oraz card(B) = m. Jaka jest liczba funkcji całkowitych oraz częściowych typu A

B?

11. Niech f : X

Y oraz A, B

X. Uzupełnij i udowodnij wzory:

a)

)

(

)

(

)

(

B

f

A

f

B

A

f

b)

)

(

)

(

?

)

(

B

f

A

f

B

A

f

c)

A

A

f

f

?

))

(

(

1


Wyszukiwarka

Podobne podstrony:
Lista 2012 9
Lista 2012 6
Lista 2012 4
Lista 2012 1
Lista 2012 5
Lista 2012 8
Lista 2012 3
Lista 2012 11
rachunek kosztlw dla inynierlw wiczenia lista 2 2012

więcej podobnych podstron