Question

Show that \({\bf{F(x,y) = x}} \oplus {\bf{y}}\) is not a threshold function.

Short answer

The given \({\bf{F(x,y) = x}} \oplus {\bf{y}}\) is not a threshold function.

Step-by-step solution

Definition

A function takes the value 1 if a specified function of the arguments exceeds a threshold and 0.

Contradiction method

It proves this by contradiction. Suppose that \({\bf{a,b}}\) and \({\bf{T}}\) are such that \({\bf{ax + by }} \ge {\bf{T}}\) if and only if \({\bf{x}} \oplus {\bf{y = l}}\), i.e., if and only if either \({\bf{x = 1}}\) and \({\bf{y = 0}}\), or else \({\bf{x = 0}}\) and \({\bf{y = 1}}\). Thus, for the first case it needs \({\bf{a}} \ge {\bf{T}}\), and for the second it needs \({\bf{b}} \ge {\bf{T}}\). Since it needs \({\bf{ax + by < T}}\) for \({\bf{x = y = 0}}\), it knows that \({\bf{T > 0}}\). Hence in particular \({\bf{b}}\) is positive.

Therefore, it has \({\bf{a + b > a}} \ge {\bf{T}}\), which contradicts the fact that \({\bf{1}} \oplus {\bf{1 = 0}}\) (requiring \({\bf{a + b}} \le {\bf{T}}\)).