Formler - Diskret Matematik

Mängdlära

Mängdnotation

a ∈ A, a ∉ A

Element a tillhör eller tillhör inte mängd A

Union av mängder

A ∪ B = {x : x ∈ A eller x ∈ B}

Mängden av alla element som finns i A eller B

Snitt av mängder

A ∩ B = {x : x ∈ A och x ∈ B}

Mängden av alla element som finns i både A och B

Komplement

$A^c = {x ∈ U : x ∉ A}$

Alla element i universalmängden U som inte finns i A

De Morgans lagar

(A ∪ B)^c = A^c ∩ B^c

Komplement av union och snitt

Inklusions-exklusionsprincipen

|A ∪ B| = |A| + |B| - |A ∩ B|

Kardinalitet av union för två mängder

Kartesisk produkt

A × B = {(a,b) : a ∈ A, b ∈ B}

Alla ordnade par från A och B

Potensmängd

|P(A)| = 2^|A|

Mängden av alla delmängder till A

Kombinatorik

Fakultet

n! = n · (n-1) · ... · 2 · 1

Antal permutationer av n objekt

Permutationer

P(n,k) = n!/(n-k)!

Antal sätt att ordna k objekt ur n objekt

Kombinationer

C(n,k) = n!/(k!(n-k)!)

Antal sätt att välja k objekt ur n objekt

Binomialsatsen

(x+y)^n = Σ C(n,k)x^k y^(n-k)

Utveckling av binomiala uttryck

Additionsprincipen

|A ∪ B| = |A| + |B| om A ∩ B = ∅

För disjunkta mängder

Multiplikationsprincipen

|A × B| = |A| · |B|

Kartesisk produkt av mängder

Stirlings nummer (andra slaget)

S(n,k) = k·S(n-1,k) + S(n-1,k-1)

Antal sätt att partitionera n objekt i k icke-tomma mängder

Catalan-tal

C_n = (1/(n+1))C(2n,n)

Antal sätt att parentesisera n faktorer

Grafteori

Graf definition

G = (V, E)

Graf G består av noder V och kanter E

Handskakningssatsen

Σdeg(v) = 2|E|

Summan av alla grader är dubbelt så många som antalet kanter

Träd egenskaper

T = (V, E), |E| = |V| - 1

Ett träd med n noder har n-1 kanter

Eulers formel

V - E + F = 2

För sammanhängande planära grafer

Spännande träd

T ⊆ G, T sammanhängande

Minimalt sammanhängande delgraf

Dijkstras algoritm

d[v] = min(d[v], d[u] + w(u,v))

Kortaste väg i viktad graf

Kromatiskt tal

χ(G) = min{k : G är k-färgbar}

Minsta antal färger för att färga graf

Matrix-Tree satsen

t(G) = det(L*)

Antal spännande träd i graf

Logik

Grundläggande operationer

p ∧ q, p ∨ q, ¬p

Konjunktion, disjunktion och negation

Implikation

p → q ≡ ¬p ∨ q

Om p så q

Bikondition

p ↔ q ≡ (p → q) ∧ (q → p)

p om och endast om q

De Morgans lagar

¬(p ∧ q) ≡ ¬p ∨ ¬q

Negation av konjunktion och disjunktion

Universell kvantifiering

∀x P(x)

För alla x gäller P(x)

Existentiell kvantifiering

∃x P(x)

Det finns ett x sådan att P(x)

Modus ponens

p → q, p ⊢ q

Om p då q, p är sant, alltså q

Modus tollens

p → q, ¬q ⊢ ¬p

Om p då q, inte q, alltså inte p

Automater och formella språk

Ändlig automat

M = (Q, Σ, δ, q₀, F)

Tillstånd, alfabet, övergångsfunktion, starttillstånd, accepttillstånd

Språk accepterat av automat

L(M) = {w ∈ Σ* : δ*(q₀, w) ∈ F}

Alla strängar som leder till accepttillstånd

Reguljärt uttryck

a*, a+, a?, a|b

Grundläggande operationer för reguljära uttryck

Pumping lemma

∃p ∀w ∈ L: |w| ≥ p ⇒ ∃xyz...

Test för att visa att språk inte är reguljärt

Kontextfri grammatik

G = (V, Σ, R, S)

Variabler, terminaler, regler, startsymbol

Komplexitetsklasser

f(n) = O(g(n))

Stora O-notation för algoritmkomplexitet

Modulär aritmetik

Kongruens

a ≡ b (mod m)

a och b har samma rest vid division med m

Modulär addition

(a + b) mod m = ((a mod m) + (b mod m)) mod m

Addition i modulär aritmetik

Modulär multiplikation

(a · b) mod m = ((a mod m) · (b mod m)) mod m

Multiplikation i modulär aritmetik

Modulär invers

a · a⁻¹ ≡ 1 (mod m)

Multiplikativ invers modulo m

Eulers totientfunktion

φ(n) = n ∏(1 - 1/p)

Antal tal relativt prima med n

Kinesiska restsatsen

x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂)

Lösning av system av kongruenser

Snabb exponentiering

aⁿ mod m

Effektiv beräkning av stora exponenter

Fermat's lilla sats

a^(p-1) ≡ 1 (mod p)

För primtal p och gcd(a,p) = 1