Полные множества функций и теорема Поста

Доказать полноту множества $\left\{ \downarrow \right\}$, включающего только стрелку Пирса, непосредственно выразив через неё отрицание, дизъюнкцию и конъюнкцию.

Определить принадлежность каждой из функций, представленных в таблице на рис. 11 на стр. 107, каждому из множеств $\mathcal{S}_{0}, \mathcal{S}_{1}, \mathcal{S}, \mathcal{L}$ и $\mathcal{M}$.

Используя результаты задачи 86, определить, какие из троек функций, представленных на рис. 11 на стр. 107, являются полными множествами. Имеются ли среди них полные множества из двух функций? Из одной функции? Какие из них будут базисами?

Найти все базисы, которые можно получить, удаляя функции из множества $\left\{ 0,1, \wedge , \vee , \rightarrow \right\}$.

Проверить полноту множества функций $\left\{ g, h\right\}$, представленных в таблице на рис. 12 на стр. 113. Если она полна, выразить с помощью этих функций обе константы, отрицание $\neg$ и импликацию → .

Выразить функции $0,1, \vee , \wedge , \leftrightarrow \mathrm{c}$ помощью формул, построенных из функций полного множества $\left\{ \neg , \rightarrow \right\}$.

Определить, как по заданной ДНФ (КНФ) определить, будет ли она сохранять ноль или единицу, не вычисляя её значений.

Доказать, что замыканием множества $\left\{ \wedge , \vee , \rightarrow \right\}$ является $\mathcal{S}_{1}$. Можно ли то же самое утверждать для множества $\left\{ \wedge , \rightarrow \right\}$?

Назовём функцию $f\left(x_{1}, \ldots , x_{n}\right)$ линейной по переменной $x_{i}$, если $f$ можно представить в виде $f\left(x_{1}, \ldots , x_{n}\right)=g\left(x_{1}, \ldots , x_{n}\right) \oplus \alpha_{i} x_{i}$, где $g\left(x_{1}, \ldots , x_{n}\right)$ — некоторая функция, не зависящая от $x_{i}, \alpha_{i} \in \left\{ 0,1\right\}$. Доказать, что булева функция $f\left(x_{1}, \ldots , x_{n}\right)$ является линейной тогда и только тогда, когда она линейна по всем переменным.

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

Доказать, что для монотонных функций $f^{(n)} \in \mathcal{M}$ справедливо представление

для всех $i=1, \ldots , n$. Вывести отсюда (индукцией по $n$), что для всякой монотонной функции, отличной от константы, существуют задающие её ДНФ и КНФ, не содержащие отрицаний переменных.

Доказать, что булева функция $f^{(n)}$ является монотонной тогда и только тогда, когда она монотонна по каждому аргументу: для всех $i=1, \ldots , n$ и всех $\sigma_{1}, \ldots , \sigma_{n} \in \mathbb {B}$ выполнено неравенство

Доказать, что булева функция $f\left(x_{1}, \ldots , x_{n}\right)$ отличная от константы является монотонной тогда и только тогда, когда её сокращённая ДНФ не содержит отрицаний.

Определить, что будет замыканием множества $\left\{ \wedge , \vee \right\}$.

Доказать, что количество монотонных булевых функций вида $f\left(x_{1}, \ldots , x_{n}\right)$ на один больше количества подмножеств $V$ множества $\mathrm{P}\left\{ x_{1}, \ldots , x_{n}\right\}$, составленных из попарно не сравнимых с помощью $\subseteq$ множеств.

Доказать, что двойственной к линейной (монотонной) функции снова будет линейная (соответственно, монотонная) функция. Определить, как ведёт себя двойственная функция $f^{*}$, если $f$ сохраняет ноль или единицу (см. задачу 71 на стр. 100).

Определить количество функций из $\mathcal{P}_{n}$, принадлежащих каждому из множеств $\mathcal{S}_{0}, \mathcal{S}_{1}, \mathcal{S}$ и $\mathcal{L}$.

Найти количество булевых функций от $n$ переменных, являющихся одновременно самодвойственными и линейными.

Найти количество булевых функций от $n$ переменных, являющихся одновременно монотонными и линейными.

Доказать, что в множестве $\mathcal{P}_{n}$ имеется не меньше $2^{C_{n}^{\lfloor n / 2\rfloor }}$ монотонных функций.

Доказать, что если $f\left(x_{1}, \ldots , x_{n}\right)$ — линейная функция, отличная от константы, то количество единиц в таблице истинности равно $2^{n-1}$. Верно ли обратное?

Найти все трёхместные булевы функции $f$, которые в одиночку образуют полное множество $\left\{ f\right\}$. Найти их количество.