Booleovská funkce

Booleovská funkce (nebo logická funkce nebo funkce algebry logiky ) [1] z n argumentů - v diskrétní matematice - zobrazení B n → B , kde B = {0,1} je booleovská množina . Prvky booleovské množiny {1, 0} jsou obvykle interpretovány jako logické hodnoty „true“ a „false“, i když v obecném případě jsou považovány za formální symboly, které nemají konkrétní význam. Nezáporné celé číslo n , označující počet argumentů, se nazývá arita nebo lokalita funkce, v případě n = 0 se booleovská funkce změní na booleovskou konstantu . Prvky kartézského součinu ( n-tá přímá mocnina) B n se nazývají booleovské vektory . Množina všech booleovských funkcí libovolného počtu argumentů je často označována P 2 a n argumentů P 2 ( n ). Proměnné, které přebírají hodnoty z booleovské množiny, se nazývají booleovské proměnné [2] . Booleovské funkce jsou pojmenovány po matematikovi George Boole .

Při práci s booleovskými funkcemi dochází k úplné abstrakci od smysluplného významu, který se předpokládá v algebře výroků [2] . Přesto lze mezi booleovskými funkcemi a formulemi výrokové algebry vytvořit korespondenci jedna ku jedné , pokud [3] :

vytvořit vzájemnou korespondenci mezi booleovskými a výrokovými proměnnými ;
vytvořit spojení mezi booleovskými funkcemi a logickými spojovacími prvky;
ponechte prioritu operací beze změny.

Základní informace

Každá booleovská funkce arity n je kompletně definována nastavením jejích hodnot na její definiční doménu, tedy na všechny booleovské vektory délky n . Počet takových vektorů je roven 2 n . Protože booleovská funkce může mít na každém vektoru buď 0, nebo 1, počet všech n -árních booleovských funkcí je 2 (2 n ) . Proto jsou v této části uvažovány pouze ty nejjednodušší a nejdůležitější booleovské funkce.

Téměř všechny booleovské funkce nižších arit (0, 1, 2 a 3) dostaly historická jména. Pokud hodnota funkce nezávisí na jedné z proměnných (tedy ve skutečnosti pro libovolné dva booleovské vektory, které se liší pouze hodnotou této proměnné, je hodnota funkce na nich stejná), pak toto proměnná, aniž by hrála nějakou „hodnotu“, se nazývá fiktivní .

Pravdivé tabulky

Booleovská funkce je definována konečnou množinou hodnot, což umožňuje, aby byla reprezentována jako pravdivostní tabulka , například [4] :

x 1	x2 _	…	xn - 1	x n	f ( x 1 , x 2 , …, x n )
0	0	…	0	0	0
0	0	…	0	jeden	0
0	0	…	jeden	0	jeden
0	0	…	jeden	jeden	0
$\vtečky$	$\vtečky$	$\ddots$	$\vtečky$	$\vtečky$	$\vtečky$
jeden	jeden	…	0	0	jeden
jeden	jeden	…	0	jeden	0
jeden	jeden	…	jeden	0	0
jeden	jeden	…	jeden	jeden	0

Nulové funkce

Pro n = 0 se počet booleovských funkcí redukuje na dvě 2 2 0 = 2 1 = 2, první z nich je shodně rovna 0 a druhá 1. Říká se jim booleovské konstanty - shodně nula a shodně jedna .
Tabulka hodnot a názvů null booleovských funkcí:

	Význam	Označení	název
	0	F0,0 = 0	identická nula
	jeden	F0,1 = 1	identická jednotka, tautologie

Unární funkce

Pro n = 1 je počet booleovských funkcí 2 2 1 = 2 2 = 4. Tyto funkce jsou definovány v následující tabulce.

Tabulka hodnot a názvů booleovských funkcí z jedné proměnné:

x0 = x	jeden	0	Označení	název
0	0	0	F1,0 = 0	identická nula
jeden	0	jeden	F1,1 = x = ¬ x = x' = NE(x)	negace, logické "NE", "NE", "NOR", invertor , SWAP (výměna)
2	jeden	0	F1,2 = x	funkce identity, logické "ANO", opakovač
3	jeden	jeden	F1,3=1	identická jednotka, tautologie

Binární funkce

Pro n = 2 je počet booleovských funkcí 2 2 2 = 2 4 = 16.

Tabulka hodnot a názvů booleovských funkcí ze dvou proměnných:

x0 = x	jeden	0	jeden	0	Zápis funkce	Název funkce
x 1 = y	jeden	jeden	0	0	Zápis funkce	Název funkce
0	0	0	0	0	F2,0=0	identická nula
jeden	0	0	0	jeden	F2,1 = x ↓ y = x NOR y = NOR( x , y ) = x NOR y = NOR ( x , y ) = NE(MAX(X,Y))	Pierce arrow - "↓" ( Quineova dýka - "†"), Webbova funkce - "°" [5] , NON-OR, 2OR-NOT, antidisjunkce, maximální inverze
2	0	0	jeden	0	F2,2 = x > y = x GT y = GT( x , y ) = x → y = x ↛ y	porovnávací funkce "první operand je větší než druhý operand", inverzní k přímé implikaci , koimplikace [6]
3	0	0	jeden	jeden	F2,3 = y = y' = ¬ y = NOT2 ( x , y ) = NOT2 ( x , y )	negace (negace, inverze) druhého operandu
čtyři	0	jeden	0	0	F2,4 = x < y = x LT y = LT( x , y ) = x ← y = x ↚ y	porovnávací funkce "první operand je menší než druhý operand", inverzní implikace , inverzní koimplikace [6]
5	0	jeden	0	jeden	F2,5 = x = x' = ¬ x = NOT1( x , y ) = NOT1 ( x , y )	negace (negace, inverze) prvního operandu
6	0	jeden	jeden	0	F2,6 = x >< y = x <> y = x NE y = NE(x, y) = x ⊕ y = x XOR y = XOR( x , y )	porovnávací funkce "operandy se nerovnají", sčítání modulo 2 s výjimkou "nebo" , Zhegalkinův součet [7]
7	0	jeden	jeden	jeden	F2,7 = x \| y = x NAND y = NAND( x , y ) = x NAND y = NAND ( x , y ) = NE(MIN(X,Y))	Schaefferův zdvih , Chulkovova tečkovaná čára [8] , NAND, 2I-NOT, antikonjunkce, minimální inverze
osm	jeden	0	0	0	F2,8 = x ∧ y = x y = xy = x & y = x AND y = AND ( x , y ) = x AND y = AND ( x , y ) = min ( x , y )	konjunkce , 2I, minimum
9	jeden	0	0	jeden	F2.9 = ( x ≡ y ) = x ~ y = x ↔ y = x EQV y = EQV ( x , y )	srovnávací funkce "operandy se rovnají", ekvivalence
deset	jeden	0	jeden	0	F2,10 = ANO1 ( x , y ) = ANO1 ( x , y ) = x	první operand
jedenáct	jeden	0	jeden	jeden	F2,11 = x ≥ y = x >= y = x GE y = GE( x , y ) = x ← y = x ⊂ y	porovnávací funkce "první operand není menší než druhý operand", obrácená implikace (od druhého argumentu k prvnímu)
12	jeden	jeden	0	0	F2,12 = ANO2( x , y ) = ANO2( x , y ) = y	druhý operand
13	jeden	jeden	0	jeden	F2.13 = x ≤ y = x <= y = x LE y = LE( x , y ) = x → y = x ⊃ y	porovnávací funkce "první operand není větší než druhý operand", přímá (materiální) implikace (z prvního argumentu do druhého)
čtrnáct	jeden	jeden	jeden	0	F2,14 = x ∨ y = x + y = x NEBO y = OR( x , y ) = x OR y = OR( x , y ) = max( x , y )	disjunkce , 2OR, max
patnáct	jeden	jeden	jeden	jeden	F2,15=1	identická jednotka, tautologie

Se dvěma argumenty jsou prefix , infix a postfixová notace z ekonomického hlediska téměř stejné.

Některé funkce, které dávají smysl v digitální technologii , jako jsou porovnávací funkce, minimum a maximum, nedávají smysl v logice, protože v logice obecně booleovské hodnoty TRUE a FALSE nemají pevnou vazbu na číselné hodnoty (například v TurboBasic , pro zjednodušení některých výpočtů, TRUE = -1 a FALSE = 0) a není možné určit, co je větší než TRUE nebo FALSE, zatímco implikace a další dávají smysl jak v digitální technologii, tak v v logice.

Ternární funkce

Pro n = 3 je počet booleovských funkcí 2 (2 3 ) = 2 8 = 256. Některé z nich jsou definovány v následující tabulce:
Tabulka hodnot a názvů některých booleovských funkcí ze tří proměnných s vlastním názvem :

x0 = x	jeden	0	jeden	0	jeden	0	jeden	0	Notový zápis	Tituly
x 1 = y	jeden	jeden	0	0	jeden	jeden	0	0
x 2 \u003d z	jeden	jeden	jeden	jeden	0	0	0	0
jeden	0	0	0	0	0	0	0	jeden	F3,1 = x ↓ y ↓ z = ↓(x,y,z) = Webb 2 (x,y,z) = NOR(x,y,z)	3OR-NOT, funkce Webb, Pierceův šíp , Quineova dýka - "†"
23	0	0	0	jeden	0	jeden	jeden	jeden	F3,23 = = ≥2(x,y,z) $\neg (>=2(x,y,z))$	Většinový spínač s inverzí, 3PPB-NE, většinový ventil s inverzí
71	0	jeden	0	0	0	jeden	jeden	jeden	F3,71= $[x,y,z]$	Podmíněná disjunkce
126	0	jeden	jeden	jeden	jeden	jeden	jeden	0	F3.126 = (x≠y≠z) = [≠(x,y,z)] = NE(x,y,z)	Nerovnost
127	0	jeden	jeden	jeden	jeden	jeden	jeden	jeden	F3,127 = x\|y\|z = \|(x,y,z) = NAND(x,y,z)	3I-NE, Schaefferův zdvih
128	jeden	0	0	0	0	0	0	0	F3,128 = x&y&z = &(x,y,z) = (x AND y AND z) = AND(x,y,z) = (x AND y AND z) = AND(x,y,z) = min (x,y,z)	3I, minimum
129	jeden	0	0	0	0	0	0	jeden	F3.129 = (x=y=z) = [=(x,y,z)] = EQV(x,y,z)	Rovnost
150	jeden	0	0	jeden	0	jeden	jeden	0	F3,150 = x⊕y⊕z = x⊕ 2 y⊕ 2 z = ⊕ 2 (x,y,z)	Ternární sčítací modul 2
216	jeden	jeden	0	jeden	jeden	0	0	0	F3,216 = f 1	Ternární odčítání výpůjčky
232	jeden	jeden	jeden	0	jeden	0	0	0	F3,232 = f 2 = [>=2(x,y,z)] = ≥2(x,y,z) = (x AND y) NEBO (y AND z) NEBO (z AND x)	Ternární přídavný nosný bit, majoritní přepínač, 3PPB, majoritní ventil
254	jeden	jeden	jeden	jeden	jeden	jeden	jeden	0	F3,254 = (x+y+z) = +(x,y,z) = (x OR y OR z) = OR(x,y,z) = (x OR y OR z) = OR(x, y,z) = max(x,y,z)	NEBO, maximum

Se třemi nebo více argumenty je předponová (a postfixová) notace ekonomičtější než infixová notace.
Obvyklý způsob zápisu funkcí je prefix (před operandy). S infixovým (mezi operandy) zápisem funkcí se funkce nazývají operátory a argumenty funkcí se nazývají operandy.

Kompletní systémy booleovských funkcí

Superpozice a uzavřené třídy funkcí

Výsledek vyhodnocení booleovské funkce lze použít jako jeden z argumentů jiné funkce. Na výsledek takové operace superpozice lze pohlížet jako na novou booleovskou funkci s vlastní pravdivostní tabulkou. Například funkce (superpozice konjunkce, disjunkce a dvou negací) bude odpovídat následující tabulce: $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	jeden
0	0	jeden	jeden
0	jeden	0	jeden
0	jeden	jeden	jeden
jeden	0	0	0
jeden	0	jeden	0
jeden	jeden	0	jeden
jeden	jeden	jeden	0

O množině funkcí se říká, že je uzavřena operací superpozice, pokud je ve stejné množině také zahrnuta jakákoli superpozice funkcí z dané množiny. Uzavřené sady funkcí se také nazývají uzavřené třídy .

Jako nejjednodušší příklady uzavřených tříd booleovských funkcí lze pojmenovat množinu sestávající z jedné identické funkce nebo množinu , z nichž jsou všechny funkce shodně rovny nule, bez ohledu na jejich argumenty. Uzavřená je také množina funkcí a množina všech unárních funkcí. Ale unie uzavřených tříd už taková být nemusí. Například spojením tříd a můžeme pomocí superpozice získat konstantu 1, která v původních třídách chyběla. $\{X\}$ $\{0\}$ $\{x,\overline {x}\}$ $\{0\}$ $\{x,\overline {x}\}$ $\overline {0}$

Uzavřená je samozřejmě i množina všech možných booleovských funkcí. $P_2$

Identita a dualita

Dvě booleovské funkce jsou navzájem identické, pokud mají stejné hodnoty v jakékoli identické sadě argumentů. Identitu funkcí f a g lze zapsat například takto:
$f(x_{1},x_{2},\tečky,x_{n})=g(x_{1},x_{2},\tečky,x_{n})$

Při pohledu na pravdivostní tabulky booleovských funkcí je snadné získat následující identity:

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

A kontrola tabulek vytvořených pro některé superpozice poskytne následující výsledky:

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 Morganovy zákony )

$x(y\nebo z)=xy\nebo xz$
$x\lor yz=(x\lor y)(x\nebo z)$ ( distributivita konjunkce a disjunkce)

Funkce se nazývá duální funkce if . Je snadné ukázat, že v této rovnosti mohou být f a g zaměněny, to znamená, že funkce f a g jsou navzájem duální. Z nejjednodušších funkcí jsou konstanty 0 a 1 navzájem duální a dualita konjunkce a disjunkce vyplývá z De Morganových zákonů. Identická funkce, stejně jako funkce negace, je sama o sobě duální. $g(x_{1},x_{2},\tečky,x_{n})$ $f(x_{1},x_{2},\tečky,x_{n})$ $f(\overline {x_{1}},\overline {x_{2}},\tečky ,\overline {x_{n}})=\overline {g(x_{1},x_{2},\tečky ,x_{n})}$

Pokud v booleovské identitě nahradíme každou funkci jejím duálem, dostaneme opět správnou identitu. Ve výše uvedených vzorcích je snadné najít dvojice duální k sobě.

Úplnost systému, Postovo kritérium

Systém booleovských funkcí se nazývá úplný , pokud je možné sestrojit jejich superpozici, která je shodná s jakoukoli předdefinovanou funkcí. Také říkají, že uzavření daného systému se shoduje se souborem . $P_2$

Americký matematik Emil Post představil následující uzavřené třídy booleovských funkcí:

Funkce, které zachovávají konstantu a ; $P_0$ $P_1$
Self-duální funkce ; $S$
Monotónní funkce ; $M$
Lineární funkce . $L$

Dokázal, že jakákoli uzavřená třída booleovských funkcí, která se neshoduje s, je celá obsažena v jedné z těchto pěti takzvaných předkompletních tříd , ale žádná z těchto pěti není obsažena celá ve spojení ostatních čtyř. Postovo kritérium úplnosti systému se tedy scvrkává na zjištění, zda je celý systém zcela obsažen v jedné z předkompletních tříd. Pokud pro každou třídu v systému existuje funkce, která v ní není obsažena, pak bude takový systém kompletní a pomocí funkcí v něm obsažených bude možné získat jakoukoli jinou booleovskou funkci. Post dokázal, že množina uzavřených tříd booleovských funkcí je spočetná množina . $P_2$

Všimněte si, že existují funkce, které nejsou zahrnuty v žádné z Postových tříd. Každá taková funkce sama o sobě tvoří kompletní systém. Příklady zahrnují Schaefferův tah nebo Pierceův šíp .

Reprezentace booleovských funkcí

Postův teorém otevírá cestu k reprezentaci booleovských funkcí syntaktickým způsobem, který se v některých případech ukazuje jako mnohem pohodlnější než pravdivostní tabulky. Výchozím bodem je zde najít nějaký kompletní systém funkcí . Pak může být každá booleovská funkce reprezentována nějakým výrazem v podpisu , který se v tomto případě také nazývá vzorec . Ohledně zvoleného systému funkcí je užitečné znát odpovědi na následující otázky: $\Sigma =\{f_{1},\ldots ,f_{n}\}$ $\Sigma$

Jak sestavit vzorec reprezentující tuto funkci?
Jak zkontrolovat, zda jsou dva různé vzorce ekvivalentní, to znamená, že definují stejnou funkci?
- Konkrétně: existuje způsob, jak redukovat libovolnou formuli na její ekvivalentní kanonickou formu tak, že dvě formule jsou ekvivalentní právě tehdy, když jsou jejich kanonické formy stejné?
Jak lze z dané funkce sestavit vzorec, který ji představuje s určitými danými vlastnostmi (například nejmenší velikost) a je to možné?

Kladné odpovědi na tyto a další otázky výrazně zvyšují aplikovanou hodnotu zvoleného systému funkcí.

Disjunktivní normální forma (DNF)

Jednoduchá konjunkce nebo konjunkce je konjunkce nějaké konečné množiny proměnných nebo jejich negací, přičemž každá proměnná se vyskytuje nejvýše jednou. Disjunktivní normální forma nebo DNF je disjunkce jednoduchých spojek. Elementární konjunkce

správně , pokud je v něm každá proměnná zahrnuta nejvýše jednou (včetně negace);
kompletní , pokud do něj každá proměnná (nebo její negace) vstoupí právě 1x;
monotónní , pokud neobsahuje žádné negace proměnných.

Například - je DNF. $a{\overline {b}}c\lor b{\overline {c}}\lor {\overline {a}}$

Dokonalá disjunktivní normální forma nebo SDNF s ohledem na nějakou danou konečnou množinu proměnných je DNF taková, že každá konjunkce obsahuje všechny proměnné dané množiny a ve stejném pořadí. Například: . $a\overline {b}c\lor abc\lor \overline {a}b\overline {c}$

Je snadné vidět, že každá booleovská funkce odpovídá nějakému DNF a jiné funkci, než je identická nula, dokonce i SDNF. K tomu stačí najít v pravdivostní tabulce této funkce všechny booleovské vektory, na kterých je její hodnota rovna 1, a pro každý takový vektor sestrojit spojku , kde . Disjunkce těchto konjunkcí je SDNF původní funkce, protože na všech booleovských vektorech se její hodnoty shodují s hodnotami původní funkce. Například pro implikaci je výsledkem , což lze zjednodušit na . $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\do y$ $\overline {x}y\lor \overline {x}\,\overline {y}\lor xy$ $\overline {x}\lor y$

Konjunktivní normální forma (CNF)

Konjunktivní normální forma (CNF) je definována duálně k DNF. Jednoduchá disjunkce nebo disjunkce je disjunkce jedné nebo více proměnných nebo jejich negací a každá proměnná je v ní zahrnuta nejvýše jednou. CNF je konjunkce jednoduchých disjunkcí.

Dokonalá konjunktivní normální forma (PCNF) s ohledem na nějakou danou konečnou množinu proměnných je taková CNF, ve které každá disjunkce zahrnuje všechny proměnné této množiny, a to ve stejném pořadí. Protože (C)CNF a (C)DNF jsou vzájemně duální, vlastnosti (C)CNF opakují všechny vlastnosti (C)DNF, zhruba řečeno „přesně naopak“.

CNF lze převést na ekvivalentní DNF otevřením závorek podle pravidla:

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

který vyjadřuje distributivitu spojky vzhledem k disjunkci. Poté je nutné odstranit opakované proměnné nebo jejich negace v každé konjunkci a také vyřadit z disjunkce všechny konjunkce, ve kterých se proměnná vyskytuje spolu s její negací. V tomto případě výsledek nemusí být nutně SDNF, i když původní CNF byl SKNF. Podobně lze vždy přejít od DNF k CNF. K tomu použijte pravidlo

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

vyjadřující distributivitu disjunkce vzhledem ke spojce. Výsledek musí být transformován výše popsaným způsobem, přičemž slovo „konjunkce“ se nahradí výrazem „disjunkce“ a naopak.

Algebraická normální forma (ANF nebo Zhegalkinův polynom)

Algebraická normální forma (v zahraniční literatuře běžný název) nebo Zhegalkinův polynom (název používaný v domácí literatuře) je forma vyjádření logické funkce jako polynom s koeficienty tvaru 0 a 1, ve kterém je spojková operace („AND“ , AND), a jako sčítání - sčítání modulo 2 (výhradně "OR", XOR). Chcete-li získat Zhegalkinův polynom, postupujte takto:

Získejte funkce sdnf
Nahraďte vše NEBO za exkluzivní NEBO
Ve všech termínech nahraďte prvky negací konstrukcí: ("element" "exclusive OR" 1)
Otevřete závorky podle pravidel Zhegalkinovy algebry a zadejte stejné termíny ve dvojicích

Klasifikace booleovských funkcí

Podle počtu n vstupních operandů, na kterých závisí hodnota na výstupu funkce, existují nulové ( n = 0), unární ( n = 1), binární ( n = 2), ternární ( n = 3) booleovské funkce a funkce z většího počtu operandů .

Podle počtu jedniček a nul v pravdivostní tabulce je úzká třída vyvážených booleovských funkcí (nazývaných také vyvážené nebo ekvipravděpodobné, protože s ekvipravděpodobnými náhodnými hodnotami na vstupu nebo při iteraci všech kombinací v pravdivostní tabulce je pravděpodobnost získání hodnota 1 na výstupu je 1/2) se odlišuje od širší třídy nevyvážených booleovských funkcí (nazývaných také nevyvážené, protože pravděpodobnost získání hodnoty 1 na výstupu je jiná než 1/2). Vyvážené booleovské funkce se primárně používají v kryptografii .

Podle závislosti hodnoty funkce na permutaci jejích vstupních bitů se rozlišují symetrické booleovské funkce (jejichž hodnota závisí pouze na počtu jednotek na vstupu) a asymetrické booleovské funkce (jejichž hodnota závisí také na permutaci jeho vstupní bity) jsou rozlišeny.

Samoduální funkce (jejichž hodnota je invertována, když jsou invertovány hodnoty všech vstupů) se liší od ostatních booleovských funkcí, které tuto vlastnost nemají, hodnotou funkce na opačných sadách hodnot argumentů . Spodní část pravdivostní tabulky pro samoduální funkce je zrcadlovým obrazem obrácené horní části (pokud vstupní kombinace v pravdivostní tabulce uspořádáte v přirozeném pořadí).

Podle algebraického stupně nelinearity se rozlišují lineární booleovské funkce ( jejichž ANF je redukována na lineární součet modulo 2 vstupních hodnot) a nelineární booleovské funkce ( z nichž ANF obsahuje alespoň jednu nelineární operaci konjunkce vstupní hodnoty). Příklady lineárních funkcí jsou: sčítání modulo 2 (exkluzivní OR, XOR), ekvivalence , stejně jako všechny booleovské funkce, jejichž ANF obsahuje pouze lineární operace sčítání modulo 2 bez konjunkcí. Příklady nelineárních funkcí jsou: konjunkce ("AND", AND), Schaefferův tah ("NOT-AND", NAND), Pierceova šipka ("NOT-OR", NOR), stejně jako všechny booleovské funkce, jejichž ANF obsahuje alespoň jedna operace nelineární konjunkce.

Základní a fiktivní proměnné

Proměnná booleovské funkce se nazývá podstatná, pokud pro booleovskou funkci existují dvě sady hodnot jejích argumentů, které se liší pouze hodnotou této proměnné a liší se hodnoty booleovské funkce na nich. Pokud se na nich hodnoty této funkce shodují, pak se proměnná nazývá dummy. Proměnná je podstatná tehdy a jen tehdy, když vstupuje do dokonalého DNF booleovské funkce nebo vstupuje do Zhegalkinova polynomu booleovské funkce.

Dvě booleovské funkce se nazývají rovné, pokud jsou množiny jejich základních proměnných stejné a hodnoty funkcí se shodují na jakýchkoli dvou stejných množinách hodnot základních proměnných. [9]

Viz také

Literatura

Alekseev V.B. (přednášející), Pospelov A.D. (překladač). Diskrétní matematika (průběh přednášek, II semestr) . - M .: Ed. otd. fak. Vypočítat. Matematika a kybernetika, Moskevská státní univerzita. M. V. Lomonosov, 2002. - 44 s.
Bykova S. V., Burkatovskaya Yu. B. Boolean functions: učebnice pro studenty vysokých škol studujících v oboru HPE 010501 "Aplikovaná matematika a informatika" . - Tomsk: Tomský stát. un-t, 2010. - 190 s.
Gavrilov G. P., Sapozhenko A. A. Problémy a cvičení v diskrétní matematice . - M. : FIZMATLIT, 2009.
Igoshin VI Matematická logika a teorie algoritmů . - 2. vyd., stereotyp .. - M . : Vydavatelské centrum "Akademie", 2008. - 448 s.
Kuznetsov OP Diskrétní matematika pro inženýra . - Petrohrad. : Lan, 2007. - 394 s.
Učebnice Katedry matematické kybernetiky VMiK MSU (na webu Katedry matematické kybernetiky MSU VMK).
Lozhkin S.A. Přednášky o základech kybernetiky: učebnice. manuál pro kurzy „Základy kybernetiky“ a „Struktura. diskrétní implementace. funkce“ . - M .: Ed. otd. fak. Vypočítat. Matematika a kybernetika, Moskevská státní univerzita. M. V. Lomonosov, 2004. - 254 s.
Marchenkov SS Uzavřené třídy booleovských funkcí . - M. : Fizmatlit, 2001. - 126 s.
Samofalov K. G., Romankevich A. M., Valuysky V. N., Kanevsky Yu. S., Pinevich M. M. Aplikovaná teorie digitálních automatů . - Kyjev: Vishcha Shkola, 1987. - S. 183-189. — 375 str.
Yablonsky SV Úvod do diskrétní matematiky . - M .: Vyšší. škola, 2006. - 384 s.

Odkazy

↑ Igoshin, 2008 , Kapitola 2. Booleovské funkce.
↑ 1 2 Igoshin, 2008 , str. 94.
↑ Igoshin, 2008 , str. 104-105.
↑ Samofalov, 1987 .
↑ Elementární booleovské funkce . Získáno 9. listopadu 2016. Archivováno z originálu 10. listopadu 2016. (neurčitý)
↑ 1 2 Vybrané otázky teorie booleovských funkcí. // A. S. Balyuk a kol., Ed. S. F. Vinokurov a N. A. Peryazev. — M.: FIZMATLIT, 2001. — 192 s. - S. 13.
↑ Igoshin, 2008 , str. 96.
↑ I.A. Nasyrov. učební pomůcka . Získáno 20. listopadu 2020. Archivováno z originálu dne 22. prosince 2019. (neurčitý)
↑ Gavrilov G.P., Sapozhenko A.A. Sbírka úloh z diskrétní matematiky. - M., Nauka, 1977. - str. 44, 46, 47

Slovníky a encyklopedie	Velký Rus
V bibliografických katalozích	LNB : 000324702