Hoppa till huvudinnehållet
Logga inSkapa konto

Formelsamling för Diskret matematik

38 formler ur SF1662, i kursens egen ordning. En formel utan sitt villkor är en gissning — därför står det utskrivet vad var och en kräver för att gälla.

Mängder, funktioner och relationer

Ekvivalensklasser

Mängder, funktioner och relationer →
[a]R={x∈A:xRa},A=⨆[a]∈A/R[a][a]_R=\{x\in A:xRa\},\qquad A=\bigsqcup_{[a]\in A/R}[a]
Vad gör formeln?
Klasserna bildar en av mängden.
När får den användas?
Relationen ska vara reflexiv, symmetrisk och transitiv.

Ur KTH: SF1662 Diskret matematik

Axiomen för en

Mängder, funktioner och relationer →
∀a∈A: aRa∀a,b∈A: (aRb∧bRa)⇒a=b∀a,b,c∈A: (aRb∧bRc)⇒aRc\begin{gathered}\forall a\in A:\ aRa\\\forall a,b\in A:\ (aRb\land bRa)\Rightarrow a=b\\\forall a,b,c\in A:\ (aRb\land bRc)\Rightarrow aRc\end{gathered}
Vad gör formeln?
Reflexivitet, och transitivitet måste visas var för sig.
När får den användas?
Relationen ligger på en och samma mängd. Total jämförbarhet krävs inte.

Ur KTH: SF1662 Diskret matematik

De Morgans lagar

Mängder, funktioner och relationer →
(A∪B)c=Ac∩Bc,(A∩B)c=Ac∪Bc(A\cup B)^c=A^c\cap B^c,\qquad(A\cap B)^c=A^c\cup B^c
Vad gör formeln?
byter union mot snitt och snitt mot union.
När får den användas?
Alla tas relativt samma universalmängd.

Ur KTH: SF1662 Diskret matematik

Induktion, rekursion och bevis

Induktionsprincipen

Induktion, rekursion och bevis →
P(n0)∧∀n≥n0 (P(n)⇒P(n+1)) ⇒ ∀n≥n0 P(n)P(n_0)\land\forall n\ge n_0\,(P(n)\Rightarrow P(n+1))\ \Rightarrow\ \forall n\ge n_0\,P(n)
Vad gör formeln?
Ett basfall och ett steg bevisar alla följande fall.
När får den användas?
Indexen är heltal och basfallet är det första tillåtna indexet.

Ur KTH: SF1662 Diskret matematik

Fibonaccis

Induktion, rekursion och bevis →
F0=0,F1=1,Fn+2=Fn+1+Fn(n≥0)F_0=0,\quad F_1=1,\quad F_{n+2}=F_{n+1}+F_n\quad(n\ge0)
Vad gör formeln?
Varje ny term är summan av de två föregående.
När får den användas?
Båda startvärdena ingår i definitionen.

Ur KTH: SF1662 Diskret matematik

Heltal och diofantiska ekvationer

Euklides algoritm

Heltal och diofantiska ekvationer →
a=bq+r⇒gcd⁡(a,b)=gcd⁡(b,r)a=bq+r\quad\Rightarrow\quad\gcd(a,b)=\gcd(b,r)
Vad gör formeln?
Upprepad division hittar största gemensamma delaren.
När får den användas?
Heltal med positiv divisor; resten är minst noll och mindre än divisorn.

Ur KTH: SF1662 Diskret matematik

Linjär

Heltal och diofantiska ekvationer →
ax+by=c,d=gcd⁡(a,b)∣c,x=x0+bdt, y=y0−adt(t∈Z)ax+by=c,\quad d=\gcd(a,b)\mid c,\quad x=x_0+\frac bd t,\ y=y_0-\frac ad t\quad(t\in\mathbb Z)
Vad gör formeln?
En särskild lösning ger alla heltalslösningar.
När får den användas?
Koefficienterna är icke-nollheltal och en särskild lösning är känd; om delbarhetsvillkoret inte gäller saknas lösningar.

Ur KTH: SF1662 Diskret matematik

Kongruenser och RSA

Kongruenser och RSA →
a−1(modm) finns  ⟺  gcd⁡(a,m)=1a^{-1}\pmod m\text{ finns}\iff\gcd(a,m)=1
Vad gör formeln?
Tillåter division med en faktor i en .
När får den användas?
Modulen är ett heltal större än ett.

Ur KTH: SF1662 Diskret matematik

Fermats lilla sats

Kongruenser och RSA →
p∤a⇒ap−1≡1(modp)p\nmid a\quad\Rightarrow\quad a^{p-1}\equiv1\pmod p
Vad gör formeln?
Reducerar stora exponenter primtal.
När får den användas?
Modulen är ett primtal som inte delar basen.

Ur KTH: SF1662 Diskret matematik

Kinesiska restsatsen

Kongruenser och RSA →
gcd⁡(m,n)=1 ⇒ {x≡a(modm)x≡b(modn) har en unik lo¨sning modulo mn\gcd(m,n)=1\ \Rightarrow\ \begin{cases}x\equiv a\pmod m\\ x\equiv b\pmod n\end{cases}\text{ har en unik lösning modulo }mn
Vad gör formeln?
Sätter samman restvillkor för olika moduler.
När får den användas?
Modulerna är positiva och .

Ur KTH: SF1662 Diskret matematik

RSA: nycklar och kryptering

Kongruenser och RSA →
n=pq,m=(p−1)(q−1),gcd⁡(e,m)=1,ed≡1(modm),c≡ae(modn)n=pq,\quad m=(p-1)(q-1),\quad\gcd(e,m)=1,\quad ed\equiv1\pmod m,\quad c\equiv a^e\pmod n
Vad gör formeln?
Kopplar kryptering och dekryptering genom inversa exponenter.
När får den användas?
Två olika primtal används. Dekrypteringsexponenten väljs positiv.

Ur KTH: SF1662 Diskret matematik

Kombinatorik och sannolikhet

Oordnat urval

Kombinatorik och sannolikhet →
(nk)=n!k!(n−k)!\binom nk=\frac{n!}{k!(n-k)!}
Vad gör formeln?
Räknar delmängder med en bestämd storlek.
När får den användas?
Välj ett helt antal objekt mellan noll och antalet tillgängliga olika objekt, utan repetition.

Ur KTH: SF1662 Diskret matematik

Permutationer med upprepade objekt

Kombinatorik och sannolikhet →
n!n1!⋯nr!,n1+⋯+nr=n\frac{n!}{n_1!\cdots n_r!},\qquad n_1+\cdots+n_r=n
Vad gör formeln?
Kompenserar för omordningar som ger samma resultat.
När får den användas?
Objekt inom samma typ är identiska; alla positioner är ordnade.

Ur KTH: SF1662 Diskret matematik

Stjärnor och streck

Kombinatorik och sannolikhet →
x1+⋯+xk=n, xi≥0⇒(n+k−1k−1) lo¨sningarx_1+\cdots+x_k=n,\ x_i\ge0\quad\Rightarrow\quad\binom{n+k-1}{k-1}\text{ lösningar}
Vad gör formeln?
Räknar fördelningar med tillåtna tomma lådor.
När får den användas?
Icke-negativa heltalsvariabler och minst en märkt låda; objekten är identiska.

Ur KTH: SF1662 Diskret matematik

Binomialsatsen

Kombinatorik och sannolikhet →
(a+b)n=∑k=0n(nk)an−kbk(a+b)^n=\sum_{k=0}^n\binom nk a^{n-k}b^k
Vad gör formeln?
Ger koefficienterna i en potensutveckling.
När får den användas?
Exponentens värde är ett icke-negativt heltal; faktorerna kommuterar.

Ur KTH: SF1662 Diskret matematik

Inklusion–exklusion för tre mängder

Kombinatorik och sannolikhet →
∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|
Vad gör formeln?
Räknar unionen utan över- eller underräkning.
När får den användas?
Mängderna är ändliga och kan överlappa.

Ur KTH: SF1662 Diskret matematik

Kombinatorik och sannolikhet →
S(n,k)=S(n−1,k−1)+kS(n−1,k)S(0,0)=1,S(n,0)=0 (n>0),S(n,k)=0 (k>n)\begin{gathered}S(n,k)=S(n-1,k-1)+kS(n-1,k)\\ S(0,0)=1,\quad S(n,0)=0\ (n>0),\quad S(n,k)=0\ (k>n)\end{gathered}
Vad gör formeln?
Räknar partitioner av olika objekt i ett bestämt antal icke-tomma, omärkta grupper.
När får den användas?
Rekursionssteget gäller positiva heltal för antalet objekt och antalet grupper. Tomma gränsfall hanteras med de angivna startvärdena.

Ur KTH: SF1662 Diskret matematik

Antalet surjektioner

Kombinatorik och sannolikhet →
k!S(n,k)=∑j=0k(−1)j(kj)(k−j)nk!S(n,k)=\sum_{j=0}^{k}(-1)^j\binom kj(k-j)^n
Vad gör formeln?
Räknar fördelningar där varje särskiljbar mottagare får minst ett objekt.
När får den användas?
Definitionsmängden har n olika element och målmängden k olika element, där n och k är positiva heltal. Varje målelement ska träffas.

Ur KTH: SF1662 Diskret matematik

Permutationer och grupper

av en permutation

Permutationer och grupper →
ord⁡(π)=lcm⁡(ℓ1,…,ℓr)\operatorname{ord}(\pi)=\operatorname{lcm}(\ell_1,\ldots,\ell_r)
Vad gör formeln?
Alla cykler måste samtidigt återgå till utgångsläget.
När får den användas?
Längderna kommer från permutationens disjunkta cykler.

Ur KTH: SF1662 Diskret matematik

Tecknet hos en permutation

Permutationer och grupper →
sgn⁡(π)=(−1)∑j(ℓj−1)\operatorname{sgn}(\pi)=(-1)^{\sum_j(\ell_j-1)}
Vad gör formeln?
Avgör om permutationen är jämn eller udda.
När får den användas?
Cyklerna är disjunkta. Fixpunkter ger exponentbidrag noll.

Ur KTH: SF1662 Diskret matematik

i en additiv restklassgrupp

Permutationer och grupper →
ord⁡Zn(a)=ngcd⁡(n,a)\operatorname{ord}_{\mathbb Z_n}(a)=\frac{n}{\gcd(n,a)}
Vad gör formeln?
Finner antalet additioner som krävs för att återkomma till noll.
När får den användas?
Gruppoperationen är addition ett positivt heltal.

Ur KTH: SF1662 Diskret matematik

Grafer, färgning och matchning

Villkor för

Grafer, färgning och matchning →
G har en Eulerkrets  ⟺  deg⁡(v) a¨r ja¨mn fo¨r varje nod vG\text{ har en Eulerkrets}\iff\deg(v)\text{ är jämn för varje nod }v
Vad gör formeln?
En sluten vandring kan använda varje kant exakt en gång.
När får den användas?
Grafen är ändlig, oriktad och sammanhängande.

Ur KTH: SF1662 Diskret matematik

Eulers formel för plana grafer

Grafer, färgning och matchning →
∣V∣−∣E∣+∣F∣=2|V|-|E|+|F|=2
Vad gör formeln?
Relaterar noder, kanter och regioner i en plan inbäddning.
När får den användas?
En ändlig sammanhängande graf är inbäddad i planet utan korsningar. Den obegränsade regionen räknas.

Ur KTH: SF1662 Diskret matematik

Halls äktenskapssats

Grafer, färgning och matchning →
Matchning som ta¨cker X  ⟺  ∀S⊆X: ∣N(S)∣≥∣S∣\text{Matchning som täcker }X\iff\forall S\subseteq X:\ |N(S)|\ge|S|
Vad gör formeln?
Karakteriserar när alla noder på ena sidan kan få olika partners.
När får den användas?
Grafen är ändlig och bipartit med sidorna X och Y.

Ur KTH: SF1662 Diskret matematik

och

Grafer, färgning och matchning →
PG(λ)=PG−e(λ)−PG/e(λ)P_G(\lambda)=P_{G-e}(\lambda)-P_{G/e}(\lambda)
Vad gör formeln?
Räknar färgningar genom att skilja på lika och olika färger vid en vald kants ändpunkter.
När får den användas?
Grafen är ändlig och enkel och e är en kant. Vid identifieras kantens ändpunkter; parallella kanter slås ihop. För heltalsvärden räknas färgningar ur en palett med så många särskiljbara färger.

Ur KTH: SF1662 Diskret matematik

Färgningar av en cykel

Grafer, färgning och matchning →
PCn(λ)=(λ−1)n+(−1)n(λ−1)P_{C_n}(\lambda)=(\lambda-1)^n+(-1)^n(\lambda-1)
Vad gör formeln?
Tar hänsyn till att även sista och första hörnet i en cykel måste få olika färger.
När får den användas?
Cykeln är enkel med n minst tre. Vid räkning är palettstorleken ett icke-negativt heltal.

Ur KTH: SF1662 Diskret matematik

Färgningar av en fullständig graf

Grafer, färgning och matchning →
PKn(λ)=λ(λ−1)⋯(λ−n+1)P_{K_n}(\lambda)=\lambda(\lambda-1)\cdots(\lambda-n+1)
Vad gör formeln?
Alla hörn måste få olika färger eftersom alla är grannar.
När får den användas?
Grafen har n minst ett hörn och varje par av olika hörn är förbundet. Palettstorleken är ett icke-negativt heltal.

Ur KTH: SF1662 Diskret matematik

Färgningar som använder hela paletten

Grafer, färgning och matchning →
∑j=0k(−1)j(kj)PG(k−j)\sum_{j=0}^{k}(-1)^j\binom kj P_G(k-j)
Vad gör formeln?
Räknar godkända hörnfärgningar där ingen av de givna färgerna lämnas oanvänd.
När får den användas?
Grafen är ändlig, enkel och icke-tom. Paletten har k särskiljbara färger, med k ett positivt heltal; varje färg måste förekomma.

Ur KTH: SF1662 Diskret matematik

Polynom och gaussiska heltal

Faktorsatsen

Polynom och gaussiska heltal →
f(a)=0  ⟺  (x−a)∣f(x)f(a)=0\iff (x-a)\mid f(x)
Vad gör formeln?
Översätter ett nollställe till en linjär faktor.
När får den användas?
Polynomet har koefficienter i en kropp och talet tillhör kroppen.

Ur KTH: SF1662 Diskret matematik

Division med rest för polynom

Polynom och gaussiska heltal →
f=qg+r,r=0 eller deg⁡r<deg⁡gf=qg+r,\qquad r=0\ \text{eller}\ \deg r<\deg g
Vad gör formeln?
Ger entydig kvot och rest.
När får den användas?
Koefficienterna ligger i en kropp och divisorn är inte nollpolynomet.

Ur KTH: SF1662 Diskret matematik

Norm i de gaussiska heltalen

Polynom och gaussiska heltal →
N(a+bi)=a2+b2,N(zw)=N(z)N(w)N(a+bi)=a^2+b^2,\qquad N(zw)=N(z)N(w)
Vad gör formeln?
Gör komplex till ett nödvändigt heltalsvillkor.
När får den användas?
Real- och imaginärdelarna är heltal.

Ur KTH: SF1662 Diskret matematik

Enheter i de gaussiska heltalen

Polynom och gaussiska heltal →
N(u)=1  ⟺  u∈{1,−1,i,−i}N(u)=1\iff u\in\{1,-1,i,-i\}
Vad gör formeln?
Enheter har en multiplikativ invers i samma ring.
När får den användas?
Talet ligger i de gaussiska heltalen.

Ur KTH: SF1662 Diskret matematik