Discrete helpers/boolf

Studies of Boolean functions

boolf

This class for Boolean functions (BF) is the biggest part of this software.
It contains some unfinished and experimental features.

This project is related to many pages in Studies of Boolean functions.

There are two main goals, both not yet reached:

• find the Euler diagram of any BF, see Studies of Euler diagrams   (The main problem is to find the necessary gapspots.)
• find an easy to calculate clan representative of any BF, e.g. the Smallest Zhegalkin index   (The current calculation of the smallest Ж is not yet easy.)

from discretehelpers.boolf import Boolf


a = Boolf('0101')
b = Boolf('0011')

assert a == Boolf('01')
assert b == Boolf('01', [1])

assert a & b == Boolf('0001')  # AND
assert a | b == Boolf('0111')  # OR
assert a ^ b == Boolf('0110')  # XOR

assert ~a == Boolf('10')  # NOT
assert ~(a&b) == Boolf('1110')

some equivalent instantiations

assert Boolf('0000') == Boolf('0') == Boolf('0', []) == Boolf(False) assert Boolf('1111') == Boolf('1') == Boolf('1', []) == Boolf(True) assert Boolf('0101') == Boolf('01') == Boolf('01', [0]) == Boolf(atom=0) assert Boolf('1010') == Boolf('10') == Boolf('10', [0]) == Boolf(atom=~0) assert Boolf('0011') == Boolf('01', [1]) == Boolf(atom=1) assert Boolf('1100') == Boolf('10', [1]) == Boolf(atom=~1) assert Boolf('0001') == Boolf('0001', [0, 1]) == Boolf(multi_and=[0, 1]) assert Boolf('0111') == Boolf('0111', [0, 1]) == Boolf(multi_or=[0, 1]) assert Boolf('1001') == Boolf('1001', [0, 1]) == Boolf(multi_xand=[0, 1]) assert Boolf('0110') == Boolf('0110', [0, 1]) == Boolf(multi_xor=[0, 1]) assert Boolf('0101 1010') == Boolf('0110', [0, 2]) assert Boolf('0101 1111') == Boolf('0111', [0, 2]) == Boolf(multi_or=[0, 2]) assert Boolf('1111 0101') == Boolf('1101', [0, 2]) == Boolf(multi_or=[0, ~2])

periodic truth tables

Within this project Boolean functions are used without specifying the arity.
Their arity is implicitly infinite, and their truth tables are implicitly periodic.   (But the term truth table is usually used for finite ones.)
They are repeating binary fractions (just like repeating decimals) with values between 0 and 1.   (This may be the only occurence of big-endian binary in this project.)

The truth tables 0001 and 0001 0001 denote the same thing, namely the Boolean function $A\land B$.
The corresponding fraction is ${\frac {1}{15}}$. (That can be expanded to ${\frac {17}{255}}$, corresponding to the longer truth table.)

The letters from the beginning of the alphabet are not meaningless variable names, but denote specific atoms.

atom fractions

${\begin{matrix}A&=&x_{0}&=&{\frac {1}{3}}&=&.0101010101010101...\\B&=&x_{1}&=&{\frac {1}{5}}&=&.0011001100110011...\\C&=&x_{2}&=&{\frac {1}{17}}&=&.0000111100001111...\\D&=&x_{3}&=&{\frac {1}{257}}&=&.0000000011111111...\\&&x_{n}&=&{\frac {1}{2^{2^{n}}+1}}\end{matrix}}$ from fractions import Fraction assert Boolf(atom=0).value_fract() == Fraction(1, 3) assert Boolf(atom=1).value_fract() == Fraction(1, 5) assert Boolf(atom=2).value_fract() == Fraction(1, 17) assert Boolf(atom=3).value_fract() == Fraction(1, 257) negations ${\begin{matrix}\neg A&=&\neg x_{0}&=&{\frac {2}{3}}&=&.1010101010101010...\\\neg B&=&\neg x_{1}&=&{\frac {4}{5}}&=&.1100110011001100...\\\neg C&=&\neg x_{2}&=&{\frac {16}{17}}&=&.1111000011110000...\\\neg D&=&\neg x_{3}&=&{\frac {256}{257}}&=&.1111111100000000...\\&&\neg x_{n}&=&{\frac {2^{2^{n}}}{2^{2^{n}}+1}}\end{matrix}}$ assert Boolf(atom=~0).value_fract() == Fraction(2, 3) assert Boolf(atom=~1).value_fract() == Fraction(4, 5) assert Boolf(atom=~2).value_fract() == Fraction(16, 17) assert Boolf(atom=~3).value_fract() == Fraction(256, 257)

valency ≤ adicity ≤ arity

Valency is the number of arguments actually used.
Adicity follows from the biggest atom, and corresponds to the required length of the truth table.
For a root BF valency and adicity are equal. E.g. Boolf('0001') ($A\land B$) has valency and adicity 2.
But Boolf('0000 0011') ($B\land C$) has valency 2 and adicity 3.
The term arity is only used for arguments of methods, e.g. to calculate the consul.

boolf = Boolf('0000 0011')
assert boolf == Boolf('0001', [1, 2])

assert boolf.valency == 2
assert boolf.adicity == 3

assert boolf.consul(3) == 1  # arity 3
assert boolf.consul(4) == 0  # arity 4