Question

Show that if \(F\) and \(G\) are Boolean functions of degree \(n\), then

\(\begin{array}{l}a)F \le F{\bf{ + }}G\\b)FG \le F\end{array}\)

Short answer

\(a)\)It gets \(F \le F{\bf{ + }}G\) by the definition of Boolean functions.

\(b)\) It gets \(FG \le F\) by the definition of Boolean functions.

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 Boolean function

(a)

At every point in the domain, it is certainly the case that if \({\bf{F}}\left( {{{\bf{x}}_{\bf{1}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right){\bf{ = 1}}\), then \({\bf{(F + G)}}\left( {{{\bf{x}}_{\bf{1}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right){\bf{ = F}}\left( {{{\bf{x}}_{\bf{1}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right){\bf{ + G}}\left( {{{\bf{x}}_{\bf{1}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right){\bf{ = 1 + G}}\left( {{{\bf{x}}_{\bf{1}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right){\bf{ = 1}}\), no matter what value \(G\) has at that point.

Therefore, by definition \(F \le F{\bf{ + }}G\).

Using contrapositive method

(b)

This is dual to the first part.

At every point in the domain, it is certainly the case that if \({\bf{F}}\left( {{{\bf{x}}_{\bf{1}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right){\bf{ = 0}}\), then \({\bf{(FG)}}\left( {{{\bf{x}}_{\bf{1}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right){\bf{ = F}}\left( {{{\bf{x}}_{\bf{1}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right){\bf{G}}\left( {{{\bf{x}}_{\bf{1}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right){\bf{ = 0}} \cdot {\bf{G}}\left( {{{\bf{x}}_{\bf{1}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right){\bf{ = 0}}\).

No matter what value \(G\) has at that point.

The contrapositive of this statement is that if \({\bf{(FG)}}\left( {{{\bf{x}}_{\bf{1}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right){\bf{ = 1}}\), then \({\bf{F}}\left( {{{\bf{x}}_{\bf{1}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right){\bf{ = 1}}\).

Therefore, by definition \(FG \le F\).