MA0301 · NTNU

Studieguide for MA0301 Elementær diskret matematikk

Komplett pensumoversikt for elementær diskret matematikk ved NTNU — med forklaringer, sentrale begreper, eksamenstips og vanlige fallgruver. Eksamensoptimalisert basert på tidligere eksamener.

Introduksjon

MA0301 Elementær diskret matematikk er en firetimers skoleeksamen på 100 poeng, hjelpemiddelkode D (ingen trykte eller håndskrevne hjelpemidler; bestemt, enkel kalkulator). Settet er bygd opp av 6–11 oppgaver som fordeler seg på et fast sett hovedtemaer, og flere av årgangene skriver poengfordelingen rett på forsiden. En gjennomgang av 29 eksamenssett fra 2009 til 2026 gir dette bildet av hva som faktisk testes:

Relasjoner er på hvert eneste sett (100 %), tett fulgt av grafteori og endelige automater og formelle språk (95 %), induksjon (91 %, og den tyngst vektede enkeltoppgaven – 20–30 poeng i årgangene 2017–2020), funksjoner (88 %), logikk (82 %) og kombinatorikk (77 %). Mengdelære er egen oppgave på to av tre sett og forutsettes ellers overalt. Rekursjon dukker opp som rekursivt definerte følger og mengder man skal bevise noe om – aldri som «løs rekurrenslikningen». Boolsk algebra var fast inventar i perioden 2017–2020, men har ikke vært på eksamen etter 2020. Klassisk tallteori (Euklids algoritme, lcm, Fermat, kinesisk restteorem) har aldri vært egen oppgave; delelighet og kongruens dukker i stedet opp inni induksjons- og relasjonsoppgavene.

Formatet er gjennomgående regning og bevis med begrunnelseskrav. Sensurdokumentene sier eksplisitt at riktig svar uten begrunnelse gir «middels trekk», og at feil metode (for eksempel en ikke-deterministisk automat når oppgaven ber om en deterministisk) gir «mye trekk». Flervalg finnes, men bare som korte innledende deloppgaver. Denne studieguiden er organisert etter de samme temaene som eksamensoppgavene bruker som overskrifter.

Mengdelære

Hyppig på eksamen

Mengder, delmengder, operasjoner, potensmengde og kartesisk produkt – og hvordan man beviser mengdelikheter ved gjensidig inklusjon.

Grunnbegreper

En mengde er en uordnet samling av distinkte elementer. Vi skriver $a \in A$ (a er element i A) og $A \subseteq B$ (A er delmengde av B, dvs. hvert element i A ligger i B). To mengder er like, $A = B$ , hvis og bare hvis $A \subseteq B$ og $B \subseteq A$ – dette dobbeltinklusjon-prinsippet er selve arbeidshesten i mengdebevis på eksamen.

Operasjoner

Med universalmengde $U$ har vi union $A \cup B$ , snitt $A \cap B$ , differanse $A - B = \{x \mid x \in A \wedge x \notin B\}$ , komplement $\overline{A} = U - A$ og symmetrisk differanse $A \triangle B = (A - B) \cup (B - A)$ . De Morgans lover binder mengdelære til logikk: $\overline{A \cup B} = \overline{A} \cap \overline{B}$ og $\overline{A \cap B} = \overline{A} \cup \overline{B}$ .

Potensmengde og kartesisk produkt

Potensmengden $\mathcal{P}(A)$ er mengden av alle delmengder av $A$ . Hvis $|A| = n$ , så er $|\mathcal{P}(A)| = 2^n$ (hvert element er enten med eller ikke med). Kartesisk produkt: $A \times B = \{(a,b) \mid a \in A, b \in B\}$ , med $|A \times B| = |A| \cdot |B|$ .

Partisjon

En partisjon av $A$ er en samling ikke-tomme, parvis disjunkte delmengder (blokker) hvis union er hele $A$ . Partisjoner kobler direkte til ekvivalensrelasjoner (se egen seksjon).

Eksempel (mengdelikhet ved dobbeltinklusjon). Vis at $A \times (B - C) = (A \times B) - (A \times C)$ .

« $\subseteq$ »: La $(x,y) \in A \times (B - C)$ . Da er $x \in A$ og $y \in B - C$ , altså $y \in B$ og $y \notin C$ . Så $(x,y) \in A \times B$ , men $(x,y) \notin A \times C$ (fordi $y \notin C$ ). Dermed $(x,y) \in (A \times B) - (A \times C)$ .

« $\supseteq$ »: La $(x,y) \in (A \times B) - (A \times C)$ . Da er $x \in A$ , $y \in B$ , og $(x,y) \notin A \times C$ . Siden $x \in A$ må $y \notin C$ . Altså $y \in B - C$ , og $(x,y) \in A \times (B - C)$ .

Begge inklusjoner gjelder, så mengdene er like. $\blacksquare$

Nøkkelformler

• $|\mathcal{P}(A)| = 2^{|A|}$
• $|A \times B| = |A| \cdot |B|$
•De Morgan: $\overline{A \cup B} = \overline{A} \cap \overline{B}$ , $\overline{A \cap B} = \overline{A} \cup \overline{B}$
• $A = B \iff A \subseteq B \wedge B \subseteq A$
•Antall ekte delmengder av en n-mengde: $2^n - 1$ ; antall ikke-tomme: $2^n - 1$

Vanlige feil

⚠️Forveksle «ekte delmengde» ( $A \subsetneq B$ ) med «delmengde» ( $A \subseteq B$ ); antall ekte delmengder av en n-mengde er $2^n - 1$ , ikke $2^n$ .
⚠️Bevise kun «én vei» av en mengdelikhet. Sensor krever begge inklusjoner (eller en ekvivalenskjede der hvert steg er reversibelt).
⚠️Glemme den tomme mengden når man lister delmengder eller blokker i en potensmengde.

Eksamenstips

💡Mengdelære er nesten alltid Oppgave 1. Forvent ett flervalgsspørsmål om kardinalitet/potensmengde, pluss et bevis ved dobbeltinklusjon.
💡Skriv beviset som en kjede av logiske ekvivalenser ( $\iff$ ) der det går – da slipper du å gjøre begge inklusjoner separat, men sjekk at hvert steg faktisk er reversibelt.
💡Oversett mengdeutsagn til logikk ( $\in \to \wedge/\vee$ ) for å bruke De Morgan og distributivitet trygt.

Laster...

Laster…