pyFunctionHood: local computation of immediate neighbours of a given monotone non-degenerate Boolean function

This Python library implements the set of rules described in arxiv:2407.01337, to compute the immediate neighbours of a given monotone non-degenerate Boolean function, without the need to generate the whole function space.

Here, immediate neighbours, are the monotone Boolean functions that are immediately above (or below) with respect to the partial order, in other words, are the functions that add/remove the minimum number of entries in the truth table.

Monotone non-degenerate Boolean functions are represented as sets of clauses, where each clause is represented by the bitarray data structure, and each bit represents the presence/absence of a given variable/regulator.

This work is developed in Python in https://github.com/ptgm/pyfunctionhood/, correcting and extending our previous work developed in Java in https://github.com/ptgm/functionhood/ and described in arxiv:1901.07623.

Given a reference monotone Boolean function, this library can be used in three distinct manners:

• in the command line passing the reference function as an argument
• using a graphical interface developed with Tkinter.
• as a library integrated in other tools

Usage - command line

Usage example: python main.py <type> <dimension> <function> [<changed_signs>]
 <type>:          [p]arents or [c]hildren
 <dimension>:     4
 <function>:      "{{1,2,3},{1,3,4},{2,3,4}}"
 <changed_signs>: optional, e.g. "0100" (bit i=1 means variable i switched sign)

Parents

To compute the parents (the functions immediately above) of a given monotone Boolean function, on can call:

python main.py p 4 "{{1,2,3},{1,3,4},{2,3,4}}"
R1 {{1,2,3},{1,2,4},{1,3,4},{2,3,4}}
R2 {{1,3},{2,3,4}}
R2 {{1,2,3},{3,4}}
R2 {{1,3,4},{2,3}}

which yields one parent function generated by Rule 1 (adding a maximal independent clause), and three parent functions generated by Rule 2 (collapsing pairs of clauses).

Children

To compute the children (the functions immediately below) of a given monotone Boolean function, one just change the first parameter:

python main.py c 4 "{{1,2,3},{1,3,4},{2,3,4}}"
R1 {{1,3,4},{2,3,4}}
R1 {{1,2,3},{1,3,4}}
R1 {{1,2,3},{2,3,4}}

Sign changes

Commands accept an optional trailing <changed_signs> argument: a bitstring of the same length as <dimension>, where bit i=1 means variable/regulator i switched sign (0->1 or 1->0) with respect to the reference topology. When provided (and not all zeros), parents/children are computed considering that change of signs instead of the default fixed-topology rules:

python main.py p 4 "{{1,2,3},{1,3,4},{2,3,4}}" 0100
python main.py c 4 "{{1,2,3},{1,3,4},{2,3,4}}" 0100

When omitted (or all zeros), the behaviour is unchanged from above, i.e. fixed-topology.

Usage - Graphical interface

There is also a graphical interface using Tkinter where the user can define the function dimension and write the desired monotone Boolean function.

The interface has a button to automatically write the Infimum function of the chosen dimension, and another for the Supremum function.

A Changed signs text box is also available to optionally specify a bitstring of the same length as the dimension, where bit i=1 means variable/regulator i switched sign. Leaving it empty (the default) keeps the fixed-topology behaviour.

The user has two buttons to generate the immediate neighbouring functions: Generate Parents to generate the list of parent functions, and Generate Children to generate the list of children functions.

In the text area the immediate neighbouring functions are shown, as well as any error if an invalid function is provided.

The button Default values cleans the text area and resets the input text boxes to their default values.

The button Close closes the application.

Usage - programmatically

If you are using this library directly you should first initialise the Hasse Diagram with a given dimension as a parameter (example below considers monotone Boolean functions of 4 variables/regulators):

from hassediagram import *
hd = HasseDiagram(4)

Then to initialise a function one can use a set of Clauses, where each Clause is a String representing the regulators that are present ("1") or absent ("0"), of dimension 4:

f = Function(4, {Clause('1110'), Clause('1011'), Clause('0111')})

or equivalently constructing the Function from its String representation:

f = Function.fromString(4, "{{1,2,3},{1,3,4},{2,3,4}}")

Once the Hasse Diagram and the function are defined, the method hd.get_f_parents(f) or hd.get_f_children(f) can be called, each returning a tuple of three sets of functions. The functions generated by Rule 1, by Rule 2 and by Rule 3, respectively. Below an example for parent functions generation:

s1, s2, s3 = hd.get_f_parents(f)
print(f'# parents from Rule1:{len(s1)} Rule2:{len(s2)} Rule3:{len(s3)}')
print('\n'.join(['R1 ' + str(f) for f in s1]\
              + ['R2 ' + str(f) for f in s2]\
              + ['R3 ' + str(f) for f in s3]))

Sign changes

To compute parents/children considering that some variables/regulators switched sign, use hd.get_f_parents_with_sign_changes(f, changed_signs) or hd.get_f_children_with_sign_changes(f, changed_signs), where changed_signs is a bitarray of the same size as the dimension, with bit i set to True if variable i switched sign:

from bitarray import bitarray
changed_signs = bitarray('0100')
s1, s2, s3 = hd.get_f_parents_with_sign_changes(f, changed_signs)

License

This code is available under GPL-3.0.

Cite

This work is available on arxiv:2407.01337.

Authors

• Patrícia Roxo
• José E. R. Cury
• Vasco Manquinho
• Claudine Chaouiya
• Pedro T. Monteiro