Question

Determine whether \({\bf{F}} \le {\bf{G}}\) or \({\bf{G}} \le {\bf{F}}\) for the following pairs of functions.

\(\begin{array}{c}{\bf{a) F(x,y) = x,G(x,y) = x + y}}\\{\bf{b) F(x,y) = x + y,G(x,y) = xy}}\\{\bf{c) F(x,y) = \bar x,G(x,y) = x + y}}\end{array}\)

Short answer

\({\bf{(a)}}\) It gets \({\bf{F}} \le {\bf{G}}\) for the given function \({\bf{F(x,y) = x,G(x,y) = x + y}}\)

\({\bf{(b)}}\) It gets \({\bf{G}} \le {\bf{F}}\) for the given function \({\bf{F(x,y) = x + y,G(x,y) = xy}}\)

\({\bf{(c)}}\) \({\bf{F}} \le {\bf{G}}\) and \({\bf{G}} \le {\bf{F}}\) are both not the case for the given function \({\bf{F(x,y) = \bar x,G(x,y) = x + y}}\)

Step-by-step solution

Definition

The complement of an element: \({\bf{\bar 0 = 1}}\) and \({\bf{\bar 1 = 0}}\).

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

The Boolean product \( \bullet \) or \({\bf{AND}}\) is \({\bf{1}}\) if both terms are \({\bf{1}}\).

\({\bf{F}} \le {\bf{G}}\) if \({\bf{G}}\left( {{{\bf{x}}_{\bf{1}}}{\bf{,}}{{\bf{x}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right){\bf{ = 1}}\) whenever \({\bf{F}}\left( {{{\bf{x}}_{\bf{1}}}{\bf{,}}{{\bf{x}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right){\bf{ = 1}}\).

Check whether the given satisfies \({\bf{F}} \le {\bf{G}}\) or \({\bf{G}} \le {\bf{F}}\)

(a)

\(\begin{array}{*{20}{l}}{{\bf{F}}\left( {{\bf{x, y}}} \right){\bf{ = x}}}\\{{\bf{G}}\left( {{\bf{x, y}}} \right){\bf{ = x + y}}}\end{array}\)

Let create a table for all possible values of \({\bf{x, y}}\) and \({\bf{z}}\).

\(\begin{array}{*{20}{c}}{\bf{x}}&{{\bf{ y}}}&{{\bf{ F(x,y) = x}}}&{{\bf{ G(x,y) = x + y}}}\\{\bf{0}}&{\bf{0}}&{\bf{0}}&{\bf{0}}\\{\bf{0}}&{\bf{1}}&{\bf{0}}&{\bf{1}}\\{\bf{1}}&{\bf{0}}&{\bf{1}}&{\bf{1}}\\{\bf{1}}&{\bf{1}}&{\bf{1}}&{\bf{1}}\end{array}\)

Now note that \({\bf{G}}\left( {{\bf{x, y}}} \right){\bf{ = 1}}\) whenever \({\bf{F}}\left( {{\bf{x, y}}} \right){\bf{ = 1}}\) in the table.

Therefore, it gives \({\bf{F}} \le {\bf{G}}\).

Check whether the given satisfies \({\bf{F}} \le {\bf{G}}\) or \({\bf{G}} \le {\bf{F}}\)

(b)

\(\begin{array}{*{20}{l}}{{\bf{F}}\left( {{\bf{x, y}}} \right){\bf{ = x + y }}}\\{{\bf{G}}\left( {{\bf{x, y}}} \right){\bf{ = x y}}}\end{array}\)

Let create a table for all possible values of \({\bf{x, y}}\) and \({\bf{z}}\).

\(\begin{array}{*{20}{r}}{\bf{x}}&{{\bf{ y}}}&{{\bf{ F(x,y) = x + y}}}&{{\bf{ G(x,y) = xy}}}\\{\bf{0}}&{\bf{0}}&{\bf{0}}&{\bf{0}}\\{\bf{0}}&{\bf{1}}&{\bf{1}}&{\bf{0}}\\{\bf{1}}&{\bf{0}}&{\bf{1}}&{\bf{0}}\\{\bf{1}}&{\bf{1}}&{\bf{1}}&{\bf{1}}\end{array}\)

Now note that \({\bf{F}}\left( {{\bf{x, y}}} \right){\bf{ = 1}}\) whenever \({\bf{G}}\left( {{\bf{x, y}}} \right){\bf{ = 1}}\) in the table.

Hence, it gives \({\bf{G}} \le {\bf{F}}\).

Check whether the given satisfies \({\bf{F}} \le {\bf{G}}\) or \({\bf{G}} \le {\bf{F}}\)

(c)

\(\begin{array}{c}{\bf{F(x,y) = \bar x }}\\{\bf{G(x,y) = x + y}}\end{array}\)

Let create a table for all possible values of \({\bf{x, y}}\) and \({\bf{z}}\).

\(\begin{array}{*{20}{c}}{\bf{x}}&{{\bf{ y}}}&{{\bf{ F(x,y) = \bar x}}}&{{\bf{ G(x,y) = x + y}}}\\{\bf{0}}&{\bf{0}}&{\bf{1}}&{\bf{0}}\\{\bf{0}}&{\bf{1}}&{\bf{1}}&{\bf{1}}\\{\bf{1}}&{\bf{0}}&{\bf{0}}&{\bf{1}}\\{\bf{1}}&{\bf{1}}&{\bf{0}}&{\bf{1}}\end{array}\)

Now note that \({\bf{F}}\left( {{\bf{x, y}}} \right){\bf{ = 1}}\) and \({\bf{G}}\left( {{\bf{x, y}}} \right){\bf{ = }}0\) for \(\left( {{\bf{x, y}}} \right){\bf{ = }}\left( {0{\bf{,}}0} \right)\), while \({\bf{F}}\left( {{\bf{x, y}}} \right){\bf{ = }}0\) and \({\bf{G}}\left( {{\bf{x, y}}} \right){\bf{ = 1}}\) for \(\left( {{\bf{x, y}}} \right){\bf{ = }}\left( {1{\bf{,}}0} \right)\).

So, \({\bf{F}} \le {\bf{G}}\) and \({\bf{G}} \le {\bf{F}}\) are both not the case.