"
  1. Insinöörimatematiikka 123 »
  2. Joukko-opin, logiikan ja todistamisen perusteita »
  3. Predikaattilogiikkaa

Predikaattilogiikkaa

Predikaattilogiikassa tutkitaan lauseiden lisäksi lausumia, eli predikaatteja \(p(x),q(x,y),\ldots\), joissa on yksi tai useampi muuttuja \(x,y,z,\ldots\). Esimerkiksi ”\(x\) on suomalainen kaupunki” ja ”\(y + z = 3\)” ovat predikaatteja. Lauseesta poiketen predikaatilla ei sinänsä ole totuusarvoa, vaan se riippuu muuttujien arvoista. Kiinnittämällä esimerkiksi \(x =\) Tampere, \(y = 2\) ja \(z = 5\) edellisistä lausumista tulee lauseet ”Tampere on suomalainen kaupunki” ja ”\(2 + 5 = 3\)”, joille on jälleen mahdollista määrittää totuusarvot.

Predikaattilogiikassa käytetään konnektiivien lisäksi kvanttoreita, joiden avulla käsitellään useampia muuttujien arvoja kerralla. Otetaan käyttöön universaalikvanttori \(\forall\) (kaikilla, ”for \(\forall\)ll”) ja olemassaolokvanttori \(\exists\) (on olemassa, ”there \(\exists\)xists”). Jos \(p(x)\) on predikaatti, jossa esiintyy muuttuja \(x\), niin kvanttoreilla \(\forall\) ja \(\exists\) sidottuja lauseita tulkitaan seuraavasti.

\[\begin{split}\begin{aligned} \forall x : p(x)&&&\text{kaikilla }x\text{ on ominaisuus }p\\ \exists x : p(x)&&&\text{on olemassa }x\text{, jolla on ominaisuus }p\end{aligned}\end{split}\]

Jos \(x\) valitaan erityisesti joukosta \(A\), voidaan merkitä myös \(\forall x \in L : p(x)\) ja \(\exists x \in L : p(x)\).

Esimerkki.

Mitkä ovat seuraavien lauseiden totuusarvot?

  1. \(\forall x \in \mathbb R: x < 3\)
  2. \(\exists x \in \mathbb R: x < 3\)
  3. \(\forall x \in \mathbb N: x \geq -7\)
Ratkaisu.
  1. Väite on tosi, jos jokainen reaaliluku on pienempi kuin \(3\). Kuitenkin \(4 \in \mathbb R\) ja \(4 \geq 3\), joten lause on epätosi.
  2. Väite on tosi, jos on olemassa sellainen reaaliluku \(x\), että \(x < 3\). Luku \(2 \in \mathbb R\) ja \(2 < 3\), joten lause on tosi.
  3. Väite on tosi, jos jokainen luonnollinen luku on vähintään yhtä suuri kuin \(-7\). Pienin luonnollinen luku on \(1 \geq -7\), joten lause on tosi.

Samassa lauseessa voi esiintyä useampia kvanttoreita, jolloin niiden merkitykset luetaan peräkkäin. Predikaatissa \(p(x, y)\) esiintyvät muuttujat \(x\) ja \(y\) voidaan sitoa kvanttorein kirjoittamalla esimerkiksi \(\forall x\exists y : p(x, y)\) tai \(\exists x \exists y : p(x, y)\).

Esimerkki.

  1. Lause \(\forall x \in \mathbb R\ \exists n \in \mathbb N: n > x\) tarkoittaa ilmausta ”jokaista reaalilukua \(x\) kohti löydetään sellainen luonnollinen luku \(n\), että \(n > x\)”. Lause on tosi.
  2. Lause \(\exists n \in \mathbb N\ \forall x \in \mathbb R: n > x\) tarkoittaa ilmausta ”on olemassa sellainen luonnollinen luku \(n\), että \(n > x\) jokaiselle reaaliluvulle \(x\)”. Lause on epätosi.

Edellisen esimerkin nojalla kvanttorien järjestystä ei saa vaihtaa. Selvitä aina itsellesi kvanttorein varustetun lauseen tulkinta luonnollisella kielellä ennen kuin jatkat sen käsittelyä.

Kvanttorit ja negaatio toimivat yhteen varsin luonnollisella tavalla.

Lause.

Loogiset ekvivalenssit \(\neg(\forall x : p(x)) \Leftrightarrow \exists x : \neg p(x)\) ja \(\neg (\exists x : p(x)) \Leftrightarrow \forall x : \neg p(x)\) ovat voimassa.

Todistus.
Täsmällinen todistus sivuutetaan, mutta havainnollistetaan tulosta luonnollisen kielen avulla. Jos on mahdollista löytää \(x\), jolla ei ole ominaisuutta \(p\), eli \(\exists x : \neg p(x)\), niin silloin sitä ei ole kaikilla mahdollisilla \(x\), \(\neg (\forall x : p(x))\). Vastaavasti, jos millään mahdollisella \(x\) ei ole ominaisuutta \(p\), \(\forall x : \neg p(x)\), niin on mahdotonta löytää sellaista \(x\), jolla se olisi, \(\neg(\exists x : p(x))\). \(\square\)

Esimerkki.

  1. Lause \(\exists x \in \mathbb R: x^2 < 0\) on tunnetusti epätosi, joten sen negaation olisi oltava tosi. Muodostetaan lauseen negaatio vaihtosäännön avulla.

    \[\neg(\exists x \in \mathbb R: x^2 < 0) \Leftrightarrow \forall x \in \mathbb R: \neg(x^2 < 0) \Leftrightarrow \forall x \in \mathbb R: x^2 \geq 0\]

    Nähdään, että negaatio on todellakin tosi.

  2. Muodostetaan aiemman esimerkin epätoden lauseen negaatio.

    \[\begin{split}\begin{aligned} \lnot(\exists n\in\mathbb N\ \forall x\in\mathbb R: n>x) &\Leftrightarrow \forall n\in\mathbb N\ \lnot(\forall x\in\mathbb R: n>x)\\ &\Leftrightarrow \forall n\in\mathbb N\ \exists x\in\mathbb R: \lnot(n>x)\\ &\Leftrightarrow \forall n\in\mathbb N\ \exists x\in\mathbb R: n\le x. \end{aligned}\end{split}\]

    Tämä väite on puolestaan tosi.