•Antall DFA-er med \(m\) tilstander over alfabet med \(k\) symboler, gitt start: \(m^{mk}\cdot 2^{m}\) (fritt \(F\))
Vanlige feil å unngå
Logikk og bevisteknikker
•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).
Mengdelære
•Glemmer at \(\mathbb{N}\) inkluderer 0 i denne kursets konvensjon — derfor utelates 0 feilaktig i komplement og mengdebygger-uttrykk.
•Forveksler \(\in\) (medlemskap) med \(\subseteq\) (delmengde), f.eks. tror at \(\{x\}\in A\) og \(\{x\}\subseteq A\) betyr det samme.
•Glemmer \(\emptyset\) når man lister potensmengden, slik at man får \(2^n-1\) i stedet for \(2^n\) elementer.
•Behandler kartesisk produkt som kommutativt: \(\langle a,b\rangle\) og \(\langle b,a\rangle\) er forskjellige par.
•Glemmer å trekke fra snittet ved telling av union (dobbelttelling) — bruk inklusjon–eksklusjon.
•I element-argumenter begrunnes ikke hvert steg; man hopper over hvilken definisjon eller logiske ekvivalens (de Morgan) som rettferdiggjør overgangen.
•Tror \(\{\emptyset\}\) er den tomme mengden — den har faktisk ett element.
Funksjoner
•Forveksle injektiv og surjektiv, eller bytte om retningen i injektivitetsbeviset (man starter fra \(f(a_1)=f(a_2)\), ikke fra \(a_1=a_2\)).
•Glemme at surjektivitet avhenger av kodomenet: \(f(x)=x^2\) er surjektiv \(\mathbb{R}\to[0,\infty)\) men ikke \(\mathbb{R}\to\mathbb{R}\).
•Behandle \(f^{-1}(T)\) som om \(f\) må være inverterbar — urbildet er alltid definert.
•Regne gulv av negative tall feil: \(\lfloor -2.3\rfloor=-3\), ikke \(-2\).
•Anta at komposisjon kommuterer: \(f\circ g\neq g\circ f\) generelt, og \((g\circ f)^{-1}=f^{-1}\circ g^{-1}\) (rekkefølgen snus).
•Forveksle invers funksjon \(f^{-1}\) med resiprok \(1/f\).
Relasjoner
•Forveksle "ikke refleksiv" med "irrefleksiv" — en relasjon kan vaere verken refleksiv eller irrefleksiv.
•Tro at symmetrisk og antisymmetrisk er motsetninger. En relasjon kan vaere begge (kun diagonale par) eller ingen av delene.
•Glemme aa sjekke transitivitet for alle stier av lengde 2, inkludert de som gaar via et element tilbake til seg selv (f.eks. \(a\to b\to a\) krever \(\langle a,a\rangle\)).
•Blande sammen ekvivalensrelasjon (RST) og partiell ordning (RAT) — symmetri vs. antisymmetri er forskjellen.
•Tegne refleksive looper eller transitive snarveier i Hasse-diagram — kun dekkrelasjonen skal med.
•Forveksle minimalt/maksimalt (lokalt) med minste/stoerste (globalt). Det kan finnes flere minimale uten et minste element.
•Bruke vanlig matriseprodukt i stedet for boolsk produkt naar man regner stier (sum skal vaere OR, ikke +).
•Paastaa at \(\le\) er en ekvivalensrelasjon — den er ikke symmetrisk, men en (total) ordning.
Induksjon og rekursjon
•Bruke bare ett basistilfelle for en andreordens rekurrens. Steget refererer to ledd bakover og er ubrukelig før begge er etablert.
•Fortegnsfeil i den karakteristiske ligningen: koeffisientene skal flyttes over med MOTSATT fortegn.
•Bruke ansatsen A·rⁿ + B·rⁿ ved dobbel rot. Den har bare én fri konstant og kan ikke tilfredsstille to vilkårlige startverdier — riktig ansats er (A + Bn)rⁿ.
•Bestemme A og B før man har funnet røttene, eller glemme å sette inn startverdiene i det hele tatt.
•Sjekke bare startverdiene og ikke rekurrensen (eller motsatt). Begge kontrollene trengs.
•Skrive «anta at P(n) er sann for alle n» i induksjonshypotesen — da har man antatt det man skal bevise. Anta P(k) for ET vilkårlig k.
•Hoppe over konklusjonen. Uten «etter induksjonsprinsippet gjelder P(n) for alle n ≥ n₀» er beviset formelt uferdig.
•Bruke karakteristisk ligning på en ikke-homogen rekurrens uten å legge til en partikulærløsning.
Tallteori og modulær aritmetikk
•Forveksle hvilket tall som er divisor i \(a \mid b\): det betyr \(b = ak\), ikke \(a = bk\).
•Glemme å sjekke at \(\gcd(a,n) \mid b\) før man løser \(ax \equiv b \pmod n\), og dermed overse at det enten finnes flere løsninger eller ingen.
•Anta at en modulær invers alltid finnes — den finnes bare når \(\gcd(a,n) = 1\).
•Kansellere en felles faktor i en kongruens uten å justere modulen: korrekt er \(a \equiv b \pmod{n/\gcd(c,n)}\).
•Bruke CRT når modulene ikke er parvis innbyrdes primiske; da gjelder ikke entydighetsgarantien.
•Erstatte eksponenter med kongruente tall: \(a \equiv b \pmod n\) gir IKKE \(a^c \equiv a^d\) selv om \(c \equiv d \pmod n\); eksponenter reduseres modulo \(p-1\) (Fermat), ikke modulo \(n\).
•Regnefeil i bakoversubstitusjonen ved utvidet Euklid — kontroller alltid at \(sa + tn = \gcd\) faktisk stemmer.
•Glemme å normalisere en negativ invers/Bézout-koeffisient til intervallet \([0,n)\).
RSA og kryptografi
•Bruke \(\varphi(mn)=\varphi(m)\varphi(n)\) uten å sjekke at \(\gcd(m,n)=1\) — formelen gjelder kun for relativt primiske faktorer.
•Forveksle modulus for invers: \(d\) er invers til \(e\) modulo \(\varphi(N)\), IKKE modulo \(N\).
•Velge \(e\) som deler \(\varphi(N)\) (f.eks. \(e=5\) når \(5\mid\varphi(N)\)) — da finnes ingen \(d\) fordi \(\gcd(e,\varphi(N))\neq1\).
•Glemme å redusere modulo \(n\) underveis i gjentatt kvadrering, slik at tallene vokser unødvendig.
•Ta feil binærsiffer i eksponenten, eller multiplisere inn kvadrater som svarer til 0-bit.
•Tro at RSA alltid er sikkert — overse at \(p\approx q\) gjør Fermat trivielt, og at \(e=3\) uten polstring åpner for Håstad/kubikkrot-angrep.
•Ved Fermat: starte med \(a=\lfloor\sqrt N\rfloor\) i stedet for \(\lceil\sqrt N\rceil\), slik at \(a^2-N\) blir negativ.
Kombinatorikk
•Forveksle permutasjon og kombinasjon — sjekk alltid om rekkefølgen faktisk teller før du velger formel.
•Bruke sumregelen på overlappende mengder. Sumregelen krever disjunkthet; ved overlapp må inklusjon-eksklusjon brukes.
•Glemme å dele på fakultetene ved gjentatte elementer i en multimengde-permutasjon (f.eks. \(\frac{11!}{4!\,4!\,2!}\) for MISSISSIPPI).
•Bruke \(n^k\) når elementer ikke kan gjentas, eller \(P(n,k)\) når de kan — bland ikke med/uten tilbakelegging.
•Telle ordnede arrangementer dobbelt ved umerkede grupper (f.eks. dele 8 personer i to umerkede lag på 4: husk å dele på 2).
•Forsøke å telle 'minst én' direkte med mange tilfeller i stedet for å bruke komplementtelling (totalt minus 'ingen').
•I stars and bars: forveksle antall variabler \(n\) og antall enheter \(k\); formelen er \(\binom{n+k-1}{k}\) der barene er \(n-1\).
Grafteori
•Blande Euler og Hamilton: Euler handler om KANTER (hver kant én gang), Hamilton om NODER (hver node én gang).
•Tro at det finnes et enkelt gradkriterium for Hamilton slik som for Euler — det gjør det IKKE (NP-komplett).
•Bruke Dirac/Ore som NØDVENDIG betingelse. De er bare TILSTREKKELIGE: en graf kan ha Hamilton-sykel selv om Dirac ikke er oppfylt.
•Anta at lik gradsekvens beviser isomorfi. Det er nødvendig, men ikke tilstrekkelig (f.eks. \(C_6\) vs \(C_3\cup C_3\)).
•Telle kanter feil fra nabomatrise: glemme å dele elementsummen på 2 for uretttede grafer.
•Forveksle Euler-VEI og Euler-KRETS: to oddenoder gir åpen vei (ikke krets), null oddenoder gir krets.
•Glemme sammenhengskravet: Euler-kriteriet forutsetter at grafen (med kanter) er sammenhengende.
Trær
•Forveksle «fullt» (hver intern node har m barn) med «komplett/perfekt» (alle blader på samme nivå).
•Glemme at roten regnes med i n = mi + 1 — formelen teller alle barn (mi) pluss roten.
•Bruke feil maks-nodeformel: korrekt er 2^(h+1)-1 for binært tre med høyde h, ikke 2^h - 1 (det er antall interne i et perfekt tre).
•Bytte om inorden og preorden: husk at inorden = venstre-ROT-høyre gir infiks, preorden = ROT-venstre-høyre gir prefiks.
•Evaluere prefiks fra venstre mot høyre — prefiks evalueres enklest fra høyre mot venstre (eller rekursivt).
•Tro at ethvert usyklisk graf er et tre — en usyklisk graf må også være sammenhengende; ellers er den bare en skog.
•I induksjonsbeviset fjerne roten i stedet for et blad — fjerning av roten kan dele treet i flere komponenter; fjern alltid et blad.
Endelige tilstandsmaskiner og formelle språk
•Kalle en grammatikk regulær selv om en produksjon har terminaler på begge sider av ikke-terminalen (f.eks. S → 0S1). Da er den kontekstfri, ikke regulær.
•Glemme λ-produksjonene når man oversetter automat → grammatikk. Uten A_i → λ for aksepttilstandene genererer grammatikken ingenting.
•Tro at NFA-er gjenkjenner flere språk enn DFA-er. De gjenkjenner nøyaktig de samme; forskjellen er antall tilstander.
•Kreve at ALLE kjøringer i en NFA skal ende i F. Det holder at én gjør det.
•Lage en ufullstendig overgangsfunksjon i en DFA. f må være total — bruk en eksplisitt felletilstand.
•Anta at et uendelig språk ikke kan være regulært. 0* er uendelig og regulært; det avgjørende er om hukommelsen må være ubegrenset.
•I ikke-regularitetsbevis: velge halen FØR man vet hvilke to prefikser som kolliderer. Halen må velges etter at i og j er gitt.
•Glemme at A* og A⁰ inneholder λ, eller forveksle A* (null eller flere) med A⁺ (én eller flere).
•Tro at a*b* = (a∪b)*. I a*b* må alle a-er komme før alle b-er.
•I en Mealy-maskin med mønstergjenkjenning: gå tilbake til starttilstanden etter et treff. Selv-overlappende mønstre (som 101) mister da treff.
Boolsk algebra
•Bruke heltallsregning: skrive \(1+1=2\) i stedet for \(1+1=1\). I boolsk algebra er \(+\) idempotent ELLER, ikke addisjon.
•Glemme at join distribuerer over meet: \(x+yz=(x+y)(x+z)\) gjelder i boolsk algebra, men IKKE i vanlig tallaritmetikk.
•Feil De Morgan: tro at \(\overline{x+y}=\overline{x}+\overline{y}\). Riktig er \(\overline{x+y}=\overline{x}\,\overline{y}\) (operasjonen bytter).
•Hevde at ethvert delelighetsgitter \(D_n\) er boolsk. Det krever at \(n\) er kvadratfri; \(D_{12}\) feiler fordi 6 og 2 mangler komplement.
•Forveksle hvilket element som er null og enhet i \(\mathcal{P}(S)\): null \(=\emptyset\), enhet \(=S\) (ikke omvendt).
•Tro at det finnes en boolsk algebra med 3 elementer. Endelige boolske algebraer har alltid \(2^k\) elementer.
•Glemme \(x\overline{x}=0\) (ikke \(x\)) og \(x+\overline{x}=1\) (ikke \(\overline{x}\)) under forenkling.
•Behandle boolsk \(+\) som om den hadde en invers ("\(-x\)"); idempotens \(x+x=x\) gjør at additive inverser ikke finnes.
Eksamenstips
Logikk og bevisteknikker
•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».
Mengdelære
•Skriv element-argumenter eksplisitt: «La \(x\) være vilkårlig med \(x\in\dots\)», og avslutt med «siden \(x\) var vilkårlig …». Marker hvert steg med begrunnelse.
•Bruk en kjede av \(\Leftrightarrow\) når du kan — da viser du begge inklusjoner samtidig og sparer tid.
•Når du teller delmengder eller union, vurder alltid produktregel (\(2^n\), \(3^n\)) og inklusjon–eksklusjon før du teller for hånd.
•Tegn et Venn-diagram som sjekk/intuisjon, men husk at et diagram alene IKKE er et gyldig bevis — element-argument kreves.
•Dobbeltsjekk grensetilfeller: \(\emptyset\), \(\mathcal{P}(\emptyset)=\{\emptyset\}\), \(A\times\emptyset=\emptyset\), og at 0 er med i \(\mathbb{N}\).
•Når oppgaven sier «vis at», forventes et fullt bevis med struktur; «beregn» forventer eksplisitt mengde/tall med mellomregning.
Funksjoner
•Skriv bevisene med eksplisitt struktur: «Anta …», utledning, «derfor …». Sensor ser etter at du starter i riktig ende.
•Ved «vis at \(f\) er bijektiv» — del beviset tydelig i en injektiv- og en surjektiv-del; finn gjerne inversen som bonus.
•For å motbevise injektiv/surjektiv: ett konkret moteksempel er nok og raskest.
•Husk konvensjonen \(\mathbb{N}=\{0,1,2,\dots\}\) i dette emnet når du teller eller velger urbilder.
•Ved gulv/tak-identiteter: start med ulikheten \(\lfloor x\rfloor\leq x<\lfloor x\rfloor+1\) og manipuler — dette løser nesten alle slike oppgaver.
•Tegn piledagram ved tvil om injektiv/surjektiv på små endelige mengder — rask visuell kontroll.
•Ved tellingsoppgaver: avgjør først om det er alle funksjoner (\(n^m\)), injeksjoner (\(P(n,m)\)) eller surjeksjoner (inklusjon-eksklusjon).
Relasjoner
•Skriv alltid eksplisitt hvilken bevismetode du bruker (element-argument for egenskaper), og sjekk hver egenskap separat med klar konklusjon.
•For aa vise at en egenskap IKKE holder, gi et konkret moteksempel med spesifikke elementer — det er raskere enn generelle argument.
•Naar du beviser at noe er en ekvivalensrelasjon, gaa systematisk gjennom R, S og T hver for seg; for partiell ordning gjennom R, A og T.
•Ved \(f(a)=f(b)\)-relasjoner: poengter at RST arves fra likhet — det gir full uttelling raskt uten lange utregninger.
•Tegn Hasse-diagram nedenfra og opp: finn minimale elementer foerst, deretter dekkrelasjoner lag for lag. Dobbeltsjekk at ingen transitiv kant er tegnet.
•Husk Bell-tallene \(B_3=5, B_4=15\) for tellespoersmaal om antall ekvivalensrelasjoner/partisjoner.
•Bruk matriserepresentasjonen som rask sjekkliste: diagonal for refleksiv, \(M=M^T\) for symmetrisk, sammenlign \(M\odot M\) med \(M\) for transitiv.
Induksjon og rekursjon
•Skriv bevisstrukturen eksplisitt med overskrifter: «Basistilfelle», «Induksjonshypotese», «Induksjonssteg», «Konklusjon». Det gir delpoeng selv ved regnefeil.
•Marker tydelig HVOR du bruker induksjonshypotesen (skriv «etter IH»). Sensor leter etter dette.
•Rekurrensoppgaver av typen «hva er a_n?» har vært en fast flervalgspost på nesten alle sett med svarkupong (2013–2021). Da skal du løse med karakteristisk ligning, ikke iterere 15 ledd for hånd — men iterer gjerne to ledd som kontroll.
•Faktoriser den karakteristiske ligningen i stedet for å bruke abc-formelen: røttene er nesten alltid små heltall. Ved tredje grad: test divisorene av konstantleddet først.
•Pass på fortegn: a_n = c₁a_{n-1} + c₂a_{n-2} gir x² − c₁x − c₂ = 0. Rekurrensen a_n = −3a_{n-1} + 10a_{n-2} gir x² + 3x − 10 = 0.
•Kontroller alltid en lukket form med både startverdiene og ett ekstra ledd fra rekurrensen — startverdiene alene fanger ikke feil røtter.
•Ved ulikheter: finn først den minste n der ulikheten begynner å gjelde, og bruk den som basistilfelle. Oppgaven ber ofte om nettopp dette først.
Tallteori og modulær aritmetikk
•Skriv hvert steg i Euklids algoritme på linjen \(a = qb + r\); det gjør bakoversubstitusjonen for Bézout rett frem.
•Kontroller alltid en invers: \(a\cdot a^{-1}\) skal gi rest 1 modulo \(n\). Det tar sekunder og fanger regnefeil.
•Ved lineære kongruenser: oppgi først \(d = \gcd(a,n)\), sjekk \(d \mid b\), reduser, og angi alle \(d\) løsninger modulo \(n\) — ikke bare én.
•For store potenser, bruk Fermat til å redusere eksponenten først; regn aldri ut potensen direkte.
•I CRT lønner det seg å skrive opp \(N\), alle \(M_i\) og alle inverser \(y_i\) systematisk i en liten tabell før du summerer.
•Husk konvensjonene i faget: \(\mathbb{N}\) inkluderer 0, og oppgi modulære svar i standard restklasse \(\{0,1,\dots,n-1\}\).
•For RSA-oppgaver: beregn \(\varphi(N) = (p-1)(q-1)\) først, og finn \(d\) som invers av \(e\) modulo \(\varphi(N)\) — ikke modulo \(N\).
RSA og kryptografi
•Skriv alltid opp \(N\), \(\varphi(N)=(p-1)(q-1)\) og betingelsen \(\gcd(e,\varphi(N))=1\) eksplisitt før du regner — det gir delpoeng og struktur.
•Vis utvidet Euklid med tilbakesubstitusjon når du finner \(d\); avslutt med en sjekk \(ed\bmod\varphi(N)=1\).
•Ved gjentatt kvadrering: skriv eksponenten binært, list opp alle kvadrater, og marker hvilke som ganges sammen. Reduser modulo \(n\) i hvert steg.
•For Fermat-faktorisering: start på \(\lceil\sqrt N\rceil\) og lag en liten tabell over \(a,\ a^2-N,\ \sqrt{a^2-N}\) til du treffer et perfekt kvadrat.
•Kan du forklare Håstad-angrepet med ord (lik \(m\), lik lav \(e\), ulike moduli, CRT, \(e\)-te rot), får du som regel full uttelling på «forklar»-oppgaver.
•Husk konvensjonen at \(\mathbb{N}\) inkluderer 0, men i \(\varphi(n)\) teller vi tallene \(1,\dots,n\) (eller ekvivalent \(0,\dots,n-1\) relativt primiske).
Kombinatorikk
•Skriv alltid ned klassifiseringen først: ordnet/uordnet og med/uten tilbakelegging. Da faller riktig formel automatisk på plass.
•Ved 'minst'/'ikke'-formuleringer: vurder komplementtelling før du gjør noe annet — det sparer ofte mye arbeid.
•Ved 'eller'-formuleringer med mulig overlapp: tegn et Venn-diagram og bruk inklusjon-eksklusjon eksplisitt med fortegn.
•Husk identitetene \(\binom{n}{k}=\binom{n}{n-k}\) og \(\binom{n}{0}=\binom{n}{n}=1\) for å forenkle utregninger.
•Tolk ord-oppgaver konkret: 'komité' = uordnet, 'podium/rekkefølge/passord' = ordnet, 'identiske objekter i bokser' = stars and bars.
•Vis mellomregning. Selv om du kjenner svaret, gir oppsettet \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\) med innsatte tall delpoeng om sluttsvaret blir feil.
•Dobbeltsjekk med en alternativ metode når mulig (f.eks. komplement vs. direkte) for å fange regnefeil under tidspress.
Grafteori
•Sjekk alltid Euler ved å TELLE oddenoder: 0 ⟹ krets, 2 ⟹ vei, ellers ingen. Verifiser også at grafen er sammenhengende.
•For Hamilton: prøv Dirac/Ore for å BEKREFTE eksistens; for å motbevise, se etter node av grad 1, broer eller bipartite-ubalanse.
•Ved isomorfi-oppgaver: motbevis raskt med invarianter (gradsekvens, kanttall, komponenter, sykellengder) FØR du leter etter en bijeksjon.
•For å BEVISE isomorfi: oppgi bijeksjonen eksplisitt i en tabell og verifiser hver kant — ikke bare påstå at den finnes.
•Bruk handshaking til å sjekke om en gradsekvens er mulig (sum må være partall) og til å regne ut \(|E|\) fra grader.
•Skriv bevis med eksplisitt struktur: for handshaking-konsekvensen, del nodene i odde/jevne og argumenter med partall-summer.
•Husk konvensjonene: noder/kanter som mengder \(\langle V,E\rangle\), uordnede par for uretttede grafer, ordnede par for rettede.
Trær
•Lær telleformlene n=mi+1 og l=(m-1)i+1 utenat, og bruk identiteten n=i+l som rask kontroll.
•Ved bevis om trær: skriv eksplisitt basistilfelle, induksjonshypotese og induksjonssteg, og fjern alltid et BLAD for å redusere problemstørrelsen.
•Tegn uttrykkstreet eksplisitt før du skriver prefiks/postfiks — da blir traverseringen mekanisk og feilfri.
•Bruk stakk-metoden systematisk når du evaluerer postfiks-uttrykk: operand→push, operator→pop to, regn ut, push.
•Husk at hver kant i et tre er en bro (fjerning splitter), og at hver tilført kant lager nøyaktig én sykel — dette er ofte testet som sant/usant-påstander.
•Cayleys formel n^(n-2) gir antall spenntrær i K_n; nyttig for små grafer (K_3=3, K_4=16, K_5=125).
Endelige tilstandsmaskiner og formelle språk
•Tegn alltid tilstandsdiagrammet og navngi hva hver tilstand «husker» (paritet, rest modulo k, siste j symboler, hvor langt i mønsteret). Det gir delpoeng og gjør overgangene selvskrevne.
•Oppgaver av typen «finn en regulær grammatikk som genererer samme språk som automaten» har gått igjen på nesten hvert sett i perioden 2013–2021. Lær oppskriften utenat: A_i → x A_j per overgang, A_i → λ per aksepttilstand.
•Sjekk alltid formkravet før du kaller en grammatikk regulær: høyst ett terminalsymbol per produksjon, og ikke-terminalen helt til høyre.
•Ved «konstruer en automat med høyst n tilstander»: tell hva du faktisk må huske. Trenger du en felletilstand, si det eksplisitt — i en DFA må f være total.
•For «delelig med k»- eller modulo-språk: én tilstand per rest gir minimal DFA med k tilstander.
•Skal du vise at et språk ikke er regulært, skriv de fem stegene eksplisitt (anta k tilstander, velg k+1 prefikser, skuffeprinsipp, velg hale, motsigelse). Sensor leter etter valget av hale.
•Ved telling: vurder komplementargument først (totalt k^n minus uønskede) — det er ofte raskere enn rekursjonen.
•Husk konvensjonen at N inkluderer 0 og at A⁰ = {λ}, så A* alltid inneholder den tomme strengen.
Boolsk algebra
•Skriv aksiomet/loven du bruker ved hvert forenklingssteg (identitet, distributiv, komplement, De Morgan). Sensor gir poeng for eksplisitt begrunnelse.
•Når du skal vise at noe IKKE er en boolsk algebra, hold det til ETT konkret moteksempel – f.eks. ett element som mangler komplement – framfor å sjekke alle aksiomer.
•For delelighetsgitter: sjekk først om \(n\) er kvadratfri. Hvis ja, bruk \(\overline{a}=n/a\) og verifiser lcm/gcd; hvis nei, finn elementet uten komplement.
•Kan du ikke forenkle algebraisk? Sett opp en sannhetstabell for begge sider – det beviser likhet utvetydig over alle \(2^n\) rader.
•Husk standardtriksene \(x+\overline{x}y=x+y\) og konsensus \(xy+\overline{x}z+yz=xy+\overline{x}z\); de dukker ofte opp og sparer mye tid.
•Når du leser av SOP fra en sannhetstabell: variabel direkte hvis verdien er 1, komplementert hvis 0, deretter join av mintermene fra alle 1-radene.
•Bruk dualitetsprinsippet til å sjekke arbeidet ditt: bytt \(+\leftrightarrow\cdot\) og \(0\leftrightarrow 1\), og se at den duale identiteten også stemmer.