Propositiologiikka
Wikipediasta
Propositiologiikka eli lauselogiikka on symbolisen logiikan alue, jossa tutkitaan propositiosymboleja ja loogisia konnektiiveja sisältävien formaalikielen lauseiden ominaisuuksia. Näistä ominaisuuksista keskeisimpiä ovat totuus ja lauseiden väliset päättelysuhteet. [1]
Propositiosymboleina käytetään formaalikielessä yleensä merkkejä , , jne. Eri propositiosymbolien voidaan tulkita edustavan toisistaan riippumattomia asiantiloja. Loogisille konnektiiveille käytetään usein merkkejä kuten . Nämä vastaavat karkeasti ottaen luonnollisen kielen lausekonnektiiveja, esimerkiksi "ei", "ja" ja "tai".
Propositiologiikkaa kehittivät ensimmäisenä stoalaiset.
Propositiologiikan syntaksi
[muokkaa | muokkaa wikitekstiä]Propositiologiikassa atomilauseita merkitään propositiosymboleilla . Lausemuuttujina käytetään suuria kirjaimia . Lausemuuttujat kuvaavat mielivaltaisia tai toistaiseksi määrittelemättömiä lauseita.
Propositiosymboleja voidaan määritellä seuraavaan tapaan:
- "".
- "Esko ui".
- "Esko kastuu".
Propositiosymboleista voidaan rakentaa monimutkaisempia ilmaisuja loogisten operaattoreiden eli konnektiivien avulla. Joskus osa konnektiiveista voidaan korvata määrittelemällä ne muutaman valitun konnektiivin avulla. Yleensä konnektiiveja esitellään seuraavat viisi, mutta on olemassa myös pari muuta konnektiivia: Shefferin viiva ja Peircen nuoli.
Merkitys | Merkintä | Lukutapa |
---|---|---|
negaatio | "ei A" (engl. not A) | |
konjunktio | "A ja B" (engl. A and B) | |
disjunktio | "A tai B" (engl. A or B) | |
implikaatio | "jos A niin B" | |
ekvivalenssi | "A jos ja vain jos B" |
Seuraavassa rekursiivisessa määritelmässä määritellään kaikki propositiolauseet.
Määritelmä 1 Propositiolause
- Propositiosymbolit ovat propositiolauseita.
- Jos on propositiolause, niin on propositiolause.
- Jos ja ovat propositiolauseita, niin on propositiolause.
- Jos ja ovat propositiolauseita, niin on propositiolause.
- Jos ja ovat propositiolauseita, niin on propositiolause.
- Jos ja ovat propositiolauseita, niin on propositiolause.
Esimerkki 2 Propositiolauseita
Määritelmän 1 perusteella propositiolauseet voidaan purkaa osatekijöikseen yksiselitteisellä tavalla (katso propositiologiikan rakennepuu). Tällöin edetään vastakkaiseen suuntaan. Jos on propositiolause, niin se on välttämättä muotoa , , , , tai . Muussa tapauksessa sitä ei ole muodostettu määritelmän mukaisesti. Tämä mahdollistaa matemaattisen induktion soveltamisen logiikkaa koskevissa todistuksissa.
Päättely propositiologiikassa
[muokkaa | muokkaa wikitekstiä]Propositiologiikassa (kuten formaalissa logiikassa muutenkin) voidaan erottaa kaksi päätapaa tutkia päättelyä: Päättelysäännöt (syntaktinen näkökulma) ja totuusarvon laskeminen (semanttinen näkökulma). Päättelysäännöt sinänsä eivät takaa sitä, että päättely säilyttää totuuden. Tämän takaa vasta sellaisten päättelysääntöjen käyttäminen, joiden eheys (katso eheyslause alempana) on todistettu. Päättelysääntöjen sinänsä soveltaminen on ainoastaan uusien lauseiden johtamista jo oletetuista. Sen sijaan, jos tiettyjen päättelysääntöjen eheys on todistettu, voidaan päättelyn pätevyys todistaa jo pelkästään näihin päättelysääntöihin nojautuen. Eheydestä käytetään usein myös nimityksiä validius ja korrektisuus.
Aksioomat ...
Päättelysäännöt ...
Pari esimerkkiä ...
Totuusjakauma ja propositiolauseen totuusarvo
[muokkaa | muokkaa wikitekstiä]Määritelmä 3 Totuusjakauma on kuvaus , jossa "tosi" ja "epätosi".
Määritelmä 4 Propositiosymbolien totuusarvo
.
Symboli esiintyy määritelmässä 4 kahdessa merkityksessä: totuusjakauman symbolina yhtäläisyysmerkin vasemmalla puolella ja propositiolauseen totuusarvon määrittäjänä oikealla puolella.
Esimerkki 5 | |
Olkoon totuusjakauma siten, että | |
, jos | |
muuten. |
Nyt
Propositiologiikan konnektiivit ovat totuusfunktionaalisia. Kutakin funktion määrittelyjoukon totuusarvoa, kaksipaikkaisten konnektiivien tapauksessa totuusarvoparia, vastaa arvojoukossa täsmälleen yksi totuusarvo. Selkeä tapa määritellä täsmällisesti konnektiivien merkitykset on totuusarvotaulukko.
Määritelmä 6 Konnektiivien totuusarvotaulukot
1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
Negaatio vastaa luonnollisen kielen sanaa ei. Se määrittää lauseen vastakohdan. Lauseen A negaatio ei A on tosi jos (jos ja vain jos) lause A on epätosi.
Konjunktio vastaa luonnollisen kielen sanaa ja. Lauseiden A ja B konjunktio A ja B on tosi vain, jos molemmat sen yhdistämät ilmaisut eli lauseet A ja B ovat tosia.
Luonnollisen kielen 'tai'-sana on kaksiselitteinen. Joskus sitä käytetään inklusiivisesti, toisinaan taas eksklusiivisesti. Inklusiivisen 'tai'-sanan sisältävä ilmaisu on tosi, jos toinen tai molemmat vaihtoehdoista ovat tosia. Nykykielessä tällöin käytetään joskus sanontaa ”ja/tai”. Eksklusiivinen 'tai'-ilmaisu on tosi, jos vain toinen ilmaisuista on tosi mutta eivät molemmat. Logiikassa tällaista tulkinnanvaraisuutta ei ole, koska konnektiivien merkitykset määritellään täsmällisesti. Yleisempää on käyttää inklusiivista disjunktiota. Eksklusiivinen disjunktio voidaan kuitenkin määritellä seuraavasti: ''.
Implikaatiolla ilmaistaan totuuden riittävää tai välttämätöntä edellytystä. Lauseen '' (luetaan: jos A niin B) mukaan on :n riittävä edellytys ja :n välttämätön edellytys.
Ekvivalenssi on tosi jos sen yhdistämien ilmaisujen totuusarvot ovat samat.
Määritelmien 4 ja 6 perusteella voidaan laskea minkä tahansa propositiolauseen totuusarvo millä tahansa totuusjakaumalla.
Esimerkki 7
Lasketaan propositiolauseen totuusarvo. Olkoon totuusjakauma kuten esimerkissä 5.
Määritelmän 4 nojalla ja .
Määritelmän 6 toisen rivin ja kuudennen sarakkeen mukaan .
Kolmannen rivin ja kuudennen sarakkeen mukaan
.
Kolmannen rivin ja seitsemännen sarakkeen mukaan siis .
Edelleen kolmannen sarakkeen mukaan .
Totuustaulua voidaan käyttää myös apuvälineenä propositiolauseen totuusarvon laskemiseksi. Seuraavassa esimerkissä Arvo-riville on merkitty kunkin elementin totuusarvo ja Laskujärjestys-riville järjestys, jossa ne on merkitty.
Esimerkki 8 Propositiolauseen totuusarvo totuustaululla
Arvo | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
Laskujärjestys | 1 | 1 | 1 | 1 | 5 | 2 | 3 | 2 | 4 | 2 | 3 | 2 |
Propositiolauseen totuus riippuu (tietenkin sen rakenteen ohella) ainoastaan propositiosymbolien totuusarvoista. Koska jokaisella oikein muodostetulla propositiolauseella on yksiselitteinen rakennepuu, voidaan propositiolauseen totuusarvo yksiselitteisesti laskea sen sisältämien propositiosymbolien totuusarvojen perusteella, kuten esimerkeistä 7 ja 8 nähdään. Jos propositiosymbolin totuusarvo tiedetään, niin se voidaan korvata esityksessä totuusarvollaan. Myös propositiosymbolia kompleksisempi propositiolauseen osa voidaan korvata totuusarvollaan.
Tautologia ja looginen seuraus
[muokkaa | muokkaa wikitekstiä]Klassisessa propositiologiikassa pätevät seuraavat lait:
- Principium exclusi terti (lat. kielletyn kolmannen laki), jonka mukaan jokainen lause on aina tosi tai epätosi.
- Principium exclusi contradictionis (lat. kielletyn ristiriidan laki), jonka mukaan mikään lause ei voi olla sekä tosi että epätosi.
Propositiologiikan täydellisyys- ja eheyslause
[muokkaa | muokkaa wikitekstiä]Propositiologiikan täydellisyyslauseen mukaan jos lause on tautologia, niin lauseella on luonnollinen päättely.
Propositiologiikan eheyslauseen mukaan jos lauseella on luonnollinen päättely oletuksista ; niin jos totuusjakaumalla pätee , niin .
Kun täydellisyyslause ja eheyslause yhdistettään, niin saadaan tuloksena seuraava lause: propositiolause on tautologia jos ja vain jos propositiolauseella on luonnollinen päättely.
Eheyslauseesta siis seuraa, että jos :lla on luonnollinen päättely, niin lause on tautologia. Todistetaan tämä eheyslauseen avulla.
Todistus
[muokkaa | muokkaa wikitekstiä]Väite: Jos lauseella on luonnollinen päättely, niin lause on tautologia.
Tehdään vastaoletus: lauseella on luonnollinen päättely mutta lause ei ole tautologia. Tällöin on olemassa totuusjakauma siten, että , joten . Koska
Edellä sovellettiin luonnolisen päättelyn tunnettuja sääntöjä konjunktion tuonti, negaation tuonti ja negaation eliminointi.
Toisaalta eheyslauseen nojalla koska ja , niin . Ollaan päädytty ristiriitaan, joten alkuperäinen väite pätee.
Täten lause on tautologia.
Konnektiivit ja loogiset portit
[muokkaa | muokkaa wikitekstiä]Elektroniikassa tärkeimpiä loogisia konnektiiveja vastaavat tietyt loogiset portit seuraavasti:
Konnektiivi | Yhdistetty lause | Looginen portti |
---|---|---|
negaatio | "ei A" | NOT-portti |
konjunktio | "A ja B" | AND-portti |
disjunktio | "A tai B tai molemmat" | OR-portti |
eksklusiivinen disjunktio | "A tai B, mutta ei molemmat" | XOR-portti |
Shefferin viiva | "ei A tai ei B" | NAND-portti |
Peircen nuoli | "ei A eikä B" | NOR-portti |
Katso myös
[muokkaa | muokkaa wikitekstiä]Lähteet
[muokkaa | muokkaa wikitekstiä]- ↑ Thompson, Jan & Martinsson, Thomas: Matematiikan käsikirja, s. 235–236. Helsinki: Tammi, 1994. ISBN 951-31-0471-0.
Kirjallisuutta
[muokkaa | muokkaa wikitekstiä]- Thompson, Jan & Martinsson, Thomas: Matematiikan käsikirja. Helsinki: Tammi, 1994. ISBN 951-31-0471-0.
- Miettinen, Seppo K.: Logiikka: Perusteet. Helsinki: Gaudeamus, 2002. ISBN 951-662-865-6.
Aiheesta muualla
[muokkaa | muokkaa wikitekstiä]- Klement, Kevin C.: Propositional Logic The Internet Encyclopedia of Philosophy. (englanniksi)
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.