Predicatenlogica

De eerste-orde-predicatenlogica is een uitbreiding van de propositielogica. De taal is uitgebreid met constanten, variabelen, predicaten en soms ook functiesymbolen. Een propositie is een speciaal geval van een predicaat, namelijk een predicaat met plaatsigheid nul. De taal van de predicatenlogica bevat verder twee kwantoren: de universele kwantor ${\displaystyle \forall }$  en de existentiële kwantor ${\displaystyle \exists }$ .

In de propositielogica kan een propositie als Wikipedia is een encyclopedie worden uitgedrukt met een letter, bijvoorbeeld P. In de predicatenlogica kan dit worden uitgedrukt met een predicaat dat een encyclopedie zijn vertegenwoordigt, bijvoorbeeld met de letter E aangegeven, en een constante voor Wikipedia, bijvoorbeeld w. De bewering Wikipedia is een encyclopedie kan dan worden uitgedrukt met de formule: E(w). Een atomaire propositie is in de predicatenlogica een formule waarin geen voegtekens (connectieven) voorkomen.

Als de letter ${\displaystyle N}$  het predicaat nuttig zijn uitdrukt, kan de zin Als Wikipedia een encyclopedie is, is Wikipedia nuttig als volgt met een predicaatlogische formule representeren:

${\displaystyle E(w)\to N(w)}$ .

Ook een uitdrukking als Alle encyclopedieën zijn nuttig kan in predicatenlogica worden uitgedrukt, bijvoorbeeld als:

${\displaystyle \forall x:(E(x)\to N(x))}$ .

De formele taal waarin de logica werkt, legt het aantal constanten, relaties en functies en de ariteit van de relaties en functies vast. Deze gegevens vormen het similariteitstype.

Men onderscheidt predicatenlogica's van verschillende ordes:

• binnen de eerste-orde-predicatenlogica kan alleen over constanten en variabelen worden gekwantificeerd,
• binnen de tweede-orde-predicatenlogica kan ook over eerste-orde-predicaten worden gekwantificeerd,
• in het algemeen kan in ${\displaystyle n}$ -de-orde-predicatenlogica's over predicaten van orde ten hoogste ${\displaystyle n-1}$  worden gekwantificeerd.

Als we een constante ${\displaystyle 0}$  en een opvolgerfunctie ${\displaystyle s}$  definiëren, kunnen we het inductieprincipe in tweede-orde-logica als volgt opschrijven:

• ${\displaystyle \forall P{\biggl (}{\Bigl (}P(0)\land \forall x{\bigl (}P(x)\to P(s(x)){\bigr )}{\Bigr )}\to \forall xP(x){\biggr )}}$ 

In de eerste-orde-predicatenlogica kan het inductieprincipe niet als een enkele formule worden opgeschreven.