Slides til 1.5

(1)

Slides til 1.5

Andreas Leopold Knutsen January 20, 2010

(2)

Argument

Mål: korrekt resonnement (eks.:matematiske bevis) p₁

p₂ ...p_n

∴ q

I Premisser/hypoteser/antagelser: p₁, . . . , p_n (sammensatte prop.)

I Konklusjon/slutning/konsekvens: q

I ∴ Dermed/ergo

I Inference=slutning

(3)

Gyldig argument

Argumentet

p₁ p₂ ...p_n

∴ q

er gyldig når:

I Sanne premisser medfører sann konklusjon, dvs.

I (p₁ ∧ p₂ ∧ · · · ∧ p_n) → q er tautologi, dvs.

I

(p₁ ∧ p₂ ∧ · · · ∧ p_n) → q

≡ T.

NB: Usann konklusjon betyr enten

I usanne premisser, eller

I ugyldig argument.

(4)

Slutningsregler: 1.5-Tabell 1

Regel Navn

pp → q

∴ q Modus ponens

¬q p → q

∴ ¬p Modus tollens p → q

q → r

∴ p → r Hypotetisk syllogisme p ∨ q

¬p

∴ q Disjunktiv syllogisme p

∴ p ∨ q Addisjon p ∧ q

∴ p Simplisering pq

∴ p ∧ q Konjunksjon p ∨ q

¬p ∨ r

∴ q ∨ r Resolusjon

(5)

Eksempel: gyldig eller ikke?

I Når det ikke regner, så snør det

I Hvis det snør, så kommer brøytebilen

I Brøytebilen kommer ikke

I Derfor regner det

I r det regner

I s det snør

I b brøytebilen kommer

Argument:

¬r → s s → b

¬b

∴ r Tas på tavlen.

(6)

Eksempel: gyldig eller ikke?

I Jeg drikker øl når det ikke er mer melk eller når jeg lager pizza

I Jeg lager pizza bare hvis det er lørdag eller det er fest

I Det er lørdag idag og jeg er på fest

I Derfor drikker jeg øl

I d jeg drikker øl

I m det nnes mer melk

I p jeg lager pizza

I l det er lørdag

I f det er fest

Argument:

¬m ∨ p → d p → l ∨ f l ∧ f

∴ d Tas på tavlen.

(7)

Slutningsregler med ∀ : 1.5-Tabell 2

Regel Navn

∀xP(x)

∴ P(c) Universell instansiering P(c) for vilkårlig c

∴ ∀xP(x) Universell generalisering

I UG skal c være et vilkårlig element i domenet, vi kan ikke anta noe mer om c.

(8)

Eksempel på universell generalisering

Vis at x² ≥ x for ethvert naturlig tall x (naturlige tall er positive hele tall)

I Domene = naturlige tall = N

I P(x) x² ≥ x

I Vil konkludere ∀xP(x)

I Viser da P(n) for vilkårlig naturlig tall n

Riktig bevis: La n være et vilkårlig naturlig tall. Da er n ≥ 1, slik at n² ≥ n · 1 = n. QED

Galt bevis: La n være et vilkårlig naturlig tall, for eksempel 4. Da er n² = 4² ≥ 4 = n. QED

Viktig poeng: P(c) → ∀xP(x) er ikke tautologi!

Moteksempel: La domenet være R, P være predikatet positiv og c = 2.

(9)

Slutningsregler med ∃ : 1.5-Tabell 2

Regel Navn

∃xP(x)

∴ P(c) for en eller annen c Eksistensiell instansiering P(c) for en eller annen c

∴ ∃xP(x) Eksistensiell generalisering

(10)

Vanlig feil med ∃ : nn den!

Argument

∃x(P(x) → Q(x))

∃x(Q(x) → R(x))

∴ ∃x(P(x) → R(x)) Galt bevis:

1. ∃x(P(x) → Q(x)) Premiss 2. ∃x(Q(x) → R(x)) Premiss

3. P(c) → Q(c) Eks. inst. fra 1.

4. Q(c) → R(c) Eks. inst. fra 2.

5. P(c) → R(c) Hyp. syll. fra 3. og 4.

6. ∃x(P(x) → R(x)) Ekst. gener. fra 5.

Hvor er feilen?

(11)

Morlille er en sten

MONTANUS: Morlille, jeg vil gjøre jer til en sten.

NILLE: Ja, snakk; det er enda mer kunstig.

MONTANUS: Nu skal I få dette å høre: En sten kan ikke y.

NILLE: Nei; det er visst nok, unntatt man kaster den.

MONTANUS: I kan ikke y.

NILLE: Det er og sant.

MONTANUS: Ergo er Morlille en sten. (Nille gråter.) Hvorfor gråter Morlille?

NILLE: Akk, jeg er så bange at jeg blir til sten. Mine ben begynner alt å bli kalde.

(12)

Argument til Morlille er en sten

I Domene alle ting i verden (inkludert mennesker)

I m morlille

I F(x) x kan y

I S(x) x er en sten

∀x(S(x) → ¬F (x))

¬F(m)

∴ S(m)

Ikke gyldig!

Gyldig del: Universell instansiering

∀x(S(x) → ¬F (x))

∴ S(m) → ¬F(m)

(13)

Feilslutningen i Morlille er en sten

S(m) → ¬F(m)

¬F(m)

∴ S(m)

Som i Eks. 10 i 1.4: ikke gyldig å si at p → q q

∴ p

Feilslutningen av å hevde konklusjonen

(14)

Morlille er ingen sten

MONTANUS: Gi jer tilfreds, Morlille! Jeg skal straks gjøre jer til menneske igjen. En sten kan ikke tenke eller tale.

NILLE: Det er sant. Jeg vet ikke om den kan tenke, men tale kan den ikke.

MONTANUS: Morlille kan tale.

NILLE: Ja, gudskjelov, som en stakkars bondekone kan jeg tale.

MONTANUS: Godt. Ergo er Morlille ingen sten.

NILLE: Akk, det gjorde godt, nu kommer jeg meg igjen.

Det må sannelig sterke hoder til å studere, jeg vet ikke hvordan deres hjerne kan holde det ut.

(15)

Argument til morlille er ikke en sten, I

I m morlille

I S(x) x er en sten

I Q(x) x kan tale

∀x(S(x) → ¬Q(x)) Q(m)

∴ ¬S(m)

Universell modus tollens

(16)

Bevis

1. ∀x(S(x) → ¬Q(x)) Premiss

2. S(m) → ¬Q(m) Univ. instansiering

3. Q(m) Premiss

4. Q(m) ≡ ¬(¬Q(m)) Dobbel negasjon

5. ¬S(m) Mod. tollens fra 2. og 4.

(17)

Argument til morlille er ikke en sten, II

I m morlille

I S(x) x er en sten

I Q(x) x kan tale

I P(x) x kan tenke

∀x(S(x) → ¬(P(x) ∨ Q(x)) Q(m)

∴ ¬S(m)

(18)

Bevis

1. ∀x(S(x) → ¬(P(x) ∨ Q(x)) Premiss

2. S(m) → ¬(P(m) ∨ Q(m)) Univ. instansiering 3. ¬(P(m) ∨ Q(m))

≡ ¬P(m) ∧ ¬Q(m) De Morgan 4. S(m) → ¬P(m) ∧ ¬Q(m) 2. og 3.

5. ¬P(m) ∧ ¬Q(m) → ¬Q(m) Simplisering

6. S(m) → ¬Q(m) Hyp. syll. fra 4. og 5.

7. Q(m) Premiss

8. Q(m) ≡ ¬(¬Q(m)) Dobbel negasjon

9. ¬S(m) Mod. tollens fra 6. og 8.

(19)

Annet eksempel: gyldig eller ikke?

I Regnfulle dager gjør at hager gror

I Hager gror ikke dersom det ikke er varmt

I Det regner alltid når det ikke er varmt

I Derfor, om det ikke er varmt, så er det varmt

I r det regner

I g hager gror

I v det er varmt

Argument:

r → g

¬v → ¬g

¬v → r

∴ ¬v → v Tas på tavlen.

(20)

Annet eksempel: Den som drikker er lykksalig

MONTANUS: (...) Hør, farlille, vil I tro at den som drikker vel, er lykksalig?

JEPPE: Jeg tror snarere at han er ulykksalig, ti man kan drikke både forstand og penger bort.

MONTANUS: Jeg vil bevise at han er lykksalig.

Qvicunque bene bibit, bene dormit . . . Nei, det er sant, I forstå ikke latin, jeg må si det på dansk. Den som

drikker vel, sover gjeme vel, er det ikke sant?

JEPPE: Det er sant nok. Når jeg har en halv rus, sover jeg som en hest.

MONTANUS: Den som sover vel, synder ikke, er ikke det også sant?

JEPPE: Jo, det er sant nok. Så lenge man sover, synder man ikke.

MONTANUS: Den som ikke synder, er lykksalig.

JEPPE: Det er og sant.

MONTANUS: Ergo, den som drikker vel, er lykksalig.

(21)

Argument til Den som drikker er lykksalig

I p man drikker

I q man sover

I r man synder

I s man er lykksalig p → q

q → ¬r

¬r → s

∴ p → s

To ganger hypotetisk syllogisme