Question

Show that if \({\bf{F}}\) and \({\bf{G}}\) are Boolean functions represented by Boolean expressions in \({\bf{n}}\) variables and \({\bf{F = G}}\), then \({{\bf{F}}^{\bf{d}}}{\bf{ = }}{{\bf{G}}^{\bf{d}}}\), where \({{\bf{F}}^{\bf{d}}}\) and \({{\bf{G}}^{\bf{d}}}\) are the Boolean functions represented by the duals of the Boolean expressions representing \({\bf{F}}\) and \({\bf{G}}\), respectively. (Hint: Use the result of Exercise \(29\).)

Short answer

The given \({F^d} = {G^d}\) is proved.

Step-by-step solution

Definition

The complement of an element: \(\bar 0 = 1\) and \(\bar 1 = 0\)

The Boolean sum \( + \) or \(O{\bf{ }}R\) is \(1\) if either term is \(1\) .

The Boolean product or \(A{\bf{ }}N{\bf{ }}D\) is \(1\) if both terms are \(1\) .

The dual of a Boolean expression interchanges the Boolean sum and the Boolean product, and interchanges\({\bf{0}}\)and\({\bf{1}}\).

De Morgan's laws

\(\begin{array}{c}\overline {\left( {xy} \right)} = \bar x + \bar y\\\overline {\left( {x + y} \right)} = \bar x\bar y\end{array}\)

Using the De Morgan’s law

Given:\(F\) and \(G\)are Boolean functions with \(n\) variables each\(F = G\)

To proof: \({F^d} = {G^d}\)

By the previous exercise:

\({F_d}\left( {{x_1},{x_2}, \ldots ,{x_n}} \right){\bf{ }} = \overline {F\left( {{{\bar x}_1},{{\bar x}_2}, \ldots ,{{\bar x}_n}} \right)} \)

\({G_d}\left( {{x_1},{x_2}, \ldots ,{x_n}} \right){\bf{ }} = \overline {G\left( {{{\bar x}_1},{{\bar x}_2}, \ldots ,{{\bar x}_n}} \right)} \)

Since \({F^d} = G\) :\(F\left( {{{\bar x}_1},{{\bar x}_2}, \ldots ,{{\bar x}_n}} \right) = G\left( {{{\bar x}_1},{{\bar x}_2}, \ldots ,{{\bar x}_n}} \right)\).

However, if two values are equal, then their complements are also equal:\(\overline {F\left( {{{\bar x}_1},{{\bar x}_2}, \ldots ,{{\bar x}_n}} \right)} = \overline {G\left( {{{\bar x}_1},{{\bar x}_2}, \ldots ,{{\bar x}_n}} \right)} \)

Therefore, you can obtain:\({F_d}\left( {{x_1},{x_2}, \ldots ,{x_n}} \right) = {G_d}\left( {{x_1},{x_2}, \ldots ,{x_n}} \right)\) by the result of the previous exercise.