•Antall boolske funksjoner av \(n\) variabler: \(2^{2^n}\)
•Endelig boolsk algebra har \(2^k\) elementer (\(k\) atomer)
•Komplement i \(D_n\) (kvadratfri): \(\overline{a}=n/a\)
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
•Hopper over basistilfellet — uten et sant basis er hele kjeden uforankret.
•Bruker IH på hele \(\sum_{i=1}^{k+1}\) i stedet for å splitte ut det siste leddet først (\(\sum_{i=1}^{k+1}=\left(\sum_{i=1}^{k}\right)+a_{k+1}\)).
•For få basistilfeller ved dype rekurrenser: Tribonacci trenger TRE basistilfeller (\(T_0,T_1,T_2\)), ikke ett.
•Velger feil basistilfelle: når påstanden bare gjelder \(n\ge n_0\) (f.eks. \(2^n>n^2\) for \(n\ge5\)), må basis være \(n=n_0\), ikke \(n=0\).
•Antar konklusjonen i steget: man skal vise \(P(k+1)\), ikke anta den.
•Glemmer at \(\mathbb{N}\) inkluderer 0 i dette emnet, og setter basis til \(n=1\) når \(n=0\) er det aktuelle minste tilfellet.
•Strukturell induksjon: glemmer å dekke ALLE konstruksjonsregler, eller behandler bare grunnelementet.
•Snur rekkefølgen feil i reversering — det korrekte er \((uv)^R=v^R u^R\), ikke \(u^R v^R\).
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
•Glemme at A* og dermed A⁰ inneholder λ — A* er aldri tom og inkluderer alltid den tomme strengen.
•Forveksle A* (null eller flere) med A⁺ (én eller flere); forskjellen er λ når λ ∉ A.
•Tro at a*b* = (a∪b)*. a*b* krever at alle a-er kommer før alle b-er; «ba» ligger ikke i a*b*.
•Anta at λ alltid aksepteres. λ aksepteres bare hvis starttilstanden er aksepterende (s₀ ∈ F).
•Lage en ufullstendig overgangsfunksjon. I en DFA må f være total — hver tilstand trenger en overgang for HVERT symbol (bruk felletilstand ved behov).
•Telle dobbelt ved «inneholder aa»-problemer ved å summere posisjoner direkte; bruk komplement (Fibonacci) i stedet for å unngå overlapp.
•Bytte om markeringen av start (kildeløs pil) og aksepterende tilstand (dobbel sirkel) i tilstandsdiagram.
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 alltid bevisstrukturen eksplisitt med overskrifter: «Basistilfelle», «Induksjonshypotese», «Induksjonssteg», «Konklusjon». Det gir delpoeng selv ved regnefeil.
•Marker tydelig HVOR du bruker induksjonshypotesen (skriv \(\overset{IH}{=}\) eller «etter IH»). Sensor leter etter dette.
•Ved «gjett og bevis»: regn ut 4–5 ledd, gjett lukket form, og presiser at du verifiserer den med induksjon.
•Tell dybden på rekurrensen for å bestemme antall basistilfeller FØR du begynner steget.
•For lineære rekurrenser: sett opp karakteristisk ligning, finn røtter, bruk startverdier til å bestemme konstantene — vis hvert steg.
•Ved strukturell induksjon: gjenta den rekursive definisjonen du bruker (av lengde, reversering, konkatenering) før beviset, så sensor ser hvilke regler du støtter deg på.
•Hvis steget ikke går opp, vurder å STYRKE påstanden (load the hypothesis) eller bytte til sterk induksjon.
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 eksplisitt og navngi hva hver tilstand «husker» (f.eks. paritet, sist sett symbol, rest modulo k).
•For «delelig med k»- eller «modulo»-språk: bruk én tilstand per rest, det gir minimal DFA med k tilstander.
•Ved telling: vurder komplement-argument først (totalt kⁿ minus uønskede) — det er ofte raskere enn direkte rekursjon.
•Når du oversetter DFA → regulært uttrykk, identifiser sløyfer og grener; beskriv akseptstier som union av konkatenasjoner med stjerne på sløyfer.
•Verifiser et regulært uttrykk ved å sjekke korteste aksepterte streng og minst én forkastet streng.
•Husk konvensjonen N inkluderer 0 og A⁰ = {λ} når du resonnerer om lengder og Kleene-stjerne.
•For paritets-kombinasjoner (partall a OG partall b): bruk produktkonstruksjon med 2×2 = 4 tilstander.
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.