# In the context of conjunctive boolean functions, what does “$\Rightarrow y$” mean?

This post gives an example to illustrate the size of a Hypothesis Space for discrete classification problems.

A hypothesis is a function $$f:\mathcal{X} \to \mathcal{Y}$$, where $$\mathcal{X}$$ is the feature space (the set of all possible inputs) and $$\mathcal{Y}$$ is the label space (the set of all possible outputs). Let \begin{align} \mathcal{X} & = \{0,1\}^4\\ \mathcal{Y} & = \{0,1\}. \end{align}

So, there are $$2^{16}$$ possible hypotheses in total.

Given this Dataset

$$2^9$$ of the possible hypotheses are consistent with the dataset.

I guess I've understand the content above, and then I got stuck on this piece of that post.

What does "$$\Rightarrow y$$" mean?

I googled "conjunctive boolean functions" and got Conjunctive normal form, which does not give some explanation about "$$\Rightarrow$$" in similar cases.

I know this symbol "$$\Rightarrow$$" could work this way,

$$x = 2 \Rightarrow x^2 = 4$$ is true

where "$$\Rightarrow$$" means "implies", x = 2 "implies" $$x^2 = 4$$,

on the other hand, $$x^2 = 4$$ does not "imply" x = 2 in general, where the counterexample is "x = -2"

Does "$$\Rightarrow y$$" in "conjunctive boolean functions" table mean that "no matter x take any value, y is always true"? It does not make any sense.

Can any one give an explanation or a hint about this?

## supplement

according to @Joe's answer, $$\Rightarrow y$$ is called the “always positive” classifier in the book, which I didn't find the explanation about how that works in the link or google.

can someone illustrate how “always positive” classifier works? What is the "counterexample of ⇒𝑦"? Why would the number of the "counterexample of ⇒𝑦" is 1? Which 1?

• The graphic you have produced explicitly exhibits them all for four variables. Why isn't the generalization clear? – whuber Aug 9 '19 at 17:34
• @whuber Thanks for your reminder, I've updated the OP. – fu DL Aug 9 '19 at 22:13
• The “always positive” classifier just predicts that y=1 “always”, no matter what the values of the predictor variables are. It was mentioned in the book as an example of how certain measures of model accuracy have limitations, e.g. that the overly simplistic “always positive” classifier scores well in some situations (such as in the case when y rarely equals zero). – Joe Aug 13 '19 at 19:33

Also, you are correct, $$\Rightarrow y$$ is called the “always positive” classifier in the book.
• Thanks for answer. I went through the link you post, didn't find the explanation about how “always positive” classifier works. Would you please illustrate that? What is the "counterexample of $\Rightarrow y$"? Why would the number of the "counterexample of $\Rightarrow y$" is 1? Which 1? – fu DL Aug 10 '19 at 4:29
• Check the other chapters. The one I posted just has the section on “conjunctive”. I believe that the “counterexample of $\Rightarrow y$” is 1 because example 1 from the Dataset has $y=0$, so $y$ is not always positive. However, it seems to me like that column of “counterexample” has many errors. For example, the counterexample to $x_1 \Rightarrow y$ should be 6, not 3. – Joe Aug 10 '19 at 12:36
• After reading pages 157 & 158 again, I understand the table now. He says that you’re assuming (or given) that there is a true underlying classification function that is "conjunctive" (no "or" operators). So each of the counterexamples shows that the corresponding hypothesis is not the true classification function. However, I think his notation is unfortunate, because he should really be using $\Leftrightarrow$. – Joe Aug 10 '19 at 16:33