appropriate goodness measures, then the speciousness of the best $K$ rules (or all sufficiently good rules) can be checked exhaustively among those $K$ rules, ignoring the rest. The foundation of this powerful result is the following observation on the relationship between marginal and conditional independence relations.

Let us consider relationships of three binary variables $X$, $Q$, and $C$. Independence assumptions are presented by the following null hypotheses: $H_{01}$: $X$ and $C$ independent, $H_{02}$: $Q$ and $C$ independent, $H_{03}$: $Q$ and $C$ conditionally independent given $X$, $H_{04}$: $Q$ and $C$ conditionally independent given $\neg X$, $H_{05}$: $X$ and $C$ conditionally independent given $Q$, $H_{06}$: $X$ and $C$ conditionally independent given $\neg Q$. Then the composed null hypotheses $(H_{01}\wedge H_{03}\wedge H_{04})$ and $(H_{02}\wedge H_{05}\wedge H_{06})$ are equivalent.

The proof is by showing that both composed null hypotheses describe the same data distribution. We recall that the distribution can be represented by triplet $(n_{xc},n_{qc},n_{xqc})$, when $n$, $n_c$, $n_x$, $n_q$, and $n_{xq}$ are given.

Assuming $H_{01}\wedge H_{03}\wedge H_{04}$ means that $p_{xc}=p_xp_c$, $p_{xqc}=\frac{p_{xq}p_{xc}}{p_x}=p_{xq}p_c$, and $p_{\neg xqc}=\frac{p_{\neg xq}p_{\neg xc}}{p_{\neg x}}=p_{\neg xq}p_c$. Therefore, $p_{qc}=p_{xqc}+p_{\neg xqc}=(p_{xq}+p_{\neg xq})p_c=p_qp_c$, and the triplet is $(p_xp_c,p_qp_c,p_{xq}p_c)$.

Assuming $H_{02}\wedge H_{05}\wedge H_{06}$ means that $p_{qc}=p_qp_c$, $p_{xqc}=\frac{p_{xq}p_{qc}}{p_q}=p_{xq}p_c$, and $p_{x\neg qc}=\frac{p_{x\neg q}p_{\neg qc}}{p_{\neg q}}=p_{x\neg q}p_c$. Therefore, 