TMA4140 · NTNU

Studieguide for TMA4140 Diskret matematikk

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

Introduksjon

Denne studieguiden dekker TMA4140 Diskret matematikk ved NTNU, forankret i tidligere eksamener. Hver seksjon gir forklaringer, gjennomgåtte eksempler med eksplisitt bevisstruktur, nøkkelformler, vanlige feil og eksamenstips.

Logikk og bevisteknikker

Eksamensrelevant

Logikk og bevisteknikker er fundamentet for hele TMA4140 og for matematikk generelt. Du må mestre utsagnslogikk (sannhetstabeller, tautologi/motsigelse, logiske ekvivalenser inkl. De Morgan og kontrapositiv), normalformer (CNF/DNF og hvordan de leses fra sannhetstabeller), gyldige slutningsregler (modus ponens/tollens, syllogismer) versus klassiske feilslutninger, de fire kjernebevismetodene (direkte, kontrapositiv, motsigelse, element-argument) med eksplisitt struktur, samt predikatlogikk med kvantorer, kvantor-negasjon og oversettelse mellom naturlig språk og formler.

Utsagnslogikk og sannhetstabeller

Et utsagn er en setning som er enten sann (T) eller usann (F). Sammensatte utsagn bygges med konnektivene $\neg$ (ikke), $\land$ (og), $\lor$ (eller), $\rightarrow$ (impliserer) og $\leftrightarrow$ (hvis og bare hvis). En sannhetstabell med $n$ variabler har $2^n$ rader. En tautologi er sann i alle rader, en motsigelse usann i alle rader, og en kontingens er verken.

Sentrale ekvivalenser:

Implikasjon: $p \rightarrow q \equiv \neg p \lor q$

Kontrapositiv: $p \rightarrow q \equiv \neg q \rightarrow \neg p$

De Morgan: $\neg(p \land q) \equiv \neg p \lor \neg q$ , $\neg(p \lor q) \equiv \neg p \land \neg q$

Distributiv: $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$

Bikondisjonal: $p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)$

To utsagn er logisk ekvivalente ( $P \equiv Q$ ) når de har samme sannhetsverdi i alle rader, ekvivalent med at $P \leftrightarrow Q$ er en tautologi. Husk at det omvendte $q \rightarrow p$ IKKE er ekvivalent med $p \rightarrow q$ , men kontrapositivet $\neg q \rightarrow \neg p$ er det.

Normalformer: CNF og DNF

En literal er en variabel eller dens negasjon. DNF (disjunktiv normalform) er en OR av AND-termer; CNF (konjunktiv normalform) er en AND av OR-klausuler. CNF er sentral i SAT-løsing fordi en formel er tilfredsstillbar nettopp når hver klausul har minst én sann literal.

Eksempel 1: Finn DNF og CNF for $p \leftrightarrow q$ fra sannhetstabellen.

Sannhetstabell:

p \leftrightarrow q

er sann i radene (T,T) og (F,F), usann i (T,F) og (F,T).

DNF (les sann-radene som mintermer): (T,T) gir

(p \land q)

; (F,F) gir

(\neg p \land \neg q)

DNF:

(p \land q) \lor (\neg p \land \neg q)

CNF (les usann-radene som maxtermer): (T,F) gir

(\neg p \lor q)

; (F,T) gir

(p \lor \neg q)

CNF:

(\neg p \lor q) \land (p \lor \neg q)

Gyldige slutninger og feilslutninger

En slutning er gyldig hvis det er umulig at premissene er sanne og konklusjonen usann samtidig — ekvivalent med at $(P_1 \land \cdots \land P_n) \rightarrow Q$ er en tautologi.

Gyldige slutningsregler:

Modus ponens: $p,\; p \rightarrow q \;\therefore\; q$

Modus tollens: $\neg q,\; p \rightarrow q \;\therefore\; \neg p$

Hypotetisk syllogisme: $p \rightarrow q,\; q \rightarrow r \;\therefore\; p \rightarrow r$

Disjunktiv syllogisme: $p \lor q,\; \neg p \;\therefore\; q$

Feilslutninger (ugyldige): affirming the consequent ( $q, p\rightarrow q \therefore p$ ) og denying the antecedent ( $\neg p, p\rightarrow q \therefore \neg q$ ).

Bevismetoder

De fire kjernemetodene har hver sin eksplisitte struktur. Direkte: anta $p$ , utled $q$ . Kontrapositiv: bevis $\neg q \rightarrow \neg p$ . Motsigelse: anta $\neg P$ , utled en umulighet. Element-argument: for $A \subseteq B$ , ta vilkårlig $x \in A$ og vis $x \in B$ .

Eksempel 2: Bevis ved kontrapositiv: «Hvis $n^2$ er partall, så er $n$ partall».

Kontrapositivet er: «Hvis

n

er oddetall, så er

n^2

oddetall».

Anta

n

er oddetall:

n = 2k+1

for et heltall

k

n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1

Dette har formen

2m+1

, altså et oddetall. Kontrapositivet er bevist.

Siden kontrapositivet er ekvivalent med originalen, følger påstanden.

Eksempel 3: Element-argument for $A \cap B \subseteq A \cup B$ .

x \in A \cap B

være vilkårlig.

Per definisjon av snitt:

x \in A

x \in B

Spesielt

x \in A

, så per definisjon av union

x \in A \cup B

Siden

x

var vilkårlig, gjelder

A \cap B \subseteq A \cup B

Predikatlogikk og kvantorer

Predikater $P(x)$ blir utsagn først når $x$ bindes av en kvantor. $\forall x\,P(x)$ («for alle») og $\exists x\,P(x)$ («det finnes minst én»).

Kvantor-negasjon:

$\neg \forall x\,P(x) \equiv \exists x\,\neg P(x)$

$\neg \exists x\,P(x) \equiv \forall x\,\neg P(x)$

Oversettelse: $\forall$ med implikasjon: $\forall x\,(S(x) \rightarrow P(x))$ . $\exists$ med konjunksjon: $\exists x\,(S(x) \land P(x))$ .

Rekkefølge: $\exists y \forall x\,P(x,y)$ er sterkere enn $\forall x \exists y\,P(x,y)$ og er ikke ekvivalent.

Nøkkelformler

• $p \rightarrow q \equiv \neg p \lor q$
• $p \rightarrow q \equiv \neg q \rightarrow \neg p$ (kontrapositiv)
• $\neg(p \land q) \equiv \neg p \lor \neg q$ og $\neg(p \lor q) \equiv \neg p \land \neg q$ (De Morgan)
• $p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)$
•Antall rader i sannhetstabell $= 2^n$
• $\neg(p \rightarrow q) \equiv p \land \neg q$
• $\neg \forall x\,P(x) \equiv \exists x\,\neg P(x)$
• $\neg \exists x\,P(x) \equiv \forall x\,\neg P(x)$
•Modus ponens: $p,\; p\rightarrow q \;\therefore\; q$ ; Modus tollens: $\neg q,\; p\rightarrow q \;\therefore\; \neg p$

Vanlige feil

⚠️Forveksle kontrapositivet ( $\neg q \rightarrow \neg p$ , ekvivalent) med det omvendte ( $q \rightarrow p$ , IKKE ekvivalent).
⚠️Begå feilslutningene affirming the consequent ( $q, p\rightarrow q \therefore p$ ) eller denying the antecedent ( $\neg p, p\rightarrow q \therefore \neg q$ ) — begge ugyldige.
⚠️Bruke $\land$ i stedet for $\rightarrow$ ved oversettelse av «alle» ( $\forall x(S(x)\land P(x))$ sier feilaktig at alt er en student).
⚠️Bruke $\rightarrow$ i stedet for $\land$ ved oversettelse av «noen» ( $\exists x(S(x)\rightarrow P(x))$ blir trivielt sant).
⚠️Bytte rekkefølge på kvantorer av ulik type — $\forall x \exists y$ og $\exists y \forall x$ er ikke ekvivalente.
⚠️Glemme at $p \rightarrow q$ er sann når $p$ er usann (vacuously true), og dermed feillese sannhetstabellen.
⚠️I motsigelsesbevis: glemme å eksplisitt utlede en faktisk motsigelse ( $r \land \neg r$ ) før man konkluderer.
⚠️Forveksle DNF (OR av AND) og CNF (AND av OR), eller lese feil rader fra sannhetstabellen (sann-rader for DNF, usann-rader for CNF).

Eksamenstips

💡Skriv alltid bevisstrukturen eksplisitt: oppgi hvilken metode (direkte/kontrapositiv/motsigelse/element-argument) og marker «Anta...», «Utled...», «Konkluder...».
💡Ved «vis at X er en tautologi/ekvivalens» kan du enten lage full sannhetstabell ELLER bruke kjede av kjente ekvivalenser — oppgi hvilken lov du bruker i hvert steg.
💡For å motbevise et $\forall$ -utsagn holder det med ETT konkret moteksempel; for å motbevise et $\exists$ -utsagn må du vise at $\neg P$ gjelder for alle.
💡Ved kvantor-negasjon: flytt $\neg$ innover steg for steg, bytt hver kvantor, og bruk $\neg(P\rightarrow Q)\equiv P\land\neg Q$ for implikasjoner inni.
💡Velg kontrapositiv når $\neg q$ gir et mer konkret utgangspunkt enn $p$ (typisk ved partall/oddetall-påstander).
💡Når du leser CNF/DNF fra en sannhetstabell: husk DNF fra sann-radene (mintermer), CNF fra usann-radene (maxtermer) — og dobbeltsjekk med én rad.
💡For mengdebevis: bruk dobbel inklusjon for likhet, og start alltid element-argument med «La $x$ være vilkårlig».

Laster...

Laster…