Predikatlogik

Från Wikipedia
Hoppa till: navigering, sök
Logik, Formellt system
Logiska system

Predikatlogik är en del av den matematiska logiken. Medan man i satslogiken bara kan sätta samman färdiga satser till mer komplicerade satser, exempelvis bilda A\land B, om A och B är satser. För att uttrycka A och B, kan man i predikatlogiken använda predikat. Exempelvis kan P representera är udda så att P(x) betyder x är udda. Man kan också bilda flerställiga relationer P(x,y), exempelvis för att representera relationen större än. I mängdteori kan hela matematiken formuleras med hjälp av predikatlogik med en enda relation \in, som uttrycker att en mängd är element i en annan. Samma logiska operationer som finns i satslogiken finns även i predikatlogiken. Dessutom finns all- och existens-kvantorer som uttrycker att något gäller för alla respektive för något objekt.

  • \forall xP(x) innebär att alla x har egenskapen P.
  • \exists xP(x) innebär att något x har egenskapen P.

Antag att vi vill uttala oss om att om någonting har två specifika egenskaper, så har det den andra av dessa egenskaper. Vi kan symbolisera det på följande sätt: \forall x((P(x) \land Q(x))\rightarrow Q(x)). Det läses: för varje x gäller, att om x har egenskapen P, och x har egenskapen Q, så har x egenskapen Q.

Ett annat exempel är \forall x\forall y ((x=y)\rightarrow(P(x)\leftrightarrow P(y))), som säger: för alla x gäller, att för alla y gäller, att om x är lika med y, så har x egenskapen P, om och endast om y har egenskapen P. Vad detta betyder är egentligen att om x och y betecknar samma föremål, så är egenskaperna för x och y lika.

Att man kan formulera predikatlogiken så att den blir fullständig bevisades av Kurt Gödel i hans doktorsavhandling.

Viktiga definitioner[redigera | redigera wikitext]

De nedanstående definitionerna är väsentliga då övriga definitioner och bevis utgår från dem. Vidare används de också för att undersöka om en formel är välbildad eller inte.

Definition 1: Definition av term.

  1. x1, x2, … är termer, det vill säga alla variabler är termer,
  2. c1, c2, … är termer, det vill säga alla konstanter är termer,
  3. Om f är en n-ställig funktionssymbol och, t1, t2, … , tn är termer, så är f(t1, t2, … , tn) en term.

Definition 2: Definition av atomär formel.

  1. Om t1 och t2 är två termer, så är t1 = t2 en atomär formel,
  2. Om P är en n-ställig predikatsymbol, och t1, t2, … , tn är termer, så är P(t1, t2, … , tn) en atomär formel.
  3. ⊥ är en atomär formel.

Definition 3: Definition av välbildad formel (vbf).

  1. Alla atomära formler är välbildade formler,
  2. Om ϕ är en välbildad formel, så är ¬ϕ en välbildad formel,
  3. Om ϕ och ψ är välbildade formler, så är (ϕ ∧ ψ), (ϕ ∨ ψ), (ϕ → ψ) och (ϕ ↔ ψ) välbildade formler,
  4. Om ϕ är en välbildad formel och v en variabel, så är ∃vϕ och vϕ välbildade formler.

[1]

Objekt, egenskaper och relationer[redigera | redigera wikitext]

Inom predikatlogik går det att dra slutsatser om objekt, egenskaper samt relationer vilket är den stora skillnaden i jämförelse med satslogiken.
Ett exempel på detta är:

John är en poet
Anna är en forskare
John är gift med Anna
Någon poet är gift med någon forskare

Vilket kan tolkas som, där a är objektet John, b är objektet Anna, P är en egenskap, Q är en annan egenskap och R ett förhållande:

a är P
b är Q
a är R till b
Något P är R till något Q

Vilket vi kan skriva som:

P(a)
Q(b)
R(a, b)
\exists a(P(a)\land \exists b(Q(b) \land R(a,b)))

vilket skulle utläsas som: Det finns ett a sådant att a är en poet och det finns ett b sådant att b är en forskare och a är gift med b

Förhållandet emellan kvantifikatorerna  \forall och  \exists [redigera | redigera wikitext]

Vi kan skriva ”ingen forskare älskar Anna” som:

\neg \ \exists x(Q(x)\ \land \ R(x,b)) (Det finns inte något x, sådant att x har egenskapen Q och x relaterar till b.)

Att säga att det inte finns någon forskare som har en viss egenskap skulle vi lika gärna kunna formulera som att alla forskare istället saknar den egenskapen och på det viset kan vi då även skriva:

 \forall x(Q(x)\ \rightarrow \ \neg \ R(x,b))

På detta sättet kan vi visa att:

 \neg \ \exists x\ \leftrightarrow \ \forall x\ \neg \

Vilket vi kan utveckla till:

 \neg \ \neg \ \exists x\ \leftrightarrow \ \neg \ \forall x\ \neg \ \rightarrow \ \exists x\ \leftrightarrow \ \neg \ \forall x\ \neg \

På detta sätt har vi således upptäckt att:

 \neg \ \exists x(Q(x) \ \wedge \ R(x,b)) \leftrightarrow \
 \forall x \ \neg \ (Q(x) \wedge \ R(x, b)) \leftrightarrow \
\forall x(Q(x) \rightarrow \ \neg \ R(x,b))

Formalisering[redigera | redigera wikitext]

Det är viktigt att när man försöker formalisera en språklig sats i predikatlogik att noggrant visa den logiska strukturen som existerar i den språkliga satsen. För att klara detta används två generella tekniker som kallas för bottom up och top down> (engelska för ”nerifrån upp” och ”uppifrån ner”).

  • Bottom Up: Med denna strategi lokaliserar man istället de atomära formlerna (se ovan) som bygger upp satsen och på det viset kan se satsens logiska struktur.
  • Top down: Med denna strategi är tanken att först leta reda på huvudoperatorn i en språklig sats för att på detta viset urskilja vilka delsatser som verkar på huvudoperatorn. Detta upprepas sedan på delsatserna.

Generellt är det en god idé att blanda de olika strategierna genom att börja med top down för att urskilja de atomära formlerna för att sedan använda bottom up.

Satstyper[redigera | redigera wikitext]

Med verktygen presenterade ovan kan man urskilja fyra typer av satser som går att formalisera med hjälp av predikatlogik.

  • Satstyp A: "Alla svanar är vackra".
  • Satstyp E: "Inga svanar är vackra".
  • Satstyp I: "Några svanar är vackra".
  • Satstyp O: "Några svanar är inte vackra".

Satstyperna A och O är kontradiktoriska och det är även satstyperna I och E. De kan inte båda vara sanna och ej heller båda vara falska.

Satstyperna A och E är konträra. De kan inte båda vara sanna, men båda vara falska.

Satstyperna I och O är subkonträra. De kan båda vara sanna, men inte båda vara falska.

Användningsområden[redigera | redigera wikitext]

Nedan nämns ett par områden där predikatlogiken används.

Elektronik[redigera | redigera wikitext]

För enklare kretsteknologi är satslogiken tillräcklig då den utgör grunden för den booleska algebran men inom högre nivåer av elektronik blir predikatlogik enormt viktigt då den tillåter skapandet av mera avancerade former av kretsar, mera specifikt inom området som på engelska heter ”Switching Theory” där logiskt sant representeras av 1 emedan logiskt falskt representeras av 0 [2]

Logisk programmering[redigera | redigera wikitext]

I vanlig programmering är uppgiften för programmering att tolka en given specifikation, som detaljerat förklarar vad ett program ska göra, till kod som förklarar hur resultaten ska uppnås. Ett program är således instruktioner till en dator som ska generera resultatet som angivits i specifikationen.

Logisk programmering skiljer sig från detta i att istället för att instruera datorn vad den ska åstadkomma så kommer programmeraren att skapa en databas med olika påståenden och regler gällande dessa. Efter detta ställer programmeraren en direkt fråga till datorn och datorn genererar ett svar utefter logisk manipulation av det som är angivet i databasen. I bästa fall behöver logisk programmering inga instruktioner utan enbart fakta.

Idag är det mest använda programmeringsspråket för denna typ av programmering Prolog, dock är Prolog mycket omdebatterat då det gör så pass stora kompromisser i form av imperativ programmering att frågan är huruvida det är ett logiskt programmeringsspråk överhuvudtaget [3]

Artificiell intelligens[redigera | redigera wikitext]

Många forskare inom området tror att en av de viktigaste delarna av mänskligt medvetande är logiskt resonemang och menar att formell logik kan stå för en av grundpelarna i skapandet av artificiell intelligens. Även detta är omdebatterat och en del forskare menar att inställningen till logiken som centrum för artificiell intelligens istället har begränsat utvecklingen snarare än att främja den. [4]

Se även[redigera | redigera wikitext]

Litteratur[redigera | redigera wikitext]

  • Barwise, Jon & Etchemendy, John, Language, proof and logic (1999)
  • Geoffrey Hunter, Metalogic, MacMillan 1971.


  1. ^ Sjögren, J: "Introduktion till predikatlogik", sidan 56, 2002
  2. ^ Vingron, S.P: "Switching Theory - Insight through predicate logic", förord, 2004
  3. ^ Galton, A: "Logic for Information Technology", sidan 3. 1990
  4. ^ Galton, A: "Logic for Information Technology", sidan 4. 1990
Venn A intersect B.svg Matematikportalen – portalen för matematik på svenskspråkiga Wikipedia.