--> Archiwum Forum
Toolism [ JCreator ]
Pytanko z matmy dyskretnej..
Pytanie kieruję do osób które raczej miały styczność z matematyką dyskretną. Przygotowuje się do egzaminu i za cholerę nie mogę znaleść nic o tym jak wyznaczać (equivalence classes ) w ( equivalence relations ) ee.. wybaczcie że tutaj podaje nazwy angielskie ale akurat matme dyskretną mam po angielskui.. nie do końca wiem jak to się po polsku nazywa. Ale moge wam powiedzieć co ją charakteruzyje , zapewne osoba która się zna rozpozna ją ( relacja equivalence musi być transitive( przechodnia) symetric ( symetryczna) i reflexive ( zwrotna ). Zatem czy ktoś wie jak znajduje się te klasy? Bo samą taką relację jestem w stanie rozpoznać ale nie wiem jak znaleść tę klasę.. Mogę zarzucić jakimś zadankiem w którym to się znajduje.
Find equivalence classes for relations given ( if it is not equivalence relation, explain why )
Relacja Z x Z xRy <=> x =(tu powinny być 3 kreski bo chodzi o przystawanie modulo) y(mod3)
Toolism [ JCreator ]
matematycy i informatycy w pracy?:)
Toolism [ JCreator ]
;) na pewno wiecie:)
Ciemny [ Legionista ]
Toolism >>>>> dyskretnej nie miałem po angielsku, ale wg mnie equivalence class to 'klasa abstrakcji' w relacji równoważności (taka relacja musi być przechodnia, symetryczna i zwrotna, co jest oczywiste, jeżeli choć trochę kuma się relacje). W klasie abstrakcji wszystkie elementy są ze sobą różnoważne, ew są ze sobą w jakiejś relacji, natomiast elementów z różnych klas nie da się ze sobą porównywać.
Twój przykład jest bardzo dobry :). Będzie tak:
0, 3, 6, 9, ... - to jest jedna klasa abstrakcji (w każdym przypadku y mod 3 = 0)
1, 4, 7, 10, ... - to jest druga klasa (y mod 3 = 1)
2, 5, 8, 11, ... - ostatnia klasa (y mod 3 = 2)
Wszystkie liczby w danej klasie są ze sobą rónoważne, co jak napisałeś potrafisz udowodnić.
A jak się znajduje klasy? Skąd wiedzieć, że to są już wszystkie możliwości? Eeeee, nie pamiętam :), chyba nie ma na to jakiegoś sposobu, tylko trzeba sprawdzać po kolei.
Romanujan [ Konstruktor Katapult ]
equivalence relation = relacja równoważności
equivalence class = klasa równoważności, klasa abstrakcji
Nie ma jednoznacznego przepisu na wyznaczanie klas abstrakcji, to bardzo dużo zależy od zadania.
Oto rozwiązanie Twojego zadania:
Najpierw sprawdzamy, czy relacja R jest relacją równoważności:
1. Zwrotność
x R x <=> x przystaje do x modulo 3 <=> 3 dzieli (x-x) <=> 3 dzieli 0, co jest zawsze prawdą
2. Symetryczność
x R y <=> x przystaje do y modulo 3 <=> 3 dzieli (x-y) <=> 3 dzieli (y-x) <=> y przystaje do x modulo 3 <=> y R x
3. Przechodniość
x R y i y R z <=> 3 dzieli (x-y) i 3 dzieli (y-z) => (zwróć uwagę, że tu jest implikacja, a nie równoważność!) 3 dzieli (x - y + y - z) (wynika to z prostego faktu, że jeśli 3 dzieli dwie liczby, to dzieli też ich sumę - mam nadzieję, że potrafisz to udowodnić) <=> 3 dzieli (x - z) <=> x R z
Zatem jest to relacja równoważności.
Teraz wyznaczymy w bardzo prosty sposób klasy równoważności:
Weźmy element x=0.
0 R y <=> 3 dzieli (0-y) <=> y dzieli się przez 3
Podobnie, weźmy x=1, a potem x=2
1 R y <=> y-1 dzieli się przez 3 <=> y+2 dzieli się przez 3
2 R y <=> ... <=> y + 1 dzieli się przez 3
Ponieważ dla dowolnego całkowitego y albo 3|y (3 dzieli y), albo 3|(y+1), albo 3|(y+2), więc znaleźliśmy już wszystkie klasy abstrakcji (niech \in oznacza symbol "należy do zbioru")
Klasa abstrakcji reprezentowana przez element 0: ‹ x \in Z: 3|x › = ‹ 0, 3, -3, 6, -6, ... ›
Klasa abstrakcji reprezentowana przez element 1: ‹ x \in Z: 3|(x+2) › = ‹ 1, -1, 4, -4, 7, -7, ... ›
Klasa abstrakcji reprezentowana przez element 2: ‹ x \in Z: 3|(x+1) › = ‹ 2, -2, 5, -5, 8, -8, ... ›
Wsio. Nie martw się - za jakiś czas przestaniesz odróżniać dwójkę od minus jedynki, a jedynkę od czwórki, a dzielenie przez trzy będzie dla Ciebie taką samą niedorzecznością, jak dzielenie przez 0 :-)
Romanujan [ Konstruktor Katapult ]
Niech to.. coś mi pozamieniało nawiasy klamrowe na kątowe...
Ciemny [ Legionista ]
Zawsze zmienia.
Toolism [ JCreator ]
dziękuję:)