Predikatlogikk

Predikatlogikk (også predikatkalkyle eller kvantorlogikk) er en gren av logikken som analyserer setninger som inneholder kvantorer («alle», «noen», «ingen» osv.) og variabler. Som en utvidelse av setningslogikken analyserer predikatlogikken ikke bare kombinasjoner av utsagn, men også utsagnenes indre struktur. Syllogistikken kan ses på som et delsystem av predikatlogikken.

Predikatlogikken har betydning for fagfelt langt utover logikk, spesielt for matematikk, lingvistikk, filosofi og informatikk. Den ble utviklet uavhengig av hverandre av Gottlob Frege^[1] og Charles S. Peirce^[2] på slutten av 1800-tallet.

Oversikt

Predikatlogikken analyserer setninger av typen «Sokrates er et menneske» og «alle mennesker er dødelige». Slike setninger kan forstås som bestående av predikater, egennavn, variabler og/eller kvantorer. I de nevnte to setningene har disse begrepene følgende betydning:

«_ er et menneske» og «_ er dødelig» er predikater (som angir egenskaper eller relasjoner).
«Sokrates» er et egennavn (som angir ett konkret individ).
«Mennesker» er en variabel (som angir en klasse av individer).
«Alle» er en kvantor (som angir et antall).

Predikat

Med predikat menes (noe avvikende fra begrepets betydning i grammatikken) en ordsekvens med en eller flere plassholder(e), som blir til et sant eller usant utsagn når plassholderne («_») fylles med egennavn. Fyller man plassholderen i «_ er et menneske» med «Sokrates», blir setningen til et sant utsagn. Plassholdere kan også fylles med variabler, f.eks. når x settes inn i predikatet «_ er et menneske». I så fall blir predikatet til en setningsfunksjon, M(x) = «x er et menneske», som blir et sant utsagn for alle x som er mennesker (f.eks. Sokrates eller Plato), og et usant utsagn for alle x som ikke er mennesker (f.eks. elefanten Jumbo eller roboten R2-D2).

Predikater kan ikke bare beskrive egenskaper, men også relasjoner. Predikater som beskriver egenskaper, har én plassholder, dvs. de er unære eller har en aritet på 1. Således er den nevnte setningsfunksjonen, M(x) = «x er et menneske», altså en funksjon med én variabel.

Relasjoner mellom to eller flere individer krever to eller flere plassholdere. Antall plassholdere eller variabler tilsvarer ariteten til setningsfunksjon. Eksempler på binære setningsfunksjoner (dvs. med en aritet på 2) er F(x, y) = «x er født tidligere enn y», eller A(x, y) = «x har en høyere atommasse enn y». Disse funksjonene er eksempelvis sanne for F(Sokrates, Platon) respektive A(gull, svovel). Eksempler på ternære setningsfunksjoner (dvs. med en aritet på 3) er B(x, y, z) = «x har y til mor og z til far», eller K(x, y, z) = «x konkurrerer med y om z». Disse funksjonene er eksempelvis sanne for B(Leia Organa, Padmé Amidala, Anakin Skywalker) respektive K(fjellrev, snøugle, lemen).

Kvantor

En kvantor angir (kvantifiserer) hvor mange individuer som oppfyller en setningsfunksjon. I setningen «alle x er dødelige», er det ordet «alle» som er kvantoren. De to mest brukte kvantorene er all- og eksistenskvantor.

Allkvantor

Allkvantorer brukes for å beskrive «allutsagn» (eller universelle utsagn), f.eks. naturlover, og gjengis vanligvis med symbolet «∀»:

«For alle x gjelder F»; «alle x oppfyller F».
Skrivemåte: ∀x F(x)
Alternativ skrivemåte: $\bigwedge _{x}F(x)$
Foreldet skrivemåte: (x) F(x)

Allkvantoren er relatert til setningslogikkens og-junktor («∧»):

{\big \lbrack }\forall xF(x){\big \rbrack }\Leftrightarrow {\big \lbrack }F(1)\land F(2)\land F(3)\land ...{\big \rbrack }

For eksempel er (det sanne) utsagnet «for alle naturlige tall n gjelder at n · 0 = 0» ensbetydende med den (uendelige) utsagnssekvensen «1 · 0 = 0, og 2 · 0 = 0, og 3 · 0 = 0, osv.»

Eksistenskvantor

Eksistenskvantorer brukes for å beskrive eksistentielle utsagn (eller «det fins»-utsagn) og gjengis vanligvis med symbolet «∃»:

«Det fins x slik at F gjelder», «det eksisterer (minst) en x som oppfyller F»
Skrivemåte: ∃x F(x)
Alternativ skrivemåte: $\bigvee _{x}F(x)$
Foreldet skrivemåte: (Ex) F(x)

Eksistenskvantoren er relatert til setningslogikkens eller-junktor («∨»):

{\big \lbrack }\exists xF(x){\big \rbrack }\Leftrightarrow {\big \lbrack }F(1)\lor F(2)\lor F(3)\lor ...{\big \rbrack }

For eksempel er (det sanne) utsagnet «det fins et naturlig tall n som oppfyller at n · n = 16» ensbetydende med den (uendelige) utsagnssekvensen «1 · 1 = 16, eller 2 · 2 = 16, eller 3 · 3 = 16, osv.»

Andre kvantorer

I tillegg til all- og eksistenskvantor benyttes til dels andre kvantorer, f.eks.

«det fins nøyaktig én x slik at F gjelder» [av og til gjengitt som $\exists !xF(x)$ , som $\bigvee _{x}^{\bullet }F(x)$ , eller som $\exists ^{1}xF(x)$ ];
«det fins ingen x slik at F gjelder» [negasjonen av eksistensutsagnet, vanligvis gjengitt som $\neg \exists xF(x)$ , men også som $\nexists xF(x)$ , eller potensielt som $\exists ^{0}xF(x)$ ];
«for nesten alle x gjelder F» [= «for alle x med endelig mange unntak gjelder F].

Diskursunivers

Vanligvis er kvantorer relative til et såkalt diskursunivers. I eksempelet over, «det fins et naturlig tall n som oppfyller at n · n = 16», er det de naturlige tallene som er diskursuniverset. Utsagnet er også oppfylt i andre diskursunivers (f.eks. alle heltall, alle rasjonale tall, alle reelle tall), mens det fins diskursunivers der utsagnet er usant (f.eks. alle tresifrede heltall, {100; 101; 102; ...; 999}) – samt diskursunivers der utsagnet blir meningsløst (f.eks. alle mennesker).

Medlemskap i diskursuniverset, f.eks. «x er element av $\mathbb {N}$ », er i seg selv en setningsfunksjon, $N(x)$ . Dermed kan diskursuniverset angis på én av de følgende måtene:

$\bigwedge _{x\in \mathbb {N} }F(x)\quad \Leftrightarrow \quad \forall x{\in }\mathbb {N} \;F(x)\quad \Leftrightarrow \quad \forall x{\big \lbrack }N(x)\to F(x){\big \rbrack }$

Dette leses som: «for alle x som er element av

\mathbb {N}

, gjelder F»; noe som altså er ekvivalent med: «for alle x gjelder at hvis x er element av

\mathbb {N}

, så oppfyller x også F».

$\bigvee _{x\in \mathbb {N} }F(x)\quad \Leftrightarrow \quad \exists x{\in }\mathbb {N} \;F(x)\quad \Leftrightarrow \quad \exists x{\big \lbrack }N(x)\land F(x){\big \rbrack }$

Dette leses som: «det fins en x som er element av

\mathbb {N}

, slik at F gjelder»; noe som altså er ekvivalent med: «det eksisterer minst én x som både er element av

\mathbb {N}

og oppfyller F».

Merk at allutsagnet her får formen av en subjunksjon («hvis–så»), hvis medlemskap i diskursuniverset formuleres som setningsfunksjon; mens eksistensutsagnet får formen av en konjunksjon (logisk «og»).

Eksempler

Noen eksempler kan illustrere hvordan setninger fra hverdagsspråket kan formaliseres gjennom predikatlogikken. Symbolene som brukes, er allkvantoren («∀»), eksistenskvantoren («∃») og ekvivalens («⇔») samt de setningslogiske sannhetsfunksjonene negasjon («ikke», «¬»), konjunksjon («både–og», «∧»), inklusiv disjunksjon («eller», «∨») og subjunksjon («hvis–så», «→»).

Unære funksjoner

I de følgende eksemplene står setningsfunksjonen E(x) for «x er en elefant», mens R(x) står for «x er rosa».

Formel	Lesemåte av formelen	Betydning	Forklaring
$\forall x{\big \lbrack }E(x)\land R(x){\big \rbrack }$	For alle x gjelder at x er en elefant og at x er rosa.	Alt er rosa elefanter.	Det fins ikke noe annet i universet enn rosa elefanter.
$\forall x{\big \lbrack }E(x)\lor R(x){\big \rbrack }$	For alle x gjelder at x er en elefant eller at x er rosa.	Alt er rosa eller elefant.	Det kan finnes rosa sokker og grå elefanter, men ikke grønne sykler.
$\exists x{\big \lbrack }E(x)\land R(x){\big \rbrack }$	Det fins en x slik at x er en elefant og at x er rosa.	Det fins en rosa elefant.	Men det kan finnes mye annet også.
$\neg \exists x{\big \lbrack }E(x)\land R(x){\big \rbrack }$	Det fins ikke noen x slik at x er en elefant og at x er rosa.	Rosa elefanter fins ikke.	Men det kan finnes mye annet.
$\forall x{\big \lbrack }E(x)\to R(x){\big \rbrack }$	For alle x gjelder at hvis x er en elefant, så er x rosa.	Alle elefanter er rosa.	Det kan finnes rosa sokker og grønne sykler, men ikke grå elefanter.
$\forall x{\big \lbrack }R(x)\to E(x){\big \rbrack }$	For alle x gjelder at hvis x er rosa, så er x en elefant.	Bare elefanter er rosa.	Det kan finnes grå elefanter og grønne sykler, men ikke rosa sokker.

Binære funksjoner

I de følgende eksemplene står setningsfunksjonen L(x, y) for «x elsker y».

Formel	Lesemåte av formelen	Betydning
$\forall x\forall yL(x,y)$	For alle x og alle y gjelder at x elsker y.	Alle elsker alle.
$\forall x\exists yL(x,y)$	For alle x fins det en y som oppfyller at x elsker y.	Alle elsker noen.
$\forall x\exists yL(y,x)$	For alle x fins det en y som oppfyller at y elsker x.	Alle elskes av noen.
$\exists x\forall yL(x,y)$	Det fins en x som oppfyller for alle y at x elsker y.	Noen elsker alle.
$\exists x\forall yL(y,x)$	Det fins en x som oppfyller for alle y at y elsker x.	Noen elskes av alle.
$\exists x\exists yL(x,y)$	Det fins en x og en y som oppfyller at x elsker y.	Noen elsker noen.
$\neg \forall x\forall yL(x,y)$	Det er ikke tilfellet for alle x og alle y at x elsker y.	Noen elsker ikke alle.
$\exists x\neg \forall yL(x,y)$	Det fins en x som ikke oppfyller for alle y at x elsker y.
$\exists x\exists y\neg L(x,y)$	Det fins en x og en y som oppfyller at x ikke elsker y.
$\neg \forall x\exists yL(x,y)$	Det er ikke tilfellet at det for alle x fins en y som oppfyller at x elsker y.	Noen elsker ingen.
$\exists x\neg \exists yL(x,y)$	Det fins en x som oppfyller at det ikke fins noen y som oppfyller at x elsker y.
$\exists x\forall y\neg L(x,y)$	Det fins en x som oppfyller for alle y at x ikke elsker y.
$\neg \exists x\forall yL(x,y)$	Det fins ikke noen x som oppfyller for alle y at x elsker y.	Ingen elsker alle.
$\forall x\neg \forall yL(x,y)$	For alle x gjelder at det ikke gjelder for alle y at x elsker y.
$\forall x\exists y\neg L(x,y)$	For alle x fins det en y som oppfyller at x ikke elsker y.
$\neg \exists x\exists yL(x,y)$	Det fins ikke noen x og ikke noen y som oppfyller at x elsker y.	Ingen elsker noen.
$\forall x\neg \exists yL(x,y)$	For alle x gjelder at det ikke fins noen y som oppfyller at x elsker y.
$\forall x\forall y\neg L(x,y)$	For alle x og alle y gjelder at x ikke elsker y.

Predikatlogiske ekvivalenser

Her presenteres noen grunnleggende ekvivalenser (dvs. gyldige omforminger) som gjelder i predikatlogikken.

Negasjon

Negasjonen av et allutsagn er et eksistensutsagn om negasjonen; og motsatt – negasjonen av et eksistensutsagn er et allutsagn om negasjonen.

$\neg \forall xF(x)\quad \Leftrightarrow \quad \exists x\neg F(x)$ $\neg \forall xF(x)\quad \Leftrightarrow \quad \exists x\neg F(x)$
1. Det er ikke tilfellet at alle svaner er hvite.
2. Det fins en svane som ikke er hvit.
$\neg \exists xF(x)\quad \Leftrightarrow \quad \forall x\neg F(x)$ $\neg \exists xF(x)\quad \Leftrightarrow \quad \forall x\neg F(x)$
1. Det fins ikke noen gule ravner.
2. For alle ravner gjelder at de ikke er gule.
$\forall xF(x)\quad \Leftrightarrow \quad \neg \exists x\neg F(x)$ $\forall xF(x)\quad \Leftrightarrow \quad \neg \exists x\neg F(x)$
1. Alle ravner er svarte.
2. Det fins ikke noen ravner som ikke er svarte.
$\exists xF(x)\quad \Leftrightarrow \quad \neg \forall x\neg F(x)$ $\exists xF(x)\quad \Leftrightarrow \quad \neg \forall x\neg F(x)$
1. Det fins en svart svane.
2. Det er ikke tilfellet at alle svaner er ikke-svarte.

Distributiv lov

Den distributive lov gjelder innenfor kombinasjonene {∀; ∧} og {∃; ∨}.

$\forall x{\big \lbrack }F(x)\land G(x){\big \rbrack }\quad \Leftrightarrow \quad {\big \lbrack }\forall xF(x){\big \rbrack }\land {\big \lbrack }\forall xG(x){\big \rbrack }$ $\forall x{\big \lbrack }F(x)\land G(x){\big \rbrack }\quad \Leftrightarrow \quad {\big \lbrack }\forall xF(x){\big \rbrack }\land {\big \lbrack }\forall xG(x){\big \rbrack }$
1. Alt er rosa og elefant. (Det eksisterer ikke noe annet enn rosa elefanter)
2. Alt er rosa, og alt er elefant.
$\exists x{\big \lbrack }F(x)\lor G(x){\big \rbrack }\quad \Leftrightarrow \quad {\big \lbrack }\exists xF(x){\big \rbrack }\lor {\big \lbrack }\exists xG(x){\big \rbrack }$ $\exists x{\big \lbrack }F(x)\lor G(x){\big \rbrack }\quad \Leftrightarrow \quad {\big \lbrack }\exists xF(x){\big \rbrack }\lor {\big \lbrack }\exists xG(x){\big \rbrack }$
1. Det fins noe som er rosa eller en elefant.
2. Det fins noe som er rosa, eller det fins noe som er en elefant.

Merk at den distributive lov ikke gjelder for andre kombinasjonene enn {∀; ∧} og {∃; ∨}!

$\forall x{\big \lbrack }F(x)\lor G(x){\big \rbrack }\quad \nLeftrightarrow \quad {\big \lbrack }\forall xF(x){\big \rbrack }\lor {\big \lbrack }\forall xG(x){\big \rbrack }$ $\forall x{\big \lbrack }F(x)\lor G(x){\big \rbrack }\quad \nLeftrightarrow \quad {\big \lbrack }\forall xF(x){\big \rbrack }\lor {\big \lbrack }\forall xG(x){\big \rbrack }$
1. Alt er rosa eller elefant (oppfylt f.eks. hvis alt som fins i universet er ni rosa sokker og tre grå elefanter).
2. Alt er rosa, eller alt er elefant (ikke oppfylt hvis alt som fins i universet er ni rosa sokker og tre grå elefanter).
$\exists x{\big \lbrack }F(x)\land G(x){\big \rbrack }\quad \nLeftrightarrow \quad {\big \lbrack }\exists xF(x){\big \rbrack }\land {\big \lbrack }\exists xG(x){\big \rbrack }$ $\exists x{\big \lbrack }F(x)\land G(x){\big \rbrack }\quad \nLeftrightarrow \quad {\big \lbrack }\exists xF(x){\big \rbrack }\land {\big \lbrack }\exists xG(x){\big \rbrack }$
1. Det fins noe som er rosa og en elefant (bare oppfylt hvis det fins minst en rosa elefant).
2. Det fins noe rosa, og det fins en elefant (oppfylt hvis det f.eks. fins rosa sokker og grå elefanter).

Kommutativ lov

Mellom kvantorer av samme type gjelder den kommutative lov.

$\forall x\forall yH(x,y)\quad \Leftrightarrow \quad \forall y\forall xH(x,y)$ $\forall x\forall yH(x,y)\quad \Leftrightarrow \quad \forall y\forall xH(x,y)$
1. Alle [x] elsker alle [y].
2. Alle [y] elskes av alle [x].
$\exists x\exists yH(x,y)\quad \Leftrightarrow \quad \exists y\exists xH(x,y)$ $\exists x\exists yH(x,y)\quad \Leftrightarrow \quad \exists y\exists xH(x,y)$
1. Noen [x] elsker noen [y].
2. Noen [y] elskes av noen [x].

Merk at den kommutative lov ikke gjelder på tvers av kvantorene!

$\forall x\exists yH(x,y)\quad \nLeftrightarrow \quad \forall y\exists xH(x,y)\quad \nLeftrightarrow \quad \exists x\forall yH(x,y)\quad \nLeftrightarrow \quad \exists y\forall xH(x,y)$ $\forall x\exists yH(x,y)\quad \nLeftrightarrow \quad \forall y\exists xH(x,y)\quad \nLeftrightarrow \quad \exists x\forall yH(x,y)\quad \nLeftrightarrow \quad \exists y\forall xH(x,y)$
1. Alle [x] elsker noen [y] (oppfylt selv om f.eks. j ikke elskes av noen).
2. Alle [y] elskes av noen [x] (oppfylt selv om f.eks. k ikke elsker noen).
3. Noen [x] elsker alle [y].
4. Noen [y] elskes av alle [x].

Høyere ordens predikatlogikk

Eksemplene som ble gitt over, hører til predikatlogikken av første orden. Her refererer alle predikater til individer (eller variabler for individer). Hvis predikatene refererer til klasser av individer, til klasser av klasser av individer osv., eller hvis kvantorene refererer til predikatvariabler (f.eks. «alle x som oppfyller noen av egenskapene F»), snakker man om høyere ordens predikatlogikk.

Referanser

^ G. Frege (1879). Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. Halle: Nebert.
^ C.S. Peirce (1885). «On the Algebra of Logic: A Contribution to the Philosophy of Notation». American Journal of Mathematics. 7: 180–196, 197–202. doi:10.2307/2369451.

Litteratur

K. Lorenz (1995). «Prädikatenlogik». I J. Mittelstraß. Enzyklopädie Philosophie und Wissenschaftstheorie. Band 3. Stuttgart: Metzler. s. 311–312.
W. Stelzner (1999). «Logik». I H.J. Sandkühler. Enzyklopädie Philosophie. Hamburg: Meiner. s. 1102–1120.

[1] G. Frege (1879). Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. Halle: Nebert.

[2] C.S. Peirce (1885). «On the Algebra of Logic: A Contribution to the Philosophy of Notation». American Journal of Mathematics. 7: 180–196, 197–202. doi:10.2307/2369451.

[1]

[2]