Logiikka: formaali logiikka


Ilkka Niiniluoto (julkaistu 16.3.2015)

Kirjoitus on (yhdessä artikkelin ”Logiikan historia” kanssa) Logos-ensyklopediaa varten laajasti muokattu ja päivitetty versio kirjoittajan artikkelista ”Logiikka”, joka on alkujaan ilmestynyt Otavan suuressa ensyklopediassa (1978).

Formaalissa logiikassa tutkitaan rakenteeltaan täsmällisiä kieliä, joissa symboleista muodostettujen merkkijonojen avulla voidaan ilmaista väitelauseita. Logiikan perusosan muodostaa lauselogiikka, jossa tarkastellaan yksinkertaisten lauseiden yhdistämistä. Predikaattilogiikassa lauseiden sisäinen rakenne analysoidaan väitteiksi, jotka koskevat yksilöiden ominaisuuksia ja suhteita. Lisäksi predikaattilogiikassa otetaan käyttöön kvanttorit, joilla voidaan ilmaista, että kaikilla tai joillakin yksilöillä on väitettyjä ominaisuuksia tai suhteita. Tavoitteena on antaa täsmällinen määritelmä sille, milloin lauseet ovat muotonsa perusteella loogisesti tosia eli valideja tai milloin lauseiden väliset päätelmät ovat loogisesti päteviä. Filosofisten sovellutusten kannalta tärkeitä lause- ja predikaattilogiikan yleistyksiä ovat erilaiset intensionaalisen logiikan järjestelmät, joissa lauseisiin voidaan liittää operaattoreita, kuten ’mahdollisesti’ ja ’välttämättä’ (modaalilogiikka), ’pitäisi olla’ ja ’saa olla’ (deonttinen logiikka) ja ’tietää että’ ja ’uskoo että’ (episteeminen ja doksastinen logiikka).

Katso myös artikkelit "Logiikka" sekä "Logiikan historia".

  1. Lauselogiikka
  2. Predikaattilogiikka
  3. Intensionaalinen logiikka
  4. Formaalinen logiikka Suomessa
  5. Suositeltavaa jatkolukemista
  6. Kirjallisuus

 

Lauselogiikka

Lauselogiikka on modernin logiikan (ks. "Logiikan historia") perusosa, jossa tarkastellaan yhdistettyjen lauseiden muodostamista yksinkertaisista lauseista lausekonnektiivien avulla. Lauselogiikan eksaktia esitystä formaalisen kielen avulla sanotaan lausekalkyyliksi.

Väitelauseet ja konnektiivit

Tarkastelkaamme seuraavia esimerkkejä suomen kielen lauseista:

  1. (1) Kupari johtaa sähköä.
    (2) Kuu on soikea tai Russell ei ole loogikko.
    (3) Jos 2 > 3, niin 1 + 1 = 1.
    (4) Maa kiertää Aurinkoa, koska Oulu on Helsingin pohjoispuolella.
    (5) Onko Musti vihainen?
    (6) Tule tänne!

Näistä (5) on kysymyslause ja (6) on käskylause, kun taas (1) – (4) ovat väitelauseita. Toisin kuin kysymykset, huudahdukset, käskyt, suostuttelut jne., väitelauseet ilmaisevat joitakin yksityisiä tai yleisiä asiaintiloja ja ovat siten periaatteessa tosia tai epätosia – riippumatta siitä, satummeko tietämään kumpi vaihtoehto kulloinkin on voimassa.

(1) on yksinkertainen väitelause, jota ei voi hajottaa osalauseisiin, kun taas (2), (3) ja (4) ovat yhdistettyjä lauseita. Jos merkitään kirjaimilla p ja q lauseita ’Kuu on soikea’ ja ’Russell on loogikko’, niin lause (2) voidaan kirjoittaa muodossa

  1. (2’) p tai ei-q.

Tässä ’tai’ ja ’ei’ ovat sidesanoja, joiden avulla annetuista lauseista voidaan muodostaa uusia lauseita. Vastaavasti lauseessa (4) esiintyy sidesana ’koska’, ts. se on muotoa

  1. (4’) r koska s.

Lauselogiikassa lauseilla tarkoitetaan nimenomaan väitelauseita eli propositioita, jotka ovat joko tosia tai epätosia. Yksinkertaisia lauseita, joita ei ole muodostettu sidesanojen avulla yksinkertaisemmista osalauseista, sanotaan atomilauseiksi; niitä merkitään kirjaimilla p, q, … Myös sidesanoille ’tai’, ’ei’, ’ja’, ’jos–niin’, ’jos ja vain jos’ otetaan käyttöön omat formaaliset merkkinsä, jolloin samalla niiden perusmerkityksestä tehdään yksikäsitteiset sopimukset. Näiden merkkien eli konnektiivien avulla atomilauseista p, q, … voidaan rakentaa yhdistettyjä lauseita, joiden totuusehdot on yksikäsitteisesti määrätty osalauseiden totuusehtojen kautta. Yhdistetyn lauseen lauselooginen muoto riippuu siitä, mitä ja missä asemassa olevia konnektiiveja siinä esiintyy.

Lauselogiikassa rajoitutaan konnektiiveihin, jotka ovat ekstensionaalisia eli totuusfunktionaalisia. Tällaiset konnektiivit liittävät yksikäsitteisesti osalauseiden totuusarvoon yhdistetyn lauseen totuusarvon. Olkoon o kaksipaikkainen konnektiivi, ts. poq on lause aina kun p ja q ovat lauseita. Konnektiivi o on ekstensionaalinen jos ja vain jos lauseen poq totuus tai epätotuus riippuu ainoastaan osalauseiden p ja q totuudesta tai epätotuudesta. Esimerkiksi luonnollisen kielen sidesana ’ja’ määrittelee ekstensionaalisen konnektiivin, sillä lause ’p ja q’ on tosi täsmälleen silloin, kun p ja q molemmat ovat tosia, ja muulloin epätosi. Sen sijaan ’koska’ ei ole ekstensionaalinen, sillä muotoa (4’) oleva lause on joissakin tapauksissa tosi ja joissakin epätosi, vaikka r:n ja s:n totuusarvot pysyisivätkin samoina . (Esimerkiksi lause (4), jossa r ja s ovat tosia, on epätosi.) Konnektiiveja, jotka eivät ole ekstensionaalisia, tutkitaan ns. intensionaalisessa logiikassa. (Ks. alla osio Intensionaalinen logiikka.)

Lauselogiikan tavallisimmat konnektiivit on esitetty seuraavassa taulukossa:

konnektiivi: merkintä: luetaan:
negaatio ∼p ei p
konjunktio p ∧ q p ja q
disjunktio p ∨ q p tai q
implikaatio p ⊃ q jos p niin q
ekvivalenssi p ≡ q p jos ja vain jos q

Ekvivalenssi kirjoitetaan usein myös muodossa ’joss’. Myös monia muita merkintätapoja käytetään yleisesti:

negaatio ∼p, ¬p, Np
konjunktio p ∧ q, p & q, p.q, pq, Kpq
disjunktio p ∨ q, Apq
implikaatio p ⊃ q, p → q, p ⇒ q, Cpq
ekvivalenssi p ≡ q, p ↔ q, p ⇔ q, Epq

Konnektiivien avulla muodostettujen lauseiden totuusehdot voidaan – ekstensionaalisuuden perusteella – ilmaista taulukoiden muodossa. Niissä totuutta merkitään luvulla 1 ja epätotuutta luvulla 0. Joskus totuusarvoille käytetään myös merkintöjä t ja e tai + ja -. Klassisessa kaksiarvoisessa lauselogiikassa ei ole muita totuusarvoja kuin 1 ja 0. Näiden merkintöjen avulla voidaan esittää negaation, konjunktion, disjunktion, implikaation ja ekvivalenssin totuustaulukot.

Negaation totuustaulukko:

p ∼p
1 0
0 0

Siten negaatio ∼p on epätosi, jos p on tosi, ja ∼p on tosi, jos p on epätosi.

Konjunktion totuustaulukko:

p q p ∧ q
1 1 1
1 0 0
0 1 0
0 0 0

Siten konjunktio p ∧ q on tosi silloin kun p ja q molemmat ovat tosia, ja epätosi muulloin.

Disjunktion totuustaulukko:

p q p ∨ q
1 1 1
1 0 1
0 1 1
0 0 0

Tämä taulukko määrittelee ns. inklusiivisen disjunktion, jossa p ∨ q on tosi mikäli ainakin toinen lauseista p ja q on tosi – siis silloinkin kun molemmat osalauseet p ja q ovat tosia. Lausekalkyylissä on tarkoituksenmukaista käyttää inklusiivista disjunktiota eikä eksklusiivista disjunktiota, joka vastaa arkikielen ilmausta ’joko-tai’. Ekslusiivisen disjunktion totuustaulukko määriteltäisiin siten, että taulukon ylimmällä rivillä olisi arvon 1 sijasta 0.

Implikaation totuustaulukko:

p q p ⊃ q
1 1 1
1 0 0
0 1 1
0 0 1

Tämä taulukko määrittelee ns. materiaalisen implikaation p ⊃ q, joka on epätosi ainoastaan siinä tapauksessa, että etujäsen p on tosi ja takajäsen q on epätosi. Siten mm. esimerkkilause (3) on tosi, mikäli se formalisoidaan implikaation ⊃ avulla, sillä sen etujäsen on epätosi. Tällainen ekstensionaalinen konnektiivi on osoittautunut tarkoituksenmukaiseksi määritellä lausekalkyylissä, vaikka aiheesta voidaankin käydä filosofista kiistaa. Materiaalista implikaatiota ei pidä sekoittaa alla määriteltävään loogiseen seuraussuhteeseen eikä myöskään ilmauksen ’jos-niin’ erilaisiin ei-ekstensionaalisiin käyttötapoihin. Esimerkiksi lause ’Jos suomalaiset lopettaisivat työnteon, heidän elintasonsa kohoaisi’ vaikuttaa ilmeisen epätodelta; kuitenkin jos tämä kontrafaktuaalinen ehtolause formalisoitaisiin materiaalisen implikaation avulla, se olisi tosi, sillä sen ehtolause on epätosi.

Ekvivalenssin totuustaulukko:

p q p ≡ q
1 1 1
1 0 0
0 1 0
0 0 1

Näin määriteltyä konnektiivia ≡ sanotaan materiaaliseksi ekvivalenssiksi – sen mukaan lause p ≡ q on tosi täsmälleen silloin, kun lauseilla p ja q on sama totuusarvo. Materiaalista ekvivalenssia ei pidä sekoittaa alla määriteltävään loogiseen ekvivalenssiin.

Käyttämällä apuna sulkumerkkejä ( ja ) matematiikasta tuttuun tapaan voidaan atomilauseista p, q, ... lähtien muodostaa yhä monimutkaisempia lauseita. Esimerkiksi lause (2’) voidaan formalisoida seuraavasti:

  1. (7) p ∨ ∼q

Lauseen (7) totuusehdot voidaan selvittää soveltamalla ensin negaation ja sitten disjunktion totuustaulukkoa:

p q ∼q p ∨ ∼q
1 1 0 1
1 0 1 1
0 1 0 0
0 0 1 1

Vastaavasti lauseen

  1. (8) ((p ∨ q) ⊃ r) ≡ (( p ⊃ r) ∧ ( q ⊃ r))

totuusehdot voidaan määrätä kirjoittamalla ensin kirjainten p, q ja r alle kaikki erilaiset totuusarvojakelut ja laskemalla sitten (taulukon alimman rivin osoittamassa) numerojärjestyksessä seuraavan taulukon pystyrivit:

((p q) r) ((p r) (q r))
1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 1 1 0 0 0 1 0 0
1 1 0 1 1 1 1 1 1 1 0 1 1
1 1 0 0 0 1 1 0 0 0 0 1 0
0 1 1 1 1 1 0 1 1 1 1 1 1
0 1 1 0 0 1 0 1 0 0 1 0 0
0 0 0 1 1 1 0 1 1 1 0 1 1
0 0 0 1 0 1 0 1 0 1 0 1 0
  1   4   6   2   5   3  

Tautologiat

Edellä on esimerkki yhdistetystä lauseesta, jonka totuustaulukossa pääkonnektiivin ≡ kohdalla (pylväässä 6) esiintyy vain ykkösiä. Tällaista lausetta, joka on aina tosi riippumatta siitä, mikä totuusarvo siinä esiintyvillä atomilauseilla on, sanotaan Ludwig Wittgensteinin ehdotusta seuraten tautologiaksi. Vastaavasti lausetta, joka on kaikissa mahdollisissa tapauksissa epätosi, sanotaan kontradiktioksi eli loogiseksi ristiriidaksi. Lauseet, jotka eivät ole tautologioita eivätkä kontradiktioita, ovat loogisesti kontingentteja. Kontingentit lauseet voivat siis olla joko tosia tai epätosia riippuen niiden sisältämien atomilauseiden totuusarvoista.

Leibnizin mukaan loogisten totuuksien tunnusmerkki on se, että ne ovat tosia ”kaikissa mahdollisissa maailmoissa”. Siten lauselogiikan loogisia totuuksia ovat tautologiat. Jos lause A on tautologia, niin merkitään ⊨ A.

Esimerkkejä tautologioista:

  1. (9) ⊨ p ∨ ∼p
    (10) ⊨ ∼(p ∧ ∼p)
    (11) ⊨ ∼∼p ≡ p

Näistä (9) on kolmannen poissuljetun laki, (10) on ristiriidan laki, ja (11) on kaksoisnegaation laki.

  1. (12) ⊨ (p ∨ p) ≡ p
    (13) ⊨ (p ∧ p) ≡ p
    (14) ⊨ p ⊃ (q ∨ p)
    (15) ⊨ (p ∧ q) ⊃ p
    (16) ⊨ (p ∨ q) ≡ (q ∨ p)
    (17) ⊨ (p ∧ q) ≡ (q ∧ p)
    (18) ⊨ (p ⊃ q) ≡ (∼q ⊃ ∼p)
    (19) ⊨ (p ≡ q) ≡ (q ≡ p)
    (20) ⊨ ((p ∨ q) ∨ r) ≡ (p ∨ (q ∨ r))
    (21) ⊨ ((p ∧ q) ∧ r) ≡ (p ∧ (q ∧ r))
    (22) ⊨ (p ∧ (q ∨ r)) ≡ ((p ∧ q) ∨ (p ∧ r))
    (23) ⊨ (p ∨ (q ∧ r)) ≡ ((p ∨ q) ∧ (p ∨ r))
    (24) ⊨ (p ∧ (p ∨ q)) ≡ p
    (25) ⊨ (p ∨ (p ∧ q)) ≡ p
    (26) ⊨ ∼(p ∨ q) ≡ (∼p ∧ ∼q)
    (27) ⊨ ∼(p ∧ q) ≡ (∼p ∨ ∼q)

Kaavat (26) ja (27) tunnetaan De Morganin lakien nimellä.

  1. (28) ⊨ p ⊃ p
    (29) ⊨ p ⊃ (q ⊃ p)
    (30) ⊨ (p ⊃ q) ⊃ ((q ⊃ r) ⊃ (p ⊃ r))
    (31) ⊨ (p ⊃ (q ⊃ r)) ⊃ ((p ⊃ q) ⊃ (p ⊃ r))
    (32) ⊨ (p ≡ q) ≡ ((p ⊃ q) ∧ (q ⊃ p))

Seuraavat tautologiat osoittavat, että konnektiivit ∧, ⊃ ja ≡ voidaan määritellä konnektiivien ∼ ja ∨ avulla.

  1. ⊨ (p ∧ q) ≡ ∼(∼p ∨ ∼q)
    ⊨ (p ⊃ q) ≡ (∼p ∨ q)
    ⊨ (p ≡ q) ≡ ((∼p ∨ q) ∧ (∼q ∨ p))

Vastaavasti ∼ ja ∧ tai ∼ ja ⊃ riittävät määrittelemään kaikki muut konnektiivit. Itse asiassa yksi ainoa sopivasti valittu kaksipaikkainen konnektiivi riittää negaation ja kaikkien muiden kaksipaikkaisten konnektiivien määrittelemiseen. Tällainen konnektiivi on ilmaisua ’ei molemmat’ vastaava Shefferin viiva |, jonka totuustaulukko on

Shefferin viivan totuustaulukko:

p q p|q
1 1 0
1 0 1
0 1 1
0 0 1

Tällöin on voimassa

  1. ⊨ (p|q) ≡ (∼p ∨ ∼q)

ja esimerkiksi

  1. ⊨ ∼p ≡ (p|p).

Toinen tällainen konnektiivi on ilmaisua ’ei–eikä’ vastaava Peircen nuoli ↓, joka saa totuustaulukossa arvon 1 vain silloin kun p ja q ovat epätosia. Ohjelmoinnissa (ja Boolen algebrassa) Shefferin viiva tunnetaan myös NAND-operaationa (engl. not and) ja Peircen viiva NOR-operaationa (engl. neither nor).

Lauselogiikan teorian kannalta tärkeitä ovat normaalimuodot, joihin jokainen ristiriidaton lause voidaan muuntaa. Olkoon A lause, joka sisältää atomilauseet p ja q. Lause A on disjunktiivisessa (konjunktiivisessa) normaalimuodossa, jos A on disjunktio (konjunktio) lauseista muotoa (±)p ∧ (±)q (tai (±)p ∨ (±)q), missä merkki (±) voidaan korvata negaatiolla ∼ tai jättää tyhjäksi. Nämä määritelmät ovat suoraan yleistettävissä tapauksiin, joissa A sisältää useampia kuin kaksi atomilausetta. Jokaiselle lauseelle B on olemassa lause A siten, että A on disjunktiivisessa (konjunktiivisessa) normaalimuodossa ja ⊨A ≡ B. Esimerkiksi lauseen p ≡ q disjunktiivinen ja konjunktiivinen normaalimuoto ovat

  1. ⊨ (p ≡ q) ≡ ((p ∧ q) ∨ (∼p ∧ ∼q))
    ⊨ (p ≡ q) ≡ ((∼p ∨ q) ∧ (p ∨ ∼q))

Klassisen lauselogiikan lauseet ovat äärellisen pituisia, joten niissä esiintyy aina äärellisen monta atomilausetta. Vastaavasti lauseiden totuustaulukot ovat äärellisiä: jos lauseessa A on n eri atomilausetta, niin A:n totuustaulukossa on 2n vaakariviä. Totuustaulukkomenetelmän avulla voidaan äärellisen monen laskutoimituksen avulla todeta mistä tahansa lauseesta A onko se tautologia vai ei, ts. kysymykselle ’Onko A tautologia vai ei?’ on olemassa efektiivinen ratkaisumenetelmä.

Looginen seuraus

Loogisten totuuksien ohella logiikassa tutkitaan muodollisesti pätevän päättelyn sääntöjä. Loogisen seurauksen käsite voidaan määritellä tautologian käsitteen avulla seuraavasti: lause B on lauseen A looginen seuraus jos ja vain jos ⊨ A ⊃ B. Yleisemmin sanomme, että B on lauseiden A1, . . ., An, looginen seuraus jos ja vain jos ⊨ (A1 ∧ ... ∧ An) ⊃ B.

Lauseet A ja B ovat loogisesti ekvivalentteja jos ja vain jos ⊨ A ≡ B. Looginen ekvivalenssi on lauseiden joukossa määritelty nk. ekvivalenssirelaatio (ts. refleksiivinen, symmetrinen ja transitiivinen relaatio), jonka ekvivalenssiluokat (sopivien määritelmien kautta) muodostavat Boolen algebran (ks. "Logiikan historia").

Loogisen seuraussuhteen perusominaisuus on edellä esitetyn määritelmän mukaan se, että se on välttämättä totuuden säilyttävä. Olkoon v jokin funktio, joka liittää kaikkiin atomilauseisiin p, q, . . . totuusarvon 0 tai 1. Funktion v arvo lauseelle A on tällöin nähtävissä A:n totuustaulukkoa vastaavalla rivillä. Jos nyt A on tosi v:n suhteen, ts. v(A) = 1, ja jos ⊨ A ⊃ B, niin myös B on tosi v:n suhteen, ts. v(B) = 1, sillä tautologian määritelmän mukaan myös v(A ⊃ B) = 1. Siten pätee: jos B seuraa loogisesti lauseista A1, . . . , An, niin aina kun A1, . . . , An sattuvat olemaan tosia, niin myös B on tosi. Tosien lauseiden loogiset seuraukset eivät voi olla epätosia – ja juuri tähän perustuu loogisen päättelyn voima ja merkitys.

Kaaviota muotoa

A1
A2
.
.
.
.
An
B

”Lauseista A1, ... An saadaan päätellä lause B”

sanotaan päättelysäännöksi. Lauseet A1, …, An ovat premissejä, ja lause B on johtopäätös eli konkluusio. Tällainen sääntö ilmaisee logiikan normatiivisuutta siinä, että se kertoo, millaiset päättelyaskeleet ovat sallittuja. Sääntö on loogisesti pätevä jos ja vain jos B on lauseiden A1, …, An looginen seuraus. Esimerkkeinä loogisesti pätevistä päättelysäännöistä voidaan mainita:

  1. (33)
A
∼∼A
  1. (34)
∼∼A
A
  1. (35)
A ∧ B
A
  1. (36)
A
B
A ∧ B
  1. (37)
A
A ∨ B
  1. (38)
∼(A ∧ B)
∼A ∨ ∼B
  1. (39)
∼(A ∨ B)
∼A ∧ ∼B
  1. (40)

modus tollendo ponens

A ∨ B
∼B
A
  1. (41)

modus (ponendo) ponens

A ⊃ B
A
B
  1. (42)

modus (tollendo) tollens

A ⊃ B
∼B
∼A
  1. (43)

hypoteettinen syllogismi

A ⊃ B
B ⊃ C
A ⊃ C
  1. (44)

disjunktiivinen syllogismi

A ∨ B
A ⊃ C
B ⊃ D
C ∨ D
  1. (45)
A ⊃ B
B ⊃ A
A ≡ B
  1. (46)

epäsuora todistus

∼A ⊃ (B ∧ ∼B)
A
  1. (47)

kontrapositio

∼B ⊃ ∼A
A ⊃ B
  1. (48)

ehdollinen todistus Jos

A
B
C

niin

A
B ⊃ C

Näiden päättelysääntöjen avulla voidaan osoittaa loogisesti päteviksi luonnollisessa kielessä esitettyjä argumentteja.

Esimerkki 1. Kalle tai Paavo on oikeassa. Jos hinnat nousevat, niin Kalle ei ole oikeassa. Mutta Paavo ei ole oikeassa. Siis hinnat eivät nouse.

Merkitään:
p = ’Kalle on oikeassa’
q = ’Paavo on oikeassa’
r = ’hinnat nousevat’

Premissit ovat tällöin p ∨ q, r ⊃ ∼p, ∼q ja johtopäätös ∼r. Todistus:

[1] p ∨ q premissi
[2] r ⊃ ∼p premissi
[3] ∼q premissi
[4] p [1], [3], sääntö (40)
[5] ∼∼p [4], sääntö (33)
[6] ∼r [2], [5], sääntö (42)

 

 

 

 

Esimerkki 2. Logiikka ei ole vaikeaa tai ei ole niin, että monet opiskelijat pitävät siitä. Jos matematiikka on vaikeaa, niin logiikkakin on vaikeaa. Siis jos monet opiskelijat pitävät logiikasta, niin matematiikka ei ole vaikeaa.

Merkitään:
p = ’logiikka on vaikeaa’
q = ’monet opiskelijat pitävät logiikasta’
r = ’matematiikka on vaikeaa’

Todistus:

[1] ∼p ∨ ∼q premissi
[2] r ⊃ p premissi
[3] q lisäpremissi
[4] ∼∼q [3], sääntö (33)
[5] ∼p [1], [4], sääntö (40)
[6] q ⊃ ∼p [1]–[5], sääntö (48)

 

 

 

 

 

Edellä on riveillä (3) – (5) oikealla siirtämällä eroteltu lisäpremissi q ja siitä pääteltävät lauseet; tämän päättelykuvion avulla saadaan ehdollisen todistuksen säännön avulla implikaation muotoinen johtopäätös (6), joka edellyttää vain varsinaiset premissit (1) ja (2).

Jos halutaan osoittaa, että lause B ei seuraa loogisesti premisseistä A1, . . . , An, on löydettävä sellainen totuusarvojakelu v atomilauseille, että v(A1) = 1, . . . , v(An) = 1, mutta v(B) = 0.

Lausekalkyyli

Edellä on määritelty lauselogiikan loogiset totuudet eli tautologiat totuustaulukkojen avulla. Tällaista lähestymistapaa kutsutaan semanttiseksi, koska siinä vedotaan totuuden ja epätotuuden käsitteisiin. Lausekalkyylin ideana on se, että loogiset totuudet voidaan määritellä myös aksiomaattisen menetelmän avulla, ts. valitsemalla sopivat tautologiat peruslauseiksi eli aksioomeiksi, joista kaikki muut tautologiat voidaan johtaa päättelysääntöjen avulla. Tätä lähestymistapaa kutsutaan syntaksiseksi, sillä siinä vedotaan vain lauseiden ”kieliopilliseen” rakenteeseen. Näin lauselogiikka voidaan esittää formaalisena kalkyylina määrittelemällä aakkosisto, lauseenmuodostussäännöt, aksioomat ja päättelysäännöt.

Lausekalkyylin aakkosisto sisältää seuraavat symbolit:

(a) p1, p2, . . . propositiokirjaimet
(b) negaatiomerkki
(c) implikaatiomerkki
(d) ( , ) sulkumerkit

 

 

 

Muut konnektiivit voidaan ottaa käyttöön määriteltyinä lyhennysmerkintöinä.

Äärelliset aakkosten jonot ovat lausekalkyylin ilmauksia. Lausekalkyylin lauseiden joukko on pienin joukko L, joka toteuttaa ehdot:

  1. (L1) p

i ∈ L jokaiselle i = 1, 2, . . .
(L2) jos A ∈ L, niin ∼A ∈ L
(L3) jos A ∈ L ja B ∈ L, niin (A ⊃ B) ∈ L
Tässä symboli ∈ tarkoittaa ”kuuluu joukkoon”. Esimerkiksi ∼(p1 ⊃ ∼p2) on lause, mutta ∼(∼p2) ei ole. Lauseen uloimmat sulkumerkit jätetään usein kirjoittamatta näkyviin, ts. A ⊃ B on lyhennysmerkintä lauseelle (A ⊃ B).

Kirjaimia A, B, ... käytetään ns. syntaktisina metavariaabeleina, jotka viittaavat mielivaltaisiin lauseisiin. Sellaiset merkkijonot kuin

  1. (49) (A ⊃ B) ⊃ ∼A

ovat lauseskeemoja, joista saadaan lauseita sijoittamalla A:n ja B:n paikalle atomilauseita tai yhdistettyjä lauseita. Esimerkiksi

  1. (p

1 ⊃ p2) ⊃ ∼p1
((p3 ⊃ p4) ⊃ ∼p1) ⊃ ∼(p3 ⊃ p4)
ovat skeeman (49) erikoistapauksia.

Kaikki seuraavien skeemojen erikoistapaukset ovat lausekalkyylin aksioomia:

  1. (A1) A ⊃ (B ⊃ A)
    (A2) (A ⊃ (B ⊃ C)) ⊃ ((A ⊃ B) ⊃ (A ⊃ C))
    (A3) ∼∼A ⊃ A

Aksioomia on siten ääretön määrä. A1, A2 ja A3 ovat lausekalkyylin aksioomaskeemat.

Lausekalkyylin ainoa päättelysääntö on modus ponens

  1. (MP)
A ⊃ B
A
B

Olkoon Σ joukko lauseita. Äärellinen jono lauseita B1, . . . , Bm on lauseen Bm deduktio eli johto premisseistä Σ, jos kaikille k = 1, . . . , m jokin seuraavista ehdoista on voimassa:

  1. (D1) B

k on aksiooma
(D2) Bk ∈ Σ
(D3) Bk voidaan päätellä MP:n avulla jonon aiemmista lauseista Bi ja Bj, i, j < k
Tällöin merkitään Σ ⊢Β. Mikäli Σ = {A1, . . . , An}, ts. Σ on lauseiden A1, …, An muodostama joukko, merkitään myös A1, . . . , An ⊢ B. Näin määriteltyä relaatiota ⊢ sanotaan dedusoitavuusrelaatioksi.

Jos lause B on dedusoitavissa tyhjästä premissijoukosta Ø, ts. Ø ⊢ B, merkitään yksinkertaisesti ⊢B, jolloin B:n sanotaan olevan lausekalkyylin teoreema eli todistuva lause. Vastaavaa deduktiota sanotaan B:n todistukseksi.

Deduktion käsite toteuttaa mm. seuraavat ehdot:

  1. (50)

Monotonisuus: Jos Σ ⊢A ja Σ ⊆ Δ, niin Δ ⊢Α.
(51) Jos Σ ⊢Α ja Δ ⊢Α ⊃ Β, niin Σ ∪ Δ ⊢Β.
(52) Deduktioskeema: Jos A1, . . . , An-1, An ⊢B, niin A1, . . . , An-1 ⊢An ⊃ B.
(53) Kompaktisuus: Jos Σ ⊢A, niin on olemassa äärellinen Σ0 ⊆ Σ, jolle Σ0 ⊢A.
Ehdossa (50) symboli ⊆ tarkoittaa osajoukkoa, ja ehdossa (51) symboli ∪ tarkoittaa joukkojen unionia eli yhdistettä: joukon A ja B unioni A ∪ B on kaikkien niiden alkioiden joukko, jotka kuuluvat A:han tai B:hen (”tai” on tässä inklusiivinen, ks. "Logiikan historia").

Lausekalkyylille tunnetaan monia muitakin aksiomatisointeja kuin skeemat (A1), (A2) ja (A3). Ensimmäisen aksioomajärjestelmän esitti Gottlob Frege vuonna 1879 (ks. "Logiikan historia"). Näissä eri järjestelmissä voidaan myös peruskonnektiivit valita eri tavoilla. Edelleen päättelysääntöjä voidaan lisätä, jolloin aksioomia tarvitaan vähemmän: Gerhard Gentzenin esittämissä luonnollisen päättelyn kalkyyleissa ei ole lainkaan aksioomia. Todistukset voidaan esittää lausejonojen sijasta myös erilaisten taulukkojen tai puiden avulla. Kuitenkin kaikkien näiden systeemien teoreemojen joukot – kun otetaan käyttöön muut konnektiivit määritelmien avulla – yhtyvät.

Lausekalkyylilla voidaan osoittaa olevan mm. seuraavat tärkeät ominaisuudet, jotka osoittavat, että lauselogiikan semanttinen ja syntaktinen tarkastelu tuottavat saman lopputuloksen:

  1. (54)

Korrektisuus: Jos ⊢ B, niin ⊨ B.
(55) Täydellisyys: Jos ⊨ B, niin ⊢ B.
Korrektisuus (englanniksi usein Soundness Theorem) (54) takaa, että kaikki aksioomista dedusoitavissa olevat eli todistuvat lauseet ovat tautologioita. Täydellisyys (55) takaa, että lausekalkyylissä voidaan todistaa kaikki tautologiat. Yhdistämällä ominaisuudet (54) ja (55) voidaan todeta, että teoreemojen joukko ja tautologioiden joukko yhtyvät:

  1. (56) B on teoreema, jos ja vain jos B on tautologia.
    (57) A

1, . . . , An ⊢ B, jos ja vain jos B on premissien A1, . . . , An looginen seuraus.
(58) Ristiriidattomuus: Mikään lause muotoa B ⋀ ∼B ei ole teoreema.
(59) Ratkeavuus: On olemassa efektiivinen ratkaisumenetelmä kysymykselle ’Onko B teoreema vai ei?’.
(59) seuraa välittömästi tuloksesta (56) sekä totuustaulukkomenetelmästä.

Ei-klassinen lausekalkyyli

Edellä kuvatulle klassiselle lausekalkyylille on esitetty useita erilaisia muunnelmia, joita kutsutaan ei-klassisiksi. Jan Łukasiewiczin vuonna 1920 esittämässä moniarvologiikassa luovutaan oletuksesta, jonka mukaan totuusarvoja on vain kaksi. Kolmiarvologiikassa on kolme totuusarvoa, joista tavallisesti yhden ajatellaan ilmaisevan epävarmuutta, ja yleisesti n-arvoisessa logiikassa on n totuusarvoa. Näiden systeemien yleistyksenä voidaan pitää Boolen-arvoisia logiikkoja, joissa klassinen totuusarvojen joukko {0, 1} korvataan mielivaltaisella Boolen algebralla.

Intuitionistinen logiikka, jonka Arend Heyting formalisoi vuonna 1930, liittyy L. E. J. Brouwerin intuitionismiin (ks. "Logiikan historia"). Se pyrkii ilmaisemaan ne päättelyperiaatteet, jotka ovat hyväksyttävä konstruktiivisessa matemaattisessa ajattelussa. Intuitionistisessa logiikassa ei esimerkiksi hyväksytä kolmannen poissuljetun lakia p ∨ ∼p eikä lakia ∼∼p ⊃ p. Luontevan tulkinnan tälle logiikalle antaa A. A. Kolmogorovin esittämä ehdotus, jonka mukaan lauseet p, q, … käsitetään ongelmiksi, jolloin konnektiiveille voidaan antaa uudenlainen sisältö:

∼p p:n ratkaisu johtaa ristiriitaan
p ∧ q p voidaan ratkaista ja q voidaan ratkaista
p ∨ q p voidaan ratkaista tai q voidaan ratkaista
p ⊃ q jokaista p:n ratkaisua kohti voidaan löytää q:n ratkaisu

Väitteen p ∨ ∼p pätevyys kaikille p merkitsisi tämän tulkinnan mukaan, että jokaiselle ongelmalle voidaan antaa positiivinen tai negatiivinen ratkaisu, mikä ei pidä paikkaansa. (Toinen tulkinta mainitaan alla predikaattilogiikan yhteydessä.)

Intuitionistisen lausekalkyylin teoreemojen luokka on aito osa klassisen lausekalkyylin teoreemojen joukosta. Jos lause A on todistuva intuitionistisessa lausekalkyylissä, merkitään ⊢i A. Relaatio ⊢i toteuttaa periaatteen

i A ∨ B, jos ⊢i A tai ⊢i B, toisin kuin ⊢. Glivenko on osoittanut, että

  1. ⊢ A, jos ja vain jos ⊢

i ∼∼A.

 

Predikaattilogiikka

Ensimmäisen kertaluvun predikaattilogiikassa laajennetaan lauselogiikan tarkastelutapaa analysoimalla atomilauseiden rakennetta predikaation ja identiteetin avulla sekä ottamalla käyttöön yksilövariaabelit eli -muuttujat ja niitä sitovat kvanttorit. Kvanttorien teorian kehittivät ensimmäisinä toisistaan riippumatta Frege vuonna 1879 ja C. S. Peirce vuonna 1885. Korkeamman kertaluvun predikaattilogiikassa käytetään lisäksi kvanttoreita predikaattivariaabeleille.

Predikaatit

Tarkastelkaamme luonnollisen kielen lauseita:

  1. (60) Russell on loogikko.
    (61) Oulu on Helsingin pohjoispuolella.
    (62) Ruotsi on Suomen ja Norjan välissä.

Näissä lauseissa esiintyy erisnimiä (’Russell’, ’Oulu’, ’Suomi’), jotka nimeävät eräitä yksilöitä. Kieliopissa on tapana sanoa, että lauseessa (60) ’Russell’ on subjekti, ’on’ on predikaatti ja ’loogikko’ on predikatiivi. Logiikassa terminologia on hieman erilaista: nimi ’Russell’ on lauseen (60) subjekti, ’loogikko’ on yksipaikkainen predikaatti ja ’on’ on niin kutsuttu kopula. Vastaavasti lauseen (61) loogisena subjektina on pari <’Oulu’, ’Helsinki’> ja kaksipaikkaisena predikaattina ’– on –:n pohjoispuolella’. Lauseessa (62) on kolmipaikkainen predikaatti ’– on –:n ja –:n välissä’. Yksipaikkaiset predikaatit ilmaisevat yksilöiden ominaisuuksia, kun taas kaksi- tai useampipaikkaiset predikaatit ilmaisevat yksilöiden välisiä suhteita.

Eräät luonnollisen kielen predikaatit eivät ilmaise yksilöiden vaan ominaisuuksien ominaisuuksia. Esimerkki tällaisesta toisen kertaluvun predikaatista on ’väri’: lauseessa

  1. (63) Vihreä on väri

liitetään ominaisuus ’olla väri’ ominaisuuteen ’olla vihreä’.

Ensimmäisen kertaluvun predikaattilogiikassa tarkastelun kohteena ovat yksilöt, joihin viitataan yksilövakioiden a1, a2, . . . avulla, sekä yksilöiden ominaisuudet ja suhteet, joita ilmaistaan predikaattien P, Q, . . . avulla. Yksipaikkaisina predikaatteina käytetään tavallisesti symboleja P11, P12, . . ., ja yleisesti n-paikkaisina predikaatteina symboleja Pn1, Pn2, . . . Näiden avulla voidaan muotoilla atomilauseita seuraavan säännön mukaan:

  1. (64) Jos P

nj on n-paikkainen predikaatti ja ai1, . . . , ain ovat yksilövakioita, niin Pnj(ai1, . . . , ain) on atomilause.
Siten lauseet (60), (61) ja (62) voidaan formalisoida esimerkiksi atomilauseiden P11(a1), P21(a2,a3) ja P31(a4, a5, a6) avulla.

Monissa matemaattisissa sovellutuksissa on hyödyllistä käyttää predikaattien sijasta funktoreita eli funktiosymboleja. Yksipaikkaisia funktiosymboleja merkitään f11, f12, . . . ja n-paikkaisia fn1, fn2, . . . Symbolista fnj ja yksilövakioista ai1, . . . , ain voidaan muodostaa termi fnj(ai1, . . . , ain), jossa funktiosymbolia fnj sovelletaan argumentteihin ai1, . . . , ain.

Ottamalla käyttöön identiteettisymboli = voidaan muodostaa muotoa t1 = t2 olevia atomilauseita, joissa t1 ja t2 ovat yksilövakioita tai funktiosymbolien avulla muodostettuja termejä. Jos esimerkiksi a1 ja a2 ovat nimet luvuille 1 ja 2 ja jos f21 on kertolaskua ilmaiseva funktori, niin yhtälö 1 ∙ 2 = 2 voidaan formalisoida muodossa f21(a1, a2) = a2.

Funktiosymbolien käyttö on siinä mielessä epäolennaista, että n-paikkaiset funktorit voidaan aina korvata (n + 1)-paikkaisilla predikaateilla. Tästä syystä monia teoreettisia tarkoituksia varten riittää tarkastella sellaista predikaattikalkyyliä, joka sisältää predikaatteja mutta ei lainkaan funktoreita.

Yksilövakiot ja predikaatit (sekä funktorit) ovat predikaattikalkyylin ei-loogisia symboleja. Predikaattikalkyyliä sanotaan monadiseksi, jos siinä on vain yksipaikkaisia predikaatteja, ja polyadiseksi, jos siinä on myös kaksi- tai useampipaikkaisia predikaatteja.

Kvanttorit

Predikaattilogiikan loogiseen aakkosistoon kuuluu lauselogiikan konnektiivien lisäksi myös yksilövariaabelit tai -muuttujat x1, x2, . . . (tai x, y, . . .) sekä kvanttorit ∀ ja ∃.

Yksilövariaabelit ovat kielellisiä symboleja, joiden avulla voidaan muodostaa ilmauksia samaan tapaan kuin yksilövakioiden avulla. Yksilövakiot a1, a2, . . . , yksilövariaabelit x1, x2, . . . , ja näistä funktiosymbolien avulla muodostetut ilmaukset fnj(t1, . . . , tn) ovat termejä. Ilmaukset muotoa P11(x4), P21(x2, a3), f21(x1, x2) = x3 jne. ovat atomikaavoja. Näissä kaavoissa esiintyvät variaabelit eli muuttujat ovat eräänlaisia paikanpitäjiä yksilövakioille: atomikaavoista saadaan atomilauseita sijoittamalla niiden tilalle yksilövakioita.

Atomikaavoista voidaan muodostaa yhdistettyjä kaavoja konnektiivien avulla samalla tavalla kuin lauselogiikassa. Tämän lisäksi on voimassa sääntö:

  1. (65) Jos A on kaava ja x on yksilövariaabeli, niin ∀xA ja ∃xA ovat kaavoja.

Symbolia ∀ sanotaan universaalikvanttoriksi ja symbolia ∃ eksistenssikvanttoriksi. Näistä ∀ vastaa luonnollisen kielen sanoja ’kaikki’ tai ’jokainen’, kun taas ∃ vastaa sanoja ’jokin’ tai ’on olemassa’:

∀xP(x) ’kaikilla yksilöillä x on ominaisuus P’
  ’jokaiselle oliolle x pätee P(x)’
   
∃xP(x) ’jollakin yksilöllä x on ominaisuus P’
  ’on olemassa (ainakin yksi) olio x siten, että P(x)’

Kaavan A yhtenäinen osa, joka on itse kaava, on A:n osakaava. Olkoon ∀xC kaavan A osakaava. Tällöin sanotaan, että kvanttorin ∀x (vaikutus)ala A:ssa on C. Variaabelin x kaikki esiintymät kaavassa ∀xC, kun kvanttorin ∀x ala on C, ovat x:n sidottuja esiintymiä A:ssa. Variaabelin x esiintymä A:ssa, joka ei ole sidottu, on x:n vapaa esiintymä A:ssa. Kaavaa, jossa on jonkin variaabelin vapaita esiintymiä, on avoin kaava. Kaavat, jotka eivät ole avoimia, ovat suljettuja kaavoja eli predikaattilogiikan lauseita.

Esimerkiksi kaavassa ∀x(P(x) ⊃ Q(x, y)) sekä implikaation etu- että takajäsen kuuluvat kvanttorin ∀x alaan, ja täten variaabeleista molemmat x:n esiintymät ovat sidottuja ja y on vapaa. Sen sijaan kaavassa ∀xP(x) ⊃ Q(x, y) ainoastaan P(x) kuuluu kvanttorin ∀x alaan: implikaation takajäsenen Q(x, y) molemmat variaabelit x ja y ovat vapaita.

Kaavaa, jossa esiintyy vapaina variaabelit x1, . . . , xn, merkitään usein symbolilla A(x1, . . . , xn). Kaavan A(x1, . . . , xn) universaalinen sulkeuma on lause ∀x1 . . . ∀xnA.

Merkintä SxtA| tarkoittaa kaavaa, joka saadaan kaavasta A sijoittamalla termi t kaikkiin variaabelin x vapaisiin esiintymiin A:ssa. S on sijoitusoperaattori. Termi t on vapaa x:lle A:ssa, jos mikään t:ssä esiintyvä variaabeli ei tule sijoituksen tuloksena sidotuksi kaavassa SxtA|.

Malliteoria

Predikaattilogiikan semantiikkaa kutsutaan malliteoriaksi. Alfred Tarskin 1933 esittämä predikaattikalkyylin lauseiden totuusmääritelmä perustuu kaavojen toteutuvuuden käsitteeseen. Olkoon L predikaattikalkyylin kieli. Tällöin L-struktuurit ovat pareja M = <X, V>, jossa X on ei-tyhjä joukko ja V on funktio, joka kuvaa kielen L yksilövakiot X:n alkioiksi, yksipaikkaiset predikaatit X:n osajoukoiksi, n-paikkaiset predikaatit n-paikkaisiksi relaatioiksi X:ssä ja n-paikkaiset funktiosymbolit n-paikkaisiksi operaattoreiksi X:ssä. Siis

  1. V(a

i) ∈ X
V(P1i) ⊆ X
V(Pni) ⊆ Xn
V(fni): Xn → X
X on L-struktuurin perusjoukko (engl. domain) ja V on tulkintafunktio.

Olkoon W joukon X alkioiden äärettömien jonojen w = <wi | i = 1, 2, . . .> joukko. Määritellään

  1. a

i[w] = V(ai) yksilövakioille ai
xi[w] = wi yksilövariaabelille xi
fni(t1, . . . , tn)[w] = V(fnj)(t1[w], . . . , tn[w]) funktiosymbolille fni ja termeille t1, . . . , tn
Nämä ehdot antavat induktiivisen (eli loogista rakennetta seuraavan) määritelmän termin t arvolle t[w] jonon w ja L-struktuurin M = <X, V> suhteen; t[w] on aina joukon X alkio.

Jono w ∈ W toteuttaa kaavan A L-struktuurissa M = <X, V> – merkitään M ⊨w A – seuraavien induktiivisten ehtojen mukaisesti:

  1. M ⊨

w Pnj(ai1, . . . , ain) joss <ai1[w], . . . , ain[w]> ∈ V(Pnj)
M ⊨w t1 = t2 joss t1[w] = t2[w]
M ⊨w ∼B, joss M ⊭w B
M ⊨w (B ∧ C) joss M ⊨w B ja M ⊨w C
M ⊨w (B ∨ C) joss M ⊨w B tai M ⊨w C
M ⊨w (B ⊃ C) joss M ⊭w B tai M ⊨w C
M ⊨w (B ≡ C) joss (M ⊨w B joss M ⊨w C)
M ⊨w ∀xkB joss M ⊨w(d|k) B kaikille d ∈ X
M ⊨w ∃xkB joss M ⊨w(d|k) B jollekin d ∈ X
Tässä määritelmässä M⊭w B on lyhennys ehdolle ei: M ⊨w B. Edelleen, kun k on jokin luonnollinen luku, w(d|k) on jono, joka saadaan jonosta w = <wi|i = 1, 2, . . . > korvaamalla wk alkiolla d.

Jos variaabeli xi ei esiinny vapaana kaavassa B, niin ehto M ⊨w B on riippumaton alkiosta wi. Siten jos B on lause ja jokin jono w toteuttaa B:n M:ssä, niin jokainen jono w toteuttaa B:n M:ssä. Näin voidaan määritellä: lause B on tosi L-struktuurissa M joss M ⊨w B jollekin w ∈ W. Jos lause B on tosi M:ssä, merkitään M ⊨ B; tällöin M on B:n malli. Jos ei päde, että M ⊨ B, ts. M ⊭ B, lause B on epätosi M:ssä. Edelleen struktuuri M on lausejoukon Σ malli, jos M ⊨ B kaikille B ∈ Σ.

Looginen totuus predikaattilogiikan tasolla voidaan määritellä jälleen Leibnizin ideaa seuraten: kielen L lause A on validi, jos M ⊨ A kaikille L-struktuureille M. Vastaavasti kaava A(x1, . . . , xn) on validi, jos ja vain jos sen universaalinen sulkeuma ∀x1 . . . ∀xnA on validi lause. Jos A on validi kaava, merkitään ⊨ A. Kaava A on kontradiktio, jos sen universaalinen sulkeuma on epätosi kaikissa L-struktuureissa.

Esimerkkejä valideista kaavoista:

  1. (66) ∀xP(x) ≡ ∼∃x∼P(x)
    (67) ∃xP(x) ≡ ∼∀x∼P(x)
    (68) ∀xP(x) ≡ ∀yP(y)
    (69) ∀xP(y) ≡ P(y)
    (70) ∀xP(x) ⊃ P(t) (t yksilövakio tai -variaabeli)
    (71) ∀x∀yP(x, y) ≡ ∀y∀xP(x, y)
    (72) ∃x∃yP(x, y) ≡ ∃y∃xP(x, y)
    (73) (P(y) ⊃ ∀xQ(x)) ≡ ∀x(P(y) ⊃ Q(x))
    (74) (P(y) ⊃ ∃xQ(x)) ≡ ∃x(P(y) ⊃ Q(x))
    (75) (∃xP(x) ⊃ Q(y)) ≡ ∀x(P(x) ⊃ Q(y))
    (76) (∀xP(x) ⊃ Q(y)) ≡ ∃x(P(x) ⊃ Q(x))
    (77) ∃x(P(x) ∨ Q(x)) ≡ (∃xP(x) ∨ ∃xQ(x))
    (78) ∀x(P(x) ∧ Q(x)) ≡ (∀x(P(x) ∧∀xQ(x))
    (79) ∃x(P(x) ∧ Q(x)) ⊃ (∃xP(x) ∧ ∃xQ(x))
    (80) (∀xP(x) ∨ ∀xQ(x)) ⊃ ∀x(P(x) ∨ Q(x))
    (81) ∃y∀xP(x, y) ⊃ ∀x∃yP(x, y)
    (82) ∀x(P(x) ⊃ Q(x)) ⊃ (∀xP(x) ⊃ ∀(Q(x))
    (83) ∀x(P(x) ⊃ Q(x)) ⊃ (∃xP(x) ⊃ ∃xQ(x))
    (84) P(a

i) ⊃ ∃xP(x)
(85) ∀xP(x) ⊃ ∃xP(x).
Loogisen seurauksen käsite voidaan määritellä periaatteessa samalla tavalla kuin lausekalkyylissä: kaava B on kaavojen A1, . . . , An looginen seuraus, jos ⊨ (A1 ∧ . . . ∧ An) ⊃ B. Lauseille tämä määritelmä voidaan muotoilla puhumalla totuudesta: lause B on lausejoukon Σ looginen seuraus, jos B on tosi kaikissa Σ:n malleissa.

Kaavat A ja B ovat loogisesti ekvivalentteja, jos ⊨ A ≡ B. Jokainen kaava A voidaan muuntaa loogisesti ekvivalentiksi kaavaksi, joka on nk. preneksissä normaalimuodossa eli muodossa Q1…QkC, jossa Qi, i = 1, . . . , k, ovat kvanttoreita ∀xi tai ∃xi ja C on kaava ilman kvanttoreita. Tällöin kaikki kvanttorit on vedetty kaavan eteen. Toinen tärkeä ryhmä predikaattilogiikan kaavojen normaalimuotoja, jossa kvanttorit työnnetään mahdollisimman syvälle kaavojen sisään, on Jaakko Hintikan kehittämät distributiiviset normaalimuodot.

Kvanttorit ja päättely

Predikaattilogiikassa saadaan käyttää päättelysääntöinä kaikkia lausekalkyylin sääntöjä; myös useat edellä luetelluista valideista lauseista voidaan muuntaa päteviksi päättelysäännöiksi. Esimerkiksi tulosta (81) vastaa sääntö

∃y∀xA
∀x∃yA

Keskeiset kvanttoreita koskevat päättelysäännöt ovat:

  1. (UG)

Universaalinen generalisaatio

A
∀xA

jos x ei ole vapaa premisseissä, joista A on johdettu.

  1. (US)

Universaalinen spesifikaatio

∀xA
SxtA|

jos termi t on vapaa x:lle A:ssa.

  1. (EG)

Eksistentiaalinen generalisaatio

SxtA|
∃xA

jos termi t on vapaa x:lle A:ssa.

  1. (ES)

Eksistentiaalinen spesifikaatio

∃xA
SxtA|

jossa t on variaabeli, joka ei esiinny kaavan ∃xA johdossa.

Näiden päättelysääntöjen avulla voidaan jälleen formalisoida luonnollisessa kielessä esitettyjä argumentteja. Lausekalkyylin päättelyaskelia merkitään LK.

Esimerkki (De Morgan). Kaikki ihmiset ovat eläimiä. Siis kaikki ihmisten päät ovat eläinten päitä.

Merkitään:
P(x) = ’x on ihminen’
Q(x) = ’x on eläin’
R(x, y) = ’y on x:n pää’

Todistus:

[1] ∀x(P(x) ⊃ Q(x)) premissi
[2] ∃z(P(z) ∧ R(z, y)) lisäpremissi
[3] P(u) ∧ R(u, y) [2], ES
[4] P(u) LK
[5] P(u) ⊃ Q(u) [1], US
[6] Q(u) [4], [5], LK
[7] R(u, y) [3], LK
[8] Q(u) ∧ R(u, y) [6], [7], LK
[9] ∃z(Q(z) ∧ R(z, y)) [8], EG
[10] ∃z(P(z) ∧ R(z, y)) ⊃ ∃z(Q(z) ∧ R(z, y)) LK
[11] ∀y(∃z(P(z) ∧ R(z, y)) ⊃ ∃z(Q(z) ∧ R(z, y))) UG

Predikaattikalkyyli

Myös predikaattilogiikka voidaan muotoilla syntaktisesti. Predikaattikalkyyli voidaan aksiomatisoida valitsemalla aksioomaskeemoiksi lausekalkyylin A1, A2 ja A3 sekä skeemat

  1. (A4) ∀xA ⊃ S

txA|, termi t vapaa x:lle A:ssa
(A5) ∀x(A ⊃ B) ⊃ (A ⊃ ∀xB), x ei vapaa A:ssa.
Päättelysääntöjä ovat modus ponens ja universaalinen generalisaatio UG. Aakkosistoon riittää ottaa mukaan kvanttori ∀, sillä kaavan (67) mukaan ∃ voidaan määritellä sen avulla.

Identiteetillä varustetussa predikaattikalkyylissä lisätään aksioomat

  1. (A6) x = x

    (A7) t

1 = t2 ⊃ (A = B), jossa kaava B saadaan kaavasta A korvaamalla termin t1 esiintymä A:ssa termillä t2 ja jossa tämä esiintymä ei ole kvanttorin ∀t1 tai ∀t2 sitoma.
Deduktio, todistus ja teoreema määritellään kuten lausekalkyylissä. Deduktioskeema pätee kuten lausekalkyylissä, mikäli An on lause. Lisäksi pätee ekvivalenssin sijoitussääntö:

  1. (86) Olkoon B kaava, joka saadaan kaavasta A korvaamalla nolla tai useampia kaavan C esiintymiä A:ssa kaavalla D. Tällöin: jos ⊢ C ≡ D, niin ⊢ A ≡ B.

Jälleen voidaan osoittaa, että semanttinen ja syntaktinen tarkastelu antavat saman lopputuloksen. Predikaattikalkyylin korrektisuus-teoreema

  1. (87)

Korrektisuus: Jos ⊢ A, niin ⊨ A
seuraa yleisemmästä tuloksesta:

  1. (88) Olkoon

Σ lausejoukko, A lause ja M L-struktuuri. Tällöin jos M ⊨ Σ ja Σ ⊢A, niin M ⊨ A.
Toisin sanoen kaikki lausejoukon Σ loogiset seuraukset ovat tosia Σ:n malleissa, joten myös predikaattilogiikassa looginen seuraus on totuuden säilyttävää. Valitsemalla Σ:n paikalle tyhjän joukon Ø saamme tuloksesta (88) seurauksen (87). Teoreemasta (87) seuraa predikaattikalkyylin ristiriidattomuus.

Täydellisyysteoreema

  1. (89)

Täydellisyys: Jos ⊨ A, niin ⊢ A
seuraa Kurt Gödelin 1930 todistamasta teoreemasta:

  1. (90) Lausejoukko

Σ on ristiriidaton, jos ja vain jos Σ:lla on malli.
Lausejoukkoa Σ sanotaan ristiriitaiseksi, jos Σ ⊢ B ∧ ∼B jollekin B, ja muulloin ristiriidattomaksi. Edelleen Σ on täydellinen L:n suhteen jos A ∈ Σ tai ∼A ∈ Σ kaikille predikaattikalkyylin L lauseille. Tuloksen (90) todistuksessa käytetään hyväksi Adolf Lindenbaumin todistamaa tulosta, jonka mukaan jokainen ristiriidaton lausejoukko sisältyy osajoukkona johonkin ristiriidattomaan ja täydelliseen lausejoukkoon. Tuloksesta (90) seuraa myös predikaattikalkyylin malliteorian kannalta keskeinen kompaktisuuslause:

  1. (91)

Kompaktisuus: Lausejoukolla Σ on malli, jos ja vain jos Σ:n jokaisella äärellisellä osajoukolla on malli.
Ensimmäisen kertaluvun teoriat ovat kielen L ristiriidattomia lausejoukkoja Σ, jotka ovat suljettuja deduktion suhteen, ts. jos Σ ⊢ A, niin A ∈ Σ. Predikaattikalkyylin todistusteorian ja malliteorian avulla voidaan tutkia ensimmäisen kertaluvun teorioiden aksiomatisoitavuutta, täydellisyyttä ja ratkeavuutta sekä näissä teorioissa esiintyvien predikaattien määriteltävyyttä.

Monadinen eli vain yksipaikkaisia predikaatteja sisältävä predikaattikalkyyli on ratkeava, ts. kysymykselle ’Onko A validi kaava vai ei?’ on olemassa efektiivinen ratkaisumenetelmä. (Efektiivisen laskettavuuden käsite määritellään eksaktilla tavalla automaattien ja rekursiivisten funktioiden teoriassa; ks. "Logiikan historia".) Sen sijaan Alonzo Churchin vuonna 1936 esittämän tuloksen mukaan polyadinen eli relaatioita sisältävä predikaattikalkyyli ei ole ratkeava: on tosin olemassa algoritmeja, jotka tunnistavat A:n validiksi, jos A on validi, mutta mikäli A ei ole validi, nämä menetelmät eivät kykene sitä varmuudella toteamaan äärellisen monella askelmäärällä.

Edellä on mainittu, että lausekalkyylin teoreemojen joukon struktuuri vastaa Boolen algebraa. Myös predikaattikalkyylille voidaan antaa algebrallinen struktuuri, joka – kvanttorien ja sijoitusoperaation vuoksi – on monimutkaisempi ja rikkaampi kuin tavallinen Boolen algebra. Tarskin ja Leon Henkinin sylinterialgebra ja Paul Halmosin polyadiset algebrat ovat algebrallisen logiikan piirissä kehitettyjä vastineita predikaattilogiikalle.

Predikaattilogiikan vaihtoehtoja ja laajennuksia

1) Intuitionistinen predikaattilogiikka saadaan lisäämällä kvanttorit intuitionistiseen lausekalkyyliin. Suosittu tapa tulkita intuitionistisia konnektiiveja ja kvanttoreita perustuu ajatukseen, että niiden merkitys riippuu yhdistettyjen lauseiden todistettavuusehdoista – eikä totuusehdoista kuten klassisessa logiikassa:

kaava: todistus:
A ∧ B konstruktio, joka todistaa sekä A:n että B:n
A ∨ B konstruktio, joka todistaa A:n tai B:n
A ⊃ B konstruktio, joka efektiivisesti muuntaa jokaisen A:n todistuksen B:n todistukseksi
∼A konstruktio, joka efektiivisesti muuntaa jokaisen A:n todistuksen kontradiktion todistukseksi
∀xA konstruktio, joka jokaista vakiota a kohden antaa kaavan SxaA| todistuksen
∃xA konstruktio, joka todistaa kaavan SxaA| jollekin vakiolle a

Esimerkiksi kaavat

  1. ∼∀xP(x) ⊃ ∃x∼P(x)
    ∼∃x∼P(x) ⊃ ∀xP(x)
    ∼∀x∼P(x) ⊃ ∃xP(x)

eivät päde intuitionistisesti. Siten matemaattisten eksistenssiteoreemojen epäsuorat todistukset eivät ole intuitionistien mukaan hyväksyttäviä. Myöskään ns. Markovin periaate

  1. (∀x(P(x) ∨ ∼P(x)) ∧ ∼∀x∼P(x)) ⊃ ∃xP(x),

joka hyväksytään venäläisen A. A. Markovin konstruktiivisessa koulukunnassa, ei ole intuitionistisesti pätevä.

2) Identiteetin ohella predikaattilogiikan kieleen voidaan liittää myös muita erityisiä symboleja, kuten määrätty kuvaus-operaattori ι (jolloin termi ιxP(x) viittaa siihen yksikäsitteisesti määrättyyn ainoaan olioon x, jolla on ominaisuus P, mikäli tällainen x on olemassa) ja Hilbertin ε-operaattori (jolloin εxP(x) viittaa mielivaltaiseen olioon x, jolle pätee P(x)).

3) Predikaattilogiikan malliteoriaa voidaan eräitä sovelluksia varten muuntaa siten, että L-struktuurin perusjoukko jakautuu useampaan erilliseen joukkoon – esimerkiksi erottaen toisistaan matemaattiset ja ei-matemaattiset objektit. Tällaista logiikkaa sanotaan monensorttiseksi (engl. many-sorted).

4) Predikaattilogiikan ilmaisuvoiman lisäämiseksi on esitetty monia logiikan systeemejä. Toisen kertaluvun logiikassa otetaan käyttöön n-paikkaiset predikaattivariaabelit wn1, wn2, . . . (n = 1, 2, …) ja n-paikkaiset funktorivariaabelit fn1, fn2, . . . (n = 1, 2, . . .) sekä sallitaan kaavat muotoa ∀wniA ja ∃wniA, joissa kvanttorit sitovat näitä uusia variaabeleita. Monadisessa toisen kertaluvun logiikassa käytetään vain yksipaikkaisia predikaattivariaabeleita w11, w12, . . .; heikolla toisen kertaluvun logiikalla tarkoitetaan sellaista monadista toisen kertaluvun logiikkaa, jossa variaabelin w1i arvoalueena ovat äärelliset joukot. Ottamalla käyttöön n. kertaluvun predikaatteja ja vastaavia variaabeleita kaikille n = 1, 2, . . . saadaan logiikan järjestelmä, jota Bertrand Russell nimitti tyyppiteoriaksi.

Monet matemaattiset väitteet ovat luonteeltaan toisen kertaluvun lauseita – esimerkiksi aritmetiikan induktioaksiooma, joka koskee kaikkia luonnollisten lukujen joukkoja (tai vastaavasti kaikkia luonnollisten lukujen ominaisuuksia), sekä reaalilukujen aksiooma, jonka mukaan kaikilla rajoitetuilla reaalilukujoukoilla on pienin yläraja. Toisen kertaluvun logiikassa voidaan ilmaista kahden struktuurin isomorfia (rakenneyhtäläisyys). Siten sen puitteissa voidaan formalisoida kategorisia aksiomaattisia teorioita, joiden kaikki mallit ovat keskenään isomorfisia.

Toisen kertaluvun logiikan – ja yleisemmin tyyppiteorian – validien lauseiden joukko ei ole rekursiivisesti numeroituva, joten sille ei voi antaa rekursiivista täydellistä aksiomatisointia. Henkin osoitti kuitenkin vuonna 1950, että tyyppiteoria on täydellinen, mikäli tavallisten ”täysien” struktuurien sijasta sallitaan ”epästandardeja” struktuureja, joissa toisen kertaluvun kvanttorit eivät varioi yli perusjoukon kaikkien osajoukkojen vaan ainoastaan yli sopivasti valitun osajoukkoperheen.

5) Identiteetillä varustetussa predikaattilogiikassa voidaan määritellä numeeriset kvanttorit ∃! (on olemassa täsmälleen yksi), ∃n (on olemassa n olioita ...), ja ∃≥n (on olemassa ainakin n olioita ...). Esimerkiksi ∃3xP(x) voidaan määritellä kaavan

∃x∃y∃z(x ≠ y ∧ y ≠ z ∧ x ≠ z ∧ P(x) ∧ P(y) ∧ P(z) ∧ ∀u(P(u) ⊃ (u = x ∨ u = y ∨ u = z)))

avulla. Yleisemmin predikaattilogiikkaan voidaan liittää kvanttorit Qa siten, että kaava QaxP(x) ilmaisee väitteen ’On olemassa ainakin a olioita x, joille P(x)’, missä a on mikä tahansa ääretön kardinaaliluku. Tällaisia kvanttoreita ja niiden muunnelmia kutsutaan yleistetyiksi kvanttoreiksi.

6) Predikaattilogiikan tärkeimpiin laajennuksiin ovat 1960-luvulta lähtien kuuluneet ns. äärettömät kielet Lκλ (κ, λ äärettömiä kardinaalilukuja). Kielessä Lκλ sallitaan äärettömät konjunktiot ja disjunktiot pituutta < κ; edelleen kvanttorit ∀ ja ∃ voivat sitoa yhdellä kertaa variaabelijonoa, jonka pituus on < λ. Klassinen predikaattilogiikka on tällöin Lωω, jossa ω on pienin ääretön kardinaali eli luonnollisten lukujen nk. numeroituva äärettömyys. Tärkeä erikoistapaus on Lω1ω, jossa sallitaan numeroituvan pitkät konjunktiot ja disjunktiot. Ns. admissiibelit kielet saadaan rajoittamalla kielen Lκλ kaavojen muodostumissääntöjä joukko-opillisten lisäehtojen avulla.

Kieliä, joissa sallitaan numeroituvan pitkät vuorottelevat kvanttorijonot

  1. ∀x

0∃x1∀x2∃x3 . . . A
sanotaan pelikvanttorilogiikoiksi.

Edelleen on tutkittu logiikan järjestelmiä, joissa kvanttorijono kaavan alussa voi olla lineaarisen sijasta osittain järjestetty, esimerkiksi

∀x0∃x1    
   
    A(x0,x1,x2,x3)
   
∀x2∃x3    

Tämän idean yleistyksenä Jaakko Hintikka ja Gabriel Sandu ovat tutkineet ”riippumattomuusystävällistä” eli IF-logiikkaa (engl. independence-friendly logic), jossa voidaan ilmaista kaavan edessä olevien kvanttorien riippuvuutta tai riippumattomuutta toisistaan.

Hintikka on tutkinut Veikko Rantalan kanssa myös äärettömiä formaalikieliä, joiden kaavoissa – toisin kuin kielissä Lκλ – voi olla äärettömän pitkiä sisäkkäisten osakaavojen ketjuja. Tällaisten kielten kaavat esitetään matemaattisesti puiden avulla.
 

 

Intensionaalinen logiikka

Klassisessa logiikassa ja sen yleistyksissä on voimassa ekstensionaalisuuden periaate, jonka mukaan lauseen A totuus tai epätotuus struktuurissa M riippuu vain A:sta ja M:stä. Sen sijaan intensionaalisia operaattoreita ja konnektiiveja sisältävien lauseiden totuusehdoissa täytyy viitata samanaikaisesti useampiin struktuureihin yhtä aikaa. Esimerkkejä intensionaalisista käsitteistä ovat:

(a) aleettiset modalitettit: välttämättä
  mahdollisesti
     
(b) deonttiset modaliteetit: pitäisi olla/tehdä O (obligaatio)
  saa olla/tehdä P (permissio)
     
(c) episteemiset modaliteetit: a tietää, että Ka
  a uskoo, että Ba
     
(d) aikakäsitteet: eilen, menneisyydessä G
  huomenna, tulevaisuudessa F

◻A luetaan ’on välttämätöntä, että A’ ja ◇A luetaan ’on mahdollista, että A’. Vastaavasti KaA luetaan ’a tietää, että A’, ja BaA luetaan ’a uskoo, että A’, missä a viittaa johonkin henkilöön. Aleettisten modaliteettien kohdalla voidaan erottaa toisistaan looginen ja fysikaalinen (kausaalinen) välttämättömyys. Tietäminen ja uskominen ovat esimerkkejä ns. propositionaalisista asenteista, joihin kuuluvat myös mm. muistaminen ja havaitseminen.

Aleettisten modaliteettien tutkimista sanotaan tavallisesti modaalilogiikaksi, deonttisten modaliteettien tutkimista deonttiseksi logiikaksi ja episteemisten modaliteettien tutkimista episteemiseksi logiikaksi. Aikakäsitteiden ominaisuuksia tutkitaan aikalogiikassa (engl. usein tense logic). Muita intensionaalisia logiikan järjestelmiä ovat preferenssilogiikka ja kysymysten logiikka.

Stig Kanger, Hintikka ja Saul Kripke esittivät 1950-luvulla perusideat ns. mahdollisten maailmojen semantiikasta, jonka avulla intensionaalisen logiikan eri lohkoja voidaan käsitellä yhtenäisellä tavalla. Myös intuitionistisen logiikan semantiikkaa voidaan käsitellä tämän saman käsitekehyksen avulla, joten sekin voidaan käsittää eräänlaiseksi intensionaaliseksi logiikaksi.

Olkoon L(S) lausekalkyylin kieli lisättynä yksipaikkaisella konnektiivilla S. Jos A on lause, niin myös SA on lause. Olkoon W joukko struktuureja tai ’mahdollisia maailmoja’ ja olkoon V tulkintafunktio, joka liittää jokaiseen struktuuriin M ∈ W niiden atomilauseiden p joukon, jotka ovat tosia M:ssä. Olkoon RS kaksipaikkainen relaatio joukossa W; tällöin RS on operaattoria S vastaava vaihtoehtorelaatio. Kolmikko F = <W, RS, V> on kehys kielelle L(S). Lauseen SA totuus mahdollisessa maailmassa M ∈ W kehyksen F suhteen, M ⊨F S, määritellään

  1. (92) M ⊨

F SA joss M’ ⊨F A kaikissa maailmoissa M’ ∈ W, joille MRSM’
Jos määritellään uusi operaattori H = ∼S∼, niin ehdosta (92) seuraa

  1. (93) M ⊨

F HA joss M’ ⊨F A jossakin maailmassa M’ ∈ W, jolle MRSM’
Operaattoriksi S voidaan valita looginen välttämättömyys ◻, fysikaalinen välttämättömyys ◻f, pitäminen O, tietäminen Ka tai ’aina tulevaisuudessa’ G; vastaavat H-operaatiot ovat looginen mahdollisuus ◇, fysikaalinen mahdollisuus ◇f, saaminen P, ∼Ka∼, sekä ’joskus tulevaisuudessa’ F. Vastaavia vaihtoehtorelaatioita voidaan luonnehtia seuraavasti: kun M, M’ ∈ W,

  1. MR◻M’
    MR◻

fM’ joss kaikki M:ssä todet lait ovat tosia M’:ssä.
MROM’ joss kaikki lauseet, joiden pitäisi olla totta M:ssä, ovat tosia M’:ssä.
MRKaM’ joss M’ on yhteensopiva sen kanssa, mitä a tietää M:ssä.
MRGM’ joss M’ on asiantila tilan M tulevaisuudessa.
Siten esimerkiksi looginen välttämättömyys ◻A tarkoittaa lauseen A totuutta kaikissa mahdollisissa maailmoissa ja looginen mahdollisuus ◇A lauseen A totuutta jossakin mahdollisessa maailmassa.

Kielen L(S) lause B on validi kehyksien F ∈ F suhteen (eli F-validi), jos kaikille F:n kehyksille F = <W, RS, V> ja kaikille M ∈ W pätee M ⊨F B. Joukko F voidaan valita asettamalla rajoituksia relaation RS ominaisuuksille. Määritellään esimerkiksi joukot F1, F2 ja F3 seuraavien ehtojen avulla:
F1 : RS on refleksiivinen
F2 : RS on refleksiivinen ja transitiivinen
F3 : RS on refleksiivinen, transitiivinen ja symmetrinen.
Relaatio R on refleksiivinen, jos MRM kaikille M; relaatio R on symmetrinen, jos ehdosta MRM’ seuraa M’RM kaikille M ja M’; relaation R transitiivisuus vaatii, että ehdoista MRM’ ja M’RM’’ seuraa MRM’’ kaikille M, M’ ja M’’. Tällöin F1-validien lauseiden joukko muodostaa Robert Feysin 1939 määrittelemän systeemin T, F2-validien lauseiden joukko C. I. Lewisin 1932 esittämän systeemin S4 ja F3-validien lauseiden joukko Lewisin systeemin S5. Näiden systeemien syntaktinen karakterisointi voidaan antaa tarkastelemalla kielen L(S) lauseita:

  1. (94) Sp ⊃ p
    (95) S(p ⊃ q) ⊃ (Sp ⊃ Sq)
    (96) Sp ⊃ SSp
    (97) Hp ⊃ SHp.

Systeemit T, S4 ja S5 voidaan aksiomatisoida lisäämällä tavallisiin lausekalkyylin aksioomiin ja päättelysääntöihin periaate

  1. (N)
A
SA

sekä aksioomaskeemat, jotka vastaavat seuraavassa taulukossa mainittuja lauseita:

systeemi: lisäaksioomat:
T (94), (95)
S4 (94), (95), (96)
S5 (94), (95), (97)

Siten esimerkiksi modaalilogiikassa vaihtoehtorelaation R refleksiivisyys takaa lain ’jos välttämättä p, niin p’ pätevyyden; R:n transitiivisuus takaa lain ’jos välttämättä p, niin välttämättä välttämättä p’; R:n symmetrisyys takaa lain ’jos mahdollisesti p, niin välttämättä mahdollisesti p’.

Systeemissä T voidaan määritellä tiukka (engl. strict) implikaatio ≺:

  1. (98) A ≺ B =

df S(A ⊃ B).
Modaalilogiikassa tiukka implikaatio tarkoittaa, että materiaalinen implikaatio A ⊃ B pätee välttämättä. Muita muunnelmia materiaaliselle implikaatiolle ovat kontrafaktuaalit ja relevanssilogiikka.

Systeemissä T voidaan todistaa mm. seuraavat teoreemat:

  1. (99) p ⊃ Hp
    (100) Sp ⊃ Hp
    (101) S(p ∧ q) ≡ (Sp ∧ Sq)
    (102) H(p ∨ q) ≡ (Hp ∧ Hq)
    (103) (Sp ∨ Sq) ⊃ S(p ∨ q)
    (104) H(p ∧ q) ⊃ (Hp ∧ Hq)
    (105) Sp ≡ ∼H∼p
    (106) S∼p ≡ ∼Hp
    (107) ∼Sp ≡ H∼p
    (108) (p ≺ q) ≡ ∼H(p ∧ ∼q)
    (109) (p ≺ q) ⊃ (Hp ⊃ Hq)
    (110) (∼p ≺ p) ≡ Sp
    (111) (p ≺ ∼p) ≡ S∼p
    (112) Sp ≡ ((q ≺ p) ∧ (∼q ≺ p))

Systeemissä S4 pätee lisäksi

  1. (113) HHp ≡ Hp
    (114) SSp ≡ Sp
    (115) HSHp ⊃ Hp
    (116) SHp ≡ SHSHp
    (117) HSp ≡ HSHSp.

Systeemissä S5 on voimassa myös

  1. (118) Sp ⊃ SSp
    (119) Hp ≡ SHp
    (120) Sp ≡ HSp
    (121) (Sp ≺ Sq) ∨ (Sq ≺ Sp)
    (122) p ⊃ SHp
    (123) HSp ⊃ p.

Tuloksen (118) mukaan systeemi S5 sisältää systeemin S4.

Systeemiä, joka saadaan lisäämällä oletuksiin T aksiooma (122), sanotaan Brouwerin systeemiksi. Jos sääntöä (98) heikennetään niin, että sitä saa soveltaa vain sellaisiin lauseisiin A, jotka ovat tautologioita tavallisen lausekalkyylin perusteella, systeemeistä T, S4 ja S5 saadaan Lewisin systeemit S1, S2 ja S3. Näiden järjestelmien välillä vallitsevat seuraavan kaavion ilmaisemat suhteet:

S5

S4
↙   ↘
T         S3
↘   ↙
S2

S1

Intensionaalisia operaattoreita voidaan liittää myös predikaattilogiikkaan. Muotoa S∀xP(x) olevien kaavojen semanttinen tulkinta ei aiheuta mitään erityisiä ongelmia. Sen sijaan kaavaan ∀xSP(x) liittyy kiistanalaisia filosofisia ongelmia, jotka koskevat yksilöiden identifioimista eri mahdollisissa maailmoissa. Keskustelua tästä aiheesta, joka liittyy nk. de dicto- ja de re –modaliteetteihin, ovat käyneet mm. W. V. O. Quine ja Hintikka.

Niin loogisen kuin fysikaalisen välttämättömyyden logiikkaa pidetään yleensä ainakin systeemin S5 vahvuisena. Hintikan vuonna 1962 esittämä episteemisen logiikan järjestelmä perustuu tiedon osalta systeemiin S4. G. H. von Wrightin vuonna 1951 kehittämä deonttinen logiikka poikkeaa näistä järjestelmistä, sillä pitäminen ei toteuta periaatetta (94), ts. sääntöä Op ⊃ p.

Intensionaalisen logiikan piiriin voidaan lukea myös uskomusten muutoksia tutkiva dynaaminen episteeminen logiikka sekä uskomusjärjestelmien täydentämistä ja korjaamista (engl. belief revision) koskeva teoria.

 

Formaalinen logiikka Suomessa

Filosofian professori Thiodolf Reinin Muodollisen logiikan oppikirja (1882, 5. p. 1936) oli pitkään käytössä oppikirjana Helsingin yliopistossa, mutta nimestään huolimatta se ei käsittele formaalista logiikkaa. Ensimmäiset moderniin logiikkaan liittyvät tutkimukset Suomessa julkaisi Hjalmar Eklund, jonka teos Russells antinomi och andra paradoxala motsägelser – logiska undersökningar (1916) käsitteli Russellin joukko-opillista paradoksia. Turun yliopiston filosofian professorina toimiessaan Eino Kaila (ks. "Kaila, Eino") julkaisi teokset Die Prinzipien der Wahrscheinlichkeitslogik (1926, ”Todennäköisyyslogiikan periaatteet”) ja Probleme der Deduktion (1928, ”Deduktion ongelmia”), jotka osoittavat hänen tutustuneen uuteen logiikkaan, mm. Russellin ja Whiteheadin Principia mathematica -teokseen ja siihen liittyvään matematiikan filosofiaa koskevaan kirjallisuuteen. Kaila, joka oli yhteydessä Wienin piiriin (ks. "Looginen positivismi ja Wienin piiri") ja erityisesti Rudolf Carnapiin, nimitettiin vuonna 1930 Helsingin yliopiston teoreettisen filosofian professoriksi. Hän toi loogisen empirismin tietoteorian ja tieteenfilosofian osaksi akateemisia opintoja ja suosi siinä yhteydessä uuden formaalisen logiikan eli ”logistiikan” opetusta, mikä näkyy Suomen filosofisen yhdistyksen (SFY) vuosikirjan Ajatus numerosta IX (1938) ja teoksesta Inhimillinen tieto (1939).

Kailan oppilaista ehti ensimmäisenä väittelemään logiikan alalta Uuno Saarnio, jonka teos Untersuchungen zur symbolischen Logik (1935, ”Tutkimuksia symbolisesta logiikasta”) arvosteli nominalismia ja kehitteli ”symbolologiaa” ratkaisuna loogisiin antinomioihin. Tämä väitöskirja aloitti SFY:n monografiasarjan Acta Philosophica Fennica. Georg Henrik von Wright keskittyi väitöskirjassaan The Logical Problem of Induction (1941, ”Induktion looginen ongelma”) todennäköisyyden käsitteeseen ja induktion ongelmaan. Oiva Ketonen opiskeli vuonna 1939 Göttingenin yliopistossa todistusteoriaa Gerhard Gentzenin johdolla ja puolusti väitöskirjaansa Untersuchungen zum Prädikatenkalkül (”Tutkimuksia predikaattikalkyylistä”) vuonna 1944. Ketonen paransi merkittävästi Gentzenin sekvenssikalkyyliä osoittamalla, miten sen säännöt voidaan muotoilla niin, että niiden päättelyaskeleet premissien ja johtopäätösten välillä ovat käännettävissä. Ketosen tulokset tulivat maailmalla tunnetuiksi S. C. Kleenen välityksellä. Erik Stenius, joka oli Zürichissä yhteistyössä Hilbertin työtoverin Paul Bernaysin kanssa, väitteli teoksella Das Problem der logischen Antinomien (1949, ”Loogisten antinomioiden ongelma”), jota seurasi vuonna 1952 tutkielma formaalisen aritmetiikan tulkinnasta ja ristiriidattomuudesta.

Cambridgen kaudellaan 1948–1952 Ludwig Wittgensteinin seuraajana von Wright tutki loogisen totuuden ongelmaa, jota hän tarkasteli monadisessa predikaattilogiikassa distributiivisten normaalimuotojen avulla. Von Wrightin oppilas Jaakko Hintikka yleisti väitöskirjassaan Distributive Normal Forms in the Calculus of Predicates (”Distributiiviset normaalimuodot predikaattikalkyylissä”, 1953) nämä normaalimuodot koko ensimmäisen kertaluvun logiikkaan, jossa ne tarjoavat omaperäisen todistusmenetelmän. Kaksi vuotta myöhemmin Hintikka osoitti, että tyyppiteoria voidaan palauttaa toisen kertaluvun logiikkaan. Hän kehitti myös todistusmenetelmän, joka vastaa Bethin taulukkoja ja totuuspuita. 1960-luvulla Hintikka käytti normaalimuotoja, joiden konstituentit edustavat mahdollisten maailmojen täydellisiä kuvauksia, induktiologiikassa ja semanttisen informaation teoriassa. Useat Hintikan oppilaat ovat väitelleet induktiologiikasta: Risto Hilpinen vuonna 1968, Juhani Pietarinen vuonna 1971 ja Ilkka Niiniluoto vuonna 1973. Konstituentit ovat tärkeä väline myös Veikko Rantalan määriteltävyyttä koskevassa väitöskirjassa vuodelta 1973 sekä Hintikan ja Rantalan 1980-luvun yhteisissä töissä äärettömistä kielistä.

Vuodesta 1951 lähtien suomalaisten filosofien keskeiseksi tutkimusalueeksi tuli modaalilogiikka, josta von Wright julkaisi teoksen An Essay in Modal Logic (1951, ”Essee modaalilogiikasta”). Samana vuonna hän julkaisi Mind-lehdessä kirjoituksen ”On Deontic Logic” (”Deonttisesta logiikasta”), josta tuli pitämistä ja saamista käsittelevän deonttisen logiikan perusteksti. Myöhemmin hän kirjoitti normilogiikan ohella mm. teon teoriasta, preferenssilogiikasta ja aikalogiikasta. Von Wrightin aksiomaattinen lähestymistapa modaaliteoriaan oli syntaktinen. Hintikka – riippumatta ruotsalaisen Stig Kangerin samanaikaisesta keksinnöstä – esitti vuonna 1957 perusidean mahdollisten maailmojen semantiikasta. Vuonna 1962 Hintikka julkaisi teoksen Knowledge and Belief (”Tieto ja usko”), joka perusti episteemisen logiikan. Hän yleisti tämän lähestymistavan kaikkiin propositionaalisiin asenteisiin teoksessa Models for Modalities (1969, ”Malleja modaliteeteille”). Tärkeitä tutkimuksia modaalilogiikasta teki myös Åbo Akademissa professorina toiminut ruotsalainen Krister Segerberg. Väitöskirjoja näistä aihepiiristä ovat tehneet Ingmar Pörn vuonna 1968, Esa Saarinen vuonna 1977, Ghita Holmström-Hintikka vuonna 1991 ja Tuomo Aho vuonna 1994.

1970-luvun lopulta lähtien Hintikka on kehittänyt peliteoreettista semantiikkaa, jossa lauseen totuus määritellään voittostrategiana pelissä ”minun” ja ”luonnon” välillä. Hän on soveltanut tätä ideaa sekä luonnollisen kielen semantiikkaan (pronominit, kvanttorit) että uuteen formaalikieleen, IF-logiikkaan (ks. edellä). Toisin kuin Fregen alkuun panemassa predikaattilogiikan perinteessä, IF-logiikassa sallitaan ja voidaan ilmaista kvanttorien välisiä riippuvuus- ja riippumattomuussuhteita. IF-logiikka, jota Hintikka on tutkinut Sandun kanssa, on osoittautunut erittäin ilmaisuvoimaiseksi järjestelmäksi, joka on paljon vahvempi kuin tavallinen ensimmäisen kertaluvun logiikka. Ahti-Veikko Pietarinen on osoittanut, että Peircen kvanttoriteoria ennakoi IF-logiikkaa.

Jan von Plato aloitti todennäköisyysteorian tutkijana, mutta siirtyi sen jälkeen todistusteoriaan. Hänen oppilainaan ovat väitelleet ruotsalaisen Per Martin-Löfin konstruktiivisesta tyyppiteoriasta vaikutteita saaneet Aarne Ranta vuonna 1990 ja Petri Mäenpää vuonna 1993. Yhdessä vaimonsa Sara Negrin kanssa von Plato on julkaissut Gentzenin innoittamia teoksia strukturaalisesta todistusteoriasta.

Formaalinen on logiikka on vuodesta 1973 lähtien saanut jalansijan myös Helsingin yliopiston matematiikan laitoksella, jossa Jouko Väänänen oppilaineen on rakentanut menestyksellisen ohjelman malliteorian, joukko-opin, äärettömien kielten, yleistettyjen kvanttoreiden ja riippuvuuslogiikan tutkimuksessa.

 

Suositeltavaa jatkolukemista

Lause- ja predikaattilogiikka:

Bell, J. L. ja Slomson, A. B. (1969). Models and Ultraproducts. North-Holland, Amsterdam.
- Hyvä malliteorian oppikirja

Boolos, George, John P. Burgess & Richard Jeffrey (2007). Computability and Logic, 5th ed. Cambridge University Press, Cambridge.
- Suosittu oppikirja laskettavuuden teoriasta

Chang, C. C. ja Keisler, H. J. (1973). Model Theory. North-Holland, Amsterdam.
- Kattava kokonaisesitys malliteoriasta

Kleene, S. C. (1967). Mathematical Logic. Wiley, New York. (Dover, 2001.)
- Todistuksia painottava suosittu oppikirja

Mann, Alec, Gabriel Sandu & Merlijn Sevenster (2011). Independence-Friendly Logic: A Game-Theoretical Approach. Cambridge University Press, Cambridge.
- Systemaattinen esitys IF-logiikasta

Mendelson, Elliott (1964). Introduction to Mathematical Logic. Van Nostrand Reinhold, New York. (4th ed., Chapman and Hall, London, 1997.)
- Paljon luettu oppikirja

Monk, J. Donald (1976). Mathematical Logic. Springer, New York.
- Hyvä yleisesitys

Niiniluoto, Ilkka (1973). Matemaattinen logiikka. Limes, Helsinki.
- Matematiikan opiskelijoille tarkoitettu oppikirja

von Plato, Jan & Negri, Sara (2001). Structural Proof Theory. Cambridge University Press, Cambridge.
- Gentzenin innoittama tutkimus todistusteoriasta

Robbin, Joel (1969). Mathematical Logic, a First Course. Benjamin, New York.
- Selkeä oppikirja

Suppes, Patrick (1957). Introduction to Logic. Van Nostrand Reinhold, New York.
- Loogista päättelyä huolella tarkasteleva oppikirja

van Dalen, Dirk (1983). Logic and Structure. 2nd ed., Springer, Berlin.
- Luonnollista päättelyä suosiva esitys

Väänänen, Jouko (1987). Matemaattinen logiikka. Gaudeamus, Helsinki.
- Matemaatikoille tarkoitettu tyylikäs teos

Intensionaalinen logiikka:

Gabbay, Dov & Guenther, Franz (toim.) (1983–1989). Handbook of Philosophical Logic, 1-4. D. Reidel, Dordrecht.
- Laaja katsaus intensionaalisen logiikan järjestelmiin ja kielifilosofisiin sovellutuksiin

Hintikka, Jaakko (1982). Kieli ja mieli. Otava, Helsinki.
- Propositionaalisten asenteiden kielifilosofisia sovellutuksia

Hintikka, Jaakko (2007). Socratic Epistemology: Explorations of Knowledge-Seeking by Questioning. Cambridge University Press, Cambridge.
- Episteemisen logiikan tieto-opillisia sovellutuksia

Hughes, G. E. & M. J. Cresswell (1968). An Introduction to Modal Logic. Methuen, London.
- Klassinen modaalilogiikan oppikirja

Linsky, Leonard (toim.) (1971). Reference and Modality. Oxford University Press, Oxford.
- Filosofiset kiistat kvantifioidusta modaalilogiikasta

Priest, Graham (2008). Introduction to Non-Classical Logic, 2nd ed. Cambridge University Press, Cambridge.
- Parakonsistentin logiikan kehittäjän teos

Rantala, Veikko & Virtanen, Ari (2004). Modaalilogiikka. Gaudeamus, Helsinki.
- Selkeä oppikirja

von Wright, G. H. (1983). Practical Reason. Blackwell, Oxford.
- Deonttisen normilogiikan pohdintaa

 

Kirjallisuus

Barwise, Jon (1975). Admissible Sets and Structures. Springer, Berlin.

Barwise, Jon (toim.) (1977). Handbook of Mathematical Logic. North-Holland, Amsterdam.

Carnap, Rudolf (1942). Introduction to Semantics. Harvard University Press, Cambridge, MA.

Chellas, Brian (1980). Modal Logic: An Introduction. Cambridge University Press, Cambridge.

Church, Alonzo (1956). Introduction to Mathematical Logic. Princeton University Press, Princeton.

Curry, Haskells B. & Feys, Robert (1958). Combinatory Logic, North-Holland, Amsterdam.

Davis, Martin (toim.) (1965). The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions. Raven Press, Hewlett.

Dummett, Michael (1977). Elements of Intuitionism. Clarendon Press, Oxford.

Eklund, Hjalmar (1916). Russells antinomi och andra paradoxala motsägelser: logiska undersökningar. Åbo.

Gärdenfors, Peter (1988). Knowledge in Flux: Modelling the Dynamics of Epistemic States. MIT Press, Cambridge, MA.

Hilbert, David & Ackermann, Wilhelm (1928). Grundzüge der theoretischen Logik. Springer, Berlin.

Hilbert, David & Bernays, Paul (1934 ja 1939). Grundlagen der Mathematik I – II. Springer, Berlin.

Hilpinen, Risto (toim.) (1971). Deontic Logic. D. Reidel, Dordrecht.

Hintikka, Jaakko (1953). Distributive normal forms in the calculus of predicates. Acta philosophica Fennica 6, Helsinki.

Hintikka, Jaakko (1962). Knowledge and Belief. Cornell University Press, Ithaca.

Hintikka, Jaakko (1969). Models for Modalities. D. Reidel, Dordrecht.

Hintikka, Jaakko (1998). The Principles of Mathematics Revisited. Cambridge University Press, Cambridge.

Kaila, Eino (1926). Die Prinzipien der Wahrscheinlichkeitslogik. Turun suomalaisen yliopiston julkaisuja 4, 1, Turku.

Kaila, Eino (1928). Probleme der Deduktion. Turun yliopiston julkaisuja 4, 2, Turku.

Kaila, Eino (1939). Inhimillinen tieto: mitä se on ja mitä se ei ole. Otava, Helsinki.

Ketonen, Oiva (1944). Untersuchungen zum Prädikatenkalkül. Suomalaisen tiedeakatemian toimituksia 23, Helsinki.

Lewis, C. I. & Langford, C. (1932). Symbolic Logic. New York.

Lewis, David (1973). Counterfactuals. Blackwell, Oxford.

Montague, Richard (1974). Formal Philosophy. Yale University Press, New Haven and London.

Niiniluoto, Ilkka (1978). Hakusana “Logiikka”, 3793–3806 teoksessa Huovinen, Pentti & Nurminen, Matti (et. al.) (toim.) 1978. Otavan suuri ensyklopedia. 10, Liennytys - makuaisti. Helsinki, Otava.

Prior, Arthur (1967). Past, Present and Future. Oxford University Press, Oxford.

Rein, Thiodolf (1882/1933). Muodollisen logiikan oppikirja. WSOY, Porvoo-Helsinki.

Rescher, N. & Urquhart, A. (1971). Temporal Logic. Springer, Berlin.

Saarnio, Uuno (1935). Untersuchungen zur symbolischen Logik. 1, Kritik der Nominalismus und Grundlegung der logistischen Zeichentheorie (Symbolologie). Acta philosophica Fennica 1, Helsinki.

Stenius, Erik (1941). Das Problem der logischen Antinomien. Commentationes physico-mathematicae / Societas scientiarum Fennica 14,6, Helsinki.

Tarski, Alfred (1956). Logic, Semantics, Metamathematics: Papers from 1923 to 1938. Clarendon Press, Oxford.

Tarski, Alfred; Abdrzej Mostowski & Arthur Robinson (1953). Undecidable Theories, North-Holland, Amsterdam.

van Ditmarsch, Hans, Wiebe van der Hoek & Barteld Kooi (2007). Dynamic Epistemic Logic. Springer, Dordrecht.

Whitehead, Alfred N. & Russell, Bertrand (1910). Principia Mathematica. Cambridge University Press, Cambridge. (Paperback, 1962.)

von Wright, G. H. (1941). The Logical Problem of iIduction. Acta philosophica Fennica 3, Helsinki.

von Wright, G. H. (1951). An Essay in Modal Logic. North-Holland, Amsterdam.

von Wright, G. H. (1951). “Deontic Logic”. Mind, Vol. 60, 1–15.

 

Internet-lähteitä

Internet Encyclopedia of Philosophy
- Logic (useita artikkeleita)

Stanford Encyclopedia of Philosophy
- classical logic, second-order and higher-order logic, logic and ontology
- deontic logic, epistemic logic, fuzzy logic, intensional logic, intuitionistic logic, logic and games, relevance logic, temporal logic

 

Yläartikkeli: 
Logiikka