Question

Give a recursive definition of the set of Boolean expressions.

Short answer

Here \({\bf{0}}\)and \({\bf{1}}\) are Boolean expressions.

The variables \({{\bf{x}}_{\bf{1}}}{\bf{,}}{{\bf{x}}_{\bf{2}}}{\bf{,}}{{\bf{x}}_{\bf{3}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}\) are a Boolean expression each.

If \({{\bf{E}}_{\bf{1}}}\) and \({{\bf{E}}_{\bf{2}}}\) are Boolean expressions, then the complement \({{\bf{\bar E}}_{\bf{1}}}\), the Boolean sum \({{\bf{E}}_{\bf{1}}}{\bf{ + }}{{\bf{E}}_{\bf{2}}}\) and the Boolean product \({{\bf{E}}_{\bf{1}}}{{\bf{E}}_2}\) also form Boolean expressions.

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

Using the Boolean sum and product

A Boolean expression in \({{\bf{x}}_{\bf{1}}}{\bf{,}}{{\bf{x}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}\) can be either a constant \({\bf{(0,1)}}\) or a single variable, or a Boolean expression is the complement, Boolean sum of Boolean product of two Boolean expressions. \({\bf{0}}\) and \({\bf{1}}\) are Boolean expressions. The variables \({{\bf{x}}_{\bf{1}}}{\bf{,}}{{\bf{x}}_{\bf{2}}}{\bf{,}}{{\bf{x}}_{\bf{3}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}\) are a Boolean expression each.

Hence, if \({{\bf{E}}_{\bf{1}}}\) and \({{\bf{E}}_{\bf{2}}}\) are Boolean expressions, then the complement \({{\bf{\bar E}}_{\bf{1}}}\), the Boolean sum \({{\bf{E}}_{\bf{1}}}{\bf{ + }}{{\bf{E}}_{\bf{2}}}\) and the Boolean product \({{\bf{E}}_{\bf{1}}}{{\bf{E}}_2}\) also form Boolean expressions.