Question

Show that the relation \( \le \) is a partial ordering on the set of Boolean functions of degree \(n\).

Short answer

It gets \( \le \) is a partial ordering on the set of Boolean function of degree \(n\).

Step-by-step solution

Definition

Let \({\bf{B = }}\left\{ {{\bf{0,1}}} \right\}\). Then \({{\bf{B}}^{\bf{n}}}{\bf{ = }}\left\{ {\left( {{{\bf{x}}_{\bf{1}}}{\bf{,}}{{\bf{x}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right)\mid {{\bf{x}}_{\bf{i}}} \in {\bf{B}}} \right.\)for \(\left. {1 \le {\bf{i}} \le {\bf{n}}} \right\}\) is the set of all possible \({\bf{n}}\)-tuples of \({\bf{0's}}\) and \({\bf{1's}}\). The variable \({\bf{x}}\) is called a Boolean variable if it assumes values only from \({\bf{B}}\), that is, if its only possible values are \(0\) and \(1\). A function from \({{\bf{B}}^{\bf{n}}}\) to \({\bf{B}}\) is called a Boolean function and it has degree \({\bf{n}}\).

Using the relation of reflexive

It needs to show that this relation is reflexive, antisymmetric, and transitive. That \({\bf{F}} \le F\) (reflexivity) is simply the tautology "if \(F\left( {{x_1}, \ldots ,{x_n}} \right) = 1\), then \(F\left( {{x_1}, \ldots ,{x_n}} \right) = 1\)." For antisymmetric, suppose that \(F \le G\) and \(G \le F\). Then the definition of the relation says that \(F\left( {{x_1}, \ldots ,{x_n}} \right) = 1\) if and only if \(G\left( {{x_1}, \ldots ,{x_n}} \right) = 1\), which is the definition of equality between functions, so \(F = G\).

Using the transitivity

Finally, for transitivity, suppose that \(F \le G\) and \(G \le H\). It wants to show that \(F \le H\). So, suppose that \(F\left( {{x_1}, \ldots ,{x_n}} \right) = 1\). Then by the first inequality \(G\left( {{x_1}, \ldots ,{x_n}} \right) = 1\), hence by the second inequality \(H\left( {{x_1}, \ldots ,{x_n}} \right) = 1\), as desired.

Therefore, it gets \( \le \) is a partial ordering on the set of Boolean function of degree \(n\).