Bevisteknikker (færdig) Flashcards
Hvad er et modstridsbevis?
Beviser at udsagnet p er sandt ved at antage at ¬p er sand og vise at denne antagelse fører til en modstrid (lyn-symbol).
Dermed må antagelsen (¬p) være falsk og udsagnet p sandt.
Hvad er et direkte bevis?
Beviser at p → q ved at antage at p er sand, og vise at så er q sand.
Hvad er et induktionsbevis?
Lad A(n) være et udsagn og n være et heltal.
Vi bruger induktionsbeviser for at se om udsagnet er sandt for alle n ≥ n0
Basistrin: Hvis A er sand for n+ og hvis vi kan vise at fra A(n) følger at A(n+1) er sand. Så er A(n) sand for alle n ≥ n0.
Induktionstrin: n
Hvad er svag induktion?
Med svag induktion beviser man med et enkelt basistrin inden man udleder en induktionshypotese.
Hvad er stærk induktion?
Med stærk induktion beviser man med flere basistrin inden man udleder en induktionshypotese.
Hvilken form for induktion er det når man har brugt mere end 1 basistrin?
Stærk induktion.
Hvad er forskellen mellem svag og stærk induktion?
Med svag induktion beviser man med et enkelt basistrin inden man udleder en induktionshypotese. Med stærk induktion bruger man flere basistrin.
Hvad er slutningsregler?
Slutningsregler er valide argumenter for udsagn.
Man konkluderer noget ud fra nogle præmisser.
f.eks.
p: “du arbejder hårdt”
q: “du bliver rig”
p → q
p
______
.
. . q
(hvor første del er præmisserne og . . . q er konklusionen)
dvs. (( p → q) ∧ p) → q (en tautologi)
Hvad er et bevis?
Valide argumenter for at argumentere at et udsagn er sandt.
Ved brug af slutningsregler.
Hvad er et kontrapositionsbevis?
Beviser at p → q ved at antage at ¬q er sand og vise at ¬p også er sand.
p → q ≡ ¬q → ¬p
Hvad er et eksistensbevis?
Sætninger som starter med “der eksisterer”, “der findes” kræver eksistensbeviser.
Nogle gange kan x’et findes og det er nok.
Hvad er et modeksempel?
Hvis man vil bevise et udsagn er falsk, er det nok at finde et modeksempel.
