Lesson 1

Basic Problems.

1. (10 points) Give an example of a function \(f \in B_{n}\) such that every CNF representation of \(f\) contains a clause of length \(n\).
   Hint:

   Consider a function that is false for only one possible input combination. What would the clauses in its CNF need to look like to ensure this property?
2. (10 points) Let \(f \in B_{5}\) and \(|f^{-1}(1)|=17\). Is \(\{f, \neg\}\) a complete basis?
3. (15 points) Give an example of a function \(f \in B_{n}\) such that every CNF representation of \(f\) has at least \(2^{n-1}\) clauses.
4. (15 points) Prove that for any function \(f \in B_{n}\), there exists a CNF with no more than \(2^{n-1}\) clauses.
5. (15 points) Let \(g_{1}, g_{2} \in B_{n} \cap \mathcal{L}\) be linear functions of \(n\) variables, and let \(f \in B_{2n}\) be defined as \[f(x_{1}, \dotsc, x_{2n}) = g_{1}(x_{1}, \dotsc, x_{n})g_{2}(x_{n+1}, \dotsc, x_{2n})\ .\] For which \(g_{1}, g_{2}\) is the set \(\{\neg, f\}\) a complete basis?
6. (15 points) A function \(f \in B_{n}\) is called symmetric if, for any permutation \(\sigma \in S_{n}\), \[f(x_{1}, \dotsc, x_{n}) = f(x_{\sigma_1}, \dotsc, x_{\sigma_n}).\] Show that any Boolean function \(f\) of three variables can be obtained from a symmetric function of seven variables: there exists a symmetric function \(g \colon \{0,1\}^{7} \to \{0,1\}\) such that \[f(x_{1}, x_{2}, x_{3}) \equiv g(y_{1}, \dotsc, y_{7}),\] where each \(y_{i}\) is one of \(x_{1}\), \(x_{2}\), or \(x_{3}\).
7. (15 points) Two formulas containing only variables and the connectives \(\land\), \(\lor\), and \(\neg\) are equivalent. Prove that they remain equivalent if every occurrence of \(\lor\) is replaced by \(\land\), and vice versa.
8. (15 points) Prove that the set \(\{\operatorname{MAJ}_{3}\}\) is a basis for the class \(\mathcal{M}\cap \mathcal{D}\) of monotone self-dual functions.
   Hint:

   Denote \(\bar{x}= (x_{4}, \dotsc, x_{n})\). Let \(f \colon \{0, 1\}^{n}\to \{0, 1\}\), and define the following functions: \[\begin{align*}f_{1}(x, y, \bar{x})&= f(x, y, y, \bar{x}), \\ f_{2}(x, y, \bar{x})&= f(y, x, y, \bar{x}), \\ f_{3}(x, y, \bar{x})&= f(y, y, x, \bar{x}).\end{align*}\] How can one express \(f\) in terms of \(f_{1}\), \(f_{2}\), and \(f_{3}\)?