Chapter 4. Normálformák

4.1. Konjunktív és diszjunktív normálformák

Definíció Az atomi formulákat és a negáltjaikat literáloknak nevezzük. Elemi konjunkciónak tekintünk minden literált, továbbá egy elemi konjunkció és egy literál konjunkcióját. Elemi diszjunkciók szintén a literálok, továbbá egy elemi diszjunkció és egy literál diszjunkciója. A konjunktív normálformájú formula egy elemi diszjunkció, vagy egy konjunktív normálforma és egy elemi diszjunkció konjunkciója, a diszjunktív normálformájú formula egy elemi konjunkció, vagy egy diszjunktív normálforma és egy elemi konjunkció diszjunkciója.

Tétel Az elsőrendű logikai nyelv minden kvantormentes formulájához konstruálható vele logikailag ekvivalens konjunktív és diszjunktív normálformájú formula.

Definíció Egy formulával ekvivalens konjunktív normálformájú formulát a formula konjunktív normálformájának , a vele ekvivalens diszjunktív normálformájú formulát a formula diszjunktív normálformájának nevezzzük.

A normálformára hozás lépései:

  1. A logikai jelek közötti összefüggések alapján a formulába minden implikációs részformula helyett vele ekvivalens diszjunkciót írunk.

  2. De Morgan törvényeivel elérjük, hogy negáció csak atomi formulákra vonatkozzon.

  3. A disztributivitást felhasználva addig alakítjuk a formulát, hogy a konjunkciók és diszjunkciók megfelelő sorrendben kövessék egymást.

  4. Végül esetleg egyszerűsítünk.

Felhasználható ekvivalenciák:

Table 4.1. asszociativitás

Table 4.2. kommutativitás

Table 4.3. disztributivitás

Table 4.4. idempotencia

Table 4.5. elimináció (elnyelés)

Table 4.6. De Morgan törvényei

Table 4.7. kiszámítási törvények

(

)

Table 4.8. logikai jelek közötti összefüggések

Table 4.9. kétszeres tagadás

Table 4.10. negáció az implikációban

Példa Hozzuk a

Equation 4.. 


formulát normálformára.

  1. Eltávolítjuk az implikációkat:

    Equation 4.. 


  2. Elérjük, hogy negáció csak atomokra vonatkozzon:

    Equation 4.. 


  3. Felhasználjuk a disztributivitást; az eredmény konjunktív normálforma:

    Equation 4.. 


  4. Egyszerűsítünk:

    Equation 4.. 


  5. Tovább egyszerűsítünk; az eredmény egyszerre konjunktív és diszjunktív normálforma:

    Equation 4..