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
[szerkesztés]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.
A nullad rendű logikában a konjunkciót () a következő módon adjuk meg:
- 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 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: ), 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 fenti összefüggés az egyik nevezetes De Morgan-azonosság.[1]
Negáció
[szerkesztés]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:
- akkor és csak akkor igaz, ha 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 igaz.
Ez pedig pontosan a negáció meghatározása.[2]
Dualitás a predikátumlogikában
[szerkesztés]A predikátumlogikában vizsgált két konstans a két kvantor az univerzális kvantor (jele: ) és az egzisztenciális kvantor (jele: ). 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:[3]
- Adott interpretáció és a változók adott értékelése mellett egy "" szerkezetű formula akkor és csak akkor hamis, ha az változó értéke módosítható úgy - a többi változó értékét érintetlenül hagyva -, hogy hamis legyen.
Az egzisztenciális kvantor pedig így adható meg:
- Adott interpretáció és a változók adott értékelése mellett egy "" szerkezetű formula akkor és csak akkor igaz, ha az változó értéke módosítható úgy - a többi változó értékét érintetlenül hagyva -, hogy igaz legyen.
Ebből látható, hogy a két kvantor egymás duálisa.
Formulákban ugyanez:
Ezeket az összefüggéseket szokás a kvantifikáció De Morgan szabályainak nevezni.
Dualitás a modális logikában
[szerkesztés]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,[4] 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 formájú kifejezés informálisan megfogalmazva akkor és csak akkor igaz, ha szükségszerű, hogy igaz. Ezt érthetjük úgy, hogy lehetetlen 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:[4]
Természetesen ugyanez fordítva is igaz, azaz:
Ezeket az összefüggéseket szokás a modális logika De Morgan szabályainak nevezni.
Általánosítások
[szerkesztés]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
[szerkesztés]Legyen egy olyan formula amely csak és kizárólag a , és konstansokat tartalmazza. Ekkor az a formula amelyet úgy kapunk -ből, hogy az előforduló , , , konstansokat rendre a , , és konstansokra cseréljük. Ezt a formulát formula duálisának nevezzük. Bizonyítható, hogy bármely és esetén fennállnak a következő összefüggések:
- akkor és csak akkor, ha
Általánosítás műveletekre
[szerkesztés]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.[5]
Adott 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:
Források
[szerkesztés]- Ruzsa Imre: Bevezetés a modern logikába, Osiris, Budapest, 2001
- Alexander Chagrov, Michael Zakharyaschev: Modal Logic, Clarendon Press, Oxford, 1997