Totuusarvo ja totuustaulukko

Lauseen määritelmän mukaisesti sen totuus tai epätotuus on pystyttävä määrittämään. Käytetään totuusarvoja kuvaamaan lyhyesti sitä, onko jokin lause tosi vai epätosi. Toden lauseen totuusarvo on $1$ (myös $\mathbf{t}$ tai $\top$) ja epätoden lauseen totuusarvo on $0$ (myös $\mathbf{e}$ tai $\bot$).

Jos lauseiden $p$ ja $q$ totuusarvot tiedetään, niin niistä konnektiivien avulla muodostettujen monimutkaisempien lauseiden totuusarvot määräytyvät seuraavasta totuustaulukosta.

$p$	$q$	$\lnot p$	$p\land q$	$p\lor q$	$p\rightarrow q$	$p\leftrightarrow q$
$1$	$1$	$0$	$1$	$1$	$1$	$1$
$1$	$0$	$0$	$0$	$1$	$0$	$0$
$0$	$1$	$1$	$0$	$1$	$1$	$0$
$0$	$0$	$1$	$0$	$0$	$1$	$1$

Esimerkiksi siis jos $p$ on epätosi ja $q$ on tosi, niin lause $p \rightarrow q$ on tosi.

Matematiikassa sovitaan, että lause $p\lor q$ on tosi myös silloin, kun molemmat lauseet $p$ ja $q$ ovat tosia. Luonnollisessa kielessä konnektiivi ”tai” voidaan tulkita myös poissulkevana, ja merkitys on aina pääteltävä asiayhteydestä. Lauseet ”liittymislahjaksi saat repun tai puseron” ja ”opiskelemaan pääsee, jos kirjoittaa laudaturin matematiikasta tai saa yli kymmenen pistettä pääsykokeesta” havainnollistavat tätä eroa.

Myös implikaation määritelmä voi tuntua intuition vastaiselta. Konnektiivi ilmaisee välttämätöntä seurausta, mutta ei mitenkään vaadi yhdistämiensä lauseiden liittyvän toisiinsa. Lause ”jos kuu on juustoa, niin $1 + 4 = 5$” ei tunnu kovin mielekkäältä, mutta tehtyjen havaintojen perusteella se on tosi. Määritelmä on kuitenkin perusteltu, sillä esimerkiksi lauseiden $x > 3$ ja $x > 2$ tapauksessa yhdistettyä lausetta

$$x>3\rightarrow x>2$$

on pidettävänä totena, sillä $3 > 2$.

Esimerkki.

Tutki totuustaulukon avulla, milloin lause $(p\rightarrow q)\land(q\rightarrow p)$ on tosi ja milloin epätosi.

Ratkaisu.

Rakennetaan lauseen totuustaulukko osa kerrallaan.

$p$	$q$	$p\rightarrow q$	$q\rightarrow p$	$(p\rightarrow q)\land(q\rightarrow p)$
$1$	$1$	$1$	$1$	$1$
$1$	$0$	$0$	$1$	$0$
$0$	$1$	$1$	$0$	$0$
$0$	$0$	$1$	$1$	$1$

Huomataan, että kysytty lause on tosi, kun $p$ ja $q$ ovat molemmat tosia tai kun $p$ ja $q$ ovat molemmat epätosia. Muulloin lause on epätosi.

Esimerkki.

Osoita, että lauseella ”jos sataa, niin jään kotiin” on aina sama totuusarvo kuin lauseella ”ei sada tai jään kotiin”.

Ratkaisu.

Merkitään muuttujalla $p$ lausetta ”sataa” ja muuttujalla $q$ lausetta ”jään kotiin”. Annetut lauseet voidaan tällöin kirjoittaa konnektiivien avulla muodossa $p \rightarrow q$ ja $\neg p \lor q$. Kirjoitetaan molempien lauseiden totuustaulukko.

$p$	$q$	$p\rightarrow q$	$\lnot p$	$\lnot p\lor q$
$1$	$1$	$1$	$0$	$1$
$1$	$0$	$0$	$0$	$0$
$0$	$1$	$1$	$1$	$1$
$0$	$0$	$1$	$1$	$1$

Koska lauseiden $p \rightarrow q$ ja $\neg p \lor q$ sarakkeet ovat samat, niillä on jokaisessa tilanteessa oltava sama totuusarvo.

Esimerkki.

Mitkä ovat lauseiden $p \lor \neg p$ ja $p \land \neg p$ totuusarvot?

Ratkaisu.

Laaditaan totuustaulukot

$p$	$\neg p$	$p \lor \neg p$
$1$	$0$	$1$
$0$	$1$	$1$

ja

$p$	$\neg p$	$p \land \neg p$
$1$	$0$	$0$
$0$	$1$	$0$

Lause $p \lor \neg p$ on siis aina tosi ja lause $p \land \neg p$ aina epätosi.

Määritelmä.

Lausetta, joka on aina tosi riippumatta siinä esiintyvien lauseiden totuusarvoista, kutsutaan tautologiaksi. Vastaavasti lausetta, joka on aina epätosi kutsutaan ristiriidaksi.

Jos $A\leftrightarrow B$ on tautologia, niin sanotaan että lauseet $A$ ja $B$ ovat loogisesti ekvivalentteja ja merkitään $A\Leftrightarrow B$. Vastaavasti jos $A\rightarrow B$ on tautologia, niin sanotaan että $B$ on lauseen $A$ looginen seuraus ja merkitään $A\Rightarrow B$.

Korostetaan vielä näiden merkintöjen eroa. Merkintä $A\rightarrow B$ tarkoittaa lauselogiikan lausetta, jonka totuusarvo voi lauseista $A$ ja $B$ riippuen olla joko tosi tai epätosi. Merkitsemällä $A\Rightarrow B$ tarkoitetaan sitä, että lause $A\rightarrow B$ on aina tosi. Tämä puolestaan tarkoittaa sitä, että lause $B$ on tosi aina kun $A$ on tosi. Tämä merkintä on tärkeä matematiikassa, sillä monet tulokset voidaan esittää implikaationa $A\Rightarrow B$, missä lausetta $A$ kutsutaan oletukseksi ja lausetta $B$ väitteeksi. Tällaisen tuloksen todistus on keino osoittaa väite $B$ todeksi silloin, kun oletus $A$ on tosi.

Vastaavasti merkinnällä $A \Leftrightarrow B$ tarkoitetaan sitä, että lause $A \leftrightarrow B$ on aina tosi. Aikaisemmassa esimerkissä osoitettiin, että lauseilla $p \rightarrow q$ ja $\neg p \lor q$ on samat totuusarvot, jolloin ekvivalenssin totuusarvojen määritelmän nojalla lause $(p \rightarrow q) \leftrightarrow \neg p \lor q$ on tautologia. Siis

$$p \rightarrow q \Leftrightarrow \neg p \lor q.$$

Tautologiat ovat keskeinen työkalu matemaattisessa päättelyssä, kun todistetaan jotakin väitettä tai muokataan sitä muodosta toiseen.

Lause.

Jos $p$, $q$ ja $r$ ovat lauseita, niin seuraavat loogiset ekvivalenssit ja seuraukset ovat voimassa.

1. $\neg\neg p \Leftrightarrow p$ (kaksoisnegaation laki),
2. $p \land q \Leftrightarrow q \land p$ ja $p \lor q \Leftrightarrow q \lor p$ (vaihdantalait),
3. $p \land (q \land r) \Leftrightarrow (p \land q) \land r$ ja $p \lor (q \lor r) \Leftrightarrow (p \lor q) \lor r$ (liitäntälait),
4. $p \land (q \lor r) \Leftrightarrow (p \land q) \lor (p \land r)$ ja $p \lor (q \land r) \Leftrightarrow (p \lor q) \land (p \lor r)$ (osittelulait),
5. $\neg(p \land q) \Leftrightarrow \neg p \lor \neg q$ ja $\neg(p \lor q) \Leftrightarrow \neg p \land \neg q$ (de Morganin lait)
6. $p \leftrightarrow q \Leftrightarrow (p \rightarrow q) \land (q \rightarrow p)$ (ekvivalenssilaki),
7. $p \rightarrow q \Leftrightarrow \neg q \rightarrow \neg p$ (kontrapositiolaki),
8. $p \land (p \rightarrow q) \Rightarrow q$ (modus ponens, suora todistus),
9. $(p \rightarrow q) \land \neg q \Rightarrow \neg p$ (modus tollens).

Nämä säännöt voidaan todistaa suoraviivaisesti kirjoittamalla totuustaulukko. Käytännössä sääntöjä ei pidä eikä tarvitse opetella ulkoa, sillä ne ovat varsin intuitiivisia.

Esimerkki.

Olkoon $p$ lause ”$n$ on parillinen kokonaisluku”, sekä $q$ lause ”$n < 0$”. Tällöin väitteen $p \lor q$, eli

$n$ on parillinen tai $n<0$

negaatio $\lnot(p\lor q)$ on de Morganin lain nojalla loogisesti ekvivalentti lauseen $\lnot p\land\lnot q$ kanssa, eli se voidaan luonnollisella kielellä kirjoittaa väitteenä

$n$ on pariton ja $n\ge0$.

Huomautus.

1. Koska konjunktio ja disjunktio ovat liitännäisiä, lauseet $(p \land q) \land r$ ja $p \lor (q \lor r)$ voidaan kirjoittaa myös ilman sulkeita muodoissa $p \land q \land r$ ja $p \lor q \lor r$.
2. Päättelysääntö modus ponens sanoo, että lause $q$ on looginen seuraus lauseista $p$ ja $p \rightarrow q$. Toisin sanoen, jos $p$ on tosi ja $q$ on lauseen $p$ seuraus, niin $q$ on tosi. Tämä on suora todistusmenetelmä.
3. Päättelysääntö modus tollens sanoo, että lause $\neg p$ on looginen seuraus lauseista $p \rightarrow q$ ja $\neg q$. Toisin sanoen, jos $q$ on lauseen $p$ seuraus ja $q$ on epätosi, niin $p$ on epätosi. Erityisesti ristiriidat ovat aina epätosia, eli jos lause $p$ johtaa ristiriitaan, sen on oltava epätosi. Tämä on todistus ristiriidan avulla.

Tautologioita voidaan käyttää myös seuraavan hyödyllisen tuloksen todistamisessa.

Lause.

Jokainen lauselogiikan lause voidaan esittää sellaisessa loogisesti ekvivalentissa muodossa, jossa esiintyy vain konnektiiveja $\lnot$, $\land$ ja $\lor$.

Todistus.

Hahmotellaan todistuksen idea. Aikaisemmin osoitettiin, että

$$p \rightarrow q \Leftrightarrow \neg p \lor q,$$

joten jokainen lauseessa esiintyvä implikaatio voidaan korvata tällä lauseella. Tämän tuloksen ja ekvivalenssilain nojalla

$$p \leftrightarrow q \Leftrightarrow (p \rightarrow q) \land (q \rightarrow p) \Leftrightarrow (\neg p \lor q) \land (\neg q \lor p),$$

joten myös jokainen ekvivalenssi voidaan korvata lauseella, jossa esiintyy vain annettuja konnektiiveja. $\square$

Posting submission...