Duality of Boolean functions

[8/100%]
Show
LaTeX

A Boolean function f∗(x1,…,xn)f^{*}\left(x_{1}, \ldots , x_{n}\right) is called dual to the function f(x1,…,xn)f\left(x_{1}, \ldots , x_{n}\right) if f∗(x1,…,xn)=¬f(¬x1,…,¬xn)f^{*}\left(x_{1}, \ldots , x_{n}\right)=\neg f\left(\neg x_{1}, \ldots , \neg x_{n}\right) for every assignment of values to the variables. For example, conjunction is dual to disjunction and vice versa.

?
(a)

Prove that the duality relation is symmetric.

(b)

Let f(y1,…,ym),g1(x1,…,xn),…,gm(x1,…,xn)f\left(y_{1}, \ldots , y_{m}\right), g_{1}\left(x_{1}, \ldots , x_{n}\right), \ldots , g_{m}\left(x_{1}, \ldots , x_{n}\right) be Boolean functions and

h(x1,…,xn)=f(g1(x1,…,xn),…,gm(x1,…,xn)). h\left(x_{1}, \ldots , x_{n}\right)=f\left(g_{1}\left(x_{1}, \ldots , x_{n}\right), \ldots , g_{m}\left(x_{1}, \ldots , x_{n}\right)\right).

Establish the following duality principle: the dual function of a superposition of functions equals the superposition of the dual functions:

h∗(x1,…,xn)=f∗(g1∗(x1,…,xn),…,gm∗(x1,…,xn)). h^{*}\left(x_{1}, \ldots , x_{n}\right)=f^{*}\left(g_{1}^{*}\left(x_{1}, \ldots , x_{n}\right), \ldots , g_{m}^{*}\left(x_{1}, \ldots , x_{n}\right)\right).

A Boolean function f∗(x1,…,xn)f^{*}\left(x_{1}, \ldots , x_{n}\right) is called dual to a function f(x1,…,xn)f\left(x_{1}, \ldots , x_{n}\right) if f∗(x1,…,xn)=¬f(¬x1,…,¬xn)f^{*}\left(x_{1}, \ldots , x_{n}\right)=\neg f\left(\neg x_{1}, \ldots , \neg x_{n}\right) for every tuple of values of the variables. For example, conjunction is dual to disjunction and vice versa.

?
(a)

Prove that the duality relation is symmetric.

(b)

Let f(y1,…,ym),g1(x1,…,xn),…,gm(x1,…,xn)f\left(y_{1}, \ldots , y_{m}\right), g_{1}\left(x_{1}, \ldots , x_{n}\right), \ldots , g_{m}\left(x_{1}, \ldots , x_{n}\right) be Boolean functions and

h(x1,…,xn)=f(g1(x1,…,xn),…,gm(x1,…,xn)). h\left(x_{1}, \ldots , x_{n}\right)=f\left(g_{1}\left(x_{1}, \ldots , x_{n}\right), \ldots , g_{m}\left(x_{1}, \ldots , x_{n}\right)\right).

Establish the following duality principle: the dual function of a superposition of functions equals the superposition of the dual functions:

h∗(x1,…,xn)=f∗(g1∗(x1,…,xn),…,gm∗(x1,…,xn)). h^{*}\left(x_{1}, \ldots , x_{n}\right)=f^{*}\left(g_{1}^{*}\left(x_{1}, \ldots , x_{n}\right), \ldots , g_{m}^{*}\left(x_{1}, \ldots , x_{n}\right)\right).

Construct the dual functions for the functions

?
(a)

¬\neg,

(b)

→,

(c)

⊕\oplus,

(d)

↑.

Construct the dual functions for the functions given by the following formulas:

?
(a)

(x→¬(¬y⊕x⊕z))(x \rightarrow \neg (\neg y \oplus x \oplus z));

(b)

((x↑y)⊕(¬x→z))((x \uparrow y) \oplus (\neg x \rightarrow z)); ⊛\circledast

(c)

((x∨¬y)→(¬x↓y))((x \vee \neg y) \rightarrow (\neg x \downarrow y)).

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

?

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

f(x1,…,xn)=g(x1⊕x2,…,x1⊕xn)⊕x1 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)(n-1)-ary Boolean function gg.

?

Let AA be a formula with tight negations (see Problem II.1.22), and let A1A_{1} be obtained from AA by replacing by ∨\vee, ∨\vee by , and the variables AiA_{i} by ¬Ai\neg A_{i}. Prove that A1∼¬AA_{1} \sim \neg A.

?

Let AA and BB be formulas with tight negations (see Problem II.1.22), and let A∗A^{*}, B∗B^{*} be the formulas dual to AA and BB respectively (A∗A^{*} is obtained from AA by replacing by ∨\vee, ∨\vee by ). Prove that A∼BA \sim B implies A∗∼B∗A^{*} \sim B^{*} (the duality law).

?

References

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