grupy R. Katarzyniak/sem. zimowy 2012/2013
Logika dla informatyków zadania pomocnicze
Zadanie 1. Zbadać, które spośród własności symetrii, przeciwsymetrii, zwrotności,
przechodniości, spójności oraz równoważności posiadają następujące relacje RXX,
X={a,b,c}
a) R = {
, , }
b) R = {,,,}
c) R = {,,,,,}
Zadanie 2. Zbadać, czy są przechodnie następujące relacje R XX, X={a,b,c}
a) R = Ć
b) R = {}
c) R = {, }
Zadanie 3. Dane są trzy definicje spójności relacji RXX:
a) Relacja RXX jest relacją spójną wtedy i tylko wtedy, gdy dla każdej pary obiektów
XX spełniona jest formuła RR
b) Relacja RXX jest relacją spójną wtedy i tylko wtedy, gdy dla każdej pary obiektów
XX spełniona jest formuła RR
c) Relacja RXX jest relacją spójną wtedy i tylko wtedy, gdy dla każdej pary obiektów
XX jeżeli xąy, to spełniona jest formuła RR
gdzie spójniki oraz definiowane są w następujący sposób:
p q pq pq
0 0 0 0
0 1 1 1
1 0 1 1
1 1 1 0
Zbadać, które z relacji binarnych przedstawionych poniższymi grafami są spójne w sensie
definicji (a)-(c):
str. 1
G1 G2
1 2
1 2
4 3
4 3
G3 G4
1 2 1 2
4 3 4 3
Zadanie 4. Niech dana będzie relacja binarna R{0,1,2,3,4}{0,1,2,3,4}, gdzie {0,1,2,3,4}
oznacza zbiór liczb oraz para liczb R wtedy i tylko wtedy, gdy liczba x dzieli liczbę y
bez reszty. Ustalić, którą spośród następujących cech posiada relacja R:
a) symetrii,
b) przeciwsymetrii,
c) zwrotności,
d) przechodniości,
e) spójności
Zadanie 5. Niech dana będzie relacja binarna PXX, gdzie X oznacza zbiór liczb
rzeczywistych oraz para liczb X wtedy i tylko wtedy, gdy zachodzi x + y = 2. Ustalić,
którą spośród następujących cech posiada relacja P:
a) symetrii,
b) przeciwsymetrii,
c) zwrotności,
d) przechodniości,
e) spójności
f) równoważności.
str. 2
Zadanie 6. Niech dana będzie relacja binarna PXX, gdzie X oznacza zbiór liczb
rzeczywistych oraz para liczb X wtedy i tylko wtedy, gdy zachodzi x +ył1. Ustalić,
którą spośród następujących cech posiada relacja P:
a) symetrii,
b) przeciwsymetrii,
c) zwrotności,
d) przechodniości,
e) spójności
f) równoważności.
Zadanie 7. Wskazać stwierdzenia prawdziwe:
a) Nie jest prawdą, że suma dwóch relacji symetrycznych PXX i QXX określonych
na zbiorze X jest symetryczna na zbiorze X.
b) Prawdą jest, że jeżeli relacja RXX jest przechodnia na zbiorze X i RSXX , to
S jest relacją przechodnią na zbiorze X.
Zadanie 8. Niech dane będą relacje R1XX, R2XX, gdzie X pewien zbiór. Relację R2
nazywamy rozszerzeniem relacji R1 wtedy i tylko wtedy, gdy zachodzi R1R2. Zbadać, czy
każdą relację RXX można rozszerzyć do pewnej relacji:
a) symetrycznej
b) przeciwsymetrycznej
c) zwrotnej
d) przeciwzwrotnej
e) przechodniej
Zadanie 9. Niech C oznacza zbiór liczb całkowitych i niech xC, yC. Przyjmujemy, że
R wtedy i tylko wtedy, gdy x-yC. Czy relacja R jest relacją równoważności?
Zadanie 10. Niech X oznacza zbiór trójkątów równobocznych na płaszczyznie i niech xX,
yX. Przyjmujemy, że R wtedy i tylko wtedy, gdy x i y mają równe pola. Czy relacja
R jest relacją równoważności?
Zadanie 11. Niech dany będzie zbiór liczb naturalnych Z={1,2,3,4,5}. Dla dowolnego xZ
oraz dowolnej liczby naturalnej wą0 przyjmijmy, że symbol mod(x,w) oznacza resztę z
dzielenia x przez w. Niech dane będą następujące relacje binarne:
R1) Relacja R1ZZ taka, że para R1 wtedy i tylko wtedy, gdy
mod(x,1)=mod(y,1).
tj. liczba x i liczba y jest w relacji R1 wtedy i tylko wtedy, gdy reszta z dzielenia liczby
x przez 1 równa jest reszcie z dzielenia liczby y przez 1.
R2) Relacja R2ZZ taka, że para R2 wtedy i tylko wtedy, gdy
mod(x,2)=mod(y,2).
str. 3
R3) Relacja R3ZZ taka, że para R3 wtedy i tylko wtedy, gdy
mod(x,6)=mod(y,6).
Udowodnić, że każda z powyższych relacji jest relacją równoważności. Każdą z relacji
przedstawić w następujący sposób:
a) za pomocą grafu skierowanego Gi, i=1,2,3.
b) za pomocą macierzy binarnej Mi, i=1,2,3.
c) za pomocą zbioru par RiZZ, i=1,2,3.
d) jako podział Pi zbioru Z, i=1,2,3.
Zadanie 12. Niech dana będzie relacja binarna reprezentowana grafem:
1 2
3
Ustalić, czy relacja ta posiada własność "x"y (R Ł R) R!
str. 4
Wyszukiwarka
Podobne podstrony:
plik 04 LI zadania pomocnicze nr 3 (listopad 2012) dodatek
plik 03 LI zadania pomocnicze nr 2 (listopad 2012)
plik 01 LI przyklad testu (listopad 2012)
Zadanie Projektowe Nr 2
zadanie zajęcia nr 4
Chemia PR OPERON Listopad 2012 ODP
Zadanie Projektowe nr 1 do pdf
Listopad 2012 Operon
Dane Do Zadania Prpjektowego Nr 2 z Przedmiotu Drogi Szynowe
Higgs (listopad 2012)
Listopad 2012
więcej podobnych podstron