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ó interdefiná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{\exist}$). 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 értekélese 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{\exist 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 \, x A \Leftrightarrow \lnot \, \exist x \lnot \,A$

$\exist \, x A \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á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