MAT1030, diskret matematikk

This is the final exam of a course called MAT1030(Discrete Mathematics) at university of Oslo. You can download the final exam by clicking here. First comes the English version and the norwegian version follows afterwards.
a

Mengder

Mengde differanse :

A - B
eller
A / B
Multimengder :
En multimengde (eng: bag/multiset) er en endelig eller uendelig samling objekter der
innbyrdes rekkefølge ignoreres, men hvor hvert objekt kan forekomme flere ganger. i andre ord Multimengder er mengder der antall forekomster av hvert element teller
Multimengden med elementene a, b, c og d skrives ofte med firkantklammer, slik: [a; b; c; d].

eksempler :
[a,b,c] = [c,b,a]
[a,b,c,a] != [c,b,a]
[a,a,a,b,c] (snitt) [a,a,d]=[a,a]
*** [a,a,b,c] U [a,c] = [a,a,b,c]
*** [a; a; b; c] + [a; c] = [a; a; a; b; c; c]
[a; a; a; b; c] n [a; a; d] = [a; b; c]

Tuppel
Et tuppel (eng: tuple) med n elementer, et n-tuppel, er en samling med n objekter der
både innbyrdes rekkefølge og antall forekomster av hvert objekt teller.
tø, tuppel : <>
Et 2-tuppel med to elementer x og y kalles også et (ordnet) par (eng: ordered pair)
I tuppel : Båade innbyrdes rekkefølge og antall forekomster er viktig.
To n-tupler er like hvis for enhver i slik at 1 < ai =" bi." sxs =" S^2" s =" S^3">

Hvis S er en mengde, så er potensmengden (eng: power set) til S mengden av alle delmengder

Venn Diagram :
Venn-diagrammer brukes til °a illustrere mengder og operasjoner p°a mengder.


Kardinalitet = “størrelsen på en mengde”

To mengder S og T har lik kardinalitet (eng: cardinality) hvis det fins en en-til-en korrespondanse
mellom elementene i S og T.
Mengden S har kardinalitet mindre eller lik T hvis det fins en en-til-en korrespondanse
mellom S og en delmengde av T.
Hvis S er en endelig mengde, så er kardinaliteten til S lik antall elementer i S.
Vi bruker notasjonen |S| for kardinaliteten til S.

Tellbar :
En uendelig mengde S er tellbar (eng: countable) hvis det fins en en-til-en korrespondanse
mellom elementene i S og de naturlige tallene. Hvis ikke, er S overtellbar (eng: uncountable).
Alle endelige mengder er tellbare.

Eksempel.
Mengden av alle partall er tellbar.
Mengden av binære tall er tallbar.
Mengden av brøktall er tellbar.
Mengden av nålevende mennesker er tellbar.
Mengden av reelle tall er ikke tellbar.

En unær relasjon (eng: unary relation) p°a S er en delmengde av S. Kalles ogs°a ofte for et
predikat (eng: predicate).
En binær relasjon (eng: binary relation) fra S til T er en delmengde av S x T.
En n-ær relasjon (eng: n-ary relation) p°a mengdene S1, S2,..., Sn er en delmengde av kryssproduktet S1 x S2 x ... x Sn.
En n-ær relasjon på en mengde S er en delmengde av Sn.

Definisjon (Refleksiv).
En binær relasjon R på mengden S er refleksiv (eng: reflexive) hvis det for alle x i S er slik at
er medlemer av R.

Definisjon (Symmetrisk).
En binær relasjon R på mengden S er symmetrisk (eng: symmetric) hvis det for alle x, y er slik at hvis er medlemer av R, så er medlemer av R.

Definisjon (Transitiv).
En binær relasjon R på mengden S er transitiv (eng: transitive) hvis det for alle x, y, z er slik at
hvis er medlem av R og er medlem av R, så er medlem av R.

Definisjon (Ekvivalensrelasjon).
En binær relasjon p°a mengden S er en ekvivalensrelasjon (eng: equivalence relation) hvis den er
refleksiv, symmetrisk og transitiv.

Definisjon (Anti-symmetrisk).
En binær relasjon R på mengden S er anti-symmetrisk (eng: anti-symmetric) hvis det for alle x, y er slik at hvis medlem av R og medlem av R, så x = y.

Definisjon (Irrefleksiv).
En binær relasjon R på mengden S er irrefleksiv (eng: irreflexive) hvis det ikke fins noen x er medlem av S slik at er medlem av R.