Question

Draw the Hasse diagram for the poset consisting of the set of the \({\bf{16}}\)Boolean functions of degree two (shown in Table \({\bf{3}}\) of Section \({\bf{12}}{\bf{.1}}\)) with the partial ordering \( \le \).

Short answer

It needs to connect two functions \({{\bf{F}}_{\bf{i}}}\) and \({{\bf{F}}_{\bf{j}}}\) by an edge, if the two functions differ in exactly one value.

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 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}}\).

Table of values

The \({\bf{1}}6\) Boolean Functions of degree \({\bf{2}}\) (given in the table mentioned in the exercise prompt)

\(\begin{array}{*{20}{r}}{\bf{x}}&{{\bf{ y}}}&{{\bf{ }}{{\bf{F}}_{\bf{1}}}}&{{\bf{ }}{{\bf{F}}_{\bf{2}}}}&{{\bf{ }}{{\bf{F}}_{\bf{3}}}}&{{\bf{ }}{{\bf{F}}_{\bf{4}}}}&{{\bf{ }}{{\bf{F}}_{\bf{5}}}}&{{\bf{ }}{{\bf{F}}_{\bf{6}}}}&{{\bf{ }}{{\bf{F}}_{\bf{7}}}}&{{\bf{ }}{{\bf{F}}_{\bf{8}}}}\\{\bf{1}}&{\bf{1}}&{\bf{1}}&{\bf{1}}&{\bf{1}}&{\bf{1}}&{\bf{1}}&{\bf{1}}&{\bf{1}}&{\bf{1}}\\{\bf{1}}&{\bf{0}}&{\bf{1}}&{\bf{1}}&{\bf{1}}&{\bf{1}}&{\bf{0}}&{\bf{0}}&{\bf{0}}&{\bf{0}}\\{\bf{0}}&{\bf{1}}&{\bf{1}}&{\bf{1}}&{\bf{0}}&{\bf{0}}&{\bf{1}}&{\bf{1}}&{\bf{0}}&{\bf{0}}\\{\bf{0}}&{\bf{0}}&{\bf{1}}&{\bf{0}}&{\bf{1}}&{\bf{0}}&{\bf{1}}&{\bf{0}}&{\bf{1}}&{\bf{0}}\end{array}\)

Further, continue the above table,

\(\begin{array}{*{20}{r}}{\bf{x}}&{{\bf{ y}}}&{{\bf{ }}{{\bf{F}}_{\bf{9}}}}&{{\bf{ }}{{\bf{F}}_{{\bf{10}}}}}&{{\bf{ }}{{\bf{F}}_{{\bf{11}}}}}&{{\bf{ }}{{\bf{F}}_{{\bf{12}}}}}&{{\bf{ }}{{\bf{F}}_{{\bf{13}}}}}&{{\bf{ }}{{\bf{F}}_{{\bf{14}}}}}&{{\bf{ }}{{\bf{F}}_{{\bf{15}}}}}&{{\bf{ }}{{\bf{F}}_{{\bf{16}}}}}\\{\bf{0}}&{\bf{0}}&{\bf{0}}&{\bf{0}}&{\bf{0}}&{\bf{0}}&{\bf{0}}&{\bf{0}}&{\bf{0}}&{\bf{0}}\\{\bf{1}}&{\bf{0}}&{\bf{1}}&{\bf{1}}&{\bf{1}}&{\bf{1}}&{\bf{0}}&{\bf{0}}&{\bf{0}}&{\bf{0}}\\{\bf{0}}&{\bf{1}}&{\bf{1}}&{\bf{1}}&{\bf{0}}&{\bf{0}}&{\bf{1}}&{\bf{1}}&{\bf{0}}&{\bf{0}}\\{\bf{0}}&{\bf{0}}&{\bf{1}}&{\bf{0}}&{\bf{1}}&{\bf{0}}&{\bf{1}}&{\bf{0}}&{\bf{1}}&{\bf{0}}\end{array}\)

Hasse diagram

Here \({{\bf{F}}_{\bf{1}}}\) is the smallest function (based on the definition of \({\bf{F}} \le {\bf{G}}\) ), because \({{\bf{F}}_{\bf{1}}}\) contains a \({\bf{1}}\) for all possible values.

Next should be the functions \({{\bf{F}}_{\bf{2}}}{\bf{,}}{{\bf{F}}_{\bf{3}}}{\bf{,}}{{\bf{F}}_{\bf{5}}}{\bf{,}}{{\bf{F}}_{\bf{9}}}\) as these functions contain \({\bf{3}}\) ones for the \({\bf{4}}\) possible values, since \({{\bf{F}}_{\bf{1}}} \le {{\bf{F}}_{\bf{2}}}{\bf{, }}{{\bf{F}}_{\bf{1}}} \le {{\bf{F}}_{\bf{3}}}{\bf{,}}{{\bf{F}}_{\bf{1}}} \le {{\bf{F}}_{\bf{5}}}{\bf{,}}{{\bf{F}}_{\bf{1}}} \le {{\bf{F}}_{\bf{9}}}\) (and all other functions are larger than at least one of the functions \({{\bf{F}}_{\bf{2}}}{\bf{,}}{{\bf{F}}_{\bf{3}}}{\bf{,}}{{\bf{F}}_{\bf{5}}}{\bf{,}}{{\bf{F}}_{\bf{9}}}\) ).

Hence, it needs to connect two functions \({{\bf{F}}_{\bf{i}}}\) and \({{\bf{F}}_{\bf{j}}}\) by an edge, if the two functions differ in exactly one value.