BFC Post


1 Introduction

In February 2026, I began designing and implementing a Boolean Function Compression (BFC) algorithm as part of a post on Machine Learning [forthcoming]. I originally expected this project to require about two weeks to design and implement. After completing the first BFC algorithm I wondered if it could improved or superceded by an algorithm with better compression performance. I then developed two additional BFC algorithms, which expanded the project duration to eight months.

Early in the BFC project I did an internet search to see whether work had already been done on BFC. Unfortunately (or fortunately, perhaps) my search was rather desultory and didn’t find anything useful. So, the three BFC algorithms presented in this post were developed without exposure to prior work. Much later as I began to prepare this post for publication I did a more comprehensive internet search and discovered that extensive work has already been done on this problem. In this post I don’t review or summarize the existing BFC work – I assume that interested parties can do this on their own. As a tech hobbyist I have the luxury of not caring about either originality or utility in the tech work I do. I work on problems that I find interesting and allow me to exercise my software engineering skills. From this standpoint, the BFC project has been satisfying but I’m ready to move on to a new challenge.


2 Table of Contents

1 Introduction
2 Table of Contents
3 BFC Problem Statement
4 Boolean Function Special Cases
5 Bottom-Up BFC Algorithm Description
6 Top-Down BFC Algorithm Description
7 Exhaustive BFC Algorithm Description
8 BFC Algorithm Compression Performance Comparison
9 BFC Algorithm Scalability
10 Software Implementation
11 Open Questions


3 BFC Problem Statement

Figure 1.1 provides a high-level view of the boolean function compression (BFC) problem. A boolean function is input to a BFC algorithm and a ternary function is output. The ternary function is a compressed version of the boolean function.

Figure 1.2 provides an example of BFC algorithm input and output. The input is a boolean function with four binary input variables and one binary output variable. The output is a ternary function with four ternary input variables and one binary output variable. The boolean function’s input variable values can be 0 or 1 and the output variable value can be 0 or 1. The ternary function’s input variable values can be 0, 1, or * (wildcard) and the output variable value can be 0 or 1. When an input variable value is a wildcard it means that the input value can be either 0 or 1. The input variables are numbered 0 to 3 from right to left with variable number 0 being least significant and variable number 3 being most significant.

A boolean function is composed of boolean rules. This post only considers boolean functions in which every possible combination of input variable values is represented by a boolean rule. This means that a boolean function with n inputs will have 2^n boolean rules. Figure 1.2 shows a four-input boolean function with 2^4 = 16 boolean rules. Each boolean rule can be uniquely identified by the values of its input variables and also by the base 10 representation of its input variable values, called the boolean rule number. The ternary rules within a ternary function are also numbered, but this is only a short-hand way of identifying a particular ternary rule within the ternary function. There is no arithmetic operation by which ternary input variable values are transformed into a ternary rule number or vice-versa. Figure 1.2 highlights boolean rule number 10 and ternary rule number 4.

Each ternary rule in a ternary function can be expanded to ‘cover’ one or more boolean rules in a boolean function. Figure 1.3 provides two examples. In the first example, the two wildcards in the ternary rule can be expanded to create four boolean rules. The output of each of these boolean rules is consistent with the boolean function in Figure 1.2; the ternary rule is said to FIRE. In the second example, the single wildcard in the ternary rule can be expanded to create two boolean rules. However, the output of the second boolean rule is inconsistent with the boolean function in Figure 1.2; the ternary rule does not FIRE. In general, a ternary rule with n wildcard inputs can be expanded to cover 2^n boolean rules.

In Figure 1.4 two different BFC algorithms compress the same boolean function. The first algorithm achieves maximal compression: there does not exist a ternary function with fewer ternary rules. The second algorithm provides sub-maximal compression for this boolean function: there are seven ternary rules in the second ternary function whereas for maximal compression there should be one.

There are two requirements for a particular ternary function to be a valid compression of a boolean function:
(1) each boolean rule in the boolean function must be covered by exactly one ternary rule in the ternary function; and
(2) boolean and ternary function outputs must be equal for all function inputs.
The two ternary functions shown in Figure 1.4 are both valid compressions of the boolean function but only one is maximal.


4 Boolean Function Special Cases

Figure 2.1 shows the two maximally compressible boolean functions with four input variables. Each boolean function can be compressed to a ternary function with one ternary rule. No other boolean function with four input variables has this property. Generalizing the two maximally compressible boolean functions shown in Figure 2.1 to boolean functions with a different number of input variables is straightforward – the boolean function outputs will be either all 0 or all 1.

Figure 2.2 shows the two minimally compressible (or incompressible) boolean functions with four input variables. Each boolean function cannot be compressed, so the ternary function has the same number of ternary rules as the boolean function has boolean rules. No other boolean function with four input variables has this property.

Figure 2.3 shows how the first incompressible boolean function shown in Figure 2.2 is generated. The process involves repeated nested copy-with-inversion operations. First, the output of boolean rule 0 is copied-with-inversion to the output of rule 1. Then, the outputs of rules 0 and 1 are copied-with-inversion to the outputs of rules 2 and 3. Then, the outputs of rules 0 – 3 are copied-with-inversion to the outputs of rules 4 – 7. Finally, the outputs of rules 0 – 7 are copied-with-inversion to the outputs of rules 8 – 15. This process can be readily generalized to boolean functions with any number of input variables.


5 Bottom-Up BFC Algorithm Description

5.1 Bottom-Up (BU) BFC introduction

My goal for the BU BFC algorithm was to find a simple compression algorithm that provides decent performance.

5.2 BU BFC algorithm overview

(1) mark all binary rules as uncovered to start
(2) begin with binary rule number 0:
generalize it as much as possible
mark the binary rules covered by the resulting ternary rule
(3) proceed to the next uncovered binary rule (if one exists) & repeat previous step
(4) when all binary rules have been covered by a ternary rule, halt

5.3 BU BFC binary rule generalization sketch

(1) begin with a number-of-wildcards (NWC) = 0 t-rule (just a copy of the b-rule)
(2) search for a NWC = 1 t-rule that FIREs
if no such t-rule is found, done
(3) search for a NWC = 2 t-rule that FIREs using the single wildcard (WC) found so far as ‘given’
if no such t-rule is found, done
(4) search for a NWC = 3 t-rule that FIREs using the two WCs found so far as ‘given’
if no such t-rule is found, done
(5) etc. up to NWC = total number of input variables in the B-FN

5.4 BU BFC algorithm example

Figure 3.1 shows a four-input B-FN (16 b-rules) and the associated T-FN (7 rules) found by the Bottom-Up BFC algorithm.

Figure 3.2 shows the same four-input B-FN and the candidate t-rules generated by the algorithm as it searched for t-rules that FIRE.

(1) The algorithm began by searching for a t-rule with one wildcard that FIREs. The first candidate t-rule generated did not FIRE, but the second one did.

(2) The algorithm then began searching for a t-rule with two wildcards using the single wildcard at input number 1 as given. The algorithm tested every possible two-wildcard t-rule and did not find one that FIREd.

(3) The algorithm then added the single-wildcard t-rule to the T-FN as number 0. The two b-rules covered by the new t-rule ([00*0 -> 1]) are numbers 0 and 2:

binary 0000; base 10 = 0
binary 0010; base 10 = 2

(4) The algorithm then moved to the next uncovered b-rule (number 1) and tried to generalize it. In this case, a t-rule with one wildcard FIREd and then another with two wilcards FIREd, so the algorithm tested every possible three-wildcard t-rule and did not find one that FIREd.

(5) The algorithm then added the new two-wildcard t-rule to the T-FN as number 1. The four b-rules covered by the new t-rule ([**01 -> 0]) are numbers 1, 5, 9, and 13:

binary 0001; base 10 = 1
binary 0101; base 10 = 5
binary 1001; base 10 = 9
binary 1101; base 10 = 13

(6) The algorithm then moved to the next uncovered b-rule (number 3) and tried to generalize it. This process continued for the remaining uncovered b-rules in the B-FN; five additional t-rules were found.

(7) The algorithm was unable to generalize the last two uncovered b-rules ([1000 -> 1] and [1010 -> 0]), therefore the t-rules are the same as the associated b-rules for t-rule numbers 5 and 6.

5.5 BU BFC performance

Occasional sub-maximal performance by this algorithm is due to:
(1) the order in which b-rules are selected for generalization is arbitrary. Sometimes greater compression would be achieved by selecting b-rules in a different order. For example, the algorithm as described begins with b-rule number 0 and then selects uncovered b-rules with progressively larger numbers. The algorithm could instead begin with b-rule number [max] and then select uncovered b-rules with progressively smaller numbers.
(2) the order in which inputs within a b-rule are selected for generalization (i.e., replacement with a wildcard) is arbitrary. Sometimes greater compression would be achieved by selecting b-rule inputs in a different order. For example, the algorithm as described begins with b-rule input number 0 and then check inputs with progressively larger numbers. The algorithm could instead begin with b-rule input number [max] and then select inputs with progressively smaller numbers.


6 Top-Down BFC Algorithm Description

6.1 Top-Down (TD) BFC Introduction

My goal for the TD BFC algorithm was to improve compression performance relative to the BU BFC algorithm. The TD BFC algorithm eliminates the arbitrariness associated with the BU BFC algorithm’s b-rule selection order.

6.2 TD BFC algorithm overview

(1) generate the initial candidate t-rule
(2) if the candidate t-rule doesn’t FIRE, generate the next candidate t-rule
otherwise, add the candidate t-rule to the T-FN
(3) repeat until all b-rules in the B-FN are covered

6.3 TD BFC algorithm notes

  • candidate t-rules are generated in the order of greatest number of wildcards (equal to the number of inputs) to the least number of wildcards (zero). This is the opposite of the BU BFC algorithm.
  • for any particular number of wildcards, every possible permutation of wildcard locations within the t-rule is generated as a candidate t-rule

6.4 TD BFC algorithm example

Figure 4.1 shows a four-input B-FN (16 b-rules) and the associated T-FN (6 rules) found by the TD BFC algorithm.

Figure 4.2 shows the same four-input B-FN and the candidate t-rules generated by the algorithm as it searched for t-rules that FIRE.

(1) The algorithm began by generating a candidate t-rule with four wildcards and then checking to see if it FIREs – it did not.

When generating a candidate t-rule the algorithm sets the t-rule output to the output of the first b-rule covered by the t-rule. The algorithm then checks whether the t-rule FIREs by determining whether all of the other b-rules covered by the t-rule have the same output value.

(2) The algorithm then checked whether any t-rules containing three wildcards FIREd – none did.

(3) The algorithm found three FIREd t-rules with two wildcards and one FIREd t-rule with one wildcard.

(4) The algorithm finished by finding two FIREd t-rules with no wildcards.

The resulting T-FN contained six t-rules.

6.5 TD BFC algorithm performance

Occasional sub-maximal performance by this algorithm is due to the arbitrary order in which candidate t-rules are generated. For example, in Figure 4.2 the order in which candidate t-rules are generated for NWC = 2 is from [00** -> 1] to [**11 -> 0]. However, this algorithm could have instead been implemented using the reverse order, which would sometimes affect compression performance.


7 Exhaustive BFC Algorithm Description

7.1 Exhaustve (EX) BFC Introduction

My goal for the EX BFC algorithm was maximal compression performance. The algorithm failed to deliver this level of performance.

In contrast to the BU and TD algorithms, the EX algorithm’s search space consists of T-FNs rather than t-rules.

7.2 EX BFC algorithm overview

NBR = number of b-rules in B-FN = 2^(number of input variables)
NTR = number of t-rules in T-FN

7.2.1 Algorithm

(1) generate a candidate NTR=1 T-FN
if it FIREs, done; return it
(2) generate candidate NTR=2 T-FNs from the NTR=1 T-FN until one FIREs
if one FIREs, done; return it
(3) generate candidate NTR=3 T-FNs from NTR=2 T-FNs until one FIREs
if one FIREs, done; return it
etc …
(4) generate the candidate NTR=NBR T-FN from the first NTR=(NBR-1) T-FN
it must FIRE, done; return it

7.2.2 How to generate a candidate NTR=(n+1) T-FN from a NTR=n T-FN

Replace a t-rule in the NTR=n T-FN by two t-rules. A wildcard for input number i in the NTR=n t-rule is replaced by 0 in one NTR=(n+1) t-rule and is replaced by 1 in the other. All of the other t-rules in the NTR=n T-FN are copied unchanged to the NTR=(n+1) T-FN.

7.2.3 How to check whether a candidate T-FN FIREs:

If there exists some method of assigning output values to all of the t-rules in the candidate T-FN such that the T-FN outputs equal the B-FN outputs, then the T-FN FIREs.

7.3 EX BFC algorithm example

Figure 5.1 shows a four-input B-FN (16 b-rules) and the associated T-FN (6 rules) found by the Exhaustive BFC algorithm. EX found the same T-FN as TD.

Figure 5.2 shows the same four-input B-FN and some of the candidate T-FNs generated by the algorithm as it searched for a T-FN that FIREs.

(1) The algorithm began by generating a candidate T-FN with one t-rule containing four wildcards and then checking to see if it FIREd – it did not.

(2) The algorithm then generated four candidate T-FNs with two t-rules, none of which FIREd. Each NTR=2 T-FN was generated by replacing a t-rule input wildcard in the NTR=1 T-FN with NTR=2 T-FN t-rules containing 0 and 1.

(3) The algorithm then generated 24 candidate T-FNs with three t-rules, none of which FIREd. Each NTR=3 T-FN was generated by replacing a t-rule input wildcard in the NTR=2 T-FN with NTR=3 T-FN t-rules containing 0 and 1. There are four NTR=2 T-FNs each with a total of six wildcards, which is why there are 4*6 = 24 NTR=3 T-FNs.

(4) This process continued for the NTR=4 candidate T-FNs, where 168 were generated; none of these FIREd.

(5) For NTR=5, 1248 candidate T-FNs were generated; none of these FIREd.

(6) For NTR=6, the 5790th candidate T-FN generated also FIREd. The search halted and this T-FN was returned as the compressed B-FN.

7.4 EX BFC algorithm performance

Occasional sub-maximal performance by this algorithm (despite the original design goal) may be due to the unintended omission of some valid T-FNs from its search space. For example, Figure 5.3 shows that for 3-input boolean function number 66 the EX BFC algorithm finds a T-FN with NTR=6 whereas the BU BFC algorithm finds a T-FN with NTR=5. Barring an EX algorithm implementation error the only other explanation for the better performance by the BU BFC algorithm is that the T-FN with NTR=5 is not in the EX algorithm’s search space.


8 BFC Algorithm Compression Performance Comparison

Figure 6 shows the number of t-rules (NTR) within the ternary function (T-FN) produced by the Bottom-Up (BU), Top-Down (TD), and Exhaustive (EX) compression algorithms for each of the 256 3-input binary functions (B-FNs). The smaller the NTR, the greater the compression. The B-FNs where the compression algorithms produced different NTRs are marked. For example, for B-FN #6 the BU algorithm produced a T-FN with 6 t-rules whereas the TD and EX algorithms found a T-FN with 5 t-rules.

Figure 6 also shows the sum of NTRs across all 256 B-FNs for each of the compression algorithms. The figure shows that BU > TD > EX for the total NTRs, but the compression performance differences between the algorithms for the 3-input B-FNs are modest.


9 BFC Algorithm Scalability

Figure 7 shows how the number of candidate t-rules generated (NCTRG) increases as the number of incompressible B-FN inputs (n) increase for the BU and TD algorithms. For the BU algorithm, NCTRG(n) is conjectured to be n * 2^n. NCTRG(n+1) / NCTRG(n) is conjectured to converge to 2 as n grows large. For the TD algorithm, NCTRG(n) is conjectured to be 3^n. NCTRG(n+1) / NCTRG(n) is conjectured to be 3.

Figure 7 also shows how the number of candidate T-FNs generated (NCTFG) increases as the number of incompressible B-FN inputs (n) increase for the EX algorithm. Unfortunately, determining NCTFG(n) for n = 4 exceeds my available computational resources. No general pattern is apparent from the first three entries in the table.


10 Software Implementation

The C language source code for my three BFC algorithm implementations can be found HERE. The README file in the zip archive provides additional information. This section provides additional information not found in the README.

10.1 BU BFC implementation

My first BFC implementation was the BU algorithm. It has the simplest implementation of the three algorithms described in this post.

10.2 TD BFC implementation

My second BFC implementation was the TD algorithm. My TD implementation is more complex than my BU implementation but less complex than my EX implementation.

10.3 EX BFC implementation

My third BFC implementation was the EX algorithm. It has the most complex implementation of the three algorithms described in this post.

My EX implementation is memory efficient but computationally inefficient. In order to generate candidate T-FNs with NTR = n, the implementation recursively generates all T-FNs with NTR = 1 through NTR = (n-1). This is grossly inefficient from a computational standpoint. An alternative approach would be to store all NTR = (n – 1) T-FNs in memory and use these as ‘seeds’ to generate NTR = n T-FNs. If no NTR = n T-FNs FIRE they would be stored in memory and used as seeds for NTR = (n + 1) T-FN generation. This approach would be computationally efficient but memory inefficient. The implementation of a computationally efficient EX algorithm is left as an exercise for the reader.


11 Open Questions

(1) Section 4 shows that there is a symmetry between the two BF special cases: for some number of inputs, exactly two boolean functions are maximally compressible (the number of t-rules in the maximal ternary function is one) and exactly two boolean functions are incompressible (the number of t-rules in the maximal ternary function equals the number of b-rules in the boolean function). Does some kind of symmetry continue between boolean functions that become less compressible (the number of t-rules in the maximal ternary function becomes greater than one) and boolean functions that become more compressible (the number of t-rules in the maximal ternary function becomes less than the number of b-rules in the boolean function)?

(2) For the BFC BU algorithm, prove that NCTRG(n) = n * 2^n, where n is the number of inputs in an incompressible boolean function. See Section 9.

(3) For the BFC TD algorithm, prove that NCTRG(n) = 3^n, where n is the number of inputs in an incompressible boolean function. See Section 9.

(4) The BFC BU, TD, and EX algorithms are all heuristic. For any given number of inputs are there certain boolean functions in which these algorithms perform much worse than an algorithm performing maximal compression?

(5) The BFC EX algorithm was intended to provide maximal compression, but failed during testing (occasionally BU and TD performed better – see Section 7.4). Can the EX algorithm be repaired? (Note: it’s possible that the EX algorithm is in fact maximal and that occasional sub-maximal compression performance is due to a bug in the code. I’m not aware of any implementation errors).

(6) An advantage of the BFC EX algorithm is that every candidate T-FN generated is guaranteed to be valid (all b-rules are covered by exactly one t-rule). If the BFC EX algorithm cannot be repaired (see question 5), is there an alternative approach that generates every possible candidate T-FN with NTR=n without generating invalid T-FNs?

(7) An alternative BFC algorithm design providing maximal compression would generate both valid and invalid T-FNs and then detect and discard the invalid T-FNs so that only valid T-FNs are checked for consistency with the boolean function outputs. Presumably this would be less computationally efficient than a maximal compression algorithm that only generates valid T-FNs (such as EX) but may be easier to design and implement. What is this alternative maximal BFC algorithm?

(8) Many years ago I briefly examined a generalization of the ternary function presented in this post. In the generalized ternary function (GTFN) the coverage of ternary rules can overlap. A ternary rule within a GTFN that FIREs in response to some input produces a “vote” for 0 or 1 that is aggregated with the “votes” of any other ternary rules that also FIRE in response to the input. The GTFN then outputs a 0 or 1 based on the result of the vote aggregation. What I found interesting about GTFNs is that it is possible to perfectly represent a boolean function as a GTFN although individual ternary rules within the GTFN may occasionally vote wrong (i.e., vote for 0 when the correct output is 1 or vice-versa). From imperfection, perfection!

A GTFN may be more resilient to damage than a boolean function. If an individual voter (ternary rule) within a GTFN “dies” (stops functioning), there may be other voters that continue to operate, allowing the GTFN to continue to respond to inputs with an output (although with increased probability of error).

What is an algorithm for generating GTFNs from boolean functions?