Definiția. Un sistem de funcții booleene (f1, f2, fn) se spune că este complet. dacă orice funcție de comutare poate fi reprezentată de o suprapunere a funcțiilor unui sistem dat.
Pentru ca sistemul funcțiilor booleene să fie complet, este necesar și suficient ca acesta să conțină:
- cel puțin o funcție care nu păstrează zero constant;
- cel puțin o funcție care nu păstrează constanta;
- cel puțin o funcție care nu este liniară;
- cel puțin o funcție care nu este monotonă;
- cel puțin o funcție care nu este auto-duală.
Acesta este criteriul pentru completitudinea sistemului.
Sistem de funcții 1. f2. fn>, care este completă, se numește o bază.
O bază minimă este o bază pentru care îndepărtarea cel puțin a uneia dintre funcțiile fi. formând baza, transformă sistemul de funcții 1. f2. fn> incomplet.
Vom lua în considerare funcțiile care depind de n argumente. Numărul de funcții diferite este.
Un sistem complet trivial constă în toate funcțiile.
Funcțiile inversiunii, disjuncției și conjuncțiilor formează un sistem complet. Aceasta rezultă din teorema principală care afirmă că orice funcție booleană poate fi scrisă sub forma unei disjuncții a mintermelor (sau conjuncțiilor maxstemurilor).
bază nu este minimă, deoarece poate fi redusă prin aruncarea din el / \ sau \ /. Acest lucru rezultă din formulele de Morgan:
Bazele sunt minime.
a) este un sistem complet funcțional (rezultă din teorema lui Zhegalkin);
b) funcția de implicare și constanta 1:;
c) funcția de implicare și inversiune. .
Un exemplu. Dovedeste ca functia Schaeffer formeaza un sistem complet
Dovada. Vom exprima ¯ și / în termenii funcției Schaeffer:
Deoarece este un sistem complet, afirmația este dovedită.
Un exemplu. Exprimăm funcția folosind doar funcția Schaeffer:
.
Un exemplu. Dovedește că A ↓ B formează un sistem complet funcțional
Deoarece inversiunea și disjuncția sunt exprimate doar prin intermediul funcției "săgeată Pirs" și reprezintă un sistem complet funcțional, atunci A ↓ B este un sistem complet funcțional.
Un exemplu. Exprimați funcția folosind doar funcția "Pârghie săgeată":
Selectați un sistem complet funcțional conform tabelului.
Inversiunea - nu păstrează 0 și 1 și nu este monotonă, nu este auto-dublă, nu este liniară.
Ambele funcții sunt auto-duale. sistem
Se poate demonstra că din orice sistem complet de funcții se poate alege un subsistem complet care să conțină nu mai mult de patru funcții. lăsa
Dacă fk (11 ... 1) = 1, atunci aceeași funcție nu este auto-duală, deoarece fk (00 ... 0) ≠ 0.
Dacă fk (11 ... 1) = 0, atunci aceeași funcție nu păstrează constanta 1 și nu este monotonică.
Prin atașarea celor trei funcții lipsă la fk, obținem un sistem constând din nu mai mult de patru funcții.
Un exemplu. Pentru a crea o bază minimă, inclusiv funcția
Bazele 8, f11> și 11, f14> nu sunt minime, deoarece f8 și f11 sunt funcționale complete.
Un exemplu. Exprimați funcția în sistem 0, f11>:
Pentru transformări folosim sistemul ca principal: