Konjunktívna normálna forma logickej funkcie. Normálne formy logických funkcií

Konjunktívna normálna forma je vhodná na automatické dokazovanie teorémov. Akýkoľvek booleovský vzorec možno zredukovať na CNF. Na to môžete použiť: zákon dvojitej negácie, de Morganov zákon, distributivita.

Encyklopedický YouTube

• 1 / 5

  Vzorce v KNF:

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

  Vzorce nie v KNF:

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

  Ale tieto 3 vzorce, ktoré nie sú v CNF, sú ekvivalentné nasledujúcim vzorcom v CNF:

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

  Výstavba CNF

  Algoritmus na konštrukciu CNF

  1) Zbavte sa všetkých logických operácií obsiahnutých vo vzorci a nahraďte ich základnými: konjunkcia, disjunkcia, negácia. To možno vykonať pomocou ekvivalentných vzorcov:

  A → B = ¬ A ∨ B , (\displaystyle A\arrowarrow 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) Nahraďte znamienko negácie týkajúce sa celého výrazu znamienkami negácie, ktorá sa vzťahuje na jednotlivé výroky premennej na základe vzorcov:

  ¬ (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) Zbavte sa dvojitých negatívov.

  4) Ak je to potrebné, aplikujte vlastnosti distribučných a absorpčných vzorcov na operácie konjunkcie a disjunkcie.

  Príklad konštrukcie CNF

  Prenesme vzorec do CNF

  F = (X → Y) ∧ ((¬ Y → Z) → ¬ X) . (\displaystyle F=(X\šípka vpravo Y)\klin ((\neg Y\šípka vpravo Z)\šípka vpravo \neg X).)

  Poďme transformovať vzorec F (\displaystyle F) na vzorec, ktorý neobsahuje → (\displaystyle \rightarrow ):

  F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ Y ∨ Z) ​​​​∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\klin (\neg (\neg Y\šípka vpravo Z)\vee \neg X)=(\neg X\vee Y)\klin (\neg (\neg \ zápor Y\vee Z)\neg \neg X).)

  Vo výslednom vzorci prenesieme negáciu na premenné a znížime dvojité zápory:

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

  Napríklad nasledujúci vzorec je napísaný v 2-CNF:

  (A ∨ B) ∧ (¬ B ∨ C) ∧ (B ∨ ¬ C) . (\displaystyle (A\alebo B)\land (\neg B\lor C)\land (B\alebo \neg C).)

  Disjunktívne a konjunktívne normálne formy výrokovej algebry. Pre každú výrokovú logickú funkciu možno zostaviť pravdivostnú tabuľku. Inverzný problém je tiež vždy riešiteľný. Uveďme niekoľko definícií.

  Elementárne konjunkcie (spojky) sa nazývajú konjunkcie premenných alebo ich negácie, v ktorých sa každá premenná vyskytuje najviac

  raz.

  Disjunktívna normálna forma(DNF) je vzorec, ktorý má formu disjunkcie elementárnych spojok.

  Elementárne disjunkcie (disjunkcie) sa nazývajú disjunkcie premenných s negáciami alebo bez nich.

  Konjunktívna normálna forma(CNF) je vzorec, ktorý má formu konjunkcie elementárnych disjunkcií.

  Pre každú funkciu výrokovej algebry možno nájsť množinu disjunktívnych a konjunktívnych normálnych foriem.

  Algoritmus na zostavenie DNF:

  1. Prejdite na Booleovské operácie pomocou ekvivalentných transformačných vzorcov.

  2. Prejdite na vzorce s tesnými negáciami, teda na vzorec, v ktorom sa negácie nenachádzajú vyššie ako nad premennými – aplikujte De Morganove zákony.

  3. Otvorte zátvorky - aplikujte zákony distributivity.

  4. Vezmite si opakujúce sa pojmy jedenkrát za sebou – zákon idempotencie.

  5. Aplikujte zákony absorpcie a polovičnej absorpcie.

  Príklad 6. Nájdite vzorce DNF: .

  V Booleovej algebre je to pravda princíp duality. Je to nasledovné.

  Funkcia sa volá dvojaký do funkcie ak . Tie. Na nájdenie duálnej funkcie k danej je potrebné zostrojiť negáciu funkcie z negácií argumentov.

  Príklad 7. Nájdite funkciu dual to .

  Medzi elementárnymi funkciami algebry logiky je 1 duálna k 0 a naopak, x je duálna na x, duálna na , duálna a naopak.

  Ak vo vzorci F 1 reprezentujúcom funkciu nahradíme všetky spojky

  na disjunkcii, disjunkcii na konjunkcii, 1 na 0, 0 na 1, potom dostaneme vzorec F * reprezentujúci funkciu * duál na .

  Konjunktívna normálna forma (CNF) je duálny koncept pre DNF, takže sa dá ľahko skonštruovať podľa nasledujúcej schémy:

  Príklad 8. Nájdite vzorec CNF: .

  Použitím výsledku z príkladu 6 máme

  Dokonalé disjunktívne a dokonalé konjunktívne normálne formy. V každom z typov normálnych foriem (disjunktívne a konjunktívne) možno rozlíšiť triedu dokonalých foriem SDNF a SCNF.

  Dokonalá elementárna konjunkcia je logickým súčinom všetkých premenných s negáciou alebo bez negácie a každá premenná sa v súčine vyskytuje iba raz.

  Akékoľvek DNF možno redukovať na SDNF rozdelením konjunkcií, ktoré neobsahujú všetky premenné, t.j. sčítaním za chýbajúcu premennú sa x i vynásobí pomocou distributívneho zákona

  Príklad 9. Nájdite SDNF pre DNF z príkladu 6

  Dokonalá elementárna disjunkcia je logický súčet všetkých premenných s negáciami alebo bez nich a každá premenná je zahrnutá do súčtu iba raz.

  Akýkoľvek CNF môže byť redukovaný na SCNF pridaním spojenia, ktoré neobsahuje žiadnu premennú Xi spojením a použitím distributívneho zákona

  Príklad 10. Prineste KNF do SKNF:

  Na zostavenie SCNF môžete použiť diagram

  Príklad 11. Nájdite SCNF pre vzorec z príkladu 6.

  Každá funkcia má SDNF a navyše jedinečný. Každá funkcia má SCNF a navyše jedinečný.

  Pretože SDNF a SKNF sú jednoznačne definované vzorcami; možno ich zostaviť pomocou pravdivostnej tabuľky vzorca.

  Na zostavenie SDNF je potrebné vybrať riadky, v ktorých má F hodnotu 1 a zapísať pre ne dokonalé elementárne spojky. Ak je hodnota premennej v požadovanom riadku pravdivostnej tabuľky rovná jednej, potom sa v dokonalej konjunkcii berie bez negácie, ak je nula, tak s negáciou. Potom dokonalé spojky (ich počet sa rovná počtu jednotiek v tabuľke) sú spojené znamienkami disjunkcie.

  Na zostavenie SCNF pomocou pravdivostnej tabuľky je potrebné vybrať v nej riadky, kde F = 0, zapísať dokonalé elementárne disjunkcie a potom ich spojiť znamienkami konjunkcie. Ak v požadovanom riadku pravdivostnej tabuľky (F=0) hodnota premennej zodpovedá nule, tak v dokonalej vete sa berie bez negácie, ak je jedna, tak s negáciou.

  Príklad 12. Nájdite SDNF a SCNF pomocou pravdivostnej tabuľky pre vzorec z príkladu 6.

  Tabuľka 14 uvádza len konečnú hodnotu F=10101101. Platnosť tohto tvrdenia by ste si mali overiť sami zostavením podrobnej pravdivostnej tabuľky.

  Tabuľka 14

  X	r	z

  Definícia 1.Spojkový jednočlen (elementárna spojka) premenných je spojenie týchto premenných alebo ich negácií.

  Napríklad, je elementárna konjunkcia.

  Definícia 2.Disjunktívny monomiál (elementárna disjunkcia) od premenných je disjunkcia týchto premenných alebo ich negácie.

  Napríklad, je elementárna disjunkcia.

  Definícia 3. Vzorec, ktorý je ekvivalentný danému vzorcu výrokovej algebry a je disjunkciou elementárnych konjunktívnych monočlenov, sa nazýva disjunktívna normálna forma(DNF) tohto vzorca.

  Napríklad,– DNF.

  Definícia 4. Vzorec, ktorý je ekvivalentný danému vzorcu výrokovej algebry a je konjunkciou elementárnych disjunktívnych monočlenov, sa nazýva konjunktívna normálna forma(CNF) tohto vzorca.

  Napríklad, – KNF.

  Pre každý vzorec výrokovej algebry možno nájsť množinu disjunktívnych a konjunktívnych normálnych foriem.

  Algoritmus na vytváranie normálnych foriem

  Pomocou ekvivalencií logickej algebry nahraďte všetky základné operácie vo vzorci: konjunkcia, disjunkcia, negácia:

  Zbavte sa dvojitých negatívov.

  Ak je to potrebné, aplikujte vlastnosti distribučných a absorpčných vzorcov na operácie konjunkcie a disjunkcie.

  2.6. Dokonalé disjunktívne a dokonalé konjunktívne normálne formy

  Akákoľvek booleovská funkcia môže mať mnoho reprezentácií vo forme DNF a CNF. Zvláštne miesto medzi týmito reprezentáciami zaujíma dokonalá DNF (SDNF) a dokonalá CNF (SCNF).

  Definícia 1. Dokonalá disjunktívna normálna forma(SDNF) je DNF, v ktorom každý konjunktívny monomiál obsahuje každú premennú z množiny práve raz, buď samú seba, alebo jej negáciu.

  Štrukturálne môže byť SDNF pre každý vzorec výrokovej algebry redukovaný na DNF definovaný takto:

  Definícia 2. Dokonalá disjunktívna normálna forma(SDNF) vzorca výrokovej algebry sa nazýva jeho DNF, ktorý má tieto vlastnosti:

  Definícia 3. Dokonalá konjunktívna normálna forma(SCNF) je CNF, v ktorom každý disjunktívny monomiál obsahuje každú premennú z množiny práve raz a objavuje sa buď sama, alebo jej negácia.

  Štrukturálne môže byť SCNF pre každý vzorec výrokovej algebry redukovaný na CNF definovaný nasledovne.

  Definícia 4. Dokonalá konjunktívna normálna forma(SCNF) daného vzorca výrokovej algebry sa nazýva CNF, ktorý spĺňa nasledujúce vlastnosti.

  Veta 1. Každá booleovská funkcia premenných, ktorá nie je identicky nepravdivá, môže byť reprezentovaná v SDNF, a to jedinečným spôsobom.

  Metódy na nájdenie SDNF

  1. spôsob

  2. spôsob

  vyberte riadky, kde vzorec nadobúda hodnotu 1;

  disjunkciu spojok skladáme pod podmienkou, že ak je premenná zahrnutá do spojky s hodnotou 1, tak túto premennú zapíšeme, ak s hodnotou 0, tak jej negáciu. Dostávame SDNF.

  Veta 2. Každá booleovská funkcia premenných, ktorá nie je identicky pravdivá, môže byť reprezentovaná v SCNF, a to jedinečným spôsobom.

  Metódy na nájdenie SCNF

  1. spôsob– pomocou ekvivalentných transformácií:

  2. spôsob- pomocou pravdivostných tabuliek:

  vyberte riadky, kde má vzorec hodnotu 0;

  konjunkciu disjunkcií skladáme za podmienky, že ak je v disjunkcii zahrnutá premenná s hodnotou 0, tak túto premennú zapíšeme, ak s hodnotou 1, tak jej negáciu. Dostávame SKNF.

  Príklad 1 Zostrojte funkcie CNF.

  Riešenie

  Vylúčme spojku "" pomocou zákonov transformácie premenných:

  = /de Morganove zákony a dvojitá negácia/ =

  /distribučné zákony/ =

  Príklad 2 Dajte vzorec DNF.

  Riešenie

  Vyjadrime logické operácie pomocou a:

  = /zaraďme negáciu medzi premenné a redukujme dvojité zápory/ =

  = /zákon distributivity/ .

  Príklad 3 Napíšte vzorec v DNF a SDNF.

  Riešenie

  Pomocou zákonov logiky zredukujeme tento vzorec na formu obsahujúcu len disjunkcie elementárnych spojok. Výsledný vzorec bude požadovaný DNF:

  Aby sme vytvorili SDNF, vytvorte pravdivostnú tabuľku pre tento vzorec:

  Označíme tie riadky tabuľky, v ktorých má vzorec (posledný stĺpec) hodnotu 1. Pre každý takýto riadok vypíšeme vzorec, ktorý je pravdivý na množine premenných tohto riadku:

  riadok 1: ;

  riadok 3: ;

  riadok 5: .

  Disjunkcia týchto troch vzorcov nadobudne hodnotu 1 iba na množinách premenných v riadkoch 1, 3, 5, a preto bude požadovanou dokonalou disjunktívnou normálnou formou (PDNF):

  Príklad 4. Prineste vzorec do SKNF dvoma spôsobmi:

  a) použitím ekvivalentných transformácií;

  b) pomocou pravdivostnej tabuľky.

  Riešenie:

  Transformujme druhú elementárnu disjunkciu:

  Vzorec vyzerá takto:

  b) zostavte pravdivostnú tabuľku pre tento vzorec:

  Označíme tie riadky tabuľky, v ktorých má vzorec (posledný stĺpec) hodnotu 0. Pre každý takýto riadok vypíšeme vzorec, ktorý je pravdivý na množine premenných tohto riadku:

  riadok 2: ;

  riadok 6: .

  Konjunkcia týchto dvoch vzorcov nadobudne hodnotu 0 iba na množinách premenných v riadkoch 2 a 6, a preto bude požadovanou dokonalou konjunktívnou normálnou formou (PCNF):

  Otázky a úlohy na samostatné riešenie

  1. Pomocou ekvivalentných transformácií zredukujte vzorce na DNF:

  2. Pomocou ekvivalentných transformácií priveďte vzorce do CNF:

  3. Pomocou druhého distribučného zákona preveďte DNF na CNF:

  A) ;

  4. Preveďte dané DNF na SDNF:

  5. Preveďte daný CNF na SCNF:

  6. Pre dané logické vzorce zostrojte SDNF a SCNF dvoma spôsobmi: pomocou ekvivalentných transformácií a pomocou pravdivostnej tabuľky.

  b) ;

  Jednoduché konjunkcia volal konjunkcia jeden alebo niekoľko premenných, pri toto každý premenlivý stretáva nie viac jeden krát (alebo sama, alebo jej negácia).

  Ide napríklad o jednoduchú spojku,

  Disjunktívne normálne tvar(DNF) volal disjunkcia jednoduché spojky.

  Napríklad výraz je DNF.

  Perfektné disjunktívny normálne tvar(SDNF) volal Páči sa ti to disjunktívny normálne formulár, pri ktoré V každý konjunkcia zahrnuté Všetky premenných daný zoznam (alebo sami, alebo ich odmietavý postoj), a V jeden A objem rovnakýok.

  Napríklad výraz je DNF, ale nie SDNF. Výraz je SDNF.

  Podobné definície (s nahradením spojky disjunkciou a naopak) platia pre CNF a SKNF. Uveďme presné znenie.

  Jednoduché disjunkcia volal disjunkcia jeden alebo niekoľko premenných, pri toto každý premenlivý zahrnuté nie viac jeden krát (alebo sama, alebo jej negácia).Výraz je napríklad jednoduchá disjunkcia,

  Konjunktiv normálne tvar(KNF) volal konjunkcia jednoduché disjunkcie(napríklad výraz je CNF).

  Dokonalá konjunktívna normálna forma (PCNF) je CNF, v ktorej každá jednoduchá disjunkcia zahŕňa všetky premenné daného zoznamu (buď samotné alebo ich negácie) a v rovnakom poradí.

  Napríklad výraz je SKNF.

  Ukážeme si algoritmy na prechod z jednej formy do druhej. Prirodzene, v špecifických prípadoch (s určitým kreatívnym prístupom) môže byť použitie algoritmov náročnejšie na prácu ako jednoduché transformácie pomocou špecifického typu daného formulára:

  a) prechod z DNF na CNF

  Algoritmus tohto prechodu je nasledujúci: nad DNF umiestnime dve negácie a pomocou De Morganových pravidiel (bez toho, aby sme sa dotkli hornej negácie), znížime negáciu DNF späť na DNF. V tomto prípade musíte otvoriť zátvorky pomocou absorpčného pravidla (alebo Blakeovho pravidla). Negácia (horná) výsledného DNF (opäť podľa de Morganovho pravidla) nám okamžite dáva CNF:

  Všimnite si, že CNF možno získať aj z pôvodného výrazu, ak vytiahneme pri mimo zátvoriek;

  b) prechod z CNF na DNF

  Tento prechod sa vykonáva jednoduchým otvorením zátvoriek (opäť sa používa absorpčné pravidlo)

  Tak sme dostali DNF.

  Reverzný prechod (od SDNF k DNF) je spojený s problémom minimalizácie DNF. Toto bude podrobnejšie diskutované v časti. 5, tu ukážeme, ako zjednodušiť DNF (alebo SDNF) podľa Blakeovho pravidla. Tento typ DNF sa nazýva skrátené DNF;

  c) skratka DNF (alebo SDNF) podľa pravidlo Blake

  Aplikácia tohto pravidla pozostáva z dvoch častí:

  Ak medzi disjunktnými pojmami v DNF sú pojmy , potom k celej disjunkcii pridáme výraz TO 1 TO 2. Túto operáciu vykonáme niekoľkokrát (možno postupne alebo súčasne) pre všetky možné dvojice pojmov a potom aplikujeme normálnu absorpciu;

  Ak bol pridaný výraz už v DNF obsiahnutý, možno ho úplne vypustiť, napr.

  alebo

  Samozrejme, že skratka DNF nie je jednoznačne definovaná, ale všetky obsahujú rovnaký počet písmen (napr. existuje DNF , po aplikovaní Blakeovho pravidla sa dá dospieť k DNF ekvivalentnému tomuto):

  c) prechod z DNF na SDNF

  Ak v nejakej jednoduchej spojke chýba premenná, napr. z, vložte do nej výraz a potom otvorte zátvorky (opakujúce sa nespojité pojmy nepíšeme). Napríklad:

  d) prechod z KNF na SKNF

  Tento prechod sa vykonáva podobným spôsobom ako predchádzajúci: ak v jednoduchej disjunkcii chýba nejaká premenná (napr. z, potom k nemu pridáme výraz (to nemení samotnú disjunkciu), po ktorom otvoríme zátvorky pomocou distribučného zákona:

  SKNF sa teda získal z CNF.

  Všimnite si, že minimálny alebo znížený CNF sa zvyčajne získa zo zodpovedajúceho DNF.

  Štandardný základ. Elementárne vzorce sú doslovné. Elementárna konjunkcia (disjunkcia). Disjunktívna (konjunktívna) normálna forma a dokonalá forma. Veta: akákoľvek booleovská funkcia odlišná od 0 (od 1) môže byť reprezentovaná vo forme SDNF (SCNF). Úplnosť štandardného základu. Príklady úplných základov: základ Zhegalkin, zdvih Schaeffer, šípka Peirce.

  Štandardný základ je súbor troch základných operácií Booleovej algebry: sčítanie (zjednotenie), násobenie (priesečník) a negácia.

  Tu zavoláme doslovne premenná x alebo jej negácia x a označujú xˆ. Booleovský prienik niekoľkých literálov definovaných rôznymi premennými, t.j. vyjadrenie tvaru X = xˆ 1 xˆ 2 . . . xˆ l, tzv elementárna konjunkcia . Požiadavka, aby všetky premenné boli odlišné, je určená nasledujúcim. Ak spojka obsahuje niekoľko identických literálov, potom je v dôsledku komutativity, asociatívnosti a idempotencie spojky možné po prechode na ekvivalentný vzorec ponechať iba jeden literál (napríklad x 1 x 1 = x 1). Ak spojka obsahuje premennú a jej negáciu, potom je vzorec ekvivalentný konštante 0, pretože x x = 0 a pre akýkoľvek vzorec Y máme Y x x = 0.

  Disjunkcia viacerých elementárnych konjunkcií je tzv disjunktívna normálna forma , alebo DNF . Napríklad,

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

  Ak je zloženie premenných v každej elementárnej konjunkcii daného DNF rovnaké, potom sa volá DNF perfektné . Uvedený príklad je DNF, ktorý nie je dokonalý. Naopak, vzorec

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

  existuje dokonalá forma.

  Keďže v Booleovej algebre sú sčítanie a násobenie symetrické operácie a sčítanie môžete vždy interpretovať ako násobenie a násobenie ako sčítanie, existuje dvojitý koncept - konjunktívna normálna forma (KNF ), čo je konjunkcia elementárnych disjunkcií, a dokonalý konjunktívny tvar (SKNF ). Z princípu duality pre symetrické polomery vyplýva, že na akékoľvek tvrdenie ohľadom DNF odpovedá duálne tvrdenie týkajúce sa CNF, ktoré sa získa nahradením sčítania (disjunkcie) násobením, násobenia (konjunkcie) sčítaním, konštanty 0 konštantou 1, konštanty 1 s konštantou 0, vzťah poradia s duálom (inverzným) v poradí. Preto sa ďalej zameriame len na štúdium DNF.

  Veta 1.4. Akákoľvek booleovská funkcia iná ako konštanta 0 môže byť reprezentovaná ako SDNF.

  ◀Dohodnime sa, že výrazom x σ rozumieme vzorec x, ak σ = 1, a vzorec x, ak σ = 0. Nech funkcia f(y 1 , . . . , y n) nadobudne na vektore hodnotu 1 (t 1, ..., t n) (takýto vektor sa nazýva zakladajúca jednotka ). Potom elementárna konjunkcia tiež nadobudne hodnotu 1 na tejto množine, ale zmizne na všetkých ostatných n-rozmerných booleovských vektoroch. Zvážte vzorec

  v ktorom sa súčet (zjednotenie) rozširuje na všetky tie množiny (t 1, . . . , t n) hodnôt argumentov, na ktorých má daná funkcia hodnotu 1. Všimnite si, že množina takýchto množín nie je prázdna, takže súčet obsahuje aspoň jeden výraz.

  Je ľahké vidieť, že vzorec Φ sa stáva 1 pre tie a len pre tie hodnoty premenných, pre ktoré sa príslušná funkcia stáva 1. To znamená, že vzorec Ψ predstavuje funkciu f.

  Dôsledok 1.1.Štandardný základ je hotový.

  ◀ V skutočnosti, ak funkcia nie je konštantná 0, potom môže byť reprezentovaná buď vo forme SDNF, čo je vzorec nad štandardným základom. Konštanta 0 môže byť vyjadrená napríklad vzorcom f(x 1, x 2,..., x n) = x 1 x 1.

  Príklad 1.2. Uvažujme funkciu troch premenných m(x 1, x 2, x 3) (tabuľka 1.4), tzv. väčšinová funkcia ̆. Táto funkcia sa vyhodnotí ako 1, ak viac ako polovica jej argumentov má hodnotu 1. Preto sa často nazýva hlasovacia funkcia. Postavme na to SDNF.

  Úplnosť štandardného základu umožňuje výber ďalších ucelených systémov funkcií. Úplnosť množiny F možno určiť z nasledujúcich úvah. Predpokladajme, že každá z troch štandardných busisových funkcií je reprezentovateľná vzorcom cez F . Potom podľa vety 1.3 bude identita F úplná.

  Príklad 1.3. Volá sa množina operácií modulo 2 sčítanie, násobenie a konštanta 1 Zhegalkinov základ . Sčítanie modulo 2 a násobenie sú základné operácie kruhu Z2, výrazy zložené s ich pomocou sú polynómy nad kruhom Z2. Konštanta 1 je v tomto prípade potrebná na zapísanie voľného termínu. Keďže xx = x, potom všetky faktory v polynóme majú stupeň 1. Preto sa pri písaní polynómu zaobídete bez pojmu stupeň. Príklady vzorcov na báze Zhegalkin:

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

  Každý takýto vzorec sa nazýva Zhegalkinov polynóm. V skutočnosti je Zhegalkinov polynóm polynóm nad kruhom Z2.

  Nie je ťažké zostaviť vzorce na základe Zhegalkin, ktoré predstavujú operácie sčítania a negácie štandardného základu (násobenie dvoch základov je bežné):

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

  Preto je základom Zhegalkin kompletný súbor.
  Dá sa ukázať, že pre akúkoľvek booleovskú funkciu je Zhegalkinov polynóm jednoznačne definovaný

  (presnejšie do poradia pojmov). Koeficienty Zhegalkinovho polynómu s malým počtom premenných možno nájsť pomocou metódy neurčitých koeficientov.

  Príklad 1.4. Zoberme si množinu jedinej funkcie – Schaefferov zdvih*. Táto sada je kompletná, ako vyplýva z nasledujúcich ľahko overiteľných identít:

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

  Príklad 1.5. Základ pozostávajúci z jedinej funkcie, Peirceovho šípu, je tiež hotový. Test na to je podobný ako v prípade Schaefferovej mŕtvice. Tento záver však možno urobiť aj na základe princípu duality pre symetrické semiringy.

  *Schaefferova mŕtvica je binárna, ale nie asociatívna operácia. Preto by ste pri používaní formulára infix mali byť opatrní: výsledok závisí od poradia operácií. V tomto prípade sa odporúča explicitne uviesť poradie operácií pomocou zátvoriek, napríklad napísať (x | y) | z, nie x | y | z, hoci obe formy sú ekvivalentné.