Konnektiivit ja totuusarvot

Logiikka on oppi perustelusta ja päättelystä. Tässä kappaleessa määritellään mitä matemaattisella päättelyllä tarkoitetaan ja millaisiin tutkimuskohteisiin sitä voidaan soveltaa.

Konnektiivit

Lauselogiikassa tutkitaan väitelauseita. Väitelauseen tunnistaa siitä, että se voi olla joko tosi tai epätosi. Esimerkiksi lause “eilen oli poutaa” ja matemaattinen yhtälö 9 > 12 ovat väitelauseita. Näistä väite on tosi tai epätosi riippuen siitä, oliko eilen poutaa vai ei, jälkimmäinen on puolestaan epätosi.

Väitelauseista voidaan rakentaa monimutkaisempia väitelauseita loogisten konnektiivien avulla. Sanat “ei”, “ja” ja “tai” ovat konnektiiveja, joilla on logiikassa nimitykset negaatio, konjunktio ja disjunktio. Niitä on tapana merkitä seuraavilla symboleilla väitelauseiden A ja B tapauksissa:

Arkinen kielenkäyttö sisältää paljon tulkinnanvaraisuuksia, joiden välttämiseksi sovitaan mitä käytettävät merkinnät tarkoittavat. Sovitaan, että

(i) Väitelause “A ja B” on tosi jos sekä A että B ovat totta.

(ii) Väitelause “A tai B” on tosi jos vähintään toinen väitelauseista A ja B on tosi.

Sulkeet

Monimutkaisempien väitelauseiden kirjoittamisessa käytetään tarvittaessa sulkeita. Sulkeilla on logiikassa samanlainen merkitys kuin numeraalisten laskutehtävien laskujärjestyksessä. Esimerkiksi lauseet (A ∨ B) ∧ C ja A ∨ (B ∧ C) tarkoittavat eri asioita. Sulkeiden käyttöä voidaan kuitenkin vähentää seuraavien sopimusten nojalla

(i) Negaatiot luetaan ennen konnektiiveja

Lause (¬A) ∨ B voidaan kirjoittaa muodossa ¬A ∨ B.

Jos A on lause “aurinko paistaa” ja B on lause “tuulee”, niin ¬A ∨ B tarkoittaa “ “Aurinko ei paista ja sataa”.

(ii) Peräkkäiset konjunktiot kirjoitetaan ilman sulkeita

Lauseet (A ∧ B) ∧ C ja A ∧ (B ∧ C) voidaan kirjoittaa muodossa A ∧ B ∧ C.

Jos A on lause “aurinko paistaa”, B on lause “tuulee” ja C on lause “sataa” niin

A ∧ B ∧ C tarkoittaa että “aurinko paistaa ja sataa ja tuulee.”

(iii) Peräkkäiset disjunktiot kirjoitetaan ilman sulkeita

Lauseet (A ∨ B) ∨ C ja A ∨ (B ∨ C) voidaan kirjoittaa muodossa A ∧ B ∧ C.

Jos A on lause “aurinko paistaa”, B on lause “tuulee” ja C on lause “sataa” niin

A ∧ B ∧ C tarkoittaa että “aurinko paistaa, sataa ja tuulee.”

Implikaatio ja ekvivalenssi

Tarkastellaan seuraavaksi yhdistettyä lausetta, joka voidaan ilmaista väitelauseena “jos väite A on tosi, niin B on tosi.” Tätä voidaan merkitä lyhyemmin A → B. Konnektiivi → on nimeltään implikaatio. Näin ollen jos merkitsemme A: ”aurinko paistaa” ja B: “tuulee” niin yhdistetty lause “Jos aurinko paistaa, niin myös tuulee” formalisoidaan muotoon A → B.

Implikaatio A → B voidaan lukea eri tavoin: ” jos A on tosi niin, B on tosi”, “B jos A”, “A:sta seuraa B”.

Mikäli väitelauseet A ja B ovat molemmat joko epätosia tai tosia eli toisen toteutumisesta seuraa aina toisen toteutuminen niin sanotaan että väitteet ovat loogisesti yhtäpitävät eli ekvivalentit. Tällöin lause “A on tosi jos ja vain jos B on tosi” voidaan ilmaista lyhyemmin A ↔ B. Konnektiivia ↔ kutsutaan ekvivalenssiksi. Edelleen, voimme merkitä lausetta “Aurinko paistaa jos ja vain jos tuulee” ekvivalenssilla A ↔ B.

Ekvivalenssi A ↔ B pitää sisällään implikaatiot: A → B ja B → A.

Logiikan kielellä ilmaistuna: (A ↔ B) ↔ ((A → B) ∧ (A → B)).

Myös ekvivalenssi A ↔ B voidaan lukea useammalla eri tavalla: “A jos ja vain jos B”, “A joss. B”, “A täsmälleen silloin kun B”, “A ja B ovat yhtäpitävät”.

Tautologia

Tautologia on lause, joka on aina tosi. Esimerkiksi lause “Huomenna sataa tai ei sada” on tautologia.

Looginen ekvivalenssi

Lauseet F ja Q ovat loogisesti ekvivalentit jos niillä on aina sama totuusarvo. Lauseiden yhtäpitävyys voidaan kirjoittaa ekvivalenssina F ↔ Q. Jos lauseiden F ja Q totuusarvot ovat aina samat niin lause F ↔ Q on tautologia.

Avoin lause ja ratkaisujoukko

Aikaisemmin tarkastelimme yksinkertaisia väitelauseita, kuten A: “paistaa aurinko”. Tämän lauseen totuusarvo riippuu kuitenkin oleellisesti tarkastelijan sijainnista x. Onkin mielekästä tarkastella ennemmin avointa lausetta A(x): “Paikassa x paistaa aurinko”, jolloin lauseen totuusarvo riippuu vapaasta muuttujasta x. Joukkoa, jonka alkioihin lause viittaa, kutsutaan lauseen perusjoukoksi. Perusjoukkona voisi olla esimerkiksi Etelä-Savon kunnat, jolloin lauseen ratkaisujoukko muodostuu kaikista niistä kunnista joissa paistaa aurinko. Voimme muodostaa myös useamman muuttujan vapaita lauseita, kuten A(x,y): “Paikassa x paistaa aurinko ajanhetkellä y”.

Aikaisemmin tarkasteltuja suljettuja lauseita (ei vapaata muuttujaa) kutsutaan myös prepositiolauseiksi ja suljettuja lauseita käsittelevää logiikkaa kutsutaan prepositiologiikaksi. Avoimia lauseita kutsutaan puolestaan predikaateiksi ja avoimia lauseita käsittelevää logiikkaa kutsutaan predikaattilogiikaksi.

Matematiikassa tarkasteltavia avoimia lauseita ovat usein yhtälöt ja epäyhtälöt, joiden yhteydessä perusjoukkoa kutsutaan myös määrittelyjoukoksi.

Esimerkki 4

Olkoon T(x) lause “x² + x = 2”. Onko lause i) T(0) ii) T(-2) tai iii) T(-3) tosi?

Ratkaisu

T(0) = 0² + 0 = 0 ≠ 2

T(-2) = (-2)² + (-2) = 2

T(-3) = (-3)² + (-3) = 6 ≠ 2

Saadaan: T(0) epätosi, T(-2) tosi ja T(-3) epätosi.

Esimerkki 5

Piirrä lukusuoralle avoimen välin ratkaisujoukko. Ilmaise ratkaisujoukko käyttäen välin merkintää. Perusjoukko on reaalilukujen joukko ℝ.

a) |x| > 5

b) -2 ≤ x < 3 tai 3 < x ≤ 5

c) epäyhtälöpari

Ratkaisu

a) |x| > 5 toteutuu kun x > 5 tai -x > 5. Jälkimmäinen epäyhtälö saadaan muotoon x < -5.

Ratkaisujoukko muodostuu siis väleistä ]∞,-5[ ja ]5,∞[

b) Ratkaisujoukko muodostuu väleistä [-2,3[ ja ]3,5]

c) Yhtälö- ja epäyhtälöryhmät ovat avoimien lauseiden konjunktioita.

Epäyhtälöryhmä

tarkoittaa avoimien lauseiden S(x):”x² – 2x – 3 > 0” ja T(x):”x > -3x + 4” konjunktiota S(x)∧T(x). Epäyhtälöparin ratkaisujoukon muodostavat ne x:n arvot, jotka kuuluvat reaalilukujen joukkoon ja toteuttavat molemmat epäyhtälöt x² – 2x – 3 > 0 ja x > -3x + 4.

Toisen asteen epäyhtälön x² – 2x – 3 > 0 ratkaisu päätellään tutkimalla toisen asteen polynomifunktion x² – 2x – 3 merkkiä.

Ratkaistaan funktion x² – 2x – 3 nollakohdat yhtälöstä x² – 2x – 3 = 0

x = -1 tai x = 3

Funktion x² – 2x – 3 kuvaaja on ylöspäin aukeava paraabeli eli epäyhtälön x² – 2x – 3 > 0 ratkaisujoukko on ]-1,3[.

Epäyhtälö x > -3x + 4 toteutuu, kun x > 1 eli epäyhtälön ratkaisujoukko on ]1,∞[.

Näin ollen epäyhtälöparin ratkaisujoukon muodostavat ne x:n pisteet, jotka sisältyvät molempiin väleihin ]-1,3[ ja ]1,∞[ eli välille ]1,3[.

Kvanttorit

Olemassaolo- eli eksistenssikvanttori ∃

∃x∈A T(x): “On olemassa (ainakin yksi) sellainen joukon A alkio x, jolle pätee lause T(x)”.

Kaikki- eli universaalikvanttori ∀

∀x∈A T(x): “Kaikilla joukon A:n alkioilla x pätee lause T(x)”

Kvanttorin negaatio

¬(∃x A(x)) ⇔ ∀x ¬A(x)

¬(∀x ∈ A: p(x)) ⇔ (∃x ¬A(x))

Yhdistetyt kvanttorit

∃x∀y∈A T(x, y): “On olemassa sellainen joukon A alkio x, että olipa y mikä tahansa joukon A alkio, niin lause T(x, y) on tosi.”

∀ x∃y∈A T(x,y): “Jokaista joukon A alkiota x kohti on olemassa sellainen y,

että lause T(x, y) on tosi.”

Perusjoukkoa ei välttämättä merkitä näkyville mikäli se käy ilmi tehtävästä muutoin.

Esimerkki 8

Reaaliluku x kuuluu rationaalilukujen ℚ joukkoon, jos ja vain jos on olemassa kokonaisluvut m ja n(≠0) siten että x=m/n.

Reaaliluku on irrationaaliluku, jos se ei ole rationaaliluku.

Todista seuraavat lauseet

a) Jos x ∈ ℚ ja y ∈ ℚ, niin x + y ∈ ℚ

b) Jos x ∉ ℚ ja y ∈ ℚ , niin x+y ∉ ℚ

a) Oletuksen nojalla on olemassa sellaiset kokonaisluvut k,l,p ja q siten, että

Näin ollen

missä kq+pl ja lq ovat kokonaislukuja ja lq≠0. Todistetusti x+y ∈ ℚ.

b) Todistetaan väite käyttämällä käänteis- eli kontrapositiotodistusta:

Palautetaan mieleen kontrapositolaki A → B ↔️ ¬B → ¬A.

Väite A → B voidaan siis osoittaa todeksi todistamalla sen kontrapositio ¬B → ¬A todeksi. Toisinaan lauseen kontrapositio on helpompi todistaa kuin alkuperäinen lause, minkä vuoksi kontrapositiotodistusta käytetään. Käänteinen todistus on valmis, kun vastaoletuksesta ¬B on päätelty että oletus A on epätosi eli ¬A on tosi.

Tarkastelemme tässä tehtävässä väitettä A → B, missä A:“ x ∉ ℚ ja y ∈ ℚ” B: ”x+y ∉ ℚ“.

Täten tehtävänannon oletus on A:“ x ∉ ℚ ja y ∈ ℚ”.

Tehdään vastaoletus ¬B: oletetaan, että x + y ∈ ℚ eli on olemassa sellaiset kokonaisluvut k ja l siten, että

Koska y ∈ ℚ niin on olemassa sellaiset luvut p ja q, että

Nyt voimme ratkaista muuttujan x yhtälöstä

missä kq-pl ja lq ovat kokonaislukuja ja lq≠0 eli x∈ ℚ. Tämä on ristiriita oletuksen A kanssa eli ¬A on tosi. Täten x+y on irrationaaliluku.

Harjoituksia