Să considerăm acum una dintre principalele probleme algebra logicii - problema condițiilor necesare și suficiente de completitudine. lăsa
- un sistem arbitrar de funcții. Întrebarea este cum de a afla, este plin sau nu? Răspunsul la această întrebare este dat de următoarea teoremă.
Teorema lui Post. Pentru ca sistemul de funcții este completă, este necesar și suficient ca acesta nu este conținut în întregime în oricare din cele cinci clase închise.
Dovada. Necesitate. Să - complet, adică. Să presupunem că este conținută într-una din aceste clase - denota prin. adică. Apoi, prin proprietățile de circuit și izolare avem
.
Aici. că nu este așa. Necesitatea este demonstrată.
Suficiență. Să nu este conținută în oricare din aceste clase. Apoi, puteți dintr-un subsistem. care nu conține mai mult de cinci funcții pe care le are această proprietate. Pentru a face acest lucru vom lua funcția. . . . și a pus
.
Pentru a dovedi suficiență, vom vedea că din funcțiile pe care le poate construi o negație și conjuncție. Dovada se realizează în două etape.
I. Construcția utilizând funcțiile. . și constante și negare.
Luați în considerare funcțiile și. Noi construim o funcție de un argument:
În conformitate cu ipotezele de mai sus
. .
În funcție de ce valori sunt și. patru opțiuni.
În acest caz. . Ca rezultat al superpoziției obține constant 1 :. Astfel, negarea si constantele construite.
În acest caz. . Build. iar prima fază este finalizată.
Avem. Noi folosim funcția. Pentru această funcție, există o pereche de opus și seturi. care ia aceeași valoare ca și
.
Luați în considerare funcția. în care, în loc de argument -lea a pus. în cazul în care. sau. în cazul în care. atunci
.
Rezultă că. Cu negarea va construi o altă constantă.
În consecință ,. . Noi folosim funcția de non-monotonă. Prin Lema 4 prin substituirea constantele se pot obține negație.
II. Arătăm că funcția poate fi construit împreună. Vom folosi construit în prima fază și negarea constantă. Noi folosim funcția non-lineară. Înlocuind constantele și construi o funcție neliniară a două argumente, ceea ce este posibil prin Lema 6:
.
Luați în considerare funcția. Pentru a construi nevoie doar de negare, pentru că adăugarea unei constante binare sau nu se schimba nimic, în cazul în care este egal cu 0 sau modifica variabila pe negația. De exemplu, atunci când. . .
Scoaterea parantezele, vedem că. Astfel, conjugarea funcțiile sistemului este construit.
Pentru a verifica caracterul complet al funcțiilor specifice ale sistemului este convenabil să completeze tabelul, care prevede 1 sau 0 sau nevhozhdenie funcții de intrare în clase. . . și. De exemplu, funcțiile sistemului
avem tabelul de mai jos: