Complete Sets of Functions and Post's Theorem

Prove the completeness of the set $\left\{ \downarrow \right\}$, containing only the Peirce arrow, by directly expressing negation, disjunction, and conjunction through it.

Determine the membership of each of the functions presented in the table in fig. 11 on p. 107 in each of the sets $\mathcal{S}_{0}, \mathcal{S}_{1}, \mathcal{S}, \mathcal{L}$, and $\mathcal{M}$.

Using the results of problem 86, determine which of the triples of functions presented in fig. 11 on p. 107 are complete sets. Are there complete sets of two functions among them? Of one function? Which of them are bases?

Find all bases that can be obtained by removing functions from the set $\left\{ 0,1, \wedge , \vee , \rightarrow \right\}$.

Check the completeness of the set of functions $\left\{ g, h\right\}$ presented in the table in fig. 12 on p. 113. If it is complete, express both constants, negation $\neg$, and implication $\rightarrow$ using these functions.

Express the functions $0,1, \vee , \wedge , \leftrightarrow$ using formulas built from functions of the complete set $\left\{ \neg , \rightarrow \right\}$.

Determine how, given a DNF (CNF), to determine whether it preserves zero or one, without computing its values.

Prove that the closure of the set $\left\{ \wedge , \vee , \rightarrow \right\}$ is $\mathcal{S}_{1}$. Can the same be claimed for the set $\left\{ \wedge , \rightarrow \right\}$?

Call a function $f\left(x_{1}, \ldots , x_{n}\right)$ linear in the variable $x_{i}$ if $f$ can be represented as $f\left(x_{1}, \ldots , x_{n}\right)=g\left(x_{1}, \ldots , x_{n}\right) \oplus \alpha_{i} x_{i}$, where $g\left(x_{1}, \ldots , x_{n}\right)$ is some function not depending on $x_{i}, \alpha_{i} \in \left\{ 0,1\right\}$. Prove that a Boolean function $f\left(x_{1}, \ldots , x_{n}\right)$ is linear if and only if it is linear in every variable.

Prove that a function $f\left(x_{1}, \ldots , x_{n}\right)$ is linear in the variable $x_{i}$ if and only if, when the value of the variable $x_{i}$ changes, the value of the function either always changes (that is, for all values of the remaining variables) or never changes (that is, $f$ does not depend on $x_{i}$).

Prove that for monotone functions $f^{(n)} \in \mathcal{M}$ the representation

holds for all $i=1, \ldots , n$. Deduce from this (by induction on $n$) that for every monotone function other than a constant, there exist a DNF and a CNF defining it that contain no negations of variables.

Prove that a Boolean function $f^{(n)}$ is monotone if and only if it is monotone in each argument: for all $i=1, \ldots , n$ and all $\sigma_{1}, \ldots , \sigma_{n} \in \mathbb {B}$ the inequality

Prove that a Boolean function $f\left(x_{1}, \ldots , x_{n}\right)$ other than a constant is monotone if and only if its abridged DNF contains no negations.

Determine what the closure of the set $\left\{ \wedge , \vee \right\}$ is.

Prove that the number of monotone Boolean functions of the form $f\left(x_{1}, \ldots , x_{n}\right)$ is one greater than the number of subsets $V$ of the set $\mathrm{P}\left\{ x_{1}, \ldots , x_{n}\right\}$ consisting of pairwise incomparable sets with respect to $\subseteq$.

Prove that the dual of a linear (monotone) function is again a linear (respectively, monotone) function. Determine how the dual function $f^{*}$ behaves if $f$ preserves zero or one (see problem 71 on p. 100).

Determine the number of functions in $\mathcal{P}_{n}$ belonging to each of the sets $\mathcal{S}_{0}, \mathcal{S}_{1}, \mathcal{S}$, and $\mathcal{L}$.

Find the number of Boolean functions of $n$ variables that are simultaneously self-dual and linear.

Find the number of Boolean functions of $n$ variables that are simultaneously monotone and linear.

Prove that the set $\mathcal{P}_{n}$ contains at least $2^{C_{n}^{\lfloor n / 2\rfloor }}$ monotone functions.

Prove that if $f\left(x_{1}, \ldots , x_{n}\right)$ is a linear function other than a constant, then the number of ones in the truth table equals $2^{n-1}$. Is the converse true?

Find all three-place Boolean functions $f$ that on their own form a complete set $\left\{ f\right\}$. Find their number.