A tétel a teljesség utáni
Nézzük az egyik fő kérdés, hogy a matematikai logika - a kérdés a szükséges és elégséges feltételei a teljesség. enged
- tetszőleges rendszer funkcióit. A kérdés az, hogyan lehet megtudni, ez a teljes, vagy nem? A válasz erre a kérdésre adott az alábbi tétel.
Post-tétel. Annak érdekében, hogy a rendszer funkcióit teljes, szükséges és elégséges, hogy ez nem teljesen szereplő bármely öt zárt osztályok.
Bizonyítás. Szükségszerűség. Let - teljes körű, azaz. Tegyük fel, hogy benne van egy ilyen osztály - jelöljük. azaz. Ezután az áramkör és izolációs tulajdonságokkal van
.
Itt van. ez nem így van. A szükségesség bizonyított.
Megfelelősége. Hagyja, nem tartalmazott semmilyen ezen osztályok. Akkor lehet egy alrendszer. amely legfeljebb öt funkció, amely az ingatlan. Ehhez vesszük a funkciót. . . . és tegye
.
Annak bizonyítására, önellátás, azt látjuk, hogy a funkciók lehet építeni egy tagadás és összefüggésben. A bizonyítás végezzük két szakaszban történik.
I. építése funkciók segítségével. . és állandók és elutasítást.
Tekintsük a funkciók és. Készítünk egy függvény egy érv:
A fenti feltételezések alapján
. .
Attól függően, hogy milyen értékek és. Négy lehetőség.
Ebben az esetben. . Ennek eredményeként a szuperpozíció kap konstans 1 :. Így, tagadás és állandók épített.
Ebben az esetben. . Építeni. és az első szakasz végére.
Van. Mi használja ezt a funkciót. Ehhez a funkcióhoz van egy pár szemben és készletek. amely úgy ugyanazt az értéket
.
Tekintsük a funkciót. ahol a helyén -ik érv. if. vagy. if. majd
.
Ebből következik, hogy. A tagadás építek állandó.
Következésképpen ,. . Mi ez a nem monoton függvény. Lemma 4 helyettesítve a konstansok nyerhető tagadása.
II. Megmutatjuk, hogy a funkció lehet kialakítani összefüggésben. Mi kell használni a beépített az első szakaszban és az állandó elutasítást. Az általunk használt nem-lineáris függvény. Behelyettesítve az állandók és a konstrukció egy nemlineáris függvény két érv, amely lehetővé Lemma 6:
.
Tekintsük a funkciót. A konstrukció csak akkor kell tagadás, mert a túl egy bináris állandó vagy nem változik semmi, ha az értéke 0, vagy módosítsa a változó annak tagadása. Például, amikor. . .
Eltávolítása zárójelben, azt látjuk, hogy. Így az összefüggésben a funkciók a rendszer épül.
Annak ellenőrzésére, teljességének speciális funkciók a rendszer kényelmes töltse ki a táblázatot, amely kimondja, 1 vagy 0, vagy forgalomba nevhozhdenie funkciók osztályok. . . és. Például a funkciók a rendszer
mi a következő táblázat tartalmazza: