Movatterモバイル変換

[0]ホーム
URL:

Siirry sisältöön
Wikipedia
Haku

Predikaattilogiikka

Wikipediasta

Predikaattilogiikka onsymbolisen logiikan osa-alue, jolla tutkitaan tietynlaisiaformaalikieliä.[1] Predikaattilogiikka jakautuu ensimmäisen kertaluvun predikaattilogiikkaan ja korkeampien kertalukujen predikaattilogiikoihin. Jälkimmäisten kohdalta mielenkiinto kohdistuu yleensä vain toisen kertaluvun predikaattilogiikkaan.

Ensimmäisen kertaluvun predikaattilogiikka, joskus lyhyemmin pelkästään predikaattilogiikka, tutkii kieliä, jotka mallintavat luonnollisen kielensubjekti-predikaattimuodon lauseita,loogisia operaatioita näillä lauseilla sekä näiden lauseiden yleistyksiä. Mallintaminen voi olla kiinnostavaa esimerkiksimatemaattisista,filosofisista taikielitieteellisistä syistä. Esimerkkinä muutama predikaattilogiikan lause ja vastine luonnollisessa kielessä.

1. Pii on positiivinen

Pπ{\displaystyle P\pi \!}

2. Jos pii on ei-positiivinen, niin kuu on juustoa

¬Pπ→Jk{\displaystyle \neg P\pi \to Jk}

3. Kaikki ihmiset ovat kuolevaisia

∀x(Ix→Kx){\displaystyle \forall x(Ix\to Kx)}

Tarkempi kuvaus predikaattilogiikan kielestä löytyy alakohdastasyntaksi.

Toisen kertaluvun predikaattilogiikka ja korkeampien kertalukujen predikaattilogiikat eroavat ensimmäisen kertaluvun predikaattilogiikasta siinä, että jälkimmäisissä voidaan puhua olioiden ominaisuuksista (2. kl.), olioiden ominaisuuksien ominaisuuksista (3. kl.) ja niin edelleen.

Syntaksi

[muokkaa |muokkaa wikitekstiä]

Syntaksi on se osa predikaattilogiikkaa, jossa kiinnostuksen kohteena ovat vain merkkijonot ja niiden ominaisuudet (ks. myöskalkyyli). Pelkästään syntaktisten piirteiden perusteella voidaan määritellä millaisia lauseet ovat ja millaista on pätevä päättely predikaattilogiikassa.

Aakkosto

[muokkaa |muokkaa wikitekstiä]

Määritelmä. Predikaattilogiikanaakkosto koostuu seuraavistasymboleista:

MerkitysMerkintä
konnektiivit¬,∧,∨,→,↔{\displaystyle \neg ,\wedge ,\vee ,\to ,\leftrightarrow \,\!}
sulkeet(,){\displaystyle (,)\,\!}
kvanttorit∀,∃{\displaystyle \forall ,\exists \,\!}
identiteettisymboli≡{\displaystyle \equiv \,\!}
relaatiosymbolitR0,R1,R2,…{\displaystyle R_{0},R_{1},R_{2},\ldots \,\!}
funktiosymbolitf0,f1,f2,…{\displaystyle f_{0},f_{1},f_{2},\ldots \,\!}
muuttujatv0,v1,v2,…{\displaystyle v_{0},v_{1},v_{2},\ldots \,\!}
yksilövakiotc0,c1,c2,…{\displaystyle c_{0},c_{1},c_{2},\ldots \,\!}

Predikaattilogiikassa merkitään lisäksi kaavamuuttujia symboleillaϕ,ψ,…{\displaystyle \phi ,\psi ,\ldots \,\!}, tai symboleillaA,B, ... .

Kaavat

[muokkaa |muokkaa wikitekstiä]

Määritelmä. Predikaattilogiikan termit

  1. Yksilövakiot ovat termejä.
  2. Muuttujat ovat termejä.
  3. Jost1,…,tn{\displaystyle t_{1},\ldots ,t_{n}\,\!} ovat termejä, niinft1…tn{\displaystyle ft_{1}\ldots {}t_{n}\,\!} on termi.

Määritelmä. Predikaattilogiikan kaavat
Olkoott1,t2,…{\displaystyle t_{1},t_{2},\ldots \,\!}termejä.

  1. t1=t2{\displaystyle t_{1}=t_{2}\,\!} on kaava.
  2. JosRi{\displaystyle R_{i}\,\!} on n-paikkainen predikaattisymboli, niinRit1…tn{\displaystyle R_{i}{}t_{1}\ldots {}t_{n}\,\!} on kaava.
  3. Josϕ{\displaystyle \phi \,\!} on kaava, niin¬ϕ{\displaystyle \neg \phi \,\!} on kaava.
  4. Josϕ{\displaystyle \phi \,\!} jaψ{\displaystyle \psi \,\!} ovat kaavoja, niin ...
  5. ...

Päättely

[muokkaa |muokkaa wikitekstiä]

Nyt voidaan esittää, millaista on pätevä päättely predikaattilogiikassa. Ajatuksena on, että kun tunnemme konnektiivit, tunnemme lauseiden deduktiiviset seuraukset.

Aikojen kuluessa on esitetty useita toisistaan hiukan poikkeavia päättelysysteemejä. Ehkä helpoimmin ymmärrettävissä on nk. luonnollisen päättelyn systeemi predikaattilogiikalle.

Luonnollinen päättely

[muokkaa |muokkaa wikitekstiä]

Luonnollisen päättelyn systeemissä päättelyn premissit kirjoitetaan viivan päälle, johtopäätös viivan alle. Päättelyjä voi yhdistää toisiinsa kirjoittamalla niitä peräkkäin. Luonnollisen päättelyn päättelysäännöt vastaavat tuonti- ja eliminointisäännöt kaikille konnektiiveille:

1. Negaation tuonti- ja eliminointisäännöt.

A∧¬A¬B ¬T (∗¬¬AA ¬E{\displaystyle {\frac {A\land \neg A}{\neg B}}\ \neg T\ (*\qquad {\frac {\neg \neg A}{A}}\ \neg E}

2. Konjunktion tuonti- ja eliminointisäännöt.

ABA∧B ∧TA∧BA ∧E{\displaystyle {\frac {\begin{matrix}A&B\end{matrix}}{A\land B}}\ \land T\qquad {\frac {A\land B}{A}}\ \land E}

3. Kaikilla-kvanttorin tuonti- ja eliminointisäännöt.

A∀xA ∀T (∗∗∀xAA(x/t) ∀E{\displaystyle {\frac {A}{\forall xA}}\ \forall T\ (**\qquad {\frac {\forall xA}{A(x/t)}}\ \forall E}

Huomautuksia: *) JosB on hylkäämätön oletus, se voidaan hylätä. **) Muuttujax ei saa esiintyä vapaana missään kaavanA todistuksen hylkäämättömässä oletuksessa.

Todistusteoria

[muokkaa |muokkaa wikitekstiä]

Todistusteoria keskittyy lauseen syntaktiseentodistettavuuteen (elijohdettavuuteen tai päättelyyn) toisista lauseista tiettyjen sääntöjenmukaisesti. Totuuden käsite on syntaktisen todistuksen suhteenmerkityksetön. Tulkinta on totuuden välttämätön edellytys eikätodistettavien lauseiden ei tarvitse olla tulkittuja.

On tietenkin mielekästä, jos todistus on määritelty siten, että se ontotuuden säilyttävää ja siis tosista lauseista voidaan todistaa vaintosia lauseita, mutta se on eri asia. Syntaktisen todistuksentarkoituksena on ainoastaan johtaa jo saaduista lauseista, viime kädessäaksioomista uusia lauseita.

Todistusteorian tärkeitä nimiä:Gerhard Gentzen,David Hilbert.

Ks. myös Gentzeninluonnollisen päättelyn systeemi.

Semantiikka

[muokkaa |muokkaa wikitekstiä]

Malliteoriassa tarkastellaan kieltäsemanttisesta näkökulmasta. Malli onjoukko-opillinen struktuuri, joka toimii logiikankaavojen tulkintanaTarskin totuusmääritelmän mukaisesti.

Tarskin totuusmääritelmä. OlkoonL{\displaystyle L} aakkosto jaϕL{\displaystyle \phi \,L}-kaava. OlkoonML{\displaystyle {\mathcal {M}}\,L}-struktuuri jas{\displaystyle s} sen tulkintajono, ts.s:N→M{\displaystyle s\colon \mathbb {N} \rightarrow {\mathcal {M}}}. Tällöin kaavanϕ{\displaystyle \phi } totuus mallissaM{\displaystyle {\mathcal {M}}}tulkintajonollas{\displaystyle s}, merk.M,s⊨ϕ{\displaystyle {\mathcal {M}},s\models \phi }, määritellään seuraavasti:

  1. ϕ=P(t0,…,tn):(t0M,s,…,tnM,s)∈PM,{\displaystyle \phi =P(t_{0},\ldots ,t_{n}):\,(t_{0}^{{\mathcal {M}},s},\ldots ,t_{n}^{{\mathcal {M}},s})\in P^{\mathcal {M}},}
  2. ϕ=¬ψ:M,s⊭ψ,{\displaystyle \phi =\neg \psi :\,{\mathcal {M}},s\not \models \psi ,}
  3. ϕ=ψ→θ:M,s⊭ψ{\displaystyle \phi =\psi \rightarrow \theta :\,{\mathcal {M}},s\not \models \psi } taiM,s⊨θ,{\displaystyle {\mathcal {M}},s\models \theta ,}
  4. ϕ=∀viψ:M,s(a/i)⊨ψ{\displaystyle \phi =\forall v_{i}\psi :\,{\mathcal {M}},s(a/i)\models \psi } kaikillaa∈M{\displaystyle a\in {\mathcal {M}}}.

JosΣ{\displaystyle \Sigma \,\!}on joukkoL{\displaystyle L}-kaavoja jaM,s⊨ϕ{\displaystyle {\mathcal {M}},s\models \phi } kaikillaϕ∈Σ{\displaystyle \phi \in \Sigma }, niin merkitäänM,s⊨Σ{\displaystyle {\mathcal {M}},s\models \Sigma }.

Malliteoriassa todistukselle rinnakkainen käsite onlooginenseuraaminen.Jos kaikille niille malleilleM{\displaystyle {\mathcal {M}}\,\!}ja tulkintajonoilles{\displaystyle s\,\!},joille päteeM⊨sΣ{\displaystyle {\mathcal {M}}\models _{s}\Sigma \,\!},pätee myösM⊨sϕ{\displaystyle {\mathcal {M}}\models _{s}\phi \,\!},sanotaan kaavanϕ{\displaystyle \phi \,\!}seuraavan loogisesti kaavajoukostaΣ{\displaystyle \Sigma \,\!}.Tämä merkitäänΣ⊨ϕ{\displaystyle \Sigma \models \phi \,\!}.

Malliteorian tärkeä nimi:Alfred Tarski.

Eheys- ja täydellisyyslauseet

[muokkaa |muokkaa wikitekstiä]

Logiikassa pyritään eheään ja täydelliseen aksiomaattiseenjärjestelmään. Eheydellä tarkoitetaan sitä, että tosista lauseista tietynpäättelysysteemin nojalla päätellyt lauseet ovat nekin tosia.Täydellisyydellä taas tarkoitetaan sitä, että kaikki ne lauseet, jotkaovat aina tosia tiettyjen lauseiden ollessa tosia, ovat jälkimmäisistäpääteltävissä. Jos tietty logiikan järjestelmä on sekä eheä ettätäydellinen, vastaavat todistusteoria ja malliteoria toisiaan tässäjärjestelmässä.

Ensimmäisen kertaluvun predikaattilogiikan täydellisyyslauseen todistiensimmäisenäKurt Gödel vuonna 1930.

Predikaattilogiikan laajennuksia

[muokkaa |muokkaa wikitekstiä]

Predikaattilogiikka ja ohjelmointi

[muokkaa |muokkaa wikitekstiä]

Logiikkapohjainen ohjelmointi onohjelmointiparadigma, jossa predikaattilogiikalla on keskeinen rooli. Logiikkaohjelmoinnin tärkein kieli onProlog.

Lähteet

[muokkaa |muokkaa wikitekstiä]
  1. ↑Thompson, Jan & Martinsson, Thomas: Matematiikan käsikirja, s. 321. 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
  • Allwood, Jens & Andersson, Lars-Gunnar & Dahl, Östen (1988):Logiikka ja kieli. 2. painos. Suomentanut Paavo Siro. Helsinki: Yliopistopaino. (1. painos 1980 Gaudeamuksen kustantamana. Alkuteos: Logik för lingvister, 1972. Suomennettu englanninkielisestä laitoksesta Logic in Linguistics, 1979.)ISBN 951-570-020-5
Noudettu kohteesta ”https://fi.wikipedia.org/w/index.php?title=Predikaattilogiikka&oldid=23070614”
Luokka:
Piilotettu luokka:
[8]ページ先頭
©2009-2025 Movatter.jp