Эквивалентность формул

если в логическом произведении хотя бы один из сомножителей равен 0, то и всё произведение равно 0 ;

если в логической сумме хотя бы одно из слагаемых равно 1, то и вся сумма равна 1;

если в логическом произведении $n \geqslant 2$ и есть сомножитель равный 1, то его можно вычеркнуть;

если в логической сумме $n \geqslant 2$ и есть слагаемое равное 0, то его можно вычеркнуть.

$\neg (x \vee \neg y) \wedge (x \rightarrow \neg y)$ и $\neg x \wedge y$;

$\neg ((x \wedge \neg y) \rightarrow (\neg x \vee z))$ и $x \wedge \neg y \wedge \neg z$;

$(x \oplus y) \rightarrow (x \wedge \neg y)$ и $(\neg x \wedge \neg y) \vee x$.

$\Phi \rightarrow 0 \equiv \neg \Phi$;

$1 \rightarrow \Phi \equiv \Phi$;

$(\Phi \rightarrow \Psi ) \rightarrow \Psi \equiv \Phi \vee \Psi$;

$\neg \Phi \rightarrow \Phi \equiv \Phi$;

$(\Phi \rightarrow \Phi ) \rightarrow \Phi \equiv \Phi$;

$\Phi \leftrightarrow \Psi \equiv (\Phi \rightarrow \Psi ) \wedge (\Psi \rightarrow \Phi ) ;$

$~ \Phi \vee (\neg \Phi \wedge \Psi ) \equiv \Phi \vee \Psi$;

$(\Phi \rightarrow \Psi ) \oplus (\Psi \rightarrow \Phi ) \equiv \Phi \oplus \Psi$.

$\Phi \rightarrow (\Psi \vee \Theta ) \equiv (\Phi \wedge \neg \Theta ) \rightarrow \Psi$;

$(\Phi \wedge \Theta ) \rightarrow \Psi \equiv \Phi \rightarrow (\Psi \vee \neg \Theta )$.

$(x \rightarrow (y \rightarrow x))$

$((x \wedge y) \rightarrow x)$

$(x \rightarrow (x \vee y))$

$((x \rightarrow \neg y) \rightarrow \neg (x \wedge y))$

$(((x \rightarrow y) \wedge (y \rightarrow z)) \rightarrow (x \rightarrow z))$

$(((x \rightarrow y) \vee (x \rightarrow z)) \rightarrow (x \rightarrow (y \vee z)))$

$((x \rightarrow y) \rightarrow ((x \rightarrow \neg y) \rightarrow \neg x))$

$((x \rightarrow (y \rightarrow z)) \rightarrow ((x \rightarrow y) \rightarrow (x \rightarrow z)))$

$\left(\neg x_{i} \wedge \Phi_{0}\right) \vee \left(x_{i} \wedge \Phi_{1}\right) ;$

$\left(\neg x_{i} \rightarrow \Phi_{0}\right) \wedge \left(x_{i} \rightarrow \Phi_{1}\right)$.

Доказать, что отношение двойственности симметрично.

Пусть $f\left(y_{1}, \ldots , y_{m}\right), g_{1}\left(x_{1}, \ldots , x_{n}\right), \ldots , g_{m}\left(x_{1}, \ldots , x_{n}\right)$ — булевы функции и

Установить следующий принцип двойственности: двойственная функция от суперпозиции функций равна суперпозиции двойственных функций:

$\neg$,

→,

$\oplus$,

↑.

$(x \rightarrow \neg (\neg y \oplus x \oplus z))$;

$((x \uparrow y) \oplus (\neg x \rightarrow z))$; $\circledast$

$((x \vee \neg y) \rightarrow (\neg x \downarrow y))$.

Доказать, что среди 20 формул от переменных $x_{1}, x_{2}$ всегда найдутся две эквивалентные.

Верно ли, что среди 20 формул от переменных $x_{1}, x_{2}$ всегда найдутся три попарно эквивалентные?

Пусть имеется $k$ формул от $n$ переменных $x_{1}, \ldots , x_{n}$. Требуется выбрать несколько попарно эквивалентных формул. Какое количество таких формул можно гарантированно найти?

каждая импликативная формула принимает значение 1 как минимум на одном наборе;

каждая импликативная формула принимает значение 0 как минимум на одном наборе;

для каждой импликативной формулы с $n \geqslant 2$ переменными и каждого значения $\sigma_{k}$ переменной $x_{k}$ существует возможность расширить $\sigma_{k}$ до набора значений $\bar{\sigma }$ всех переменных, на котором формула имеет значение 1 ;

каждая импликативная функция не имеет фиктивных аргументов;

никакие две разные импликативные формулы не эквивалентны.