Övning 1: Konstruera en sanningstavla för uttrycket ¬p ∨ (p ∧ q).

p | q | ¬p | p∧q | ¬p∨(p∧q) T | T | F | T | T T | F | F | F | F F | T | T | F | T F | F | T | F | T Svar: Uttrycket är sant utom när p=T och q=F

Grundläggande

Matematisk logik

Propositionell logik, sanningstavlor, logiska operatorer och bevis.

proposition konjunktion disjunktion implikation ekvivalens negation

Logik är matematikens språk för att uttrycka och analysera påståenden. Precis som vi i vardagen säger 'om det regnar så blir marken blöt', använder matematiken logik för att göra exakta resonemang. Logik hjälper oss att skilja mellan giltiga och ogiltiga argument, och är grunden för allt från datorprogrammering till artificiell intelligens.

Fördjupning

Propositionell logik behandlar sammansatta påståenden byggda från enkla propositioner med hjälp av logiska konnektiv som 'och', 'eller', 'inte' och 'om...så'. Genom sanningstavlor kan vi systematiskt analysera när sammansatta påståenden är sanna eller falska, och genom logiska lagar kan vi transformera uttryck till enklare former.

Propositioner och sanningsvärden

En proposition är ett påstående som antingen är sant eller falskt, men inte båda. Vi betecknar propositioner med bokstäver som p, q, r och använder T (true) för sant och F (false) för falskt. Alla påståenden är inte propositioner - frågor och kommandon har inga sanningsvärden.

Exempel på propositioner

Propositioner:

· p: 'Stockholm är Sveriges huvudstad' (T)

· q: '2 + 2 = 5' (F)

· r: 'x > 10' (beror på x:s värde)

Ej propositioner:

· 'Vad heter du?' (fråga)

· 'Stäng dörren!' (kommando)

· 'Detta påstående är falskt' (paradox)

Formal definition av proposition och sanningsvärden

Logiska konnektiv

Logiska konnektiv låter oss bygga komplexa påståenden från enkla. De fem grundläggande konnektiven är negation (¬), konjunktion (∧), disjunktion (∨), implikation (→) och ekvivalens (↔). Varje konnektiv har en exakt definition genom sanningstavlor.

Negation: \negp är sant när p är falskt och vice versa

Konjunktion: p \land q är sant endast när både p och q är sanna

Disjunktion: p \lor q är sant när minst en av p eller q är sant

Implikation: p \to q är falskt endast när p är sant och q är falskt

Ekvivalens: p \leftrightarrow q är sant när p och q har samma sanningsvärde

Sanningstavlor

En sanningstavla visar sanningsvärdet för en sammansatt proposition för alla möjliga kombinationer av sanningsvärden för dess komponenter. För n propositioner behövs 2^n rader i sanningstavlan. Sanningstavlor är det grundläggande verktyget för att analysera logiska uttryck.

Sanningstavla för de grundläggande logiska konnektiven

Konstruktion av sanningstavla

Analysera uttrycket (p ∧ q) → (p ∨ q)

Identifiera variabler: p och q (2 variabler → 4 rader)

Beräkna deluttryck: p ∧ q och p ∨ q

Beräkna huvuduttrycket med implikation

Resultatet visar att uttrycket alltid är sant (tautologi)

Sanningstavla för det sammansatta uttrycket (p ∧ q) → (p ∨ q)

Tautologier, kontradiktioner och kontingenser

En tautologi är ett uttryck som alltid är sant oavsett sanningsvärdena för dess komponenter. En kontradiktion är alltid falsk. En kontingent är varken tautologi eller kontradiktion - dess sanningsvärde beror på komponenternas värden.

Exempel på tautologi: p \lor \negp (lagen om utesluten tredeman)

Exempel på kontradiktion: p \land \negp

Identifiering av logiska typer

p → p: Sanningstavla visar T för alla värden → tautologi

p ∧ ¬p: Sanningstavla visar F för alla värden → kontradiktion

p → q: Sanningstavla visar både T och F → kontingent

Logiska lagar och ekvivalenser

Logiska lagar är tautologier som visar hur vi kan transformera logiska uttryck till ekvivalenta former. De viktigaste lagarna inkluderar kommutativa, associativa och distributiva lagar, samt De Morgans lagar som relaterar negation till konjunktion och disjunktion.

Kommutativa lagar: p \land q \equiv q \land p och p \lor q \equiv q \lor p

Associativa lagar för gruppering av operationer

Distributiva lagar: p \land (q \lor r) \equiv (p \land q) \lor (p \land r)

De Morgans lagar: \neg(p \land q) \equiv \negp \lor \negq och \neg(p \lor q) \equiv \negp \land \negq

Förenklig av logiska uttryck

Förenkla ¬(p ∧ ¬q) ∨ (¬p ∧ q)

Använd De Morgans lag: (¬p ∨ ¬¬q) ∨ (¬p ∧ q)

Förenkla dubbel negation: (¬p ∨ q) ∨ (¬p ∧ q)

Använd distributivitet: ¬p ∨ (q ∨ (¬p ∧ q))

Absorption: ¬p ∨ q

Argument och giltighet

Ett argument består av premisser (antaganden) och en konklusion. Ett argument är giltigt om konklusionen logiskt följer från premisserna - det vill säga, om premisserna är sanna så måste konklusionen vara sann. Giltighet handlar om logisk struktur, inte om sanningshalten i premisserna.

Definition av giltigt argument: (P₁ \land P₂ \land ... \land Pₙ) \to C är en tautologi

Modus ponens - ett giltigt argumentschema

Premiss 1: p → q (om p så q)

Premiss 2: p

Konklusion: q

Detta är giltigt eftersom ((p → q) ∧ p) → q är en tautologi

Bekräftelse av konsekvensen - ogiltigt argument

Premiss 1: p → q

Premiss 2: q

Konklusion: p

Detta är ogiltigt: ((p → q) ∧ q) → p är inte en tautologi

Motexempel: 'Om det regnar blir marken blöt' + 'Marken är blöt' ⇏ 'Det regnar'

Vanliga misstag

❌ Förväxla 'eller' inklusivt och exklusivt

I logik är 'eller' (∨) inklusivt - p ∨ q är sant även när båda är sanna

Exempel: 'Jag äter kött eller fisk' kan betyda båda, men 'p ∨ q' inkluderar alltid båda möjligheterna

❌ Misstolka implikation

p → q säger inget om vad som händer när p är falskt

Exempel: 'Om det regnar så blir marken blöt' säger inget om vad som händer när det inte regnar

❌ Felaktig negation av kvantifierade påståenden

Negation av 'alla' ger 'minst en inte', inte 'inga'

Exempel: ¬(alla hundar är bruna) = 'minst en hund är inte brun', inte 'inga hundar är bruna'

Tillämpningar

Datorprogrammering

Booleska uttryck i if-satser och loopar bygger direkt på propositionell logik

Exempel: if (x > 0 && y < 10) motsvarar (x > 0) ∧ (y < 10)

Digitalkretsar

Logiska grindar implementerar logiska operationer i hårdvara

Exempel: AND-grind implementerar konjunktion, OR-grind implementerar disjunktion

Artificiell intelligens

Kunskapsrepresentation och automatisk slutledning bygger på logik

Exempel: Expertystem använder if-then regler för att dra slutsatser från fakta

Övningar

1 Lätt

Konstruera en sanningstavla för uttrycket ¬p ∨ (p ∧ q).

Tips

Börja med grundvariablerna p och q, beräkna sedan deluttryck

Visa facit

p | q | ¬p | p∧q | ¬p∨(p∧q)
T | T | F | T | T
T | F | F | F | F
F | T | T | F | T
F | F | T | F | T

Svar: Uttrycket är sant utom när p=T och q=F

2 Medel

Använd De Morgans lag för att förenkla ¬(p ∧ ¬q).

Tips

De Morgans lag transformerar negation av konjunktion

Visa facit

Använd De Morgans lag: ¬(p ∧ ¬q) = ¬p ∨ ¬(¬q)
Förenkla dubbel negation: ¬p ∨ q

Svar: ¬p ∨ q

3 Medel

Avgör om argumentet är giltigt: 'Om alla katter är djur och Fluffy är en katt, då är Fluffy ett djur.'

Tips

Formalisera argumentet och kontrollera om det följer ett giltigt schema

Visa facit

Låt p = 'Fluffy är en katt', q = 'Fluffy är ett djur'
Premiss 1: p → q (alla katter är djur)
Premiss 2: p (Fluffy är en katt)
Konklusion: q (Fluffy är ett djur)
Detta följer modus ponens och är giltigt

Svar: Argumentet är giltigt (modus ponens)

Sammanfattning

Propositionell logik ger oss exakta verktyg för att analysera argument och påståenden. Genom logiska konnektiv (¬, ∧, ∨, →, ↔) kan vi bygga komplexa uttryck från enkla propositioner. Sanningstavlor låter oss systematiskt analysera dessa uttryck, medan logiska lagar som De Morgans lagar hjälper oss att förenkla dem. Begrippen tautologi, kontradiktion och giltiga argument är fundamentala för matematiskt resonemang.