Bereken: A3 en A0 in (P(V), XOR) met V={1,2,3,4,5,6} en A={2,5,6} en 5-3, 2-2 en 4-20 in (Z7\{0},*)
Ina Ha
Student hbo - vrijdag 14 november 2003
Antwoord
Hoi,
P(V) is de machtsverzameling van V, dit is de verzameling van alle mogelijk deelverzamelingen van V. In dit geval bestaat ze uit 22=64 elementen: { {}, {1},{2},{3},{4},{5},{6} {1,2},{1,3},{1,4},{1,5},{1,6},{2,3},{2,4},{2,5},{2,6},{3,4},{3,5},{3,6},{4,5},{4,6},{5,6}, ... {1,2,3,4,5,6} }
Dit is nogal onhandig werken, daarom kunnen we elk element D van P(V) voorstellen door een bitstring van 6 bits. De i-de bit zetten we 1 wanneer i tot D behoort. P(V) bevat alle mogelijk deelverzamelingen, dus zijn alle mogelijk bitstrings van 6 lang goed. Omgekeerd stelt elke bitstring van 6 lang een element van P(V) voor. Elke bitstring kunnen we verkort voorstellen door ze te interpreteren als de binaire voorstellen van een getal. We hebben dus een bijectie geconstrueerd tussen P(V) en {0,1,2,...,63}
De bewerking XOR voor verzamelingen A XOR B = (A\B)U(B/A), voor bitstrings is het makkelijker: de resulterende bit staat op wanneer precies één van de input-bits opstaat.
In heb bijzonder zie je in dat a XOR a = 0 voor bits en ook voor verzamelingen: A XOR A = (A\A)U(A\A) = {}U{} = {}. We hebben ook dat 0 XOR a = a of {} XOR A = A. Hiermee kan je de machten in je opgave uitrekenen.
Voor het tweede deel werken we in U7,* (met U7= 0\{0}={1,2,3,4,5,6}).
Omdat 7 priem is, is de kleine stelling van Fermat/Euler van toepassing: a6=1 (mod 7) in U7. Om machten te berekenen, volstaat het dus de tabel te maken van de machten tot en met 6. Als je die stelling niet kent, dan kan je gewoon vaststellen dat het klopt... Dit zijn de tabellen voor de bewerkingen * en ^.
Voor elk element a van A is a0=1 en kan je aflezen wat a3 is.
Omdat 7 priem is, heeft elk getal 1,2,..,6 een inverse. Je vindt ze makkelijk in de vermenigvuldigingstabel. Concreet lees je af dat 5-1=3, 2-1=4 en 4-1=2.
De antwoorden op je vragen worden dan: 5-3= (5-1)3= 33=6. 2-2= (2-1)2= 42=2. 4-20= (4-1)20= 220= 218+2= 22=4.
0\{0}={1,2,3,4,5,6}).
Dit zijn de tabellen voor de bewerkingen * en ^.
