Diskret matemtaikk

mengd

ein samling av element (objekt), utan krav til kva elementa er.

ℕ

mengda av alle naturlege tal: {0, 1, 2, 3, …}.

ℤ

mengda av alle heiltal: {…, −2, −1, 0, 1, 2, …}.

ℝ

mengda av alle reelle tal (alle tal på tallinja).

den tomme mengda

∅ eller {} – ei mengd utan element.

x ∈ M

x er eit element i mengda M.

x ∉ M

x er ikkje eit element i M.

Er {1, 3} lik {3, 1}?

Ja, rekkefølgje spelar inga rolle i mengder.

Har gjentaking betydning i mengder?

Nei, {1,1,3} er same mengd som {1,3}.

Kan ei mengd vere eit element i ei anna mengd?

Ja

A = {{1,2,4}, {2}, ∅, {2,3,5}} er ei mengd med fire element.

Er 2 ∈ A i dette tilfellet?

Nei, men {2} ∈ A.

A ⊆ B

A er ei delmengd av B

Alle element i A er også element i B.

Kva kan vi seie viss A ⊆ B og B ⊆ A?

Då er A = B.

Kva betyr symbolet |?

“slik at”.

Kva betyr {x ∈ ℕ | x > 2}?

Mengda av alle naturlege tal større enn 2.

Korleis beskriv vi partal?

{2y | y ∈ ℕ}.

Korleis beskriv vi oddetal?

{2y + 1 | y ∈ ℕ}

samansette tal

Positive heiltal som kan delast av andre tal enn 1 og seg sjølve.

union (A ∪ B)

element som ligg i A eller B (eller begge).

snitt (A ∩ B)

Element som ligg både i A og B.

differanse (A \ B)

Element som ligg i A, men ikkje i B.

universell mengd U

Mengda som inneheld alle element vi vurderer.

Kva er komplementet til A?

Aᶜ = U \ A.

Kva er komplementet av partala i N?

Oddetal

ein binærrelasjon

ei delmengde av eit kartesisk produkt.

antall binærrelasjoner på A

P(A x A)

det kartesiske produktet (A x B)

mengda av alle ordna par der det første elementet kjem frå éi mengd og det andre frå ei anna (eller same) mengd.

ordna par <a,b>

rekkjefølgja betyr noko, så (a,b) ≠ (b,a)

uordna par {a,b}

tilsvarar mengder, så {a,b} = {b,a}

Potensmengde, P(A)

Mengda av alle delmengder av ei mengde

mengdebygger-notasjon

ein måte å beskrive mengder ved eigenskapar ({x∣… })

Binomialkoeffisient

tallet på måtar å velje k element frå mengda n utan rekkjefølgje og tilbakelegging.

De Morgans lover

grunnleggjande reglar i logikk som seier korleis negasjon verkar på samansette utsagn med og (∧) og eller (∨).

bevis for at to mengdar er like

to mengder er like dersom dei er delmengder av kvarandre.

eit utsagn

noko som kan vere anten sant eller usant, og alltid nøyaktig éin av delane.

eit atomært utsagn

eit utsagn som ikkje er sett saman av andre utsagn.

eit samansett utsagn

eit utsagn som er bygd opp av fleire utsagn ved hjelp av logiske konnektivar.

syntaks i utsagnslogikk

reglane for korleis vi skriv gyldige utsagnslogiske formlar.

semantikk i utsagnslogikk

korleis vi tolkar og gir meining til utsagnslogiske formlar.

ein logisk konnektiv

ein operator som bind saman utsagn, til dømes ¬, ∧, ∨ og →.

¬ (negasjon)

NOT (ikkje)

∧ (konjunksjon)

«og» – den er berre sann når begge utsagna er sanne.

∨ (disjunksjon)

«eller» – den er sann når minst eitt av utsagna er sanne.

→ (implikasjon)

«medfører»

A → B er usann berre når A er sann og B er usann.

Kva betyr A → B med ord?

Dersom A er sann, så må B vere sann.

ein utsagnsvariabel

ein symbolsk representasjon av eit atomært utsagn, til dømes P eller Q.

ein utsagnslogisk formel

eit uttrykk bygd av utsagnsvariablar, konnektivar og parentesar.

Kva er presedensreglane for konnektiv?

Først ¬, så ∧, deretter ∨, og til slutt →

sannheitsverdi

verdien 1 (sann) eller 0 (usann).

ein valuasjon

ein tilordning av sannheitsverdiar til utsagnsvariablar.

sannheitsverditabell

ein tabell som viser sannheitsverdien til ein formel for alle valuasjonar.

logisk ekvivalens ( <=> )

to formlar har same sannheitsverdi for alle valuasjonar.

logisk konsekvens (=>)

Q er ein logisk konsekvens av P dersom alle valuasjonar som gjer P sann, også gjer Q sann.

Det er umogleg at P er sann og Q er usann samtidig.

logisk konsekvens vs logisk ekvivalens

Ekvivalens går begge vegar, konsekvens berre éin veg.

Når er eit resonnement gyldig?

Det er gyldig dersom konklusjonen er ein logisk konsekvens av premissane.

Det finst ingen valuasjon der alle premissane er sanne og konklusjonen er usann.

modus tollens

Dersom A skulle vore sann, måtte B vore sann. Når B er usann, kan ikkje A vere sann.

eit ugyldig argument

eit argument der premissane kan vere sanne samtidig som konklusjonen er usann.

tautologi

ein formel som er sann for alle valuasjonar.

kontradiksjon (motsigelse)

ein formel som er usann for alle valuasjonar.

Kva betyr at ei formel er oppfyllbar?

Det finst minst éi valuasjon som gjer formelen sann.

Kva betyr at ei formel er falsifiserbar?

Det finst minst éi valuasjon som gjer formelen usann.

Kan ei formel vere både oppfyllbar og falsifiserbar?

Ja, dei fleste formlar er begge delar.

Kan ei tautologi vere falsifiserbar?

nei

Kan ein kontradiksjon vere oppfyllbar?

nei

utsagnslogiske lover

reglar som seier når to formlar er logisk ekvivalente.

Dobbel negasjon

ei utsagnslogisk lov som seier at to negasjonar opphevar kvarandre.
Formelt: ¬¬A ⇔ A

Korleis kan utsagnslogiske lover bevisast?

vha sannheitsverditabellar.

Kva betyr at ei formel er uavhengig av ei anna?

Verken formelen eller negasjonen hennar er ein logisk konsekvens av den andre.

Når er to formlar uavhengige?

Når dei er uavhengige av kvarandre begge vegar.

Assosiative lover

Lover som seier at rekkjefølgja på gruppering (parentesar) spelar inga rolle.

Kommutative lover

Lover som seier at rekkjefølgja på utsagna spelar inga rolle.

Kva er eit bevis?

Ei rekke gyldige argument som viser at ei påstand følgjer logisk frå antakingar.

ein formodning

Ein påstand som ein trur er sann, men som ikkje er bevist.

Kva er skilnaden på teorem og formodning?

Teorem er bevist, formodningar er ikkje bevist.

eksistenspåstand

ein påstand som seier at det finst minst eitt element med ei gitt eigenskap.

ein universell påstand

ein påstand som seier at noko gjeld for alle element i ei mengd.

eit konstruktivt eksistensbevis

eit bevis der ein eksplisitt finn eit element som oppfyller påstanden.

eit ikkje-konstruktivt eksistensbevis

eit bevis som viser at noko finst, utan å gi eit konkret eksempel.

direkte bevis

eit bevis der ein går direkte frå antakingane til konklusjonen med gyldige steg.

Når brukar vi direkte bevis?

Når samanhengen mellom premiss og konklusjon er klar og enkel å vise.

kontrapositivt bevis

ein bevismetode er ein skal vise at G er en logisk konsekvens av F, ved å vise at ¬F er en logisk konsekvens av ¬G

motsigelsesbevis

eit bevis der ein antar at påstanden er usann og kjem fram til ei motsigelse.

Kva er bevis ved tilfeller?

Eit bevis der ein deler opp i ulike tilfeller og viser påstanden i kvart tilfelle.

induksjonsbevis

ein bevismetode for universelle påstander over uendelege mengder, ofte naturlege tal.

Korleis motbeviser vi ei universell påstand?

Ved å finne eitt moteksempel.

moteksempel

eit enkelt tilfelle som viser at ei universell påstand ikkje held.

Korleis motbeviser vi ei eksistenspåstand?

ved å vise at ingen element har den aktuelle eigenskapen.

Kva er det kartesiske produktet A × B?

Mengda av alle ordna par ⟨a, b⟩ der a ∈ A og b ∈ B.

Kor mange element har A × A dersom |A| = n?

n² element.

Kva er ein relasjon på ei mengd A?

ein delmengd av A × A

Kva er ein relasjon frå A til B?

ein delmengd av A × B

ein binær relasjon

ein relasjon som består av par av to element.

Kor mange relasjonar finst på ei mengd A med n element?

2^n²

Infiksnotasjon for relasjonar

Det betyr at vi skriv relasjonen mellom elementa, i staden for som eit par.

I staden for å skrive ⟨a, b⟩ ∈ R, skriv vi a R b.

⟨1, 3⟩ ∈ ≤ skrivast som 1 ≤ 3.

Korleis kan ein relasjon visast grafisk?

Med piler frå x til y for kvart par ⟨x, y⟩ i relasjonen.

Kva betyr at ein relasjon er refleksiv?

Ein relasjon R på ei mengd A er refleksiv dersom alle element er relatert til seg sjølve (alle peikar på seg sjølve.)

For alle a ∈ A gjeld ⟨a, a⟩ ∈ R.

Kva betyr at ein relasjon er irrefleksiv?

Det betyr at ingen element er relatert til seg sjølve.

For alle a ∈ A gjeld ⟨a, a⟩ ∉ R.

Kva betyr at ein relasjon er transitiv?

Det betyr at relasjonen kan “hoppe vidare”. Viss a er relatert til b, og b er relatert til c,

så må også a vere relatert til c.

⟨a, b⟩ ∈ R og ⟨b, c⟩ ∈ R ⇒ ⟨a, c⟩ ∈ R.

Kva betyr at ein relasjon er symmetrisk?

Det betyr at viss a er relatert til b, må b vere relatert til a.

⟨a, b⟩ ∈ R ⇒ ⟨b, a⟩ ∈ R.

Når er ein relasjon anti-symmetrisk?

Ein relasjon R er anti-symmetrisk dersom det berre kan gå begge vegar når det er same element. Viss a er relatert til b, og b er relatert til a, så må a og b vere det same elementet.

⟨a, b⟩ ∈ R og ⟨b, a⟩ ∈ R ⇒ a = b.