Övning 2: Negera påståendet ∀x ∃y P(x,y) och förenkla.

Negera universell kvantifikator: ¬∀x blir ∃x Negera existentiell kvantifikator: ¬∃y blir ∀y Negera predikatet: ¬P(x,y) Resultat: ∃x ∀y ¬P(x,y) Svar: ∃x ∀y ¬P(x,y)

Medel

Predikatlogik

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

predikat kvantifikator universell existentiell domän

Om propositionell logik är som att prata om hela meningar, så är predikatlogik som att titta inuti meningarna och se deras inre struktur. När vi säger 'alla hundar är djur' pratar vi inte bara om enskilda påståenden, utan om egenskaper som objekt kan ha och relationer mellan dem. Predikatlogik ger oss verktygen att analysera sådana påståenden exakt och systematiskt.

Fördjupning

Predikatlogik, eller första ordningens logik, utvidgar propositionell logik med kvantifikatorer (∀ och ∃) och predikat som beskriver egenskaper och relationer. Detta gör att vi kan formalisera påståenden om objekt i en domän och resonera om dem på ett exakt sätt. Predikatlogik är grunden för matematisk bevisföring och databaslogik.

Predikat och domäner

Ett predikat är en funktion som tar objekt som input och ger sanningsvärden som output. Till exempel kan P(x) betyda 'x är en primtal' eller R(x,y) kan betyda 'x är större än y'. Domänen är mängden av alla objekt vi diskuterar. Predikat låter oss beskriva egenskaper och relationer mellan objekt i domänen.

Definition av predikat: P(x₁, x₂, ..., xₙ) \to {sant, falskt}

Exempel på predikat

Domän: mängden av alla personer

· P(x): 'x är en student'

· Q(x): 'x är över 18 år'

· R(x,y): 'x är äldre än y'

· S(x,y,z): 'x introducerade y för z'

Evaluering:

· P(Anna) kan vara sant om Anna är student

· R(Anna, Bob) kan vara sant om Anna är äldre än Bob

Kvantifikatorer

Kvantifikatorer låter oss göra påståenden om hela grupper av objekt. Den universella kvantifikatorn ∀ betyder 'för alla' eller 'för varje', medan den existentiella kvantifikatorn ∃ betyder 'det finns' eller 'det existerar minst en'. Dessa är fundamentala för att uttrycka matematiska påståenden.

Universell kvantifikator: \forallx P(x) betyder 'för alla x gäller P(x)'

Existentiell kvantifikator: \existsx P(x) betyder 'det finns ett x sådant att P(x)'

Kvantifierade påståenden

∀x (P(x) → Q(x)): 'Alla studenter är över 18 år'

∃x (P(x) ∧ ¬Q(x)): 'Det finns en student som inte är över 18 år'

∀x ∃y R(x,y): 'För varje person finns det någon som är yngre'

∃x ∀y R(x,y): 'Det finns en person som är äldre än alla andra'

Visuell representation av kvantifikatorers innebörd och relationer

Negation av kvantifierade påståenden

Att negera kvantifierade påståenden följer specifika regler som är avgörande för korrekt matematisk slutledning. Negationen av 'alla' blir 'minst en inte', och negationen av 'det finns' blir 'inga'. Dessa regler är en utvidgning av De Morgans lagar till kvantifikatorer.

Negationsregler: \neg\forallx P(x) \equiv \existsx \negP(x) och \neg\existsx P(x) \equiv \forallx \negP(x)

Negation i praktiken

Påstående: 'Alla hundar gillar ben' = ∀x (Hund(x) → GillarBen(x))

Negation: ¬∀x (Hund(x) → GillarBen(x)) ≡ ∃x ¬(Hund(x) → GillarBen(x))

Förenkla implikation: ∃x (Hund(x) ∧ ¬GillarBen(x))

På svenska: 'Det finns en hund som inte gillar ben'

Bundna och fria variabler

I kvantifierade uttryck är variabler antingen bundna (av en kvantifikator) eller fria. En bunden variabel har sitt värde bestämt av kvantifikatorn, medan en fri variabel behöver tilldelas ett värde från domänen för att uttrycket ska få ett sanningsvärde.

Exempel på bundna och fria variabler i kvantifierade uttryck

Identifiering av variabler

I uttrycket ∀x (P(x) → Q(x,y)):

· x är bunden av ∀

· y är fri

I uttrycket ∃x (R(x,z) ∧ ∀y S(x,y)):

· x är bunden av ∃

· y är bunden av ∀

· z är fri

Komplexa kvantifikatoruttryck

Verkliga påståenden innehåller ofta flera kvantifikatorer som interagerar. Ordningen på kvantifikatorer är kritisk - ∀x ∃y P(x,y) betyder något helt annat än ∃y ∀x P(x,y). Att förstå dessa skillnader är avgörande för korrekt formalisering av matematiska påståenden.

Skillnaden mellan \forallx \existsy P(x,y) och \existsy \forallx P(x,y)

Kvantifikatorordning och betydelse

∀x ∃y Större(y,x): 'För varje tal finns ett större tal'

∃y ∀x Större(y,x): 'Det finns ett tal som är större än alla tal'

Första påståendet är sant för reella tal

Andra påståendet är falskt för reella tal (inget största tal)

Visualisering av kvantifikatorernas räckvidd och interaktioner

Formalisering av naturligt språk

Att översätta från naturligt språk till predikatlogik kräver noggrant tänkande kring kvantifikatorernas räckvidd och ordning. Ord som 'alla', 'några', 'ingen' och 'endast' har specifika logiska motsvarigheter som måste hanteras korrekt.

Vanliga översättningar

· 'Alla studenter är smarta': ∀x (Student(x) → Smart(x))

· 'Några studenter är smarta': ∃x (Student(x) ∧ Smart(x))

· 'Inga studenter är lata': ∀x (Student(x) → ¬Lat(x))

· 'Endast studenter är smarta': ∀x (Smart(x) → Student(x))

· 'Alla gillar någon': ∀x ∃y Gillar(x,y)

· 'Någon gillar alla': ∃x ∀y Gillar(x,y)

Komplex formalisering

Påstående: 'Varje lärare undervisar minst en student som är duktig'

Identifiera predikat: Lärare(x), Undervisar(x,y), Student(y), Duktig(y)

Formalisera: ∀x (Lärare(x) → ∃y (Student(y) ∧ Duktig(y) ∧ Undervisar(x,y)))

Kontrollera: För varje lärare finns minst en duktig student som läraren undervisar

Vanliga misstag

❌ Felaktig kvantifikatorordning

∀x ∃y P(x,y) och ∃y ∀x P(x,y) har mycket olika betydelser

Exempel: ∀x ∃y (y > x) ≠ ∃y ∀x (y > x) - första är sant, andra falskt för naturliga tal

❌ Förväxla implikation och konjunktion med kvantifikatorer

∀x (P(x) → Q(x)) ≠ ∀x (P(x) ∧ Q(x)) - implikation för 'alla som har P', konjunktion för 'alla har både P och Q'

Exempel: 'Alla hundar är djur' är ∀x (Hund(x) → Djur(x)), inte ∀x (Hund(x) ∧ Djur(x))

❌ Felaktig negation av kvantifierade påståenden

Glömma att negation av kvantifikatorer följer specifika regler

Exempel: ¬'Alla är glada' är 'Någon är inte glad', inte 'Alla är inte glada'

Tillämpningar

Databaslogik

SQL-frågor bygger på predikatlogik med kvantifikatorer som motsvarar JOIN och EXISTS

Exempel: SELECT * FROM studenter WHERE EXISTS (SELECT * FROM kurser WHERE student_id = studenter.id)

Programverifiering

Förvillkor och eftervillkor i program uttrycks med predikatlogik

Exempel: ∀i (0 ≤ i < n → array[i] ≤ array[i+1]) för sorterad array

Matematisk bevisföring

Definitioner och satser formaliseras med kvantifikatorer

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

Övningar

1 Lätt

Formalisera påståendet 'Alla hundar gillar minst en katt' med predikat Hund(x), Katt(y) och Gillar(x,y).

Tips

Använd universell kvantifikator för hundar och existentiell för katter

Visa facit

Identifiera kvantifikatorer: 'alla hundar' = ∀x, 'minst en katt' = ∃y
Struktur: För alla x, om x är hund, då finns y som är katt och x gillar y
Formalisering: ∀x (Hund(x) → ∃y (Katt(y) ∧ Gillar(x,y)))

Svar: ∀x (Hund(x) → ∃y (Katt(y) ∧ Gillar(x,y)))

2 Medel

Negera påståendet ∀x ∃y P(x,y) och förenkla.

Tips

Använd negationsreglerna för kvantifikatorer

Visa facit

Negera universell kvantifikator: ¬∀x blir ∃x
Negera existentiell kvantifikator: ¬∃y blir ∀y
Negera predikatet: ¬P(x,y)
Resultat: ∃x ∀y ¬P(x,y)

Svar: ∃x ∀y ¬P(x,y)

3 Medel

Förklara skillnaden mellan ∀x ∃y Gillar(x,y) och ∃y ∀x Gillar(x,y).

Tips

Tänk på kvantifikatorernas ordning och vad den betyder

Visa facit

∀x ∃y Gillar(x,y): För varje person finns någon som personen gillar
∃y ∀x Gillar(x,y): Det finns en person som gillas av alla
Första påståendet är svagare och mer troligt sant
Andra påståendet kräver en universellt gillad person

Svar: Första: alla gillar någon. Andra: någon gillar av alla.

Sammanfattning

Predikatlogik utvidgar propositionell logik med predikat som beskriver egenskaper och relationer, samt kvantifikatorer ∀ (alla) och ∃ (det finns) som låter oss göra påståenden om grupper av objekt. Kvantifikatorernas ordning är kritisk för betydelsen, och negation följer specifika regler. Predikatlogik är grunden för matematisk formalisering och databaslogik.