Question

Show that \(\left\{ \downarrow \right\}\) is functionally complete using Exercise 15.

Short answer

Therefore, shows that \(\left\{ \downarrow \right\}\) is functionally complete using Exercise 15

Step-by-step solution

Definition

The complements of an elements \(\overline {\bf{0}} {\bf{ = 1}}\) and \(\overline {\bf{1}} {\bf{ = 0}}\).

The Boolean sum + or OR is 1 if either term is 1.

The Boolean product (.) or AND is 1 if both terms are 1.

The NAND operator | is 1 if either term is 0.

The NOR operator\( \downarrow \)is 1 if both terms are 0.

Show that\(\left\{   \downarrow  \right\}\) is functionally complete. 

Every Boolean function can be represented using the operation \(\left( {{\bf{. , + , - }}} \right)\), which implies that the set \(\left\{ {{\bf{. , + , - }}} \right\}\) is functionally complete.

From the exercise 15.

(a) \(\overline {\bf{x}} {\bf{ = x}} \downarrow {\bf{x}}\)

(b) \({\bf{xy = (x}} \downarrow {\bf{x)}} \downarrow {\bf{(y}} \downarrow {\bf{y)}}\)

(c) \({\bf{x + y = (x}} \downarrow {\bf{y)}} \downarrow {\bf{(x}} \downarrow {\bf{y)}}\)

Thus,it can write any expression including a complement, Boolean product and a Boolean sum using the NOR operator\( \downarrow \). Since \(\left\{ {{\bf{. , + , - }}} \right\}\) is functionally complete,\(\left\{ \downarrow \right\}\) is also functionally complete.

Therefore, it shows that \(\left\{ \downarrow \right\}\) is functionally complete using Exercise 15.