Startpagina / Samenvattingen / T33131 Discrete Wiskunde B / relatie-element-verzameling

Structuren op verzamelingen - LE 17 Equivalentierelaties

Q: Welke relaties ken je?

reflexief: voor elk element uit verzameling A geldt xRx irreflexief: voor elk element uit uit verzameling A geldt niet xRx symmetrisch: als xRy, dan ook yRx antisymmetrisch: als xRy én yRx dan geldt x=y. tranisitief: als xRy en yRz dan ook xRz = als er in 2 stappen van a naar b kan dan ook in 1 stap, Kortom: als er een lange weg in graaf naar eindpunt is moet er ook een korte zijn. --> risat als geheugensteun voor mogelijke graven.

18 belangrijke vragen over Structuren op verzamelingen - LE 17 Equivalentierelaties

Wat zijn de mogelijke kenmerken van binaire relaties?

Reflexief
Irreflexief
Symmetrisch
Antisymmetrisch
Transitief

Welke relaties ken je?

reflexief: voor elk element uit verzameling A geldt xRx
irreflexief: voor elk element uit uit verzameling A geldt niet xRx
symmetrisch: als xRy, dan ook yRx
antisymmetrisch: als xRy én yRx dan geldt x=y.
tranisitief: als xRy en yRz dan ook xRz = als er in 2 stappen van a naar b kan dan ook in 1 stap, Kortom: als er een lange weg in graaf naar eindpunt is moet er ook een korte zijn.
--> risat als geheugensteun voor mogelijke graven.

Een grafentekening bevat een deel van de punten met een relatie op zichzelf.
Is er sprake van een irreflexieve relatie?

Nee, want voor een irreflexieve relatie is alleen sprake als geen enkel element een relatie heeft met zichzelf.

Wanneer is een relatie irreflexief?

Een relatie R in een verzameling A is irreflexief als geldt dat voor elke x is een element van A geldt dat xRx niet opgaat. Dus bij geen één element x van A heeft relatie R betrekking op x zelf.

Wat is het verschil en de overeenkomst tussen een symmetrische relatie, een antisymmetrische relatie en een reflexieve relatie van elementen van verzameling A?

Een antisymmetrische relatie heeft altijd een wederkerende betrekking alleen op zichzelf en nooit op een ander element. Een symmetrische relatie is altijd tussen 2 verschillende elementen. Een nietreflexieve relatie heeft nooit betrekking op hetzelfde element. Een reflexieve relatie heeft altijd betrekking op het element en zichzelf. Als er wel geen wederkerende pijlen zijn, geen enkele dan is de figuur wel antisymetrisch.

Welke relaties sluiten elkaar uit?

reflexief en irreflexief. Maar: een niet reflectieve relatie is niet automatisch irreflectief.
Let op: Voor symmetrisch en antisymmetrisch geldt dit niet!
antisymmetrische verzamelingen zijn niet altijd ook symmetrisch, antisymmetrische verzamelingen zijn altijd wederkerend. Symmetrische verzamelingen kunnen ook antisymmetrisch zijn.

Wanneer is er sprake van een transitieve relatie?

Dan geldt voor elk element van verzameling a:
Als x heeft een relatie met y en y dezelfde relatie met z dan heeft dus x ook zo'n relatie met z.
xRy kan ook gelden als x of y ook een R relatie op zichzelf hebben.
Om te checken of voor verzameling A relatie R transitief is moet je alle mogelijke combinaties van x,y,z zijn elementen van A uitproberen.

Definitie van de Machten van een verzameling

De n-de macht van een binaire relatie R in verzameling A is gelijk aan R tot de macht n = {(x,y) | er zijn p1, p2,p3, ... pn-1 waarvoor p1Rp2, p2Rp3, ...ne pn-1Rpy }

Wat is het verschil tussen de de machtsverzameling van V en de verzameling van alle partities van V?

De lege verzameling maakt deel uit van de machtsverzameling en niet van de verzameling van alle partities.

Wat betekent [x]R?

Stelling 17.11:
[x]R = {y is een element van V | xRy}
Dit wil zeggen als xRy dan behoren x eny tot dezelfde equivalentieklasse, kortom tot dezelfde partitie van V die is samengesteld op basis van relatie R.

Waarom is een partitie een equivalentierelatie?

Omdat voor alle elementen van de partitie geldt dat xRx (reflexief) xRy dan ook yRx (symmetrisch) en als xRy en yRz dan ook xRz (transitief)

Op welke 2 manieren kan je een hoofdverzameling partitioneren?

1. Door de hoofdverzameling zelf in te delen partities.
2. Door de relatie R als uitgangspunt te nemen. Een element x uit de hoofdverzameling te kiezen en van elk ander element y te bepalen of deze een equivalentierelatie heeft met x. Als er een relatie is dan behoren de x e y tot dezelfde partitie. Van de overgebleven elementen die geen R hebben met x pak je een nieuw element en herhaal je de procedure. Net zolang tot elk element een plek in een partitie heeft.

Wat is het verschil tussen een equivalentieklasse en een partitie?

Een equivalentieklasse is onderdeel van een partitie. Een equivalentieklasse wordt weergegeven door [x] op basis van R. De klasse is samengesteld uit elementen die elk met elkaar relatie R hebben.
een partitie is een hoofdverzameling V die is opgedeeld in delen, partities. Elke partitie heeft elementen uit V die op basis van een relatie R ingedeeld zijn in de betreffende partitie. Geen enkel element komt in meer partities voor. Geen enkele equivalentieklasse is leeg.
Definitie van partitie = verdeling, opdeling.

Heeft elke klasse, partitie slechts 1 representant?

Er is maar 1 element van de klasse representant, maar elk element kan de rol van representant vervullen. De representant geeft met de relatie R aan welke elementen tot de klasse behoren. Als geldt element heeft relatie R met representant dan behoort die tot de klasse van de representant.

Wat is het verschil tussen een partitie en een equivalentieklasse?

De definitie van een equivalentieklasse is de verzameling van alle y waarvoor geldt xRy.
Een partitie wordt wel aangeduid aks Ai (A met onder kleine i) A is dan een partitie van hoofdverzameling V. De kleine i geeft aan om welke partitie het gaat. is voor element x en y de i gelijk dan behoren ze tot dezelfde partitie Ai.
Ai is een element van A betekent dat Ai een bepaalde partitie is van de verzameling partities A.

Wat is het Quotiënt van de equivalentierelatie R in een hoofdverzameling V?

Dat is de verzameling equivalentieklassen in een verzameling V op basis van equivalentierelatie R. Bij het bepalen van het Quotiënt moet je kijken naar de verdeling van de elementen van V en niet de verdeling van de uitkomsten van de relatie.

Wat betekent V/R?

Dat is de verzameling equivalentieklassen van hoofdverzameling V, ingedeeld op basis van relatie R. De equivalentieklassen zijn dus elementen van verzameling V/R

Definitie V/R

verzameling van equivalentie klassen van relatie R op hoofdverzameling V. Dus alle euivqalentieverzamelingen van V (op basis van relatie R) / V.
Voorbeeld:
Als V is {1,2,3,4,5,6,7,8} en A1 = even en A2 = oneven dan is A1={2,4,6,8};
A2 = {1,3,5,7} en V/R = {{1,3,5,7}, {2,4,6,8}}.
Het quotiënt kan je dus omschrijven als de verdeling van de elementen van V over de verschillende klassen.

De vragen op deze pagina komen uit de samenvatting van het volgende studiemateriaal:

T33131 Discrete Wiskunde B

Bekijk samenvatting

Een unieke studie- en oefentool
Nooit meer iets twee keer studeren
Haal de cijfers waar je op hoopt
100% zeker alles onthouden

Onthoud sneller, leer beter. Wetenschappelijk bewezen.

Studiemateriaal generieke omslagafbeelding

Structuren op verzamelingen - LE 17 Equivalentierelaties

18 belangrijke vragen over Structuren op verzamelingen - LE 17 Equivalentierelaties

Wat zijn de mogelijke kenmerken van binaire relaties?

Welke relaties ken je?

Een grafentekening bevat een deel van de punten met een relatie op zichzelf. Is er sprake van een irreflexieve relatie?

Wanneer is een relatie irreflexief?

Wat is het verschil en de overeenkomst tussen een symmetrische relatie, een antisymmetrische relatie en een reflexieve relatie van elementen van verzameling A?

Welke relaties sluiten elkaar uit?

Wanneer is er sprake van een transitieve relatie?

Definitie van de Machten van een verzameling

Wat is het verschil tussen de de machtsverzameling van V en de verzameling van alle partities van V?

Wat betekent [x]R?

Waarom is een partitie een equivalentierelatie?

Op welke 2 manieren kan je een hoofdverzameling partitioneren?

Wat is het verschil tussen een equivalentieklasse en een partitie?

Heeft elke klasse, partitie slechts 1 representant?

Wat is het verschil tussen een partitie en een equivalentieklasse?

Wat is het Quotiënt van de equivalentierelatie R in een hoofdverzameling V?

Wat betekent V/R?

Definitie V/R

Samenvattingen die gerelateerd zijn aan Structuren op verzamelingen - LE 16 Boolealgebra's

T33131 Discrete Wiskunde B

Psychologie

1 Inleiding

Inleiding informatica deel 2

Databases

Adviseren moet je doen !

De psychologie van arbeid en gezondheid

inleiding informatica deel 3

Networking All-in-One For Dummies

Foundations of IT service management op basi…

ISDDF

Inleiding informatica

Een grafentekening bevat een deel van de punten met een relatie op zichzelf.
Is er sprake van een irreflexieve relatie?