Wrocław, 20 paz
dziernika 2015
Wydział Informatyki i Zarządzania, rok I
Logika dla informatyków
Zadania  lista 3
1. Niech R �� X �� Y oraz niech A, B �� X. Pokazać, że
R(A �� B) �� R(A) �� R(B)
2. Niech S, T będą relacjami binarnymi na X. 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)
3. Sprawdzić, czy przechodnie są wszystkie relacje binarne R �� X2 określone na zbiorze X spełniają-
cym warunek:
a) card(X) = 1
b) card(X) = 2
c) card(X) = 3
4. Jeśli R1 �� X 2, to R2 �� X 2 takie, że R1 �� R2 nazywamy rozszerzeniem relacji R1. Czy każdą relację
R �� X 2 można rozszerzyć do relacji:
a) symetrycznej,
b) przeciwsymetrycznej,
c) zwrotnej,
d) przeciwzwrotnej,
e) przechodniej,
f) spójnej.
5. Niech R będzie relacją binarną w zbiorze X. Pokazać, że
a) Jeżeli R jest relacją przechodnią, to R ��R �� R.
b) Jeżeli R jest relacją symetryczną, to R �� R 1.
6. Dla podanych zbiorów X i relacji R w X sprawdzić, czy R jest relacją równoważności.
a) X jest zbiorem liczb całkowitych; ��R wtedy i tylko wtedy, gdy x+y jest liczbą parzystą.
b) X jest zbiorem liczb rzeczywistych; ��R wtedy i tylko wtedy, gdy |x y| Ł� 2.
c) X jest zbiorem punktów na płaszczyz
nie; <,>��R wtedy i tylko wtedy, gdy
x1=y2.
7. Sprawdzić czy suma mnogościowa i przekrój relacji równoważności R oraz Q na zbiorze X są
relacjami równoważności? Odpowiedz
uzasadnić. Jeśli tak, to opisać ich zbiory ilorazowe.
8. Ile jest różnych relacji równoważności na zbiorze n-elementowym?
9. Niech będzie dany pewien graf G = (V, A), gdzie A �� V2. Jaką interpretację można przypisać
złożeniu relacji A? Co oznaczają A2, ..., An dla n = 2, 3, & ?
10. Niech |" będzie relacją częściowego porządku (tzn. relacją zwrotną, antysymetryczną i
przechodnią) na zbiorze A oraz niech B �� A. Mówimy, że a��A jest:
 elementem najmniejszym w zbiorze B, jeśli "�b��B �� a |" b,
 elementem największym w zbiorze B, jeśli "�b��B �� b |" a,
 elementem minimalnym w zbiorze B, jeśli "�b��B �� ��(b |" a),
 elementem maksymalnym w zbiorze B, jeśli "�b��B �� ��(a |" b).
Niech X będzie podzbiorem liczb naturalnych X = {1, 2, 3, 4, 5, 6}, oraz niech B będzie
podzbiorem zbioru A = 2X, do którego należą tylko te podzbiory, których suma elementów jest
mniejsza od 7. Do B należy, na przykład, zbiór {1, 2, 3}, którego suma elementów wynosi 6.
Rozpatrzmy porządek częściowy określony na zbiorze B przez inkluzję. Wyznaczyć w B
elementy:
a) najmniejszy,
b) największy,
c) minimalny,
d) maksymalny.