Iloczyn Kartezjański, Relacje Binarne, Grafy, Relacje Porząd

[Racannon]

Witam. to mój pierwszy post więc proszę o wyrozumiałość
Mam kilka zadań, w których przydała by mi się pomoc, są z kilku działów ale umieściłem je w jednym poście żeby nie szukać ich po całym forum

Zadanie 1.Iloczyn Kartezjański - proszę o sprawdzenie
Wyznaczyć zbiór \(\displaystyle{ G \cup H, G \cap H, G \setminus H, H \setminus G}\), jeżeli \(\displaystyle{ G=A \times B}\) i \(\displaystyle{ H=C \times D}\) oraz

\(\displaystyle{ A=\{1,2,3,4\}, B=\{1,2,4,2\}, C=\{1,3,6,1\}, D=\{1,4,6,8\}}\)

\(\displaystyle{ G = A \times B = \\
=\{(1,1),(1,2),(1,4),(1,2),(2,1),(2,2),(2,4),(2,2),(3,1),(3,2),(3,4),(3,2),(4,1),(4,2),(4,4),(4,2)\}}\)

\(\displaystyle{ H = C \times D = \\
=\{(1,1),(1,4),(1,6),(1,8),(3,1),(3,4),(3,6),(3,8),(6,1),(6,4),(6,6),(6,8),(1,1),(1,4),(1,6),(1,8)\}}\)

\(\displaystyle{ G \cap H = \{(1,1),(1,4),(3,1),(3,4)\}}\)

\(\displaystyle{ G \cup H = \{(1,1),(1,2),(1,4),(1,2),(2,1),(2,2),(2,4),(2,2),(3,1),(3,2),(3,4),(3,2),\\
(4,1),(4,2),(4,4),(4,2),(1,6),(1,8),(3,6),(3,8),(6,1),(6,4),(6,6),(6,8)\}}\)

\(\displaystyle{ G \setminus H = \{(1,2),(1,2),(2,1),(2,2),(2,4),(2,2),(3,2),(3,2),(4,1),(4,2),(4,4),(4,2)\}}\)

\(\displaystyle{ H \setminus G = \{(1,6),(1,8),(3,6),(3,8),(6,1),(6,4),(6,6),(6,8),(1,6),(1,8)\}}\)

Zadanie 2. Relacje Binarne - prosze o sprawdzenie
W zbiorze \(\displaystyle{ X \times Y}\) dana jest relacja \(\displaystyle{ R}\). Wyznaczyć wszystkie elementy należące do tej relacji. Sprawdź czy relacja ta jest zwrotna, przeciwzwrotna, symetryczna, antysymetryczna, przechodnia. Czy jest relacją równoważności.

\(\displaystyle{ X=\{1,2,5\}, Y=\{12,13,14,15\}, R=\{(x,y): x|y\}\\
R=\{(1,12),(1,13),(1,14),(1,15),(2,12),(2,14),(5,15)\}}\)

- relacja nie jest zwrotna;
- relacja jest przeciwzwrotna;
- relacja nie jest symetryczna;
- relacja jest przeciwsymetryczna;
- relacja nie jest przechodnia;
- nie jest relacją równoważności;

Zadanie 3. Grafy - tu prosiłbym o jak najdokładniejszą podpowiedz gdyż nie mam kompletnie pojęcia o tym jak narysować ten graf
Sporządz rysunek grafu skierowanego \(\displaystyle{ G}\), w którym zbiór wierzchołków \(\displaystyle{ V(G) = \{ w,x,y,z\}}\), zbiór krawędzi \(\displaystyle{ E(G) = \{a,b,c,d,e,f,g\}}\) , a funkcja \(\displaystyle{ \gamma}\) podana jest w tabeli :
\(\displaystyle{ \begin{tabular}{c|ccccccc} e & a & b & c & d & e & f & g \\ \hline \gamma (e) & (x,w) & (w,x) & (x,x) & (w,z) & (w,y) & (w,z) & (z,y) \\ \hline \end{tabular}}\)

Wskaż w tym grafie cykl. Jaka jest najkrótsza droga z wierzchołka \(\displaystyle{ x}\) do \(\displaystyle{ y}\). Jaka jest długość tej drogi. Czy istnieje tylko jedna taka droga? Napisz macierz sąsiedztwa dla tej relacji. Czy para \(\displaystyle{ (z,x)}\) jest w relacji osiągalności.

Zadanie 4. Relacje porządkujące - proszę o sprawdzenie
W zbiorze \(\displaystyle{ X}\) dana jest relacja \(\displaystyle{ R}\). Zbadać, czy ta relacja jest:
1) relacja porządku,
2) relacją liniowego porządku,
3) relacją dobrego porządku.
W przypadku gdy jest to relacja porządku, wyznaczyć elementy: maksymalny, minimalny, największy, najmniejszy, ograniczenia górne, ograniczenia dolne, kres górny, kres dolny (o ile takie istnieją).

a) \(\displaystyle{ X=\{2^{n}: n \in \mathbb N\}}\) zaś \(\displaystyle{ R=\{(x,y): x|y\}}\)
jest relacją porządku;
jest relacją liniowego porządku;
jest relacją dobrego porządku;
element maksymalny i najwiekszy nie istnieją
elementem minimalnym i najmiejszym jest liczba \(\displaystyle{ 2}\);

[Kartezjusz]

1. Usuń ze zbiorów powtarzające się elementy
2.Dobrze
3. Zapis:\(\displaystyle{ e=a \wedge \phi(e)=(x,w)}\) oznacza,że krawędź oznaczysz literką \(\displaystyle{ a}\)
jeśli połączysz wierzchołek \(\displaystyle{ x}\)z wierzchołkiem\(\displaystyle{ w}\) tak,że strzałka pokazująca kierunek pokazuje na \(\displaystyle{ w}\).
Macierz sąsiedztwa mówi,że jeśli \(\displaystyle{ (xRy \Leftrightarrow}\) istnieje krawędź łącząca te dwa wierzchołki) zachodzi dajesz 1 jeśli nie 0
Relacja osiągalności \(\displaystyle{ xRy \Leftrightarrow}\) istnieje ciąg krawędzi który z x doproadzi na y
Cykl-podgraf realizujący relację osiągalności dla pary \(\displaystyle{ (x,x)}\)

[dosiu]

dlaczego w zadaniu 2. nie jest zwrotna ?
przecież każdy element sam ze sobą jest zwrotny ;/
chyba inaczej się patrzy na zwrotność jeśli elementy pochodzą z dwóch różnych zbiorów?

[Jan Kraszewski]

chyba inaczej się patrzy na zwrotność jeśli elementy pochodzą z dwóch różnych zbiorów?

Dla mnie rozpatrywanie zwrotności w takim przypadku nie ma sensu, choć na siłę można sobie wyobrazić, jak taka definicja mogłaby wyglądać dla różnych zbiorów. Podobną uwagę mam do innych własności relacji.

JK

[dosiu]

tzn że jeśli elementy pochodzą z dwóch różnych zbiorów (np. \(\displaystyle{ X=\{1,2,3\}, Y=\{a,b,c\}, R(x,y) \Leftrightarrow x=y}\)) a pytają mnie czy relacja jest zwrotna to odpowiedzią poprawną jest że nie ?

[Jan Kraszewski]

Pytanie jest źle postawione. Po pierwsze nie wiadomo, czym są \(\displaystyle{ a,b,c}\). Po drugie, nie wiem, co miałaby zwrotność oznaczać dla relacji pomiędzy elementami różnych zbiorów. Dla mnie definiowanie tej własności w tej sytuacji nie ma sensu, więc z mojego punktu widzenia pytanie jest źle postawione.

Ale jeżeli pokażesz mi definicję takiej "zwrotności", to Ci odpowiem.

JK

[dosiu]

no nie znam takowej więc zostawię już ten temat. Rozumiem, że odpowiedzi podane przez Racannon w zadaniu 2 są poprawne ?

[Jan Kraszewski]

Rozumiem, że odpowiedzi podane przez Racannon w zadaniu 2 są poprawne ?

Po drugie, nie wiem, co miałaby zwrotność oznaczać dla relacji pomiędzy elementami różnych zbiorów. Dla mnie definiowanie tej własności w tej sytuacji nie ma sensu, więc z mojego punktu widzenia pytanie jest źle postawione.

A skąd ja mam wiedzieć, jak nie znam definicji tych własności w tej sytuacji?

JK

[dosiu]

to uważasz, że w zadaniu 2 zbiory X i Y są podane tylko po to żeby sprawdzić czy rozumiem na czym polega relacja, a cechy relacji już powinienem sprawdzać na całej przestrzeni ?

bo wtedy mi wychodzą odpowiedzi:
- relacja jest zwrotna;
- relacja nie jest przeciwzwrotna;
- relacja nie jest symetryczna;
- relacja jest przeciwsymetryczna;
- relacja jest przechodnia;
- jest relacją równoważności;

[Jan Kraszewski]

to uważasz, że w zadaniu 2 zbiory X i Y są podane tylko po to żeby sprawdzić czy rozumiem na czym polega relacja,

Nic nie uważam. Skoro wg mnie zadanie jest bez sensu, to jak przypuszczać, do czego ma służyć?

a cechy relacji już powinienem sprawdzać na całej przestrzeni ?

Na jakiej "całej przestrzeni"?

JK

[Kartezjusz]

Relacja to jest podzbiór płaszczyzny kartezjańskiej ,a nasz podzbiór
\(\displaystyle{ A \times B \subset \mathbb{N} \times \mathbb{N}}\) to ten wypisany przez koleżankę wówczas w języku nasze własności można zapisać w postaci
ZWROTNOŚĆ
\(\displaystyle{ (x,x) \in A \times B}\)
SYMETRIA
\(\displaystyle{ (x,y) \in A \times B \Rightarrow (y,x) \in A \times B}\)

[Jan Kraszewski]

Opisujesz inną sytuację. I zapominasz o kwantyfikatorach.

JK

[Kartezjusz]

Ja tak rozumiem to zadanie.

[Jan Kraszewski]

Każdy może na swój sposób rozumieć to zadanie, co oznacza, że jest to złe zadanie.

JK