Niech \(\displaystyle{ X = \left\{ a,b\right\} .}\) Zdefiniować wszystkie relacje przechodnie \(\displaystyle{ R \subseteq X \times X}\).
Czy istnieje jakiś schemat/algorytm albo zbiór w jakimś pdf, jak postępować przy tego typu zadaniu?
Generowanie wszystkich relacji
-
- Użytkownik
- Posty: 95
- Rejestracja: 20 sty 2021, o 10:40
- Płeć: Mężczyzna
- wiek: 18
- Podziękował: 1 raz
- Pomógł: 1 raz
Generowanie wszystkich relacji
Ostatnio zmieniony 6 kwie 2024, o 15:20 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Administrator
- Posty: 34302
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: Generowanie wszystkich relacji
Wszystkich relacji jest \(\displaystyle{ 16}\), więc tak dużo roboty nie ma... A schemat jest jeden: pomyśleć.
Najprościej jest zlokalizować relacje nieprzechodnie, a potem wziąć cała resztę. A w tej sytuacji relacja nie będzie przechodnia tylko wtedy, gdy należą do niej pary \(\displaystyle{ \left\langle a,b\right\rangle }\) i \(\displaystyle{ \left\langle b,a\right\rangle}\), a nie należy któraś z par \(\displaystyle{ \left\langle a,a\right\rangle,\left\langle b,b\right\rangle }\) (lub obie). Masz zatem tylko trzy relacje nieprzechodnie.
JK
Najprościej jest zlokalizować relacje nieprzechodnie, a potem wziąć cała resztę. A w tej sytuacji relacja nie będzie przechodnia tylko wtedy, gdy należą do niej pary \(\displaystyle{ \left\langle a,b\right\rangle }\) i \(\displaystyle{ \left\langle b,a\right\rangle}\), a nie należy któraś z par \(\displaystyle{ \left\langle a,a\right\rangle,\left\langle b,b\right\rangle }\) (lub obie). Masz zatem tylko trzy relacje nieprzechodnie.
JK
-
- Administrator
- Posty: 34302
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: Generowanie wszystkich relacji
Nie wiem, dlaczego relację pustą traktujesz odmiennie. Relacją na zbiorze \(\displaystyle{ X}\) jest dowolny podzbiór zbioru \(\displaystyle{ X \times X}\), który jest czteroelementowy, więc ma \(\displaystyle{ 2^4=16}\) podzbiorów.
JK
JK