91Ó°ÊÓ

a) Show that \((1 \cdot 1)+(\overline{0 \cdot 1}+0)=1\) b) Translate the equation in part (a) into a propositional equivalence by changing each 0 into an \(\mathbf{F}\) , each 1 into a \(\mathbf{T}\) , each Boolean sum into a disjunction, each Boolean product into a conjunction, each complementation into a negation, and the equals sign into a propositional equivalence sign.

Construct circuits from inverters, AND gates, and OR gates to produce these outputs. $$ \begin{array}{ll}{\text { a) } \overline{x}+y} & {\text { b) } \overline{(x+y)} x} \\ {\text { c) } x y z+\overline{x} \overline{y} \overline{z}} & {\text { d) } \overline{(\overline{x}+z)(y+\overline{z})}}\end{array} $$

Draw the 4 -cube \(Q_{4}\) and label each vertex with the minterm in the Boolean variables \(w, x, y,\) and \(z\) associated with the bit string represented by this vertex. For each literal in these variables, indicate which 3 -cube \(Q_{3}\) that is a subgraph of \(Q_{4}\) represents this literal. Indicate which 2 -cube \(Q_{2}\) that is a subgraph of \(Q_{4}\) represents the products \(w z, \overline{x} y,\) and \(\overline{y} \overline{z}\)

Use a K-map to find a minimal expansion as a Boolean sum of Boolean products of each of these functions in the variables \(x, y,\) and \(z .\) a) \(\overline{x} y z+\overline{x} \overline{y} z\) b) \(x y z+x y \overline{z}+\overline{x} y z+\overline{x} y \overline{z}\) c) \(x y \overline{z}+x \overline{y} z+x \overline{y} \overline{z}+\overline{x} y z+\overline{x} \overline{y} z\) d) \(x y z+x \overline{y} z+x \overline{y} \overline{z}+\overline{x} y z+\overline{x} y z+\overline{x} \overline{y} \overline{z}\)

Show that cells in a K-map for Boolean functions in five variables represent minterms that differ in exactly one literal if and only if they are adjacent or are in cells that become adjacent when the top and bottom rows and cells in the first and eighth columns, the first and fourth columns, the second and seventh columns, the third and sixth columns, and the fifth and eighth columns are considered adjacent.

Find the duals of these Boolean expressions. $$\begin{array}{ll}{\text { a) } x+y} & {\text { b) } \overline{x} \overline{y}} \\ {\text { c) } x y z+\overline{x} \overline{y} \overline{z}} & {\text { d) } x \overline{z}+x \cdot 0+\overline{x} \cdot 1}\end{array}$$

Build a circuit using OR gates, AND gates, and inverters that produces an output of 1 if a decimal digit, encoded using a binary coded decimal expansion, is divisible by \(3,\) and an output of 0 otherwise.

In Exercises \(35-42,\) use the laws in Definition 1 to show that the stated properties hold in every Boolean algebra. Show that in a Boolean algebra, every element \(x\) has a unique complement \(\overline{x}\) such that \(x \vee \overline{x}=1\) and \(x \wedge \overline{x}=0\) .

In Exercises \(35-42,\) use the laws in Definition 1 to show that the stated properties hold in every Boolean algebra. Prove that in a Boolean algebra, the law of the double complement holds; that is, \(\overline{\overline{x}}=x\) for every element \(x .\)