Голосарій курсу

Кореневе дерево називають $m$-арним, якщо кожна його внутрішня вершина має не більше ніж $m$ синів.

Граф, вершини якого відповідають усім $2^n$ бітовим рядкам довжиною  $n$, називають $n$ - вимірним кубом і позначають $Q_n$.

Простий граф $G$ називають  $t$ – зв’язним, якщо  $\kappa(G) \geq t$ і реберно - $t$ - зв’язним, якщо   $\lambda(G) \geq t$.

Множину $P_2$ всіх булевих функцій разом з уведеною на ній системою операцій називають алгеброю булевих функцій.

Алгебру $(P_2; \neg, \wedge,\vee)$ з операціями заперечення, кон’юнкції та диз’юнкції називають алгеброю Буля.

Алгебру $(P_2;\wedge, \oplus )$ з операціями кон’юнкції та додавання за mod2 називають алгеброю Жегалкіна.

Нехай $T$ – кореневе дерево. 

Якщо $v$ – його вершина, відмінна від кореня, то батько $v$ – це єдина вершина $u$ така, що є орієнтоване ребро $(u,v)$. Якщо $u$ – батько, то $v$ – син. 

Аналогічно за генеалогічною термінологією можна означити інших предків і нащадків вершини $v$.

Бінарне відношення з $A$ в $B$ – це підмножина $R$ декартового добутку $A\times B$  цих множин: $R \subset A\times B$.

Якщо $(a,b)\in R$, то пишуть $aRb$.

Матрицю, кожний елемент якої дорівнює $0$ або $1$, називають булевою.

Булевою називають функцію $f({{x}_{1}},...,{{x}_{n}})$ з областю значень $\{0, 1\}$, змінні ${x}_{1},..., {x}_{n}$ якої також набувають лише цих двох значень.