Medel

Predikatlogik

Kvantifikatorer, predikat och logisk slutledning i första ordningens logik.

predikat kvantifikator universell existentiell domän fria variabler

Propositionslogik räcker inte för att hantera många vardagliga påståenden. Säg att du vill uttrycka: 'Alla katter är djur' eller 'Det finns någon som är längre än 2 meter'. Propositionslogik kan bara säga om enskilda påståenden är sanna eller falska, men kan inte hantera 'alla' eller 'det finns någon'. Det är här predikatlogik kommer in - den utökar logiken med kvantifikatorer som låter oss resonera om grupper och egenskaper. Istället för bara 'P är sant' kan vi säga 'för alla x gäller att P(x)' eller 'det finns ett x sådant att P(x)'. Detta öppnar upp för mycket mer nyanserat och kraftfullt logiskt resonemang.

Fördjupning

Predikatlogik (första ordningens logik) utökar propositionslogik genom att introducera predikat, variabler, kvantifikatorer och funktioner. Medan propositionslogik arbetar med atomära påståenden, kan predikatlogik uttrycka relationer mellan objekt och egenskaper hos objekt. Vi använder universell kvantifikator (∀) för 'alla' och existentiell kvantifikator (∃) för 'det finns'. Predikat som P(x) kan läsas som 'x har egenskapen P' eller 'P gäller för x'. Detta system är tillräckligt kraftfullt för att formalisera nästan all matematik och många naturliga språk, men det finns även begränsningar som Gödels ofullständighetsteorem visar.

Predikat och variabler

I predikatlogik arbetar vi med objekt och deras egenskaper eller relationer. Ett predikat beskriver en egenskap eller relation som kan vara sann eller falsk för olika objekt.

Vad är ett predikat?

Ett predikat är som en funktion som returnerar sant eller falskt

P(x) kan betyda 'x är en primtal' eller 'x är röd'

R(x,y) kan betyda 'x är större än y' eller 'x älskar y'

Predikat blir propositioner när vi ersätter variabler med specifika objekt

Från vardagsspråk till predikat

Vardagsspråk: 'Stockholm är en huvudstad'

Predikat: H(Stockholm) där H(x) betyder 'x är en huvudstad'

Vardagsspråk: 'Alice är längre än Bob'

Predikat: L(Alice, Bob) där L(x,y) betyder 'x är längre än y'

Vardagsspråk: 'Alla hundar är djur'

Predikat: ∀x (H(x) → D(x)) där H(x) = 'x är en hund', D(x) = 'x är ett djur'

Variabler (x, y, z) representerar objekt i vår diskursdomän. Domänen är mängden av alla objekt vi talar om - det kan vara tal, personer, djur, etc.

Universell kvantifikator (∀)

Universell kvantifikator ∀ (läses 'för alla') används för att göra påståenden om alla objekt i domänen. ∀x P(x) betyder 'för alla x gäller P(x)'.

Grundläggande universell kvantifiering

∀x P(x) är sant om P(x) är sant för ALLA objekt i domänen

∀x P(x) är falskt om det finns NÅGOT objekt för vilket P(x) är falskt

Exempel: ∀x (x + 0 = x) i domänen av tal - alltid sant

Motexempel: ∀x (x > 5) i domänen av tal - falskt (t.ex. 3 > 5 är falskt)

Universell kvantifiering med implikation

∀x (P(x) → Q(x)) betyder 'alla P är också Q'

Exempel: ∀x (Hund(x) → Djur(x)) = 'Alla hundar är djur'

Detta är falskt endast om vi hittar en hund som inte är ett djur

Notera: Vi behöver inte ha några hundar alls för att påståendet ska vara sant

Illustration av hur universell kvantifiering fungerar med konkreta exempel från olika domäner

Existentiell kvantifikator (∃)

Existentiell kvantifikator ∃ (läses 'det finns') används för att göra påståenden om att minst ett objekt har en viss egenskap. ∃x P(x) betyder 'det finns (minst) ett x sådant att P(x)'.

Grundläggande existentiell kvantifiering

∃x P(x) är sant om P(x) är sant för MINST ETT objekt i domänen

∃x P(x) är falskt om P(x) är falskt för ALLA objekt i domänen

Exempel: ∃x (x > 100) i domänen av tal - sant (t.ex. 101 > 100)

Motexempel: ∃x (x < x) i domänen av tal - falskt (inget tal är mindre än sig själv)

Existentiell kvantifiering med konjunktion

∃x (P(x) ∧ Q(x)) betyder 'det finns något som är både P och Q'

Exempel: ∃x (Student(x) ∧ Programmerare(x)) = 'Det finns studenter som programmerar'

Detta kräver att vi hittar minst ett objekt som är både student OCH programmerare

Visuell representation av existentiell kvantifiering med exempel från olika sammanhang

Negation av kvantifikatorer

Att negera kvantifikatorer följer specifika regler som påminner om De Morgans lagar. Dessa regler är fundamentala för logiskt resonemang.

Negation av universell kvantifiering

¬∀x P(x) ≡ ∃x ¬P(x)

'Det är inte sant att alla har egenskapen P' = 'Det finns någon som inte har egenskapen P'

Exempel: ¬∀x (Student(x) → Smart(x))

≡ ∃x ¬(Student(x) → Smart(x))

≡ ∃x (Student(x) ∧ ¬Smart(x)) = 'Det finns en student som inte är smart'

Negation av existentiell kvantifiering

¬∃x P(x) ≡ ∀x ¬P(x)

'Det finns inte någon med egenskapen P' = 'Alla saknar egenskapen P'

Exempel: ¬∃x (Enhörning(x))

≡ ∀x ¬Enhörning(x) = 'Inga enhörningar finns' = 'Allt som finns är inte enhörningar'

Sammanfattning av negationsregler för kvantifikatorer med praktiska exempel

Flervariabler och kapslade kvantifikatorer

Verklig logisk komplexitet uppstår när vi kombinerar flera variabler och kvantifikatorer. Ordningen på kvantifikatorer är kritisk för betydelsen.

Ordning spelar roll

∀x ∃y L(x,y) betyder 'För alla x finns det ett y sådant att L(x,y)'

∃y ∀x L(x,y) betyder 'Det finns ett y sådant att för alla x gäller L(x,y)'

Exempel med L(x,y) = 'x älskar y':

∀x ∃y L(x,y) = 'Alla älskar någon' (alla har någon de älskar)

∃y ∀x L(x,y) = 'Någon älskas av alla' (det finns en person som alla älskar)

Matematiska exempel

∀x ∃y (y > x) = 'För varje tal finns ett större tal' (sant för reella tal)

∃y ∀x (y > x) = 'Det finns ett tal som är större än alla tal' (falskt för reella tal)

∀x ∀y ((x < y) → ∃z (x < z ∧ z < y)) = 'Mellan två olika tal finns alltid ett tredje' (täthet)

Visuell jämförelse av olika kvantifikatorordningar och deras betydelser

Funktioner och ekvivalens

Predikatlogik kan också innehålla funktioner som mappar objekt till andra objekt, samt ekvivalensrelationer för att uttrycka när två objekt är 'samma'.

Funktioner i predikatlogik

f(x) representerar 'funktionen f applicerad på x'

Exempel: förälder(x) = 'x:s förälder'

Vi kan skriva: ∀x (Människa(x) → Människa(förälder(x)))

Detta betyder: 'Alla människors föräldrar är också människor'

Ekvivalens och identitet

x = y betyder att x och y refererar till samma objekt

∀x (x = x) = 'Allt är identiskt med sig själv' (reflexivitet)

∀x ∀y ((x = y) → (y = x)) = 'Identitet är symmetrisk'

∀x ∀y ∀z (((x = y) ∧ (y = z)) → (x = z)) = 'Identitet är transitiv'

Illustration av hur funktioner och ekvivalensrelationer används i predikatlogik

Vanliga misstag

❌ Förväxla ordningen på kvantifikatorer

∀x ∃y P(x,y) betyder något helt annat än ∃y ∀x P(x,y)

Exempel: 'Alla har en favoritfärg' (∀x ∃y FavoritFärg(x,y)) vs 'Det finns en färg som alla tycker bäst om' (∃y ∀x FavoritFärg(x,y))

❌ Felaktig negation av kvantifikatorer

Studenter försöker negera kvantifikatorer utan att ändra dem, men ¬∀x P(x) ≠ ∀x ¬P(x)

Exempel: 'Inte alla studenter är smarta' är inte samma som 'Alla studenter är inte smarta'

❌ Glömma domän när man tolkar påståenden

Samma formella uttryck kan vara sant i en domän men falskt i en annan

Exempel: ∀x (x + 1 > x) är sant för tal men meningslöst för färger

❌ Förväxla ∀x (P(x) → Q(x)) med ∀x P(x) → ∀x Q(x)

Den första säger 'alla P är Q', den andra säger 'om alla är P så är alla Q'

Exempel: 'Alla hundar är djur' är inte samma som 'om alla är hundar så är alla djur'

Tillämpningar

Databasfrågspråk

SQL använder kvantifikatorer genom EXISTS, ALL och andra konstruktioner för att söka i databaser

Exempel: SELECT * FROM studenter WHERE EXISTS (SELECT * FROM kurser WHERE studenter.id = kurser.student_id AND kurs = 'Logik')

Programverifiering

Specifikationer av program använder predikatlogik för att beskriva vad program ska göra

Exempel: ∀i (0 ≤ i < array.length → array[i] ≥ 0) specifiserar att alla element i en array är icke-negativa

Matematik

Matematiska definitioner och påståenden uttrycks naturligt i predikatlogik

Exempel: Definition av kontinuitet: ∀ε>0 ∃δ>0 ∀x (|x-a|<δ → |f(x)-f(a)|<ε)

Artificiell intelligens

Kunskapsrepresentation och automatiskt resonemang bygger på predikatlogik

Exempel: ∀x (Fågel(x) ∧ ¬Pingvin(x) → KanFlyga(x)) representerar kunskap om fåglar

Naturlig språkprocessning

Datoröversättning och språkförståelse använder logiska representationer

Exempel: 'Alla studenter läser någon bok' → ∀x (Student(x) → ∃y (Bok(y) ∧ Läser(x,y)))

Övningar

1 Lätt

Översätt till predikatlogik: 'Alla katter är djur, men inte alla djur är katter'

Tips

Använd K(x) för 'x är en katt' och D(x) för 'x är ett djur'. Första delen är en universell implikation, andra delen en negerad universell implikation

Visa facit

Första delen: 'Alla katter är djur' = ∀x (K(x) → D(x))
Andra delen: 'Inte alla djur är katter' = ¬∀x (D(x) → K(x))
Förenkla andra delen: ¬∀x (D(x) → K(x)) ≡ ∃x ¬(D(x) → K(x)) ≡ ∃x (D(x) ∧ ¬K(x))
Slutresultat: ∀x (K(x) → D(x)) ∧ ∃x (D(x) ∧ ¬K(x))

Svar: ∀x (K(x) → D(x)) ∧ ¬∀x (D(x) → K(x)) vilket kan skrivas som ∀x (K(x) → D(x)) ∧ ∃x (D(x) ∧ ¬K(x))

2 Medel

Negera följande påstående och förenkla: ∀x (Student(x) → ∃y Tycker_om(x,y))

Tips

Använd negationsreglerna för kvantifikatorer steg för steg. Kom ihåg att ¬(P → Q) ≡ P ∧ ¬Q

Visa facit

Börja med: ¬∀x (Student(x) → ∃y Tycker_om(x,y))
Negera universell kvantifikator: ∃x ¬(Student(x) → ∃y Tycker_om(x,y))
Negera implikation: ∃x (Student(x) ∧ ¬∃y Tycker_om(x,y))
Negera existentiell kvantifikator: ∃x (Student(x) ∧ ∀y ¬Tycker_om(x,y))
Tolkning: 'Det finns en student som inte tycker om någon'

Svar: ∃x (Student(x) ∧ ∀y ¬Tycker_om(x,y))

3 Medel

Är följande två uttryck ekvivalenta? ∀x ∃y L(x,y) och ∃y ∀x L(x,y) där L(x,y) betyder 'x älskar y'

Tips

Tänk på vad varje uttryck säger och ge konkreta exempel eller motexempel

Visa facit

∀x ∃y L(x,y): 'Alla älskar någon' - varje person älskar minst en person
∃y ∀x L(x,y): 'Någon älskas av alla' - det finns en person som alla älskar
Det andra implicerar det första, men inte tvärtom
Motexempel: Om Alice älskar Bob och Bob älskar Clara, då är första sant men andra falskt
Det finns ingen person som båda Alice och Bob älskar

Svar: Nej, de är inte ekvivalenta. Det andra uttrycket är starkare än det första

4 Svår

Formalisera: 'Det finns en student som är smartare än alla andra studenter'

Tips

Du behöver existentiell kvantifiering för 'det finns en student' och universell för 'alla andra'. Tänk på hur du uttrycker 'andra'

Visa facit

Börja med existentiell kvantifiering: ∃x (Student(x) ∧ ...)
'smartare än alla andra' kräver universell kvantifiering över andra studenter
∀y ((Student(y) ∧ x ≠ y) → Smartare(x,y))
x ≠ y säkerställer att vi inte jämför studenten med sig själv
Slutresultat: ∃x (Student(x) ∧ ∀y ((Student(y) ∧ x ≠ y) → Smartare(x,y)))

Svar: ∃x (Student(x) ∧ ∀y ((Student(y) ∧ x ≠ y) → Smartare(x,y)))

5 Svår

Bevisa att ∀x ∀y P(x,y) ≡ ∀y ∀x P(x,y) (kvantifikatorer av samma typ kan byta plats)

Tips

Använd definitionerna av universell kvantifiering och visa att båda uttrycken har samma sanningsvärde

Visa facit

∀x ∀y P(x,y) är sant ⟺ för alla a,b gäller P(a,b)
∀y ∀x P(x,y) är sant ⟺ för alla b,a gäller P(a,b)
Eftersom vi kvantifierar över samma domän spelar ordningen ingen roll
Båda uttryck kräver att P(a,b) ska vara sant för alla möjliga par
Därför är de logiskt ekvivalenta

Svar: Båda uttryck är sanna om och endast om P(a,b) är sant för alla par (a,b) i domänen

Sammanfattning

Predikatlogik utökar propositionslogik med predikat, variabler och kvantifikatorer, vilket gör det möjligt att uttrycka påståenden om grupper och egenskaper. Universell kvantifikator (∀) uttrycker 'alla' medan existentiell kvantifikator (∃) uttrycker 'det finns'. Viktiga regler inkluderar negation av kvantifikatorer (¬∀x P(x) ≡ ∃x ¬P(x)) och att ordningen på kvantifikatorer spelar stor roll (∀x ∃y ≠ ∃y ∀x). Predikatlogik är grunden för matematik, databaser, programverifiering och AI-system. Behärskandet av kvantifikatorer och deras negation är essentiellt för logiskt resonemang och formell specification av system.