Diszjunktív normálforma

A diszjunktív normálforma, röviden DNF a matematikai logika egy területén, a nulladrendű logikán belül definiálható fogalom, egy logikai műveletet leíró olyan ítéletlogikai formulát jelent, mely a művelet változóinak vagy negáltjainak konjunkcióinak diszjunkciója:

$\bigvee _{i}\bigwedge _{j}(\neg )x_{ij}.$

A diszjunktív normálformák tehát olyan nulladrendű logikai formulák, melyekben csak változók és az $\lnot ,\vee ,\wedge$ operátorok fordulnak elő (és egyéb megkötések is érvényesek).

Tehát, ha a logikai művelet az $X_{1},X_{2},...,X_{n}$ változókon van értelmezve, akkor egy diszjunktív normálformája lehet például:

$\left(\lnot X_{1}\wedge X_{2}\right)\vee \left(\lnot X_{2}\wedge X_{3}\right)\vee ...\vee \left(\lnot X_{n-1}\wedge X_{n}\right)$

Fontosabb elnevezések

Tekintsük az alábbi, DNF alakú formulát:

$\left(\lnot X_{1}\wedge \lnot X_{2}\right)\vee \left(X_{2}\wedge X_{3}\wedge \lnot X_{4}\right)$

• a változókat a (normál)forma atomjainak nevezzük, a fenti példában atomok $X_{1},X_{2},X_{3},X_{4}$ ;
• a változókat vagy negáltjaikat közös néven a (normál)forma literáljainak nevezzük; a fenti példában literálok $\lnot X_{1},\lnot X_{2},X_{2},X_{3},\lnot X_{4}$ ; a negálatlan literálokat pozitívnak, míg a negáltakat negatívnak is szokás nevezni.
• a literálok konjunkcióit pedig elemi konjunkcióknak, a fenti példában ezek: $\lnot X_{1}\wedge \lnot X_{2}$ és $X_{2}\wedge X_{3}\wedge \lnot X_{4}$.

E formuláknak különféle alkalmazásai vannak például a számításelméletben, az automatikus tételbizonyítások elméletében (rezolúciós kalkulus, logikai programozás).

Példák és ellenpéldák

Néhány logikai művelet, diszjunktív normálformában:

$A$

$A\vee B$

$A\vee \lnot B$

$A\wedge \lnot B$

$\left(A\wedge \lnot B\right)\vee \left(\lnot A\wedge \lnot B\right)$

A következő formulák viszont nem diszjunktív normálformulák:

$\lnot (A\wedge B)\vee C$, mert a negáció nem csak atomot köt, hanem egy összetett formulát;

$(A\vee B)\wedge C$, mert nem egy elemi konjunkció, hanem egy elemi diszjunkció a konjunkció egy tagja;

$(A\vee B)\rightarrow C$, mert előfordul nem megengedett operátor ($\rightarrow$ ).

Viszont a fenti formulákkal (műveletekkel) ekvivalensek az alábbi, diszjunktív normálforma alakú formulák:

$\lnot A\vee \lnot B\vee C$ (minden elemi konjunkció egytagú, atomi;)

$(A\wedge C)\vee (B\wedge C)$

$\left(\lnot A\wedge \lnot B\right)\vee \left(C\right)$

Műveletek és formulák előállítása DNF alakban

Tetszőleges ítéletlogikai műveletet és formulát elő lehet állítani DNF alakban. Néha többféleképp is, azaz az előállítás nem egyértelmű.

Szintaktikus módszerek

Egy nem-, és-, vagy-, implikáció- és ekvivalencia-jeleket tartalmazó nulladrendű formula mindig átalakítható DNF alakba, mégpedig szintaktikusan, azaz csak átalakítási szabályok segítségével; anélkül, hogy a formulát ki kellene értékelnünk.

A következő szabályokat lehet, érdemes alkalmazni egy formula DNF alakba hozásakor:

1. $A\leftrightarrow B\equiv \left(A\rightarrow B\right)\wedge \left(B\rightarrow A\right)$;
2. $A\rightarrow B\equiv \lnot A\vee B$;
3. $\lnot (A\vee B)\equiv \lnot A\wedge \lnot B$ (De Morgan-szabály I.);
4. $\lnot (A\wedge B)\equiv \lnot A\vee \lnot B$ (De Morgan-szabály II.);
5. $(A\vee B)\wedge C\equiv (A\wedge C)\vee (B\wedge C)$ (disztributivitási törv.);
6. $\lnot \lnot A\equiv A$ (kettős tagadás).

A DNF egyszerűsítésre sokszor még használhatóak az ún. adszorbciós szabályok:

1. $(A\wedge B)\vee A\equiv A$;
2. $(A\vee B)\wedge A\equiv A$.

Szemantikus módszerek. A KDNF

Ha adott egy többváltozós logikai művelet, például értéktáblázattal, akkor ennek ismeretében megkonstruálható egy DNF, ami az illető műveletet leírja. Ez azt is jelenti, hogy az $\left(\lnot ,\vee ,\wedge \right)$ rendszer funkcionálisan teljes.

Egy diszjunktív normálforma értéktáblázatát elkészítve, a formula adott sorban (interpretációban) pontosan akkor lesz igaz, ha abban az interpretációban legalább egy elemi konjunkció igaz, tehát pontosan akkor hamis, ha abban az interpretációban minden elemi konjunkció hamis. Márpedig egy elemi konjunkció pontosan akkor hamis, ha legalább egy literálja hamis abban az interpretációban, akkor igaz tehát, ha minden literál igaz; azaz negálatlan atomjai igazak, a negáltak pedig hamisak. Adott interpretációt tekintve, ha tehát az atomokat összediszjunkciózzuk úgy, hogy a konjunkcióban negálatlanul szerepeljenek az „igaz” igazságértéket kapott atomok, és negáltan a „hamis” igazságértéket kapottak; akkor a konjunkció értéke igaz lesz. Ezáltal pedig a konjunkciók diszjunkciója is igaz lesz ebben az interpretációban.

Ennek megfelelően a következőképp konstruálhatunk DNF-t tetszőleges művelethez: a művelet értéktáblázata minden olyan sorához (interpretációjához), melyben az f művelet az i (igaz) logikai értéket veszi fel, konstruálunk egy literálokból álló elemi konjunkciót, mégpedig úgy, hogy ha az X_k változónak abban a sorban i értéket adtunk, akkor ez a változó a diszjunkcióba mint negálatlan atom (pozitív literál) kerül be, ha pedig h (hamis) értéket, akkor negáltan. Tehát minden olyan sorhoz/interpretációhoz, melyre f(X₁, … , X_n) = i , ily módon létrehozunk egy elemi konjunkciót, mely pontosan ebben az interpretációban igaz. Majd képezzük ezek diszjunkcióját: ez pontosan akkor igaz, ha valamelyik elemi konjunkciója igaz, na de ha a diszjunkció az adott interpretációban igaz, akkor készítettünk egy ebben az igaz interpretációban igaz elemi konjunkciót az előbb, mely a diszjunkció egy tagjaként biztosítja, hogy a diszjunkció igaz legyen. Így egy DNF alakú formulát kapunk, és a fentiek alapján ez valóban „ekvivalens” az eredeti logikai függvénnyel. Az ezen algoritmus eredményeképp kapott DNF-t a logikai művelet/formula kitüntetett diszjunktív normálformájának (KDNF) is nevezik.

Formálisan „polinommal” adhatjuk meg az f KDNF alakját:

$KDNF\left(f\left(X_{1},X_{2},...,X_{n}\right)\right)=\bigvee _{I\in \left\{0,1\right\}^{n}\wedge f^{I}=1}\bigwedge _{j=1}^{n}\left[(-1)^{X_{i}^{I}}X_{i}\right]$.

Tehát a diszjunkcióképzés az összes olyan interpretációra (kiértékelésre) terjed ki, mely igazzá teszi f-et; továbbá g^I-vel jelöltük a g függvény adott I kiértékelésbeli logikai értékét (például ha g=f vagy ha g=X_i), és -1-gyel való „szorzásként” a negálást.

Megjegyzés: e módszerrel nem lehet az azonosan hamis logikai függvényekhez DNF-t rendelni. És valóban, ezeknek nincs is, illetve esetleg azt szoktuk mondani, hogy DNF alakjuk az "üres diszjunkció", amit 0-val (h-val) is szokás jelölni.

Példa

KDNF konstruálása

E módszereket a következő, $f(A,B):=\left(A\rightarrow B\right)$ kétváltozós függvény példáján illusztráljuk:

A B f(A,B) elemi diszjunkció 0 0 1 $\lnot A\wedge \lnot B$ 0 1 1 $\lnot A\wedge B$ 1 0 0 - 1 1 1 $A\wedge B$

Vagyis az $f(A,B)=\left(A\rightarrow B\right)$ függvényhez/formulához szemantikusan konstruált normálforma a következő lesz:

$\left(A\wedge B\right)\vee \left(\lnot A\wedge B\right)\vee \left(\lnot A\wedge \lnot B\right)$     (*) .

Szintaktikus konstrukció

Szintaktikusan egy sokkal egyszerűbb, egyetlen elemi diszjunkcióból álló DNF-et tudunk konstruálni: $\left(A\rightarrow B\right)\equiv \lnot A\vee B$ érvényes ugyanis (a fentebb megadott 2. szintaktikai szabályt használtuk).

A KDNF egyszerűsítése

A szemantikus módszerrel kapott KDNF-ből a következőképp, a (*) formula alábbi átalakításaival, egyszerűsítésével is eljuthatunk szintaktikus úton a fent leírt sokkal egyszerűbb DNF-hoz; a KDNF utolsó két klózának konjunkciójából álló részformuláját alakítgatjuk:

$\left(\lnot A\wedge B\right)\vee \left(\lnot A\wedge \lnot B\right)$ $\equiv$ $\left[\left(\lnot A\wedge B\right)\vee \lnot A\right]\wedge \left[\left(\lnot A\wedge B\right)\vee \lnot B\right]$ $\equiv$ $\equiv$ $\left[\lnot A\right]\wedge \left[\left(\lnot A\vee \lnot B\right)\wedge \left(B\vee \lnot B\right)\right]$ $\equiv$ $\left[\lnot A\right]\wedge \left[\left(\lnot A\vee \lnot B\right)\wedge \left(1\right)\right]$ $\equiv$
$\equiv$ $\left[\lnot A\right]\wedge \left[\lnot A\vee \lnot B\right]$ $\equiv$ $\lnot A$

Tekintetbe véve még az első klózt is; $f(A,B)=A\rightarrow B$ $\equiv$ $\left(A\wedge B\right)\vee \left(\lnot A\right)$ $\equiv$ $\left(A\vee \lnot A\right)\wedge \left(B\vee \lnot A\right)$ $\equiv$ $1\wedge \left(B\vee \lnot A\right)$ $\equiv$ $\left(B\vee \lnot A\right)$ $\equiv$ $\lnot A\vee B$

(E hosszadalmas eljárás egy lentebbi szakaszt kíván illusztrálni).

A DNF nem egyértelmű

Mindebből látható, hogy a DNF tényleg nem egyértelmű, sok esetben egyszerűsíthető a fent megadott, illetve további szintaktikus szabályok (az ítéletlogika törvényei) segítségével.

Problémák és alkalmazások

A DNF-előállító eljárások sok algoritmikus, számításelméleti problémát vetnek fel.

Egyszerűsítő eljárások

Láttuk, hogy a DNF nem egyértelműen létezik egy adott Boole-függvényhez vagy formulához. Felmerül a kérdés, hogy definiálható-e és található-e mindegyikükhöz egy-egy valamilyen értelemben „legegyszerűbb” DNF?

Például a fent leírt szemantikus eljárással kapott DNF-k gyakorta exponenciális sok tagból állnak. Ezért a múlt században (az 1950-es évektől) az elektronikus számítógépek és az áramkörelmélet megjelenése után komoly kutatási terület volt a matematikai logikán belül a normálformák egyszerűsítése. Rengeteg egyszerűsítő eljárást fedeztek fel, a leggyakrabban idézett a DNF-ek kezelésére kidolgozott Quine-McCluskey-algoritmus.

Hivatkozások

Lásd még

• konjunktív normálforma
• Skolem-normálforma
• Horn-logika

Külső hivatkozások

Magyar nyelven

• Sulinet a normálformákról

Angolul

• A DNF-ek vizsgálata számításelméleti szempontból (cikk, PDF)
• Dr. Math leírása, sok példával
• Részletes leírása és kapcsolata a logikai programozással.

Irodalom

• Papadimitriou, Christos H.: Számítási bonyolultság (Computational complexity). Egyetemi tankönyv. Novadat Bt., 1999. ISBN 963-9056-20-0.
• Pásztorné Varga Katalin – Várterész Magda: A matematikai logika alkalmazásszemléletű tárgyalása, Panem, Bp., 2003. ISBN 963-545-364-7