Introduksjon

TMA4412 Matematikk 2C: Diskret matematikk (NTNU, 7,5 sp) handler om logikk og bevis, mengder, funksjoner og relasjoner, induksjon og rekursjon, tallteori og kryptografi (RSA og diskrete logaritmer), kombinatorikk, grafer og trær og endelige tilstandsmaskiner med regulære uttrykk.

Viktig om emnekoden: TMA4412 viderefører TMA4140 Diskret matematikk, som ikke har undervisning lenger; siste TMA4140-eksamen var sommeren 2025. Stoffet er det samme, med diskrete logaritmer i tillegg. Eksamen i TMA4412 er torsdag 26. november 2026 kl. 09.00: 4 timer skriftlig skoleeksamen i Inspera, som teller 100 %. Hjelpemiddelkode D betyr ingen notater eller formelark, bare en bestemt, enkel kalkulator (for eksempel Casio FX-82CW eller fx-82ES PLUS). Alle formler og oppskrifter i denne guiden må du altså kunne utenat. Sjekk emnesiden før eksamen.

Eksamensformen: Emnesiden sier bare at skriftlig eksamen teller 100 %. I desember 2025 var settet todelt. Del 1 besto av fem oppgaver à 12 poeng som du skriver på ark med full begrunnelse, og sensor ga poeng per riktig steg. Del 2 var 20 korte oppgaver à 2 poeng i Inspera (tallsvar og ja/nei-valg), der bare svaret teller. Del 1 talte 60 % og Del 2 40 %. Kontinuasjonseksamen i august 2026 hadde ti skriftlige oppgaver à 10 poeng.

Guiden bygger på 22 eksamenssett fra 2015 til 2026: 20 TMA4140-sett (desember og august) og de to første TMA4412-settene (desember 2025 og august 2026), med NTNUs løsningsforslag og rettemal. Settene fra 2023 og senere veier tyngst, fordi de viser dagens form. NTNU har selv merket hvilke eldre oppgaver som fortsatt er relevante, og guiden følger den lista: regulære grammatikker, tilstandsmaskiner med utdata, bevis for at et språk ikke er regulært, boolsk algebra, normalformer og prefiks- og postfiksuttrykk er tatt ut av den, og de får derfor bare kort plass.

Hver seksjon starter med Slik testes dette på eksamen: hvor ofte temaet er med (for eksempel «i 22 av 22 sett»), hvor mange poeng det gir og hvordan spørsmålene er formulert. Deretter kommer stoffet og tre eksempler i eksamensform med egne tall, poeng og «Svar» til slutt. Fire ting har vært med i alle sju settene siden 2023: et induksjonsbevis, en tilstandsmaskin du skal konstruere, en telleoppgave og en oppgave om mengder, som oftest står helt først. RSA eller en annen kryptooppgave har vært med i seks av de sju.

Logikk og bevisteknikker

Eksamensrelevant

Logikk er med i 18 av 22 sett 2015–2026 og i alle 7 sett siden 2023. Kjernen er å avgjøre tautologi, motsigelse eller ingen av delene, vise eller avvise ekvivalens, og avgjøre og negere kvantorutsagn over et gitt univers.

Slik testes dette på eksamen

Logikk er med i 18 av 22 sett 2015–2026 og i alle 7 sett 2023–2026, med 5–20 % av poengene (desember 2025, TMA4412: 10 %). Formene:

Tautologi, motsigelse eller ingen av delene (10 sett): fem formler à 2 p i desember 2025 (TMA4412), Del 2 oppgave 4; fire formler i august 2026 (TMA4412), oppgave 4; «velg de to konstante formlene» i desember 2024, Del 1 oppgave 6b.
Ekvivalens og sannhetsverdier: avgjør om to formler er ekvivalente (august 2024, oppgave 3), finn verdiene som gjør en formel usann (desember 2024, Del 1 oppgave 5), tolk og forenkle en formel (sommer 2025, oppgave 5).
Kvantorer (8 sett): sannhetsverdi over et gitt univers (august 2026 (TMA4412), oppgave 7), tolkning i ord og negasjon med lovene (sommer 2025, oppgave 7).

Formelle modeller der et relasjonssymbol skal tolkes (desember 2023, oppgave 6b; desember 2024, Del 2 oppgave 5) og konjunktiv normalform (desember 2022, august 2023) er tatt ut av NTNUs liste over relevante eldre oppgaver. Bevisteknikkene testes inne i andre temaer, for eksempel motsigelsesbevis for at $\varphi(n) \neq 3$ (desember 2024, Del 2 oppgave 6d).

Sannhetstabell og implikasjonen

Med $n$ variabler har tabellen $2^n$ rader. Implikasjonen $p \to q$ er usann i nøyaktig én rad, og det gir omskrivingen bak nesten alle forenklinger:

$p \to q$ er 0 bare i raden $p = 1, q = 0$ .
$\lnot p \lor q$ er 0 bare når $\lnot p = 0$ og $q = 0$ , altså også bare i raden $p = 1, q = 0$ .
Kolonnene er like i alle fire rader, så $p \to q \equiv \lnot p \lor q$ .

Sannhetstabell med radene (p, q) = (1, 1), (1, 0), (0, 1), (0, 0) og kolonnene p → q = 1, 0, 1, 1, ¬p = 0, 0, 1, 1 og ¬p ∨ q = 1, 0, 1, 1. Cellen p → q = 0 er farget rød. — Kolonnene $p \to q$ og $\lnot p \lor q$ er like.

Med denne likheten og De Morgans lover $\lnot(p \land q) \equiv \lnot p \lor \lnot q$ og $\lnot(p \lor q) \equiv \lnot p \land \lnot q$ kan de fleste formler forenkles uten tabell. Vis på samme måte at $p \to q \equiv \lnot q \to \lnot p$ (kontrapositiv) og at $p \leftrightarrow q \equiv (p \to q) \land (q \to p)$ .

Rask test for tautologi: anta at formelen er usann og jobb innover. Er hovedkonnektivet $\to$ , må venstresida være sann og høyresida usann. En selvmotsigelse betyr tautologi; ellers har du en usann rad. Motsigelse vises tilsvarende. «Ingen av delene» krever to konkrete rader, én sann og én usann.

Ekvivalens: $F \equiv G$ når $F \leftrightarrow G$ er en tautologi. Vis det ved å omforme begge til samme uttrykk; avvis det med én rad der de er ulike. $G$ er en logisk konsekvens av $F$ når $F \to G$ er en tautologi (desember 2023, oppgave 6a). Finn radene der premisset er sant, og sjekk kandidatene bare der: $F = (p \lor q) \land \lnot p$ er sann bare for $p = 0, q = 1$ , så $q$ og $p \to q$ er konsekvenser, mens $p$ og $p \land q$ ikke er det.

Eksempel 1: Tautologi, motsigelse eller ingen av delene (Inspera, 4 × 2 p)

Klassifiser hver formel som tautologi, motsigelse eller ingen av delene.
a) $(p \land (p \to q)) \to q$
b) $(p \to q) \land (p \land \lnot q)$
c) $(p \lor q) \to (p \land q)$
d) $((p \to q) \land (q \to r)) \to (p \to r)$

a) Anta at formelen er usann. Da er $q = 0$ og $p \land (p \to q) = 1$ , altså $p = 1$ og $p \to q = 1$ . Men $p = 1, q = 0$ gir $p \to q = 0$ . Selvmotsigelse, så ingen rad er usann.
b) $p \to q \equiv \lnot(p \land \lnot q)$ , så formelen har formen $\lnot X \land X$ og er aldri sann.
c) $p = q = 1$ gir 1, mens $p = 1, q = 0$ gir $1 \to 0 = 0$ .
d) Anta usann: $p \to r = 0$ gir $p = 1, r = 0$ . Venstresida må være 1, så $p \to q = 1$ gir $q = 1$ , men da er $q \to r = 0$ . Selvmotsigelse.

Svar: a) tautologi, b) motsigelse, c) ingen av delene, d) tautologi.

Eksempel 2: Ekvivalens med lover og moteksempel (12 p)

a) Vis med logiske lover at $(p \to q) \land (p \to r) \equiv p \to (q \land r)$ . (5 p)
b) Er $(p \to q) \to r$ ekvivalent med $p \to (q \to r)$ ? Begrunn. (4 p)
c) For hvilke sannhetsverdier er $\lnot(p \to (q \lor r))$ sann? (3 p)

a) Skriv om begge implikasjonene: $(\lnot p \lor q) \land (\lnot p \lor r)$ .
Den distributive loven baklengs gir $\lnot p \lor (q \land r)$ .
Tilbake til implikasjon: $p \to (q \land r)$ . Venstre side er omformet til høyre side, så de er ekvivalente.
b) Prøv $p = q = r = 0$ . Venstre: $p \to q = 1$ , så $1 \to 0 = 0$ . Høyre: $0 \to (q \to r) = 1$ .
Formlene har ulik verdi i denne raden og er derfor ikke ekvivalente.
c) Negasjonen er sann når $p \to (q \lor r)$ er usann, det vil si $p = 1$ og $q \lor r = 0$ .
$q \lor r = 0$ krever $q = r = 0$ .

Svar: a) Ekvivalente (steg 1–3). b) Nei: raden $p = q = r = 0$ gir 0 mot 1. c) Bare for $p = 1$ , $q = 0$ , $r = 0$ .

Kvantorer

$\forall x\, P(x)$ er sann når $P(x)$ holder for hvert element i universet; ett moteksempel gjør den usann. $\exists x\, P(x)$ er sann når ett vitne finnes. Rekkefølgen betyr noe: i $\forall x\, \exists y$ kan $y$ avhenge av $x$ , i $\exists y\, \forall x$ må én og samme $y$ virke for alle $x$ . Over $\mathbb{Z}$ er $\forall x\, \exists y\,(y \gt x)$ sann ( $y = x + 1$ ), men $\exists y\, \forall x\,(y \gt x)$ usann.

Negasjon: $\lnot \forall x\, P(x) \equiv \exists x\, \lnot P(x)$ og $\lnot \exists x\, P(x) \equiv \forall x\, \lnot P(x)$ . Flytt negasjonen ett steg innover om gangen, og neger til slutt selve predikatet: $\lt$ blir $\ge$ , $=$ blir $\neq$ , og $\land$ blir $\lor$ med De Morgan.

Kjede av tre bokser: ¬∀x ∃y P(x, y), pil «¬∀ blir ∃¬» til ∃x ¬∃y P(x, y), pil «¬∃ blir ∀¬» til ∃x ∀y ¬P(x, y). — Negasjonen vandrer innover og snur hver kvantor den passerer.

Eksempel 3: Kvantorer over heltallene (12 p)

Universet er $\mathbb{Z}$ .
a) Avgjør sannhetsverdien til i) $\forall x\, \exists y\,(x + y = 0)$ , ii) $\exists y\, \forall x\,(xy = x)$ , iii) $\forall x\, \exists y\,(2y = x)$ , iv) $\exists x\, \forall y\,(x \le y^2)$ . (6 p)
b) Skriv negasjonen av iii) uten negasjon foran en kvantor, og si hva den betyr i ord. (3 p)
c) Hvilke av i)–iv) skifter sannhetsverdi hvis universet byttes til $\mathbb{Q}$ ? (3 p)

i) Gitt $x$ , velg $y = -x \in \mathbb{Z}$ . Da er $x + y = 0$ . Sann.
ii) Vitnet $y = 1$ gir $x \cdot 1 = x$ for alle $x$ . Sann.
iii) Moteksempel $x = 1$ : $2y = 1$ gir $y = \tfrac12 \notin \mathbb{Z}$ . Usann.
iv) Vitnet $x = 0$ : $0 \le y^2$ for alle $y$ . Sann.
b) $\lnot \forall x\, \exists y\,(2y = x)$ blir først $\exists x\, \lnot \exists y\,(2y = x)$ og så $\exists x\, \forall y\,(2y \neq x)$ : det finnes et heltall som ikke er det dobbelte av noe heltall. Sann ( $x = 1$ ).
c) I $\mathbb{Q}$ har $2y = x$ løsningen $y = x/2 \in \mathbb{Q}$ , så iii) blir sann. Vitnene i i), ii) og iv) er fortsatt rasjonale.

Svar: a) i) sann, ii) sann, iii) usann, iv) sann. b) $\exists x\, \forall y\,(2y \neq x)$ , som er sann. c) Bare iii), som blir sann.

Bevisteknikker

Skriv hvilken metode du bruker og hva du antar.

«Vis at p → q» med piler til Direkte (anta p, utled q), Kontrapositivt (anta ¬q, utled ¬p) og Motsigelse (anta p og ¬q, finn en motsigelse). — Motsigelse bygger på $\lnot(p \to q) \equiv p \land \lnot q$ .

Direkte: $n = 2k + 1$ gir $n^2 = 2(2k^2 + 2k) + 1$ , som er odde.
Kontrapositivt: påstand: er $n^2 + 5$ odde, så er $n$ et partall. Anta $n$ odde. Da er $n^2$ odde (punkt 1) og $n^2 + 5$ et partall: $\lnot q \to \lnot p$ .
Motsigelse: $6x + 9y = 100$ har ingen heltallsløsning. Anta at heltall $x, y$ løser den. Da deler 3 venstresida $3(2x + 3y)$ , men ikke 100. Motsigelse.

Tips: «Vis at påstanden ikke holder» besvares med ett konkret moteksempel regnet ut med tall.

Nøkkelformler

• $p \to q \equiv \lnot p \lor q$ — implikasjonen skrevet om; usann bare for $p = 1, q = 0$
• $p \to q \equiv \lnot q \to \lnot p$ — kontrapositiv, grunnlaget for kontrapositivt bevis
• $\lnot(p \land q) \equiv \lnot p \lor \lnot q$ og $\lnot(p \lor q) \equiv \lnot p \land \lnot q$ — De Morgans lover
• $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$ — distributiv lov (også med $\land$ og $\lor$ byttet om)
• $\lnot \forall x\, P(x) \equiv \exists x\, \lnot P(x)$ — negasjon av allkvantor
• $\lnot \exists x\, P(x) \equiv \forall x\, \lnot P(x)$ — negasjon av eksistenskvantor
• $F \equiv G$ når $F \leftrightarrow G$ er en tautologi — definisjonen av ekvivalens

Vanlige feil

⚠️Å tro at $p \to q$ er usann når $p$ er usann. En implikasjon med usann premiss er alltid sann.
⚠️Å bytte $\forall x\, \exists y$ med $\exists y\, \forall x$ . Den første lar $y$ avhenge av $x$ , den andre krever én felles $y$ .
⚠️Å negere $x \lt y$ til $x \gt y$ . Riktig negasjon er $x \ge y$ .
⚠️Å forveksle den omvendte $q \to p$ med den kontrapositive $\lnot q \to \lnot p$ .
⚠️Å svare «tautologi» etter å ha sjekket noen få rader. Påstanden gjelder alle $2^n$ rader.

Eksamenstips

💡For tautologi: anta at formelen er usann og jobb innover. En selvmotsigelse betyr tautologi, og det går raskere enn en tabell med åtte rader.
💡«Ingen av delene» begrunnes med to konkrete rader: én som gir sann og én som gir usann.
💡For kvantorer: oppgi vitnet ( $\exists$ ) eller moteksempelet ( $\forall$ ) med tall. Inspera-delen gir ingen delpoeng, den skriftlige delen gir poeng for begrunnelsen.
💡Ved negasjon: flytt $\lnot$ ett steg om gangen og skriv hvert steg. Sluttsvaret skal ikke ha $\lnot$ foran en kvantor.

Laster...

Studieguide for TMA4412 Matematikk 2C: Diskret matematikk