Konjunktivni normalni oblik logičke funkcije. Normalni oblici logičkih funkcija

Konjunktivni normalni oblik je pogodan za automatsko dokazivanje teorema. Bilo koja Booleova formula može se svesti na CNF. Za to možete koristiti: zakon dvostruke negacije, de Morganov zakon, distributivnost.

Enciklopedijski YouTube

• 1 / 5

  Formule u KNF-u:

  ¬ A ∧ (B ∨ C), (\displaystyle \neg A\klin (B\vee C),) (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E) , (\displaystyle (A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge ( D\vee\neg E),) A∧B. (\displaystyle A\klin B.)

  Formule ne u KNF:

  ¬ (B ∨ C) , (\displaystyle \neg (B\vee C),) (A ∧ B) ∨ C , (\displaystyle (A\wedge B)\vee C,) A ∧ (B ∨ (D ∧ E)) . (\displaystyle A\klin (B\vee (D\klin E)).)

  Ali ove 3 formule koje nisu u CNF-u ekvivalentne su sljedećim formulama u CNF-u:

  ¬ B ∧ ¬ C , (\displaystyle \neg B\klin \neg C,) (A ∨ C) ∧ (B ∨ C) , (\displaystyle (A\vee C)\wedge (B\vee C),) A ∧ (B ∨ D) ∧ (B ∨ E) . (\displaystyle A\klin (B\vee D)\klin (B\vee E).)

  Izgradnja CNF

  Algoritam za konstruiranje CNF

  1) Riješite se svih logičkih operacija sadržanih u formuli, zamjenjujući ih osnovnima: konjunkcija, disjunkcija, negacija. To se može učiniti pomoću ekvivalentnih formula:

  A → B = ¬ A ∨ B , (\displaystyle A\rightarrow B=\neg A\vee B,) A ↔ B = (¬ A ∨ B) ∧ (A ∨ ¬ B) . (\displaystyle A\leftrightarrow B=(\neg A\vee B)\wedge (A\vee \neg B).)

  2) Zamijenite znak negacije koji se odnosi na cijeli izraz s predznakom negacije koji se odnosi na pojedine iskaze varijabli na temelju formula:

  ¬ (A ∨ B) = ¬ A ∧ ¬ B , (\displaystyle \neg (A\vee B)=\neg A\klin \neg B,) ¬ (A ∧ B) = ¬ A ∨ ¬ B . (\displaystyle \neg (A\klin B)=\neg A\vee \neg B.)

  3) Riješite se dvostrukih negativa.

  4) Primijeniti, ako je potrebno, svojstva distributivnosti i formule apsorpcije na operacije konjunkcije i disjunkcije.

  Primjer konstrukcije CNF

  Prenesimo formulu na CNF

  F = (X → Y) ∧ ((¬ Y → Z) → ¬ X) . (\displaystyle F=(X\desna strelica Y)\klin ((\neg Y\desna strelica Z)\desna strelica \neg X).)

  Transformirajmo formulu F (\displaystyle F) na formulu koja ne sadrži → (\displaystyle \rightarrow ):

  F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ Y ∨ Z) ​​​​∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\klin (\neg (\neg Y\rightarrow Z)\vee \neg X)=(\neg X\vee Y)\klin (\neg (\neg \ neg Y\vee Z)\vee \neg X).)

  U dobivenoj formuli prenosimo negaciju na varijable i smanjujemo dvostruke negative:

  F = (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\wedge ((\neg Y\wedge \neg Z)\vee \neg X).)

  Na primjer, sljedeća formula je napisana u 2-CNF:

  (A ∨ B) ∧ (¬ B ∨ C) ∧ (B ∨ ¬ C) . (\stil prikaza (A\ili B)\zemlja (\neg B\ili C)\zemlja (B\ili \neg C).)

  Disjunktivni i konjunktivni normalni oblici iskazne algebre. Za svaku funkciju propozicijske logike može se konstruirati tablica istinitosti. Inverzni problem je također uvijek rješiv. Uvedimo nekoliko definicija.

  Elementarni veznici (konjunkti) nazivaju se konjunkcije varijabli ili njihove negacije u kojima se svaka varijabla pojavljuje najviše

  jednom.

  Disjunktivni normalni oblik(DNF) je formula koja ima oblik disjunkcije elementarnih konjunkcija.

  Elementarne disjunkcije (disjunkcije) nazivaju se disjunkcije varijabli sa ili bez negacija.

  Konjunktivni normalni oblik(CNF) je formula koja ima oblik konjunkcije elementarnih disjunkcija.

  Za svaku funkciju propozicionalne algebre može se pronaći skup disjunktivnih i konjunktivnih normalnih formi.

  Algoritam za konstrukciju DNF-a:

  1. Idite na Booleove operacije koristeći ekvivalentne transformacijske formule.

  2. Idite na formule s bliskim negacijama, odnosno na formule u kojima se negacije ne nalaze iznad varijabli - primijenite De Morganove zakone.

  3. Otvorite zagrade - primijenite zakone distributivnosti.

  4. Uzimajte termine koji se ponavljaju jedan po jedan - zakon idempotencije.

  5. Primijeniti zakone apsorpcije i poluapsorpcije.

  Primjer 6. Pronađite DNF formule: .

  U Booleovoj algebri to je točno načelo dvojnosti. To je kako slijedi.

  Funkcija se zove dual na funkciju if . Oni. Da bismo pronašli funkciju dualnu na zadanu, potrebno je konstruirati negaciju funkcije iz negacija argumenata.

  Primjer 7. Pronađite funkciju dualnu na .

  Među elementarnim funkcijama logičke algebre, 1 je dualna na 0 i obrnuto, x je dualna na x, dualna na , dualna i obrnuto.

  Ako u formuli F 1 koja predstavlja funkciju zamijenimo sve veznike

  na disjunkciji, disjunkciji na konjunkciji, 1 na 0, 0 na 1, tada dobivamo formulu F * koja predstavlja funkciju * ​​dualnu na .

  Konjunktivna normalna forma (CNF) je dualni koncept za DNF, tako da se lako može konstruirati prema sljedećoj shemi:

  Primjer 8. Pronađite formulu CNF: .

  Koristeći rezultat primjera 6, imamo

  Perfektni disjunktivni i perfektni konjunktivni normalni oblici. U svakom od tipova normalnih oblika (disjunktivnih i konjunktivnih) razlikuje se klasa perfektnih oblika SDNF i SCNF.

  Savršena elementarna konjunkcija logički je umnožak svih varijabli sa ili bez negacije, a svaka se varijabla u umnošku pojavljuje samo jednom.

  Svaki DNF može se svesti na SDNF razdvajanjem konjunkcija koje ne sadrže sve varijable, tj. dodavanjem varijable koja nedostaje x i se množi prema zakonu distribucije

  Primjer 9. Pronađite SDNF za DNF primjera 6

  Savršena elementarna disjunkcija je logički zbroj svih varijabli sa ili bez negacija, a svaka varijabla je uključena u zbroj samo jednom.

  Svaki CNF može se reducirati na SCNF dodavanjem konjunkcijskog člana koji ne sadrži nikakvu varijablu X i pomoću konjunkcije i primjenom zakona distribucije

  Primjer 10. Donesite KNF u SKNF:

  Da biste konstruirali SCNF, možete koristiti dijagram

  Primjer 11. Pronađite SCNF za formulu primjera 6.

  Svaka funkcija ima SDNF i, štoviše, jedinstven. Svaka funkcija ima SCNF i, štoviše, jedinstven.

  Jer SDNF i SKNF jedinstveno su definirani formulama; mogu se konstruirati pomoću tablice istinitosti formule.

  Za konstruiranje SDNF-a potrebno je odabrati retke u kojima F ima vrijednost 1 i za njih napisati savršene elementarne konjunkcije. Ako je vrijednost varijable u željenom retku tablice istine jednaka jedinici, tada se u savršenoj konjunkciji uzima bez negacije, ako je nula, onda s negacijom. Tada se savršeni veznici (njihov broj je jednak broju jedinica u tablici) povezuju disjunkcijskim znakovima.

  Za konstrukciju SCNF pomoću tablice istinitosti potrebno je u njoj odabrati retke u kojima je F = 0, te zapisati savršene elementarne disjunkcije, a zatim ih povezati konjunkcijskim znakovima. Ako u traženom retku tablice istinitosti (F=0) vrijednost varijable odgovara nuli, tada se u savršenoj klauzuli uzima bez negacije, ako je jedinica, onda s negacijom.

  Primjer 12. Pronađite SDNF i SCNF pomoću tablice istine za formulu primjera 6.

  Tablica 14 prikazuje samo konačnu vrijednost F=10101101. Trebali biste sami provjeriti valjanost ove izjave izradom detaljne tablice istinitosti.

  Tablica 14

  x	g	z

  Definicija 1.Konjunktivni monom (elementarna konjunkcija) varijabli je konjunkcija tih varijabli ili njihovih negacija.

  Na primjer, je elementarna konjunkcija.

  Definicija 2.Disjunktivni monom (elementarna disjunkcija) od varijabli je disjunkcija tih varijabli ili njihovih negacija.

  Na primjer, je elementarna disjunkcija.

  Definicija 3. Formula koja je ekvivalentna zadanoj formuli propozicione algebre i disjunkcija je elementarnih konjunktivnih monoma naziva se disjunktivni normalni oblik(DNF) ove formule.

  Na primjer,– DNF.

  Definicija 4. Formula koja je ekvivalentna zadanoj formuli propozicione algebre i konjunkcija je elementarnih disjunktivnih monoma naziva se konjunktivni normalni oblik(CNF) ove formule.

  Na primjer, – KNF.

  Za svaku formulu propozicionalne algebre može se pronaći skup disjunktivnih i konjunktivnih normalnih formi.

  Algoritam za konstruiranje normalnih formi

  Koristeći ekvivalente logičke algebre, zamijenite sve osnovne operacije u formuli: konjunkcija, disjunkcija, negacija:

  Riješite se dvostrukih negativa.

  Primijenite, ako je potrebno, svojstva distributivnosti i formule apsorpcije na operacije konjunkcije i disjunkcije.

  2.6. Perfektni disjunktivni i perfektni konjunktivni normalni oblici

  Bilo koja Booleova funkcija može imati mnoge reprezentacije u obliku DNF i CNF. Među tim prikazima posebno mjesto zauzimaju savršeni DNF (SDNF) i savršeni CNF (SCNF).

  Definicija 1. Savršeni disjunktivni normalni oblik(SDNF) je DNF u kojem svaki konjunktivni monom sadrži svaku varijablu iz skupa točno jednom, bilo samu sebe ili svoju negaciju.

  Strukturno, SDNF za svaku formulu propozicijske algebre svedenu na DNF može se definirati na sljedeći način:

  Definicija 2. Savršeni disjunktivni normalni oblik(SDNF) formule iskazne algebre naziva se njezin DNF, koji ima sljedeća svojstva:

  Definicija 3. Perfektni konjunktivni normalni oblik(SCNF) je CNF u kojem svaki disjunktivni monom sadrži svaku varijablu iz skupa točno jednom, a pojavljuje se ili sam ili njegova negacija.

  Strukturno, SCNF za svaku formulu propozicijske algebre svedenu na CNF može se definirati na sljedeći način.

  Definicija 4. Perfektni konjunktivni normalni oblik(SCNF) dane formule propozicionalne algebre naziva se CNF koja zadovoljava sljedeća svojstva.

  Teorem 1. Svaka Booleova funkcija varijabli koja nije identično lažna može se predstaviti u SDNF-u, i to na jedinstven način.

  Metode za pronalaženje SDNF

  1. metoda

  2. metoda

  odaberite retke u kojima formula ima vrijednost 1;

  sastavljamo disjunkciju konjunkcija pod uvjetom da ako je varijabla uključena u konjunkciju s vrijednošću 1, tada zapisujemo tu varijablu, ako s vrijednošću 0, onda njenu negaciju. Dobivamo SDNF.

  Teorem 2. Svaka Booleova funkcija varijabli koja nije identično istinita može se predstaviti u SCNF-u, i to na jedinstven način.

  Metode za pronalaženje SCNF

  1. metoda– koristeći ekvivalentne transformacije:

  2. metoda– korištenje tablica istinitosti:

  odaberite retke u kojima formula ima vrijednost 0;

  sastavljamo konjunkciju disjunkcija pod uvjetom da ako je varijabla uključena u disjunkciju s vrijednošću 0, tada zapisujemo tu varijablu; ako s vrijednošću 1, onda njezinu negaciju. Dobivamo SKNF.

  Primjer 1. Konstruirajte CNF funkcije.

  Riješenje

  Eliminirajmo veznik "" koristeći zakone transformacije varijabli:

  = /de Morganovi zakoni i dvostruka negacija/ =

  /distribucijski zakoni/ =

  Primjer 2. Daj formulu DNF-u.

  Riješenje

  Izrazimo logičke operacije pomoću i:

  = /klasificirajmo negaciju kao varijable i smanjimo dvostruke negative/ =

  = /zakon distributivnosti/ .

  Primjer 3. Napišite formulu u DNF i SDNF.

  Riješenje

  Koristeći se zakonima logike, ovu formulu svodimo na oblik koji sadrži samo disjunkcije elementarnih konjunkcija. Rezultirajuća formula bit će željeni DNF:

  Da bismo konstruirali SDNF, napravimo tablicu istine za ovu formulu:

  Označavamo one retke tablice u kojima formula (posljednji stupac) ima vrijednost 1. Za svaki takav redak ispisujemo formulu koja je istinita na skupu varijabli ovog retka:

  linija 1: ;

  redak 3: ;

  redak 5: .

  Disjunkcija ove tri formule poprimit će vrijednost 1 samo na skupovima varijabli u redovima 1, 3, 5, i stoga će biti željena savršena disjunktivna normalna forma (PDNF):

  Primjer 4. Donesite formulu u SKNF na dva načina:

  a) pomoću ekvivalentnih transformacija;

  b) pomoću tablice istinitosti.

  Riješenje:

  Transformirajmo drugu elementarnu disjunkciju:

  Formula izgleda ovako:

  b) sastavite tablicu istinitosti za ovu formulu:

  Označavamo one retke tablice u kojima formula (posljednji stupac) ima vrijednost 0. Za svaki takav redak ispisujemo formulu koja je istinita na skupu varijabli ovog retka:

  redak 2: ;

  redak 6: .

  Konjunkcija ovih dviju formula poprimit će vrijednost 0 samo na skupovima varijabli u recima 2 i 6, te će stoga biti željena savršena konjunktivna normalna forma (PCNF):

  Pitanja i zadaci za samostalno rješavanje

  1. Pomoću ekvivalentnih transformacija svedite formule na DNF:

  2. Pomoću ekvivalentnih transformacija dovedite formule u CNF:

  3. Koristeći drugi zakon distribucije, pretvorite DNF u CNF:

  A) ;

  4. Pretvorite dane DNF-ove u SDNF-ove:

  5. Pretvorite dani CNF u SCNF:

  6. Za zadane logičke formule konstruirajte SDNF i SCNF na dva načina: korištenjem ekvivalentnih transformacija i korištenjem tablice istinitosti.

  b) ;

  Jednostavan veznik nazvao veznik jedan ili nekoliko varijable, na ovaj svaki varijabla sastaje se Ne više jedan puta (ili sebe, ili nju negacija).

  Na primjer, je jednostavna konjunkcija,

  Disjunktivna normalan oblik(DNF) nazvao disjunkcija jednostavan veznici.

  Na primjer, izraz je DNF.

  Savršen disjunktivan normalan oblik(SDNF) nazvao kao ovo disjunktivan normalan oblik, na koji V svaki veznik uključeno svi varijable dano popis (ili se, ili njihov poricanje), i V jedan I volumen istiu redu.

  Na primjer, izraz je DNF, ali ne i SDNF. Izraz je SDNF.

  Slične definicije (sa zamjenom konjunkcije disjunkcijom i obrnuto) vrijede za CNF i SKNF. Navedimo točnu formulaciju.

  Jednostavan disjunkcija nazvao disjunkcija jedan ili nekoliko varijable, na ovaj svaki varijabla uključeno Ne više jedan puta (ili sebe, ili nju negacija).Na primjer, izraz je jednostavna disjunkcija,

  Vezivni normalan oblik(KNF) nazvao veznik jednostavan disjunkcije(na primjer, izraz je CNF).

  Savršena konjunktivna normalna forma (PCNF) je CNF u kojoj svaka jednostavna disjunkcija uključuje sve varijable danog popisa (bilo same sebe ili njihove negacije), i to istim redoslijedom.

  Na primjer, izraz je SKNF.

  Predstavimo algoritme za prijelaz iz jednog oblika u drugi. Naravno, u određenim slučajevima (uz određeni kreativni pristup) korištenje algoritama može biti zahtjevnije od jednostavnih transformacija pomoću određene vrste danog oblika:

  a) prijelaz iz DNF u CNF

  Algoritam za ovaj prijelaz je sljedeći: stavljamo dvije negacije iznad DNF-a i, koristeći De Morganova pravila (bez dodirivanja gornje negacije), reduciramo negaciju DNF-a natrag na DNF. U ovom slučaju morate otvoriti zagrade koristeći pravilo apsorpcije (ili Blakeovo pravilo). Negacija (gornja) rezultirajućeg DNF-a (opet prema de Morganovom pravilu) odmah nam daje CNF:

  Imajte na umu da se CNF također može dobiti iz izvornog izraza ako ga izbacimo na izvan zagrada;

  b) prijelaz s CNF na DNF

  Ovaj prijelaz se izvodi jednostavnim otvaranjem zagrada (opet se koristi pravilo apsorpcije)

  Tako smo dobili DNF.

  Obrnuti prijelaz (iz SDNF u DNF) povezan je s problemom minimiziranja DNF. O tome će se detaljnije govoriti u odjeljku. 5, ovdje ćemo pokazati kako pojednostaviti DNF (ili SDNF) prema Blakeovom pravilu. Ova vrsta DNF-a naziva se skraćeno DNF;

  c) skraćenica DNF (ili SDNF) po Pravilo Blake

  Primjena ovog pravila sastoji se od dva dijela:

  Ako među disjunktnim članovima u DNF postoje članovi , tada cijeloj disjunkciji dodajemo pojam DO 1 DO 2. Ovu operaciju izvodimo nekoliko puta (po mogućnosti uzastopno ili istovremeno) za sve moguće parove članova, a zatim primjenjujemo normalnu apsorpciju;

  Ako je dodani pojam već sadržan u DNF-u, tada se može potpuno odbaciti, na primjer,

  ili

  Naravno, skraćeni DNF nije jednoznačno definiran, ali svi sadrže isti broj slova (npr. postoji DNF , nakon primjene Blakeovog pravila na njega, može se doći do DNF ekvivalenta ovome):

  c) prijelaz s DNF na SDNF

  Ako nekoj jednostavnoj konjunkciji nedostaje varijabla, na primjer, z, umetnite izraz u njega, a zatim otvorite zagrade (ne pišemo ponavljajuće disjunktne članove). Na primjer:

  d) prijelaz iz KNF u SKNF

  Ovaj prijelaz se provodi na način sličan prethodnom: ako jednostavnoj disjunkciji nedostaje neka varijabla (npr. z, zatim mu dodamo izraz (ovo ne mijenja samu disjunkciju), nakon čega otvaramo zagrade pomoću zakona distribucije):

  Dakle, SKNF je dobiven iz CNF.

  Imajte na umu da se minimalni ili smanjeni CNF obično dobiva iz odgovarajućeg DNF-a.

  Standardna osnova. Elementarne formule su literali. Elementarna konjunkcija (disjunkcija). Disjunktivni (konjunktivni) normalni oblik i svršeni oblik. Teorem: svaka Booleova funkcija različita od 0 (od 1) može se prikazati u obliku SDNF (SCNF). Cjelovitost standardne osnove. Primjeri potpunih baza: Zhegalkinova baza, Schaefferov potez, Peirceova strelica.

  Standardna osnova je skup od tri osnovne operacije Booleove algebre: zbrajanje (unija), množenje (presjek) i negacija.

  Ovdje ćemo nazvati doslovan varijablu x ili njezinu negaciju x i označiti xˆ. Booleov presjek nekoliko literala definiranih različitim varijablama, tj. izraz oblika X = xˆ 1 xˆ 2 . . . xˆ l, tzv elementarna konjunkcija . Zahtjev da sve varijable budu različite određen je sljedećim. Ako konjunkcija uključuje nekoliko identičnih literala, tada je zbog komutativnosti, asocijativnosti i idempotencije konjunkcije moguće, prelazeći na ekvivalentnu formulu, ostaviti samo jedan literal (npr. x 1 x 1 = x 1). Ako konjunkcija uključuje varijablu i njezinu negaciju, tada je formula ekvivalentna konstanti 0, budući da je x x = 0 i za svaku formulu Y imamo Y x x = 0.

  Disjunkcija nekoliko elementarnih konjunkcija naziva se disjunktivni normalni oblik , ili DNF . Na primjer,

  x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5 .

  Ako je sastav varijabli u svakoj elementarnoj konjunkciji danog DNF-a isti, tada se DNF naziva savršen . Navedeni primjer je DNF koji nije savršen. Naprotiv, formula

  x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4

  postoji savršeni oblik.

  Budući da su u Booleovoj algebri zbrajanje i množenje simetrične operacije i zbrajanje uvijek možete interpretirati kao množenje, a množenje kao zbrajanje, postoji dvojni koncept - konjunktivni normalni oblik (KNF ), koja je konjunkcija elementarnih disjunkcija, i svršeni konjunktivni oblik (SKNF ). Iz principa dualnosti za simetrične poluprstenove slijedi da se na svaku tvrdnju o DNF odgovara dualnom tvrdnjom o CNF, koja se dobiva zamjenom zbrajanja (disjunkcije) množenjem, množenja (konjunkcije) zbrajanjem, konstante 0 s konstantom 1, konstante 1 s konstantom 0, odnos reda s dualnim (inverznim) redom. Stoga ćemo se dalje fokusirati na proučavanje samo DNF-a.

  Teorem 1.4. Bilo koja Booleova funkcija osim konstante 0 može se predstaviti kao SDNF.

  ◀Dogovorimo se da pod x σ podrazumijevamo formulu x ako je σ = 1, a formulu x ako je σ = 0. Neka funkcija f(y 1 , . . . , y n) poprimi vrijednost 1 na vektoru (t 1 , . . . , t n ) (takav se vektor naziva sastavna jedinica ). Tada elementarna konjunkcija također poprima vrijednost 1 na ovom skupu, ali nestaje na svim ostalim n-dimenzionalnim Booleovim vektorima. Razmotrite formulu

  u kojem se zbroj (unija) proteže na sve one skupove (t 1, . . . , t n) vrijednosti argumenata na kojima dana funkcija ima vrijednost 1. Imajte na umu da skup takvih skupova nije prazan, pa je zbroj sadrži barem jedan član.

  Lako je vidjeti da formula Φ postaje 1 za one i samo one vrijednosti varijabli za koje dotična funkcija postaje 1. To znači da formula Ψ predstavlja funkciju f.

  Korolar 1.1. Standardna osnova je gotova.

  ◀ Doista, ako funkcija nije konstanta 0, tada se može prikazati ili u obliku SDNF-a, što je formula preko standardne baze. Konstanta 0 može se prikazati, na primjer, formulom f(x 1, x 2, . . . , x n) = x 1 x 1.

  Primjer 1.2. Promotrimo funkciju triju varijabli m(x 1, x 2, x 3) (tablica 1.4), tzv. većinska funkcija ̆. Ova funkcija daje vrijednost 1 ako više od polovice njezinih argumenata ima vrijednost 1. Stoga se često naziva funkcija glasanja. Izgradimo SDNF za to.

  Cjelovitost standardne osnove omogućuje odabir drugih cjelovitih sustava funkcija. Potpunost skupa F može se utvrditi iz sljedećih razmatranja. Pretpostavimo da se svaka od tri standardne poslovne funkcije može predstaviti formulom nad F . Tada će prema teoremu 1.3 identitet F biti potpun.

  Primjer 1.3. Poziva se skup operacija modula 2 zbrajanja, množenja i konstante 1 Zhegalkinova osnova . Zbrajanje po modulu 2 i množenje osnovne su operacije Z2 prstena, a izrazi sastavljeni pomoću njih su polinomi nad Z2 prstenom. Konstanta 1 u ovom slučaju je neophodna za pisanje slobodnog člana. Budući da je xx = x, tada svi faktori u polinomu imaju stupanj 1. Stoga, kada pišete polinom, možete bez pojma stupnja. Primjeri formula nad Zhegalkinovom osnovom:

  xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

  Svaka takva formula naziva se Zhegalkin polinom. Zapravo, Zhegalkinov polinom je polinom nad prstenom Z2.

  Nije teško konstruirati formule preko Zhegalkinove baze, koje predstavljaju operacije zbrajanja i negacije standardne baze (množenje dviju baza je uobičajeno):

  x+y=x⊕y⊕xy, x =x⊕1.

  Stoga je Zhegalkinova osnova kompletan set.
  Može se pokazati da je za bilo koju Booleovu funkciju Zhegalkinov polinom jedinstveno definiran

  (točnije do reda pojmova). Koeficijenti Zhegalkinovog polinoma s malim brojem varijabli mogu se pronaći metodom neodređenih koeficijenata.

  Primjer 1.4. Razmotrimo skup jedne funkcije - Schaefferov udar*. Ovaj skup je potpun, kao što slijedi iz sljedećih lako provjerljivih identiteta:

  x =x|x, xy=x|y =(x|y)|(x|y), x+y=x |y =(x|x)|(y|y).

  Primjer 1.5. Osnova koja se sastoji od jedne funkcije, Peirceove strelice, također je dovršena. Test za ovo sličan je slučaju Schaefferovog moždanog udara. Međutim, ovaj se zaključak može izvesti i na temelju načela dualnosti za simetrične poluprstenove.

  *Schaefferov potez je binarna, ali ne asocijativna operacija. Stoga, kada koristite infiks formu, trebate biti oprezni: rezultat ovisi o redoslijedu operacija. U tom slučaju preporuča se eksplicitno naznačiti redoslijed operacija pomoću zagrada, na primjer, napisati (x | y) | z, a ne x | y | z, iako su oba oblika ekvivalentna.