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 og Charles S. Peirce 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&nbsp;de nevnte to setningene har disse begrepene følgende betydning:
*  menneske» og  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  menneske» med «Sokrates», blir setningen til et sant utsagn. Plassholdere kan også fylles med variabler, f.eks. når *x* settes inn i predikatet  menneske». I&nbsp;så fall blir predikatet til en setningsfunksjon, *M*(*x*) =  menneske», som blir et sant utsagn for alle *x* som er mennesker (f.eks. Sokrates eller Platon), 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å&nbsp;1. Således er den nevnte setningsfunksjonen, *M*(*x*) =  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å&nbsp;2) er  =  født tidligere  eller  =  en høyere atommasse  Disse funksjonene er eksempelvis sanne for *F*(Sokrates, Platon) respektive *A*(gull, svovel). Eksempler på *ternære* setningsfunksjoner (dvs. med en aritet på&nbsp;3) er  =  *y* til mor og *z* til far», eller  =  med *y*  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 individer som oppfyller en setningsfunksjon. I&nbsp;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 «&forall;»:
* «For alle *x* gjelder *F*»; «alle *x* oppfyller *F*».
* Skrivemåte: &forall;*x* *F*(*x*)
* Alternativ skrivemåte: \bigwedge_{x} F(x)
* Foreldet skrivemåte: (*x*) *F*(*x*)

Allkvantoren er relatert til setningslogikkens ''og''-junktor («&and;»):
:\big \lbrack \forall x F(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  ensbetydende med den (uendelige) utsagnssekvensen 

### Eksistenskvantor
**Eksistenskvantorer** brukes for å beskrive *eksistentielle utsagn* (eller «det fins»-utsagn) og gjengis vanligvis med symbolet «&exist;»:
* «Det fins *x* slik at *F* gjelder», «det eksisterer (minst) en *x* som oppfyller *F*»
* Skrivemåte: &exist;*x* *F*(*x*)
* Alternativ skrivemåte: \bigvee_{x} F(x)
* Foreldet skrivemåte: (E*x*) *F*(*x*)

Eksistenskvantoren er relatert til setningslogikkens ''eller''-junktor («&or;»):
:\big \lbrack \exists x F(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  ensbetydende med den (uendelige) utsagnssekvensen 

### 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! x F(x), som \bigvee^{\bullet}_{x} F(x), eller som \exists^{1} x F(x)];
* «det fins ingen *x* slik at *F* gjelder» [negasjonen av eksistensutsagnet, vanligvis gjengitt som \neg \exists x F(x), men også som \nexists x F(x), eller potensielt som \exists^{0} x F(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&nbsp;eksempelet over, «det fins et naturlig tall *n* som oppfyller at , 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}) &ndash; samt diskursunivers der utsagnet blir meningsløst (f.eks. alle mennesker).

Medlemskap i diskursuniverset, f.eks. «*x* er element av \N», er i seg selv en setningsfunksjon, N(x). Dermed kan diskursuniverset angis på én av de følgende måtene:
* \bigwedge_{x \in \N} F(x) \quad \Leftrightarrow \quad \forall x {\in} \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 \N, gjelder *F*»; noe som altså er ekvivalent med: «for alle *x* gjelder at hvis *x* er element av \N, så oppfyller *x* også *F*». 
* \bigvee_{x \in \N} F(x) \quad \Leftrightarrow \quad \exists x {\in} \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 \N, slik at *F* gjelder»; noe som altså er ekvivalent med: «det eksisterer minst én *x* som både er element av \N og oppfyller *F*».
Merk at allutsagnet her får formen av en subjunksjon  hvis medlemskap i diskursuniverset formuleres som setningsfunksjon; mens eksistensutsagnet får formen av en konjunksjon 

## Eksempler
Noen eksempler kan illustrere hvordan setninger fra hverdagsspråket kan formaliseres gjennom predikatlogikken. Symbolene som brukes, er allkvantoren («&forall;»), eksistenskvantoren («&exist;») og ekvivalens («&hArr;») samt de setningslogiske sannhetsfunksjonene negasjon  konjunksjon  inklusiv disjunksjon  og subjunksjon 

### Unære funksjoner
I de følgende eksemplene står setningsfunksjonen  for  en elefant», mens  står for 

### Binære funksjoner
I de følgende eksemplene står setningsfunksjonen  for 

## 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 &ndash; negasjonen av et eksistensutsagn er et allutsagn om negasjonen.
* \neg \forall x F(x) \quad \Leftrightarrow \quad \exists x \neg F(x)
*# Det er ikke tilfellet at alle svaner er hvite.
*# Det fins en svane som ikke er hvit.
* \neg \exists x F(x) \quad \Leftrightarrow \quad \forall x \neg F(x)
*# Det fins ikke noen gule ravner.
*# For alle ravner gjelder at de ikke er gule.
*\forall x F(x) \quad \Leftrightarrow \quad \neg \exists x \neg F(x)
*# Alle ravner er svarte.
*# Det fins ikke noen ravner som ikke er svarte.
*\exists x F(x) \quad \Leftrightarrow \quad \neg \forall x \neg F(x)
*# Det fins en svart svane.
*# Det er ikke tilfellet at alle svaner er ikke-svarte.

### Distributiv lov
Den distributive lov gjelder innenfor kombinasjonene {&forall;; &and;} og {&exist;; &or;}.
* \forall x \big \lbrack F(x) \land G(x) \big \rbrack \quad \Leftrightarrow \quad \big \lbrack \forall x F(x) \big \rbrack \land \big \lbrack \forall x G(x) \big \rbrack
*# Alt er rosa og elefant. (Det eksisterer ikke noe annet enn rosa elefanter)
*# Alt er rosa, og alt er elefant.
* \exists x \big \lbrack F(x) \lor G(x) \big \rbrack \quad \Leftrightarrow \quad \big \lbrack \exists x F(x) \big \rbrack \lor \big \lbrack \exists x G(x) \big \rbrack
*# Det fins noe som er rosa eller en elefant.
*# 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 {&forall;; &and;} og {&exist;; &or;}!
* \forall x \big \lbrack F(x) \lor G(x) \big \rbrack \quad \nLeftrightarrow \quad \big \lbrack \forall x F(x) \big \rbrack \lor \big \lbrack \forall x G(x) \big \rbrack
*# Alt er rosa eller elefant (oppfylt f.eks. hvis alt som fins i universet er ni rosa sokker og tre grå elefanter).
*# 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 x F(x) \big \rbrack \land \big \lbrack \exists x G(x) \big \rbrack
*# Det fins noe som er rosa og en elefant (bare oppfylt hvis det fins minst en rosa elefant).
*# 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 y H(x,y) \quad \Leftrightarrow \quad \forall y \forall x H(x,y)
*# Alle [*x*] elsker alle [*y*].
*# Alle [*y*] elskes av alle [*x*].
* \exists x \exists y H(x,y) \quad \Leftrightarrow \quad \exists y \exists x H(x,y)
*# Noen [*x*] elsker noen [*y*].
*# Noen [*y*] elskes av noen [*x*].

Merk at den kommutative lov *ikke* gjelder på tvers av kvantorene!
* \forall x \exists y H(x,y) \quad \nLeftrightarrow \quad \forall y \exists x H(x,y) \quad \nLeftrightarrow \quad \exists x \forall y H(x,y) \quad \nLeftrightarrow \quad \exists y \forall x H(x,y)
*# Alle [*x*] elsker noen [*y*] (oppfylt selv om f.eks. *j* ikke elskes av noen).
*# Alle [*y*] elskes av noen [*x*] (oppfylt selv om f.eks. *k* ikke elsker noen).
*# Noen [*x*] elsker alle [*y*].
*# 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


## Litteratur
* 
*