<p>Extending Sparks’s theorem, we determine the cardinality of the lattice of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$(C_1,C_2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>C</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>C</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-clonoids of Boolean functions for certain pairs <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$(C_1,C_2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>C</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>C</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> of clones of Boolean functions. Namely, when <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$C_1$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>C</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation> is a subclone (a proper subclone, resp.) of the clone of all linear (affine) functions and <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$C_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>C</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> is a subclone of the clone generated by a semilattice operation and constants (a subclone of the clone of all 0- or 1-separating functions, resp.), then the lattice of <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$(C_1,C_2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>C</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>C</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-clonoids is uncountable. Combining this fact with several earlier results, we obtain a complete classification of the cardinalities of the lattices of <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$(C_1,C_2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>C</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>C</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-clonoids for all pairs <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$(C_1,C_2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>C</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>C</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> of clones on <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\{0,1\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>.</p>

Clonoids of Boolean functions with a linear source clone and a semilattice or 0- or 1-separating target clone

期刊论文
发表日期：

2026年3月24日

查看全文

Erkko Lehtonen

摘要

Extending Sparks’s theorem, we determine the cardinality of the lattice of $(C_1,C_2)$ $(C_{1}, C_{2})$ -clonoids of Boolean functions for certain pairs $(C_1,C_2)$ $(C_{1}, C_{2})$ of clones of Boolean functions. Namely, when $C_1$ $C_{1}$ is a subclone (a proper subclone, resp.) of the clone of all linear (affine) functions and $C_2$ $C_{2}$ is a subclone of the clone generated by a semilattice operation and constants (a subclone of the clone of all 0- or 1-separating functions, resp.), then the lattice of $(C_1,C_2)$ $(C_{1}, C_{2})$ -clonoids is uncountable. Combining this fact with several earlier results, we obtain a complete classification of the cardinalities of the lattices of $(C_1,C_2)$ $(C_{1}, C_{2})$ -clonoids for all pairs $(C_1,C_2)$ $(C_{1}, C_{2})$ of clones on $\{0,1\}$ ${0, 1}$ .