Relacje — macierz i graf relacji, złożenie, własności, porządki i optimum Pareto · Matematyka

Po co ekonomiście relacje?

Obserwujesz na Instagramie znanego piłkarza. On Ciebie raczej nie obserwuje. Na Facebooku jest inaczej: jeśli Ty jesteś znajomym Kasi, to Kasia jest znajomą Twoją — zawsze w obie strony. To dwa różne rodzaje powiązań między ludźmi, a matematyka ma na nie nazwę: relacja. W pierwszym przypadku kierunek ma znaczenie, w drugim nie — i to jest jedna z własności relacji, które tu poznasz.

W ekonomii relacje to przede wszystkim porównania: „inwestycja X jest nie gorsza od Y”, „ten kandydat jest lepszy od tamtego”. Kłopot zaczyna się, gdy kryteriów jest kilka. Inwestycja z największym zyskiem ma zwykle największe ryzyko, a najtańsze mieszkanie jest najdalej od uczelni. Nie da się wskazać jednego zwycięzcy, ale da się odrzucić warianty, które przegrywają z innym pod każdym względem. To, co zostanie, to zbiór Pareto — na końcu modułu policzysz go na macierzach, tak jak na kolokwium.

Co będzie na kolokwium

Z relacji na kolokwium wraca sześć typów poleceń. Każde ma tu przepis, rozwiązane przykłady i ćwiczenia z natychmiastową odpowiedzią.

1
„Wypisz pary relacji i zapisz ją w postaci macierzy (grafu)”
Sprawdzasz warunek dla każdej pary $(x, y)$ : spełniony → 1, niespełniony → 0. Wiersze to pierwszy zbiór, kolumny — drugi.
Przepis i przykłady ↓Ćwiczenia ↓jak w Zad. 3, str. 49–50
2
„Wyznacz $P \cup R$ , $P \cap R$ , $P ∖ R$ , $P^{'}$ , $P^{- 1}$ ”
Działania jak na zbiorach, komórka po komórce. Przy odwrotności wiersze zamieniasz z kolumnami.
Przepis i przykłady ↓Ćwiczenia ↓
3
„Czy złożenie relacji jest wykonalne? Wyznacz złożenie”
Sprawdzasz, czy „środkowe” zbiory się zgadzają. Komórka $(x, z)$ to 1, gdy wiersz $x$ i kolumna $z$ mają jedynkę na tej samej pozycji.
Przepis i przykłady ↓Ćwiczenia ↓jak w Zad. 3, str. 49–50
4
„Zbadaj własności relacji (zwrotność, symetryczność, …, przechodniość)”
Patrzysz na przekątną, na pary komórek symetrycznych względem przekątnej i na złożenie $R \circ R$ .
Przepis i przykłady ↓Ćwiczenia ↓jak w Zad. 1, str. 58, i)
5
„Czy relacja jest relacją porządkującą? Jaką?”
Najpierw przechodniość, potem stopień asymetrii, na końcu spójność — i odczytujesz pole ze schematu.
Przepis i przykłady ↓Ćwiczenia ↓
6
„Wyznacz zbiór rozwiązań Pareto”
Macierze preferencji → część wspólna $M$ → zaostrzenie $S$ → kolumny z samych zer.
Przepis i przykłady ↓Ćwiczenia ↓jak w Zad. 2 i 3, str. 68

Polecenia mogą brzmieć trochę inaczej („przedstaw”, „podaj”, „zbadaj”, „ustal”). Liczy się to, o co pyta zadanie: o pary, o działanie, o złożenie, o własności, o typ porządku czy o zbiór Pareto.

Relacja — pojęcia od podstaw

Przykład z życia: $A$ to studenci (Ola, Kuba, Ewa), a $B$ — przedmioty (matematyka, mikroekonomia). Iloczyn $A \times B$ ma $3 \cdot 2 = 6$ par — każdy student z każdym przedmiotem. Relacja „zdał” to tylko te pary, które się naprawdę zdarzyły, np. (Ola, matematyka), (Ola, mikroekonomia), (Kuba, mikroekonomia). Ewa niczego nie zdała — nie ma jej w żadnej parze, ale dalej należy do zbioru $A$ .

P \subset A \times B

Relacja między A i B

czytamy: „P zawiera się w A razy B”

$P$ to zbiór wybranych par $(x, y)$ , w których $x \in A$ , $y \in B$ .

Jak zapamiętać: relacja to „wycinek” tabeli wszystkich par.

x P y

Bycie w relacji

czytamy: „x jest w relacji P z y”

Para $(x, y)$ należy do $P$ . To samo co $(x, y) \in P$ .

Jak zapamiętać: literka relacji stoi między elementami jak spójnik.

D (P)

Dziedzina

czytamy: „dziedzina relacji P”

Zbiór, z którego bierzemy pierwszy element pary — przy $P \subset A \times B$ to $A$ .

Jak zapamiętać: D jak „dom” — tu zaczyna się każda para.

D^{- 1} (P)

Przeciwdziedzina

czytamy: „przeciwdziedzina relacji P”

Zbiór, z którego bierzemy drugi element pary — przy $P \subset A \times B$ to $B$ .

Jak zapamiętać: „przeciw” = po drugiej stronie pary.

Często obie strony pary pochodzą z jednego zbioru: $P \subset A \times A$ , czyli $P \subset A^2$ . Mówimy wtedy o relacji w zbiorze $A$ — np. „obserwuje na Instagramie” wśród studentów z Twojej grupy albo „jest mniejsza lub równa” wśród liczb. Tylko dla takich relacji badamy własności (zwrotność, symetryczność…) i porządki.

Sprawdź się

Relacja $P \subset A \times B$ , gdzie $A = {1, 2}$ , $B = {5, 6, 7}$ . Ile najwięcej par może mieć $P$ ?

Pary, macierz, graf — trzy zapisy relacji

Gdy zbiory są skończone, relację można zapisać na trzy sposoby: wypisać pary, zapisać macierz albo narysować graf. Wszystkie trzy niosą tę samą informację. Wybierasz ten zapis, o który prosi polecenie.

Jak czytać macierz — jak w statkach

Macierz relacji to tabelka z zerami i jedynkami. Każda kratka odpowiada jednej parze $(x, y)$ :

$x$ odczytujesz z lewej strony — to etykieta wiersza;
$y$ odczytujesz z góry — to etykieta kolumny.

Działa to jak w grze w statki: pole „B4” to kolumna B i wiersz 4. Tutaj mówimy „kratka $(1, 3)$ ” — wiersz 1, kolumna 3. Cyfra w kratce mówi, czy para należy do relacji: 1 — należy, 0 — nie należy.

P

1

2

3

1

2

011001

Zakreślona kratka to $(1, 3)$ : wiersz 1, kolumna 3. Jest w niej 1, więc para $(1, 3)$ należy do relacji $P$ . Kratka obok, $(1, 2)$ , też ma 1. A kratka $(2, 1)$ — w drugim wierszu, w pierwszej kolumnie — ma 0, więc pary $(2, 1)$ w relacji nie ma.

Zadanie · krok po kroku

Zapisz relacje P i Q w postaci macierzy

Zad. 3, str. 49–50, c) — część 1

$A = \{-1, 0, 1, 2\}$ , $B = \{1, 2, 3\}$ , $C = \{x \in \mathbb{N} : x < 2\}$ . Relacje: $P \subset A \times B$ , $xPy \Leftrightarrow xy \leq 2$ oraz $Q \subset B \times C$ , $xQy \Leftrightarrow xy \geq 1$ .

Plan — co zrobimy i po co

Wypisujemy elementy wszystkich zbiorów. Bez tego nie wiemy, ile wierszy i kolumn ma macierz.
Wypełniamy macierz $P$ kratka po kratce: dla każdej pary sprawdzamy warunek $xy \leq 2$ .
Z jedynek odczytujemy pary i rysujemy graf — to ta sama relacja w innym zapisie.
Tak samo budujemy macierz $Q$ .

Innej drogi nie ma: macierz relacji zawsze powstaje przez sprawdzenie warunku dla każdej pary.

Wypisz elementy zbiorów
$A$ i $B$ są już wypisane. $C = \{0, 1\}$ , bo liczby naturalne mniejsze od 2 to 0 i 1.
Z tego wynika rozmiar macierzy: $P$ ma 4 wiersze (bo $A$ ma 4 elementy) i 3 kolumny (bo $B$ ma 3). Razem 12 kratek, czyli 12 par do sprawdzenia.
Bo tak — umowa
Na zajęciach $0 \in \mathbb{N}$ . Bez zera zbiór $C$ miałby jeden element, a macierz $Q$ — jedną kolumnę zamiast dwóch.

Wypełnij macierz P kratka po kratce

W każdej kratce odpowiadamy na to samo pytanie: czy para $(x, y)$ spełnia warunek $xy \leq 2$ ?

Jak to zrobić dla jednej kratki:

Odczytaj $x$ — liczbę z lewej strony wiersza — i $y$ — liczbę nad kolumną.
Wstaw je do warunku. Zapis $xy$ znaczy $x$ razy $y$ .
Pomnóż.
Porównaj wynik z 2. Wynik mniejszy albo równy 2 → wpisz 1. Wynik większy od 2 → wpisz 0.

Przykład — kratka w wierszu 1 i kolumnie 3. Tu $x = 1$ i $y = 3$ . Mnożymy: $1 \cdot 3 = 3$ . Czy $3 \leq 2$ ? Nie, 3 jest większe od 2. Wpisujemy 0.

Bo tak — umowa

Dwie litery obok siebie bez znaku między nimi oznaczają mnożenie: $xy = x \cdot y$ . Tak samo w liceum $2a$ znaczyło $2 \cdot a$ .

Tak wygląda rachunek dla wszystkich 12 kratek:

$x \ y$	$y = 1$	$y = 2$	$y = 3$
$x = - 1$	$(- 1) \cdot 1 = - 1$ $- 1 \leq 2$ → 1	$(- 1) \cdot 2 = - 2$ $- 2 \leq 2$ → 1	$(- 1) \cdot 3 = - 3$ $- 3 \leq 2$ → 1
$x = 0$	$0 \cdot 1 = 0$ $0 \leq 2$ → 1	$0 \cdot 2 = 0$ $0 \leq 2$ → 1	$0 \cdot 3 = 0$ $0 \leq 2$ → 1
$x = 1$	$1 \cdot 1 = 1$ $1 \leq 2$ → 1	$1 \cdot 2 = 2$ $2 \leq 2$ → 1	$1 \cdot 3 = 3$ $3 > 2$ → 0
$x = 2$	$2 \cdot 1 = 2$ $2 \leq 2$ → 1	$2 \cdot 2 = 4$ $4 > 2$ → 0	$2 \cdot 3 = 6$ $6 > 2$ → 0

Jak czytać tę siatkę:

każda kratka to jedna para: $x$ z lewej, $y$ z góry. Górna linijka to mnożenie, dolna — porównanie z 2. Strzałka pokazuje cyfrę, która trafia do macierzy. Stuknij kratkę, a pod siatką zobaczysz jej rachunek opisany słowami.

Gotowa macierz $P$ to same cyfry ze strzałek:

P

1

2

3

- 1

0

1

2

111111110100

Dlaczego?

Idziemy wiersz po wierszu, żeby nie pominąć żadnej kratki. Kolejność nie zmienia wyniku — każda kratka to osobne pytanie.

Inny sposób

Możesz najpierw wypisać pary, które spełniają warunek, a potem wpisać jedynki w ich kratki i resztę uzupełnić zerami. Przy małych zbiorach to szybkie, ale łatwiej coś przeoczyć.

Odczytaj pary i narysuj graf
Każda jedynka to jedna para: (liczba z lewej, liczba z góry).
$\begin{aligned} P = \{&(-1, 1), (-1, 2), (-1, 3), \\ &(0, 1), (0, 2), (0, 3), \\ &(1, 1), (1, 2), (2, 1)\} \end{aligned}$
Jak czytać ten graf:
po lewej elementy $A$ , po prawej elementy $B$ . Strzałka $x \to y$ znaczy $xPy$ — jedna strzałka na każdą jedynkę z macierzy. Z $-1$ i z $0$ wychodzą strzałki do wszystkich elementów $B$ , a z $2$ — tylko do 1.
Dlaczego?
Pary, macierz i graf to trzy zapisy tej samej relacji. Polecenie mówi, który z nich podać.
Tak samo zbuduj macierz Q
$Q \subset B \times C$ , więc wiersze to $1, 2, 3$ (elementy $B$ ), a kolumny to $0, 1$ (elementy $C$ ). Warunek: $xy \geq 1$ — iloczyn większy albo równy 1.
$x \ y$ $y = 0$ $y = 1$
$x = 1$ $1 \cdot 0 = 0$ $0 < 1$ → 0 $1 \cdot 1 = 1$ $1 \geq 1$ → 1
$x = 2$ $2 \cdot 0 = 0$ $0 < 1$ → 0 $2 \cdot 1 = 2$ $2 \geq 1$ → 1
$x = 3$ $3 \cdot 0 = 0$ $0 < 1$ → 0 $3 \cdot 1 = 3$ $3 \geq 1$ → 1
- Wiersz $x = 1$ , kolumna $y = 0$ . Wstawiamy do warunku $x y \geq 1$ : $1 \cdot 0 = 0$ , a $0 < 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
- Wiersz $x = 1$ , kolumna $y = 1$ . Wstawiamy do warunku $x y \geq 1$ : $1 \cdot 1 = 1$ , a $1 \geq 1$ . Warunek jest spełniony, więc wpisujemy 1 — para należy do relacji.
- Wiersz $x = 2$ , kolumna $y = 0$ . Wstawiamy do warunku $x y \geq 1$ : $2 \cdot 0 = 0$ , a $0 < 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
- Wiersz $x = 2$ , kolumna $y = 1$ . Wstawiamy do warunku $x y \geq 1$ : $2 \cdot 1 = 2$ , a $2 \geq 1$ . Warunek jest spełniony, więc wpisujemy 1 — para należy do relacji.
- Wiersz $x = 3$ , kolumna $y = 0$ . Wstawiamy do warunku $x y \geq 1$ : $3 \cdot 0 = 0$ , a $0 < 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
- Wiersz $x = 3$ , kolumna $y = 1$ . Wstawiamy do warunku $x y \geq 1$ : $3 \cdot 1 = 3$ , a $3 \geq 1$ . Warunek jest spełniony, więc wpisujemy 1 — para należy do relacji.
Jak czytać tę siatkę:
tak samo jak wyżej: górna linijka to mnożenie, dolna — porównanie z 1.
$Q$
$0$ $1$
$1$ $2$ $3$
010101
Dlaczego?
W kolumnie $0$ są same zera, bo każda liczba razy 0 daje 0, a $0 < 1$ . W kolumnie $1$ iloczyn to po prostu $x$ , a każdy element $B$ jest co najmniej równy 1.

$x \ y$	$y = 0$	$y = 1$
$x = 1$	$1 \cdot 0 = 0$ $0 < 1$ → 0	$1 \cdot 1 = 1$ $1 \geq 1$ → 1
$x = 2$	$2 \cdot 0 = 0$ $0 < 1$ → 0	$2 \cdot 1 = 2$ $2 \geq 1$ → 1
$x = 3$	$3 \cdot 0 = 0$ $0 < 1$ → 0	$3 \cdot 1 = 3$ $3 \geq 1$ → 1

Graf relacji w jednym zbiorze rysujemy inaczej: jedno kółko na każdy element. Gdy element jest w relacji sam ze sobą ( $xPx$ ), rysujemy pętelkę. Przykład: relacja „ $x$ jest dzielnikiem $y$ ” w zbiorze $\{1, 2, 3, 6\}$ .

R

1

2

3

6

1

2

3

6

1111010100110001

Jak czytać ten graf:

pętelka przy każdym elemencie, bo każda liczba jest swoim dzielnikiem — na macierzy to jedynki na przekątnej (fioletowe tło). Strzałka $1 \to 6$ znaczy „1 dzieli 6”. Między 2 a 3 nie ma strzałki, bo żadna z tych liczb nie dzieli drugiej.

Działania na relacjach

Relacja to zbiór par. Dlatego na relacjach działa wszystko, co znasz ze zbiorów: suma, część wspólna, różnica i dopełnienie. Najłatwiej to zobaczyć na kołach.

Mały przykład: $A = \{1, 2\}$ , $B = \{1, 2, 3\}$ . Wszystkich par w $A \times B$ jest 6. Relacja $P$ : $x < y$ . Relacja $R$ : $x + y \geq 4$ .

P

1

2

3

1

2

011001

R

1

2

3

1

2

001011

P \cup R

1

2

3

1

2

011011

P \cap R

1

2

3

1

2

001001

P ∖ R

1

2

3

1

2

010000

R ∖ P

1

2

3

1

2

000010

P^{'}

1

2

3

1

2

100110

Jak czytać ten rysunek:

prostokąt to wszystkie 6 par z $A \times B$ . Niebieskie koło to pary relacji $P$ , różowe — pary relacji $R$ . Para w części wspólnej kół należy do obu relacji. Pod kołami te same relacje jako macierze. Kliknij działanie: na kołach podświetli się obszar wyniku, a w macierzy wyniku — jej jedynki. Kliknij parę na kołach albo kratkę w macierzy: ta sama kratka zakreśli się w każdej macierzy, a pod spodem zobaczysz, ile wynosi w każdym działaniu.

Na macierzach liczysz kratka po kratce: bierzesz kratkę w tym samym miejscu w obu macierzach i stosujesz regułę z tabeli.

Działanie	Kratka wyniku to 1, gdy…
$P \cup R$ (suma)	w $P$ lub w $R$ jest 1
$P \cap R$ (część wspólna)	w $P$ i w $R$ jest 1
$P \setminus R$ (różnica)	w $P$ jest 1, a w $R$ jest 0
$P'$ (dopełnienie)	w $P$ jest 0 — każde 0 zamieniasz na 1, a każde 1 na 0

To samo na większych macierzach z zadania z zajęć: $P$ to $xy \leq 2$ , a druga relacja $R$ na tych samych zbiorach to $x + y \geq 3$ .

P

1

2

3

- 1

0

1

2

111111110100

R

1

2

3

- 1

0

1

2

000001011111

P \cup R

1

2

3

- 1

0

1

2

111111111111

P \cap R

1

2

3

- 1

0

1

2

000001010100

P ∖ R

1

2

3

- 1

0

1

2

111110100000

R ∖ P

1

2

3

- 1

0

1

2

000000001011

P^{'}

1

2

3

- 1

0

1

2

000000001011

Para $(- 1, 1)$ — wiersz $- 1$ , kolumna $1$ (zakreślona w każdej macierzy). W $P$ jest 1, w $R$ jest 0.
$P \cup R$ : 1 — wystarczy jedna jedynka
$P \cap R$ : 0 — potrzebne są dwie jedynki
$P ∖ R$ : 1 — jest w $P$ , nie ma w $R$
$R ∖ P$ : 0 — nie ma jej w $R$
$P^{'}$ : 0 — w $P$ jest 1, więc w dopełnieniu 0
Para $(- 1, 2)$ — wiersz $- 1$ , kolumna $2$ (zakreślona w każdej macierzy). W $P$ jest 1, w $R$ jest 0.
$P \cup R$ : 1 — wystarczy jedna jedynka
$P \cap R$ : 0 — potrzebne są dwie jedynki
$P ∖ R$ : 1 — jest w $P$ , nie ma w $R$
$R ∖ P$ : 0 — nie ma jej w $R$
$P^{'}$ : 0 — w $P$ jest 1, więc w dopełnieniu 0
Para $(- 1, 3)$ — wiersz $- 1$ , kolumna $3$ (zakreślona w każdej macierzy). W $P$ jest 1, w $R$ jest 0.
$P \cup R$ : 1 — wystarczy jedna jedynka
$P \cap R$ : 0 — potrzebne są dwie jedynki
$P ∖ R$ : 1 — jest w $P$ , nie ma w $R$
$R ∖ P$ : 0 — nie ma jej w $R$
$P^{'}$ : 0 — w $P$ jest 1, więc w dopełnieniu 0
Para $(0, 1)$ — wiersz $0$ , kolumna $1$ (zakreślona w każdej macierzy). W $P$ jest 1, w $R$ jest 0.
$P \cup R$ : 1 — wystarczy jedna jedynka
$P \cap R$ : 0 — potrzebne są dwie jedynki
$P ∖ R$ : 1 — jest w $P$ , nie ma w $R$
$R ∖ P$ : 0 — nie ma jej w $R$
$P^{'}$ : 0 — w $P$ jest 1, więc w dopełnieniu 0
Para $(0, 2)$ — wiersz $0$ , kolumna $2$ (zakreślona w każdej macierzy). W $P$ jest 1, w $R$ jest 0.
$P \cup R$ : 1 — wystarczy jedna jedynka
$P \cap R$ : 0 — potrzebne są dwie jedynki
$P ∖ R$ : 1 — jest w $P$ , nie ma w $R$
$R ∖ P$ : 0 — nie ma jej w $R$
$P^{'}$ : 0 — w $P$ jest 1, więc w dopełnieniu 0
Para $(0, 3)$ — wiersz $0$ , kolumna $3$ (zakreślona w każdej macierzy). W $P$ jest 1, w $R$ jest 1.
$P \cup R$ : 1 — jedynka w obu
$P \cap R$ : 1 — jedynka w obu
$P ∖ R$ : 0 — jest też w $R$
$R ∖ P$ : 0 — jest też w $P$
$P^{'}$ : 0 — w $P$ jest 1, więc w dopełnieniu 0
Para $(1, 1)$ — wiersz $1$ , kolumna $1$ (zakreślona w każdej macierzy). W $P$ jest 1, w $R$ jest 0.
$P \cup R$ : 1 — wystarczy jedna jedynka
$P \cap R$ : 0 — potrzebne są dwie jedynki
$P ∖ R$ : 1 — jest w $P$ , nie ma w $R$
$R ∖ P$ : 0 — nie ma jej w $R$
$P^{'}$ : 0 — w $P$ jest 1, więc w dopełnieniu 0
Para $(1, 2)$ — wiersz $1$ , kolumna $2$ (zakreślona w każdej macierzy). W $P$ jest 1, w $R$ jest 1.
$P \cup R$ : 1 — jedynka w obu
$P \cap R$ : 1 — jedynka w obu
$P ∖ R$ : 0 — jest też w $R$
$R ∖ P$ : 0 — jest też w $P$
$P^{'}$ : 0 — w $P$ jest 1, więc w dopełnieniu 0
Para $(1, 3)$ — wiersz $1$ , kolumna $3$ (zakreślona w każdej macierzy). W $P$ jest 0, w $R$ jest 1.
$P \cup R$ : 1 — wystarczy jedna jedynka
$P \cap R$ : 0 — potrzebne są dwie jedynki
$P ∖ R$ : 0 — nie ma jej w $P$
$R ∖ P$ : 1 — jest w $R$ , nie ma w $P$
$P^{'}$ : 1 — w $P$ jest 0, więc w dopełnieniu 1
Para $(2, 1)$ — wiersz $2$ , kolumna $1$ (zakreślona w każdej macierzy). W $P$ jest 1, w $R$ jest 1.
$P \cup R$ : 1 — jedynka w obu
$P \cap R$ : 1 — jedynka w obu
$P ∖ R$ : 0 — jest też w $R$
$R ∖ P$ : 0 — jest też w $P$
$P^{'}$ : 0 — w $P$ jest 1, więc w dopełnieniu 0
Para $(2, 2)$ — wiersz $2$ , kolumna $2$ (zakreślona w każdej macierzy). W $P$ jest 0, w $R$ jest 1.
$P \cup R$ : 1 — wystarczy jedna jedynka
$P \cap R$ : 0 — potrzebne są dwie jedynki
$P ∖ R$ : 0 — nie ma jej w $P$
$R ∖ P$ : 1 — jest w $R$ , nie ma w $P$
$P^{'}$ : 1 — w $P$ jest 0, więc w dopełnieniu 1
Para $(2, 3)$ — wiersz $2$ , kolumna $3$ (zakreślona w każdej macierzy). W $P$ jest 0, w $R$ jest 1.
$P \cup R$ : 1 — wystarczy jedna jedynka
$P \cap R$ : 0 — potrzebne są dwie jedynki
$P ∖ R$ : 0 — nie ma jej w $P$
$R ∖ P$ : 1 — jest w $R$ , nie ma w $P$
$P^{'}$ : 1 — w $P$ jest 0, więc w dopełnieniu 1

Jak czytać ten rysunek:

wszystkie macierze mają te same wiersze ( $A$ ) i kolumny ( $B$ ). Kliknij dowolną kratkę, np. w wierszu 1 i kolumnie 2: zakreśli się ta sama kratka we wszystkich macierzach, a pod spodem zobaczysz, skąd wzięła się każda wartość.

Relacja odwrotna

P^{'}

Dopełnienie relacji

czytamy: „dopełnienie P (P prim)”

Wszystkie pary z $A \times B$ , których nie ma w $P$ . Na macierzy: 0 ↔ 1.

Jak zapamiętać: jak negacja w logice — zmienia każdą cyfrę.

P^{- 1}

Relacja odwrotna

czytamy: „P do minus pierwszej”

Te same pary zapisane w drugą stronę: $(y, x)$ zamiast $(x, y)$ . $P^{- 1} \subset B \times A$ .

Jak zapamiętać: para $(0, 3)$ staje się parą $(3, 0)$ .

Relacja odwrotna $P^{-1}$ ma te same pary co $P$ , tylko z zamienioną kolejnością: para $(0, 3)$ staje się parą $(3, 0)$ .

Co to zmienia w macierzy? Pierwszy element pary wskazuje wiersz, a drugi — kolumnę. Skoro elementy w parze zamieniają się miejscami, to wiersze zamieniają się z kolumnami. Cyfry zostają te same.

Jak to zrobić:

Narysuj pustą macierz $P^{-1}$ . Jej wiersze to elementy $B$ , a kolumny — elementy $A$ (odwrotnie niż w $P$ ).
Weź pierwszy wiersz $P$ i wpisz go jako pierwszą kolumnę $P^{-1}$ , z góry na dół.
Powtórz to dla każdego wiersza.

P \subset A \times B

1

2

3

- 1

0

1

2

111111110100

P^{- 1} \subset B \times A

- 1

0

1

2

1

2

3

············

Komórka w wierszu $- 1$ i kolumnie $1$ macierzy $P$ (para $(- 1, 1)$ , wartość 1) trafia do wiersza $1$ i kolumny $- 1$ macierzy $P^{- 1}$ — tam jest para $(1, - 1)$ z tą samą wartością.
Komórka w wierszu $- 1$ i kolumnie $2$ macierzy $P$ (para $(- 1, 2)$ , wartość 1) trafia do wiersza $2$ i kolumny $- 1$ macierzy $P^{- 1}$ — tam jest para $(2, - 1)$ z tą samą wartością.
Komórka w wierszu $- 1$ i kolumnie $3$ macierzy $P$ (para $(- 1, 3)$ , wartość 1) trafia do wiersza $3$ i kolumny $- 1$ macierzy $P^{- 1}$ — tam jest para $(3, - 1)$ z tą samą wartością.
Komórka w wierszu $0$ i kolumnie $1$ macierzy $P$ (para $(0, 1)$ , wartość 1) trafia do wiersza $1$ i kolumny $0$ macierzy $P^{- 1}$ — tam jest para $(1, 0)$ z tą samą wartością.
Komórka w wierszu $0$ i kolumnie $2$ macierzy $P$ (para $(0, 2)$ , wartość 1) trafia do wiersza $2$ i kolumny $0$ macierzy $P^{- 1}$ — tam jest para $(2, 0)$ z tą samą wartością.
Komórka w wierszu $0$ i kolumnie $3$ macierzy $P$ (para $(0, 3)$ , wartość 1) trafia do wiersza $3$ i kolumny $0$ macierzy $P^{- 1}$ — tam jest para $(3, 0)$ z tą samą wartością.
Komórka w wierszu $1$ i kolumnie $1$ macierzy $P$ (para $(1, 1)$ , wartość 1) trafia do wiersza $1$ i kolumny $1$ macierzy $P^{- 1}$ — tam jest para $(1, 1)$ z tą samą wartością.
Komórka w wierszu $1$ i kolumnie $2$ macierzy $P$ (para $(1, 2)$ , wartość 1) trafia do wiersza $2$ i kolumny $1$ macierzy $P^{- 1}$ — tam jest para $(2, 1)$ z tą samą wartością.
Komórka w wierszu $1$ i kolumnie $3$ macierzy $P$ (para $(1, 3)$ , wartość 0) trafia do wiersza $3$ i kolumny $1$ macierzy $P^{- 1}$ — tam jest para $(3, 1)$ z tą samą wartością.
Komórka w wierszu $2$ i kolumnie $1$ macierzy $P$ (para $(2, 1)$ , wartość 1) trafia do wiersza $1$ i kolumny $2$ macierzy $P^{- 1}$ — tam jest para $(1, 2)$ z tą samą wartością.
Komórka w wierszu $2$ i kolumnie $2$ macierzy $P$ (para $(2, 2)$ , wartość 0) trafia do wiersza $2$ i kolumny $2$ macierzy $P^{- 1}$ — tam jest para $(2, 2)$ z tą samą wartością.
Komórka w wierszu $2$ i kolumnie $3$ macierzy $P$ (para $(2, 3)$ , wartość 0) trafia do wiersza $3$ i kolumny $2$ macierzy $P^{- 1}$ — tam jest para $(3, 2)$ z tą samą wartością.

Jak czytać ten rysunek:

każdy wiersz lewej macierzy ma swój kolor. Ten sam kolor ma kolumna prawej macierzy, do której ten wiersz trafia. Klikaj „Przepisz wiersz” i patrz, jak wiersz staje się kolumną. Stuknij kratkę lewej macierzy, a zobaczysz, gdzie jest w prawej.

Sprawdź się

$P \subset A \times B$ ma macierz 4 × 3 (4 wiersze, 3 kolumny). Jaki rozmiar ma macierz $P^{- 1}$ ?

Złożenie relacji

Złożenie to przejście w dwóch krokach: najpierw relacją $P$ z $x$ do $y$ , potem relacją $Q$ z $y$ do $z$ . Skojarzenie na start: lot z przesiadką — liczy się tylko, czy z $x$ da się dolecieć do $z$ .

x (Q \circ P) z \Leftrightarrow \exists_{y} x P y \land y Q z

Czytamy: $x$ jest w relacji $Q$ po $P$ z $z$ wtedy i tylko wtedy, gdy istnieje takie $y$ , że $x P y$ i $y Q z$

$Q \circ P$: złożenie: najpierw relacja $P$ , potem $Q$ ; czytamy „ $Q$ po $P$ ”
$\exists_{y}$: istnieje element pośredni $y$ — wystarczy jeden
$x P y \land y Q z$: z $x$ do $y$ prowadzi $P$ , a z $y$ do $z$ prowadzi $Q$

Kiedy złożenie da się wykonać? Drugi krok musi startować tam, gdzie skończył się pierwszy. Jeśli $P \subset A \times B$ i $Q \subset B \times C$ , to $P$ kończy się w $B$ i $Q$ zaczyna w $B$ — złożenie $Q \circ P$ jest wykonalne. Wynik prowadzi od pierwszego zbioru do ostatniego: $Q \circ P \subset A \times C$ .

\begin{gathered} A \xrightarrow{\ P\ } B \xrightarrow{\ Q\ } C \\ Q \circ P \subset A \times C \end{gathered}

Jak policzyć macierz złożenia

Przykład na liczbach: $A = \{1, 2\}$ , $B = \{1, 2, 3\}$ , $C = \{1, 2, 3\}$ . Relacja $P \subset A \times B$ : $x < y$ . Relacja $Q \subset B \times C$ : $y + z = 4$ .

P

1

2

3

1

2

011001

Q

1

2

3

1

2

3

001010100

Macierz $Q \circ P$ ma wiersze z $A$ (start) i kolumny z $C$ (koniec). Każdą kratkę $(x, z)$ liczysz tak samo:

Z macierzy $P$ weź wiersz $x$ (złoty w przykładzie: wiersz 1).
Z macierzy $Q$ weź kolumnę $z$ (złota: kolumna 1).
Zapisz je jeden pod drugim — pozycja po pozycji. Pozycje to elementy $B$ .
Jeśli na którejś pozycji obie mają 1 → wpisz 1. Jeśli nigdzie → wpisz 0.

Przykład — kratka $(1, 1)$ :

pozycja $y$	$1$	$2$	$3$
wiersz $1$ w $P$	0	1	1
kolumna $1$ w $Q$	0	0	1

Na pozycji

y = 3

obie mają 1:

1 P 3

3 Q 1

. Da się przejść z

1

1

przez

3

, więc w komórce

(1, 1)

wpisujemy 1.

Całe złożenie — kliknij dowolną kratkę wyniku, a zobaczysz jej rachunek:

P

1

2

3

1

2

011001

Q

1

2

3

1

2

3

001010100

Q \circ P

1

2

3

1

2

······

Komórka $(1, 1)$ :
pozycja $y$ $1$ $2$ $3$
wiersz $1$ w $P$ 0 1 1
kolumna $1$ w $Q$ 0 0 1
Na pozycji $y = 3$ obie mają 1: $1 P 3$ i $3 Q 1$ . Da się przejść z $1$ do $1$ przez $3$ , więc w komórce $(1, 1)$ wpisujemy 1.
Komórka $(1, 2)$ :
pozycja $y$ $1$ $2$ $3$
wiersz $1$ w $P$ 0 1 1
kolumna $2$ w $Q$ 0 1 0
Na pozycji $y = 2$ obie mają 1: $1 P 2$ i $2 Q 2$ . Da się przejść z $1$ do $2$ przez $2$ , więc w komórce $(1, 2)$ wpisujemy 1.
Komórka $(1, 3)$ :
pozycja $y$ $1$ $2$ $3$
wiersz $1$ w $P$ 0 1 1
kolumna $3$ w $Q$ 1 0 0
Nie ma pozycji, na której obie mają 1 — nie da się przejść z $1$ do $3$ przez żaden element. W komórce $(1, 3)$ wpisujemy 0.
Komórka $(2, 1)$ :
pozycja $y$ $1$ $2$ $3$
wiersz $2$ w $P$ 0 0 1
kolumna $1$ w $Q$ 0 0 1
Na pozycji $y = 3$ obie mają 1: $2 P 3$ i $3 Q 1$ . Da się przejść z $2$ do $1$ przez $3$ , więc w komórce $(2, 1)$ wpisujemy 1.
Komórka $(2, 2)$ :
pozycja $y$ $1$ $2$ $3$
wiersz $2$ w $P$ 0 0 1
kolumna $2$ w $Q$ 0 1 0
Nie ma pozycji, na której obie mają 1 — nie da się przejść z $2$ do $2$ przez żaden element. W komórce $(2, 2)$ wpisujemy 0.
Komórka $(2, 3)$ :
pozycja $y$ $1$ $2$ $3$
wiersz $2$ w $P$ 0 0 1
kolumna $3$ w $Q$ 1 0 0
Nie ma pozycji, na której obie mają 1 — nie da się przejść z $2$ do $3$ przez żaden element. W komórce $(2, 3)$ wpisujemy 0.

pozycja $y$	$1$	$2$	$3$
wiersz $2$ w $P$	0	0	1
kolumna $1$ w $Q$	0	0	1

pozycja $y$	$1$	$2$	$3$
wiersz $2$ w $P$	0	0	1
kolumna $2$ w $Q$	0	1	0

pozycja $y$	$1$	$2$	$3$
wiersz $2$ w $P$	0	0	1
kolumna $3$ w $Q$	1	0	0

Jak czytać ten rysunek:

lewa macierz to $P$ , środkowa to $Q$ , prawa to złożenie $Q \circ P$ (na start ukryte). Po kliknięciu kratki wyniku na złoto podświetlą się wiersz w $P$ i kolumna w $Q$ , a na zielono — pozycje, na których obie mają 1.

Zadanie · krok po kroku

Które złożenia są wykonalne? Wyznacz je

Zad. 3, str. 49–50, c) — część 2

$P \subset A \times B$ ( $xy \leq 2$ ) i $Q \subset B \times C$ ( $xy \geq 1$ ) z poprzedniego zadania: $A = \{-1, 0, 1, 2\}$ , $B = \{1, 2, 3\}$ , $C = \{0, 1\}$ .

Plan — co zrobimy i po co

Przy każdym z czterech złożeń sprawdzamy, czy „środkowe” zbiory się zgadzają. Liczyć macierz ma sens tylko dla złożeń wykonalnych.
Dla jedynego wykonalnego złożenia liczymy macierz kratka po kratce: wiersz z pierwszej relacji pod kolumną z drugiej.

Polecenie każe sprawdzić wszystkie cztery złożenia — także te, które nie wyjdą. Za stwierdzenie „niewykonalne” z uzasadnieniem też dostajesz punkty.

P ∘ Q — najpierw Q, potem P
$Q \subset B \times C$ kończy się w $C$ , a $P \subset A \times B$ zaczyna w $A$ . $C \neq A$ , więc złożenie $P \circ Q$ jest niewykonalne.
Dlaczego?
Po relacji $Q$ jesteśmy w zbiorze $C$ , a relacja $P$ startuje ze zbioru $A$ . Nie ma elementu, przez który dałoby się przejść.
Q ∘ P — najpierw P, potem Q
$P$ kończy się w $B$ , $Q$ zaczyna w $B$ — zbiory się zgadzają. $Q \circ P$ jest wykonalne, a wynik leży w $A \times C$ : 4 wiersze ( $A$ ) i 2 kolumny ( $C$ ).
Policz macierz Q ∘ P
Dla każdej kratki $(x, z)$ : wiersz $x$ macierzy $P$ pod kolumną $z$ macierzy $Q$ . Przykład — kratka $(-1, 0)$ :
pozycja $y$ $1$ $2$ $3$
wiersz $- 1$ w $P$ 1 1 1
kolumna $0$ w $Q$ 0 0 0
Nie ma pozycji, na której obie mają 1 — nie da się przejść z $- 1$ do $0$ przez żaden element. W komórce $(- 1, 0)$ wpisujemy 0.
Tak samo liczysz pozostałe kratki:
$P$
$1$ $2$ $3$
$- 1$ $0$ $1$ $2$
111111110100
$Q$
$0$ $1$
$1$ $2$ $3$
010101
$Q \circ P$
$0$ $1$
$- 1$ $0$ $1$ $2$
········
Kliknij komórkę macierzy $Q \circ P$ , żeby ją odkryć i zobaczyć, skąd się wzięła.
- Komórka $(- 1, 0)$ :
  pozycja $y$ $1$ $2$ $3$
  wiersz $- 1$ w $P$ 1 1 1
  kolumna $0$ w $Q$ 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $- 1$ do $0$ przez żaden element. W komórce $(- 1, 0)$ wpisujemy 0.
- Komórka $(- 1, 1)$ :
  pozycja $y$ $1$ $2$ $3$
  wiersz $- 1$ w $P$ 1 1 1
  kolumna $1$ w $Q$ 1 1 1
  Na pozycji $y = 1$ obie mają 1: $- 1 P 1$ i $1 Q 1$ . Da się przejść z $- 1$ do $1$ przez $1$ , więc w komórce $(- 1, 1)$ wpisujemy 1.
- Komórka $(0, 0)$ :
  pozycja $y$ $1$ $2$ $3$
  wiersz $0$ w $P$ 1 1 1
  kolumna $0$ w $Q$ 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $0$ do $0$ przez żaden element. W komórce $(0, 0)$ wpisujemy 0.
- Komórka $(0, 1)$ :
  pozycja $y$ $1$ $2$ $3$
  wiersz $0$ w $P$ 1 1 1
  kolumna $1$ w $Q$ 1 1 1
  Na pozycji $y = 1$ obie mają 1: $0 P 1$ i $1 Q 1$ . Da się przejść z $0$ do $1$ przez $1$ , więc w komórce $(0, 1)$ wpisujemy 1.
- Komórka $(1, 0)$ :
  pozycja $y$ $1$ $2$ $3$
  wiersz $1$ w $P$ 1 1 0
  kolumna $0$ w $Q$ 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $1$ do $0$ przez żaden element. W komórce $(1, 0)$ wpisujemy 0.
- Komórka $(1, 1)$ :
  pozycja $y$ $1$ $2$ $3$
  wiersz $1$ w $P$ 1 1 0
  kolumna $1$ w $Q$ 1 1 1
  Na pozycji $y = 1$ obie mają 1: $1 P 1$ i $1 Q 1$ . Da się przejść z $1$ do $1$ przez $1$ , więc w komórce $(1, 1)$ wpisujemy 1.
- Komórka $(2, 0)$ :
  pozycja $y$ $1$ $2$ $3$
  wiersz $2$ w $P$ 1 0 0
  kolumna $0$ w $Q$ 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $2$ do $0$ przez żaden element. W komórce $(2, 0)$ wpisujemy 0.
- Komórka $(2, 1)$ :
  pozycja $y$ $1$ $2$ $3$
  wiersz $2$ w $P$ 1 0 0
  kolumna $1$ w $Q$ 1 1 1
  Na pozycji $y = 1$ obie mają 1: $2 P 1$ i $1 Q 1$ . Da się przejść z $2$ do $1$ przez $1$ , więc w komórce $(2, 1)$ wpisujemy 1.
Jak czytać ten rysunek:
kliknij kratki prawej macierzy po kolei. Kolumna 0 w $Q$ to same zera, więc w wyniku kolumna 0 to same zera. Kolumna 1 w $Q$ to same jedynki, a w każdym wierszu $P$ jest jakaś jedynka — więc kolumna 1 wyniku to same jedynki.
Dlaczego?
Do jedynki w kratce $(x, z)$ potrzebny jest element $y$ , dla którego $xPy$ i $yQz$ . Dla $z = 0$ takiego $y$ nie ma: $y \cdot 0 = 0 < 1$ , więc żaden $y$ nie jest w relacji $Q$ z zerem.
Inny sposób
Można liczyć na parach: dla każdego $x$ wypisz, do których $y$ prowadzi $P$ , a potem, do których $z$ prowadzi z nich $Q$ . Wynik jest ten sam. Macierze są wygodniejsze, gdy par jest dużo.
P ∘ P i Q ∘ Q
- $P \circ P$ : $P$ kończy się w $B$ , a zaczyna w $A$ . $B \neq A$ — niewykonalne.
- $Q \circ Q$ : $Q$ kończy się w $C$ , a zaczyna w $B$ . $C \neq B$ — niewykonalne.
Dlaczego?
Złożenie relacji z samą sobą ( $P \circ P$ , zapisywane też $P^2$ ) działa tylko wtedy, gdy relacja kończy się w tym samym zbiorze, w którym się zaczyna — czyli dla relacji w jednym zbiorze.

pozycja $y$	$1$	$2$	$3$
wiersz $- 1$ w $P$	1	1	1
kolumna $0$ w $Q$	0	0	0

pozycja $y$	$1$	$2$	$3$
wiersz $- 1$ w $P$	1	1	1
kolumna $0$ w $Q$	0	0	0

pozycja $y$	$1$	$2$	$3$
wiersz $- 1$ w $P$	1	1	1
kolumna $1$ w $Q$	1	1	1

pozycja $y$	$1$	$2$	$3$
wiersz $0$ w $P$	1	1	1
kolumna $0$ w $Q$	0	0	0

pozycja $y$	$1$	$2$	$3$
wiersz $0$ w $P$	1	1	1
kolumna $1$ w $Q$	1	1	1

pozycja $y$	$1$	$2$	$3$
wiersz $1$ w $P$	1	1	0
kolumna $0$ w $Q$	0	0	0

pozycja $y$	$1$	$2$	$3$
wiersz $1$ w $P$	1	1	0
kolumna $1$ w $Q$	1	1	1

pozycja $y$	$1$	$2$	$3$
wiersz $2$ w $P$	1	0	0
kolumna $0$ w $Q$	0	0	0

pozycja $y$	$1$	$2$	$3$
wiersz $2$ w $P$	1	0	0
kolumna $1$ w $Q$	1	1	1

Własności relacji

Własności badamy dla relacji w jednym zbiorze ( $R \subset A \times A$ ). Jej macierz jest kwadratowa, a wiersze i kolumny mają te same etykiety, w tej samej kolejności.

Przy każdej własności patrzysz na jedno z dwóch miejsc:

przekątna — kratki od lewego górnego do prawego dolnego rogu, czyli pary $(x, x)$ : element sam ze sobą;
lustrzane kratki — $(x, y)$ i $(y, x)$ . Leżą po dwóch stronach przekątnej, jakby przekątna była lustrem.

a

b

c

a

b

c

101100011

Fioletowe tło to przekątna. Złote kratki $(a, c)$ i $(c, a)$ to jedna para lustrzanych kratek, zakreślone $(a, b)$ i $(b, a)$ — druga.

Na zajęciach jest siedem własności. Przy każdej masz dwie małe macierze: gdy własność zachodzi (TAK) i gdy nie zachodzi (NIE). Zielone kratki to te, na które patrzysz, a różowe — kontrprzykład.

Zwrotna

każdy element jest w relacji z samym sobą

TAK

a

b

c

a

b

c

101010111

przekątna: same 1

NIE

a

b

c

a

b

c

100101001

na przekątnej jest 0 (przy

b

)

Z życia: „jest w tym samym wieku co” — każdy jest w swoim wieku

Antyzwrotna

żaden element nie jest w relacji z samym sobą

TAK

a

b

c

a

b

c

010001100

przekątna: same 0

NIE

a

b

c

a

b

c

010010100

na przekątnej jest 1 (przy

b

)

Z życia: „jest starszy niż” — nikt nie jest starszy od siebie

Symetryczna

jeśli $x$ jest w relacji z $y$ , to $y$ z $x$ też

TAK

a

b

c

a

b

c

110101010

lustrzane komórki równe: 1 i 1, 0 i 0

NIE

a

b

c

a

b

c

110001010

w lustrze 1 i 0

Z życia: „jest znajomym na Facebooku” — zawsze w obie strony

Asymetryczna

jeśli $x$ jest w relacji z $y$ , to $y$ z $x$ na pewno nie (i nikt sam ze sobą)

TAK

a

b

c

a

b

c

011001000

przekątna: same 0, przy każdej 1 w lustrze 0

NIE

a

b

c

a

b

c

010100000

dwie jedynki w lustrze

Z życia: „jest starszy niż”

Quasi-asymetryczna

jak asymetryczna, ale przekątna może być dowolna

TAK

a

b

c

a

b

c

111001001

przy każdej 1 w lustrze 0 (przekątnej nie sprawdzasz)

NIE

a

b

c

a

b

c

110110001

dwie jedynki w lustrze

Z życia: „ $\leq$ ” na liczbach

Spójna

każde dwa różne elementy są w relacji przynajmniej w jedną stronę

TAK

a

b

c

a

b

c

011001000

w każdej lustrzanej parze jest co najmniej jedna 1

NIE

a

b

c

a

b

c

110010001

dwa zera w lustrze (

a

c

)

Z życia: „ $\leq$ ” — każde dwie liczby da się porównać

Przechodnia

jeśli $x$ z $y$ i $y$ z $z$ , to $x$ z $z$

TAK

a

b

c

a

b

c

111011001

a \to b

b \to c

(zielone), więc musi być

a \to c

(złote) — jest

NIE

a

b

c

a

b

c

010001000

a \to b

b \to c

, ale w

(a, c)

jest 0

Z życia: „jest starszy niż” — starszy od starszego jest starszy

Przechodniość krok po kroku

Przechodniość znaczy: jeśli da się przejść z $x$ do $y$ , a potem z $y$ do $z$ , to musi się też dać przejść z $x$ do $z$ od razu. Każda droga „w dwóch krokach” musi mieć skrót „w jednym kroku”.

Na zajęciach sprawdza się to wzorem $R \circ R \subset R$ — czytamy: „złożenie $R$ z $R$ zawiera się w $R$ ”. W praktyce to trzy kroki:

Zbuduj pustą macierz $R \circ R$ — z tymi samymi wierszami i kolumnami co $R$ .
Wypełnij każdą kratkę $(x, z)$ tak jak przy złożeniu: wiersz $x$ macierzy $R$ pod kolumną $z$ tej samej macierzy $R$ . Wspólna jedynka → 1, brak → 0. Jedynka znaczy: z $x$ do $z$ da się dojść w dwóch krokach.
Porównaj $R \circ R$ z $R$ kratka po kratce. Szukasz kratki, w której $R \circ R$ $R \circ R$ ma 1, a $R$ $R$ ma 0.
- Jest choć jedna taka kratka → relacja nie jest przechodnia (w dwóch krokach się da, w jednym — nie).
- Nie ma żadnej → relacja jest przechodnia.

Cały ten proces zobaczysz w zadaniu niżej, w kroku 4.

Zadanie · krok po kroku

Zbadaj własności relacji xRy ⇔ |x − y| ≤ 1 w zbiorze {1, 2, 3, 4}

Plan — co zrobimy i po co

Budujemy macierz — bez niej własności nie widać.
Patrzymy na przekątną → zwrotność i antyzwrotność.
Patrzymy na lustrzane kratki → symetria, asymetria, quasi-asymetria, spójność.
Liczymy $R \circ R$ i porównujemy z $R$ → przechodniość.
Zbieramy wyniki. Przy każdej własności, która nie zachodzi, podajemy kontrprzykład.

Kolejność kroków 2–4 jest dowolna. Ta jest najwygodniejsza, bo idzie od rzeczy widocznych od razu do tej, którą trzeba policzyć.

Zbuduj macierz

Dla każdej kratki: $x$ z lewej, $y$ z góry. Liczysz różnicę $x - y$ , bierzesz jej wartość bezwzględną i sprawdzasz, czy wynik jest $\leq 1$ .

$x \ y$	$y = 1$	$y = 2$	$y = 3$	$y = 4$
$x = 1$	$∣1 - 1∣ = 0$ $0 \leq 1$ → 1	$∣1 - 2∣ = 1$ $1 \leq 1$ → 1	$∣1 - 3∣ = 2$ $2 > 1$ → 0	$∣1 - 4∣ = 3$ $3 > 1$ → 0
$x = 2$	$∣2 - 1∣ = 1$ $1 \leq 1$ → 1	$∣2 - 2∣ = 0$ $0 \leq 1$ → 1	$∣2 - 3∣ = 1$ $1 \leq 1$ → 1	$∣2 - 4∣ = 2$ $2 > 1$ → 0
$x = 3$	$∣3 - 1∣ = 2$ $2 > 1$ → 0	$∣3 - 2∣ = 1$ $1 \leq 1$ → 1	$∣3 - 3∣ = 0$ $0 \leq 1$ → 1	$∣3 - 4∣ = 1$ $1 \leq 1$ → 1
$x = 4$	$∣4 - 1∣ = 3$ $3 > 1$ → 0	$∣4 - 2∣ = 2$ $2 > 1$ → 0	$∣4 - 3∣ = 1$ $1 \leq 1$ → 1	$∣4 - 4∣ = 0$ $0 \leq 1$ → 1

Wiersz $x = 1$ , kolumna $y = 1$ . Wstawiamy do warunku $∣ x - y ∣ \leq 1$ : $∣1 - 1∣ = 0$ , a $0 \leq 1$ . Warunek jest spełniony, więc wpisujemy 1 — para należy do relacji.
Wiersz $x = 1$ , kolumna $y = 2$ . Wstawiamy do warunku $∣ x - y ∣ \leq 1$ : $∣1 - 2∣ = 1$ , a $1 \leq 1$ . Warunek jest spełniony, więc wpisujemy 1 — para należy do relacji.
Wiersz $x = 1$ , kolumna $y = 3$ . Wstawiamy do warunku $∣ x - y ∣ \leq 1$ : $∣1 - 3∣ = 2$ , a $2 > 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 1$ , kolumna $y = 4$ . Wstawiamy do warunku $∣ x - y ∣ \leq 1$ : $∣1 - 4∣ = 3$ , a $3 > 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 2$ , kolumna $y = 1$ . Wstawiamy do warunku $∣ x - y ∣ \leq 1$ : $∣2 - 1∣ = 1$ , a $1 \leq 1$ . Warunek jest spełniony, więc wpisujemy 1 — para należy do relacji.
Wiersz $x = 2$ , kolumna $y = 2$ . Wstawiamy do warunku $∣ x - y ∣ \leq 1$ : $∣2 - 2∣ = 0$ , a $0 \leq 1$ . Warunek jest spełniony, więc wpisujemy 1 — para należy do relacji.
Wiersz $x = 2$ , kolumna $y = 3$ . Wstawiamy do warunku $∣ x - y ∣ \leq 1$ : $∣2 - 3∣ = 1$ , a $1 \leq 1$ . Warunek jest spełniony, więc wpisujemy 1 — para należy do relacji.
Wiersz $x = 2$ , kolumna $y = 4$ . Wstawiamy do warunku $∣ x - y ∣ \leq 1$ : $∣2 - 4∣ = 2$ , a $2 > 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 3$ , kolumna $y = 1$ . Wstawiamy do warunku $∣ x - y ∣ \leq 1$ : $∣3 - 1∣ = 2$ , a $2 > 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 3$ , kolumna $y = 2$ . Wstawiamy do warunku $∣ x - y ∣ \leq 1$ : $∣3 - 2∣ = 1$ , a $1 \leq 1$ . Warunek jest spełniony, więc wpisujemy 1 — para należy do relacji.
Wiersz $x = 3$ , kolumna $y = 3$ . Wstawiamy do warunku $∣ x - y ∣ \leq 1$ : $∣3 - 3∣ = 0$ , a $0 \leq 1$ . Warunek jest spełniony, więc wpisujemy 1 — para należy do relacji.
Wiersz $x = 3$ , kolumna $y = 4$ . Wstawiamy do warunku $∣ x - y ∣ \leq 1$ : $∣3 - 4∣ = 1$ , a $1 \leq 1$ . Warunek jest spełniony, więc wpisujemy 1 — para należy do relacji.
Wiersz $x = 4$ , kolumna $y = 1$ . Wstawiamy do warunku $∣ x - y ∣ \leq 1$ : $∣4 - 1∣ = 3$ , a $3 > 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 4$ , kolumna $y = 2$ . Wstawiamy do warunku $∣ x - y ∣ \leq 1$ : $∣4 - 2∣ = 2$ , a $2 > 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 4$ , kolumna $y = 3$ . Wstawiamy do warunku $∣ x - y ∣ \leq 1$ : $∣4 - 3∣ = 1$ , a $1 \leq 1$ . Warunek jest spełniony, więc wpisujemy 1 — para należy do relacji.
Wiersz $x = 4$ , kolumna $y = 4$ . Wstawiamy do warunku $∣ x - y ∣ \leq 1$ : $∣4 - 4∣ = 0$ , a $0 \leq 1$ . Warunek jest spełniony, więc wpisujemy 1 — para należy do relacji.

Jak czytać tę siatkę:

górna linijka to odległość między $x$ a $y$ , dolna — porównanie z 1.

R

1

2

3

4

1

2

3

4

1100111001110011

Bo tak — umowa

$|x - y|$ to wartość bezwzględna: odległość między liczbami na osi. Zawsze wychodzi liczba nieujemna, np. $|1 - 3| = |-2| = 2$ . Warunek $|x - y| \leq 1$ znaczy więc: „liczby leżą obok siebie albo są równe”.

Przekątna: zwrotna, nie antyzwrotna
Na przekątnej są same 1, więc relacja jest zwrotna. Nie jest antyzwrotna, bo antyzwrotna wymaga samych 0.
Dlaczego?
Na przekątnej $x = y$ , więc $|x - x| = 0 \leq 1$ . Każda kratka przekątnej musi mieć 1.
Lustrzane kratki: symetryczna, nie quasi-asymetryczna, nie spójna
$R$
$1$ $2$ $3$ $4$
$1$ $2$ $3$ $4$
1100111001110011
- Każda kratka ma tę samą cyfrę co jej odbicie w lustrze, bo $|x - y| = |y - x|$ . Relacja jest symetryczna.
- Złote kratki $(1, 2)$ i $(2, 1)$ to dwie jedynki w lustrze. Dlatego relacja nie jest quasi-asymetryczna, a więc tym bardziej nie jest asymetryczna.
- Różowe kratki $(1, 3)$ i $(3, 1)$ to dwa zera w lustrze: 1 i 3 nie są w relacji w żadną stronę. Relacja nie jest spójna.
Dlaczego?
Do obalenia własności wystarczy jeden kontrprzykład — jedna para kratek. Do potwierdzenia trzeba sprawdzić wszystkie pary.
Przechodniość: policz R ∘ R i porównaj z R
Krok A. Liczymy $R \circ R$ kratka po kratce: wiersz $x$ macierzy $R$ pod kolumną $z$ tej samej macierzy. Przykład — kratka $(1, 3)$ :
pozycja $y$ $1$ $2$ $3$ $4$
wiersz $1$ w $R$ 1 1 0 0
kolumna $3$ w $R$ 0 1 1 1
Na pozycji $y = 2$ obie mają 1: $1 R 2$ i $2 R 3$ . Da się przejść z $1$ do $3$ przez $2$ , więc w komórce $(1, 3)$ wpisujemy 1.
Tak samo powstają pozostałe kratki — kliknij dowolną w prawej macierzy:
$R$
$1$ $2$ $3$ $4$
$1$ $2$ $3$ $4$
1100111001110011
$R$
$1$ $2$ $3$ $4$
$1$ $2$ $3$ $4$
1100111001110011
$R \circ R$
$1$ $2$ $3$ $4$
$1$ $2$ $3$ $4$
················
Kliknij komórkę macierzy $R \circ R$ , żeby ją odkryć i zobaczyć, skąd się wzięła.
- Komórka $(1, 1)$ :
  pozycja $y$ $1$ $2$ $3$ $4$
  wiersz $1$ w $R$ 1 1 0 0
  kolumna $1$ w $R$ 1 1 0 0
  Na pozycji $y = 1$ obie mają 1: $1 R 1$ i $1 R 1$ . Da się przejść z $1$ do $1$ przez $1$ , więc w komórce $(1, 1)$ wpisujemy 1.
- Komórka $(1, 2)$ :
  pozycja $y$ $1$ $2$ $3$ $4$
  wiersz $1$ w $R$ 1 1 0 0
  kolumna $2$ w $R$ 1 1 1 0
  Na pozycji $y = 1$ obie mają 1: $1 R 1$ i $1 R 2$ . Da się przejść z $1$ do $2$ przez $1$ , więc w komórce $(1, 2)$ wpisujemy 1.
- Komórka $(1, 3)$ :
  pozycja $y$ $1$ $2$ $3$ $4$
  wiersz $1$ w $R$ 1 1 0 0
  kolumna $3$ w $R$ 0 1 1 1
  Na pozycji $y = 2$ obie mają 1: $1 R 2$ i $2 R 3$ . Da się przejść z $1$ do $3$ przez $2$ , więc w komórce $(1, 3)$ wpisujemy 1.
- Komórka $(1, 4)$ :
  pozycja $y$ $1$ $2$ $3$ $4$
  wiersz $1$ w $R$ 1 1 0 0
  kolumna $4$ w $R$ 0 0 1 1
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $1$ do $4$ przez żaden element. W komórce $(1, 4)$ wpisujemy 0.
- Komórka $(2, 1)$ :
  pozycja $y$ $1$ $2$ $3$ $4$
  wiersz $2$ w $R$ 1 1 1 0
  kolumna $1$ w $R$ 1 1 0 0
  Na pozycji $y = 1$ obie mają 1: $2 R 1$ i $1 R 1$ . Da się przejść z $2$ do $1$ przez $1$ , więc w komórce $(2, 1)$ wpisujemy 1.
- Komórka $(2, 2)$ :
  pozycja $y$ $1$ $2$ $3$ $4$
  wiersz $2$ w $R$ 1 1 1 0
  kolumna $2$ w $R$ 1 1 1 0
  Na pozycji $y = 1$ obie mają 1: $2 R 1$ i $1 R 2$ . Da się przejść z $2$ do $2$ przez $1$ , więc w komórce $(2, 2)$ wpisujemy 1.
- Komórka $(2, 3)$ :
  pozycja $y$ $1$ $2$ $3$ $4$
  wiersz $2$ w $R$ 1 1 1 0
  kolumna $3$ w $R$ 0 1 1 1
  Na pozycji $y = 2$ obie mają 1: $2 R 2$ i $2 R 3$ . Da się przejść z $2$ do $3$ przez $2$ , więc w komórce $(2, 3)$ wpisujemy 1.
- Komórka $(2, 4)$ :
  pozycja $y$ $1$ $2$ $3$ $4$
  wiersz $2$ w $R$ 1 1 1 0
  kolumna $4$ w $R$ 0 0 1 1
  Na pozycji $y = 3$ obie mają 1: $2 R 3$ i $3 R 4$ . Da się przejść z $2$ do $4$ przez $3$ , więc w komórce $(2, 4)$ wpisujemy 1.
- Komórka $(3, 1)$ :
  pozycja $y$ $1$ $2$ $3$ $4$
  wiersz $3$ w $R$ 0 1 1 1
  kolumna $1$ w $R$ 1 1 0 0
  Na pozycji $y = 2$ obie mają 1: $3 R 2$ i $2 R 1$ . Da się przejść z $3$ do $1$ przez $2$ , więc w komórce $(3, 1)$ wpisujemy 1.
- Komórka $(3, 2)$ :
  pozycja $y$ $1$ $2$ $3$ $4$
  wiersz $3$ w $R$ 0 1 1 1
  kolumna $2$ w $R$ 1 1 1 0
  Na pozycji $y = 2$ obie mają 1: $3 R 2$ i $2 R 2$ . Da się przejść z $3$ do $2$ przez $2$ , więc w komórce $(3, 2)$ wpisujemy 1.
- Komórka $(3, 3)$ :
  pozycja $y$ $1$ $2$ $3$ $4$
  wiersz $3$ w $R$ 0 1 1 1
  kolumna $3$ w $R$ 0 1 1 1
  Na pozycji $y = 2$ obie mają 1: $3 R 2$ i $2 R 3$ . Da się przejść z $3$ do $3$ przez $2$ , więc w komórce $(3, 3)$ wpisujemy 1.
- Komórka $(3, 4)$ :
  pozycja $y$ $1$ $2$ $3$ $4$
  wiersz $3$ w $R$ 0 1 1 1
  kolumna $4$ w $R$ 0 0 1 1
  Na pozycji $y = 3$ obie mają 1: $3 R 3$ i $3 R 4$ . Da się przejść z $3$ do $4$ przez $3$ , więc w komórce $(3, 4)$ wpisujemy 1.
- Komórka $(4, 1)$ :
  pozycja $y$ $1$ $2$ $3$ $4$
  wiersz $4$ w $R$ 0 0 1 1
  kolumna $1$ w $R$ 1 1 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $4$ do $1$ przez żaden element. W komórce $(4, 1)$ wpisujemy 0.
- Komórka $(4, 2)$ :
  pozycja $y$ $1$ $2$ $3$ $4$
  wiersz $4$ w $R$ 0 0 1 1
  kolumna $2$ w $R$ 1 1 1 0
  Na pozycji $y = 3$ obie mają 1: $4 R 3$ i $3 R 2$ . Da się przejść z $4$ do $2$ przez $3$ , więc w komórce $(4, 2)$ wpisujemy 1.
- Komórka $(4, 3)$ :
  pozycja $y$ $1$ $2$ $3$ $4$
  wiersz $4$ w $R$ 0 0 1 1
  kolumna $3$ w $R$ 0 1 1 1
  Na pozycji $y = 3$ obie mają 1: $4 R 3$ i $3 R 3$ . Da się przejść z $4$ do $3$ przez $3$ , więc w komórce $(4, 3)$ wpisujemy 1.
- Komórka $(4, 4)$ :
  pozycja $y$ $1$ $2$ $3$ $4$
  wiersz $4$ w $R$ 0 0 1 1
  kolumna $4$ w $R$ 0 0 1 1
  Na pozycji $y = 3$ obie mają 1: $4 R 3$ i $3 R 4$ . Da się przejść z $4$ do $4$ przez $3$ , więc w komórce $(4, 4)$ wpisujemy 1.
Jak czytać ten rysunek:
złożenie relacji $R$ z samą sobą. Lewa i środkowa macierz to ta sama relacja $R$ . Prawa to wynik — jedynka znaczy „da się dojść w dwóch krokach”.
Krok B. Porównujemy $R \circ R$ z $R$ . Różowe kratki mają 1 w $R \circ R$ , a 0 w $R$ :
$R \circ R$
$1$ $2$ $3$ $4$
$1$ $2$ $3$ $4$
1110111111110111
$R$
$1$ $2$ $3$ $4$
$1$ $2$ $3$ $4$
1100111001110011
Takie kratki są (np. $(1, 3)$ ), więc relacja nie jest przechodnia.
Dlaczego?
Jedynka w $R \circ R$ w kratce $(1, 3)$ znaczy: z 1 do 3 da się dojść w dwóch krokach (przez 2). W $R$ ta kratka ma 0 — w jednym kroku się nie da. Po ludzku: 1 sąsiaduje z 2, 2 sąsiaduje z 3, ale 1 nie sąsiaduje z 3.
Inny sposób
Szybki test bez liczenia całego złożenia. Jeśli w wierszu $x$ jest 1 w kolumnie $y$ (czyli $xRy$ ), to każda jedynka z wiersza $y$ musi być też w wierszu $x$ .
$R$
$1$ $2$ $3$ $4$
$1$ $2$ $3$ $4$
1100111001110011
W kratce $(1, 2)$ jest 1 (zakreślona), więc wiersz 2 (zielony) musi się „mieścić” w wierszu 1 (złotym). Wiersz 2 ma jedynkę w kolumnie 3, a wiersz 1 — nie. Test oblany: relacja nie jest przechodnia.
Zbierz wynik
Relacja jest zwrotna i symetryczna. Nie jest antyzwrotna, asymetryczna, quasi-asymetryczna, spójna ani przechodnia.
$R$
$1$ $2$ $3$ $4$
$1$ $2$ $3$ $4$
1100111001110011
- TAK — relacja jest zwrotna. Na przekątnej same jedynki: każdy element jest w relacji z samym sobą.
- NIE — relacja nie jest antyzwrotna. Na przekątnej w wierszu $1$ jest 1 — $1$ jest w relacji z samym sobą.
- TAK — relacja jest symetryczna. Każda jedynka ma jedynkę w lustrzanym miejscu po drugiej stronie przekątnej, a każde zero — zero.
- NIE — relacja nie jest asymetryczna. Na przekątnej jest 1 (wiersz $1$ ), a asymetryczna wymaga samych zer na przekątnej.
- NIE — relacja nie jest quasi-asymetryczna. Symetryczne jedynki: ( $1$ , $2$ ) i ( $2$ , $1$ ) — $1$ jest w relacji z $2$ i na odwrót.
- NIE — relacja nie jest spójna. Symetryczne zera: ( $1$ , $3$ ) i ( $3$ , $1$ ) — $1$ i $3$ nie są ze sobą w relacji w żadną stronę.
- NIE — relacja nie jest przechodnia. $1$ jest w relacji z $2$ i $2$ z $3$ , ale $1$ nie jest w relacji z $3$ (w komórce ( $1$ , $3$ ) jest 0).
- Typ: relacja nie jest przechodnia, więc nie jest relacją porządkującą.
Jak czytać ten rysunek:
kliknij własność: na zielono podświetlą się kratki, które ją potwierdzają, na różowo — kontrprzykład. Ostatni przycisk mówi, czy to relacja porządkująca.

pozycja $y$	$1$	$2$	$3$	$4$
wiersz $1$ w $R$	1	1	0	0
kolumna $3$ w $R$	0	1	1	1

pozycja $y$	$1$	$2$	$3$	$4$
wiersz $1$ w $R$	1	1	0	0
kolumna $1$ w $R$	1	1	0	0

pozycja $y$	$1$	$2$	$3$	$4$
wiersz $1$ w $R$	1	1	0	0
kolumna $2$ w $R$	1	1	1	0

pozycja $y$	$1$	$2$	$3$	$4$
wiersz $1$ w $R$	1	1	0	0
kolumna $3$ w $R$	0	1	1	1

pozycja $y$	$1$	$2$	$3$	$4$
wiersz $1$ w $R$	1	1	0	0
kolumna $4$ w $R$	0	0	1	1

pozycja $y$	$1$	$2$	$3$	$4$
wiersz $2$ w $R$	1	1	1	0
kolumna $1$ w $R$	1	1	0	0

pozycja $y$	$1$	$2$	$3$	$4$
wiersz $2$ w $R$	1	1	1	0
kolumna $2$ w $R$	1	1	1	0

pozycja $y$	$1$	$2$	$3$	$4$
wiersz $2$ w $R$	1	1	1	0
kolumna $3$ w $R$	0	1	1	1

pozycja $y$	$1$	$2$	$3$	$4$
wiersz $2$ w $R$	1	1	1	0
kolumna $4$ w $R$	0	0	1	1

pozycja $y$	$1$	$2$	$3$	$4$
wiersz $3$ w $R$	0	1	1	1
kolumna $1$ w $R$	1	1	0	0

pozycja $y$	$1$	$2$	$3$	$4$
wiersz $3$ w $R$	0	1	1	1
kolumna $2$ w $R$	1	1	1	0

pozycja $y$	$1$	$2$	$3$	$4$
wiersz $3$ w $R$	0	1	1	1
kolumna $3$ w $R$	0	1	1	1

pozycja $y$	$1$	$2$	$3$	$4$
wiersz $3$ w $R$	0	1	1	1
kolumna $4$ w $R$	0	0	1	1

pozycja $y$	$1$	$2$	$3$	$4$
wiersz $4$ w $R$	0	0	1	1
kolumna $1$ w $R$	1	1	0	0

pozycja $y$	$1$	$2$	$3$	$4$
wiersz $4$ w $R$	0	0	1	1
kolumna $2$ w $R$	1	1	1	0

pozycja $y$	$1$	$2$	$3$	$4$
wiersz $4$ w $R$	0	0	1	1
kolumna $3$ w $R$	0	1	1	1

pozycja $y$	$1$	$2$	$3$	$4$
wiersz $4$ w $R$	0	0	1	1
kolumna $4$ w $R$	0	0	1	1

Teraz zadanie z zajęć. Przepis jest ten sam. Nowe jest tylko to, że warunek zapisano symbolami, więc najpierw trzeba go przetłumaczyć na zwykłe słowa.

Zadanie · krok po kroku

Zbadaj własności relacji: suma kwadratów dzieli się przez 3

Zad. 1, str. 58, i)

Relacja $P \subset \{1, 2, 3, 4, 5, 6\}^2$ jest określona warunkiem:

xPy \Leftrightarrow \exists k \in \mathbb{Z}: x^2 + y^2 = 3k

Zbadaj jej własności.

Plan — co zrobimy i po co

Tłumaczymy warunek na zwykłe słowa — bez tego nie wiadomo, co liczyć w kratkach.
Budujemy macierz $6 \times 6$ , bo własności czytamy z macierzy.
Patrzymy na przekątną → zwrotność i antyzwrotność.
Patrzymy na lustrzane kratki → symetria, quasi-asymetria, asymetria, spójność.
Liczymy $P \circ P$ i porównujemy z $P$ → przechodniość.
Zbieramy wyniki. Przy każdej własności, która nie zachodzi, podajemy kontrprzykład.

Kroki 3–6 to ten sam przepis co w zadaniu wyżej.

Przetłumacz warunek na zwykłe słowa
$x P y \Leftrightarrow \exists k \in Z : x^{2} + y^{2} = 3 k$
Czytamy: $x$ jest w relacji $P$ z $y$ wtedy i tylko wtedy, gdy istnieje liczba całkowita $k$ taka, że $x^{2} + y^{2} = 3 k$
$\exists k \in Z$
„istnieje liczba całkowita $k$ ”. $Z$ to zbiór liczb całkowitych: …, $- 2$ , $- 1$ , $0$ , $1$ , $2$ , …
$x^{2} + y^{2}$
suma kwadratów: $x \cdot x + y \cdot y$
$3 k$
trzy razy liczba całkowita, czyli jedna z liczb …, $- 3$ , $0$ , $3$ , $6$ , $9$ , … Suma kwadratów ma być jedną z nich. Po ludzku: $x^{2} + y^{2}$ dzieli się przez 3 bez reszty.
Dwa przykłady:
- Para $(1, 2)$ : $1^2 + 2^2 = 1 + 4 = 5$ . Wśród liczb $3k$ są $3$ i $6$ , ale nie ma $5$ . Para nie należy do $P$ .
- Para $(3, 6)$ : $3^2 + 6^2 = 9 + 36 = 45 = 3 \cdot 15$ . Takie $k$ istnieje — to $15$ . Para należy do $P$ .
Bo tak — umowa
$\{1, 2, 3, 4, 5, 6\}^2$ to skrót od $\{1, 2, 3, 4, 5, 6\} \times \{1, 2, 3, 4, 5, 6\}$ — tak jak $5^2$ to skrót od $5 \cdot 5$ . Relacja jest więc w jednym zbiorze, a jej macierz ma 6 wierszy i 6 kolumn z tymi samymi liczbami.

Zbuduj macierz

Dla każdej kratki: $x$ z lewej, $y$ z góry. Liczysz $x^2 + y^2$ i dzielisz wynik przez 3. Dzieli się bez reszty → 1. Zostaje reszta → 0.

$x \ y$	$y = 1$	$y = 2$	$y = 3$	$y = 4$	$y = 5$	$y = 6$
$x = 1$	$1^{2} + 1^{2} = 2$ $reszta 2$ → 0	$1^{2} + 2^{2} = 5$ $reszta 2$ → 0	$1^{2} + 3^{2} = 10$ $reszta 1$ → 0	$1^{2} + 4^{2} = 17$ $reszta 2$ → 0	$1^{2} + 5^{2} = 26$ $reszta 2$ → 0	$1^{2} + 6^{2} = 37$ $reszta 1$ → 0
$x = 2$	$2^{2} + 1^{2} = 5$ $reszta 2$ → 0	$2^{2} + 2^{2} = 8$ $reszta 2$ → 0	$2^{2} + 3^{2} = 13$ $reszta 1$ → 0	$2^{2} + 4^{2} = 20$ $reszta 2$ → 0	$2^{2} + 5^{2} = 29$ $reszta 2$ → 0	$2^{2} + 6^{2} = 40$ $reszta 1$ → 0
$x = 3$	$3^{2} + 1^{2} = 10$ $reszta 1$ → 0	$3^{2} + 2^{2} = 13$ $reszta 1$ → 0	$3^{2} + 3^{2} = 18$ $reszta 0$ → 1	$3^{2} + 4^{2} = 25$ $reszta 1$ → 0	$3^{2} + 5^{2} = 34$ $reszta 1$ → 0	$3^{2} + 6^{2} = 45$ $reszta 0$ → 1
$x = 4$	$4^{2} + 1^{2} = 17$ $reszta 2$ → 0	$4^{2} + 2^{2} = 20$ $reszta 2$ → 0	$4^{2} + 3^{2} = 25$ $reszta 1$ → 0	$4^{2} + 4^{2} = 32$ $reszta 2$ → 0	$4^{2} + 5^{2} = 41$ $reszta 2$ → 0	$4^{2} + 6^{2} = 52$ $reszta 1$ → 0
$x = 5$	$5^{2} + 1^{2} = 26$ $reszta 2$ → 0	$5^{2} + 2^{2} = 29$ $reszta 2$ → 0	$5^{2} + 3^{2} = 34$ $reszta 1$ → 0	$5^{2} + 4^{2} = 41$ $reszta 2$ → 0	$5^{2} + 5^{2} = 50$ $reszta 2$ → 0	$5^{2} + 6^{2} = 61$ $reszta 1$ → 0
$x = 6$	$6^{2} + 1^{2} = 37$ $reszta 1$ → 0	$6^{2} + 2^{2} = 40$ $reszta 1$ → 0	$6^{2} + 3^{2} = 45$ $reszta 0$ → 1	$6^{2} + 4^{2} = 52$ $reszta 1$ → 0	$6^{2} + 5^{2} = 61$ $reszta 1$ → 0	$6^{2} + 6^{2} = 72$ $reszta 0$ → 1

Wiersz $x = 1$ , kolumna $y = 1$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $1^{2} + 1^{2} = 2$ , a $reszta 2$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 1$ , kolumna $y = 2$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $1^{2} + 2^{2} = 5$ , a $reszta 2$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 1$ , kolumna $y = 3$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $1^{2} + 3^{2} = 10$ , a $reszta 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 1$ , kolumna $y = 4$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $1^{2} + 4^{2} = 17$ , a $reszta 2$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 1$ , kolumna $y = 5$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $1^{2} + 5^{2} = 26$ , a $reszta 2$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 1$ , kolumna $y = 6$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $1^{2} + 6^{2} = 37$ , a $reszta 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 2$ , kolumna $y = 1$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $2^{2} + 1^{2} = 5$ , a $reszta 2$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 2$ , kolumna $y = 2$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $2^{2} + 2^{2} = 8$ , a $reszta 2$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 2$ , kolumna $y = 3$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $2^{2} + 3^{2} = 13$ , a $reszta 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 2$ , kolumna $y = 4$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $2^{2} + 4^{2} = 20$ , a $reszta 2$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 2$ , kolumna $y = 5$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $2^{2} + 5^{2} = 29$ , a $reszta 2$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 2$ , kolumna $y = 6$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $2^{2} + 6^{2} = 40$ , a $reszta 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 3$ , kolumna $y = 1$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $3^{2} + 1^{2} = 10$ , a $reszta 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 3$ , kolumna $y = 2$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $3^{2} + 2^{2} = 13$ , a $reszta 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 3$ , kolumna $y = 3$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $3^{2} + 3^{2} = 18$ , a $reszta 0$ . Warunek jest spełniony, więc wpisujemy 1 — para należy do relacji.
Wiersz $x = 3$ , kolumna $y = 4$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $3^{2} + 4^{2} = 25$ , a $reszta 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 3$ , kolumna $y = 5$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $3^{2} + 5^{2} = 34$ , a $reszta 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 3$ , kolumna $y = 6$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $3^{2} + 6^{2} = 45$ , a $reszta 0$ . Warunek jest spełniony, więc wpisujemy 1 — para należy do relacji.
Wiersz $x = 4$ , kolumna $y = 1$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $4^{2} + 1^{2} = 17$ , a $reszta 2$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 4$ , kolumna $y = 2$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $4^{2} + 2^{2} = 20$ , a $reszta 2$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 4$ , kolumna $y = 3$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $4^{2} + 3^{2} = 25$ , a $reszta 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 4$ , kolumna $y = 4$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $4^{2} + 4^{2} = 32$ , a $reszta 2$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 4$ , kolumna $y = 5$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $4^{2} + 5^{2} = 41$ , a $reszta 2$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 4$ , kolumna $y = 6$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $4^{2} + 6^{2} = 52$ , a $reszta 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 5$ , kolumna $y = 1$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $5^{2} + 1^{2} = 26$ , a $reszta 2$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 5$ , kolumna $y = 2$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $5^{2} + 2^{2} = 29$ , a $reszta 2$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 5$ , kolumna $y = 3$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $5^{2} + 3^{2} = 34$ , a $reszta 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 5$ , kolumna $y = 4$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $5^{2} + 4^{2} = 41$ , a $reszta 2$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 5$ , kolumna $y = 5$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $5^{2} + 5^{2} = 50$ , a $reszta 2$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 5$ , kolumna $y = 6$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $5^{2} + 6^{2} = 61$ , a $reszta 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 6$ , kolumna $y = 1$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $6^{2} + 1^{2} = 37$ , a $reszta 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 6$ , kolumna $y = 2$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $6^{2} + 2^{2} = 40$ , a $reszta 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 6$ , kolumna $y = 3$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $6^{2} + 3^{2} = 45$ , a $reszta 0$ . Warunek jest spełniony, więc wpisujemy 1 — para należy do relacji.
Wiersz $x = 6$ , kolumna $y = 4$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $6^{2} + 4^{2} = 52$ , a $reszta 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 6$ , kolumna $y = 5$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $6^{2} + 5^{2} = 61$ , a $reszta 1$ . Warunek nie jest spełniony, więc wpisujemy 0 — para nie należy do relacji.
Wiersz $x = 6$ , kolumna $y = 6$ . Wstawiamy do warunku $x^{2} + y^{2} = 3 k$ : $6^{2} + 6^{2} = 72$ , a $reszta 0$ . Warunek jest spełniony, więc wpisujemy 1 — para należy do relacji.

Jak czytać tę siatkę:

górna linijka to suma kwadratów, dolna — reszta z dzielenia tej sumy przez 3. Reszta 0 → 1 (suma dzieli się przez 3), inna reszta → 0.

P

1

2

3

4

5

6

1

2

3

4

5

6

000000000000001001000000000000001001

Jedynki są tylko w czterech kratkach: $(3, 3)$ , $(3, 6)$ , $(6, 3)$ i $(6, 6)$ . To pary, w których obie liczby dzielą się przez 3.

Inny sposób

Na kolokwium da się szybciej: zamiast 36 sum policz tylko 6 kwadratów i ich reszty z dzielenia przez 3.

$x$	1	2	3	4	5	6
$x^2$	1	4	9	16	25	36
reszta	1	1	0	1	1	0

Dodaj reszty $x^2$ i $y^2$ — wyjdzie reszta całej sumy (działa, bo w tabeli są tylko reszty 0 i 1). Sprawdźmy na parze $(2, 5)$ : reszty $1 + 1 = 2$ , a $4 + 25 = 29$ i $29 = 3 \cdot 9 + 2$ — reszta też $2$ . Zgadza się.

$0 + 0 = 0$ → suma dzieli się przez 3.
$0 + 1 = 1$ i $1 + 1 = 2$ → zostaje reszta.

Jedynka wychodzi więc tylko wtedy, gdy obie liczby mają resztę 0. To liczby 3 i 6.

Przekątna: ani zwrotna, ani antyzwrotna
$P$
$1$ $2$ $3$ $4$ $5$ $6$
$1$ $2$ $3$ $4$ $5$ $6$
000000000000001001000000000000001001
Na przekątnej są i zera, i jedynki: 0, 0, 1, 0, 0, 1.
- Różowa kratka $(1, 1)$ ma 0, więc relacja nie jest zwrotna.
- Złota kratka $(3, 3)$ ma 1, więc relacja nie jest antyzwrotna.
To pułapka z ramki „Niezwrotna to nie antyzwrotna”: relacja nie jest ani zwrotna, ani antyzwrotna.
Dlaczego?
$1^2 + 1^2 = 2$ nie dzieli się przez 3, więc w kratce $(1, 1)$ jest 0. $3^2 + 3^2 = 18 = 3 \cdot 6$ dzieli się przez 3, więc w kratce $(3, 3)$ jest 1.
Lustrzane kratki: symetryczna, nie quasi-asymetryczna, nie spójna
$P$
$1$ $2$ $3$ $4$ $5$ $6$
$1$ $2$ $3$ $4$ $5$ $6$
000000000000001001000000000000001001
- Każda kratka ma tę samą cyfrę co jej odbicie w lustrze. Relacja jest symetryczna.
- Złote kratki $(3, 6)$ i $(6, 3)$ to dwie jedynki w lustrze. Relacja nie jest quasi-asymetryczna, a więc nie jest też asymetryczna.
- Różowe kratki $(1, 2)$ i $(2, 1)$ to dwa zera w lustrze: 1 i 2 nie są w relacji w żadną stronę. Relacja nie jest spójna.
Dlaczego?
Para $(x, y)$ i para $(y, x)$ dają tę samą sumę, bo $x^2 + y^2 = y^2 + x^2$ — kolejność dodawania nie zmienia wyniku. Dlatego kratka i jej odbicie zawsze mają tę samą cyfrę.
Przechodniość: policz P ∘ P i porównaj z P
Krok A. Liczymy $P \circ P$ kratka po kratce: wiersz $x$ macierzy $P$ pod kolumną $z$ tej samej macierzy. Przykład — kratka $(3, 6)$ :
pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
wiersz $3$ w $P$ 0 0 1 0 0 1
kolumna $6$ w $P$ 0 0 1 0 0 1
Na pozycji $y = 3$ obie mają 1: $3 P 3$ i $3 P 6$ . Da się przejść z $3$ do $6$ przez $3$ , więc w komórce $(3, 6)$ wpisujemy 1.
Tak samo powstają pozostałe kratki — kliknij dowolną kratkę macierzy wyniku $P \circ P$ :
$P$
$1$ $2$ $3$ $4$ $5$ $6$
$1$ $2$ $3$ $4$ $5$ $6$
000000000000001001000000000000001001
$P$
$1$ $2$ $3$ $4$ $5$ $6$
$1$ $2$ $3$ $4$ $5$ $6$
000000000000001001000000000000001001
$P \circ P$
$1$ $2$ $3$ $4$ $5$ $6$
$1$ $2$ $3$ $4$ $5$ $6$
····································
Kliknij komórkę macierzy $P \circ P$ , żeby ją odkryć i zobaczyć, skąd się wzięła.
- Komórka $(1, 1)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $1$ w $P$ 0 0 0 0 0 0
  kolumna $1$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $1$ do $1$ przez żaden element. W komórce $(1, 1)$ wpisujemy 0.
- Komórka $(1, 2)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $1$ w $P$ 0 0 0 0 0 0
  kolumna $2$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $1$ do $2$ przez żaden element. W komórce $(1, 2)$ wpisujemy 0.
- Komórka $(1, 3)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $1$ w $P$ 0 0 0 0 0 0
  kolumna $3$ w $P$ 0 0 1 0 0 1
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $1$ do $3$ przez żaden element. W komórce $(1, 3)$ wpisujemy 0.
- Komórka $(1, 4)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $1$ w $P$ 0 0 0 0 0 0
  kolumna $4$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $1$ do $4$ przez żaden element. W komórce $(1, 4)$ wpisujemy 0.
- Komórka $(1, 5)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $1$ w $P$ 0 0 0 0 0 0
  kolumna $5$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $1$ do $5$ przez żaden element. W komórce $(1, 5)$ wpisujemy 0.
- Komórka $(1, 6)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $1$ w $P$ 0 0 0 0 0 0
  kolumna $6$ w $P$ 0 0 1 0 0 1
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $1$ do $6$ przez żaden element. W komórce $(1, 6)$ wpisujemy 0.
- Komórka $(2, 1)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $2$ w $P$ 0 0 0 0 0 0
  kolumna $1$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $2$ do $1$ przez żaden element. W komórce $(2, 1)$ wpisujemy 0.
- Komórka $(2, 2)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $2$ w $P$ 0 0 0 0 0 0
  kolumna $2$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $2$ do $2$ przez żaden element. W komórce $(2, 2)$ wpisujemy 0.
- Komórka $(2, 3)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $2$ w $P$ 0 0 0 0 0 0
  kolumna $3$ w $P$ 0 0 1 0 0 1
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $2$ do $3$ przez żaden element. W komórce $(2, 3)$ wpisujemy 0.
- Komórka $(2, 4)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $2$ w $P$ 0 0 0 0 0 0
  kolumna $4$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $2$ do $4$ przez żaden element. W komórce $(2, 4)$ wpisujemy 0.
- Komórka $(2, 5)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $2$ w $P$ 0 0 0 0 0 0
  kolumna $5$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $2$ do $5$ przez żaden element. W komórce $(2, 5)$ wpisujemy 0.
- Komórka $(2, 6)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $2$ w $P$ 0 0 0 0 0 0
  kolumna $6$ w $P$ 0 0 1 0 0 1
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $2$ do $6$ przez żaden element. W komórce $(2, 6)$ wpisujemy 0.
- Komórka $(3, 1)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $3$ w $P$ 0 0 1 0 0 1
  kolumna $1$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $3$ do $1$ przez żaden element. W komórce $(3, 1)$ wpisujemy 0.
- Komórka $(3, 2)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $3$ w $P$ 0 0 1 0 0 1
  kolumna $2$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $3$ do $2$ przez żaden element. W komórce $(3, 2)$ wpisujemy 0.
- Komórka $(3, 3)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $3$ w $P$ 0 0 1 0 0 1
  kolumna $3$ w $P$ 0 0 1 0 0 1
  Na pozycji $y = 3$ obie mają 1: $3 P 3$ i $3 P 3$ . Da się przejść z $3$ do $3$ przez $3$ , więc w komórce $(3, 3)$ wpisujemy 1.
- Komórka $(3, 4)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $3$ w $P$ 0 0 1 0 0 1
  kolumna $4$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $3$ do $4$ przez żaden element. W komórce $(3, 4)$ wpisujemy 0.
- Komórka $(3, 5)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $3$ w $P$ 0 0 1 0 0 1
  kolumna $5$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $3$ do $5$ przez żaden element. W komórce $(3, 5)$ wpisujemy 0.
- Komórka $(3, 6)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $3$ w $P$ 0 0 1 0 0 1
  kolumna $6$ w $P$ 0 0 1 0 0 1
  Na pozycji $y = 3$ obie mają 1: $3 P 3$ i $3 P 6$ . Da się przejść z $3$ do $6$ przez $3$ , więc w komórce $(3, 6)$ wpisujemy 1.
- Komórka $(4, 1)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $4$ w $P$ 0 0 0 0 0 0
  kolumna $1$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $4$ do $1$ przez żaden element. W komórce $(4, 1)$ wpisujemy 0.
- Komórka $(4, 2)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $4$ w $P$ 0 0 0 0 0 0
  kolumna $2$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $4$ do $2$ przez żaden element. W komórce $(4, 2)$ wpisujemy 0.
- Komórka $(4, 3)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $4$ w $P$ 0 0 0 0 0 0
  kolumna $3$ w $P$ 0 0 1 0 0 1
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $4$ do $3$ przez żaden element. W komórce $(4, 3)$ wpisujemy 0.
- Komórka $(4, 4)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $4$ w $P$ 0 0 0 0 0 0
  kolumna $4$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $4$ do $4$ przez żaden element. W komórce $(4, 4)$ wpisujemy 0.
- Komórka $(4, 5)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $4$ w $P$ 0 0 0 0 0 0
  kolumna $5$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $4$ do $5$ przez żaden element. W komórce $(4, 5)$ wpisujemy 0.
- Komórka $(4, 6)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $4$ w $P$ 0 0 0 0 0 0
  kolumna $6$ w $P$ 0 0 1 0 0 1
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $4$ do $6$ przez żaden element. W komórce $(4, 6)$ wpisujemy 0.
- Komórka $(5, 1)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $5$ w $P$ 0 0 0 0 0 0
  kolumna $1$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $5$ do $1$ przez żaden element. W komórce $(5, 1)$ wpisujemy 0.
- Komórka $(5, 2)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $5$ w $P$ 0 0 0 0 0 0
  kolumna $2$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $5$ do $2$ przez żaden element. W komórce $(5, 2)$ wpisujemy 0.
- Komórka $(5, 3)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $5$ w $P$ 0 0 0 0 0 0
  kolumna $3$ w $P$ 0 0 1 0 0 1
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $5$ do $3$ przez żaden element. W komórce $(5, 3)$ wpisujemy 0.
- Komórka $(5, 4)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $5$ w $P$ 0 0 0 0 0 0
  kolumna $4$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $5$ do $4$ przez żaden element. W komórce $(5, 4)$ wpisujemy 0.
- Komórka $(5, 5)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $5$ w $P$ 0 0 0 0 0 0
  kolumna $5$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $5$ do $5$ przez żaden element. W komórce $(5, 5)$ wpisujemy 0.
- Komórka $(5, 6)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $5$ w $P$ 0 0 0 0 0 0
  kolumna $6$ w $P$ 0 0 1 0 0 1
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $5$ do $6$ przez żaden element. W komórce $(5, 6)$ wpisujemy 0.
- Komórka $(6, 1)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $6$ w $P$ 0 0 1 0 0 1
  kolumna $1$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $6$ do $1$ przez żaden element. W komórce $(6, 1)$ wpisujemy 0.
- Komórka $(6, 2)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $6$ w $P$ 0 0 1 0 0 1
  kolumna $2$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $6$ do $2$ przez żaden element. W komórce $(6, 2)$ wpisujemy 0.
- Komórka $(6, 3)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $6$ w $P$ 0 0 1 0 0 1
  kolumna $3$ w $P$ 0 0 1 0 0 1
  Na pozycji $y = 3$ obie mają 1: $6 P 3$ i $3 P 3$ . Da się przejść z $6$ do $3$ przez $3$ , więc w komórce $(6, 3)$ wpisujemy 1.
- Komórka $(6, 4)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $6$ w $P$ 0 0 1 0 0 1
  kolumna $4$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $6$ do $4$ przez żaden element. W komórce $(6, 4)$ wpisujemy 0.
- Komórka $(6, 5)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $6$ w $P$ 0 0 1 0 0 1
  kolumna $5$ w $P$ 0 0 0 0 0 0
  Nie ma pozycji, na której obie mają 1 — nie da się przejść z $6$ do $5$ przez żaden element. W komórce $(6, 5)$ wpisujemy 0.
- Komórka $(6, 6)$ :
  pozycja $y$ $1$ $2$ $3$ $4$ $5$ $6$
  wiersz $6$ w $P$ 0 0 1 0 0 1
  kolumna $6$ w $P$ 0 0 1 0 0 1
  Na pozycji $y = 3$ obie mają 1: $6 P 3$ i $3 P 6$ . Da się przejść z $6$ do $6$ przez $3$ , więc w komórce $(6, 6)$ wpisujemy 1.
Jak czytać ten rysunek:
złożenie relacji $P$ z samą sobą. Pierwsze dwie macierze to ta sama relacja $P$ . Trzecia to wynik — jedynka znaczy „da się dojść w dwóch krokach”.
Krok B. Porównujemy $P \circ P$ z $P$ . Szukamy kratki, w której $P \circ P$ ma 1, a $P$ ma 0.
$P \circ P$
$1$ $2$ $3$ $4$ $5$ $6$
$1$ $2$ $3$ $4$ $5$ $6$
000000000000001001000000000000001001
$P$
$1$ $2$ $3$ $4$ $5$ $6$
$1$ $2$ $3$ $4$ $5$ $6$
000000000000001001000000000000001001
Takiej kratki nie ma. Jedynki stoją w tych samych miejscach (zielone) — $P \circ P$ wyszło takie samo jak $P$ . Warunek $P \circ P \subset P$ jest spełniony, więc relacja jest przechodnia.
Dlaczego?
Przechodniość psuje tylko kratka, w której $P \circ P$ ma 1, a $P$ ma 0: droga w dwóch krokach bez skrótu w jednym. Tu wszystkie jedynki łączą tylko liczby 3 i 6. Każda droga w dwóch krokach zaczyna się i kończy na 3 albo 6, a każde dwie z tych liczb są w relacji bezpośrednio — skrót zawsze istnieje.
Inny sposób
Szybki test z zadania wyżej: jeśli w wierszu $x$ jest 1 w kolumnie $y$ , to wiersz $y$ musi się „mieścić” w wierszu $x$ . Jedynki są tylko w wierszach 3 i 6, a te dwa wiersze są identyczne. Test zdany.
Zbierz wynik
Relacja jest symetryczna i przechodnia. Nie jest zwrotna, antyzwrotna, asymetryczna, quasi-asymetryczna ani spójna.
$P$
$1$ $2$ $3$ $4$ $5$ $6$
$1$ $2$ $3$ $4$ $5$ $6$
000000000000001001000000000000001001
- NIE — relacja nie jest zwrotna. Na przekątnej w wierszu $1$ jest 0 — $1$ nie jest w relacji z samym sobą.
- NIE — relacja nie jest antyzwrotna. Na przekątnej w wierszu $3$ jest 1 — $3$ jest w relacji z samym sobą.
- TAK — relacja jest symetryczna. Każda jedynka ma jedynkę w lustrzanym miejscu po drugiej stronie przekątnej, a każde zero — zero.
- NIE — relacja nie jest asymetryczna. Na przekątnej jest 1 (wiersz $3$ ), a asymetryczna wymaga samych zer na przekątnej.
- NIE — relacja nie jest quasi-asymetryczna. Symetryczne jedynki: ( $3$ , $6$ ) i ( $6$ , $3$ ) — $3$ jest w relacji z $6$ i na odwrót.
- NIE — relacja nie jest spójna. Symetryczne zera: ( $1$ , $2$ ) i ( $2$ , $1$ ) — $1$ i $2$ nie są ze sobą w relacji w żadną stronę.
- TAK — relacja jest przechodnia. Dla każdych dwóch jedynek „x w relacji z y” i „y w relacji z z” jest też jedynka w komórce (x, z) — złożenie P∘P zawiera się w P.
- Typ: relacja jest przechodnia, ale nie pasuje do żadnego pola schematu (nie jest ani zwrotna, ani asymetryczna).
Jak czytać ten rysunek:
kliknij własność: na zielono podświetlą się kratki, które ją potwierdzają, na różowo — kontrprzykład. Ostatni przycisk mówi, czy to relacja porządkująca.

pozycja $y$	$1$	$2$	$3$	$4$	$5$	$6$
wiersz $3$ w $P$	0	0	1	0	0	1
kolumna $6$ w $P$	0	0	1	0	0	1

pozycja $y$	$1$	$2$	$3$	$4$	$5$	$6$
wiersz $1$ w $P$	0	0	0	0	0	0
kolumna $1$ w $P$	0	0	0	0	0	0

pozycja $y$	$1$	$2$	$3$	$4$	$5$	$6$
wiersz $1$ w $P$	0	0	0	0	0	0
kolumna $2$ w $P$	0	0	0	0	0	0

pozycja $y$	$1$	$2$	$3$	$4$	$5$	$6$
wiersz $1$ w $P$	0	0	0	0	0	0
kolumna $3$ w $P$	0	0	1	0	0	1

pozycja $y$	$1$	$2$	$3$	$4$	$5$	$6$
wiersz $1$ w $P$	0	0	0	0	0	0
kolumna $4$ w $P$	0	0	0	0	0	0

pozycja $y$	$1$	$2$	$3$	$4$	$5$	$6$
wiersz $1$ w $P$	0	0	0	0	0	0
kolumna $5$ w $P$	0	0	0	0	0	0

pozycja $y$	$1$	$2$	$3$	$4$	$5$	$6$
wiersz $1$ w $P$	0	0	0	0	0	0
kolumna $6$ w $P$	0	0	1	0	0	1

pozycja $y$	$1$	$2$	$3$	$4$	$5$	$6$
wiersz $2$ w $P$	0	0	0	0	0	0
kolumna $1$ w $P$	0	0	0	0	0	0

pozycja $y$	$1$	$2$	$3$	$4$	$5$	$6$
wiersz $2$ w $P$	0	0	0	0	0	0
kolumna $2$ w $P$	0	0	0	0	0	0

pozycja $y$	$1$	$2$	$3$	$4$	$5$	$6$
wiersz $2$ w $P$	0	0	0	0	0	0
kolumna $3$ w $P$	0	0	1	0	0	1

pozycja $y$	$1$	$2$	$3$	$4$	$5$	$6$
wiersz $2$ w $P$	0	0	0	0	0	0
kolumna $4$ w $P$	0	0	0	0	0	0

Relacje porządkujące

coraz mocniejsza asymetria ↑

ostry porządekasymetryczna, przechodnia

liniowy ostry porządekasymetryczna, przechodnia, spójna

porządekquasi-asymetryczna, przechodnia, zwrotna

liniowy porządekquasi-asymetryczna, przechodnia, zwrotna, spójna

preporządekprzechodnia, zwrotna

liniowy preporządekprzechodnia, zwrotna, spójna

dochodzi spójność →

Jak czytać ten schemat:

w każdym polu jest nazwa typu i własności, które relacja musi mieć. Im wyżej, tym mocniejsza asymetria: na dole jej nie ma, w środku jest quasi-asymetria, na górze pełna asymetria (zamiast zwrotności). Prawa kolumna to te same typy z dodatkiem spójności — wtedy przed nazwą stoi „liniowy”. We wszystkich polach jest przechodniość.

Skąd słowo „liniowy”? Relacja spójna pozwala porównać każde dwa elementy. Wtedy da się ustawić wszystkie w jednej kolejce — na jednej linii. Gdy spójności brak, niektórych par nie da się porównać: liczby 2 i 3 w relacji „jest dzielnikiem” nie stoją ani jedna przed drugą.

Relacja	Typ — i dlaczego
$\leq$ w $\{1, 2, 3\}$	liniowy porządek: zwrotna, quasi-asymetryczna, przechodnia, spójna
$<$ w $\{1, 2, 3\}$	liniowy ostry porządek: asymetryczna, przechodnia, spójna
„jest dzielnikiem” w $\{1, 2, 3, 6\}$	porządek: zwrotna, quasi-asymetryczna, przechodnia, ale niespójna (2 i 3)
„zysk $X \geq$ zysk $Y$ ” dla zysków 20, 30, 30	liniowy preporządek: zwrotna, przechodnia, spójna, ale nie quasi-asymetryczna (remis)
„jest starszy niż” w grupie z bliźniakami	ostry porządek: asymetryczna, przechodnia, ale niespójna (bliźniaki)
$\lvert x - y\rvert \leq 1$ w $\{1, 2, 3, 4\}$	nie jest porządkująca, bo nie jest przechodnia
$x^2 + y^2$ dzieli się przez 3 w $\{1, \dots, 6\}$	nie pasuje do żadnego pola: przechodnia, ale ani zwrotna, ani asymetryczna

R

1

2

3

6

1

2

3

6

1111010100110001

TAK — relacja jest zwrotna. Na przekątnej same jedynki: każdy element jest w relacji z samym sobą.
NIE — relacja nie jest antyzwrotna. Na przekątnej w wierszu $1$ jest 1 — $1$ jest w relacji z samym sobą.
NIE — relacja nie jest symetryczna. Komórki ( $1$ , $2$ ) i ( $2$ , $1$ ) leżą symetrycznie, ale mają różne wartości: 1 i 0.
NIE — relacja nie jest asymetryczna. Na przekątnej jest 1 (wiersz $1$ ), a asymetryczna wymaga samych zer na przekątnej.
TAK — relacja jest quasi-asymetryczna. Poza przekątną żadna jedynka nie ma jedynki w lustrzanym miejscu (przekątna nie ma znaczenia).
NIE — relacja nie jest spójna. Symetryczne zera: ( $2$ , $3$ ) i ( $3$ , $2$ ) — $2$ i $3$ nie są ze sobą w relacji w żadną stronę.
TAK — relacja jest przechodnia. Dla każdych dwóch jedynek „x w relacji z y” i „y w relacji z z” jest też jedynka w komórce (x, z) — złożenie P∘P zawiera się w P.
Typ: relacja jest przechodnia, więc to relacja porządkująca: porządek.

Jak czytać ten rysunek:

relacja „ $x$ jest dzielnikiem $y$ ” w zbiorze $\{1, 2, 3, 6\}$ . Kliknij „spójna?” — na różowo podświetlą się zera w lustrze, $(2, 3)$ i $(3, 2)$ . Potem kliknij „typ porządku?”.

Optimum Pareto

Szukasz mieszkania na studia. Liczy się cena i odległość od uczelni — im mniej, tym lepiej w obu przypadkach.

Mieszkanie	A	B	C	D
Cena (zł)	1200	1500	1500	1000
Odległość (km)	3	1	4	6

Żadne mieszkanie nie wygrywa we wszystkim: B jest najbliżej, D najtańsze. Ale C jest gorsze od A pod każdym względem — droższe i dalej. Mieszkanie C możesz skreślić bez żalu. Mówimy, że C jest zdominowane (przez A, a także przez B: ta sama cena, ale bliżej).

Na kolokwium dominację liczy się na macierzach. Dla każdego kryterium budujesz relację preferencji: $X$ jest w relacji z $Y$ , gdy $X$ jest nie gorszy od $Y$ w tym kryterium.

X P_{E} Y \Leftrightarrow E (X) \geq E (Y) X P_{S} Y \Leftrightarrow S (X) \leq S (Y)

$E (X)$: oczekiwany zysk z inwestycji $X$ — im więcej, tym lepiej, więc „nie gorszy” to $\geq$
$S (X)$: ryzyko inwestycji $X$ — im mniej, tym lepiej, więc „nie gorszy” to $\leq$
$P_{E}, P_{S}$: osobna relacja preferencji dla każdego kryterium

Skąd to się bierze?· Dlaczego zaostrzenie robi właśnie to?

Wzór $S = (M^{-1})' \cap M$ robi trzy rzeczy po kolei:

$M^{-1}$ (relacja odwrotna) ma w kratce $(X, Y)$ to, co $M$ ma w lustrzanej kratce $(Y, X)$ .
Dopełnienie $'$ zamienia cyfry. Jedynka zostaje tam, gdzie lustrzana kratka w $M$ miała 0.
Część wspólna z $M$ zostawia 1 tylko tam, gdzie $M$ ma 1 w kratce $(X, Y)$ i 0 w kratce $(Y, X)$ .

Po ludzku: $X$ jest nie gorszy od $Y$ we wszystkim, a $Y$ od $X$ — nie. Czyli $X$ jest w czymś lepszy. To jest dominacja.

Na przekątnej zawsze wychodzi 0: wariant nie dominuje sam siebie.
Dwie jedynki w lustrze też znikają: dwa warianty równe we wszystkim się nie dominują.

Kolumna $Y$ w $S$ mówi, kto dominuje $Y$ . Same zera — nikt. Dlatego szukamy kolumn, a nie wierszy.

Zadanie · krok po kroku

Wyznacz zbiór Pareto dla czterech inwestycji

Zad. 2, str. 68, a)

Inwestycje $A$ , $B$ , $C$ , $D$ . $E$ — oczekiwany zysk (im więcej, tym lepiej), $S$ — ryzyko (im mniej, tym lepiej).

Inwestycja	A	B	C	D
Oczekiwany zysk $E$	20	30	35	40
Ryzyko $S$	10	20	20	25

Plan — co zrobimy i po co

Dla każdego kryterium budujemy macierz preferencji. Pokazuje, kto jest „nie gorszy” od kogo w tym jednym kryterium.
Liczymy część wspólną $M$ . Zostają pary „nie gorszy we wszystkim naraz”.
Liczymy zaostrzenie $S$ . Zostają pary „lepszy”, czyli dominacja.
Szukamy kolumn z samych zer. To warianty, których nikt nie dominuje — zbiór Pareto.

To procedura z zajęć. Ten sam wynik da porównanie każdej pary wariantów w tabeli (przy 4 wariantach to 6 par). Macierze robią dokładnie to samo, ale po kolei, więc nic nie umyka.

Zbuduj macierze preferencji
$XP_EY \Leftrightarrow E(X) \geq E(Y)$ oraz $XP_SY \Leftrightarrow S(X) \leq S(Y)$ . Obie relacje są w zbiorze $\{A, B, C, D\}$ , więc macierze są 4 × 4.
Jak wypełnić wiersz: bierzesz wartość wariantu z lewej strony i porównujesz ją po kolei z wartością każdego wariantu z góry. Znak porównania zależy od kryterium.
$P_{E}$
$A$ $B$ $C$ $D$
$A$ $B$ $C$ $D$
1000110011101111
$P_{S}$
$A$ $B$ $C$ $D$
$A$ $B$ $C$ $D$
1111011101110001
Dlaczego?
Wiersz $C$ w $P_E$ : $E(C) = 35$ . Porównujemy: $35 \geq 20$ (1), $35 \geq 30$ (1), $35 \geq 35$ (1), $35 < 40$ (0). Wiersz $B$ w $P_S$ : $S(B) = 20$ . Porównujemy: $20 > 10$ (0), $20 \leq 20$ (1), $20 \leq 20$ (1), $20 \leq 25$ (1).
Bo tak — umowa
„Im więcej, tym lepiej” (zysk) → znak $\geq$ . „Im mniej, tym lepiej” (ryzyko, koszt) → znak $\leq$ . Który kierunek jest lepszy, mówi treść zadania.
Część wspólna M
Jedynka zostaje tylko tam, gdzie jest w obu macierzach — kratka po kratce, jak przy działaniach na relacjach.
$M$
$A$ $B$ $C$ $D$
$A$ $B$ $C$ $D$
1000010001100001
Przekreślone jedynki znikną w następnym kroku (przekątna i jedynki w lustrze). Jedynka w kółku zostanie.
Dlaczego?
Dominacja wymaga, żeby wariant był nie gorszy we wszystkich kryteriach naraz. „We wszystkich naraz” to część wspólna — tak jak „i” w logice.
Zaostrzenie S
Bierzemy $M$ i zamieniamy na 0: wszystkie jedynki z przekątnej oraz jedynki, które mają jedynkę w lustrze. Tu jedynek w lustrze nie ma, więc zerujemy tylko przekątną. Zostaje jedna jedynka: $(C, B)$ .
$S$
$A$ $B$ $C$ $D$
$A$ $B$ $C$ $D$
0000000001000000
Dlaczego?
Jedynka w $(C, B)$ znaczy: $C$ dominuje $B$ . Sprawdzenie w tabeli: $C$ ma większy zysk (35 > 30) przy takim samym ryzyku (20).
Kolumny z samych zer
Kolumny $A$ , $C$ , $D$ (podświetlone na złoto) to same zera. Kolumna $B$ ma jedynkę — $B$ jest zdominowane.
$P = \{A, C, D\}$
Dlaczego?
Kolumna to „kto dominuje ten wariant”. Same zera = nikt, więc wariant zostaje w zbiorze Pareto.

Zadanie · krok po kroku

Pareto dla czterech pracowników i trzech kryteriów

Zad. 3, str. 68, a)

Pracownicy $A$ , $B$ , $C$ , $D$ . $L$ — liczba projektów (im więcej, tym lepiej), $N$ — nieobecności (im mniej, tym lepiej), $W$ — wynagrodzenie (z punktu widzenia pracodawcy: im mniej, tym lepiej). Pracodawca chce zwolnić połowę pracowników. Czy zbiór Pareto wystarczy, żeby wskazać dwie osoby do zwolnienia?

Pracownik	A	B	C	D
Projekty $L$	10	9	9	8
Nieobecności $N$	5	7	3	3
Wynagrodzenie $W$	3	4	4	3

Plan — co zrobimy i po co

Ta sama procedura co wyżej, tylko z trzema kryteriami: trzy macierze preferencji → część wspólna $M$ → zaostrzenie $S$ → kolumny zer. Na końcu odpowiadamy na pytanie z treści: czy zbiór Pareto wystarczy, żeby wskazać dwie osoby.

Trzy macierze preferencji
$XP_LY \Leftrightarrow L(X) \geq L(Y)$ , $XP_NY \Leftrightarrow N(X) \leq N(Y)$ , $XP_WY \Leftrightarrow W(X) \leq W(Y)$ .
$P_{L}$
$A$ $B$ $C$ $D$
$A$ $B$ $C$ $D$
1111011101110001
$P_{N}$
$A$ $B$ $C$ $D$
$A$ $B$ $C$ $D$
1100010011111111
$P_{W}$
$A$ $B$ $C$ $D$
$A$ $B$ $C$ $D$
1111011001101111
Dlaczego?
Przy kryterium „im mniej, tym lepiej” łatwo przestawić wiersze. Sprawdzaj każdy wiersz z tabelą: wiersz $C$ w $P_W$ to $W(C) = 4$ porównane z 3, 4, 4, 3 — czyli 0, 1, 1, 0. Wiersz $D$ : $W(D) = 3$ — same 1.
Część wspólna M i zaostrzenie S
$M$
$A$ $B$ $C$ $D$
$A$ $B$ $C$ $D$
1100010001100001
$S$
$A$ $B$ $C$ $D$
$A$ $B$ $C$ $D$
0100000001000000
W $S$ zostają dwie jedynki: $(A, B)$ i $(C, B)$ — $B$ jest zdominowany przez $A$ i przez $C$ .
Zbiór Pareto i odpowiedź
$P = \{A, C, D\}$
Zdominowany jest tylko jeden pracownik ( $B$ ). Zbiór Pareto nie wystarczy, żeby wskazać dwie osoby do zwolnienia — trzeba dodatkowych metod oceny (np. wag kryteriów).
Dlaczego?
Metoda Pareto odrzuca tylko warianty, które przegrywają z innym we wszystkim. Między $A$ , $C$ i $D$ nie ma takiej przewagi: $A$ ma najwięcej projektów, $C$ i $D$ najmniej nieobecności, $D$ i $A$ najniższe wynagrodzenie.

Ściąga przed kolokwium

RelacjaPodzbiór

A \times B

xPy

— para

(x, y)

należy do

P

. Kolejność ma znaczenie.

MacierzWiersze = pierwszy element pary, kolumny = drugi. 1 — w relacji, 0 — nie.

DziałaniaKomórka po komórce:

\cup

— lub,

\cap

— i,

\setminus

— 1 i 0,

'

— 0 ↔ 1. Tylko przy tych samych dziedzinach.

Odwrotność

P^{-1}

: pary odwrócone, wiersze ↔ kolumny.

P^{-1} \neq P'

Złożenie

Q \circ P

: najpierw

P

, potem

Q

. Wykonalne, gdy środkowe zbiory równe.

(x, z) = 1

, gdy wiersz

x

P

i kolumna

z

Q

mają wspólną jedynkę.

PrzekątnaSame 1 — zwrotna. Same 0 — antyzwrotna.

Pary symetryczneRówne — symetryczna. Brak dwóch jedynek — quasi-asymetryczna (+ zera na przekątnej → asymetryczna). Brak dwóch zer — spójna.

Przechodnia

R \circ R \subset R

. Szybko: gdy

xRy

, wiersz

y

mieści się w wierszu

x

PorządkiPrzechodnia → porządkująca. Asymetryczna — ostry porządek; zwrotna + quasi — porządek; zwrotna — preporządek. Spójna → „liniowy”.

Dominacja

X

nie gorszy we wszystkim i lepszy w czymś →

X

dominuje

Y

Pareto

M

= część wspólna preferencji →

S

: zeruj przekątną i symetryczne jedynki → kolumny zer = zbiór Pareto.

Ćwiczenia przed kolokwium

Krótkie zadania z natychmiastową odpowiedzią, ułożone według poleceń z kolokwium. Przy każdej odpowiedzi — dobrej i złej — zobaczysz, dlaczego tak jest.

Pary, macierz i graf

Wypełnij macierz

Zbuduj macierz relacji

$A = \{0, 1, 2\}$ , $B = \{1, 2, 3\}$ , $P \subset A \times B$ : $xPy \Leftrightarrow x + y \leq 3$ . Wiersze to elementy $A$ , kolumny — elementy $B$ .

P

1

2

3

0

1

2

Ćwiczenia · 5 zadań

$A = {1, 2}$ , $B = {1, 2, 3}$ , $x P y \Leftrightarrow x < y$ . Jakie pary należą do $P$ ?
Ile wierszy i kolumn ma macierz relacji $P \subset A \times B$ , gdy $∣ A ∣ = 4$ , $∣ B ∣ = 3$ ?
W macierzy relacji $P$ w wierszu 2 i kolumnie 5 jest 1. Co to znaczy?
Na grafie relacji jest strzałka od $a$ do $b$ (i nie ma strzałki od $b$ do $a$ ). Co to znaczy?
Dziedzina relacji $P \subset A \times B$ to:

Działania i odwrotność

Wypełnij macierz

Relacja odwrotna

To ta sama relacja co wyżej: $xPy \Leftrightarrow x + y \leq 3$ , $A = \{0, 1, 2\}$ , $B = \{1, 2, 3\}$ . Wypełnij macierz $P^{-1} \subset B \times A$ — wiersze to teraz elementy $B$ .

P^{- 1}

0

1

2

1

2

3

Ćwiczenia · 5 zadań

Macierz $P$ to $[1101]$ . Jak wygląda $P^{'}$ ?
$P = {(1, a), (2, b)}$ . Ile wynosi $P^{- 1}$ ?
$P \subset A \times B$ , $R \subset B \times A$ , $A \neq = B$ . Czy można wyznaczyć $P \cup R$ jako relację?
Komórka macierzy $P ∖ R$ to 1, gdy…
Macierz $P^{- 1}$ powstaje z macierzy $P$ przez:

Złożenie relacji

Wypełnij macierz

Policz złożenie Q ∘ P

$A = \{1, 2, 3\}$ , $B = \{1, 2\}$ , $C = \{1, 2, 3\}$ . $P \subset A \times B$ : $xPy \Leftrightarrow x \leq y$ , $Q \subset B \times C$ : $xQy \Leftrightarrow x < y$ . Oto ich macierze:

P

1

2

1

2

3

110100

Q

1

2

3

1

2

011001

Wypełnij macierz $Q \circ P \subset A \times C$ : komórka $(x, z)$ to 1, gdy wiersz $x$ w $P$ i kolumna $z$ w $Q$ mają jedynkę na tej samej pozycji.

Q \circ P

1

2

3

1

2

3

pozycja $y$ $1$ $2$
wiersz $1$ w $P$ 1 1
kolumna $1$ w $Q$ 0 0
Nie ma pozycji, na której obie mają 1 — nie da się przejść z $1$ do $1$ przez żaden element. W komórce $(1, 1)$ wpisujemy 0.
pozycja $y$ $1$ $2$
wiersz $1$ w $P$ 1 1
kolumna $2$ w $Q$ 1 0
Na pozycji $y = 1$ obie mają 1: $1 P 1$ i $1 Q 2$ . Da się przejść z $1$ do $2$ przez $1$ , więc w komórce $(1, 2)$ wpisujemy 1.
pozycja $y$ $1$ $2$
wiersz $1$ w $P$ 1 1
kolumna $3$ w $Q$ 1 1
Na pozycji $y = 1$ obie mają 1: $1 P 1$ i $1 Q 3$ . Da się przejść z $1$ do $3$ przez $1$ , więc w komórce $(1, 3)$ wpisujemy 1.
pozycja $y$ $1$ $2$
wiersz $2$ w $P$ 0 1
kolumna $1$ w $Q$ 0 0
Nie ma pozycji, na której obie mają 1 — nie da się przejść z $2$ do $1$ przez żaden element. W komórce $(2, 1)$ wpisujemy 0.
pozycja $y$ $1$ $2$
wiersz $2$ w $P$ 0 1
kolumna $2$ w $Q$ 1 0
Nie ma pozycji, na której obie mają 1 — nie da się przejść z $2$ do $2$ przez żaden element. W komórce $(2, 2)$ wpisujemy 0.
pozycja $y$ $1$ $2$
wiersz $2$ w $P$ 0 1
kolumna $3$ w $Q$ 1 1
Na pozycji $y = 2$ obie mają 1: $2 P 2$ i $2 Q 3$ . Da się przejść z $2$ do $3$ przez $2$ , więc w komórce $(2, 3)$ wpisujemy 1.
pozycja $y$ $1$ $2$
wiersz $3$ w $P$ 0 0
kolumna $1$ w $Q$ 0 0
Nie ma pozycji, na której obie mają 1 — nie da się przejść z $3$ do $1$ przez żaden element. W komórce $(3, 1)$ wpisujemy 0.
pozycja $y$ $1$ $2$
wiersz $3$ w $P$ 0 0
kolumna $2$ w $Q$ 1 0
Nie ma pozycji, na której obie mają 1 — nie da się przejść z $3$ do $2$ przez żaden element. W komórce $(3, 2)$ wpisujemy 0.
pozycja $y$ $1$ $2$
wiersz $3$ w $P$ 0 0
kolumna $3$ w $Q$ 1 1
Nie ma pozycji, na której obie mają 1 — nie da się przejść z $3$ do $3$ przez żaden element. W komórce $(3, 3)$ wpisujemy 0.

Ćwiczenia · 5 zadań

$P \subset A \times B$ , $Q \subset B \times C$ , zbiory $A$ , $B$ , $C$ są różne. Które złożenie jest wykonalne?
$P \subset A \times B$ , $Q \subset B \times C$ . Złożenie $Q \circ P$ jest podzbiorem:
$P \subset A \times B$ , $A \neq = B$ . Czy $P \circ P$ jest wykonalne?
Wiersz $x$ w macierzy $P$ to (0, 1, 0), a kolumna $z$ w macierzy $Q$ to (1, 0, 0). Co jest w komórce $(x, z)$ macierzy $Q \circ P$ ?
Wiemy, że $x P y$ i $y Q z$ . Co z tego wynika?

Własności relacji

Zbadaj własności

Suma parzysta

$A = \{1, 2, 3\}$ , $xRy \Leftrightarrow x + y$ jest liczbą parzystą. Zaznacz przy każdej własności „tak” albo „nie”, a na końcu wybierz typ.

R

1

2

3

1

2

3

101010101

zwrotna?
antyzwrotna?
symetryczna?
asymetryczna?
quasi-asymetryczna?
spójna?
przechodnia?
typ relacji porządkującej?

Zbadaj własności

Następnik

$A = \{1, 2, 3\}$ , $xRy \Leftrightarrow y = x + 1$ .

R

1

2

3

1

2

3

010001000

zwrotna?
antyzwrotna?
symetryczna?
asymetryczna?
quasi-asymetryczna?
spójna?
przechodnia?
typ relacji porządkującej?

Zbadaj własności

Relacja z macierzy

Relacja $R$ w zbiorze $\{a, b, c\}$ dana macierzą.

R

a

b

c

a

b

c

111010001

zwrotna?
antyzwrotna?
symetryczna?
asymetryczna?
quasi-asymetryczna?
spójna?
przechodnia?
typ relacji porządkującej?

Ćwiczenia · 5 zadań

Na przekątnej macierzy relacji są kolejno 1, 0, 1. Relacja jest:
Relacja asymetryczna to taka, która jest:
Macierz relacji to $[0110]$ . Relacja jest:
W macierzy komórki $(a, c)$ i $(c, a)$ mają 0. Relacja na pewno nie jest:
$a R b$ i $b R c$ , ale nie $a R c$ . Relacja na pewno nie jest:

Typ relacji porządkującej

Ćwiczenia · 6 zadań

Relacja jest zwrotna, quasi-asymetryczna i przechodnia, ale nie jest spójna. To:
Relacja jest asymetryczna, przechodnia i spójna. To:
Relacja „ $\leq$ ” w zbiorze ${1, 2, 3}$ to:
Relacja jest zwrotna, symetryczna i spójna, ale nie jest przechodnia. To:
Relacja „zysk $X \geq$ zysk $Y$ ” dla trzech inwestycji z zyskami 20, 30, 30 to:
Relacja „ $x$ jest dzielnikiem $y$ ” w zbiorze ${1, 2, 4, 8}$ to:

Zbiór Pareto

Wypełnij macierz

Zaostrzenie relacji

Cztery telefony: cena (im mniej, tym lepiej) 1500, 2000, 1500, 1800 zł i bateria (im więcej, tym lepiej) 5000, 4500, 4000, 5000 mAh — dla $A$ , $B$ , $C$ , $D$ . Część wspólna macierzy preferencji to:

M

A

B

C

D

A

B

C

D

1111010000100101

Wypełnij macierz zaostrzenia $S$ : zamień na 0 jedynki z przekątnej i symetryczne jedynki, resztę przepisz.

S

A

B

C

D

A

B

C

D

Ćwiczenia · 6 zadań

Telefony z zadania wyżej: który zbiór to zbiór Pareto?
$Y$ jest zdominowany przez $X$ , gdy:
W macierzy $S$ w kolumnie $C$ jest jedynka w wierszu $A$ . Co to znaczy?
Dwie inwestycje mają identyczny zysk i ryzyko. Co dzieje się z nimi w zaostrzeniu?
Kryterium „ryzyko” (im mniej, tym lepiej). Kiedy $X P_{S} Y$ ?
Uczelnie: $X$ — 30 km, prestiż 4; $Y$ — 70 km, prestiż 5; $Z$ — 70 km, prestiż 10 (odległość: mniej lepiej, prestiż: więcej lepiej). Zbiór Pareto to:

Quiz z teorii

Quiz · 10 pytań

Relacje — 10 pytań

Relacja $P \subset A \times B$ to:
Czy $x P y$ znaczy to samo co $y P x$ ?
Przekątna macierzy relacji to:
Czym różnią się $P^{'}$ i $P^{- 1}$ ?
W złożeniu $Q \circ P$ najpierw działa:
Relacja $R$ jest przechodnia, gdy:
Relacja jest spójna, gdy w macierzy:
Relacje porządkujące to najkrócej relacje:
Zaostrzenie $S = (M^{- 1})^{'} \cap M$ w praktyce:
Do zbioru Pareto należą warianty, których kolumna w macierzy $S$ :