Logikk, motsigelsesbevis

[kaaasen]

Hei!

 

Jeg vet ikke om det er noen som har hatt logikk som fag her, men jeg håper på at det finnes noen her som kan hjelpe meg.

 

Jeg sitter med en oppgave jeg har hvor jeg skal bruke motsigelsesbevis til å bevise at en påstand er sann. Påstanden er som følger:

 

Bevis påstanden «Hvis (X → Y) og (Y → Z) er sanne, så er (X → Z) sann»

 

Jeg har sittet lenge med oppgaven, men kjører meg fast hver gang, fordi formelen MÅ være sann, men jeg finner ingen motsigelser.

 

Dvs. at hvis jeg setter X som sann så må Y og Z være sanne, men det at Y og Z er sanne gir meg ingen motsigelser. Har vel såvidt jeg vet vært innom alle valuasjoner, og alle valuasjoner gjør jo formelen sann - uten å presentere noen motsigelser for meg :S

[nicho_meg]

Så lenge påstanden er sann finner du selvsagt ingen motsigelse. Du må anta at påstanden ikke er sann for å finne motsigelsen. Den finner du først og da vet du, siden den nye påstanden er feil, at den originale påstanden er riktig.

 

Edit: Euclid sitt bevis på at det ikke finnes et største primtall er vel kanskje det beste eksempelet på selvmotsigelsesbevis: http://primes.utm.edu/notes/proofs/infinite/euclids.html

Påstanden er at det ikke finnes et største primtall. Dermed kan man påstå det motsatte (at det finnes et største primtall) og bevise at dette fører til en selvmotsigelse.

Endret 11. september 2014 av nicho_meg

[kaaasen]

Takk for svar!

 

Men hele poenget er vel å finne en motsigelse?

I eksemplet som er nevnt i boken står det (jeg skriver bare et par av setningene, så konteksten blir litt feil):

"Bevis at formelen (P → Q) v (Q → P) er sann for alle valuasjoner."

 

Hvorpå konklusjonen i eksemplet blir "Det er ikke mulig at en valuasjon gjør P både sann og usann, og vi har en motsigelse. Vi kan konkludere med at (P→ Q) v (Q→ P) er sann for alle valuasjoner.

 

Det er dette som forvirrer meg, for å være ærlig...

 

edit; jeg er selvfølgelig klar over at eksempelet som brukes i boken og oppgaven jeg prøver å løse er forskjellig fra hverandre, men i eksempelet har jo forfatteren klart å finne en motsigelse for å bevise at noe er sant, akkurat som jeg er på jakt etter.

Endret 11. september 2014 av kimbert007

[nicho_meg]

Du kan påstå at(x->z) ikke er sann når (x->y) og (y->z) og du vil dermed få en selvmotsigelse.

[Aleks855]

 

Bevis påstanden «Hvis (X → Y) og (Y → Z) er sanne, så er (X → Z) sann»

 

Siden TeXen på dette forumet er utdatert, så tar vi det som bilde. Antar du skal bruke logikk-reglene for å vise det.

 

http://rasch-uo.no/eksempler/logikk-motsigelsesbevis1.png

[Aleks855]

Du kan påstå at(x->z) ikke er sann når (x->y) og (y->z) og du vil dermed få en selvmotsigelse.

 

Det er jo bare en omformulering av oppgaven. Ikke et bevis

[nicho_meg]

 

Du kan påstå at(x->z) ikke er sann når (x->y) og (y->z) og du vil dermed få en selvmotsigelse.

 

Det er jo bare en omformulering av oppgaven. Ikke et bevis

 

Joda, det var bare et første steg, før man setter opp sannhetstabellen og får et selvmotsigelsesbevis. Målet med oppgaven var et bevis vha selvmotsigelse, ikke eleganse.

Jeg går stort sett for det enkle over det elegante, men løsningen din er penere.

[Elefantmesteren]

(X → Y) er sann i to tilfeller:

X er usann: (X → Z) er sann

X og Y er sann: dette impliserer at Z er sann for at (Y → Z) skal være sann: (X → Z) er sann

 

derfor en selvmotsigelse å si at (X → Z) er usann når de to andre er sann

[Aleks855]

(X → Y) er sann i to tilfeller:

X er usann: (X → Z) er sann

X og Y er sann: dette impliserer at Z er sann for at (Y → Z) skal være sann: (X → Z) er sann

 

derfor en selvmotsigelse å si at (X → Z) er usann når de to andre er sann

 

Dette er ikke et "bevis ved selvmotsigelse". Det er bare en omformulering av påstanden man skal bevise.

[ærligøs]

Jeg kan dette bare på engelsk, så strever litt med norske uttrykk.

 

 

 

 

1. X → Y

 

2. Y → Z / X → Z

 

3. -( X → Z) Antagelse indirekte bevis (motsigelsesbevis)

 

4. -(-X v Z) 3, Material implikasjon

 

5. - -X & -Z 4, De Morgan’s regel

 

6. X & -Z 5, Dobbelnegasjon

 

7. X 6, Simplifikasjon

 

8. Y 1,7, Modus Ponens

 

9. -Z & X 6, Kommutasjon

 

10. -Z 9. Simplifikasjon

 

11. -Y 2, 10, Modus Tollens

 

12. Y & -Y 8,11, Konjunksjon

 

13. - -( X → Z) 3-12, Motsigelsesbevis

 

14. ( X → Z) 13, Dobbelnegasjon

 

Kontradiksjonen har vi i linje 8 og 11.

 

edit: rettet en feil (håper det ikke er flere)

 

Endret 12. september 2014 av ærligøs