Predikaattilogiikka

Wikipedia

Predikaattilogiikka on logiikan osa-alue, jolla tutkitaan tietynlaisia formaalikieliä. 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 kielen subjekti-predikaattimuodon lauseita, loogisia operaatioita näillä lauseilla sekä näiden lauseiden yleistyksiä. Mallintaminen voi olla kiinnostavaa esimerkiksi matemaattisista, filosofisista tai kielitieteellisistä syistä. Esimerkkinä muutama predikaattilogiikan lause ja vastine luonnollisessa kielessä.

1. Pii on positiivinen

$P \pi \!$

2. Jos pii on negativinen, niin kuu on juustoa

$\neg P \pi \to Jk$

3. Kaikki ihmiset ovat kuolevaisia

$\forall x (Ix \to Kx)$

Tarkempi kuvaus predikaattilogiikan kielestä löytyy alakohdasta syntaksi.

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.

Sisällysluettelo

1 Syntaksi
2 Semantiikka
3 Eheys- ja täydellisyyslauseet
4 Predikaattilogiikan laajennuksia
- 4.1 Kirjallisuutta

[muokkaa] Syntaksi

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

[muokkaa] Aakkosto

Määritelmä. Predikaattilogiikan aakkosto koostuu seuraavista symboleista:

Merkitys	Merkintä
konnektiivit	$\neg,\wedge,\vee,\to,\leftrightarrow \,\!$
sulkeet	$(,) \,\!$
kvanttorit	$\forall,\exists \,\!$
identiteettisymboli	$\equiv \,\!$
relaatiosymbolit	$R_0,R_1,R_2,\ldots \,\!$
funktiosymbolit	$f_0,f_1,f_2,\ldots \,\!$
muuttujat	$v_0,v_1,v_2,\ldots\,\!$
yksilövakiot	$c_0,c_1,c_2,\ldots \,\!$

Predikaattilogiikassa merkitään lisäksi kaavamuuttujia symboleilla $\phi,\psi,\ldots\,\!$ , tai symboleilla A, B, ... .

[muokkaa] Kaavat

Määritelmä. Predikaattilogiikan termit

Yksilövakiot ovat termejä.
Muuttujat ovat termejä.
Jos $t_1,\ldots,t_n\,\!$ ovat termejä, niin $ft_1\ldots{}t_n\,\!$ on termi.

Määritelmä. Predikaattilogiikan kaavat
Olkoot $t_1,t_2,\ldots\,\!$ termejä.

$t_1 = t_2\,\!$ on kaava.
Jos $R_i\,\!$ on n-paikkainen predikaattisymboli, niin $R_i{}t_1\ldots{}t_n\,\!$ on kaava.
Jos $\phi\,\!$ on kaava, niin $\neg\phi\,\!$ on kaava.
Jos $\phi\,\!$ ja $\psi\,\!$ ovat kaavoja, niin ...
...

[muokkaa] Päättely

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.

[muokkaa] Luonnollinen päättely

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 eliminontisäännöt kaikille konnektiiveille:

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

$\frac{A \and \neg A}{\neg B} \ \neg T \ (* \qquad \frac{ \neg \neg A}{A} \ \neg E$

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

$\frac{\begin{matrix} A & B \end{matrix}}{A \and B}\ \and T \qquad \frac{A \and B}{A}\ \and E$

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

$\frac{A}{\forall x A}\ \forall T\ (** \qquad \frac{\forall x A}{A( x / t)}\ \forall E$

Huomautuksia: *) Jos B on hylkäämätön oletus, se voidaan hylätä. **) Muuttuja x ei saa olla kaavan A todistuksen hylkäämätön oletus.

[muokkaa] Todistusteoria

Todistusteoria keskittyy lauseen syntaktiseen todistettavuuteen (eli johdettavuuteen tai päättelyyn) toisista lauseista tiettyjen sääntöjen mukaisesti. Totuuden käsite on syntaktisen todistuksen suhteen merkityksetö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 on totuuden säilyttävää ja siis tosista lauseista voidaan todistaa vain tosia lauseita, mutta se on eri asia. Syntaktisen todistuksen tarkoituksena on ainoastaan johtaa jo saaduista lauseista, viime kädessä aksioomista uusia lauseita.

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

Ks. myös Genzenin luonnollisen päättelyn systeemi.

[muokkaa] Semantiikka

Malliteoriassa tarkastellaan kieltä semanttisesta näkökulmasta. Malli on joukko-opillinen struktuuri, joka toimii logiikan kaavojen tulkintana Tarskin totuusmääritelmän mukaisesti.

Tarskin totuusmääritelmä. Olkoon $L$ aakkosto ja $\phi \, L$ -kaava. Olkoon $\mathcal{M} \, L$ -struktuuri ja $s$ sen tulkintajono, ts. $s\colon \mathbb{N} \rightarrow \mathcal{M}$ . Tällöin kaavan $φ$ totuus mallissa $\mathcal{M}$ tulkintajonolla $s$ , merk. $\mathcal{M},s\models\phi$ , määritellään seuraavasti:

$\phi = P(t_0, \ldots , t_n) : \, (t_0^{\mathcal{M},s}, \ldots , t_n^{\mathcal{M},s})\in P^{\mathcal{M}},$
$\phi = \neg \psi : \, \mathcal{M},s\not\models \psi,$
$\phi = \psi \rightarrow \theta : \, \mathcal{M},s\not\models \psi$ tai $\mathcal{M},s\models \theta ,$
$\phi = \forall v_i \psi : \, \mathcal{M},s(a/i)\models \psi$ kaikilla $a\in\mathcal{M}$ .

Jos $\Sigma\,\!$ on joukko $L$ -kaavoja ja $\mathcal{M},s\models \phi$ kaikilla $\phi\in\Sigma$ , niin merkitään $\mathcal{M},s\models\Sigma$ .

Malliteoriassa todistukselle rinnakkainen käsite on looginen seuraaminen. Jos kaikille niille malleille $\mathcal{M}\,\!$ ja tulkintajonoille $s\,\!$ , joille pätee $\mathcal{M}\models_s\Sigma\,\!$ , pätee myös $\mathcal{M}\models_s\phi\,\!$ , sanotaan kaavan $\phi\,\!$ seuraavan loogisesti kaavajoukosta $\Sigma\,\!$ . Tämä merkitään $\Sigma\models\phi\,\!$ .

Malliteorian tärkeä nimi: Alfred Tarski.

[muokkaa] Eheys- ja täydellisyyslauseet

Logiikassa pyritään eheään ja täydelliseen aksiomaattiseen järjestelmään. Eheydellä tarkoitetaan sitä, että tosista lauseista tietyn päättelysysteemin nojalla päätellyt lauseet ovat nekin tosia. Täydellisyydellä taas tarkoitetaan sitä, että kaikki ne lauseet, jotka ovat 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 todisti ensimmäisenä Kurt Gödel vuonna 1930.

[muokkaa] Predikaattilogiikan laajennuksia

Yleistetyt kvanttorit
Äärettömät kielet
Toisen kertaluvun predikaattilogiikka

[muokkaa] Kirjallisuutta

Allwood, Jens, Lars-Gunnar Andersson & Östen Dahl (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

Haettu osoitteesta http://fi.wikipedia.org../../../p/r/e/Predikaattilogiikka.html

Luokka: Logiikka

We provide Linux to the World