Bevis

Uj, den var lurig. Jag är med på att ruta 1 i vänstra kolumnen svarar mot ruta 6 högra kolumnen. Jag är också med på att nr 3, 4 och 5 i högra kolumnen kan strykas från kandidaterna.

Men vilken av 1 och 2 i högra kolumnen är indirekt och vilken är motsägelse? Jag är böjd att hålla med ditt svar, men är inte helt hundra.

Ärligt talat har jag ingen aning om vad jag gjort. Vi har inte riktigt lärt oss detta heller så. 

Jag tror du gissat rätt. Tur är bättre än skicklighet.

PS Vi kan väl kalla varianten ickeQ —> ickeP för ett indirekt bevis. Det är ju ekvivalent med P—>Q.

Motsägelsebeviset bygger på att om inte P—>Q vore sant så skulle vi stå inför en orimlighet. Ett vanligt exempel är beviset för att roten ur 2 är irrationellt. Man bevisar det genom att visa att ifall det vore rationellt så skulle vi få tal som vore både jämna och udda vilket inte går. Alltså måste det vara irrationellt. 

Ok, tack för svaren. 

Funderade på olika bevistyper. Egentligen tycker jag rutorna missar något. Vi ska bevisa ”Om P så Q”.

(1) Vi börjar med förutsättningarna i P och letar oss på olika stigar fram till Q. Det är det vanliga sättet att bevisa påståenden. Direkt bevis känna som en bra term.

(2) Vi börjar med att förutsätta att Q är falskt. Sedan visar vi att i så fall är P falskt. Då följer ”om P så Q”. Vill någon kalla det för ett indirekt bevis, så gärna för mig.

(3) Nu har vi motsägelsebeviset. Men när jag tänker efter så har jag sällan mött det när det gäller ”om P så Q”. Ett känt bevis är från Euklides. Han påstod

Det finns hur många primtal som helst.  

I beviset antar han att påståendet är falskt. Då finns det ett största primtal. Sedan visar han att det i så fall finns ett ännu större primtal. Motsägelse! Alltså är påståendet sant.

Men tittar vi på påståendet ”det finns hur många primtal som helst”, så är det inte uppbyggt på formen ”Om P så Q”. Man kan eventuellt formulera om det, t ex så här:

P: a är ett tal

Q: Det finns primtal som är större än a.

Men det tycker jag känns konstlat. För att ta ett mer banalt exempel: Jag påstår att det finns högst 250 orter i Sverige med mer än 50 000 invånare. Jag visa att det är sant genom att anta att om det skulle vara fler än 249 orter med 50 000 invånare så skulle Sveriges folkmängd vara över tolv och en halv miljon, vilket vi vet att det inte är.

Men hur formulerar vi påståendet ”det finns högst 250 orter i Sverige med 50 tusen invånare” på formen ”om P så Q”? Det känns onaturligt, ”Om Sverige är ett land så…”, nej det blir inte bra. 

Ett motsägelsebevis av ett påstående $R$ är att anta $\neg R$ och visa att leder till något falskt, dvs. man visar att $\neg R\to\bot$. Detta görs ofta genom att $\neg R$ medför både att $S$ och $\neg S$, för något påstående $S$. Man härleder en motsägelse.

I detta fall är vårt påstående $R=P\to Q$. Vi antar att detta är falskt, dvs.

$\neg(P\to Q)$, vilket är ekvivalent med $P\land \neg Q$.

Man kan tänka att en implikation $P\to Q$ är falsk om och endast om $P$ är sann och $Q$ är falsk.

Ett indirekt bevis är antingen ett motsägelsebevis eller ett kontrapositivt bevis (proof of the contrapositive). Alla motsägelsebevis är alltså även indirekta bevis. Jag antar att det som uppgiften menar med "indirekt bevis" är det kontrapositiva beviset. Denna typ av bevis är bara relevant när man ska visa implikationer. Det ser ut som följande:

Om vi ska visa en implikation $P\to Q$, kan vi istället visa dess kontrapositiva version $\neg Q\to \neg P$. Det fungerar eftersom dessa två formler är ekvivalenta.

Tack Gustaf, då var jag inte helt ute i skogen iaf.