({{, (RefLink[BooleanMinimize, paclet:ref/BooleanMinimize])[expr] 
finds a minimal-length disjunctive normal form representation of expr.}, {, (RefLink[BooleanMinimize, paclet:ref/BooleanMinimize])[expr,form]
finds a minimal-length representation for expr in the specified form.}, {, (RefLink[BooleanMinimize, paclet:ref/BooleanMinimize])[expr,form,cond]
finds a minimal-length expression in the specified form that is equivalent to expr when cond is true.}})

OpenersNotesSection(Spacer1)Details and Options

(RefLink[BooleanMinimize, paclet:ref/BooleanMinimize])[expr,form] always produces an expression equivalent to expr.

Available forms are:

In general, there may be several minimal-length representations for a particular expression in a certain form. (RefLink[BooleanMinimize, paclet:ref/BooleanMinimize]) gives one of them.

(RefLink[BooleanMinimize, paclet:ref/BooleanMinimize]) supports a (RefLink[Method, paclet:ref/Method]) option that specifies the detailed method to use.

OpenersPrimaryExamplesSection(Spacer1)Examples  (9)

OpenersExampleSection0(Spacer1)Basic Examples  (2)

Find the minimal disjunctive normal form:

BooleanMinimize[a∧b∨¬a∧b]

A Boolean counting function in disjunctive normal form:

BooleanCountingFunction[{2,3},{a,b,c,d}]

Find a minimal disjunctive normal form:

BooleanMinimize[%]

OpenersExampleSection1(Spacer1)Scope  (2)

A Boolean function of five variables represented in DNF:

expr=BooleanCountingFunction[{2,3},{a,b,c,d,e}]

Minimal-length DNF:

m1=BooleanMinimize[expr,"DNF"]

{Length[m1],Length[expr]}

Minimal-length CNF:

m2=BooleanMinimize[expr,"CNF"]

Minimal-length NAND form:

m3=BooleanMinimize[expr,"NAND"]

Minimal-length NOR form:

m4=BooleanMinimize[expr,"NOR"]

Minimal-length ANF:

m5=BooleanMinimize[expr,"ANF"]

Show that all the forms are equivalent:

TautologyQ[Equivalent[expr,m1,m2,m3,m4,m5]]

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

f=BooleanCountingFunction[{2,3},4][a,b,c,d]

cond=Xor[a,b,c,d]

g=BooleanMinimize[f,cond]

h=BooleanMinimize[f,"CNF",cond]

The resulting forms are equivalent when cond is true:

TautologyQ[Implies[cond,Equivalent[f,g,h]]]

They are not equivalent without the condition:

TautologyQ[Equivalent[f,g,h]]

Typically the forms are longer without conditions:

BooleanMinimize[f]

BooleanMinimize[f,"CNF"]

OpenersExampleSection3(Spacer1)Applications  (1)

OpenersExampleSubsection0(Spacer1)Distribution of Minimal Size  (1)

Compute the minimal DNF representation:

size[h_]:=If[Head[h]===Or,Length[h],1]

data=Table[{i,size@BooleanMinimize[BooleanFunction[i,{x,y,z}]]},{i,0,2^2^3-1}];

Plot the size as a function of index:

ListLinePlot[data]

Get its distribution:

ListLinePlot[Tally[data[[All,-1]]]]

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

data=Table[{i,size@BooleanMinimize[BooleanFunction[i,{x,y,z,w}]]},{i,0,999}];

ListLinePlot[data]

ListLinePlot[Tally[data[[All,-1]]]]

OpenersExampleSection4(Spacer1)Properties & Relations  (4)

The output from (RefLink[BooleanMinimize, paclet:ref/BooleanMinimize]) is equivalent to its input:

f=BooleanFunction[228,{a,b,c}]

g=BooleanMinimize[f]

TautologyQ[Equivalent[f,g]]

The output from (RefLink[BooleanMinimize, paclet:ref/BooleanMinimize]) with condition is conditionally equivalent to its input:

f=BooleanFunction[158,{a,b,c}]

cond=a||b||c;

g=BooleanMinimize[f,"DNF",cond]

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

TautologyQ[Implies[cond,Equivalent[f,g]]]

They are not equivalent on their own:

TautologyQ[Equivalent[f,g]]

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

e=BooleanCountingFunction[{1,2},{a,b,c}]

(RefLink[BooleanMinimize, paclet:ref/BooleanMinimize]) will produce an expression of length 3:

f=BooleanMinimize[e]

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

g=f/.{b->c,c->b}

TautologyQ[Equivalent[f,g]]

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

{f=BooleanMinimize[Not[e],"CNF"],g=f/.{b->c,c->b},TautologyQ[Equivalent[f,g]]}

{f=BooleanMinimize[e,"NAND"],g=f/.{b->c,c->b},TautologyQ[Equivalent[f,g]]}

{f=BooleanMinimize[Not[e],"NOR"],g=f/.{b->c,c->b},TautologyQ[Equivalent[f,g]]}

Use (RefLink[BooleanConvert, paclet:ref/BooleanConvert]) when the minimal length form is not required:

BooleanConvert[BooleanCountingFunction[{1,2},3][a,b,c]]

BooleanMinimize[BooleanCountingFunction[{1,2},3][a,b,c]]

(RefLink[BooleanConvert, paclet:ref/BooleanConvert]) can also convert to additional forms:

BooleanConvert[BooleanCountingFunction[{1,2},3][a,b,c],"Implies"]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[BooleanConvert, paclet:ref/BooleanConvert])  ▪  (RefLink[FullSimplify, paclet:ref/FullSimplify])  ▪  (RefLink[BooleanCountingFunction, paclet:ref/BooleanCountingFunction])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Boolean Computation, paclet:guide/BooleanComputation])}, {▪(RefLinkPlain[Algebraic Transformations, paclet:guide/AlgebraicTransformations])}, {▪(RefLinkPlain[Logic & Boolean Algebra, paclet:guide/LogicAndBooleanAlgebra])}, {▪(RefLinkPlain[Discrete Mathematics, paclet:guide/DiscreteMathematics])}})}})