Sisältö[-] Feedback

Lausekalkyyli eli propositiologiikka [-]

Jos $a$ ovat $b$ lauseita tai väitteitä, jotka voivat olla tosia tai epätosia mutta ei mitään siltä väliltä niin määrittelemme seuraavat (hyvin luonnolliset) ns. konnektiivit:

  • Lause $(a\And b)$ on tosi kun $a$ on tosi ja $b$ on tosi.
  • Lause $(a\Or b)$ on tosi kun $a$ on tosi tai $b$ on tosi (ja myös kun molemmat ovat tosia).
  • Lause $(\Neg a)$ on tosi kun $a$ ei ole tosi eli $a$ on epätosi.
Lisäksi määrittelemme implikaation ja ekvivalenssin seuraavasti:
  • Lause $(a\to b)$ on tosi kun $((\Neg a)\Or b)$ on tosi, eli kun $b$ on tosi tai $a$ on epätosi.
  • Lause $(a\leftrightarrow b)$ on tosi kun $((a\to b)\And (b\to a))$ on tosi.

Lauseet ovat joko ns. atomilauseita tai sitten muotoa $(a\And b)$, $(a\Or b)$ tai $(\Neg a)$ missä $a$ ja $b$ ovat lauseita (ja kun käytetään sopivia prioriteettisääntöjä voidaan ''turhat'' sulut jättää pois).

Vaihtoehtoisia merkintöjä [+]

  • Matemaattisessa logiikassa käytetään yleisesti $\And$:n sijasta $\wedge$, $\Or$:n sijasta $\vee$ ja $\Neg\!$:n sijasta $\neg$.
  • Eri ohjelmointikielissä käytetään $\And\!$:n sijasta mm. $\&$, $\&\&$ tai $\text{and}$, $\Or\!$:n sijasta mm. $|$, $||$ tai $\text{or}$ sekä negaation $\Neg\!$:n sijasta mm. $!$ ja $\text{not}$.
  • Implikaatiot $\to$ ja $\leftrightarrow$ kirjoitetaan usein muodossa $\Rightarrow$ ja $\Leftrightarrow$.
  • Joukkojen määrittelyssä käytetään usein $\And\!$:n sijasta pilkkua eli kirjoitetaan $\{x\in \R\mid x^3-x^2-4\cdot x +4=0,\, x>0\}$ kun tarkoitetaan $\{x\in \R\mid x^3-x^2-4\cdot x +4=0 \And x>0\}$ (ja voidaan myös kirjoittaa $\{x\in \R\mid x^3-x^2-4\cdot x +4=0 \text{ ja } x>0\}$).

Implikaatio [+]

Huomaa, että implikaatio $a\to b$ on lause, joka on joko tosi tai epätosi mutta ei sano mitään syy-seuraus suhteesta vaikka voimme sanoa "jos $a$ niin $b$". Esimerkiksi lause
$(\sqrt 2\in \Q) \to (-1>0)$
on tosi koska $(\sqrt 2\in \Q)$ on epätosi jolloin on yhdentekevää onko väite $(-1>0)$ tosi vai ei. Sen sijaan tällainen lause ei ole kovin mielekäs kun taas implikaatio
$(3>2) \to (9>4)$
on sekä tosi että mielekäs koska se on erikoistapaus lauseesta $((x>y) \And (y\geq 0))\to (x^2>y^2)$
joka sanoo, että funktio $x\mapsto x^2$ on aidosti kasvava joukossa $[0,\infty\ipr$.

Toinen esimerkki siitä, että implikaatio $a \to b$ ei vastaa jokapäiväistä kielenkäyttöä "jos $a$ niin $b$" tai "$a$:sta seuraa $b$" on että lause
$(a\to b)\Or (b\to a)$
on tautologia eli tosi riippumatta lauseiden $a$ ja $b$ totuusarvoista.

Esimerkkejä [+]

Olkoon $A=\set{1,2,3,4}$, $B=\set{0,3,4}$ ja $C=\set{x\mid x \text{ on kokonaisluku }\geq 2}$. Mitkä seuraavista väitteistä ovat tosia?

  • $x\in A\cap C \rightarrow x\in B$ kaikilla $x$? Vastaus [+]
    Koska $A\cap C=\set{2,3,4}$ niin pätee $2\in A\cap C$ mutta koska $2\notin B$ niin tämä väite ei ole tosi (ja väite sanoo, että $A\cap C\subseteq B$).
  • $A\subseteq B \rightarrow C\subseteq A$? Vastaus [+]
    Koska $2\in A$ mutta $2\notin B$ niin ei päde $A\subseteq B$ ja näin ollen implikaatio $A\subseteq B \rightarrow C\subseteq A$ on tosi.
  • On olemassa $y\in C$ siten, ettei päde $y\in B \rightarrow y\in A$? Vastaus [+]
    Väite $y\in B \rightarrow y\in A$ ei päde jos ja vain jos $y\in B$ ja $y\notin A$ eli $y\in B\setminus A=\{0\}$ ja koska $0\notin C$ niin väite on epätosi.

Lausekalkyylin todistukset ja päättelysäännöt [+]

Todistus on lista lauseita perusteluineen ja jokainen lause on joko aksiomi (jolloin perustelu on oletus) tai johdettu aikaisemmistä lauseista jonkin päättelysäännön avulla (jolloin perustelu on kyseiset lauseet ja niihin sovellettava päättelysääntö). Esimerkiksi ns. modus ponens eli
$\qquad x$
$\qquad \underline {x\to y}$
$\qquad y$
on tärkeä päättelysääntö ja perustuu siihen, että $(x\And (x\to y))\to y$ on tautologia, eli aina tosi riippumatta $x$:n ja $y$:n totuusarvoista. Tämä päättelysääntö (kuten muutkin) käytetään siten, että jos todistuslistassa on jo lauseet $a$ ja $a\to b$ niin listaan lisätään lause $b$.

Mutta huomaa, että tämä todistustapa sopii hyvin jos tavoiteena on saada ''kone'' hyväksymään väitteen oikeellisuutta mutta paljon huonommin jos lukijana tai kuulijana on ihminen. Mutta jos todistuksen esittää epämuodollisemmassakin muodossa ilman logiikan merkintöjä niin voidaan edelleen vaatia, että tätä todistusta on pystyttävä täydentämään lisävaiheilla kunnes lopulta jokaiselle vaiheelle olisi osoitettavissa tietty muodollinen päättelysääntö.

Esimerkki [+]

Olkoot $p$ ja $q$ kaksi lausetta. Nyt todistamme, että $q$ on tosi jos $p\And (\Neg p)$ on tosi, eli jos oletuksena on ristiriitainen väite voimme todistaa minkä väitteen tahansa. Päättelysääntöinä käytämme tässä seuraavia:

Sääntö 1Sääntö 2Sääntö 3Sääntö 4
\(\begin{aligned} &x\Or y\\ &\rlap{\underline{~~~~~~}}\Neg x\\ &y\end{aligned}\) \( \begin{aligned} & \underline{x\And y}\\ & x \end{aligned} \) \( \begin{aligned} &\rlap{\underline{~~~~~~~~~~}} x\\ & x\Or y\end{aligned} \) \( \begin{aligned} & \rlap{\underline{~~~~~~~~~~~~}} {x\And y}\\ & y\And x \end{aligned} \)

Todistus on seuraavanlainen:

  1. $p\And (\Neg p)$: Oletus
  2. $p$: (1) ja Sääntö 2 missä $x=p$ ja $y=\Neg p$
  3. $p \Or q$: (2) ja Sääntö 3 missä $x=p$ ja $y=q$
  4. $(\Neg p) \And p$: (1) ja Sääntö 4 missä $x=p$ ja $y=\Neg p$
  5. $\Neg p$: (4) ja Sääntö 2 missä $x=\Neg p$ ja $y=p$
  6. $q$: (3), (5) ja Sääntö 1 missä $x=p$ ja $y=q$.
Toinen, yksinkertaisempi todistus voisi perustua siihen että $p\And (\Neg p)$ on epätosi jolloin $(p\And (\Neg p))\to q$ on tosi ja sitten voisimme soveltaa modus ponensia.

Predikaattikalkyyli [-]

Predikaattikalkyyli on lausekalkyylin laajennus, jossa operaatioden eli konnektiivien ($\Neg$, $\And$, $\Or$, $\to$ ja $\leftrightarrow$) lisäksi käytetään universaali- ja eksistenssi kvanttorit $\forall$ (''kaikilla'') ja $\exists$ (''on olemassa''), ja lauseiden lisäksi käytetään muuttujia $x, y,\ldots$ ja predikaatteja $P, Q,\ldots$. Predikaateilla on äärellinen määrä argumentteja, esim. $P(x)$, $Q(x,y)$, jne., ja esimerkiksi $Q(x,y)$ on jokaisella $x$ ja $y$ joko tosi tai epätosi. Predikaatti, jonka argumenttien lukumäärä on $0$ on lausekalkyylin lause.

  • Lause $\forall x \, P(x)$ on tosi kun $P(x)$ on tosi kaikilla $x$.
  • Lause $\exists x \, P(x)$ on tosi kun on olemassa $x$ siten, että $P(x)$ on tosi.
Predikaattikalkyylin todistusteoria [+]
on samankaltainen kuin lausekalkyylin mutta lisää sääntöjä tarvitaan tietenkin kvanttoreita varten. Siinä yhteydessä ja yleisemminkin tärkein huomio on että jos pystytään osoittamaan, että jokin väite pätee mielivaltaisella alkiolla $x$ (minkälainen se sitten onkaan) niin se pätee kaikilla senkaltaisilla alkioilla.

Esimerkki [+]

Väitteen ''Kaikilla reaaliluvuilla $x$ pätee, että jos $x$ on positiivinen niin on olemassa positiivinen reaaliluku $y$ siten että $y < x$'' voimme predikaattikalkyylin merkinnöillä kirjoittaa muodossa \[ \forall x\, (P(x) \to (\exists y\, (P(y) \And L(y,x)))) \] missä $P(x)$ on tosi jos $x$ on positiivinen reaaliluku, eli $P(x)$ on lause $(x\in \R)\And (x>0)$ missä siis $x\in \R$ ja $x>0$ ovat predikkaatteja, ja $L(y,x)$ on tosi jos $y$ on pienempi kuin $x$ eli $L(y,x)$ on predikaatti $(y< x)$.

Tämän väitteen voimme todistaa esimerkiksi näin:
Olkoon $x > 0$ mielivaltainen reaaliluku. Silloin myös $y=\frac x2$ on positiivinen reaaliluku ja koska $x >0 $ niin $y=\frac x2 < x$.
Sen sijaan seuraava päättely ei kelpaa: Olkoon $x$ jokin positiivinen reaaliluku, esimerkiksi $x=2$. Silloin $1$ on positiivinen reaaliluku joka on pienempi kuin $x=2$ koska tämä päättely todistaa oikeaksi ainoastaan lauseen $\exists x (x\in \R \And x>0 \And \exists y(y\in \R \And y > 0 \And y < x))$.

Prioriteettijärjestys, $\forall x\in A$ ja $\exists x\in A$ [+]

Sulkuja käyttämällä lause- ja predikaattikalkyylin lauseet tulevat yksikäsitteisellä tavalla määritellyksi, mutta koska liian monta sulkua tekee lukemisen hankalaksi (ihmiselle toisin kuin tietokoneelle) niin loogiset konnektiivit ja kvanttorit evaluoidaan tavallisesti seuraavassa järjestyksessä (sulkujen sisällä): Ensin $\Neg$, sitten $\forall$ ja $\exists$, sitten $\And$ ja $\Or$ ja lopuksi $\to$ ja $\leftrightarrow$.

Lauseet $\forall x\in A\, (P(x))$ ja $\exists x\in A\, (P(x))$ ovat lyhenteitä lauseista \begin{align*} &\forall x\, (x\in A \to P(x)),\\ & \exists x\, (x\in A \And P(x)), \end{align*} ja tarkoittavat (tietenkin) että "kaikilla $A$:n alkiolla $x$ pätee $P(x)$" ja "on olemassa $A$:n alkio $x$, jolla $P(x)$ pätee".

Negaatio $\Neg\!$, konnektiivit $\And$ ja $\Or$ sekä kvanttorit $\forall$ ja $\exists$ [+]

Kaikilla lauseilla $a$ ja $b$ pätee \begin{align*} \Neg (a\And b) &\leftrightarrow (\Neg a) \Or (\Neg b),\\ \Neg (a\Or b) &\leftrightarrow (\Neg a) \And (\Neg b), \end{align*} eli esimerkiksi väiteet $a$ ja $b$ eivät ole tosia täsmälleen silloin kun $a$ ei ole tosi tai $b$ ei ole tosi. Lause $\Neg (a\And b) \leftrightarrow (\Neg a) \Or (\Neg b)$ on ns. tautologia koska se on tosi riippumatta $a$:n ja $b$:n totuusarvoista.

Samoin kaikilla predikaateilla $P$ pätee \begin{align*} \Neg(\forall x(P(x))) &\leftrightarrow \exists x(\Neg P(x)),\\ \Neg(\exists x(P(x))) &\leftrightarrow \forall x(\Neg P(x)). \end{align*}

Esimerkki: Järjestetyn parin koordinaatit [+]

Parin $[x,y]$ (tai $(x,y)$ erityisesti jos kyseessä on $xy$-tason piste) ensimmäinen koordinaatti on (tietenkin) $x$ ja toinen on $y$.

Jos otamme parin määritelmäksi $[a,b]=\{\{a\},\{a,b\}\}$ niin voimme määritellä predikaatit $E(p,x)$ ja $T(p,y)$, jotka sanovat, että $x$ on $p$:n ensimmäinen koordinaatti ja $y$ on $p$:n toinen koordinaatti seuraavalla tavalla: \[ E(p,x)=\forall z((z\in p)\to(x\in z)) \] (tai lyhyemmin $\forall z\in p\, (x\in z))$ ja missä $u==v$ on predikaatti, joka sanoo, että $u$ on sama joukko kuin $v$. Lyhyemmin tämän voimme esittää muodossa    

Viimeksi muokattu: G. Gripenberg,