Question

Give an example of a self-dual Boolean function of three variables.

Short answer

The first example \({\bf{F(x,y,z) = x}}\) is self-dual.

The second example \({\bf{F(x,y,z) = xy + \bar xy}}\) is self-dual.

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

A Boolean function is self-dual iff \({\bf{F}}\left( {{{\bf{x}}_{\bf{1}}}{\bf{,}}{{\bf{x}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right){\bf{ = }}\overline {{\bf{F}}\left( {{{{\bf{\bar x}}}_{\bf{1}}}{\bf{,}}{{{\bf{\bar x}}}_{\bf{2}}}{\bf{, \ldots ,}}{{{\bf{\bar x}}}_{\bf{n}}}} \right)} \)

Law of the double complement \({\bf{\bar x = x}}\)

Identity laws

\(\begin{array}{c}{\bf{x + 0 = x }}\\{\bf{x \times 1 = x}}\end{array}\)

Idempotent laws

\(\begin{array}{l}{\bf{x + x = x}}\\{\bf{x}} \bullet {\bf{x = x}}\end{array}\)

Commutative laws:

\(\begin{array}{l}{\bf{p}} \vee {\bf{q}} \equiv {\bf{q}} \vee {\bf{p}}\\{\bf{p}} \wedge {\bf{q}} \equiv {\bf{q}} \wedge {\bf{p}}\end{array}\)

De Morgan's laws

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

Zero property

\({\bf{x\bar x = 0}}\)

Unit property

\({\bf{x + \bar x = 1}}\)

Using the law of double complement

Two possible self-dual Boolean function of three variables is

\({\bf{F(x,y,z) = xF(x,y,z) = xy + \bar xy}}\)

First example,

\(\begin{aligned} F(x,y,z) = x \\ \overline {F(\bar x,\bar y,\bar z)} {\mathbf{ }} = \bar x \\ = x \\ = F(x,y,z) \\ \end{aligned} \)

They are the two self-dual functions.

Hence, by the definition of self-dual, \({\bf{F}}\) is self-dual.

Using the law of double complement, De Morgan’s, Distributive, Idempotent, Commutative, Identity and the property of zero, unit

Second example,

\({\bf{F(x,y,z) = xy + \bar xy}}\)

\(\begin{aligned}\overline {F(\bar x,\bar y,\bar z)} {\text{ }} &= \overline {\bar x \bar y + \bar x \bar y} \\ &= \overline {\bar x \bar y + x \bar y} \\ & = \bar x \bar y\overline {x \bar y} \\ &= (\bar x + \bar y)(\bar x + \bar y) \\ &= (x + y)(\bar x + y) \\ &= x \bar x + \bar xy + xy + yy \\ & = 0 + \bar xy + xy + yy \\ & = \bar xy + xy + y \\ \end{aligned} \)

Using the law of double complement, De Morgan’s, Distributive, Idempotent, Commutative, Identity and the property of zero, unit

Using the law of commutative and distributive

\(\begin{aligned}\overline {F(\bar x,\bar y,\bar z)} {\mathbf{ }} &= (\bar x + x)y + y \\ &= (x + \bar x)y + y \\ &= 1 \times y + y \\ &= y + y \\ &= y \\ &= 1 \bullet y \\ &= (x + \bar x) \bullet y \\ &= xy + \bar xy \\ &= F(x,y,z) \\ \end{aligned} \)

Therefore, by the definition of self-dual, \({\bf{F}}\) is self-dual.