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

Нехай $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}$ якої також набувають лише цих двох значень.

Нехай $P$ – $m\times k$ матриця, $Q$ – $k\times n$ матриця.

Булевий добуток матриць $P$ та $Q$ – це $m\times n$ матриця $Z=P \odot Q$, елементи якої $z_{ij}=(p_{i1}\wedge q_{1j})\vee(p_{i2}\wedge q_{2j})\vee ... \vee (p_{ik}\wedge q_{kj})=\vee_{r=1}^{k}(p_{ir}\wedge q_{rj})$,  $i=\overline{1,m}$, $j=\overline{1,n}$.

Булевий степінь для булевих $n\times n$ матриць (позначають як $A^{[r]}$, $r\in N$) означають так: $A^{[r]}=\underbrace{A\odot A\odot ... \odot A }_ r$.