Built-in Mathematica Symbol

BooleanMinimize

BooleanMinimize[expr]
finds a minimal-length disjunctive normal form representation of expr.

BooleanMinimize[expr, form]
finds a minimal-length representation for expr in the specified form.

BooleanMinimize[expr, form, cond]
finds a minimal-length expression in the specified form that is equivalent to expr when cond is true.

MORE INFORMATION

BooleanMinimize[expr, form] always produces an expression equivalent to expr.

Available forms are:

	"DNF","SOP"	disjunctive normal form, sum of products
	"CNF","POS"	conjunctive normal form, product of sums
	"ANF"	algebraic normal form
	"NOR"	two-level Nor and Not
	"NAND"	two-level Nand and Not
	"AND"	two-level And and Not
	"OR"	two-level Or and Not

In general, there may be several minimal-length representations for a particular expression in a certain form. BooleanMinimize gives one of them.

BooleanMinimize supports a Method option which specifies the detailed method to use.

EXAMPLES

CLOSE ALL

Basic Examples (2)

Find the minimal disjunctive normal form:

A Boolean counting function in disjunctive normal form:

Find a minimal disjunctive normal form:

Find the minimal disjunctive normal form:

In[1]:=

Out[1]=

A Boolean counting function in disjunctive normal form:

In[1]:=

Out[1]=

Find a minimal disjunctive normal form:

In[2]:=

Out[2]=

Scope (2)

A Boolean function of five variables represented in DNF:

Minimal length DNF:

Minimal length CNF:

Minimal length NAND form:

Minimal length NOR form:

Minimal length ANF:

Show that all the forms are equivalent:

Minimize a Boolean function using a "care set" or condition:

The resulting forms are equivalent when cond is true:

They are not equivalent without the condition:

Typically the forms are longer without conditions:

Applications (1)

Compute the minimal DNF representation:

Plot the size as a function of index:

Get its distribution:

Compute the size for the first 1000 four-variable functions:

Properties & Relations (4)

The output from BooleanMinimize is equivalent to its input:

The output from BooleanMinimize with condition is conditionally equivalent to its input:

The forms f and g are equivalent when cond is true:

They are not equivalent on their own:

The minimal lengths "DNF", "CNF", "NAND" or "NOR" are not unique:

BooleanMinimize will produce an expression of length 3:

Another equivalent expression of length 3 is given by exchanging b and c:

Similar examples for "CNF", "NAND" and "NOR":

Use BooleanConvert when the minimal length form is not required:

BooleanConvert can also convert to additional forms: