Функции алгебры логики

$(y \& x) \vee (\neg y \& z)$;

$(x \& y) \vee \neg x$;

$(x \supset (y \supset z)) \supset ((x \supset y) \supset (x \supset z))$.

и $\supset$ через $\vee$ и $\neg$;

$\vee$ и $\supset$ через и $\neg$;

и $\vee$ через $\supset$ и $\neg$;

, $\vee$, $\supset$, $\neg$ через $\mid$;

$\neg$ через $\supset$ и 0;

$\neg$ через $+$ и 1;

$\vee$ через $\supset$.

$\neg$ через , $\vee$, $\supset$ и $\equiv$;

$\supset$ через , $\vee$;

через $\vee$, $\supset$.

Доказать, что для каждой функции $f(x, x_{1}, \ldots , x_{n})$ выполняется равенство

Пусть $n \geq i \geq 1$. Доказать, что каждую функцию $f(x_{1}, \ldots , x_{n})$ алгебры логики можно представить в виде

где $\varepsilon_{j} \in \left\{ 0, 1\right\}$, $x_{j}^{0} = \neg x_{j}$, $x_{j}^{1} = x_{j}$.

$\left\{ \& , \vee , \neg \right\}$;

$\left\{ \vee , \neg \right\}$;

$\left\{ \& , \neg \right\}$;

$\left\{ \supset , \neg \right\}$.

$\left\{ \& , \vee , \supset \right\}$;

$\left\{ \neg \right\}$.

$\left\{ \mid \right\}$;

$\left\{ \downarrow \right\}$ (здесь $\downarrow = \neg (x \vee y)$);

$\left\{ \supset , 0\right\}$;

$\left\{ +, \vee , 1\right\}$.

$\left\{ +, \cdot , 1\right\}$ --- полная система функций;

любая функция $f(x_{1}, \ldots , x_{n})$ единственным образом представима полиномом Жегалкина, т.е. в виде:

где $\varepsilon_{0}, \varepsilon_{i_{1} \ldots i_{k}} \in \left\{ 0, 1\right\}$.

$\left\{ \neg , \equiv \right\}$;

$\left\{ \neg , +\right\}$;

$\left\{ \equiv , +\right\}$;

$\left\{ \equiv , \vee \right\}$.

$\left\{ \supset , /\right\}$, где $x / y = \neg (y \supset x)$;

$\left\{ 0, 1, [\cdot , \cdot , \cdot ]\right\}$, где $[x, y, z] = (y \& x) \vee (\neg y \& z)$;

$\left\{ \equiv , \vee , 0\right\}$.

состоящей из одной 3-местной функции;

состоящей из одной $n$-местной функции ($n \geq 2$).

$\left\{ \& , \supset \right\}$ --- базис для $C_{1}$;

$\left\{ \& , +\right\}$ --- базис для $C_{0}$;

$\left\{ \vee , \& , 0, 1\right\}$ --- базис для $M$;

$\left\{ 0, \equiv \right\}$ --- базис для $L$;

$\left\{ \neg , xy + xz + yz\right\}$ --- базис для $D$.

из всякой немонотонной функции и функций 0 и 1 можно получить суперпозициями функцию $\neg$;

класс $M$ является предполным классом.

из всякой несамодвойственной функции и функции $\neg$ можно получить суперпозициями функций 0 и 1;

класс $D$ является предполным классом.

из всякой нелинейной функции и функций 0, 1, $\neg$ можно получить суперпозициями функцию ;

класс $L$ является предполным классом.

$\varepsilon ((T \vee T_{1}), x) \Leftrightarrow (\varepsilon (T, x) \vee \varepsilon (T_{1}, x))$;

$\varepsilon ((T \& T_{1}), x) \Leftrightarrow (\varepsilon (T, x) \& \varepsilon (T_{1}, x))$;

$\varepsilon (\neg T, x) \Leftrightarrow \neg \varepsilon (T, x)$.

$Z(\neg T) = -Z(T)$, где $-Z = U \backslash Z$;

$Z(T \vee T_{1}) = Z(T) \cup Z(T_{1})$;

$Z(T \& T_{1}) = Z(T) \cap Z(T_{1})$.

если $f(a_{1}, \ldots , a_{k}) = g(a_{1}, \ldots , a_{k})$ для всех $a_{1}, \ldots , a_{k}$, то в теории множеств выполняется тождество $Z(T) = Z(T_{1})$;

если $(f(a_{1}, \ldots , a_{k}) \supset g(a_{1}, \ldots , a_{k})) = 1$ для всех $a_{1}, \ldots , a_{k}$, то в теории множеств выполняется соотношение $Z(T) \subseteq Z(T_{1})$;

если $f(a_{1}, \ldots , a_{k}) = 1$ для всех $a_{1}, \ldots , a_{k}$, то в теории множеств выполняется тождество $Z(T) = U$;

если $f(a_{1}, \ldots , a_{k}) = 0$ для всех $a_{1}, \ldots , a_{k}$, то в теории множеств выполняется тождество $Z(T) = \emptyset$.

$(X \cup Y) \cup Z = X \cup (Y \cup Z)$;

$X \cap Y = Y \cap X$;

$-(X \cap Y) = -X \cup -Y$;

$-(-X) = X$?

$(a \& (\neg a \vee b)) \supset b = 1$;

$a \& (a \vee b) = a$;

$a \vee \neg a = 1$;

$(a \& b) \supset (a \vee b) = 1$;

$a \& b = b \& a$;

$a = a \& (b \vee \neg b)$;

$\neg (a \& b) = \neg a \vee \neg b$;

$(a \& b) \vee a = a$;

$(a \& b) \& c = a \& (b \& c)$;

$\neg (a \vee b) = \neg a \& \neg b$;

$a \vee (a \& b) = a$;

$(a \vee b) \vee c = a \vee (b \vee c)$;

$a \& \neg a = 0$?