Dualitás (logika)

A Wikipédiából, a szabad enciklopédiából
(Dualitás szócikkből átirányítva)
Ugrás a navigációhoz Ugrás a kereséshez

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.

Konjunkció és alternáció[szerkesztés]

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ás[szerkesztés]

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

Jegyzetek[szerkesztés]

  1. Ruzsa, 2001 p.35
  2. Ruzsa, 2001 p.34
  3. Ruzsa, 2001 p.80
  4. a b Ruzsa, 2001 p.245
  5. Ezt Mihálydeák Tamás alkotta meg, szóbeli közlés alapján idézzük.