02 - Elsőrendű logika - szemantika

previously on Heroes
Ítéletkalkulusban ha volt egy formulánk, könnyedén kiértékelhettük: csak adnunk kellett egy változó-értékadást, ami a változóknak beállította az értékét 0-ra vagy 1-re, és ezeket az értékeket alulról felfelé terjesztettük, a végén megkapva az egész formula értékét.

Az alulról felfelé értékelés továbbra is megmarad, de a "változóértékadás" helyett egy sokkal komplexebb dolgot kell megadjunk, ha formulát akarunk kiértékelni: egy struktúrát. ami egy

$\mathcal{A}~=~(A,I,\varphi)$

hármas. (Ez csak annyit jelent, hogy három dolgot kell megadjunk, az elsőnek a neve $A$ lesz, a másodiké $I$, a harmadiké $\varphi$, mindjárt mondom, hogy minek mi a "típusa" és ezt a hármat együtt elnevezhetjük $\mathcal{A}$-nak is. Általában egy struktúrát nagy "írott" betűvel jelölünk, az első komponensét ugyanannak a betűnek a sima nagybetűs változatával.)

Egy ilyen hármasban

$A$ egy nemüres halmaz, az objektumok halmaza, hívják alaphalmaznak vagy univerzumnak is. (őket veszik majd fel értékül a termek.) $\varphi$ a változóknak egy "default" értékadása, azaz egy olyan függvény, ami minden $x$ változóhoz egy $\varphi(x)\in A$ objektumot rendel. $I$ pedig az interpretációs függvény, ami a függvény- és predikátumjeleknek ad "jelentést": az $f$ függvényjelhez az $I(f)$-fel jelölt függvényt, a $p$ predikátumjelhez az $I(p)$-vel jelölt predikátumot rendeli. Konkrétan: ha $f/n$ egy ($n$-változós) függvényjel, akkor $I(f)$ egy $A^n\to A$ függvény ha $p/n$ egy ($n$-változós) predikátumjel, akkor $I(p)$ egy $A^n\to\{0,1\}$ predikátum. itt van egy megkötés: ha van $=/2$ predikátumjel, akkor $I(=)$ mindenképp tényleg az egyenlőség predikátum kell legyen.

Például ha a függvényjeleink $f/1$, $g/2$ és $c/0$, predikátumjeleink pedig $p/1$ és $q/2$, akkor egy struktúra lehet pl. az az $\mathcal{A}=(A,I,\varphi)$, ahol $A=\mathbb{N}_0=\{0,1,2,\ldots\}$ a természetes számok ($0$-t is tartalmazó) halmaza; $\varphi(x)=2$, $\varphi(y)=3$, $\varphi(z)=7$, \ldots (nem adom meg az egészet, de mind a végtelen sok változónak van valami alap értéke) az $I$ interpretációs függvényünk pedig $f$-hez egy $\mathbb{N}_0\to\mathbb{N}_0$ függvényt, $g$-hez egy $\mathbb{N_0}^2\to\mathbb{N_0}$ függvényt, $c$-hez egy $\to\mathbb{N}_0$ függvényt, azaz egy $\mathbb{N}_0$-beli értéket kell rendeljen, $p$-hez egy egyváltozós $\mathbb{N}_0\to\{0,1\}$ predikátumot, $q$-hoz pedig egy $\mathbb{N}_0\times\mathbb{N}_0\to\{0,1\}$ predikátumot. Akár így:  $\begin{align*}I(f)(n)&:=n+1&&\hbox{tehát $f$ az ,,adj hozzá egyet'' függvény}\\I(g)(n,m)&:=n+2m&&\hbox{why not, függvény ez is}\\I(c)&=7&&\hbox{konstans, egy eleme az alaphalmaznak}\\I(p)(n)=1&\Leftrightarrow n\hbox{ prímszám}&&\hbox{predikátumról azt adjuk meg pl, hogy mikor igaz}\\I(q)(n,m)=1&\Leftrightarrow n<m\end{align*}$

(note to self: a $\LaTeX$ben lévő text fonttal kezdenem kell valamit.)

Egy ilyen struktúra már elegendő információt szolgáltat ahhoz, hogy minden termnek legyen egy értéke benne és minden formulának is (bár ezt az értéket nem biztos, hogy ki is lehet számítani!). Kezdjük a termekkel, hiszen alulról kifelé akarunk kiértékelni és a termek vannak "belül". Ez lesz az egyszerűbb is, hiszen a termeknek összesen két konstruktora volt:

Ha $t$ egy term és $\mathcal{A}=(A,I,\varphi)$ egy struktúra, akkor $t$ értéke $\mathcal{A}$-ban egy $A$-beli objektum lesz, amit $\mathcal{A}(t)$-vel jelölünk (tehát mintha a termet behelyettesítenénk $\mathcal{A}$-be, mint függvénybe) és felépítés szerinti indukcióval definiálunk (ami még mindig annyit jelent, hogy minden képzési szabályra felírunk egy "ha a termet így építettük fel, akkor ez legyen az értéke, ha úgy, akkor az" szabályt úgy, hogy használhatjuk a "kisebb" termek értékét is. Mégpedig így:

ha a $t$ term egy $x$ változó, akkor $\mathcal{A}(t)~:=~\varphi(x)$ azaz: a változók értékét $\varphi$ mondja meg ha pedig a $t$ term egy $f(t_1,\ldots,t_n)$ alakú összetett term, akkor $\mathcal{A}(t)~:=~I(f)(\mathcal{A}(t_1),\ldots,\mathcal{A}(t_n))$. azaz: ha egy összetett termet kell kiértékelnünk, akkor rekurzívan értékeljük ki az "argumentumait", majd ezt a kapott $n$ objektumot helyettesítsük be abba a függvénybe, amit $\mathcal{A}$-ban jelöl a term gyökérszimbóluma (a képen ez az $f$, ami jelöli az $I(f)$ függvényt).

és ez minden, mert ez a két konstruktorunk volt.

Például az előző struktúrában a természetes számok fölött: $\mathcal{A}(x)=\varphi(x)=2$, ez volt $x$ alapértéke a példa struktúra $\varphi$-jében $\mathcal{A}(f(x))=I(f)(\mathcal{A}(x))=I(f)(2)=2+1=3$, mert az $f$ ebben a struktúrában az "adj hozzá $1$-et" függvény volt, az argumentum értéke pedig $2$ $\mathcal{A}(g(f(x),y))=I(g)(3,3)=3+2\cdot 3=9$, mert $g$ volt az "add össze az első argumentumot és a második dupláját" függvény, az első argumentumának az értéke $3$, a másodiké pedig $\varphi(y)=3$ szintén

A formulák kiértékelése eggyel komplikáltabb és kell hozzá még egy jelölés, mert a kvantorok megváltoztatják a változók értékét (ha informatikusul akarjuk elképzelni, akkor kb "végighúznak egy ciklust a változó összes lehetséges értékével"):

Ha $\mathcal{A}=(A,I,\varphi)$ egy struktúra, $x$ egy változó, $a\in A$ pedig egy objektum, akkor $\mathcal{A}_{[x\mapsto a]}$ azt a struktúrát jelöli, ami összesen annyiban tér el $\mathcal{A}$-tól, hogy benne $x$ default értéke $a$, minden más ugyanaz. Vagyis: $\mathcal{A}_{[x\mapsto a]}=(A,I,\varphi')$, tehát ugyanaz marad az objektumok halmaza és minden függvény- és predikátumjel is ugyanazt jelenti, csak a változók default értékadása változik $\varphi'$-vé, ahol  $\varphi'(x)=a$ (erre változott) és minden másik $y\neq x$-re $\varphi'(y)=\varphi(y)$ (a többi változó értéke nem változik).

Most, hogy ez a jelünk megvan, definiálhatunk: ha $F$ egy formula és $\mathcal{A}$ egy struktúra, akkor $F$ értéke $\mathcal{A}$-ban egy $\{0,1\}$-beli igazságérték lesz, amit $\mathcal{A}(F)$-fel jelölünk és $F$ felépítése szerinti indukcióval definiálunk. Csak most sok eset van, mert formulákat szintaktikailag is sokféleképp építhettünk fel. Mégpedig:

Ha $F=p(t_1,\ldots,t_n)$, akkor $\mathcal{A}(F)~:=~I(p)(\mathcal{A}(t_1),\ldots,\mathcal{A}(t_n)).$ azaz: ha atomi formulát kell kiértékelnünk, akkor először is kiértékeljük benne a termeket, aztán megnézzük, hogy milyen predikátumot jelöl ebben a struktúrában a gyökérszimbólum (ami itt most $p$), és ebbe a predikátumba behelyettesítjük az $n$ darab termünk értékeit a megfelelő sorrendben. Ha $F=\uparrow$, akkor $\mathcal{A}(F)~:=~1$ (az $\uparrow$ formula igaz, ok) Ha $F=\downarrow$, akkor $\mathcal{A}(F)~:=~0$ (a $\downarrow$ formula hamis, ok) Ha $F=(\neg G)$, akkor $\mathcal{A}(F)~:=~\neg\mathcal{A}(G)$ (ha egy $\neg G$ alakú formulát kell kiértékelnünk, akkor értékeljük ki a $G$-t és negáljuk az eredményt, ok) Ha $F=(G\vee H)$, akkor $\mathcal{A}(F)~:=~\mathcal{A}(G)\vee\mathcal{A}(H)$ (ha egy vagyolást, akkor értékeljük ki a két közvetlen részformulát és vagyoljuk az eredményeket) Ha $F=(G\wedge H)$, akkor $\mathcal{A}(F)~:=~\mathcal{A}(G)\wedge\mathcal{A}(H)$ (éselésre ugyanez) Ha $F=(G\to H)$, akkor $\mathcal{A}(F)~:=~\mathcal{A}(G)\to\mathcal{A}(H)$ (implikációra ugyanez) Ha $F=(G\leftrightarrow H)$, akkor $\mathcal{A}(F)~:=~\mathcal{A}(G)\leftrightarrow\mathcal{A}(H)$ (duplanyílra ugyanez, eddig semmi meglepetés nem történt) Ha $F=\exists xG$, akkor $\mathcal{A}(F):=\begin{cases}1&\hbox{ha van olyan }a\in A\hbox{, melyre }\mathcal{A}_{[x\mapsto a]}(G)=1\\0&\hbox{ha nincs}\end{cases}$ azaz: mintha végigmennénk egy "ciklussal" az $x$ összes lehetséges értékén, és ha találunk egyet is, melyre beállítva $x$-et a formula "magja" igaz lesz, akkor ez a formula is igaz, ha meg mindenre hamis lesz, akkor hamis. Ha $F=\forall xG$, akkor $\mathcal{A}(F):=\begin{cases}1&\hbox{ha minden }a\in A\hbox{-ra }\mathcal{A}_{[x\mapsto a]}(G)=1\\0&\hbox{ha nem}\end{cases}$ azaz: mintha végigmennénk egy "ciklussal" az $x$ összes lehetséges értékén, és ha találunk egyet is, melyre beállítva $x$-et a formula "magja" hamis lesz, akkor ez a formula is hamis ha meg mindenre igaz lesz, akkor igaz.

Például ebben az előző struktúrában $\mathcal{A}(p(f(x)))=I(p)(\mathcal{A}(f(x)))=I(p)(3)=1$, mert $I(p)(n)$ akkor volt $1$, ha $n$ prímszám és a $3$ egy prímszám. $\mathcal{A}(\forall xp(f(x)))$ akkor igaz, ha minden $a\in\mathbb{N}_0$-ra $\mathcal{A}_{[x\mapsto a]}(p(f(x))=1$. De mivel pl. az $a=3$-ra $\mathcal{A}_{[x\mapsto 3]}(p(f(x)))=I(p)(I(f)(3))=I(p)(4)=0$, mert ebben a struktúrában $x$ értéke $3$, $3+1$ az $4$ és a $4$ nem prímszám, ezért van olyan $a$, melyre a mag hamis lesz, ha erre állítjuk $x$ értékét, ezért $\mathcal{A}(\forall x p(f(x)))=0$.

A következő posztban majd látjuk, hogy ez azért nem megy mindig ilyen könnyen.
A kapcsolódó gyakanyag a hetedik, érdemes hozzáolvasni.

folytköv