Что такое замыкание (булева алгебра)?

[rar]

Можно доходчиво на примере объяснить, что такое замыкание?

[Xaositect]

Замыкание класса функций?

[rar]

Да. Класса или множества. Эти понятия эквивалентны.

[Xaositect]

Замыкание множества функций $F$ --- это множество всех функций, которые могут быть представлены формулами над этим множеством.

Например, возьмем $F = \{\bar{\phantom{x}}\}$. Какие функции могут быть представлены формулами над $F$? Любая формула имеет вид либо $\bar{x}$, либо $\bar{\mathcal{F}}$, где $\mathcal{F}$ - формула. Т.е. любая формула над множеством из одного отрицания - это переменная с каким-то количеством отрицаний над ней. Так как $\bar{\bar{x}} = x$, то $[F]$ будет состоять из двух функций - $x$ и $\bar{x}$

Еще пример. $F = \{\oplus, \wedge\}$. Пользуясь соотношением $(x\oplus y)z = xz \oplus yz$, а также коммутативностью и ассоциативностью конъюнкции, в любой формуле можно раскрыть скобки и получить выражение вида $\bigoplus x_{i_1}x_{i_2}\dots x_{i_k}$. Если подставить вместо всех переменных $0$, мы получим $0$. То есть любая формула представляет функцию из класса $T_0$. Обратно, если взять полином Жегалкина произвольной функции из $T_0$, он будет либо формулой над $F$, либо $0$. В последнем случае $0 = x\oplus x$, то есть функция тоже может быть представлена формулой над $F$. Таким образом, получаем $[F] = T_0$.

Еще пример $F = \{0, 1, \vee\}$. Любая формула - либо $0$, либо $1$, либо конъюнкция какого-то количества переменных, единиц либо нулей. Пользуясь соотношениями $0\vee x = x$, $x\vee x = x$ и $1\vee x = 1$, можно привести формулу к одному из трех видов: $0$, $1$ или $\bigvee\limits_k x_{i_k}$
Этот класс обозначают либо $D$, либо(в западной традиции) $\pmb{\pmb{\vee}}$: $D = [\{0,1,\vee\}]$

Если что-то непонятно, спрашивайте дальше, здесь я немного сумбурно объяснил и некоторые детали опустил.

[rar]

Спасибо. Почти разобрался.