Question

Show that \({\bf{F}}(w,x,y,z) = wx + {\bf{yz}}\) is not a threshold function.

Short answer

Thus \({\bf{F}}(w,x,y,z) = wx + {\bf{yz}}\) is not a threshold function.

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 \({\bf{1}}\) if either term is \({\bf{1}}\).

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

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

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

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

A threshold gate produces output \({\bf{y}}\) if the input \({{\bf{x}}_{\bf{1}}}{\bf{,}}{{\bf{x}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}\) exceeds the threshold value \(T\) for the weights \({{\bf{w}}_{\bf{1}}}{\bf{,}}{{\bf{w}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{w}}_{\bf{n}}}\left( {{{\bf{w}}_{\bf{1}}}{{\bf{x}}_{\bf{1}}}{\bf{ + }}{{\bf{w}}_{\bf{2}}}{{\bf{x}}_{\bf{2}}}{\bf{ + \ldots + }}{w_n}{x_n} \ge T} \right)\).

Using the contradiction

To proof: \({\bf{F}}(w,x,y,z) = wx + {\bf{yz}}\) is not a threshold function.

Let us assume that \({\bf{F}}(w,x,y,z) = wx + {\bf{yz}}\) is a threshold function with weights \(a,b,c,d\) on \(w,x,y,z\) respectively and threshold \(T\)

When \({\bf{w = x = 1}}\) and \({\bf{y = z = 0}}\), then the function returns \(1\) and thus the threshold needs to be exceeded.

\(\begin{array}{c}{\bf{aw + bx + cy + dz = }}a \cdot 1 + b \cdot 1{\bf{ + }}c \cdot 0{\bf{ + }}d \cdot 0\\{\bf{ = a + b}}\\{\bf{ > }}T\end{array}\)

When \(w = x = 0\) and \(y = z = 1\), then the function returns \(1\) and thus the threshold needs to be exceeded.

\(\begin{array}{c}aw + bx + cy + dz = a \cdot 0 + b \cdot 0{\bf{ + }}c \cdot 1{\bf{ + }}d \cdot 1\\{\bf{ = c + d}}\\{\bf{ > }}T\end{array}\)

Check whether the given is threshold or not

Adding the previous two inequalities results in \({\bf{a + b + c + d > T + T = 2 }}T\).

When \(w{\bf{ = y = 1}}\) and \({\bf{x = z = 0}}\), then the function returns \({\bf{0}}\) and thus the threshold is not exceeded.

\(\begin{array}{c}{\bf{aw + bx + cy + dz = }}a \cdot 1{\bf{ + }}b \cdot 0{\bf{ + }}c \cdot 1{\bf{ + }}d \cdot 0\\{\bf{ = a + c}}\\{\bf{ < }}T\end{array}\)

When \(w = y = 0\) and \(x = z = 1\), then the function returns \({\bf{0}}\) and thus the threshold is not exceeded.

\(\begin{array}{c}aw + bx + cy + dz = a \cdot 0{\bf{ + }}b \cdot 1{\bf{ + }}c \cdot 0{\bf{ + }}d \cdot 1\\ = b + d\\ < T\end{array}\)

Check whether the given is threshold or not

Adding the previous two inequalities results in \({\bf{a + b + c + d < T + T = 2 T}}\).

However, it has then obtained a contradiction (since \({\bf{a + b + c + d > 2 T}}\) and \({\bf{a + b + c + d < 2 T}}\) cannot both be true at the same time).

Therefore, \({\bf{F}}(w,x,y,z) = wx + {\bf{yz}}\) is not a threshold function.