Scopul acestei secțiuni este de a răspunde la una din principalele întrebări ale algebrului logicii - problema condițiilor necesare și suficiente pentru completitudinea unui sistem de funcții booleene. Răspunsul la această întrebare este dat de următoarea teoremă, dovada căreia se va baza pe metoda lui AV Kuznetsov și
S. K. Yablonsky.
Teorema 3 (cu privire la caracterul complet) Pentru ca un sistem de funcții booleene să fie complet, este necesar și suficient ca acesta să nu fie inclus în nici una din cele cinci clase închise T0. T1. S, M, L.
Dovada, necesitatea. Fie A un sistem complet conținut într-una din clasele T0. T1. S, M, L. Fără pierderea generalității, presupunem asta. Apoi. În consecință ,. ceea ce este imposibil.
Suficiență. Să presupunem că sistemul de funcții Boolean D nu este în întregime conținut în oricare dintre clasele T0. T1. S, M, L. Apoi, în sistemul D există în mod necesar următoarele funcții :. nu păstrează 0; . fără conservare 1; nu o funcție auto-duală; funcția neliniară; nu este o funcție monotonă. Având în vedere conceptul de variabilă dummy, putem presupune că aceste funcții depind de aceleași variabile.
În primul rând, construim constantele 0 și 1 din sistemul de funcții A.
Luați în considerare funcția. Această funcție este o suprapunere de funcții și. Deoarece nu aparține clasei T0. . Dacă acum g (1) = 1, atunci este o constantă 1. Înlocuind constanta 1 în funcție. avem constant 0, pentru că.
Să fie acum. Din egalitatea g (0) = 1 și g (1) = 0, concluzionăm că. Luăm o funcție non-auto-duală. Evident, în acest caz există un astfel de set de variabile. că =.
Luați în considerare o funcție și construiți o funcție utilizând operația de suprapunere. Atunci primim:
Astfel, h (0) = h (1). Și aceasta înseamnă că h (x) este o constantă de 0 sau 1. Deoarece am construit o funcție. atunci suprapunerea acestei funcții cu una dintre constante dă o altă constanță. În consecință, constantele 0 și 1 sunt construite de noi.
Acum, folosind teorema anterioară, putem folosi suprapunerea unei funcții și constantele 0,1 pentru a construi o funcție. și, prin urmare, toate funcțiile. Anterior am arătat că orice funcție booleană poate fi reprezentată ca o suprapunere a funcțiilor și funcțiilor deja construite. Prin urmare, pentru a completa dovada teoremei, rămâne să construim o funcție. Pentru a face acest lucru, luăm funcția și construim polinomul Zhegalkin pentru această funcție. Deoarece această funcție este neliniară, în acest polinom există un termen care conține cel puțin doi factori. Fără pierderea generalității, putem presupune că acești factori sunt și. Apoi putem scrie polinomul Zhegalkin pentru funcția în următoarea formă:
Datorită unicității polinomului, funcția nu este identică cu zero. Alegem astfel de valori ale variabilelor. asta. Având în vedere acest lucru, ajungem la această funcție
unde constantele 0 sau 1. Construim funcția după cum urmează:
Astfel, teorema de completitudine este complet dovedită.
În acele probleme în care este necesar să se determine dacă sistemul de funcții boolean dat este complet, vom compila tabele, care sunt numite Mesaje postale. Datele din tabel sunt următoarele.
Este ușor de verificat dacă această funcție nu aparține T0. nici T1. Deci, cum. iar valoarea funcției la tastare (0,0,0) este mai mare decât atunci când tastați (1,1,1), atunci funcția nu este monotonă. Evident, toate variabilele unei funcții date sunt semnificative. Și deoarece această funcție nu se poate potrivi nici. nici cu. atunci este neliniar. Ca în exemplul 6, se poate demonstra că funcția este auto-dublă. În consecință, sistemul A4 nu este complet.
Noi numim un sistem de funcții booleene ireductibil. dacă nici o funcție nu poate fi exclusă din ea, astfel încât sistemul rămas după ce excepția este completată din nou.
Este evident că orice sistem complet de funcții booleene poate fi redus la ireductibil. După cum rezultă din teorema de completitudine, orice sistem complet ireductibil conține cel mult 5 funcții. Următoarele teoreme arată că, în realitate, numărul lor poate fi întotdeauna redus la 4.
Teorema 4. Numărul maxim posibil de funcții într-un sistem complet ireductibil de funcții booleene este egal cu 4.
Într-adevăr, în demonstrarea teoremei de completitudine, am văzut că din orice sistem complet de funcții booleene se poate distinge un subsistem complet care conține nu mai mult de cinci funcții. Și funcționează. care nu păstrează 0 sau nu conservă 1 sau dacă este auto-dual. Prin urmare, pe lângă această funcție, este suficient să lăsăm în sistem doar trei funcții: neliniare, nonmonotonice sau o funcție care nu păstrează 1 sau o funcție non-auto-duală.
Următorul exemplu arată că constanta 4 nu poate fi coborâtă.
Exemplu 7. Luați în considerare un sistem de funcții.
Să compilați tabelul Post pentru acest sistem:
Se poate observa din tabel că acest sistem este complet și ireductibil, deoarece
Întrebări pentru autocontrol
1 Care sistem de funcții booleene este numit complet?
2 Care este închiderea setului de funcții booleene?
3 Ce clasă de funcții booleene este numită închisă?
4 Definiți cele cinci clase importante închise.
5 Indicați teorema de completitudine.
6 Formulați algoritmul Post.
7 Care sistem de funcții booleene este numit ireductibil?
8 Care este numărul maxim de funcții într-un sistem complet ireductibil de funcții booleene?
Articole similare
Trimiteți-le prietenilor: