Elsődleges normál forma
Definíció. Azt mondják, hogy a elsőrendű logika általános képletű, amelynek normális alakú, ha tartalmazza csak a műveletek összefüggésben, diszjunkciót és kvantor működését és megtagadják működés rendelt elemi képletek.
Nyilvánvaló, hogy a javaslatok algebra és a predikátumok logikája egyenértékűségével a predikátumok logikájának minden formulája normál formává redukálható. Például csökkentjük a képletet a normál alakra
Az egyenértékű transzformációk kihasználása. kapunk
A predikátumok logikájának képletei normális formái között nagy jelentőséggel bír az úgynevezett primordiális normál formák (pnf). Ezekben a kvantitatív műveletek vagy teljesen hiányoznak, vagy a logika algebra összes művelete után használják, vagyis a predikátum logikai képletének elődje normális formája az
ahol az A szimbólum nem tartalmaz kvantálót.
Tétel. A predikátumok logikájának bármely formulája lecsökkenthető a prefixált normál formára.
Bizonyítás. Feltételezzük, hogy a képlet már normál formára redukálódott, és megmutatjuk, hogy a normál alakra redukálható.
Ha az adott képlet elemi, akkor nem tartalmaz quantizereket, és ezért már előre meghatározott normális formában van.
Tételezzük fel, hogy a tétel igaz a legtöbb k műveletet tartalmazó képletekre, és bebizonyítjuk, hogy ezen feltételezés mellett a képletek is érvényesek. pontos k + 1 műveletet tartalmaz.
Tegyük fel, hogy az A képlet tartalmaz egy k 1 műveletet, és L (x) alakú, ahol az egyik kvantálót jelölik.
Mivel L (x) k műveleteket tartalmaz, ezért következésképpen normál normál formává redukálható, akkor minden kvantitatív művelet elé kerül. De az L (x) képlet nyilvánvalóan előzetesen normális formában van.
Tegyük fel, hogy az A képletnek olyan alakja van, ahol az L képlet redukálódik az előválasztott normál alakra, és k műveleteket tartalmaz. Ezután az 1 és 2 ekvivalenciák segítségével a negációt a kvantáló jel alatt vezetjük be, és ez az A képletet az előrendes formához vezeti.
Tegyük fel, hogy az A képletnek van az a formája, ahol és azt a prefixált normál alakra redukáljuk.
Nézzük át a kapcsolódó objektumváltozókat a képletben, hogy a képletekben az összes kapcsolódó változó különböző legyen. Ebben az esetben a képleteket a formában kell megírni
A 7. és az 1. ekvivalenciák alkalmazásával az A képletet írjuk le, a képletet a kvantálók tünetei mellett:
Ezután bemutatjuk a képletet a kvantáló jelek alatt. Ezután az "A" képlet kapja meg az előfeszített normál formát:
A bizonyítékot hasonlóan végezzük abban az esetben is, ha az A képletnek van forma .
Megjegyzés. Ha a predikátum logikai képletét pnf-re redukáljuk. a kifejezést vagy a kifejezést figyelembe kell venni, akkor az 5. és a 10. ekvivalenciát kell használnunk.
Például előhozzuk a megelőző normális értéket