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ż:
