Boolesk funktion

En boolsk funktion (eller en logisk funktion , eller en funktion af logikkens algebra ) [1] af n argumenter - i diskret matematik - en mapping B n → B , hvor B = {0,1} er et boolesk sæt . Elementerne i det boolske sæt {1, 0} fortolkes normalt som de logiske værdier "sand" og "falsk", selvom de i det generelle tilfælde betragtes som formelle symboler, der ikke har en bestemt betydning. Et ikke-negativt heltal n , der angiver antallet af argumenter, kaldes funktionens aritet eller lokalitet, i tilfælde af n = 0 bliver den boolske funktion til en boolsk konstant . Elementerne i det kartesiske produkt ( den n . direkte potens) B n kaldes boolske vektorer . Sættet af alle booleske funktioner af et vilkårligt antal argumenter er ofte betegnet med P 2 , og af n argumenter med P 2 ( n ). Variabler, der tager værdier fra et boolesk sæt, kaldes boolske variabler [2] . Booleske funktioner er opkaldt efter matematikeren George Boole .

Når man arbejder med boolske funktioner, er der en fuldstændig abstraktion fra den meningsfulde betydning, der antages i algebraen af propositioner [2] . Ikke desto mindre kan der etableres en en-til-en overensstemmelse mellem booleske funktioner og propositionalgebraformler , hvis [3] :

etablere en en-til-en overensstemmelse mellem booleske og propositionelle variable ;
etablere en forbindelse mellem booleske funktioner og logiske forbindelser;
forlader prioriteten af operationer uændret.

Grundlæggende information

Hver boolsk funktion af arity n er fuldstændig defineret ved at sætte dens værdier på dens definitionsdomæne, det vil sige på alle boolske vektorer med længden n . Antallet af sådanne vektorer er lig med 2 n . Da en boolsk funktion kan tage enten 0 eller 1 på hver vektor, er antallet af alle n -ære booleske funktioner 2 (2 n ) . I dette afsnit er det derfor kun de enkleste og vigtigste boolske funktioner, der behandles.

Næsten alle boolske funktioner af lavere ariteter (0, 1, 2 og 3) fik historiske navne. Hvis værdien af funktionen ikke afhænger af en af variablerne (dvs. faktisk for to boolske vektorer, der kun adskiller sig i værdien af denne variabel, er værdien af funktionen på dem den samme), så er denne variabel, uden at spille nogen "værdi", kaldes fiktiv .

Sandhedstabeller

En boolsk funktion er defineret af et endeligt sæt værdier, som gør det muligt at repræsentere den som en sandhedstabel , for eksempel [4] :

x 1	x2 _	…	xn - 1	x n	f ( x 1 , x 2 , …, x n )
0	0	…	0	0	0
0	0	…	0	en	0
0	0	…	en	0	en
0	0	…	en	en	0
$\vprikker$	$\vprikker$	$\ddots$	$\vprikker$	$\vprikker$	$\vprikker$
en	en	…	0	0	en
en	en	…	0	en	0
en	en	…	en	0	0
en	en	…	en	en	0

Nullære funktioner

For n = 0 reduceres antallet af boolske funktioner til to 2 2 0 = 2 1 = 2, den første af dem er identisk lig med 0, og den anden er 1. De kaldes boolske konstanter - identisk nul og identisk en .
Tabel over værdier og navne på null booleske funktioner:

	Betyder	Betegnelse	Navn
	0	F0,0 = 0	identisk nul
	en	F0,1 = 1	identisk enhed, tautologi

Unære funktioner

For n = 1 er antallet af booleske funktioner 2 2 1 = 2 2 = 4. Disse funktioner er defineret i følgende tabel.

Tabel over værdier og navne på booleske funktioner fra en variabel:

x0 = x	en	0	Betegnelse	Navn
0	0	0	F1,0 = 0	identisk nul
en	0	en	F1,1 = x = ¬ x = x' = IKKE(x)	negation, logisk "NEJ", "NOT", "NOR", inverter , SWAP (udveksling)
2	en	0	F1,2 = x	identitetsfunktion, logisk "JA", repeater
3	en	en	F1,3=1	identisk enhed, tautologi

Binære funktioner

For n = 2 er antallet af booleske funktioner 2 2 2 = 2 4 = 16.

Tabel over værdier og navne på booleske funktioner fra to variable:

x0 = x	en	0	en	0	Funktionsnotation	Funktionsnavn
x 1 = y	en	en	0	0	Funktionsnotation	Funktionsnavn
0	0	0	0	0	F2,0=0	identisk nul
en	0	0	0	en	F2,1 = x ↓ y = x NOR y = NOR( x , y ) = x NOR y = NOR ( x , y ) = IKKE(MAX(X,Y))	Pierce arrow - "↓" ( Quines dolk - "†"), Webb funktion - "°" [5] , IKKE-ELLER, 2ELLER-NOT, antidisjunktion, maksimal inversion
2	0	0	en	0	F2,2 = x > y = x GT y = GT( x , y ) = x → y = x ↛ y	sammenligningsfunktion "den første operand er større end den anden operand", invers af direkte implikation , ko-implikation [6]
3	0	0	en	en	F2,3 = y = y' = ¬ y = NOT2( x , y ) = NOT2( x , y )	negation (negation, inversion) af den anden operand
fire	0	en	0	0	F2,4 = x < y = x LT y = LT( x , y ) = x ← y = x ↚ y	sammenligningsfunktion "den første operand er mindre end den anden operand", invers implikation , invers koimplikation [6]
5	0	en	0	en	F2,5 = x = x' = ¬ x = IKKE1( x , y ) = IKKE1( x , y )	negation (negation, inversion) af den første operand
6	0	en	en	0	F2,6 = x >< y = x <> y = x NE y = NE(x, y) = x ⊕ y = x XOR y = XOR( x , y )	sammenligningsfunktion "operander er ikke ens", modulo 2-addition eksklusive "eller" , Zhegalkins sum [7]
7	0	en	en	en	F2,7 = x \| y = x NAND y = NAND( x , y ) = x NAND y = NAND ( x , y ) = IKKE(MIN(X,Y))	Schaeffers slagtilfælde , Chulkovs stiplede linje [8] , NAND, 2I-NOT, antikonjunktion, minimal inversion
otte	en	0	0	0	F2,8 = x ∧ y = x y = xy = x & y = x OG y = OG( x , y ) = x OG y = OG( x , y ) = min ( x , y )	konjunktion , 2I, minimum
9	en	0	0	en	F2.9 = ( x ≡ y ) = x ~ y = x ↔ y = x EQV y = EQV( x , y )	sammenligningsfunktion "operander er ens", ækvivalens
ti	en	0	en	0	F2,10 = JA1( x , y ) = JA1( x , y ) = x	første operand
elleve	en	0	en	en	F2,11 = x ≥ y = x >= y = x GE y = GE( x , y ) = x ← y = x ⊂ y	sammenligningsfunktion "den første operand er ikke mindre end den anden operand", omvendt implikation (fra det andet argument til det første)
12	en	en	0	0	F2,12 = JA2( x , y ) = JA2( x , y ) = y	anden operand
13	en	en	0	en	F2.13 = x ≤ y = x <= y = x LE y = LE( x , y ) = x → y = x ⊃ y	sammenligningsfunktion "den første operand er ikke større end den anden operand", direkte (materiel) implikation (fra det første argument til det andet)
fjorten	en	en	en	0	F2,14 = x ∨ y = x + y = x ELLER y = OR( x , y ) = x ELLER y = OR( x , y ) = max( x , y )	disjunktion , 2OR, max
femten	en	en	en	en	F2,15=1	identisk enhed, tautologi

Med to argumenter er præfiks , infix og postfix- notation næsten det samme med hensyn til økonomi.

Nogle funktioner, der giver mening i digital teknologi , såsom sammenligningsfunktioner, minimum og maksimum, giver ikke mening i logik, da de boolske værdier TRUE og FALSE i logik generelt ikke har en hård binding til numeriske værdier (for eksempel i TurboBasic , for at forenkle nogle beregninger, TRUE = -1 og FALSE = 0), og det er umuligt at bestemme, hvad der er større end TRUE eller FALSE, mens implikationer og andre giver mening både i digital teknologi og i logikken.

Ternære funktioner

For n = 3 er antallet af booleske funktioner 2 (2 3 ) = 2 8 = 256. Nogle af dem er defineret i følgende tabel:
Tabel over værdier og navne på nogle booleske funktioner fra tre variabler med deres eget navn :

x0 = x	en	0	en	0	en	0	en	0	Notation	Titler
x 1 = y	en	en	0	0	en	en	0	0
x 2 \u003d z	en	en	en	en	0	0	0	0
en	0	0	0	0	0	0	0	en	F3,1 = x ↓ y ↓ z = ↓(x,y,z) = Webb 2 (x,y,z) = NOR(x,y,z)	3OR-NOT, Webb-funktion, Pierces pil , Quines dolk - "†"
23	0	0	0	en	0	en	en	en	F3,23 = = ≥2(x,y,z) $\neg (>=2(x,y,z))$	Majoritetsafbryder med inversion, 3PPB-NE, majoritetsventil med inversion
71	0	en	0	0	0	en	en	en	F3,71= $[x,y,z]$	Betinget disjunktion
126	0	en	en	en	en	en	en	0	F3.126 = (x≠y≠z) = [≠(x,y,z)] = NE(x,y,z)	Ulighed
127	0	en	en	en	en	en	en	en	F3,127 = x\|y\|z = \|(x,y,z) = NAND(x,y,z)	3I-NOT, Schaeffer-slagtilfælde
128	en	0	0	0	0	0	0	0	F3,128 = x&y&z = &(x,y,z) = (x OG y OG z) = OG(x,y,z) = (x OG y OG z) = OG(x,y,z) = min. (x,y,z)	3I, minimum
129	en	0	0	0	0	0	0	en	F3.129 = (x=y=z) = [=(x,y,z)] = EQV(x,y,z)	Lighed
150	en	0	0	en	0	en	en	0	F3,150 = x⊕y⊕z = x⊕ 2 y⊕ 2 z = ⊕ 2 (x,y,z)	Ternær addition modulo 2
216	en	en	0	en	en	0	0	0	F3.216 = f 1	Ternær subtraktionslån
232	en	en	en	0	en	0	0	0	F3,232 = f 2 = [>=2(x,y,z)] = ≥2(x,y,z) = (x OG y) ELLER (y OG z) ELLER (z OG x)	Ternær tilsætningsbærebit, flertalsafbryder, 3PPB, flertalsventil
254	en	en	en	en	en	en	en	0	F3,254 = (x+y+z) = +(x,y,z) = (x ELLER y ELLER z) = ELLER(x,y,z) = (x ELLER y ELLER z) = ELLER(x, y,z) = max(x,y,z)	ELLER, maksimum

Med tre eller flere argumenter er præfiks (og postfix) notation mere økonomisk end infix notation.
Den sædvanlige måde at skrive funktioner på er præfiks (før operander). Med infix (mellem operander) notation af funktioner kaldes funktioner for operatorer, og funktionsargumenter kaldes operander.

Komplette systemer med booleske funktioner

Superposition og lukkede klasser af funktioner

Resultatet af at evaluere en boolsk funktion kan bruges som et af argumenterne til en anden funktion. Resultatet af en sådan superpositionsoperation kan ses som en ny boolsk funktion med sin egen sandhedstabel. For eksempel vil en funktion (superposition af konjunktion, disjunktion og to negationer) svare til følgende tabel: $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	en
0	0	en	en
0	en	0	en
0	en	en	en
en	0	0	0
en	0	en	0
en	en	0	en
en	en	en	0

Et sæt funktioner siges at være lukket under driften af superposition, hvis enhver overlejring af funktioner fra et givet sæt også er inkluderet i det samme sæt. Lukkede sæt af funktioner kaldes også lukkede klasser .

Som de enkleste eksempler på lukkede klasser af boolske funktioner kan man navngive et sæt bestående af en identisk funktion eller et sæt , hvorfra alle funktioner er identisk lig nul, uanset deres argumenter. Sæt af funktioner og sættet af alle unære funktioner er også lukket. Men foreningen af lukkede klasser er måske ikke længere sådan. For eksempel, ved at kombinere klasserne og , kan vi bruge superposition til at få konstanten 1, som var fraværende i de oprindelige klasser. $\{x\}$ $\{0\}$ $\{x,\overline {x}\}$ $\{0\}$ $\{x,\overline {x}\}$ $\overline {0}$

Selvfølgelig er sættet af alle mulige booleske funktioner også lukket. $P_2$

Identitet og dualitet

To boolske funktioner er identiske med hinanden, hvis de har samme værdier på ethvert identisk sæt af argumenter. Identiteten af funktionerne f og g kan for eksempel skrives som følger:
$f(x_{1},x_{2},\dots,x_{n})=g(x_{1},x_{2},\dots,x_{n})$

Ser man på sandhedstabellerne for booleske funktioner, er det let at få følgende identiteter:

$\overline {0}=1$	$\overline {1}=0$	$\overline {\overline {x}}=x$	$xy=yx$	$x\lor y=y\lor x$
$0x=0$	$1x=x$	$0\lor x=x$	$1\lorx=1$	$xx=x\eller x=x$

Og kontrol af tabellerne bygget til nogle superpositioner vil give følgende resultater:

x\overline {x}=0

x\lor \overline {x}=1

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

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

( de Morgans love )

$x(y\lor z)=xy\lor xz$
$x\lor yz=(x\lor y)(x\lor z)$ ( fordeling af konjunktion og disjunktion)

Funktionen kaldes den dobbelte funktion, hvis . Det er let at vise, at i denne lighed kan f og g ombyttes, det vil sige, at funktionerne f og g er dobbelte i forhold til hinanden. Af de simpleste funktioner er konstanterne 0 og 1 dobbelte i forhold til hinanden, og dualiteten af konjunktion og disjunktion følger af De Morgans love. Den identiske funktion er ligesom negationsfunktionen dobbelt i forhold til sig selv. $g(x_{1},x_{2},\dots,x_{n})$ $f(x_{1},x_{2},\dots,x_{n})$ $f(\overline {x_{1}},\overline {x_{2}},\dots,\overline {x_{n}})=\overline {g(x_{1},x_{2},\dots ,x_{n})}$

Hvis vi i en boolsk identitet erstatter hver funktion med dens dual, får vi igen den korrekte identitet. I ovenstående formler er det let at finde par, der er dobbelte med hinanden.

Systemets fuldstændighed, Posts kriterium

Et system af boolske funktioner kaldes komplet , hvis det er muligt at konstruere deres superposition, som er identisk med enhver foruddefineret funktion. De siger også, at lukningen af et givet system falder sammen med sættet . $P_2$

Den amerikanske matematiker Emil Post introducerede følgende lukkede klasser af boolske funktioner:

Funktioner, der bevarer konstanten og ; $P_0$ $P_1$
Selvdobbelte funktioner ; $S$
Monotone funktioner ; $M$
Lineære funktioner . $L$

Han beviste, at enhver lukket klasse af boolske funktioner, der ikke falder sammen med , er helt indeholdt i en af disse fem såkaldte prækomplette klasser , men ingen af de fem er indeholdt helt i foreningen af de andre fire. Posts kriterium for fuldstændigheden af et system går således ud på at finde ud af, om hele systemet er indeholdt helt i en af de prækomplette klasser. Hvis der for hver klasse i systemet er en funktion, som ikke er inkluderet i det, så vil et sådant system være komplet, og ved hjælp af de funktioner, der er inkluderet i det, vil det være muligt at få en hvilken som helst anden boolsk funktion. Post beviste, at sættet af lukkede klasser af boolske funktioner er et tælleligt sæt . $P_2$

Bemærk, at der er funktioner, som ikke er inkluderet i nogen af Posts klasser. Enhver sådan funktion danner i sig selv et komplet system. Eksempler inkluderer Schaeffers slag eller Pierces pil .

Repræsentation af booleske funktioner

Posts sætning åbner vejen for at repræsentere boolske funktioner på en syntaktisk måde, der i nogle tilfælde viser sig at være meget mere praktisk end sandhedstabeller. Udgangspunktet her er at finde et komplet system af funktioner . Så kan hver boolsk funktion repræsenteres af et led i signaturen , som i dette tilfælde også kaldes en formel . Med hensyn til det valgte system af funktioner er det nyttigt at kende svarene på følgende spørgsmål: $\Sigma =\{f_{1},\ldots ,f_{n}\}$ $\Sigma$

Hvordan bygger man en formel, der repræsenterer denne funktion?
Hvordan kontrollerer man, at to forskellige formler er ækvivalente, det vil sige, at de definerer den samme funktion?
- Især: er der en måde at reducere en vilkårlig formel til dens ækvivalente kanoniske form, således at to formler er ækvivalente, hvis og kun hvis deres kanoniske former er ens?
Hvordan kan en given funktion bruges til at konstruere en formel, der repræsenterer den med bestemte givne egenskaber (for eksempel den mindste størrelse), og er dette muligt?

Positive svar på disse og andre spørgsmål øger den anvendte værdi af det valgte system af funktioner markant.

Disjunktiv normalform (DNF)

En simpel konjunktion eller konjunktion er en konjunktion af et endeligt sæt af variabler eller deres negationer, hvor hver variabel højst forekommer én gang. Den disjunktive normalform eller DNF er disjunktionen af simple konjunktioner. Elementær konjunktion

korrekt , hvis hver variabel ikke er inkluderet i den mere end én gang (inklusive negation);
komplet , hvis hver variabel (eller dens negation) indtaster den nøjagtigt 1 gang;
monotonisk , hvis den ikke indeholder negationer af variable.

For eksempel - er en DNF. $a{\overline {b}}c\lor b{\overline {c}}\lor {\overline {a}}$

En perfekt disjunktiv normalform eller SDNF med hensyn til et givet endeligt sæt af variabler er en DNF, således at hver konjunktion indeholder alle variablerne i det givne sæt og i samme rækkefølge. For eksempel :. $a\overline {b}c\lor abc\lor \overline {a}b\overline {c}$

Det er let at se, at hver boolsk funktion svarer til en eller anden DNF, og til en anden funktion end det identiske nul, endda en SDNF. For at gøre dette er det nok at finde i sandhedstabellen for denne funktion alle boolske vektorer, hvor dens værdi er lig med 1, og for hver sådan vektor at konstruere en konjunktion , hvor . Disjunktionen af disse konjunktioner er SDNF for den oprindelige funktion, da dens værdier på alle boolske vektorer falder sammen med værdierne for den oprindelige funktion. For eksempel, for en implikation , er resultatet , som kan forenkles til . $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\til y$ $\overline {x}y\lor \overline {x}\,\overline {y}\lor xy$ $\overline {x}\lor y$

Konjunktiv normalform (CNF)

Konjunktiv normal form (CNF) er defineret dobbelt med DNF. En simpel disjunktion eller disjunct er en disjunktion af en eller flere variable eller deres negationer, og hver variabel er inkluderet i den ikke mere end én gang. CNF er en konjunktion af simple disjunktioner.

En perfekt konjunktiv normalform (PCNF), med hensyn til et givet endeligt sæt af variabler, er en sådan CNF, hvor hver disjunktion inkluderer alle variablerne i dette sæt, og i samme rækkefølge. Da (C)CNF og (C)DNF er gensidigt dobbelte, gentager egenskaberne af (C)CNF alle egenskaberne for (C)DNF, groft sagt "præcis det modsatte".

CNF kan konverteres til dets tilsvarende DNF ved at åbne parenteser i henhold til reglen:

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

som udtrykker konjunktionens fordeling i forhold til disjunktionen. Derefter er det nødvendigt at fjerne gentagne variabler eller deres negationer i hver konjunktion, og også at kassere fra disjunktionen alle konjunktioner, hvor variablen forekommer sammen med dens negation. I dette tilfælde vil resultatet ikke nødvendigvis være SDNF, selvom den oprindelige CNF var SKNF. På samme måde kan man altid gå fra DNF til CNF. For at gøre dette skal du bruge reglen

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

udtrykker fordelingen af disjunktionen i forhold til konjunktionen. Resultatet skal transformeres på den måde, der er beskrevet ovenfor, og erstatte ordet "konjunktion" med "disjunktion" og omvendt.

Algebraisk normalform (ANF eller Zhegalkin polynomium)

Algebraisk normalform (almindelig navn i udenlandsk litteratur) eller Zhegalkin-polynomium (navn brugt i indenlandsk litteratur) er en form for repræsentation af en logisk funktion som et polynomium med koefficienter på formen 0 og 1, hvori konjunktionsoperationen ("AND" , AND), og som addition - addition modulo 2 (eksklusiv "ELLER", XOR). For at opnå Zhegalkin-polynomiet skal du gøre følgende:

Hent sdnf-funktioner
Erstat Alle ELLER med Eksklusiv ELLER
I alle termer skal du erstatte elementer med negation med konstruktionen: ("element" "eksklusiv ELLER" 1)
Åbn parenteserne i henhold til reglerne i Zhegalkin-algebraen og giv identiske udtryk i par

Klassifikation af booleske funktioner

Ved antallet n af inputoperander, som værdien ved udgangen af funktionen afhænger af, er der null ( n = 0), unære ( n = 1), binære ( n = 2), ternære ( n = 3) boolsk funktioner og funktioner fra et større antal operander.

Ved antallet af enere og nuller i sandhedstabellen, en smal klasse af balancerede boolske funktioner (også kaldet balancerede eller ligesandsynlige, da med ligesandsynlige tilfældige værdier ved input eller ved iteration af alle kombinationer i sandhedstabellen, er sandsynligheden for at opnå værdien 1 ved udgangen er 1/2) adskilles fra den bredere klasse af ubalancerede booleske funktioner (også kaldet ubalancerede, da sandsynligheden for at få værdien 1 ved udgangen er forskellig fra 1/2). Balancerede booleske funktioner bruges primært i kryptografi .

I henhold til funktionsværdiens afhængighed af permutationen af dens inputbit, symmetriske booleske funktioner (hvis værdien kun afhænger af antallet af enheder ved input) og asymmetriske boolske funktioner (hvis værdien også afhænger af permutationen af dens inputbits) skelnes.

Selvdobbelte funktioner (hvis værdien inverteres, når værdierne af alle input er inverteret) adskilles fra andre boolske funktioner, der ikke har denne egenskab ved værdien af funktionen på modsatte sæt af argumentværdier . Den nederste del af sandhedstabellen for selvdobbelte funktioner er et spejlbillede af den omvendte øvre del (hvis du arrangerer inputkombinationerne i sandhedstabellen i en naturlig rækkefølge).

Ifølge den algebraiske grad af ikke-linearitet skelnes der mellem lineære booleske funktioner ( hvis ANF er reduceret til en lineær sum modulo 2 af inputværdierne) og ikke-lineære booleske funktioner ( hvor ANF indeholder mindst én ikke-lineær operation af konjunktion af inputværdier). Eksempler på lineære funktioner er: modulo 2 addition (eksklusiv OR, XOR), ækvivalens , samt alle boolske funktioner, hvis ANF kun indeholder lineære modulo 2 additionsoperationer uden konjunktioner. Eksempler på ikke-lineære funktioner er: konjunktion ("AND", AND), Schaeffer streg ("NOT-AND", NAND), Pierces pil ("NOT-OR", NOR), samt alle booleske funktioner, hvis ANF indeholder mindst én ikke-lineær konjunktionsoperation.

Væsentlige og dummy-variabler

En variabel af en boolsk funktion kaldes essentiel, hvis der for en boolsk funktion er to sæt værdier af dens argumenter, der kun adskiller sig i værdien af denne variabel, og værdierne af den boolske funktion på dem er forskellige. Hvis værdierne af denne funktion falder sammen med dem, kaldes variablen dummy. En variabel er essentiel, hvis og kun hvis den indtaster en perfekt DNF for en boolsk funktion, eller den indtaster et Zhegalkin-polynomium af en boolsk funktion.

To boolske funktioner kaldes lige, hvis mængderne af deres essentielle variabler er ens, og værdierne af funktionerne falder sammen med to lige store værdisæt af de essentielle variabler. [9]

Se også

Litteratur

Alekseev V.B. (foredragsholder), Pospelov A.D. (kompilator). Diskret matematik (forelæsningsforløb, 2. semester) . - M. : Red. ulige. fak. Beregn. Matematik og kybernetik, Moscow State University. M. V. Lomonosov, 2002. - 44 s.
Bykova S. V., Burkatovskaya Yu. B. Boolske funktioner: en lærebog for studerende fra videregående uddannelsesinstitutioner, der studerer i specialet HPE 010501 "Anvendt matematik og informatik" . - Tomsk: Tomsk-staten. un-t, 2010. - 190 s.
Gavrilov G. P., Sapozhenko A. A. Problemer og øvelser i diskret matematik . - M. : FIZMATLIT, 2009.
Igoshin VI Matematisk logik og teori om algoritmer . - 2. udg., stereotype .. - M . : Publishing Center "Academy", 2008. - 448 s.
Kuznetsov OP Diskret matematik for en ingeniør . - Sankt Petersborg. : Lan, 2007. - 394 s.
Lærebøger fra Institut for Matematisk Kybernetik i VMiK MSU (på hjemmesiden for Institut for Matematisk Kybernetik i MSU VMK).
Lozhkin S.A. Forelæsninger om det grundlæggende i kybernetik: lærebog. manual til kurserne "Fundamentals of Cybernetics" og "Structure. diskret implementering. funktioner" . - M. : Red. ulige. fak. Beregn. Matematik og kybernetik, Moscow State University. M. V. Lomonosov, 2004. - 254 s.
Marchenkov SS Lukkede klasser af booleske funktioner . - M. : Fizmatlit, 2001. - 126 s.
Samofalov K. G., Romankevich A. M., Valuysky V. N., Kanevsky Yu. S., Pinevich M. M. Anvendt teori om digitale automater . - Kiev: Vishcha Shkola, 1987. - S. 183-189. — 375 s.
Yablonsky SV Introduktion til diskret matematik . - M . : Højere. skole, 2006. - 384 s.

Links

↑ Igoshin, 2008 , kapitel 2. Boolske funktioner.
↑ 1 2 Igoshin, 2008 , s. 94.
↑ Igoshin, 2008 , s. 104-105.
↑ Samofalov, 1987 .
↑ Elementære booleske funktioner . Hentet 9. november 2016. Arkiveret fra originalen 10. november 2016. (ubestemt)
↑ 1 2 Udvalgte spørgsmål i teorien om booleske funktioner. // A. S. Balyuk et al. Ed. S. F. Vinokurov og N. A. Peryazev. — M.: FIZMATLIT, 2001. — 192 s. - S. 13.
↑ Igoshin, 2008 , s. 96.
↑ I.A. Nasyrov. læremiddel . Hentet 20. november 2020. Arkiveret fra originalen 22. december 2019. (ubestemt)
↑ Gavrilov G.P., Sapozhenko A.A. Samling af problemer i diskret matematik. - M., Nauka, 1977. - s. 44, 46, 47

Ordbøger og encyklopædier	Stor russer
I bibliografiske kataloger	LNB : 000324702