Boolen funktio

Boolen funktio (tai looginen funktio tai logiikan algebran funktio ) [1] n argumentista - diskreetissä matematiikassa - kuvaus B n → B , missä B = {0,1} on Boolen joukko . Boolen joukon {1, 0} elementit tulkitaan yleensä loogisiksi arvoiksi "true" ja "false", vaikka yleensä niitä pidetään muodollisina symboleina, joilla ei ole erityistä merkitystä. Ei-negatiivista kokonaislukua n , joka ilmaisee argumenttien määrää, kutsutaan funktion arityksi tai paikkakunnaksi, jos n = 0, looginen funktio muuttuu boolen vakioksi . Karteesisen tulon ( n :nnen suoran tehon) B n alkioita kutsutaan Boolen vektoreiksi . Kaikkien minkä tahansa argumenttien lukumäärän Boolen funktioiden joukko merkitään usein P 2 :lla ja n argumentin joukko P 2 ( n ). Muuttujia, jotka ottavat arvot Boolen joukosta, kutsutaan Boolen muuttujiksi [2] . Boolen funktiot on nimetty matemaatikon George Boolen mukaan .

Boolen funktioiden kanssa työskennellessä on olemassa täydellinen abstraktio siitä merkityksellisestä merkityksestä, joka oletetaan lausealgebrassa [2] . Kuitenkin yksi yhteen vastaavuus voidaan muodostaa Boolen funktioiden ja lausealgebran kaavojen välille , jos [3] :

muodostaa yksi yhteen vastaavuus loogisten ja propositionaalisten muuttujien välillä ;
muodostaa yhteyden Boolen funktioiden ja loogisten yhteyksien välille;
jätetään toimintojen prioriteetti ennalleen.

Perustiedot

Jokainen arityn n Boolen funktio on täysin määritelty asettamalla sen arvot sen määritelmäalueelle, eli kaikille Boolen vektoreille, joiden pituus on n . Tällaisten vektoreiden lukumäärä on 2 n . Koska Boolen funktio voi saada joko 0:n tai 1:n jokaisessa vektorissa, kaikkien n -arvoisten Boolen funktioiden lukumäärä on 2 (2 n ) . Siksi tässä osiossa tarkastellaan vain yksinkertaisimpia ja tärkeimpiä Boolen funktioita.

Melkein kaikki alempien ariteettien Boolen funktiot (0, 1, 2 ja 3) saivat historialliset nimet. Jos funktion arvo ei riipu yhdestä muuttujasta (eli itse asiassa millä tahansa kahdella Boolen vektorilla, jotka eroavat vain tämän muuttujan arvosta, funktion arvo niillä on sama), tämä muuttujaa, joka ei toista mitään "arvoa", kutsutaan fiktiiviseksi .

Totuustaulukot

Boolen funktio määritellään äärellisellä arvojoukolla, mikä mahdollistaa sen esittämisen totuustaulukkona , esimerkiksi [4] :

x 1	x2_ _	…	xn - 1	x n	f ( x 1 , x 2 , …, x n )
0	0	…	0	0	0
0	0	…	0	yksi	0
0	0	…	yksi	0	yksi
0	0	…	yksi	yksi	0
$\vdots$	$\vdots$	$\ddots$	$\vdots$	$\vdots$	$\vdots$
yksi	yksi	…	0	0	yksi
yksi	yksi	…	0	yksi	0
yksi	yksi	…	yksi	0	0
yksi	yksi	…	yksi	yksi	0

Nullaarifunktiot

Kun n = 0, Boolen funktioiden lukumäärä pienenee kahteen 2 2 0 = 2 1 = 2, joista ensimmäinen on identtisesti 0 ja toinen on 1. Niitä kutsutaan Boolen vakioiksi - identtisesti nolla ja identtisesti yksi .
Nollaloogisten funktioiden arvojen ja nimien taulukko:

	Merkitys	Nimitys	Nimi
	0	F0,0 = 0	identtinen nolla
	yksi	F0,1 = 1	identtinen yksikkö, tautologia

Unaarifunktiot

Kun n = 1, Boolen funktioiden lukumäärä on 2 2 1 = 2 2 = 4. Nämä funktiot määritellään seuraavassa taulukossa.

Taulukko Boolen funktioiden arvoista ja nimistä yhdestä muuttujasta:

x0 = x	yksi	0	Nimitys	Nimi
0	0	0	F1.0 = 0	identtinen nolla
yksi	0	yksi	F1,1 = x = ¬ x = x' = EI(x)	negaatio, looginen "EI", "EI", "EI", invertteri , SWAP (vaihto)
2	yksi	0	F1,2 = x	identiteettitoiminto, looginen "KYLLÄ", toistin
3	yksi	yksi	F1.3=1	identtinen yksikkö, tautologia

Binäärifunktiot

Kun n = 2, Boolen funktioiden lukumäärä on 2 2 2 = 2 4 = 16.

Taulukko Boolen funktioiden arvoista ja nimistä kahdesta muuttujasta:

x0 = x	yksi	0	yksi	0	Funktiomerkintä	Toiminnon nimi
x 1 =y	yksi	yksi	0	0	Funktiomerkintä	Toiminnon nimi
0	0	0	0	0	F2.0=0	identtinen nolla
yksi	0	0	0	yksi	F2,1 = x ↓ y = x NOR y = NOR( x , y ) = x NOR y = NOR ( x , y ) = EI(MAX(X,Y))	Pierce-nuoli - "↓" ( Quinen tikari - "†"), Webb-toiminto - "°" [5] , EI TAI, 2OR-EI, antidisjunktio, maksimi inversio
2	0	0	yksi	0	F2,2 = x > y = x GT y = GT( x , y ) = x → y = x ↛ y	vertailufunktio "ensimmäinen operandi on suurempi kuin toinen operandi", suoran implikoinnin käänteinen , koimplikaatio [6]
3	0	0	yksi	yksi	F2,3 = y = y' = ¬ y = NOT2( x , y ) = NOT2( x , y )	toisen operandin negaatio (negatio, inversio).
neljä	0	yksi	0	0	F2,4 = x < y = x LT y = LT( x , y ) = x ← y = x ↚ y	vertailufunktio "ensimmäinen operandi on pienempi kuin toinen operandi", käänteinen implikaatio , käänteinen koimplikaatio [6]
5	0	yksi	0	yksi	F2,5 = x = x' = ¬ x = NOT1( x , y ) = NOT1( x , y )	ensimmäisen operandin negaatio (negatio, inversio).
6	0	yksi	yksi	0	F2,6 = x >< y = x <> y = x NE y = NE(x, y) = x ⊕ y = x XOR y = XOR( x , y )	vertailufunktio "operandit eivät ole tasa-arvoisia", modulo 2 -lisäys ilman "tai" , Zhegalkinin summa [7]
7	0	yksi	yksi	yksi	F2.7 = x \| y = x NAND y = NAND( x , y ) = x NAND y = NAND ( x , y ) = EI(MIN(X,Y))	Schaefferin veto , Chulkovin katkoviiva [8] , NAND, 2I-NOT, antikonjunktio, minimiinversio
kahdeksan	yksi	0	0	0	F2,8 = x ∧ y = x y = xy = x & y = x JA y = JA( x , y ) = x JA y = JA ( x , y ) = min ( x , y )	konjunktio , 2I, minimi
9	yksi	0	0	yksi	F2.9 = ( x ≡ y ) = x ~ y = x ↔ y = x EQV y = EQV( x , y )	vertailufunktio "operandit ovat yhtä suuret", ekvivalenssi
kymmenen	yksi	0	yksi	0	F2,10 = KYLLÄ1( x , y ) = KYLLÄ1( x , y ) = x	ensimmäinen operandi
yksitoista	yksi	0	yksi	yksi	F2,11 = x ≥ y = x >= y = x GE y = GE( x , y ) = x ← y = x ⊂ y	vertailufunktio "ensimmäinen operandi ei ole pienempi kuin toinen operandi", käänteinen implikaatio (toisesta argumentista ensimmäiseen)
12	yksi	yksi	0	0	F2,12 = KYLLÄ2( x , y ) = KYLLÄ2( x , y ) = y	toinen operandi
13	yksi	yksi	0	yksi	F2.13 = x ≤ y = x <= y = x LE y = LE( x , y ) = x → y = x ⊃ y	vertailufunktio "ensimmäinen operandi ei ole suurempi kuin toinen operandi", suora (aineellinen) implikaatio (ensimmäisestä argumentista toiseen)
neljätoista	yksi	yksi	yksi	0	F2,14 = x ∨ y = x + y = x TAI y = TAI( x , y ) = x TAI y = TAI( x , y ) = max( x , y )	disjunktio , 2OR, max
viisitoista	yksi	yksi	yksi	yksi	F2.15=1	identtinen yksikkö, tautologia

Kahdella argumentilla etuliitteen , infixin ja jälkiliitteen merkintätapa ovat taloudellisuuden kannalta lähes samat.

Jotkut digitaalitekniikassa järkevät funktiot, kuten vertailufunktiot, minimi ja maksimi, eivät ole järkeviä logiikassa, koska logiikassa loogisilla arvoilla TRUE ja FALSE ei yleensä ole kovaa sidontaa numeerisiin arvoihin. (esimerkiksi TurboBasicissa joidenkin laskelmien yksinkertaistamiseksi TOSI = -1 ja EPÄTOSI = 0) ja on mahdotonta määrittää, mikä on suurempi kuin TOSI tai EPÄTOSI, kun taas implikaatiot ja muut ovat järkeviä sekä digitaalitekniikassa että logiikassa.

Kolmiosaiset funktiot

Arvolla n = 3 loogisten funktioiden lukumäärä on 2 (2 3 ) = 2 8 = 256. Jotkut niistä on määritelty seuraavassa taulukossa:
Joidenkin Boolen funktioiden arvo- ja nimitaulukko kolmesta muuttujasta omalla nimellä :

x0 = x	yksi	0	yksi	0	yksi	0	yksi	0	Merkintä	Otsikot
x 1 =y	yksi	yksi	0	0	yksi	yksi	0	0
x 2 \u003d z	yksi	yksi	yksi	yksi	0	0	0	0
yksi	0	0	0	0	0	0	0	yksi	F3,1 = x ↓ y ↓ z = ↓(x,y,z) = Webb 2 (x,y,z) = NOR(x,y,z)	3OR-NOT, Webb-toiminto, Piercen nuoli , Quinen tikari - "†"
23	0	0	0	yksi	0	yksi	yksi	yksi	F3,23 = = ≥2(x,y,z) $\neg (>=2(x,y,z))$	Enemmistökytkin inversiolla, 3PPB-NE, enemmistöventtiili inversiolla
71	0	yksi	0	0	0	yksi	yksi	yksi	F3.71= ${\näyttötyyli [x,y,z]}$	Ehdollinen disjunktio
126	0	yksi	yksi	yksi	yksi	yksi	yksi	0	F3.126 = (x≠y≠z) = [≠(x,y,z)] = NE(x,y,z)	Epätasa-arvo
127	0	yksi	yksi	yksi	yksi	yksi	yksi	yksi	F3,127 = x\|y\|z = \|(x,y,z) = NAND(x,y,z)	3I-NOT, Schaeffer-isku
128	yksi	0	0	0	0	0	0	0	F3,128 = x&y&z = &(x,y,z) = (x JA y JA z) = JA(x,y,z) = (x JA y JA z) = JA(x,y,z) = min (x, y, z)	3I, minimi
129	yksi	0	0	0	0	0	0	yksi	F3.129 = (x=y=z) = [=(x,y,z)] = EQV(x,y,z)	Tasa-arvo
150	yksi	0	0	yksi	0	yksi	yksi	0	F3,150 = x⊕y⊕z = x⊕ 2 y⊕ 2 z = ⊕ 2 (x,y,z)	Kolminkertainen lisäys modulo 2
216	yksi	yksi	0	yksi	yksi	0	0	0	F3.216 = f 1	Kolmiosaisen vähennyksen lainaus
232	yksi	yksi	yksi	0	yksi	0	0	0	F3,232 = f 2 = [=>=2(x,y,z)] = ≥2(x,y,z) = (x JA y) TAI (y JA z) TAI (z JA x)	Kolmiosainen lisäkuljetin, pääkytkin, 3PPB, enemmistöventtiili
254	yksi	yksi	yksi	yksi	yksi	yksi	yksi	0	F3,254 = (x+y+z) = +(x,y,z) = (x TAI y TAI z) = TAI(x,y,z) = (x TAI y TAI z) = TAI(x, y,z) = max(x,y,z)	TAI, maksimi

Kolmella tai useammalla argumentilla etuliitteen (ja jälkiliitteen) merkintä on taloudellisempaa kuin infix-merkintä.
Tavallinen tapa kirjoittaa funktioita on etuliite (ennen operandeja). Infixin (operandien välissä) funktioiden merkinnällä funktioita kutsutaan operaattoreiksi ja funktion argumentteja kutsutaan operandeiksi.

Täydelliset Boolen funktioiden järjestelmät

Superpositio ja suljetut funktioiden luokat

Boolen funktion arvioinnin tulosta voidaan käyttää toisen funktion argumenttina. Tällaisen superpositiooperaation tulosta voidaan pitää uutena Boolen funktiona, jolla on oma totuustaulukko. Esimerkiksi funktio (konjunktion, disjunktion ja kahden negation superpositio) vastaa seuraavaa taulukkoa: $f(x,y,z)=\overline {x(\overline {y}\lorz)}$

$x_{2}=x$	$x_{1}=y$	$x_{0}=z$	$f(x,y,z)$
0	0	0	yksi
0	0	yksi	yksi
0	yksi	0	yksi
0	yksi	yksi	yksi
yksi	0	0	0
yksi	0	yksi	0
yksi	yksi	0	yksi
yksi	yksi	yksi	0

Funktioiden joukon sanotaan olevan suljettu superpositiolla, jos samaan joukkoon sisältyy myös funktioiden superpositio tietystä joukosta. Suljettuja funktiojoukkoja kutsutaan myös suljetuiksi luokiksi .

Yksinkertaisimpina esimerkkeinä Boolen funktioiden suljetuista luokista voidaan nimetä joukko , joka koostuu yhdestä identtisestä funktiosta, tai joukko , jonka kaikki funktiot ovat identtisesti yhtä suuria kuin nolla, riippumatta niiden argumenteista. Myös funktiojoukko ja kaikki unaarifunktiot ovat suljettuja. Mutta suljettujen luokkien liitto ei ehkä enää ole sellainen. Esimerkiksi yhdistämällä luokat ja , voimme käyttää superpositiota saadakseen vakion 1, joka puuttui alkuperäisistä luokista. $\{x\}$ $\{0\}$ $\{x,\overline {x}\}$ $\{0\}$ $\{x,\overline {x}\}$ $\overline {0}$

Tietysti myös kaikkien mahdollisten Boolen funktioiden joukko on suljettu. $P_2$

Identiteetti ja kaksinaisuus

Kaksi Boolen funktiota ovat identtisiä toistensa kanssa, jos niillä on samat arvot kaikilla identtisillä argumenteilla. Funktioiden f ja g identiteetti voidaan kirjoittaa esimerkiksi seuraavasti:
$f(x_{1},x_{2},\pisteet ,x_{n})=g(x_{1},x_{2},\pisteet ,x_{n})$

Tarkasteltaessa Boolen funktioiden totuustaulukoita on helppo saada seuraavat identiteetit:

$\overline {0}=1$	$\overline {1}=0$	$\overline {\overline {x}}=x$	$xy=yx$	$x\tai y=y\tai x$
$0x=0$	${\näyttötyyli 1x=x}$	$0\tai x=x$	$1\lorx=1$	$xx=x\tai x=x$

Ja joidenkin superpositioiden varalta rakennettujen taulukoiden tarkistaminen antaa seuraavat tulokset:

x\overline {x}=0

x\lor \overline {x}=1

\overline {x\cdot y}=\overline {x}\lor \overline {y}

\overline {x}\cdot \overline {y}=\overline {x\lor y}

( de Morganin lait )

$x(y\tai z)=xy\tai xz$
$x\lor yz=(x\tai y)(x\tai z)$ ( konjunktion ja disjunktion distributiivisuus )

Funktiota kutsutaan kaksoisfunktioksi, jos . On helppo osoittaa, että tässä yhtälössä f ja g voidaan vaihtaa keskenään, eli funktiot f ja g ovat duaalisia keskenään. Yksinkertaisimmista funktioista vakiot 0 ja 1 ovat duaalisia keskenään, ja konjunktion ja disjunktion duaalisuus seuraa De Morganin laeista. Identtinen funktio, kuten negatiivinen funktio, on kaksoisfunktio itselleen. $g(x_{1},x_{2},\pisteet ,x_{n})$ $f(x_{1},x_{2},\pisteet ,x_{n})$ $f(\overline {x_{1}},\overline {x_{2}},\dots ,\overline {x_{n}})=\overline {g(x_{1},x_{2},\dots ,x_{n})}$

Jos Boolen identiteetissä korvaamme jokaisen funktion sen duaalilla, saamme jälleen oikean identiteetin. Yllä olevista kaavoista on helppo löytää toisilleen kaksoispareja.

Järjestelmän täydellisyys, Postin kriteeri

Boolen funktioiden järjestelmää kutsutaan täydelliseksi , jos on mahdollista muodostaa niiden superpositio, joka on identtinen minkä tahansa ennalta määritetyn funktion kanssa. He sanovat myös, että tietyn järjestelmän sulkeminen osuu yhteen sarjan kanssa . $P_2$

Amerikkalainen matemaatikko Emil Post esitteli seuraavat Boolen funktioiden suljetut luokat:

Toiminnot, jotka säilyttävät vakion ja ; $P_0$ $P_1$
Itsenäiset kaksoistoiminnot ; $S$
Monotoniset toiminnot ; $M$
Lineaariset funktiot . $L$

Hän osoitti, että mikä tahansa suljettu Boolen funktioiden luokka, joka ei ole sama kuin, sisältyy kokonaan yhteen näistä viidestä niin sanotusta esitäydellisestä luokasta , mutta yksikään viidestä ei sisälly kokonaan neljän muun liittoon. Siten Postin järjestelmän täydellisyyden kriteeri tiivistyy sen selvittämiseen, sisältyykö koko järjestelmä kokonaan johonkin esitäydellisistä luokista. Jos jokaisessa järjestelmän luokassa on funktio, joka ei sisälly siihen, niin tällainen järjestelmä on täydellinen ja siihen sisältyvien funktioiden avulla on mahdollista saada mikä tahansa muu Boolen funktio. Post osoitti, että Boolen funktioiden suljettujen luokkien joukko on laskettava joukko . $P_2$

Huomaa, että on toimintoja, jotka eivät sisälly mihinkään Postin luokkiin. Mikä tahansa tällainen toiminto itsessään muodostaa täydellisen järjestelmän. Esimerkkejä ovat Schaefferin veto tai Piercen nuoli .

Boolen funktioiden esitys

Postin lause avaa tien Boolen funktioiden esittämiseen syntaktisella tavalla, joka joissain tapauksissa osoittautuu paljon kätevämmäksi kuin totuustaulukot. Lähtökohtana tässä on löytää täydellinen funktiojärjestelmä . Tällöin jokainen Boolen funktio voidaan esittää jollakin termillä allekirjoituksessa , jota tässä tapauksessa kutsutaan myös kaavaksi . Valitun funktiojärjestelmän osalta on hyödyllistä tietää vastaukset seuraaviin kysymyksiin: $\Sigma =\{f_{1},\ldots ,f_{n}\}$ $\Sigma$

Kuinka rakentaa tätä funktiota edustava kaava?
Kuinka tarkistaa, että kaksi eri kaavaa ovat ekvivalentteja, eli ne määrittelevät saman funktion?
- Erityisesti: onko olemassa keinoa pelkistää mielivaltainen kaava vastaavaan kanoniseen muotoonsa siten, että kaksi kaavaa ovat ekvivalentteja silloin ja vain, jos niiden kanoniset muodot ovat samat?
Kuinka tietyn funktion avulla voidaan muodostaa kaava, joka esittää sitä tietyillä ominaisuuksilla (esimerkiksi pienimmällä koolla), ja onko tämä mahdollista?

Positiiviset vastaukset näihin ja muihin kysymyksiin lisäävät merkittävästi valitun funktiojärjestelmän soveltamisarvoa.

Disjunktiivinen normaalimuoto (DNF)

Yksinkertainen konjunktio tai konjunkti on joidenkin äärellisten muuttujien tai niiden negatiivisten joukon konjunktio, jossa jokainen muuttuja esiintyy enintään kerran. Disjunktiivinen normaalimuoto tai DNF on yksinkertaisten konjunktioiden disjunktio. Elementaarinen konjunktio

oikea , jos jokainen muuttuja sisältyy siihen enintään kerran (mukaan lukien negaatio);
täydellinen , jos jokainen muuttuja (tai sen negaatio) syöttää sen täsmälleen kerran;
monotoninen , jos se ei sisällä muuttujien negaatioita.

Esimerkiksi - on DNF. $a{\overline {b}}c\lor b{\overline {c}}\lor {\overline {a}}$

Täydellinen disjunktiivinen normaalimuoto tai SDNF jollekin tietylle äärelliselle muuttujajoukolle on DNF siten, että jokainen konjunktio sisältää kaikki tietyn joukon muuttujat ja samassa järjestyksessä. Esimerkiksi: . $a\overline {b}c\lor abc\lor \overline {a}b\overline {c}$

On helppo nähdä, että jokainen Boolen funktio vastaa jotakin DNF:ää ja muuta funktiota kuin identtistä nollaa, jopa SDNF:ää. Tätä varten riittää, kun löytää tämän funktion totuustaulukosta kaikki Boolen vektorit, joilla sen arvo on 1, ja jokaiselle sellaiselle vektorille rakentaa konjunktio , jossa . Näiden konjunktioiden disjunktio on alkuperäisen funktion SDNF, koska kaikissa Boolen vektoreissa sen arvot ovat yhtäpitäviä alkuperäisen funktion arvojen kanssa. Esimerkiksi implikaatiolle tulos on , joka voidaan yksinkertaistaa muotoon . $b=(b_{1},b_{2},\ldots ,b_{n})$ $x_{1}^{{b_{1}}}x_{2}^{{b_{2}}}\ldots x_{n}^{{b_{n}}}$ $x_{i}^{1}=x_{i}$ $x_{i}^{0}=\overline {x_{i}}$ $x\to y$ $\overline {x}y\lor \overline {x}\,\overline {y}\lor xy$ $\overline {x}\lor y$

Konjunktiivinen normaalimuoto (CNF)

Konjunktiivinen normaalimuoto (CNF) määritellään kaksoismuodossa DNF:lle. Yksinkertainen disjunktio tai disjunktio on yhden tai useamman muuttujan tai niiden negaatioiden disjunktio, ja jokainen muuttuja sisältyy siihen enintään kerran. CNF on yksinkertaisten disjunktioiden konjunktio.

Täydellinen konjunktiivinen normaalimuoto (PCNF) on jonkin tietyn äärellisen muuttujajoukon suhteen sellainen CNF, jossa jokainen disjunktio sisältää kaikki tämän joukon muuttujat ja samassa järjestyksessä. Koska (C)CNF ja (C)DNF ovat keskenään kaksijakoisia, (C)CNF:n ominaisuudet toistavat kaikki (C)DNF:n ominaisuudet, karkeasti sanottuna "täsmälleen päinvastoin".

CNF voidaan muuntaa vastaavaksi DNF:ksi avaamalla sulkeet seuraavan säännön mukaisesti:

a(b\tai c)\to ab\lor ac

joka ilmaisee konjunktion distributiivisuuden suhteessa disjunktioon. Tämän jälkeen on tarpeen poistaa toistuvat muuttujat tai niiden negaatiot kustakin konjunktiosta ja myös hylätä disjunktiosta kaikki konjunktiot, joissa muuttuja esiintyy negaationsa kanssa. Tässä tapauksessa tulos ei välttämättä ole SDNF, vaikka alkuperäinen CNF olisikin SKNF. Samoin voidaan aina siirtyä DNF:stä CNF:ään. Voit tehdä tämän käyttämällä sääntöä

a\tai bc\to (a\tai b)(a\tai c)

ilmaisee disjunktion distributiivisuuden suhteessa konjunktiin. Tulos on muutettava edellä kuvatulla tavalla korvaamalla sana "konjunktio" sanalla "disjunktio" ja päinvastoin.

Algebrallinen normaalimuoto (ANF tai Zhegalkin-polynomi)

Algebrallinen normaalimuoto (yleinen nimi ulkomaisessa kirjallisuudessa) tai Zhegalkin-polynomi (nimi, jota käytetään kotimaisessa kirjallisuudessa) on loogisen funktion esitysmuoto polynomina , jonka kertoimet ovat muotoa 0 ja 1, jossa konjunktiooperaatio ("AND") , AND), ja lisäyksenä - additio modulo 2 (yksinomainen "OR", XOR). Saadaksesi Zhegalkin-polynomin, toimi seuraavasti:

Hanki sdnf-toiminnot
Korvaa kaikki TAI ainutlaatuisella OR:lla
Kaikissa termeissä korvaa elementit negatiivisella rakenteella: ("elementti" "yksinomainen TAI" 1)
Avaa sulut Zhegalkin-algebran sääntöjen mukaisesti ja anna identtiset termit pareittain

Boolen funktioiden luokitus

Syöteoperandien lukumäärällä n , josta funktion lähdön arvo riippuu, on nolla ( n = 0), unaarinen ( n = 1), binäärinen ( n = 2), kolmiosainen ( n = 3) Boolen funktioita ja toimintoja suuremmasta määrästä operandeja .

Totuustaulukon ykkösten ja nollien lukumäärän mukaan kapea luokka tasapainotettuja Boolen funktioita (kutsutaan myös tasapainotetuiksi tai tasatodennäköisiksi, koska tasatodennäköisillä satunnaisarvoilla syötteessä tai iteroitaessa kaikkia totuustaulukon yhdistelmiä todennäköisyys saada arvo 1 lähdössä on 1/2) erotetaan laajemmasta epäsymmetristen Boolen funktioiden luokasta (kutsutaan myös epäsymmetriseksi, koska todennäköisyys saada arvo 1 lähdössä on eri kuin 1/2). Balanced Boolean -funktioita käytetään ensisijaisesti kryptografiassa .

Funktioarvon riippuvuuden mukaan sen tulobittien permutaatiosta symmetriset Boolen funktiot (jonka arvo riippuu vain tulon yksiköiden määrästä) ja epäsymmetriset Boolen funktiot (jonka arvo riippuu myös funktion permutaatiosta sen tulobitit) erotetaan toisistaan.

Itsekaksoisfunktiot (jonka arvo käännetään, kun kaikkien syötteiden arvot käännetään) erotetaan muista Boolen funktioista, joilla ei ole tätä ominaisuutta funktion arvolla vastakkaisissa argumenttiarvojoukoissa . Itsekaksoisfunktioiden totuustaulukon alaosa on peilikuva käänteisestä yläosasta (jos järjestät totuustaulukon syöteyhdistelmät luonnolliseen järjestykseen).

Algebrallisen epälineaarisuusasteen mukaan erotetaan lineaariset Boolen funktiot ( jonka ANF on pelkistetty syötearvojen lineaariseen summaan modulo 2) ja epälineaariset Boolen funktiot ( joiden ANF sisältää vähintään yhden epälineaarisen konjunktiooperaation syöttöarvot). Esimerkkejä lineaarisista funktioista ovat: modulo 2 -lisäys (yksinomainen TAI, XOR), ekvivalenssi sekä kaikki Boolen funktiot, joiden ANF sisältää vain lineaarisia modulo 2 -laskuoperaatioita ilman konjunktiota. Esimerkkejä epälineaarisista funktioista ovat: konjunktio ("AND", AND), Schaeffer-viiva ("NOT-AND", NAND), Piercen nuoli ("NOT-OR", NOR) sekä kaikki Boolen funktiot, joiden ANF sisältää vähintään yksi epälineaarinen konjunktioperaatio.

Välttämättömät ja valemuuttujat

Boolen funktion muuttujaa kutsutaan välttämättömäksi, jos Boolen funktiolle on olemassa kaksi argumenttien arvojoukkoa, jotka eroavat vain tämän muuttujan arvosta ja niiden Boolen funktion arvot eroavat toisistaan. Jos tämän funktion arvot ovat samat, muuttujaa kutsutaan dummyksi. Muuttuja on välttämätön silloin ja vain, jos se syöttää Boolen funktion täydellisen DNF :n tai Boolen funktion Zhegalkin-polynomin .

Kahta Boolen funktiota kutsutaan yhtäläisiksi, jos niiden olennaisten muuttujien joukot ovat yhtä suuret ja funktioiden arvot osuvat yhteen millä tahansa kahdella yhtä suurella olennaisten muuttujien arvojoukolla. [9]

Katso myös

Kirjallisuus

Alekseev V.B. (luennoitsija), Pospelov A.D. (kääntäjä). Diskreetti matematiikka (luentokurssi, II lukukausi) . - M .: Toim. otd. fak. Laskea. Matematiikka ja kybernetiikka, Moskovan valtionyliopisto. M. V. Lomonosov, 2002. - 44 s.
Bykova S. V., Burkatovskaya Yu. B. Boolen funktiot: oppikirja korkeakoulujen opiskelijoille, jotka opiskelevat erikoisuudella HPE 010501 "Soveltava matematiikka ja informatiikka" . - Tomsk: Tomskin osavaltio. un-t, 2010. - 190 s.
Gavrilov G. P., Sapozhenko A. A. Diskreetin matematiikan ongelmia ja harjoituksia . - M .: FIZMATLIT, 2009.
Igoshin VI Matemaattinen logiikka ja algoritmien teoria . - 2. painos, stereotypia .. - M . : Publishing Center "Academy", 2008. - 448 s.
Kuznetsov OP Diskreetti matematiikka insinöörille . - Pietari. : Lan, 2007. - 394 s.
VMiK MSU:n matemaattisen kybernetiikan laitoksen oppikirjat (MSU VMK:n matemaattisen kybernetiikan laitoksen verkkosivuilla).
Lozhkin S.A. Luennot kybernetiikan perusteista: oppikirja. käsikirja kursseille "Kybernetiikan perusteet" ja "Rakenne". diskreetti toteutus. toiminnot" . - M .: Toim. otd. fak. Laskea. Matematiikka ja kybernetiikka, Moskovan valtionyliopisto. M. V. Lomonosov, 2004. - 254 s.
Marchenkov SS Boolen funktioiden suljetut luokat . - M .: Fizmatlit, 2001. - 126 s.
Samofalov K. G., Romankevich A. M., Valuysky V. N., Kanevsky Yu. S., Pinevich M. M. Digitaalisten automaattien sovellettu teoria . - Kiova: Vishcha Shkola, 1987. - S. 183-189. — 375 s.
Yablonsky SV Johdatus diskreettiin matematiikkaan . - M . : Korkeampi. koulu, 2006. - 384 s.

Linkit

↑ Igoshin, 2008 , luku 2. Boolen funktiot.
↑ 1 2 Igoshin, 2008 , s. 94.
↑ Igoshin, 2008 , s. 104-105.
↑ Samofalov, 1987 .
↑ Boolen perusfunktiot . Haettu 9. marraskuuta 2016. Arkistoitu alkuperäisestä 10. marraskuuta 2016. (määrätön)
↑ 1 2 Valittuja kysymyksiä Boolen funktioiden teoriasta. // A. S. Balyuk et ai., toim. S. F. Vinokurov ja N. A. Peryazev. — M.: FIZMATLIT, 2001. — 192 s. - S. 13.
↑ Igoshin, 2008 , s. 96.
↑ I.A. Nasyrov. opetusväline . Haettu 20. marraskuuta 2020. Arkistoitu alkuperäisestä 22. joulukuuta 2019. (määrätön)
↑ Gavrilov G.P., Sapozhenko A.A. Diskreetin matematiikan tehtäväkokoelma. - M., Nauka, 1977. - s. 44, 46, 47

Sanakirjat ja tietosanakirjat	Iso venäläinen
Bibliografisissa luetteloissa	LNB : 000324702