Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 FindBooleanAlternative

Source Notebook

Find alternative Boolean expressions using a given set of operators

Contributed by: Stephen Wolfram and Nikolay Murzin

ResourceFunction["FindBooleanAlternative"][expr, ops]

finds an alternative expression for a Boolean expression expr in terms of the operators in the list ops.

ResourceFunction["FindBooleanAlternative"][expr, ops, n]

returns up to n alternative expressions.

Details and Options

The default maximum size of an expression to search for is 8, which is controlled by the "MaxSize" option.
If n is set to All, ResourceFunction["FindBooleanAlternative"] returns all alternative expressions up to the specified maximum size of expressions.
Supported Boolean operators include Not, And, Or, Nand, Nor, Xor, Implies and Equivalent.

Examples

Basic Examples (1) 

Find alternative Boolean expressions for Nand and Implies:

In[1]:=
ResourceFunction["FindBooleanAlternative"][Nand[p, q], {And, Or, Not}]
Out[1]=
In[2]:=
ResourceFunction["FindBooleanAlternative"][Implies[p, q], {Nor}]
Out[2]=

Scope (3) 

Find three Boolean alternative expressions for Implies in terms of Nand:

In[3]:=
ResourceFunction["FindBooleanAlternative"][Implies[p, q], {Nand}, 3]
Out[3]=

Find all Boolean alternative expressions:

In[4]:=
ResourceFunction["FindBooleanAlternative"][Implies[p, q], {Nand}, All]
Out[4]=

Express Majority in terms of And and Or:

In[5]:=
ResourceFunction["FindBooleanAlternative"][ Majority[p, q, r], {And, Or}]
Out[5]=

Transform a BooleanFunction:

In[6]:=
ResourceFunction["FindBooleanAlternative"][ BooleanFunction[2, 3], {Not, And}]
Out[6]=

Options (2) 

MaxSize (2) 

The "MaxSize" option specifies the maximum size of expressions to search for (default is 8):

In[7]:=
Length@ResourceFunction["FindBooleanAlternative"][ Implies[p, ! q], {Nor}, All]
Out[7]=

Specify a larger "MaxSize":

In[8]:=
Length@ResourceFunction["FindBooleanAlternative"][ Implies[p, ! q], {Nor}, All, "MaxSize" -> 9]
Out[8]=

Properties and Relations (2) 

FindBooleanAlternative is able to find the same forms of expressions as BooleanConvert:

In[9]:=
BooleanConvert[Nand[p, q], "ANF"]
Out[9]=
In[10]:=
ResourceFunction["FindBooleanAlternative"][Nand[p, q], {And, Not}]
Out[10]=

FindBooleanAlternative is able to find different alternatives, not necessary the canonical one:

In[11]:=
BooleanConvert[Nand[p, q], "CNF"]
Out[11]=
In[12]:=
ResourceFunction["FindBooleanAlternative"][Nand[p, q], {Or, Not}, 5] // Column
Out[12]=

Possible Issues (1) 

For Boolean expressions not representable using a provided set of operators, FindBooleanAlternatives will try to find one until maximum expression size is reached, which may take a long time:

In[13]:=
TimeConstrained[ ResourceFunction["FindBooleanAlternative"][Nand[p, q], {And, Or}], 5]
Out[13]=

Version History

  • 1.0.0 – 25 February 2022

Related Resources

License Information