Utsagnslogikk

Et utsagn: En setning som er enten sann eller usann. (har ingenting å si om du selv vet om den er sann eller usann)

Eksempler:
$3+2=5$
$1+1=3$
Det finnes uendelig mange tall
Jeg liker heavy metal

setninger som ikke er utsagn:
3+2
2n+1=7 (sannheten avhenger av n)

Et predikat: Setning som avhenger av variabel (eller flere variabler) for å være sann/usann.
For hvert valg av variabel(eller variablene) skal vi ha et utsagn

Predikat: $Q(n):2n+1=7\forall n\in \mathbb{N}$
$Q(3)$ er sann, $Q(4)$ er usann.

konnektiver

Operasjon på/mellom utsagn
$\neg$ negasion (MKneg))
$\wedge$ og (MKland)
$\vee$ eller (MKlor)
$⟹$ impliserer (MK=>)
$⟸$ implisert av (MKimpliedby)
$\iff$ ekvivalent med (MK<—>)

Negasjon: Hvis $P$ er sann, så er $\neg P$ usann. Hvis $\neg P$ er sann, så er $P$ sann.
$\neg \neg P=P$

Og: $P\wedge Q$ er sant hvis og bare hvis både $P$ og $Q$ er sanne
$\neg (P\wedge Q)$ er sann *hvis og bare hvis både $P$ og $Q$ er usanne

Eller: $P\vee Q$ er sant hvis $P$ eller $Q$ eller $P\wedge Q$ er sanne

$P$	$Q$	$P\wedge Q$
S	S	S
S	U	U
U	S	U
U	U	U

P	Q	$P\vee Q$
S	S	S
U	S	S
S	U	S
U	U	U

Implikasjon

dersom $Q$ alltid er sann når $P$ er sann, så $P⟹Q$
“Jeg har en hundrelapp $⟹$ jeg har råd til en is”

Pass på hvilken vei pilen går. Det minst generelle impliserer ikke det mer generelle.

“Hvis P er usann, så kan vi egentlig ikke si noe om Q er det som egentlig står her”
fordi implikasjonen sier hva vi kan utlede dersom P er sant

Fra kalkulus:
Implikasjon: Vi påstår P, og at $P⟹Q$, Q er sant.
Dersom vi fra P kan utlede Q:$P⟹Q$

“Q er minst like sann som P”

Sannhetstabell:

P	Q	$P⟹Q$
U	U	S
U	S	S
S	U	U
S	S	S

Sannhetsverdi er uavhengig av veien mellom P og Q…
“Alle synes dette er rart
Farris, men bare på torsdager osv.

Men hva er negasjonen av implikasjon?

Ekvivalens

$P⟹Q\wedge Q⟹P$
fill in the blanks!

P	Q	$P\iff Q$	$P⟹Q$	$Q⟹P$	$(P⟹Q)\wedge (P⟸Q)$
S	S
U	S
S	U
U	U
dont be suspicious, dont be suspicious

De Morgans lover for utsagn

$\neg (P\wedge Q)=\neg P\vee \neg Q$
Løs opp parentesen, og snu konnektivet!
$(A\cap B{)}^C=A^C\cup B^C$

$\neg (P\vee Q)=\neg P\wedge \neg P$

Sammenheng med De Morgan for mengder:
$P\leftrightarrow A$
$Q\leftrightarrow B$
$\neg {\leftrightarrow }^C$
$\wedge \leftrightarrow \cap$
$\vee \leftrightarrow \cup$

Bevises ved sannhetstabell. Det gidder jeg ikke.

Det ingen sa til oss

$P⟹Q\equiv \neg P\vee Q$
$\neg (P⟹Q)=\neg P\wedge Q$

Distributivitet:
$P\wedge (Q\vee R)=(P\wedge Q)\vee (P\wedge R)$
$P\wedge (Q\vee R)=(P\wedge Q)\vee (P\wedge R)$