Counting functions on the Boolean cube

[5/100%]
Show
LaTeX

Which subsets of the vertices of B4\mathbb {B}^{4} correspond to the following Boolean functions:

?
(a)

f1(x1,x2,x3,x4)=1⇔x1=0f_{1}\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=1 \Leftrightarrow x_{1}=0;

(b)

f2(x1,x2,x3,x4)=1⇔x4=1f_{2}\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=1 \Leftrightarrow x_{4}=1;

(c)

f3(x1,x2,x3,x4)=1⇔x1+x2⩾x3+x4f_{3}\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=1 \Leftrightarrow x_{1}+x_{2} \geqslant x_{3}+x_{4};

(d)

f4(x1,x2,x3,x4)=1⇔x1x2=0f_{4}\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=1 \Leftrightarrow x_{1} x_{2}=0 or x3x4=1x_{3} x_{4}=1?

Call the tuples α=(α1,…,αn)∈Bn\alpha =\left(\alpha_{1}, \ldots , \alpha_{n}\right) \in \mathbb {B}^{n} and β=(β1,…,βn)∈Bn\beta =\left(\beta_{1}, \ldots , \beta_{n}\right) \in \mathbb {B}^{n} neighboring if they occur in adjacent rows of the table for a function of nn variables, that is, they represent the binary expansions of numbers iαi_{\alpha } and iβi_{\beta } for which ∣iα−iβ∣=1\left|i_{\alpha }-i_{\beta }\right|=1.

Find the number of functions in Pn\mathcal{P}_{n} that take, on every pair of neighboring tuples,

?
(a)

equal values;

(b)

different values.

Call the tuples α=(α1,…,αn)∈Bn\alpha =\left(\alpha_{1}, \ldots , \alpha_{n}\right) \in \mathbb {B}^{n} and β=(β1,…,βn)∈Bn\beta =\left(\beta_{1}, \ldots , \beta_{n}\right) \in \mathbb {B}^{n} opposite if αi+βi=1\alpha_{i}+\beta_{i}=1 for every ii (in other words, αi=1\alpha_{i}=1 if and only if βi=0\beta_{i}=0).

Find the number of functions in Pn\mathcal{P}_{n} that take different values on every pair of opposite tuples.

?

Let n=2kn=2 k. Call a tuple α=(α1,…,αn)∈Bn\alpha =\left(\alpha_{1}, \ldots , \alpha_{n}\right) \in \mathbb {B}^{n} paired if αi=αk+i\alpha_{i}=\alpha_{k+i} for all i=1,…,ki=1, \ldots , k, that is α=α′α′\alpha =\alpha^{\prime } \alpha^{\prime } for some tuple α′\alpha^{\prime } of size kk. Find the number of functions in Pn\mathcal{P}_{n} that take the same value on all paired tuples.

?

Which subsets of the vertices of B4\mathbb {B}^{4} correspond to the following Boolean functions:

?
(a)

f1(x1,x2,x3,x4)=1⇔x1=0f_{1}\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=1 \Leftrightarrow x_{1}=0;

(b)

f2(x1,x2,x3,x4)=1⇔x4=1f_{2}\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=1 \Leftrightarrow x_{4}=1;

(c)

f3(x1,x2,x3,x4)=1⇔x1+x2⩾x3+x4f_{3}\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=1 \Leftrightarrow x_{1}+x_{2} \geqslant x_{3}+x_{4};

(d)

f4(x1,x2,x3,x4)=1⇔x1x2=0f_{4}\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=1 \Leftrightarrow x_{1} x_{2}=0 or x3x4=1x_{3} x_{4}=1?

References

[ДДК+21a] Дехтярь М.И., Дудаков С.М., Карлов М.И., Карлов Б.Н. Лекции по дискретной математике. 3-е изд., Тверской государственный университет, 2021.
[ДДК+21b] Дехтярь М.И., Дудаков С.М., Карлов Б.Н., Карлов М.И. Задачник по дискретной математике. 2-е изд., Тверской государственный университет, 2021.