Predikatlogik

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 ${\displaystyle A\land B}$, om ${\displaystyle A}$ och ${\displaystyle B}$ är satser), kan man i predikatlogiken resonera om företeelser och deras egenskaper. För att uttrycka A och B, kan man i predikatlogiken använda predikat. Exempelvis kan ${\displaystyle P}$ representera är udda så att ${\displaystyle P(x)}$ betyder ${\displaystyle x}$ är udda. Man kan också bilda flerställiga relationer ${\displaystyle 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 ${\displaystyle \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.

• ${\displaystyle \forall xP(x)}$ innebär att alla ${\displaystyle x}$ har egenskapen ${\displaystyle P}$.

• ${\displaystyle \exists xP(x)}$ innebär att något ${\displaystyle x}$ har egenskapen ${\displaystyle 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: ${\displaystyle \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 ${\displaystyle \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.