Know-how, előadás, erbrane tétele
Elsődleges normál forma
Azt mondják, hogy a képlet normális formában van, ha maradt minden benne lévő kvantáló, vagyis ha az a forma
hol vannak az univerzalitás vagy létezés mennyiségi meghatározói, változók, és kvantáló-mentes képlet. Ez a képlet paraméterekkel rendelkezhet (ha a képletnek más paraméterei is vannak).
Ennek a résznek a fő eredménye, hogy bármely képlet (igazolható) egyenértékű valamely képletben a prefixált normál formában (a prefixált képlet). Bizonyítani fogjuk, hogy egyidejűleg megteremtjük a képletek osztályozását (bizonyos értelemben a "logikai komplexitásuk" tükrében). A komplexitás mércéjeként a számszerűsítő számok számát a prefiksált normális formában vehetjük. De helyénvalóbb figyelembe venni a kvantálócsoportok számát (feltételezve, hogy az azonos nevű kvantorok előtte vannak).
Azt mondják, hogy az előre meghatározott képlet egy képlet, ha a számszerűsítő előtag mennyiségi csoportokat tartalmaz, és a létező kvantifikátorok az elsőek. Ha az univerzalitás kvantálja az első. beszélj az osztályról. (Hasonló számokat használnak az algoritmusok elméletében az aritmetikai készletek osztályozásához, lásd [5]).
Példa: a képlet az osztályhoz tartozik, a képlet az osztályhoz tartozik, és a képlet egyáltalán nem normális formában van.
103. Jelölje meg a formulát a prefiksban levő normál formában, bizonyíthatóan egyenértékű az előző formulákkal.
Érdeklik, hogy mi történik a "logikai komplexitás" -gal a logikai műveletek alatt mért képlet alapján. Kezdjük nagyon egyszerű megfigyelésekkel.
- Minden osztályban szereplő képlet vagy bizonyíthatóan egyenértékű egy osztály képletével, valamint egy osztály képletével. Valójában, ha a képletnek nincs paramétere, akkor bizonyosan egyenértékű a képletekkel és (az egyik következmény egy axióma, a másik az Bernays-szabályból származik). Így hozzáadhatunk egy próbabábu mennyiségét a kvantáló kezdetéhez vagy annak végéhez; a második esetben meg kell említenünk a 2. lemezt.
- Az osztály bármely képletének tagadása bizonyíthatóan egyenértékű az osztály valamelyik képletével és fordítva. Valójában láttuk, hogy a levezethető egyenértékű és fordítva, így a negáció hordozható belül, a kvantálók kettős változóvá változtatása az ügy során.
Megmutatjuk, hogy a két képlet összekapcsolása bizonyíthatóan egyenértékű valamelyik képletből. Például egy összefüggés bizonyíthatóan egyenértékű egy képletgel. Tény, hogy az axiómát univerzális kvantor, akkor visszavonja, és visszavonja, így együttállása a kimenetet, akkor meg lehet akasztani két univerzális kvantor. A másik irányba: a képletből származunk, majd alkalmazzuk az Bernays szabályt, és így tovább.
104. Mutassuk meg, hogy menthetsz egy kvantálót és használhatod a képletet.
Az általános érvelés (az osztály bármelyik két képleténél) csaknem olyan egyszerű, csak a vonatkozó változókat kell átnevezni az 52. tétellel.
Most megmutatjuk, hogy egy osztályból két képlet összekapcsolása bizonyíthatóan egyenértékű egy osztályképletével, és hogy két osztályképlet diszjunkciója bizonyíthatóan egyenértékű egy osztályképlet-eloszlással. Ehhez az űrlap egyenértékűségét kell használnunk
Ezek az egyenértékűségek, amint az könnyen látható, általában érvényesek és ezért levezethetők. Elég könnyű megérteni az elsőt (találni egy pár objektumot adott tulajdonságokkal, meg kell találnia a pár első és második tagját külön). A második egyenértékűség egy kicsit bonyolultabb - a legkönnyebb észrevenni, hogy az elsőhöz kerül, amikor egy negációt ad hozzá. (A nagyobb összetettség tükrözi azt a tényt, hogy a második egyenértékűség, ellentétben az elsővel, nem intuicionistaan helyes.)
Most már könnyen érthető, hogy az összefüggésben, és diszjunkcióját két képlet, az osztály (vagy azzal egyenértékű bizonyítható képletek az azonos osztályba. Tény, használatával ekvivalenciáit lehet üríteni kvantor előtag a fent meghatározott. Például, a képlet
bizonyíthatóan egyenértékű a képletével
majd a képletet