Teoria ja esimerkit tehtynä

Yhdistettyjen lauseiden totuusarvoja tutkitaan totuustaulujen avulla.

Taulukossa toden lauseen totuusarvo on 1 ja epätoden 0. (Tai t ja e.)

Negaation totuustaulu

¬A

Lauseen A negaatio on epätosi,
kun A on tosi.

Konjunktion totuustaulu

A ∧ B

Lauseiden A ja B konjunktio on tosi vain, kun molemmat lauseet ovat tosia.

Disjunktion totuustaulu

A ∨ B

Lauseiden A ja B disjunktio on tosi, kun ainakin toinen lause on tosi.

Implikaation totuustaulu

A ⇒ B

Lauseiden A ja B implikaatio on epätosi, kun A on tosi ja B on epätosi. Muulloin tosi.

”Epätodesta oletuksesta voi päätellä mitä tahansa.”

Ekvivalenssin totuustaulu

A ⇔ B

Lauseiden A ja B ekvivalenssi on tosi aina, kun molemmat lauseet ovat tosia tai molemmat epätosia.

Konnektiivien suoritusjärjestys (ellei sulut toisin määrää)

Negaatio
Konjunktio ( ) ja disjunktio ( ) vasemmalta oikealle
Implikaatio ( ) ja ekvivalenssi ( ) vasemmalta oikealle

Peräkkäiset samat konnektiivit kirjoitetaan ilman sulkeita.
(A ∧ B) ∧ C = A ∧ (B ∧ C) = A ∧ B ∧ C
¬(¬A) = ¬¬A = A

HUOM! Jos yhdistetty lause on muodostettu n:stä atomilauseesta (A, B, C…), on totuustaulussa 2ⁿ vaakariviä.

ESIM 1. Muodosta totuustaulu lauseille

a) ¬(A v ¬B)

Käytetään apusarakkeita (ensin "ei B", sitten "A tai (ei B)", lopuksi "ei (A tai ei B)")
$\begin{array}{l|l} A&B&\neg\left(A\vee\neg B\right)&\neg B&A\vee\neg B\\ \hline 1&1&0&0&1\\ 1&0&0&1&1\\ 0&1&1&0&0\\ 0&0&0&1&1 \end{array}$

b) A ⇔ (A v B)
$\begin{array}{l|l} A&B&A\Leftrightarrow\left(A\vee B\right)&A\vee B\\ \hline 1&1&1&1\\ 1&0&1&1\\ 0&1&0&1\\ 0&0&1&0 \end{array}$

c) (¬A => B) ∧ C
$\begin{array}{l|l} A&B&C&\left(\neg A\Rightarrow B\right)\wedge C&\neg A&\left(\neg A\Rightarrow B\right)\\ \hline 1&1&1&1&0&1\\ 1&1&0&0&0&1\\ 1&0&1&1&0&1\\ 1&0&0&0&0&1\\ 0&1&1&1&1&1\\ 0&1&0&0&1&1\\ 0&0&1&0&1&0\\ 0&0&0&0&1&0 \end{array}$

Tautologia

Lause, joka on aina tosi (identtisesti tosi), on tautologia.

Lause, joka on aina epätosi (identtisesti epätosi), on kontradiktio.

Tautologian totuustauluun tulee jokaiselle riville totuusarvoksi 1.

ESIM 1. Osoita, että lause (A ⇒ B) ⇔ (¬A ∨ B) on tautologia.

$\begin{array}{l|l} A&B&\left(A\Rightarrow B\right)\Leftrightarrow\left(\neg A\vee B\right)&A\Rightarrow B&\neg A\vee B\\ \hline 1&1&1&1&1\\ 1&0&1&0&0\\ 0&1&1&1&1\\ 0&0&1&1&1 \end{array}$

Tehtävän loppuun kirjoitetaan: Siis lause (A ⇒ B) ⇔ (¬A ∨ B) on aina tosi eli tautologia.

Looginen yhtäpitävyys, ekvivalenttius

Lauseet P ja Q ovat loogisesti ekvivalentit eli loogisesti yhtäpitävät, jos niillä on aina sama totuusarvo.

Lauseet P ja Q ovat loogisesti ekvivalentit täsmälleen silloin, kun lause P <=> Q on
tautologia (eli kun lauseiden P ja Q ekvivalenssi on aina tosi).

HUOM! Loogisesti ekvivalentit lauseet eivät kuitenkaan ole yleensä samoja.

ESIM 2. Osoita, että lauseet ¬(¬P ∧ ¬Q) ja P ∨ Q ovat loogisesti yhtäpitäviä.

$\begin{array}{l|l} P&Q&\neg(\neg P∧\neg Q)&P\vee Q&\left(\neg P\wedge\neg Q\right)\\ \hline 1&1&1&1&0\\ 1&0&1&1&0\\ 0&1&1&1&0\\ 0&0&0&0&1 \end{array}$

Siis lauseiden totuusarvot ovat aina samat, joten ne ovat loogisesti yhtäpitävät.

HUOM! Jokaiselle lauselogiikan lauseelle voidaan muodostaa loogisesti ekvivalentti lause käyttäen konnektiiveja ¬, ∧ ja ∨.

ESIM 3. Lauseella P on seuraava totuustaulu. Muodosta lauseista A ja B lause, joka on loogisesti ekvivalentti lauseen P kanssa.

***

Tärkeitä tautologioita

Kaksoisnegaation laki	¬¬A ⇔ A
De Morganin lait	¬(A ∨ B) ⇔ ¬A ∧ ¬B
	¬(A ∧ B) ⇔ ¬A ∨ ¬B
Kontrapositio	A ⇒ B ⇔ ¬B ⇒ ¬A

Näiden lakien avulla voidaan osoittaa lauseita ekvivalenteiksi ilman totuustauluja. Ekvivalenssin (⇔) vasemmalla puolella oleva voidaan korvata oikealla puolella olevan kanssa ja päinvastoin.

ESIM 4. Osoita käyttämättä totuustaulua, että lauseet (P ∨ Q) ⇒ ¬R ja R ⇒ (¬P ∧ ¬Q) ovat loogisesti ekvivalentit.

Todistus:

$(P∨Q)⇒\neg R\ \ \ \Leftrightarrow$ kontrapositio

$\neg\neg R\ \Rightarrow\ \neg\left(P\vee Q\right)\ \ \ \ \Leftrightarrow$ kaksoisnegaatio, De Morganin laki
$R⇒(\neg P∧\neg Q)$

ESIM 5. Kasper, Jesper ja Joonatan olivat syytettyinä. Luotettava todistaja kertoi: ”Ei pidä paikkaansa, että jos Jesper on syytön, niin Joonatan on syytön”. Toinen yhtä luotettava todisti, että: ”Kasper on syytön, jos ja vain jos Jesper on syytön ja Joonatan on syyllinen”. Kuka on syyllinen vai joutuuko koko kööri putkaan?

Kirjoitetaan atomilauseet
A = "Kasper on syytön"

B = "Jesper on syytön"

C = "Joonatan on syytön"

Kirjoitetaan todistajien lauseet: $\neg\left(B\Rightarrow C\right)$ ja $A\Leftrightarrow\left(B\wedge\neg\ C\right)$ .

Tehdään totuustaulu ja etsitään rivi, jossa molemmat puhuvat totta (1).

$\begin{array}{l|l} A&B&C&\neg\left(B\Rightarrow C\right)&A\Leftrightarrow\left(B\wedge\neg\ C\right)&\left(B\Rightarrow C\right)&B\wedge\neg\ C\\ \hline 1&1&1&0&0&1&0\\ 1&1&0&1&1&0&1\\ 1&0&1&0&0&1&0\\ 1&0&0&0&0&1&0\\ 0&1&1&0&1&1&0\\ 0&1&0&1&0&0&1\\ 0&0&1&0&1&1&0\\ 0&0&0&0&1&1&0 \end{array}$

Rivillä, jossa A = 1, B = 1 ja C = 0, käy näin. Siis Joonatan on syyllinen ja muut syyttömiä.