Zhegalkinin polynomi

Zhegalkin-polynomi on polynomi kentän yli , eli polynomi , jonka kertoimet ovat muotoa 0 ja 1, jossa konjunktio otetaan tulona ja poissulkeva tai summa otetaan huomioon . Ivan Zhegalkin ehdotti polynomia vuonna 1927 käteväksi keinoksi esittää Boolen logiikkafunktioita . Ulkomaisessa kirjallisuudessa Zhegalkin-polynomin muodossa olevaa esitystä kutsutaan yleensä algebralliseksi normaalimuodoksi (ANF). ${\mathbb {Z}}_{2}$

Zhegalkinin lause on väite minkä tahansa Boolen funktion esityksen olemassaolosta ja ainutlaatuisuudesta Zhegalkin-polynomin muodossa [1] .

Zhegalkin-polynomi on ei-invertoitujen muuttujien pareittain erillisten tulojen modulo-kaksi summa , jossa mikään muuttuja ei esiinny useammin kuin kerran missään tulossa, ja myös (tarvittaessa) vakio 1 [1] . Muodollisesti Zhegalkin-polynomi voidaan esittää muodossa

P(X_{1},\dots ,X_{n})=a\oplus a_{1}X_{1}\oplus a_{2}X_{2}\oplus \dots \oplus a_{n} X_{n}\oplus a_{12}X_{1}X_{2}\oplus a_{13}X_{1}X_{3}\oplus \ldots \oplus a_{1\dots n}X_{1}\ pisteet X_{n},

a,\ldots ,a_{1\ldots n}\in \{0,1\},

tai muodollisempi kuin

P=a\oplus \bigoplus _{\begin{array}{c}1\leqslant i_{1}<\ldots <i_{k}\leqslant n\\k\in {\overline {1,n }}\end{array}}a_{i_{1},\ldots ,i_{k}}\wedge x_{i_{1}}\wedge \ldots \wedge x_{i_{k}},\quad a, a_{i_{1},\ldots ,i_{k}}\in \{0,1\}.

Esimerkkejä Zhegalkin-polynomeista:

P=B\oplus AB,

P=X\oplus YZ\oplus ABX\oplus ABDYZ,

P=1\oplus A\oplus ABD.

Tausta

Postin lauseen mukaan, jotta Boolen funktioiden järjestelmä olisi täydellinen, sen tulee sisältää:

Ainakin yksi funktio, joka ei tallenna 0:ta.
Ainakin yksi funktio, joka ei säilytä 1.
Vähintään yksi epälineaarinen funktio.
Ainakin yksi ei-monotoninen toiminto.
Vähintään yksi ei-itse-kaksoistoiminto.

Tämä vaatimus täyttyy erityisesti funktiojärjestelmällä (konjunktio, modulo kaksi yhteenlasku, vakio 1). Sen perusteella rakennetaan Zhegalkin-polynomit. ${\bigl \langle }\wedge ,\oplus ,1{\bigr \rangle }$

Esityksen olemassaolo ja ainutlaatuisuus

Zhegalkinin lauseen mukaan jokainen Boolen funktio esitetään yksilöllisesti Zhegalkin-polynomina. Lause todistetaan seuraavasti. Huomaa, että muuttuvia Boolen funktioita on n . Tässä tapauksessa konjunktiota on tarkalleen 2 n , koska jokainen n :stä mahdollisesta tekijästä joko tulee konjunktiin tai ei. Polynomissa jokaisella tällaisella konjunktiolla on 0 tai 1, eli n muuttujassa on erilaisia Zhegalkin-polynomeja . Nyt riittää todistaa, että eri polynomit toteuttavat erilaisia funktioita. Oletetaan päinvastoin. Sitten vertaamalla kaksi erilaista polynomia ja siirtämällä toinen niistä yhtälön toiseen osaan, saadaan polynomi, joka on identtisesti yhtä suuri kuin nolla ja jolla on nollasta poikkeavat kertoimet. Tarkastellaan sitten termiä, jonka yksikkökerroin on pienin, eli jossa on pienin määrä muuttujia (mikä tahansa, jos niitä on useita). Korvaamalla näiden muuttujien paikoille ykköset ja muiden paikoille nollia, saadaan, että tässä joukossa vain tämä termi saa yksikköarvon, eli yhden joukon nollafunktio saa arvon 1. A. ristiriita. Tämä tarkoittaa, että Zhegalkin-polynomi toteuttaa jokaisen Boolen funktion ainutlaatuisella tavalla. $2^{{2^{n}}}$ $x_{i_{1}}\ldots x_{i_{k}}$ $2^{{2^{n}}}$

Funktion esitys Zhegalkin-polynomin muodossa

Vastaavilla DNF-muunnoksilla

Verrattuna DNF :ään, Zhegalkin-polynomissa ei ole OR- ja NOT-operaatioita. Siten Zhegalkin-polynomi voidaan saada DNF:stä ilmaisemalla operaatiot OR ja NOT summausmoduulin kaksi operaatioilla ja vakiolla 1. Tätä varten käytetään seuraavia suhteita:

A\vee B=A\oplus B\oplus AB,

{\overline {A}}=A\oplus 1.

Alla on esimerkki DNF:n muuntamisesta Zhegalkin-polynomiksi:

XY\vee {\overline {X}}\,{\overline {Y}}=XY\oplus {\overline {X}}\,{\overline {Y}}\oplus XY{\overline {X }}\,{\overline {Y}}=XY\oplus {\overline {X}}\,{\overline {Y}}=XY\oplus (X\oplus 1)(Y\oplus 1)=

\quad =XY\oplus XY\oplus X\oplus Y\oplus 1=X\oplus Y\oplus 1.

Muutokset perustuvat suhteisiin

A\oplus A=0,

(A\oplus B)C=AC\oplus BC.

SDNF:n vastaavien muunnosten avulla

SDNF :llä on ominaisuus, että millä tahansa syötemuuttujien arvolla vain yksi lausekkeen jäsen muuttuu yksiköksi. Tällaisille lausekkeille disjunktiooperaatio vastaa modulo two -summausoperaatiota .

Kun SDNF muunnetaan Zhegalkin-polynomiksi, riittää, että kaikki disjunktiot korvataan operaatioilla modulo two additio ja päästään eroon inversioista vastaavalla muunnolla

{\overline {A}}=A\oplus 1.

Carnot-kartalla

Kolmen muuttujan looginen funktio , joka esitetään Carnot-karttana , muunnetaan Zhegalkin-polynomiksi seuraavissa vaiheissa: $P(A,B,C)$

Käsittelemme kaikkia Karnaugh-kartan soluja niiden koodien yksiköiden lukumäärän nousevassa järjestyksessä. Kolmen muuttujan funktiolle solujen järjestys on 000-100 - 010-001 - 110-101 - 011-111. Jokainen Carnot-kartan solu liittyy Zhegalkin-polynomin jäseneen riippuen koodin paikoista, joissa niitä on. Esimerkiksi solu 111 on jäsen ABC , solu 101 on jäsen AC , solu 010 on jäsen B ja solu 000 on jäsen 1.
Jos kyseisessä solussa on 0, siirry seuraavaan soluun.
Jos tarkasteltavassa solussa on 1, lisätään vastaava termi Zhegalkin-polynomiin, käännetään kaikki Carnot-kartan solut, joissa tämä termi on yhtä suuri kuin 1, ja siirrytään seuraavaan soluun. Esimerkiksi, jos solua 110 tarkasteltaessa siinä on yksikkö, niin termi AB lisätään Zhegalkin-polynomiin ja kaikki Carnot-kartan solut, joissa A = 1 ja B = 1, käännetään. yhtä suuri kuin yksikkö, sitten termi 1 lisätään Zhegalkin-polynomiin ja käännetään koko Carnotin kartta.
Muunnosprosessi voidaan katsoa päättyneeksi, kun seuraavan inversion jälkeen Karnaugh-kartan kaikista soluista tulee nolla.

Kolmiomenetelmä

Kolmiomenetelmällä (kutsutaan usein Pascalin kolmiomenetelmäksi) voit muuntaa totuustaulukon Zhegalkin-polynomiksi rakentamalla apukolmiotaulukon seuraavien sääntöjen mukaisesti:

Rakennetaan täydellinen totuustaulukko, jossa rivit ovat binäärikoodien nousevassa järjestyksessä 000 ... 00 - 111 ... 11.
Rakennetaan apukolmiotaulukko, jonka ensimmäinen sarake on sama kuin totuustaulukon funktioarvojen sarake.
Jokaisen seuraavan sarakkeen solu saadaan summaamalla modulo 2 edellisen sarakkeen kaksi solua - jotka ovat samalla rivillä ja rivillä alla.
Aputaulukon sarakkeet on numeroitu binäärikoodeilla samassa järjestyksessä kuin totuustaulukon rivit.
Jokainen binäärikoodi liittyy yhteen Zhegalkin-polynomin jäsenistä riippuen koodin paikoista, joissa niitä on. Esimerkiksi solu 111 on jäsen ABC , solu 101 on jäsen AC , solu 010 on jäsen B , solu 000 on jäsen 1 ja niin edelleen.
Jos minkä tahansa sarakkeen ylimmällä rivillä on yksikkö, vastaava termi on läsnä Zhegalkin-polynomissa.

Kolmiomenetelmä perustuu V. P. Suprunin esittämään lauseeseen, joka ei liity suoraan Pascalin kolmioon. Vuonna 1985 ehdotettiin binääristä kolmiomenetelmää käytettäväksi täydellisen disjunktiivisen normaalimuodon arvojen vektorin muuntamiseksi Zhegalkinin polynomikertoimien vektoriksi mielivaltaiselle symmetriselle Boolen funktiolle. Vuonna 1987 menetelmä laajennettiin mielivaltaiseen Boolen funktioon. Huomaa, että kolmiomenetelmä mahdollistaa Reed-Muller-polynomin muodostamisen negatiivisella polarisaatiolla sekä symmetrisille funktioille että mielivaltaisille funktioille. .

FFT-menetelmä

Taloudellisin laskelmien määrän suhteen ja sopivin Zhegalkin-polynomin manuaaliseen rakentamiseen on nopea Fourier-muunnos (FFT) -menetelmä.

Rakennamme taulukon, jossa on 2 N saraketta ja N + 1 riviä, missä N on funktion muuttujien lukumäärä. Taulukon ylimmälle riville sijoitetaan funktioarvojen vektori eli totuustaulukon viimeinen sarake.

Jaamme tuloksena olevan taulukon jokaisen rivin lohkoihin (mustat viivat kuvassa). Ensimmäisellä rivillä lohko vie yhden solun, toisessa rivissä kaksi, kolmannessa neljä, neljännessä kahdeksan jne. Jokainen lohko jossakin rivissä, jota kutsumme "alalohkoksi", vastaa aina täsmälleen kahta edellisen rivin lohkoa. Kutsutaan niitä "vasemmalle ylemmäksi lohkoksi" ja "oikeaksi ylälohkoksi".

Rakentaminen alkaa toisesta rivistä. Vasemman ylälohkon sisältö siirretään ilman muutoksia alalohkon vastaaviin soluihin (kuvassa vihreät nuolet). Sitten operaatio "modulo two additio" suoritetaan bitti kerrallaan oikean ja ylemmän vasemman lohkon yli ja saatu tulos siirretään alalohkon oikean puolen vastaaviin soluihin (kuvassa punaiset nuolet). Tämä toimenpide suoritetaan kaikilla riveillä ylhäältä alas ja kaikilla lohkoilla jokaisella rivillä. Rakentamisen valmistumisen jälkeen alarivillä on lukujono, jotka ovat Zhegalkin-polynomin kertoimia, jotka on kirjoitettu samassa järjestyksessä kuin edellä kuvatussa kolmiomenetelmässä.

Summausmenetelmä

Totuustaulukon avulla on helppo laskea Zhegalkin-polynomin yksittäiset kertoimet. Tätä varten sinun on summattava modulo 2 funktion arvot niillä taulukon riveillä, joissa muuttujat, jotka eivät ole konjunktiossa, saavat nollan arvoa.

Oletetaan esimerkiksi, että sinun täytyy löytää kerroin konjunktiosta xz kolmen muuttujan f ( x , y , z ) funktiolle. Tässä konjunktiossa ei ole y -muuttujaa . Etsitään syötejoukot, joissa muuttuja y saa nollan arvon. Nämä ovat joukot 0, 1, 4, 5 (000, 001, 100, 101). Tällöin kerroin konjunktiossa xz on yhtä suuri kuin

a_{5}=f_{0}\oplus f_{1}\oplus f_{4}\oplus f_{5}=f(0,0,0)\oplus f(0,0,1)\ oplus f(1,0,0)\oplus f(1,0,1).

Koska vapaassa jäsenessä ei ole muuttujia, niin

a_{0}=f_{0}.

Jäsenelle, joka sisältää kaikki muuttujat, summa sisältää kaikki funktion arvot:

a_{N-1}=f_{0}+f_{1}+f_{2}+\ldots +f_{N-2}+f_{N-1}.

Esitetään graafisesti Zhegalkin-polynomin kertoimet funktioiden arvojen summana modulo 2 joissakin kohdissa. Tätä varten rakennetaan neliötaulukko, jossa jokainen sarake edustaa funktion arvoa yhdessä pisteestä ja rivi on Zhegalkin-polynomin kerroin. Tietyn sarakkeen ja rivin leikkauspisteessä oleva piste tarkoittaa, että funktion arvo tietyssä pisteessä sisältyy tietyn polynomikertoimen summaan (katso kuva). Kutsutaan tätä taulukkoa T N , jossa N on funktiomuuttujien lukumäärä.

On olemassa malli, jonka avulla voit saada taulukon N muuttujan funktiolle, jossa on taulukko N − 1 muuttujan funktiolle. Uusi taulukko T N +1 on järjestetty 2 × 2 -matriisiksi taulukoita T N , jolloin matriisin oikea ylälohko on tyhjennetty.

Katso myös

Algebra Zhegalkin

Muistiinpanot

↑ 1 2 Kapitonova Yu. V., Krivoy S. L., Letichevsky A. A. Diskreetin matematiikan luentoja. - SPb., BHV-Petersburg, 2004. - ISBN 5-94157-546-7 , s. 110-111.
↑ V. P. Suprun. Taulukkomenetelmä Boolen funktioiden polynomilaajennukseen // Kybernetiikka. - 1987. - Nro 1 . - S. 116-117 .
↑ V. P. Suprun. Boolen funktioiden teorian perusteet. - M.: Lenand / URSS. - 2017. - 208 s.

Kirjallisuus

Yablonsky SV Johdatus diskreettiin matematiikkaan. - M.: Nauka. – 1986
Marchenkov S. S. Boolen funktioiden suljetut luokat. — M.: Fizmatlit. – 2000
Suprun VP Boolen funktioiden teorian perusteet. - M.: Lenand / URSS. – 2017.