Fő tartalom
Számítástudomány
Tantárgy/kurzus: Számítástudomány > 2. témakör
5. lecke: Moduláris aritmetika- Mi a moduláris aritmetika?
- Modulo művelet
- Játék a modulóval
- Maradékosztály
- Kongruencia reláció
- Ekvivalence reláció
- Maradékos osztásra vonatkozó tétel
- Moduláris összeadás és kivonás
- Moduláris összeadás
- Moduláris kihívás (összeadás és kivonás)
- Moduláris szorzás
- Moduláris szorzás
- Moduláris hatványozás
- Gyors moduláris hatványozás
- Gyors moduláris hatványozás
- Moduláris inverz
- Az euklideszi algoritmus
© 2023 Khan AcademyFelhasználási feltételekAdatkezelési tájékoztatóSüti figyelmeztetés
Ekvivalence reláció
Ekvivalens állítások
Mielőtt továbbmegyünk, fontos észben tartani, hogy az alábbi állítások ekvivalensek:
- C, space, vertical bar, space, left parenthesis, A, minus, B, right parenthesis (A „|” jel itt azt jelenti: osztója)
- A, equals, B, plus, K, dot, C (ahol K egész szám)
Ez lehetővé teszi, hogy több alakban is kifejezhessük ugyanazt a koncepciót.
Például az alábbi állítások ekvivalensek:
- 5, space, vertical bar, space, left parenthesis, 13, minus, 23, right parenthesis ( 5, space, vertical bar, space, minus, 10, ami igaz, mert 5, times, left parenthesis, minus, 2, right parenthesis, equals, minus, 10 )
- 13, equals, 23, plus, K, dot, 5. Ez teljesülni fog K, equals, minus, 2-re: 13, equals, 23, plus, left parenthesis, minus, 2, right parenthesis, dot, 5
A kongruens modulo egy ekvivalencia művelet
Győződj meg arról, hogy az előző példában használt szeletek rendelkeznek az alábbi tulajdonságokkal:
- Az egyes szeletekhez tartozó értékpárok között kapcsolat van.
- Nincs olyan érték, ami két szeletben is megtalálható (a szeletek kölcsönösen diszjunktak, vagyis szétválaszthatók).
- Ha egyesítjük az összes szeletet, akkor a kapott halmaz tartalmazni fogja az összes számot.
Az ilyen tulajdonságú szeletekkel rendelkező kör ekvivalencia relációt ír le.
Az ekvivalencia reláció meghatározza, hogyan tudjuk felosztani a kört (hogyan particionáljuk az értékeket), hogyan képezünk ekvivalencia osztályokat.
Az ekvivalencia reláció meghatározza, hogyan tudjuk felosztani a kört (hogyan particionáljuk az értékeket), hogyan képezünk ekvivalencia osztályokat.
Általánosan fogalmazva, az ekvivalencia relációnak rendelkeznie kell az alábbi tulajdonságokkal:
- A kör: a vizsgált értékek gyűjteménye.
- A körszelet: egy ekvivalencia osztály.
- A körszelet felosztása: ekvivalencia reláció.
A korábbi példa esetén:
- A kör: az összes egész szám.
- A B-vel jelölt körszelet: az az ekvivalencia osztály, ahol start text, m, o, d, space, end text, C, equals, B.
- A kör felszeletelése: a kongruens modulo C relációval, \equiv, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis.
Ebből következően azt mondhatjuk, hogy a kongruens modulo C egy ekvivalencia reláció. Az egész számokat C különböző ekvivalencia osztályba sorolja, ezeket az oszályokat maradékosztálynak hívjuk.
Miért fontos az, hogy a kongruens modulo C ekvivalencia reláció ?
Ha tudjuk azt, hogy a kongruens modulo C ekvivalencia reláció, ennek következtében rendelkezni kell bizonyos tulajdonságokkal.
Ekvivalencia relációkra az alábbi tulajdonságok jellemzőek:
Ekvivalencia relációkra az alábbi tulajdonságok jellemzőek:
- reflexív: A ekvivalens A-val.
- szimmetrikus: ha A ekvivalens B-vel, akkor B ekvivalens A-val.
- tranzitív: ha A ekvivalens B-vel és B ekvivalens C-vel, akkor A ekvivalens C-vel.
Mivel a kongruens modulo ekvivalencia reláció (mod C)-re, ez azt jelenti:
- ha A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis, akkor B, \equiv, A, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
- ha A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis és B, \equiv, D, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis, akkor A, \equiv, D, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
Példa
Alkalmazzuk ezeket a tulajdonságokat a start text, m, o, d, space, end text, 5 konkrét példára:
- 3, \equiv, 3, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis (reflexivitás)
- ha 3, \equiv, 8, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis, akkor 8, \equiv, 3, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis (szimmetria)
- ha 3, \equiv, 8, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis és 8, \equiv, 18, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis, akkor 3, \equiv, 18, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis (tranzitivitás)
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.