BoolForge Tutorial #1: Working with Boolean functions

In this tutorial, we will explore the BooleanFunction class — the foundation of BoolForge. You will learn how to:

• create Boolean functions from truth tables and text expressions,

• compute basic properties such as degree and bias, and

• convert between truth tables, logical expressions, polynomials, and the CANA package.

import boolforge
import numpy as np

Create a Boolean function

Boolean functions can be described in logical form, as polynomials, or as truth tables. BoolForge treats Boolean functions as binary vectors of length \(2^n\), where n is the number of inputs. The vectors describe the right side of the truth table. The left side of the truth table is not stored because it is the same for any function with n inputs. For example, the function f(A,B) = A AND B is stored as [0,0,0,1], which is exactly the right side of the truth table

A	B	f(A,B)
0	0	0
0	1	0
1	0	0
1	1	1

Create a Boolean function from truth table

An instance of BooleanFunction can be generated by specifying the right side of the truth table, i.e., by providing a binary vector of length \(2^n\) for any \(n\geq 0\). For example, to create the AND function above, we can write

# Define a simple Boolean function f(A,B) = A AND B with optional name 'f_AND'
f = boolforge.BooleanFunction([0, 0, 0, 1], name="f_AND")
print('f',f)

f [0 0 0 1]

Create a Boolean function from text

Instances of BooleanFunction can also be created from text. For example, to define the same function as f, we can write

f2 = boolforge.BooleanFunction('A and B')
print('f2',f2)

f2 [0 0 0 1]

The text processor is fairly versatile. For example, we can define the same function as f also by writing

f3 = boolforge.BooleanFunction('A + B > 1')
print('f3',f3)

f3 [0 0 0 1]

Some examples of more complicated functions include

# Define a 3-input function without any symmetries
g = boolforge.BooleanFunction('(A AND B) OR (NOT A AND C)')

# Define a 3-input linear / parity function
h = boolforge.BooleanFunction('(x + y + z) % 2 == 0')

# Define a 3-input threshold function
k = boolforge.BooleanFunction('x + y - z > 0')

labels = ['g','h','k']
boolforge.display_truth_table(g,h,k,labels=labels)

x1      x2      x3      |       g       h       k
-------------------------------------------------
0       0       0       |       0       1       0
0       0       1       |       1       0       1
0       1       0       |       0       0       1
0       1       1       |       1       1       0
1       0       0       |       0       0       1
1       0       1       |       0       1       0
1       1       0       |       1       1       1
1       1       1       |       1       0       1

Attributes of BooleanFunction

Every instance of BooleanFunction has five attributes:

attribute	data type	description
f	np.array(int)	stores the Boolean function (the right side of its truth table)
n	int	the degree, i.e., the number of variables
variables	np.array(str)	the name of the variables. By default, \(x_0, \ldots, x_{n-1}\)
name	str	optional, default ‘’
properties	dict	stores certain properties of the function as they are computed

print('f.f',f.f)
print('f.n',f.n)
print('f.variables',f.variables)
print('f.name',f.name)
print('f.properties',f.properties)

f.f [0 0 0 1]
f.n 2
f.variables ['x0' 'x1']
f.name f_AND
f.properties {}

Since f was generated from truth table, its variables default to \(x_0, x_1\). On the contrary, generating instances of BooleanFunction from text also provides the variable names. This becomes important when reading from text files entire Boolean networks, i.e., collections of Boolean functions. For example, for f2, f3, g, and h, we have:

print('f2.variables',f2.variables)
print('f3.variables',f3.variables)
print('g.variables',g.variables)
print('h.variables',h.variables)

f2.variables ['A' 'B']
f3.variables ['A' 'B']
g.variables ['A' 'B' 'C']
h.variables ['x' 'y' 'z']

The variable order is determined by the first occurence of the variable in the generating text. See e.g.,

print(boolforge.BooleanFunction('(x + y + z) % 2 == 0').variables)
print(boolforge.BooleanFunction('(y + z + x) % 2 == 0').variables)

['x' 'y' 'z']
['y' 'z' 'x']

Basic properties of Boolean functions

We can inspect various properties of a Boolean function. The degree, i.e., the number of inputs, is readily available via ‘f.n’. Other properties can be computed.

print("Number of variables:", f.n)
print("Is constant?", f.is_constant())
print("Is degenerate?", f.is_degenerate())
print("Indices of essential variables:", f.get_essential_variables())
print("Type of inputs:", f.get_type_of_inputs())
print("Hamming weight:", f.get_hamming_weight())
print("Absolute bias:", f.get_absolute_bias())

Number of variables: 2
Is constant? False
Is degenerated? False
Indices of essential variables: [0, 1]
Type of inputs: ['positive' 'positive']
Hamming weight: 1
Absolute bias: 0.5

Rerunning the above code for g helps understand the different properties.

• ‘g.is_constant()’ checks if the function is constant,

• ‘g.is_degenerate()’ checks if the function contains non-essential variables,

• ‘g.get_essential_variables()’ provides the indices (Python: starting at 0!) of the essential variables,

• ‘g.get_type_of_inputs()’ describes the type of each input (‘increasing’,’decreasing’,’conditional’, or ‘non-essential’).

• The Hamming weight is the number of 1s in the right side of the truth table.

• The absolute bias is 0 if the function is unbiased, i.e., if the number of 0s is equal to the number of 1s, and it is 1 for constant functions.

print("Number of variables:", g.n)
print("Is constant?", g.is_constant())
print("Is degenerate?", g.is_degenerate())
print("Indices of essential variables:", g.get_essential_variables())
print("Type of inputs:", g.get_type_of_inputs())
print("Hamming weight:", g.get_hamming_weight())
print("Absolute bias:", g.get_absolute_bias())

Number of variables: 3
Is constant? False
Is degenerated? False
Indices of essential variables: [0, 1, 2]
Type of inputs: ['positive' 'positive' 'conditional']
Hamming weight: 4
Absolute bias: 0.0

Convert to logical and polynomial expression

While Boolean functions are stored as truth tables, they can be expressed in logical and polynomial format.

print(f"Logical form of {f.name}:", f.to_logical(AND=' ∧ ', OR=' ∨ ', NOT=' ¬'))
print(f"Polynomial form of {f.name}:", f.to_polynomial())

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[13], line 1
----> 1 print(f"Logical form of {f.name}:", f.to_logical(AND=' ∧ ', OR=' ∨ ', NOT=' ¬'))
      2 print(f"Polynomial form of {f.name}:", f.to_polynomial())

AttributeError: 'BooleanFunction' object has no attribute 'to_logical'

In addition, an instance of BooleanFunction can be turned into an instance of BooleanNode from the CANA package. This requires the optional CANA package to be installed.

cana_object = f.to_cana()
print(type(cana_object))

<class 'cana.boolean_node.BooleanNode'>