5
$\begingroup$

I'm having trouble understanding OEIS $\text{A}000157$, not necessarily its description, but rather its terms. I've already visited how many semantically different boolean functions are there for n boolean variables?, but the results didn't seem to match those listed in this sequence. The definition and elements are as follows:

Number of Boolean functions of n variables.

1, 2, 7, 111, 308063, 100126976263592, 131867858014413288241233435594064, ...

This is unclear to me for the following reason: What are the logical operators one should use? By looking at the first and seconds terms of this sequence, I assumed that $\lor\text{ and }\land$ are the only allowed operators, of course including brackets as needed. But this reasoning doesn't seem to hold for the third term:

Let $\space f:\Bbb{B}^3\rightarrow\Bbb{B}$. It can therefore have the following forms: $$\left\{ \begin{array}{l}f(a,\:b,\:c)=a\land b\land c\\ f(a,\:b,\:c)=a \lor b\lor c\\f(a,\:b,\:c)=(a\land b)\lor c\\ f(a,\:b,\:c)=a\lor(b\land c)\\f(a,\:b,\:c)=(a\land c)\lor b\\f(a,\:b,\:c)=(a\lor b)\land c\\f(a,\:b,\:c)=(a\lor c)\land b\\f(a,\:b,\:c)=(b\lor c)\land a\\\cdots\end{array}\right.$$

Is my understanding flawed, or are any of the statements above, in fact, semantically equivalent? Are the boolean operations used really $\lor$ and $\land$ (I feel like excluding $\lnot$ is quite odd)? Moreover, is there a formula for this sequence?

$\endgroup$
  • $\begingroup$ Did you look at OEIS A000370 which is linked to from A000157? $\endgroup$ – Somos Feb 14 '18 at 17:20
  • $\begingroup$ @Somos I did, and to be completely honest, I am not sure I understand that one either. $\endgroup$ – Mr. Xcoder Feb 14 '18 at 17:23
  • 1
    $\begingroup$ You can read the paper by Harrison mentioned on the OEIS page here oeis.org/A000370/a000370.pdf, it contains the definition. $\endgroup$ – Matthew Towers Feb 14 '18 at 17:40
  • $\begingroup$ While A000370 as explained in the answer is a natural sequence to come up with (for a combinatorialist), and A000157 is just that divided by two, I wonder why anyone would consider that latter sequence. It doesn't seem to count any naturally occuring structures. $\endgroup$ – Christian Sievers Feb 17 '18 at 9:17
2
$\begingroup$

The reader may be interested to know that there is a certain equivalence of boolean functions that may be counted by Power Group Enumeration. This is the case where equivalence includes permutation of the inputs and / or simultaneous complementation of the inputs and possible complementation of the outputs. We do not repeat the details of the algorithm here as it is exactly the same as what was documented at this MSE link I or at this MSE link II. The algorithm can be described very straightforwardly as counting the number of ways we may cover the cycles of permutation $\alpha$ by cycles of a permutation $\beta$ where $\alpha$ is a permutation from the group permuting the slots and $\beta$ from the group permuting the repertoire. Hence we have it solved if we can compute the cycle indices of the two groups.

In the present case the group acting on the values going into the slots i.e. the repertoire is trivial and has cycle index by inspection

$$Z(P) = \frac{1}{2} a_1^2 + \frac{1}{2} a_2.$$

The challenge is the cycle index $Z(Q)$ of the symmetric group and / or complementation acting on the $2^N$ input vectors / binary strings by permuting bits and / or complementing them. We have included an algorithm by enumeration (compute the action on the $2^N$ strings and factor it into cycles), but this will only serve as a verification of the correctness of the algorithm from first principles because of the exponential growth of the number of terms being permuted. We now explain the computation from first principles. There are two classes of permutations here, the first resulting from permuting the bits and the second from permuting bits followed by complementation / inversion. Start with the first. A permutation $\tau\in S_N$ acts on each of the $2^N$ strings by rotating bits according its cycles, i.e. the bits on every cycle are shifted by one position (except for a fixed point). With a cycle from $\tau$ of length $n$ we can therefore obtain cycles belonging to $\beta$ of length $d|n$ for all divisors $d$ of $n$, depending on the period $d$ of the substring of the bits corresponding to the cycle. Such a string of period length $d$ is obtained by repeating an aperiodic binary string of length $d$, $n/d$ times. It follows that the contribution for $\tau$ is obtained by iterating over all combinations of divisors of the cycles from $\tau,$ recording the value $d$ of the length of the resultant cycle and the number of possible assignments, which is $\gamma_1(d),$ the number of aperiodic binary strings of length $d.$ Given such a tuple of divisors the length of the combined cycle in $\beta$ is the LCM of the divisors and the total number of such cycles is given by dividing the total number of terms (product of the $\gamma_1(d)$) by the cycle length. Observe that for the terms membership in the set of strings from $2^N$ for a given tuple of divisors is disjoint and $\tau$ preserves this property. This is sufficient to compute the contribution to $\beta$ from the vector of divisors and the product of all contributions then yields the factored $\beta$ corresponding to $\tau.$ We just need $\gamma_1(d)$ but we have

$$\sum_{d|n} \gamma_1(d) = 2^n \quad\text{and hence}\quad \gamma_1(n) = \sum_{d|n} 2^d \mu(n/d).$$

Continuing with the second class of permutations we use the same scheme of classifying according to periodicity on the cycles of $\tau$ by constructing vectors of divisors for the cycle lengths of $\tau.$ The object remains to determine the lengths of the cycles that these bit strings are on. We observe that the circular orbits of substrings of the $2^N$ bit strings lying on a cycle generated by $\tau$ now have the property that not only is the string rotated by one position to get to the next, but also that the entries that are at odd offsets from the start of the orbit are not only rotated, but also have their bits inverted. This means that for a divisor $d$ that is odd we take $2d$ steps to return to the start, since the source string will not appear among the inverses (we would need an even number of bits) and the non-inverses advance by two positions with every appearance. The situation is somewhat more complicated when $d$ even. Supposing first that the source string will not appear among the inverses we then have that the orbit still has length $d.$ The odd-offset values are inverted but with $d$ even the source is reached at the end after a total of $d$ operations, with the inverted values at odd offsets. This leaves the case where the source string appears among the inverses. For this to happen it must consist of an even number of repetitions of a bit string followed by its inverse. For a string of length $n$ these are given by

$$\sum_{d|n} [[d\;\text{even}]] \times[[n/d\;\text{odd}]]\times \gamma_1(n/d).$$

Here the segments of length $n/d$ alternate between not being inverted and being inverted. The length must be odd because inversion applies at odd offsets in the orbit. With $n=2^p m$ and $p$ maximal this becomes

$$\sum_{d|m} \gamma_1(n/d/2^p) = \sum_{d|m} \gamma_1(m/d) = \sum_{d|m} \gamma_1(d) = 2^m \times [[n\;\text{even}]].$$

The Iverson bracket appears here because we get zero when $n$ is odd and not $2^n$, because there are no even divisors and the first Iverson bracket in the first formula fails on all $d.$

Introducing $v_2(n) = p$ we then have for the number $\gamma_2(d)$ of aperiodic strings where the source string appears among the inverses by Mobius inversion

$$\gamma_2(n) = \sum_{d|n} [[d\;\text{even}]] \times 2^{d/2^{v_2(d)}} \mu(n/d).$$

It remains to determine the length of the cycle these strings are on, which must be $d/2$ for one segment followed by its inverse since with four segments etc. the string would not be aperiodic. We now have all the ingredients to apply the construction from the first class without complementation, except that technically we have two kinds of contributions for $d$ where $\gamma_2(d)$ is not zero and $d$ is even, corresponding to source strings appearing and not appearing among the inverses. The computation remains the same -- compute the LCM of the length of all cycles for $\beta$ being generated by the cycles of $\tau$ and the number of strings having this profile in terms of divisors and inversion to determine the number of cycles of the length that was obtained. The contribution to the number of strings from the two cases is a factor of $\gamma_2(d)$ or $\gamma_1(d)-\gamma_2(d)$ accordingly. This concludes the documentation of the algorithm.

We may now compute the cycle indices of the slot permutation group for use with PGE. For example $n=5$ will produce

$${\frac {{a_{{1}}}^{32}}{240}}+1/24\,{a_{{1}}}^{16}{a_{{2}}}^{8} +1/16\,{a_{{1}}}^{8}{a_{{2}}}^{12}+1/12\,{a_{{1}}}^{8}{a_{{3}}}^{8} \\ +{\frac {13\,{a_{{2}}}^{16}}{120}} +1/12\,{a_{{1}}}^{4}{a_{{2}}}^{2}{a_{{3}}}^{4}{a_{{6}}}^{2} +1/8\,{a_{{1}}}^{4}{a_{{2}}}^{2}{a_{{4}}}^{6} \\ +1/8\,{a_{{2}}}^{4}{a_{{4}}}^{6}+1/10\,{a_{{1}}}^{2}{a_{{5}}}^{6} +1/6\,{a_{{2}}}^{4}{a_{{6}}}^{4}+1/10\,a_{{2}}{a_{{10}}}^{3}.$$

We can also compute cycle indices that are not accessible by enumeration, e.g. for $n=16$ the cycle index starts ($16!\times 2$ permutations)

$${\frac {{a_{{1}}}^{65536}}{41845579776000}} +{\frac {{a_{{1}}}^{32768}{a_{{2}}}^{16384}}{348713164800}} +{\frac {{a_{{1}}}^{16384}{a_{{2}}}^{24576}}{7664025600}} \\ +{\frac {{a_{{1}}}^{8192}{a_{{2}}}^{28672}}{348364800}} +{\frac {{a_{{1}}}^{4096}{a_{{2}}}^{30720}}{30965760}} +{\frac {{a_{{1}}}^{2048}{a_{{2}}}^{31744}}{5529600}}+\cdots$$

The sequence of the count of these equivalence classes of boolean functions is

$$2, 5, 26, 1072, 9340584, 6406603624626816, \\ 16879085743296494006611933604867584,\ldots$$

which is OEIS A299104. The Maple code for this computation goes as follows.

with(combinat);
with(numtheory);

APBS := n -> add(2^d*mobius(n/d), d in divisors(n));

MXODD_DIV :=
proc(n)
local m;

    m := n;

    while type(m, `even`) do
        m := m/2;
    od;

    m;
end;

APBS_INV := n ->
add(`if`(type(d, `even`), 2^MXODD_DIV(d), 0)*mobius(n/d),
    d in divisors(n));

pet_cycleind_symm :=
proc(n)
option remember;

    if n=0 then return 1; fi;

    expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

pet_flatten_term :=
proc(varp)
local terml, d, cf, v;

    terml := [];

    cf := varp;
    for v in indets(varp) do
        d := degree(varp, v);
        terml := [op(terml), seq(v, k=1..d)];
        cf := cf/v^d;
    od;

    [cf, terml];
end;

pet_cycleind_bin_p :=
proc(n)
option remember;
local res, prod, term, flat, iter;

    if n=1 then return a[1]^2 fi;

    iter :=
    proc(pos, cycs, sofar)
    local d, len, comb;

        if pos > nops(cycs) then
            len := lcm(seq(q, q in sofar));
            comb := mul(APBS(q), q in sofar);

            prod := prod*a[len]^(comb/len);
            return;
        fi;

        for d in divisors(op(1, cycs[pos])) do
            iter(pos+1, cycs, [op(sofar), d]);
        od;
    end;

    res := 0;

    for term in pet_cycleind_symm(n) do
        flat := pet_flatten_term(term);

        prod := 1;
        iter(1, flat[2], []);
        res := res + flat[1]*prod;
    od;

    res;
end;

bin_p_bool :=
proc(n)
option remember;
local idx, vars;

    idx := pet_cycleind_bin_p(n);
    vars := indets(idx);

    subs([seq(v=2, v in vars)], idx);
end;


pet_cycleind_bin_snp :=
proc(n)
option remember;
local res, prod, term, flat, iter;

    if n=1 then return 1/2*a[1]^2+1/2*a[2] fi;

    iter :=
    proc(pos, cycs, sofar)
    local d, q, len, comb;

        if pos > nops(cycs) then
            len := 1;
            comb := 1;

            for q to nops(cycs) do
                d := op(1, sofar[q]);
                if op(2, sofar[q]) then
                    len :=
                    lcm(len, d/2);
                    comb :=
                    comb *
                    APBS_INV(d);
                else
                    if type(d, `odd`) then
                        len :=
                        lcm(len, 2*d);
                    else
                        len :=
                        lcm(len, d);
                    fi;

                    comb :=
                    comb *
                    (APBS(d)-APBS_INV(d));
                fi;
            od;

            prod := prod*a[len]^(comb/len);
            return;
        fi;

        for d in divisors(op(1, cycs[pos])) do
            if APBS_INV(d) > 0 then
                iter(pos+1, cycs, [op(sofar), [d, true]]);
            fi;
            iter(pos+1, cycs, [op(sofar), [d, false]]);
        od;
    end;

    res := 0;

    for term in pet_cycleind_symm(n) do
        flat := pet_flatten_term(term);

        prod := 1;
        iter(1, flat[2], []);
        res := res + flat[1]*prod;
    od;

    res/2 + pet_cycleind_bin_p(n)/2;
end;

bin_snp_bool :=
proc(n)
option remember;
local idx, vars;

    idx := pet_cycleind_bin_snp(n);
    vars := indets(idx);

    subs([seq(v=2, v in vars)], idx);
end;

bin_snpn_bool :=
proc(n)
option remember;
local idx_slots, idx_cols, res, a, b,
    flat_a, flat_b, cyc_a, cyc_b, len_a, len_b, p, q;

    idx_slots := pet_cycleind_bin_snp(n);
    idx_cols := 1/2*a[1]^2+1/2*a[2];

    res := 0;

    for a in idx_slots do
        flat_a := pet_flatten_term(a);
        for b in idx_cols do
            flat_b := pet_flatten_term(b);

            p := 1;
            for cyc_a in flat_a[2] do
                len_a := op(1, cyc_a);
                q := 0;

                for cyc_b in flat_b[2] do
                    len_b := op(1, cyc_b);

                    if len_a mod len_b = 0 then
                        q := q + len_b;
                    fi;
                od;

                p := p*q;
            od;

            res := res + p*flat_a[1]*flat_b[1];
        od;
    od;

    res;
end;


pet_autom2cycles :=
proc(src, aut)
local numa, numsubs;
local marks, pos, cycs, cpos, clen;

    numsubs := [seq(src[k]=k, k=1..nops(src))];
    numa := subs(numsubs, aut);

    marks := Array([seq(true, pos=1..nops(aut))]);

    cycs := []; pos := 1;

    while pos <= nops(aut) do
        if marks[pos] then
            clen := 0; cpos := pos;

            while marks[cpos] do
                marks[cpos] := false;
                cpos := numa[cpos];
                clen := clen+1;
            od;

            cycs := [op(cycs), clen];
        fi;

        pos := pos+1;
    od;

    return mul(a[cycs[k]], k=1..nops(cycs));
end;

ENUM_cycleind_bin_p :=
proc(n)
option remember;
local cind, perm, src, autom, ind, d;

    src := [];

    for ind from 2^n to 2*2^n-1 do
        d := convert(ind, `base`, 2);
        src := [op(src), d[1..n]];
    od;

    cind := 0;

    perm := firstperm(n);

    while type(perm, `list`) do
        autom :=
        [seq([seq(src[q][perm[p]], p=1..n)],
             q=1..2^n)];

        cind := cind +
        pet_autom2cycles(src, autom);

        perm := nextperm(perm);
    od;

    cind/n!;
end;

ENUM_cycleind_bin_snp :=
proc(n)
option remember;
local cind, perm, src, autom, ind, d;

    src := [];

    for ind from 2^n to 2*2^n-1 do
        d := convert(ind, `base`, 2);
        src := [op(src), d[1..n]];
    od;

    cind := 0;

    perm := firstperm(n);

    while type(perm, `list`) do
        autom :=
        [seq([seq(1-src[q][perm[p]], p=1..n)],
             q=1..2^n)];

        cind := cind +
        pet_autom2cycles(src, autom);

        perm := nextperm(perm);
    od;

    cind/n!/2 + ENUM_cycleind_bin_p(n)/2;
end;
$\endgroup$
2
$\begingroup$

The sequence A000370 enumerates Boolean functions up to an equivalence relation. More precisely, a function with any of its inputs or output negated is equivalent to the original function. Also, if the inputs are permuted, it is equivalent as well. So the sequence enumerates the equivalence classes. In the case of $n=2$, for example, there are $4$ equivalence classes. $f(A,B)=T$ is one class with $2$ members, $f(A,B)=A$ is another with $4$ members, $f(A,B)=A\lor B$ with $8$ members, and $f(A,B)=A\oplus B$ with $2$ members. Given this, then $A000157(n) = A000370(n)/2$ as stated in the OEIS entry for A000157.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.