Dualitás (logika)

A logikában azt a jelenséget hívjuk dualitásnak, amikor egy logikai konstans igazságfeltételeit megadva, egy új konstans igazságfeltételeit kaphatjuk, ha az első meghatározásban az igaz szó előfordulásait átcseréljük a hamis szóra. Ez az általános törvényszerűség megfigyelhető mind a kijelentéslogikában (más néven proporcinális vagy nullad rendű logikában), mind az elsőrendű logikában (más néven predikátumlogika) mind pedig a különféle modális logikákban.

Dualitás a kijelentéslogikában

A kijelentéslogikában logikai konstansként csak a logikai konnektívumok viselkednek, ezért értelemszerűen ezek igazságfeltételes definícióit vizsgálhatjuk a dualitás szempontjából.

Konjunkció és alternáció

A nullad rendű logikában a konjunkciót ($\scriptstyle {A\wedge B}$) a következő módon adjuk meg:

$\scriptstyle {A\wedge B}$ akkor és csak akkor igaz, ha mindkét tagja igaz.

Ha a bevezetőben írt cserét végrehajtjuk, akkor a következőt kapjuk:

… akkor és csak akkor hamis, ha mindkét tagja hamis.

Ez pedig pontosan az $\scriptstyle {A\vee B}$ alternáció hamisságfeltétele, ami már az igazságfeltételét is meghatározza.

A bevezetőben adott informális meghatározással szemben a nulladrendű logikában pontosabban is meg tudjuk határozni ezt a jelenséget. Ehhez azt kell észrevennünk, hogy a kijelentéslogika nyelvében definiált egyetlen egyargumentumú igazságfüggvény a negáció (jele: $\scriptstyle {\lnot }$), pontosan ezt a "megfordítást" végzi el. Így ha egy konjunkciót vagy alternációt tartalmazó formulára megfelelően alkalmazzuk, akkor megkaphatjuk az adott formula duálisát. Azaz a konjunkció és az alternáció interdefiniálhatóak egymással. Ezt fejezi ki tömörebben a következő képlet:

$(A\wedge B)\Leftrightarrow \lnot (\lnot A\vee \lnot B)$

A fenti összefüggés az egyik nevezetes De Morgan-azonosság.

Negáció

Ha a bevezetőben leírt "felcserélést" a negáción próbáljuk végrehajtani, érdekes eredményt kapunk. Belátható ugyanis, hogy a negáció duálisa saját maga. Ehhez vegyük először a negáció meghatározását:

$\scriptstyle {\lnot A}$ akkor és csak akkor igaz, ha $\scriptstyle {A}$ hamis.

Ha ezután fölcseréljük az igaz szót a hamissal, a következő eredményt kapjuk.

… akkor és csak akkor hamis, ha $\scriptstyle {A}$ igaz.

Ez pedig pontosan a negáció meghatározása.

Dualitás a predikátumlogikában

A predikátumlogikában vizsgált két konstans a két kvantor az univerzális kvantor (jele: $\scriptstyle {\forall }$) és az egzisztenciális kvantor (jele: $\scriptstyle {\exists }$). Ha megfigyeljük az igazságfeltételeiket, ismét csak a dualitást figyelhetjük meg.: Az univerzális kvantor ugyanis megadható a következőképpen:

Adott interpretáció és a változók adott értékelése mellett egy "$\scriptstyle {\forall x\,(A)}$" szerkezetű formula akkor és csak akkor hamis, ha az $\scriptstyle {x}$ változó értéke módosítható úgy - a többi változó értékét érintetlenül hagyva -, hogy $\scriptstyle {A}$ hamis legyen.

Az egzisztenciális kvantor pedig így adható meg:

Adott interpretáció és a változók adott értékelése mellett egy "$\scriptstyle {\exists x\,(A)}$" szerkezetű formula akkor és csak akkor igaz, ha az $\scriptstyle {x}$ változó értéke módosítható úgy - a többi változó értékét érintetlenül hagyva -, hogy $\scriptstyle {A}$ igaz legyen.

Ebből látható, hogy a két kvantor egymás duálisa.

Formulákban ugyanez:

$\forall \,xA\Leftrightarrow \lnot \,\exists x\lnot \,A$

$\exists \,xA\Leftrightarrow \lnot \,\forall x\lnot \,A$

Ezeket az összefüggéseket szokás a kvantifikáció De Morgan szabályainak nevezni.

Dualitás a modális logikában

A modális logikában vizsgált két új konstans a $\scriptstyle {\Box }$ és a $\scriptstyle {\Diamond }$. Ezek a konstansok az operátorok családjába tartoznak. Kiolvasásuk nehézkes, általában "szükségszerű"-nek és "lehetséges"-nek szokás hívni őket. Ruzsa Imre azt javasolja, hogy "nec"-nek és "posz"-nak olvassuk ki, azonban valószínűleg a legsemlegesebb kiolvasás, ha egyszerűen "doboz"-nak és "gyémánt"-nak hívjuk őket.^[forrás?]

Egy $\scriptstyle {\Box \,A}$ formájú kifejezés informálisan megfogalmazva akkor és csak akkor igaz, ha szükségszerű, hogy $\scriptstyle {A}$ igaz. Ezt érthetjük úgy, hogy lehetetlen $\scriptstyle {A}$ hamissága. Ha pedig lehetetlen alatt azt értjük, hogy nem lehetséges, akkor a következő módon formulázhatjuk meg $\scriptstyle {\Box }$ és $\scriptstyle {\Diamond }$ dualitását:

$\Box \,A\Leftrightarrow \lnot \,\Diamond \,\lnot \,A$

Természetesen ugyanez fordítva is igaz, azaz:

$\Diamond \,A\Leftrightarrow \lnot \,\Box \,\lnot \,A$

Ezeket az összefüggéseket szokás a modális logika De Morgan szabályainak nevezni.

Általánosítások

Az eddig tárgyalt, informálisan kifejtett jelenségnek léteznek különböző erejű, teljesen formális általánosításai is. Az első nullad rendű formulákra mondja ki a dualitást, a második pedig n-argumentumú műveletekre.

Általánosítás formulákra

Legyen $\scriptstyle {\varphi }$ egy olyan formula amely csak és kizárólag a $\scriptstyle {\wedge }$, $\scriptstyle {\vee }$ és $\scriptstyle {\lnot }$ konstansokat tartalmazza. Ekkor $\scriptstyle {\varphi ^{*}}$ az a formula amelyet úgy kapunk $\scriptstyle {\varphi }$-ből, hogy az előforduló $\scriptstyle {\wedge }$, $\scriptstyle {\vee }$, $\scriptstyle {\top }$, $\scriptstyle {\bot }$ konstansokat rendre a $\scriptstyle {\vee }$, $\scriptstyle {\wedge }$, $\scriptstyle {\bot }$ és $\scriptstyle {\top }$ konstansokra cseréljük. Ezt a $\scriptstyle {\varphi ^{*}}$ formulát $\scriptstyle {\varphi }$ formula duálisának nevezzük. Bizonyítható, hogy bármely $\scriptstyle {\varphi }$ és $\scriptstyle {\psi }$ esetén fennállnak a következő összefüggések:

• $\scriptstyle {\varphi (p_{1},\dots p_{n})\leftrightarrow \neg \varphi ^{*}(\neg p_{1}\dots \neg p_{n})}$
• $\scriptstyle {\varphi \leftrightarrow \psi }$ akkor és csak akkor, ha $\scriptstyle {\varphi ^{*}\leftrightarrow \psi ^{*}}$

Általánosítás műveletekre

A formulákra általánosított dualitás-definíció igazából a fenti informális körülírás formalizálása volt. Nulladrendű rendszer után megadható lenne elsőrendű vagy modális nyelvekre is formuladualitási definíció. Azonban felírható egy teljesen általános algebrai definíció is.

Adott $\scriptstyle {H}$ alaphalmaz esetén, melynek elemein megengedett az invertálás, egy n-argumentumú invertálható reláció duálisát a következő összefüggés alapján kapjuk meg:

$f^{*}(x_{1},...,x_{n})=_{\mathrm {def} }f^{-1}({x_{1}}^{-1},...,{x_{n}}^{-1})$

Forrás

1. Ruzsa Imre: Bevezetés a modern logikába, Osiris, Budapest, 2001
2. Alexander Chagrov, Michael Zakharyaschev: Modal Logic, Clarendon Press, Oxford, 1997