Wrocław, 10 paz
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 �� X2. 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 = {, , }
b) R = {, , , , , }
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 �� X2, to S jest relacją przechodnią.
5. Niech [a] =def {b��A | ��R} będzie klasą abstrakcji generowaną przez binarną relację równoważności
R na zbiorze A. Dowieść, że:
a)
U�[a] =� A
a��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 = {x | x jest skończonej długości ciągiem złożonym z liter lub cyfr, którego pierwszym
def
elementem jest litera}
Czy zdefiniowane poniżej relacje binarne R1, R2 �� ID2 są relacjami równoważności? Jeżeli tak, to jakie są
wyznaczone przez nie zbiory ilorazowe?
a) R1 =def { | pierwsza litera identyfikatora id1 jest taka sama jak pierwsza litera
identyfikatora id2}
b) R2 =def { | identyfikator id1 czytany wspak jest taki sam identyfikator id2}
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 R1, R2 ��
BAZA2 są relacjami równoważności? Jeżeli tak, to jakie są wyznaczone przez nie zbiory ilorazowe?
a) R1 =def {<, > | w1 = w2 Ł� z1 = z2}
b) R2 =def {<, > | w1 = w2 Ł� |z1  z2| < 1000}
8. Niech R, S �� X2 będą relacjami równoważności. Czy relacjami równoważności są również:
a) R �� S
b) R \ S
9. Niech S, T będą relacjami binarnymi na X2. 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) f (A �� B) =� f (A) �� f (B)
b) f (A�� B) ? f (A) �� f (B)
-�1
c) f ( f (A)) ? A