Question

For each of these equalities either prove it is an identity or find a set of values of the variables for which it does not hold.

\(\begin{array}{l}a)x|(y\mid z){\bf{ = }}(x\mid y)|z\\b)x \downarrow (y \downarrow z){\bf{ = }}(x \downarrow y) \downarrow (x \downarrow z)\\c)x \downarrow (y\mid z){\bf{ = }}(x \downarrow y)\mid (x \downarrow z)\end{array}\)

Define the Boolean operator \( \odot \) as follows: \(1 \odot 1{\bf{ = }}1,1 \odot 0{\bf{ = }}0,0 \odot 1{\bf{ = }}0\), and \(0 \odot 0{\bf{ = }}1\).

Short answer

\((a)\)Identity does not hold for \((x,y,z){\bf{ = }}(0,0,1),(0,1,1),(1,0,0),(1,1,0)\).

\((b)\)Identity does not hold for \((x,y,z){\bf{ = }}(0,0,1),(0,1,0),(1,0,0),(1,0,1),(1,1,0),(1,1,1)\).

\((c)\) Identity does not hold for \((x,y,z){\bf{ = }}(0,0,1),(0,1,0),(1,0,0),(1,0,1),(1,1,0),(1,1,1)\).

Step-by-step solution

Definition

The complement of an element: \(\bar 0{\bf{ = 1}}\) and \({\bf{\bar 1 = 0}}\).

The Boolean sum \({\bf{ + }}\) or \(OR\) is \(1\) if either term is \(1\).

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

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

The \(XOR\) operator \( \oplus \) is \(1\) if one of the terms is \(1\) (but not both).

The \(NAND\) operator \(\mid \) is \(1\) if either term is \(0\).

Domination laws

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

Check whether the given hold identity or not

(a)

\(x|(y\mid z){\bf{ = }}(x\mid y)|z\)

Now create a table for all possible values of \(x,y\) and \(z\).

\(\begin{array}{*{20}{c}}x&y&z&{y\mid z}&{x\mid y}&{x\mid (y\mid z)}&{(x\mid y)\mid z}\\0&0&0&1&1&1&1\\0&0&1&1&1&1&0\\0&1&0&1&1&1&1\\0&1&1&0&1&1&0\\1&0&0&1&1&0&1\\1&0&1&1&1&0&0\\1&1&0&1&0&0&1\\1&1&1&0&0&1&1\end{array}\)

Then note that the last two columns of the table are not identical, thus the identity does not hold, for example, the last two columns differ in the second row which corresponds with the solution \((x,y,z){\bf{ = }}(0,0,1)\).

Therefore, the identities do not hold for \((x,y,z){\bf{ = }}(0,0,1),(0,1,1),(1,0,0),(1,1,0)\).

Check whether the given hold identity or not

(b)

\(x \downarrow (y \downarrow z){\bf{ = }}(x \downarrow y) \downarrow (x \downarrow z)\)

Now create a table for all possible values of \(x,y\) and \(z\).

\(\begin{array}{*{20}{c}}x&y&z&{y \downarrow z}&{x \downarrow y}&{x \downarrow z}&{x \downarrow (y \downarrow z)}&{(x \downarrow y) \downarrow (x \downarrow z)}\\0&0&0&1&1&1&0&0\\0&0&1&0&1&0&1&0\\0&1&0&0&0&1&1&0\\0&1&1&0&0&0&1&1\\1&0&0&1&0&0&0&1\\1&0&1&0&0&0&0&1\\1&1&0&0&0&0&0&1\\1&1&1&0&0&0&0&1\end{array}\)

Then note that the last two columns of the table are not identical, thus the identity does not hold, for example, the last two columns differ in the second row which corresponds with the solution \((x,y,z){\bf{ = }}(0,0,1)\).

Therefore, the identities do not hold for

\((x,y,z){\bf{ = }}(0,0,1),(0,1,0),(1,0,0),(1,0,1),(1,1,0),(1,1,1)\).

Check whether the given hold identity or not

(c)

\(x \downarrow (y\mid z){\bf{ = }}(x \downarrow y)\mid (x \downarrow z)\)

Now create a table for all possible values of \(x,y\) and \(z\).

\(\begin{array}{*{20}{c}}x&y&z&{y\mid z}&{x \downarrow y}&{x \downarrow z}&{x \downarrow (y\mid z)}&{(x \downarrow y)\mid (x \downarrow z)}\\0&0&0&1&1&1&0&0\\0&0&1&1&1&0&0&1\\0&1&0&1&0&1&0&1\\0&1&1&0&0&0&1&1\\1&0&0&1&0&0&0&1\\1&0&1&1&0&0&0&1\\1&1&0&1&0&0&0&1\\1&1&1&0&0&0&0&1\end{array}\)

Then note that the last two columns of the table are not identical, thus the identity does not hold, for example, the last two columns differ in the second row which corresponds with the solution \((x,y,z){\bf{ = }}(0,0,1)\).

Therefore, the identities do not hold for

\((x,y,z){\bf{ = }}(0,0,1),(0,1,0),(1,0,0),(1,0,1),(1,1,0),(1,1,1)\).