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.
Details and Options
- 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 that specifies the detailed method to use.
Examples
open all close allBasic Examples (2)
Scope (2)
A Boolean function of five variables represented in DNF:
expr = BooleanCountingFunction[{2, 3}, {a, b, c, d, e}]m1 = BooleanMinimize[expr, "DNF"]{Length[m1], Length[expr]}m2 = BooleanMinimize[expr, "CNF"]m3 = BooleanMinimize[expr, "NAND"]m4 = BooleanMinimize[expr, "NOR"]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"]Applications (1)
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]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]]]]Properties & Relations (4)
The output from BooleanMinimize is equivalent to its input:
f = BooleanFunction[228, {a, b, c}]g = BooleanMinimize[f]TautologyQ[Equivalent[f, g]]The output from 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}]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 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]]BooleanConvert can also convert to additional forms:
BooleanConvert[BooleanCountingFunction[{1, 2}, 3][a, b, c], "Implies"]Text
Wolfram Research (2008), BooleanMinimize, Wolfram Language function, https://reference.wolfram.com/language/ref/BooleanMinimize.html.
CMS
Wolfram Language. 2008. "BooleanMinimize." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/BooleanMinimize.html.
APA
Wolfram Language. (2008). BooleanMinimize. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/BooleanMinimize.html