1.3 Logik

Definition

En utsaga är ett påstående som kan vara sant eller falskt men inte bägge delarna.
Ex:
a) 3 är ett heltal
sant - utsaga
b) $\pi$ är större än 3
sant - utsaga
c) $4\times 7=47$
falskt - utsaga
d) Det finns intelegent liv i andra galaxer
varken sant eller falskt - ej utsaga

Logiska konnektiver

$p,q$ är utsagor
$\neg p$ - “icke p” - sant om $p$ är falskt
ex.
$p:\sqrt{2}$ är ett rationellt tal, falskt
$\neg p:\sqrt{2}$ är inte ett rationellt tal, sant

$p\vee q$ - “p eller q” - sant om minst en utsaga är sann
ex.
$p:$ det är sol
$q:$ det regnar
$p\vee q:$ det är sol eller regnar

$p\wedge q$ - “p och q” - sant om båda är sanna
ex.
$p:$ det är sol
$q:$ det regnar
$p\wedge q:$ det är sol och regnar samtidigt

$p\Rightarrow q$ - “p medför q” - om p är sant är q också det

• “p implicerar q”
• “om p så q”
• “p är ett tillräckligt vilkor för q”
• “q är ett nödvändigt vilkor för p”

$p\iff q$ - “p ekvivalent med q”

• “p är sant och endast om q”
• “p omm q”
• “p iff q”

Ex:
a)
$p:2x-5=7$
$q:x=6$
$p\iff q$ b)
$p:x=2$
$q:x^2=4$
$p\Rightarrow q$
c)
$p:x=2\vee x=-2$
$q:x^2=4$
$p\iff q$
d)
$p:x^2\ge 4\wedge x<0$
$q:x\le -2$
$q\Rightarrow p$
$p\Rightarrow q$
$p\iff q$

Det gäller att

I. $\neg (\neg p)=p$
II. $p\to q\iff \neg p\vee q$
III. $(p\to q)\wedge (q\to p)\iff p\leftrightarrow q$

Kontraposition

$(p\to q)\iff (\neg q\to \neg p)$
vid negation av båda vänder medförelsen

Ex: a)
$p:$ Jag är hemma
$q:$ Lampan är tänd
$p\to q:$ om jag är hemma så är lampan tänd
$\neg q\to \neg p:$ om lampan är släckt är jag inte hemma
$p\to q\iff \neg p\vee q:$ Jag är inte hemma eller lampan är tänd
$\neg p:$ sant (inte hemma) $\Rightarrow$ lampan kanske lyser
$\neg p:$ falskt (hemma) $\Rightarrow$ lampan måste lysa

Bevismetoder

I. Direkta bevis (Konstruktiva)
II. Motbevis (Mot exempel)
III. Indirekta bevis
a) Kontrapositiva bevis
b) Motsägelsebevis (bevisa att motsattsen inte kan stämma)

Exempel

I. Direkt bevis

Notera att:

$1=1^2-0^2$
$3=2^2-1^2$
$5=3^2-2^2$

Påstående:

Varje udda heltal kan skrivas som differansen mellan två efterföljande kvadrater.

Notera att:

Jämnt heltal kan skrivas som $2k,k\in \mathbb{Z}$
Och varje udda heltal som $2k+1,k\in \mathbb{Z}$

Bevis:

Ett godtyckligt udda heltal:
$2k+1=2k+1+k^2-k^2$
$=(k^2+2k+1^2)-1^2$
$=(k+1{)}^2-k^2$

II. Motbevis

Notera att:

$31=primtal$
$331=primtal$
$3331=primtal$
$33331=primtal$
$333331=primtal$

Påstående:

Varje tal på formen $\mathrm{3..31}$ är primtal

Bevis:

Vi prövar:

$333331=primtal$
$3333331=primtal$
$33333331=primtal$
$333333331=17\ast 19607843$

III. Indirekta bevis

a) Kontrapositiva bevis

Notera att:

$n^{2=4}\iff n=\pm 2$
$n^2=16\iff n=\pm 4$
$n^2=36\iff n=\pm 6$

Påstående:

Om $n^2$ är ett jämnt heltal så är även $n$ ett jämnt heltal

Bevis:

Låt $p$ och $q$ beteckna påståendena $p:n^2$ är ett jämnt heltal $q:n$ är ett jämnt heltal vi vill visa $p\Rightarrow q$

visa istället att $\neg q\Rightarrow \neg p$
(Kontrapositon)

$\neg q:n$ är ett udda heltal $\neg p:n^2$ är ett udda heltal då $n=2k+1,k\in \mathbb{Z}$ $n^2=(2k^2+1{)}^2=(2k{)}^2+2\ast 2k+1^2$
$=4k^2+4k+1$
$=2(2k^2+2k)+1=udda=\neg p$
parantesen ger heltal, heltal gånger 2 blir jämnt, plus ett blir udda Vi har visat: $\neg q\to \neg p\iff p\to q$

b) Motsägelsebevis

Påstående;

Det finns inget rationellt tal $a$, dvs $a=\frac{m}{n},m\in \mathbb{Z},n\in \mathbb{N}$, så att $a^2=2$

Bevis:

Antag motsattsen $\neg p:$ det finns heltal $m$ och $n$ utan gemensam faktor så att $a^2=\frac{m^2}{n^2}=2$
$\Rightarrow m^2=2n^2:m^2$ är jämt $\Rightarrow m$ är jämnt heltal (enligt tidigare) $m=2k,k\in \mathbb{Z}$

$m^2=(2k{)}^2=4k^2$ $\frac{m^2}{n^2}=2$ ger $4k^2=2n^2$ $n^2=2k^2$ $\Rightarrow n$ är ett jämnt heltal (enligt tidigare) $n=2l$

$a=\frac{m}{n}=\frac{2k}{2l}$ (gemensam faktor ger orimligt enligt antagandet) $\neg p:$ falskt $\Rightarrow p:$ sant