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

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

Определить, какие из следующих формул задают монотонные функции:

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

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

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

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

Какие функции следует удалить из множества $F=\left\{ f, g, h\right\}$, чтобы оно стало базисом?

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

Найти все базисы, составленные из функций на рис. 5. Для каждого из них выразить с помощью функций базиса обе константы, отрицание $\neg$ и импликацию →.

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

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

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

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

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

Найти замыкание множества $\left\{ \wedge , \oplus \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}$ не зависит).

Доказать, что замыканием множества $\left\{ \leftrightarrow \right\}$ является $\mathcal{S}_{1} \cap \mathcal{L}$.

Доказать, что для монотонных функций $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)$ отличная от константы является монотонной тогда и только тогда, когда её сокращённая ДНФ не содержит отрицаний.

Построить все монотонные функции вида $f(x, y, z)$.

Определить, что будет замыканием множества $\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^{*}=f$ (см. задачу 151 на стр. 49).

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

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

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

для некоторой $(n-1)$-местной булевой функции $g$.

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

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

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

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

Сколько имеется монотонных булевых функций от $n$ переменных, у которых значения зависят лишь от количества единиц в наборе аргументов?

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

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

Доказать, что если функция $f$ построена только с помощью дизъюнкции и импликации, то количество единиц в таблице истинности не меньше половины. Верно ли обратное?

Доказать, что в условии задачи 205 на стр. 63 конъюнкцию удалить нельзя.

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

Доказать, что если двухместная булева функция сохраняет ноль и единицу, то она является монотонной. Показать, что уже для трёхместных функций это неверно.

Доказать, что если двухместная булева функция самодвойственна, то она линейна. Показать, что уже для трёхместных функций это неверно.

Доказать, что если базис не содержит функций местности более двух, то он содержит не более трёх функций. Привести пример, который показывает, что число три уменьшить нельзя.

Доказать, что если базис не содержит нульместных функций и ни одна из функций не имеет фиктивных аргументов, то он содержит не более трёх функций. Привести пример, который показывает, что число три уменьшить нельзя.