Det følgende er adaptert fra Håvard Terlands forelesningsnotater for [Elementær diskret matematikk V24](https://wiki.math.ntnu.no/ma0301/2024v/start) (Uke 5/Uke 10), med litt tillegg her og der. Dette notatet erstatter kap. 15 og 16 i Roger Antonsens *Logiske Metoder*, og leder inn i kap. 13 og 14. Vi dekker med andre ord dekker stoffet i en annen rekkefølge enn boken. ### 1. Predikatlogikk Husk definisjonen av en refleksiv relasjon: En relasjon på $A$, si $R$, er en delmengde av $A \times A$ slik at $(x,x) \in R$ **for alle** $x$ i $A$. Veldig ofte i matematikk dukker det opp ord som "alle", og spesielt uttrykket "for alle", samt uttrykk som "det eksisterer". En relasjon er for eksempel *ikke* symmetrisk om det eksisterer et par $(x,y)$ i relasjonen slik at $(y,x)$ *ikke* er i relasjonen. I predikatlogikk jobber vi med utsagn som "for alle" og "det eksisterer", ved å "utvide" utsagnslogikk med blant annet tegnene - $\forall$ – for alle, - $\exists$ – det eksisterer. Vi kaller $\forall$ for universalkvantoren, og $\exists$ for eksistenskvantoren. #### 1.1 Terminologi og notasjon Vi bytter ofte "for alle" ut med $\forall$. "For alle $x \in Aquot; kan da skrives $\forall x \in A$. Tilsvarende bytter vi ofte ut "det eksisterer" med $\exists$. Til slutt merker vi oss at "det eksisterer *nøyaktig én*" ofte skrives $\exists!$. For eksempel kan vi skrive > $\exists! x \in \mathbb{N}$ slik at $x < 1$ for å uttrykke at det kun eksisterer ett naturlig tall som er mindre enn én. > ##### Eksempel 1 > La $R$ være en relasjon på $A$. > - $R$ er refleksiv $\Leftrightarrow \forall x \in A$ er $(x,x) \in R$. > - $R$ er symmetrisk $\Leftrightarrow \forall (x,y) \in A$ har vi $(x,y) \in R \Rightarrow (y,x) \in R$. > - $R$ er *ikke* refleksiv $\Leftrightarrow \exists x \in A$ slik at $(x,x) \not\in R$. Vi har nå sett eksempler på hvordan kvantorene $\forall, \exists$ kan forenkle matematiske definisjoner og matematiske språk generelt. Vi skal nå diskutere litt grundigere hvordan vi kan bruke kvantorene våre til å utvide matematisk logikk fra utsagnslogikk til *predikatlogikk*. Betrakt setningen "$x \cdot 2$ er et partall". Er dette et *utsagn*? I så fall måtte setningen tatt en sannhetsverdi. Er den *sann* eller *usann*? Det avhenger av $x$! Tolker vi $x$ som en ukjent, er setningen altså *ikke* et utsagn. Straks $x$ er *bestemt*, får vi derimot et utsagn. > ##### Eksempel 2 > La $P(x) \coloneqq x \cdot 2$ *er et partall*. Da er $P(1)$ et utsagn, nemlig "$1 \cdot 2$ *er et partall*", og $P(1)$ er *sann*. Er $P(x)$ fra eksempelet over sann for alle $x$? Det spørs hvilke verdier vi tillater at $x$ tar; setter vi $x = 1/2$, eller $x = \pi$, eller $x = {}$ "Hei", får vi i de to første tilfellene at $P(x)$ blir usann, og i det siste tilfellet får vi noe vi ikke enkelt kan tolke. Det er derfor slik at vi alltid velger et *univers* å trekke verdier fra. > ##### Eksempel 3 > La universet være de naturlige tallene $\mathbb{N}$. Da er $\forall x\ P(x)$ *sann*. Merk at $P(x)$ har én fri variabel, mens $\forall x\ P(x)$ har *ingen* frie variabler. Dermed er uttrykket $\forall x\ P(x)$ et *utsagn*! > ##### Definisjon 1 > Et uttrykk som blir et utsagn straks et gitt antall variabler er bestemt, kalles et *predikat*. Et predikat med $k$ frie variabler kalles et predikat av *aritetet* $k$. **Merk:** Definisjonen over lar oss tolke *utsagn* som *predikater av aritet $0$*. $P$ fra de forrige eksemplene er et predikat av aritet $1$. > ##### Eksempel 4 > La $Q(x,y) \coloneqq (x + y = 3)$, og la universet være $\mathbb{N}$ (slik at $x$ og $y$ er naturlige tall). Betrakt uttrykkene: > - $\exists x\ Q(x,1)$. Dette uttrykket er et utsagn med sannhetsverdi *sann*. > - Hva er verdien $x$ som utsagnet sier at må eksistere? > - $\exists x\ Q(x,y)$. Dette uttrykket er et predikat med aritet $1$. > - Ser du hvorfor ariteten er $1$ og ikke $2$? > - $\forall x\ \exists y\ Q(x,y)$. Dette uttrykket er et utsagn (ingen frie variabler) med sannhetsverdi *usann*. > - Kan du vise at utsagnet er usant ved å finne et moteksempel, det vil si en verdi for $x$ slik at utsagnet ikke holder? > - Hvilken sannhetsverdi ville utsagnet tatt dersom vi i stedet lot universet være heltallene $\mathbb{Z}$? #### 1.2 Rekkefølge på kvantorer La $S(x,y) \coloneqq x < y$, og la universet være de naturlige tallene $\mathbb{N}$. (Test deg selv: Hvilke sannhetsverdier har $S(1,3)$, $S(3,1)$ og $S(2,2)$? Svar i fotnote[^1].) > ##### Eksempel 5 > Betrakt utsagnet $\forall x\ \exists y\ S(x,y)$. Vi leser dette som at "for alle $x$ finnes det en $y$ slik at $x<yquot;. Er dette utsagnet sant eller usant? > > Riktig: Det er *sant*, da vi alltid kan velge en $y$ som "kommer etter" $x$. For eksempel kan vi sette at $y = x + 1$. Da får vi utsagnet $\forall x\ S(x, x+1) \Leftrightarrow \forall x: x < x + 1$, som er *sant* for alle $x$. Hva hvis vi bytter om rekkefølgen på kvantorene? > ##### Eksempel 6 > Betrakt utsagnet $\exists y\ \forall x\ S(x,y)$, som vi leser som at "det eksisterer en $y$ slik at for alle $x$ så er $x < yquot;. Er dette uttrykket sant? > > Riktig: Det er *usant* – vi kan ikke finne noen *enkelt*verdier for $y$ som er større enn alle naturlige tall: Dersom vi hadde satt $y = \infty$, så ville vi hatt $y \not\in U = \mathbb{N}$. > > (Men dersom universet var $U = \mathbb{N} \cup \{\infty\}$, så hadde uttrykket vært sant!) Intuitivt, så handler forskjellen i kvantorenes rekkefølge om *unikhet* og *avhengighet*: Hvis jeg skriver $\exists y\ \forall x\ P(x,y)$, så krever jeg at det skal eksistere en *enkelt*verdi $y$ slik at $P(x,y)$ blir sann *uansett* hva $x$ er. Hvis jeg derimot skriver $\forall x\ \exists y\ P(x,y)$, så får jeg lov å velge en ny verdi $y$ for hver verdi av $x$. Med andre ord tillater vi at $y$ *avhenger av* $x$, slik som i eksempelet over, hvor vi satte $y(x) = x + 1$. Merk hvordan dette også innebærer at den éne rekkefølgen leder til et *sterkere* utsagn enn den andre, for hvis vi har én verdi $y$ slik at $P(x,y)$ er sann for alle $x$, så er det jo nødvendigvis også sant at for alle $x$, så er det en verdi $y$ slik at $P(x,y)$ er sann. Men i motsatt retning så så vi i eksemplene over at sannhet ikke alltid følger: At hver verdi $x$ kommer med en verdi $y$ slik at utsagnet blir sant, impliserer ikke nødvendigvis at det finnes én "global" verdi for $y$ som fungererer for alle $x$ *samtidig*. Dette er oppsummert i følgende teorem. > ##### Teorem 1 > La $P$ være et predikat av aritet 2. Da har vi at > > $\exists y\ \forall x\ P(x,y) \Rightarrow \forall x\ \exists y\ P(x,y)$, > > og > > $\forall x\ \exists y\ P(x,y) \not\Rightarrow \exists y\ \forall x\ P(x,y)$. Hvis utsagnene er *usanne*, får vi den omvendte implikasjonen (via negasjonsloven for implikasjoner fra utsagnslogikk). > ##### Korollar 1 > La $P$ være et predikat av aritet 2. Da har vi at > > $\neg(\forall x\ \exists y\ P(x,y)) \Rightarrow \neg(\exists y\ \forall x\ P(x,y))$, > > og > > $\neg(\exists y\ \forall x\ P(x,y)) \not\Rightarrow \neg(\forall x\ \exists y\ P(x,y))$. Med andre ord, hvis vi ikke kan velge en $y$ for hver $x$ slik at utsagnet blir sant, så kan vi heller ikke finne en global $y$ som fungerer for alle $x$ samtidig; men hvis vi vet at det ikke finnes en global $y$, så sier det oss ikke noe som helst om hvorvidt det kan finnes en måte å tilegne hver $x$ en $y$ på slik at utsagnet blir sant. > ##### Eksempel 7 > Husk at vi definerte $S(x,y) \coloneqq x < y$. > > Er utsagnet $\forall y\ \exists x\ S(x,y)$ sant eller usant? Hva med $\exists x\ \forall y\ S(x,y)$? (Svar i fotnote.[^2]) #### 1.3 Kvantorer og negasjoner La $P$ være et predikat av aritet $1$ over universet $U = \{1,2,3,4\}$. Det betyr at $P(1), P(2), P(3)$ og $P(4)$ er fire utsagn. Hvis vi skriver $\forall x\ P(x)$, så betyr det at utsagnet $P(1) \land P(2) \land P(3) \land P(4)$ er sant. Hva hvis vi har at $\neg \forall x\ P(x)$? Ved å sette inn utsagnet over, får vi at $\neg(P(1) \land P(2) \land P(3) \land P(4))$ må være sant, som via De Morgans lov gir oss $\neg P(1) \lor \neg P(2) \lor \neg P(3) \lor \neg P(4)$. Men da har vi bare sagt at det finnes en $x$ slik at $\neg P(x)$! Dermed kan vi skrive dette som $\exists x\ \neg P(x)$. > ##### Teorem 2 > La $P$ være et predikat av aritet $1$. Da har vi at > > $\neg \forall x\ P(x) \Leftrightarrow \exists x\ \neg P(x)$, > > og > > $\neg \exists x\ P(x) \Leftrightarrow \forall x\ \neg P(x)$. Gjenta gjerne "utledningen" vi gjorde over med $\neg \exists x\ P(x)$, og sjekk at det du får stemmer overens med den andre setningen i teoremet! Det følger at vi alltid kan bytte ut symbolet $\forall$ med en kombinasjon av $\exists$ og $\neg$, og vice versa. > ##### Korollar 2 > La $P$ være et predikat av aritet $1$. Da har vi at > > $\forall x\ P(x) \Leftrightarrow \neg \neg \forall x\ P(x) \Leftrightarrow \neg(\exists x\ \neg P(x))$, > > og > > $\exists x\ P(x) \Leftrightarrow \neg \neg \exists x\ P(x) \Leftrightarrow \neg(\forall x\ \neg P(x))$. #### Kvantorer og konnektiver Kvantorene *distribuerer* forskjellig over konnektivene $\lor$ og $\land$. Vi viser dette via et par eksempler. La oss begynne med ekistenskvantoren. La $x$ være et naturlig tall, la predikatet $P(x)$ evaluere til *sant* dersom $x \in \mathbb{N}$ er et partall, og la $Q(x)$ evaluere til *sant* dersom $x$ er et oddetall. Hvis man skriver $\exists x\ (P(x) \lor Q(x))$, så vil vi da lese dette som "det finnes et naturlig tall $x$ slik at $x$ er et oddetall eller et partall". Dette er så klart sant, siden alle naturlige tall enten er oddetall eller partall. Vi ser at det vi også kunne skrevet $\exists x\ P(x) \lor \exists x\ Q(x)$, altså "det finnes et naturlig tall $x$ slik at $x$ er et partall *eller* det eksisterer et naturlig tall $x$ slik at $x$ er et oddetall". Vi kunne også gått andre veien, og vi har dermed en ekvivalens. Men med "og"-konnektiven $\land$ fungerer ikke denne ekvivalensen lenger: Hvis jeg skriver $\exists x\ P(x) \land \exists x\ Q(x))$, så er dette sant, fordi det finnes både naturlige tall som er partall og naturlige tall som er oddetall. Men hvis jeg skriver $\exists x\ (P(x) \land Q(x))$, så er dette usant, fordi det eksisterer ikke tall som *både* er partall og oddetall. For universalkvantoren får vi den omvendte situasjonen. La universet være de naturlige tallene, og la $x \in A \subseteq \mathbb{N}$, altså er $x$ tall hentet fra en delmengde av de naturlige tallene. La nå predikatet $P(x)$ være sann dersom $x \in \mathbb{N}$ er et primtall, og la $Q(x)$ være sann dersom $x$ er et oddetall (som før). Hvis jeg skriver $\forall x\ (P(x) \land Q(x))$, vil jeg da lese det som at "alle tall $x$ er både primtall og oddetall". Hvis jeg lar delmengden $A$ være mengden av alle primtall større enn (men ikke inkludert) $2$, vil dette være oppfylt. Da er det også sant at $\forall x\ P(x) \land \forall x\ Q(x)$, altså at alle $x \in A$ er primtall, og alle $x \in A$ er oddetall. Vi ser at vi kunne også gått andre veien, og vi har en ekvivalens. Men igjen bryter ekvivalensen sammen for den andre konnektiven, $\lor$. For å se dette, la predikatene $P$ og $Q$ være som over, men la delmengden $A$ være lik $\{1, 2, 3\}$, og la $x \in A$. Da er utsagnet $\forall x\ P(x) \lor Q(x)$, som vi leser som "alle elementer i $A$ er enten et primtall eller et oddetall" *sant*, for alle elementene i $A$ er enten et oddetall ($1$), eller et primtall ($2$), eller begge deler ($3$). Men utsagnet $\forall P(x) \lor \forall x\ Q(x)$, som vi leser som "alle elementer i $A$ er primtall *eller* alle elementer i $A$ er oddetall" blir *usant*, fordi det finnes både et element som ikke er et primtall ($1$), og et element som ikke er et oddetall ($2$). Det neste teoremet oppsummerer dette. > ##### Teorem 3 > La $P$ og $Q$ være predikater av aritet $1$. Da har vi for eksistenskvantoren $\exists$ at > > $\exists x (P(x) \lor Q(x)) \Leftrightarrow \exists x P(x) \lor \exists x Q(x)$, > > $\exists x (P(x) \land Q(x)) \not\Leftrightarrow \exists x P(x) \land \exists x Q(x)$, > > og for universalkvantoren $\forall$ at > > $\forall x (P(x) \land Q(x)) \Leftrightarrow \forall x P(x) \land \forall x Q(x)$, > > $\forall x (P(x) \lor Q(x)) \not\Leftrightarrow \forall x P(x) \lor \forall x Q(x)$. (Merk at moteksemplene vi ga i teksten over er nok til å bevise ikke-ekvivalensene, men at for å bevise *ekvivalensene* så må man gjøre litt mer jobb. Vi holder oss her til å presentere en intuisjon for hvorfor det virker sannsynlig at de holder, og behandler dem som "lov" heretter.) ### 2. Relasjoner og predikater La $A$ være en mengde. En delmengde av $A^n$ kalles en $n$-ær relasjon over $A$, eller en relasjon av aritet $n$ over $A$. En relasjon av aritet $2$ kalles ofte en *binærrelasjon*, eller bare en "relasjon". Det vil si at når vi ikke spesifiserer ariteten, så betyr det stort sett at vi mener relasjoner av aritet $2$. Når det er hensiktsmessig, vil vi spesifisere ariteten. Relasjoner av aritet $n$ og predikater av aritet $n$ er tett koblet til hverandre. La $R$ være en $n$-ær relasjon over $A$. Vi kan se på $R$ som et predikat ved å definere $R(a_1, a_2, \dots, a_n) \coloneqq ((a_1, a_2, \dots, a_n) \in R)$, altså at *predikatet* $R(a_1, a_2, \dots, a_n)$ tar sannhetsverdi *sann* hvis og bare hvis $(a_1, a_2, \dots, a_n)$ er i *relasjonen* $R$. > ##### Eksempel 8 > La mengden $A \subseteq \mathbb{Z}^3$ være definert som $A = \{(x,y,z) \in \mathbb{Z}^3\ |\ x + y = z \}$. Da er $A$ en relasjon av aritet $3$, og vi har for eksempel at $(1,3,4) \in A$, og at $(1,1,1) \not\in A$. > > La nå $A(x,y,z) \coloneqq ((x,y,z)\in A) \Leftrightarrow (x+y = z)$. Da er $A(x,y,z)$ et predikat av aritet 3. Hvis vi lar universet være $\mathbb{Z}$, kan du finne en kvantisering av $x$, $y$ og $z$ slik at det resulterende utsagnet blir sant? (Svar i fotnote.[^3]) Motsatt vei så kan vi for ethvert predikat av aritet $n$ over universet $U$, definere en $n$-ær relasjon over $U$. La $P$ være et slikt predikat. Vi definerer da relasjonen $R_P$ som følger: $R_P = \{ (x_1, x_2, \dots, x_n) \in U^n\ |\ P(x_1, \dots, x_n) \}$. Med ord: Relasjonen $R_P$ er mengden av tupler $(x_1, \dots, x_n)$, hvor hver $x_i$ er et element i $U$, slik at predikatet $P(x_1, \dots, x_n)$ tar sannhetsverdi *sann*. (Husk at vi vanligvis ikke skriver eksplisitt at $P(\dots) = \mathcal{true}$ eller $P(\dots) = \mathcal{false}$, men lar heller bare $P(\dots)$ og $\neg P(\dots)$ stå for det samme.) #### 2.1 Tolkning av setninger Husk at vi i utsangslogikk starter med noen atomære formler, for eksempel $A = \{P, Q, R\}$, og bygger opp logiske uttrykk fra dem. Gitt et uttrykk over $A$, får den da en sannhetsverdi straks vi har valgt en tilordning. Når vi har et predikatlogisk uttrykk, eller en *setning*, må vi på samme måte bestemme hva de ulike symbolene skal bety: Variabler som $x, y, \dots$ trenger ikke å fortolkes, men de må bli gitt et univers $U$. Symbolene som representerer predikater må derimot tolkes eller konkretiseres, og det samme må funksjoner, dersom de oppstår i en predikatlogisk setning. > ##### Eksempel 9 > La $\varphi = \forall x \forall y\ (P(x,y) \rightarrow P(y,x))$. > > Å *tolke* $\varphi$ innebærer da å velge et univers $U$, samt et konkret predikat $P$. I praksis uttrykker vi ofte valget av $P$ som en relasjon, i dette tilfellet av aritet $2$. > > La oss se på to tolkninger av $\varphi$, (hvor vi i begge tilfellene for enkelhetens skyld spesifiserer relasjonen $R_P$ tilhørende predikatet $P$, heller enn $P$ selv). > > 1. La $U = \mathbb{Z}$ og $R_P = \{(x,y) \in \mathbb{Z}^2\ |\ x \leq y \}$. Er $\varphi$ da sann eller usann? (Svar i fotnote.[^4]) > 2. La $U = \{1,2,3\}$ og $R_P = \{(1,2), (2,1), (3,3)\}$ . Er da $\varphi$ sann eller usann? (Svar i fotnote.[^5]) [^1]: Sann, Usann, Usann [^2]: Det første utsagnet er *usant*, fordi det finnes et moteksempel: Hvis $y = 0$, så eksisterer det ikke noe naturlig tall $x$ slik at $x < y$, (da $0$ allerede er det minste naturlige tallet). *Korollar 1* lar oss umiddelbart konkludere med at da må det andre utsagnet også være *usant*. Du kan se dette ved å legge merke til at moteksempelet vi nettopp ga er gyldig uansett om vi tillater at $x$ avhenger av $y$ eller ikke. [^3]: $\forall x \forall y \exists z\ A(x,y,z)$: Uansett hva $x$ og $y$ er, så vil det finnes et heltall $z$ slik at $x + y = z$. Tilsvarende har vi at $\forall x \forall z \exists y\ A(x,y,z)$ og $\forall y \forall z \exists x\ A(x,y,z)$ begge er sanne, og det samme er $\forall x \exists y \exists z\ A(x,y,z)$ og $\exists x \exists y \exists z\ A(x,y,z)$. (Disse utsagnene er faktisk implisert av det første – ser du hvorfor?) Hva med de andre mulighetene? Vel, for eksempel så må $\exists x \forall y \forall z\ A(x,y,z)$ være *usann*, fordi vi kan ikke finne én $x$ slik at $x + y = z$ uansett hvilke heltall $y$ og $z$ er. Ser du hvorfor $\forall x \forall y \forall z\ A(x,y,z)$ og $\forall x \exists y \forall z\ A(x,y,z)$ også må være usanne? [^4]: Usann: $\varphi$ sier da at uansett hvilke to heltall du velger, så dersom $x \leq y$, så må $y \leq x$. Det er lett å komme opp med moteksempler til dette utsagnet – faktisk så vil alle valg av $x$ og $y$ slik at $x \neq y$ være gyldige moteksempler! [^5]: Sann: Her er det bare tre elementer i relasjonen å sjekke, så dette kan enkelt gjøres for hånd: $(1,2)$ er i $R_P$, og det er $(2,1)$ også, så da er uttrykket $((1,2) \in R_P) \rightarrow ((2,1) \in R_P)$ sant; og tilsvarende for de to andre elementene.