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 ($A\wedge B$) a következő módon adjuk meg:

$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 $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: $\mathrm{\neg }$), 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)\iff \mathrm{\neg }(\mathrm{\neg }A\vee \mathrm{\neg }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:

$\mathrm{\neg }A$ akkor és csak akkor igaz, ha $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 $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: $\mathrm{\forall }$) és az egzisztenciális kvantor (jele: $\mathrm{\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 "$\mathrm{\forall }x(A)$" szerkezetű formula akkor és csak akkor hamis, ha az $x$ változó értéke módosítható úgy - a többi változó értékét érintetlenül hagyva -, hogy $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 "$\mathrm{\exists }x(A)$" szerkezetű formula akkor és csak akkor igaz, ha az $x$ változó értéke módosítható úgy - a többi változó értékét érintetlenül hagyva -, hogy $A$ igaz legyen.

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

$\mathrm{\forall }xA\iff \mathrm{\neg }\mathrm{\exists }x\mathrm{\neg }A$

$\mathrm{\exists }xA\iff \mathrm{\neg }\mathrm{\forall }x\mathrm{\neg }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 $◻$ és a $◊$. 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 $◻A$ formájú kifejezés informálisan megfogalmazva akkor és csak akkor igaz, ha szükségszerű, hogy $A$ igaz. Ezt érthetjük úgy, hogy lehetetlen $A$ hamissága. Ha pedig lehetetlen alatt azt értjük, hogy nem lehetséges, akkor a következő módon formulázhatjuk meg $◻$ és $◊$ dualitását:

$◻A\iff \mathrm{\neg }◊\mathrm{\neg }A$

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

$◊A\iff \mathrm{\neg }◻\mathrm{\neg }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 $\phi$ egy olyan formula amely csak és kizárólag a $\wedge$, $\vee$ és $\mathrm{\neg }$ konstansokat tartalmazza. Ekkor ${\phi }^{*}$ az a formula amelyet úgy kapunk $\phi$-ből, hogy az előforduló $\wedge$, $\vee$, $\mathrm{\top }$, $\mathrm{\perp }$ konstansokat rendre a $\vee$, $\wedge$, $\mathrm{\perp }$ és $\mathrm{\top }$ konstansokra cseréljük. Ezt a ${\phi }^{*}$ formulát $\phi$ formula duálisának nevezzük. Bizonyítható, hogy bármely $\phi$ és $\psi$ esetén fennállnak a következő összefüggések:

• $\phi (p_1,\dots p_n)\leftrightarrow \mathrm{\neg }{\phi }^{*}(\mathrm{\neg }{p}_1\dots \mathrm{\neg }{p}_n)$
• $\phi \leftrightarrow \psi$ akkor és csak akkor, ha ${\phi }^{*}\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 $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{d}\mathrm{e}\mathrm{f}}{f}^{-1}({x_1}^{-1},...,{x_n}^{-1})$

Források

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