Komplett pensumoversikt for diskret matematikk ved NTNU — med forklaringer, sentrale begreper, eksamenstips og vanlige fallgruver. Eksamensoptimalisert basert på tidligere eksamener.
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 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.
Et utsagn er en setning som er enten sann (T) eller usann (F). Sammensatte utsagn bygges med konnektivene (ikke), (og), (eller), (impliserer) og (hvis og bare hvis). En sannhetstabell med variabler har rader. En tautologi er sann i alle rader, en motsigelse usann i alle rader, og en kontingens er verken.
Sentrale ekvivalenser:
Implikasjon:
Kontrapositiv:
De Morgan: ,
Distributiv:
Bikondisjonal:
To utsagn er logisk ekvivalente () når de har samme sannhetsverdi i alle rader, ekvivalent med at er en tautologi. Husk at det omvendte IKKE er ekvivalent med , men kontrapositivet er det.
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 fra sannhetstabellen.
En slutning er gyldig hvis det er umulig at premissene er sanne og konklusjonen usann samtidig — ekvivalent med at er en tautologi.
Gyldige slutningsregler:
Modus ponens:
Modus tollens:
Hypotetisk syllogisme:
Disjunktiv syllogisme:
Feilslutninger (ugyldige): affirming the consequent () og denying the antecedent ().
De fire kjernemetodene har hver sin eksplisitte struktur. Direkte: anta , utled . Kontrapositiv: bevis . Motsigelse: anta , utled en umulighet. Element-argument: for , ta vilkårlig og vis .
Eksempel 2: Bevis ved kontrapositiv: «Hvis er partall, så er partall».
Eksempel 3: Element-argument for .
Predikater blir utsagn først når bindes av en kvantor. («for alle») og («det finnes minst én»).
Kvantor-negasjon:
Oversettelse: med implikasjon: . med konjunksjon: .
Rekkefølge: er sterkere enn og er ikke ekvivalent.
Nøkkelformler
Vanlige feil
Eksamenstips
Laster...