Duality of Boolean functions
[8/100%]A Boolean function is called dual to the function if for every assignment of values to the variables. For example, conjunction is dual to disjunction and vice versa.
Prove that the duality relation is symmetric.
Let be Boolean functions and
Establish the following duality principle: the dual function of a superposition of functions equals the superposition of the dual functions:
A Boolean function is called dual to a function if for every tuple of values of the variables. For example, conjunction is dual to disjunction and vice versa.
Prove that the duality relation is symmetric.
Let be Boolean functions and
Establish the following duality principle: the dual function of a superposition of functions equals the superposition of the dual functions:
Construct the dual functions for the functions
,
→,
,
↑.
Construct the dual functions for the functions given by the following formulas:
;
;
.
Prove that a Boolean function is self-dual if and only if (see problem 151 on p. 49).
Prove that an -ary Boolean function is self-dual if and only if
for some -ary Boolean function .
Let be a formula with tight negations (see Problem II.1.22), and let be obtained from by replacing by , by , and the variables by . Prove that .
Let and be formulas with tight negations (see Problem II.1.22), and let , be the formulas dual to and respectively ( is obtained from by replacing by , by ). Prove that implies (the duality law).