Math Problems Vault

Problem 193

(a)(b)(c)(d)

Determine which of the following formulas define self-dual functions:

?

(a)

$\Phi_{1}=x \vee (\neg y \wedge z) ;$

(b)

$\Phi_{2}=(\neg x \wedge y) \vee (z \wedge \neg (x \oplus y))$ ;

(c)

$\Phi_{3}=(x \wedge \neg z) \vee (y \wedge \neg z) \vee (x \wedge y)$ ;

(d)

$\Phi_{4}=(\neg x \rightarrow (y \vee z)) \rightarrow (\neg y \wedge z)$ .

Problem 194

(a)(b)(c)(d)

Determine which of the following formulas define monotone functions:

?

(a)

$\Phi_{1}=(y \rightarrow \neg x) \rightarrow (y \wedge z) ;$

(b)

$\Phi_{2}=(\neg (x \wedge y) \vee \neg z) \rightarrow (\neg x \rightarrow (y \wedge z))$ ;

(c)

$\Phi_{3}=(\neg x \rightarrow (y \wedge \neg z)) \rightarrow y$ ;

(d)

$\Phi_{4}=\neg z \rightarrow (y \wedge \neg x)$ .

Problem 195

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

?

Problem 196

Prove that the set $\left\{ \vee , \wedge , \rightarrow \right\}$ is not complete. Can it be made complete by adding some constant?

?

Problem 197

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

$x_{1}$	$x_{2}$	$x_{3}$	$f_{1}$	$f_{2}$	$f_{3}$	$f_{4}$	$f_{5}$	$f_{6}$	$f_{7}$
0	0	0	1	1	0	0	0	0	1
0	0	1	0	1	0	1	0	0	1
0	1	0	0	0	1	1	1	0	0
0	1	1	1	0	0	0	1	1	0
1	0	0	1	0	1	1	0	1	1
1	0	1	0	0	0	0	0	0	1
1	1	0	0	1	1	0	1	0	0
1	1	1	0	1	1	1	1	0	0
: Fig. 4: Functions from problem 197.

?

Problem 198

Using the results of problem 197, determine which of the triples of functions presented in fig. 4 on the next page are complete sets. Are there complete sets of two functions among them? Of one function? Which of them will be bases?

?

Problem 199

Which functions should be removed from the set $F=\left\{ f, g, h\right\}$ so that it becomes a basis?

f(x, y)=x \vee y ; \quad g(x, y)=x \rightarrow \neg y ; \quad h(x, y)=x \oplus y.

?

Problem 200

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

?

Problem 201

Find all bases composed of the functions in fig. 5. For each of them express both constants, negation $\neg$ , and implication → by means of the functions of the basis.

$x_{1}$	$x_{2}$	$x_{3}$	$f$	$g$	$h$
0	0	0	1	1	0
0	0	1	0	1	0
0	1	0	0	0	1
0	1	1	1	0	0
1	0	0	0	0	1
1	0	1	1	1	0
1	1	0	1	1	1
1	1	1	0	1	0
: Fig. 5: Functions $f, g, h$ .

?

Problem 202

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

?

Problem 203

Boolean functions are given by the sequence of their values under a lexicographic ordering of the arguments. Find all bases that can be composed from the following functions.

?

(a)

$f_{1}=(00111100)$ ;

(b)

$f_{2}=(10100101)$ ;

(c)

$f_{3}=(01101001)$ ;

(d)

$f_{4}=(10010110)$ ;

(e)

$f_{5}=(11101000)$ ;

(f)

$f_{6}=(01110001)$ ;

(g)

$f_{7}=(10011011)$ ;

(h)

$f_{8}=(11001000)$ ;

For each basis show how to construct the constants, negation, and conjunction (or disjunction) using its elements.

(i)

$f_{9}=(01010111)$ ;

(j)

$f_{10}=(00010101)$ .

Problem 204

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

?

Problem 205

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

?

Problem 206

Prove that the closure of each of the sets $\left\{ \leftrightarrow , \wedge \right\} ,\left\{ \leftrightarrow , \vee \right\}$ , $\left\{ \leftrightarrow , \rightarrow \right\}$ is $\mathcal{S}_{1}$ .

?

Problem 207

Find the closure of the set $\left\{ \wedge , \oplus \right\}$ .

?

Problem 208

Let us call a function $f\left(x_{1}, \ldots , x_{n}\right)$ linear in the variable $x_{i}$ if $f$ can be represented in the form $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}$ , and $\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 all the variables.

?

Problem 209

Prove that a function $f\left(x_{1}, \ldots , x_{n}\right)$ is linear in the variable $x_{i}$ if and only if, whenever 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}$ ).

?

Problem 210

Prove that the closure of the set $\left\{ \leftrightarrow \right\}$ is $\mathcal{S}_{1} \cap \mathcal{L}$ .

?

Problem 211

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

\begin{aligned} f\left(x_{1}, \ldots , x_{n}\right)=\left(x _{ i } \wedge f \left(x_{1}, \ldots , x_{i-1},\right.\right. & \left.\left.1, x_{i+1}, \ldots , x_{n}\right)\right) \vee \\ & \vee f\left(x_{1}, \ldots , x_{i-1}, 0, x_{i+1}, \ldots , x_{n}\right) \end{aligned}

for all $i=1, \ldots , n$ . From this deduce (by induction on $n$ ) that for every monotone function distinct from a constant there exist DNF and CNF representing it that contain no negations of variables.

?

Problem 212

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

f\left(\sigma _{1}, \ldots , \sigma _{i-1}, 0, \sigma _{i+1}, \ldots , \sigma _{n}\right) \leqslant f\left(\sigma _{1}, \ldots , \sigma _{i-1}, 1, \sigma _{i+1}, \ldots , \sigma _{n}\right).

holds.

?

Problem 213

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

?

Problem 214

Construct all monotone functions of the form $f(x, y, z)$ .

?

Problem 215

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

?

Problem 216

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\}$ made up of pairwise incomparable sets with respect to $\subseteq$ .

?

Problem 217

Prove that a Boolean function $f$ is self-dual if and only if $f^{*}=f$ (see problem 151 on p. 49).

?

Problem 218

Prove that a Boolean function $f\left(x_{1}, \ldots , x_{n}\right)$ is self-dual if and only if it satisfies the property from problem 166 on p. 54.

?

Problem 219

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 151 on p. 49).

?

Problem 220

Prove that an $n$ -ary Boolean function $f\left(x_{1}, \ldots , x_{n}\right)$ is self-dual if and only if

f\left(x_{1}, \ldots , x_{n}\right)=g\left(x_{1} \oplus x_{2}, \ldots , x_{1} \oplus x_{n}\right) \oplus x_{1}

for some $(n-1)$ -ary Boolean function $g$ .

?

Problem 221

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

?

Problem 222

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

?

Problem 223

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

?

Problem 224

Determine the number of functions from $\mathcal{P}_{n}$ belonging to each of the classes:

?

(a)

$\mathcal{S}_{0} \cap \mathcal{S}_{1}$ ;

(b)

$\mathcal{S}_{0} \cup \mathcal{S}_{1}$ ;

(c)

$\mathcal{S} \cap \mathcal{S}_{0}$ ;

(d)

$\mathcal{L} \cap \mathcal{S}_{0} ;$

(e)

$\mathcal{L} \cap \mathcal{S}_{1}$ ;

(f)

$\mathcal{S} \cap \mathcal{S}_{0} \cap \mathcal{S}_{1}$ ;

(g)

$\left(\mathcal{S} \backslash \mathcal{S}_{0}\right) \cap \mathcal{S}_{1}$ ;

(h)

$\mathcal{M} \backslash \mathcal{S}_{0}$ ;

(i)

$\mathcal{M} \backslash \mathcal{S}_{1}$ .

Problem 225

How many monotone Boolean functions of $n$ variables are there whose values depend only on the number of ones in the tuple of arguments?

?

Problem 226

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

?

Problem 227

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

?

Problem 228

Prove that if a function $f$ is built only using disjunction and implication, then the number of ones in the truth table is at least half. Is the converse true?

?

Problem 229

Prove that in the condition of problem 205 on p. 63 the conjunction cannot be removed.

?

Problem 230

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

?

Problem 231

Prove that if a two-place Boolean function preserves zero and one, then it is monotone. Show that this is already false for three-place functions.

?

Problem 232

Prove that if a two-place Boolean function is self-dual, then it is linear. Show that this is already false for three-place functions.

?

Problem 233

Prove that if a basis contains no functions of arity more than two, then it contains no more than three functions. Give an example showing that the number three cannot be decreased.

?

Problem 234

Prove that if a basis contains no zero-place functions and none of the functions has dummy arguments, then it contains no more than three functions. Give an example showing that the number three cannot be decreased.

?