WOLFRAM

Wolfram Language & System Documentation Center
Wolfram Language Home Page »

BooleanMinimize
✖
BooleanMinimize

✖

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 allclose all

Basic Examples  (2)Summary of the most common use cases

Find the minimal disjunctive normal form:

In[1]:=1
✖
https://wolfram.com/xid/0n4uf2pv9lm-dfe0db
Out[1]=1

A Boolean counting function in disjunctive normal form:

In[1]:=1
✖
https://wolfram.com/xid/0n4uf2pv9lm-k9rnoy
Out[1]=1

Find a minimal disjunctive normal form:

In[2]:=2
✖
https://wolfram.com/xid/0n4uf2pv9lm-c1dwp6
Out[2]=2

Scope  (2)Survey of the scope of standard use cases

A Boolean function of five variables represented in DNF:

In[1]:=1
✖
https://wolfram.com/xid/0n4uf2pv9lm-qtk6f4
Out[1]=1

Minimal-length DNF:

In[2]:=2
✖
https://wolfram.com/xid/0n4uf2pv9lm-uem3e
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0n4uf2pv9lm-b2uhck
Out[3]=3

Minimal-length CNF:

In[4]:=4
✖
https://wolfram.com/xid/0n4uf2pv9lm-kaaiam
Out[4]=4

Minimal-length NAND form:

In[5]:=5
✖
https://wolfram.com/xid/0n4uf2pv9lm-bmu9m
Out[5]=5

Minimal-length NOR form:

In[6]:=6
✖
https://wolfram.com/xid/0n4uf2pv9lm-fhbshf
Out[6]=6

Minimal-length ANF:

In[7]:=7
✖
https://wolfram.com/xid/0n4uf2pv9lm-cqtm3d
Out[7]=7

Show that all the forms are equivalent:

In[8]:=8
✖
https://wolfram.com/xid/0n4uf2pv9lm-jgvn56
Out[8]=8

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

In[1]:=1
✖
https://wolfram.com/xid/0n4uf2pv9lm-gf665x
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0n4uf2pv9lm-sl2ga
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0n4uf2pv9lm-wcxnn
Out[3]=3
In[4]:=4
✖
https://wolfram.com/xid/0n4uf2pv9lm-fi8llh
Out[4]=4

The resulting forms are equivalent when cond is true:

In[5]:=5
✖
https://wolfram.com/xid/0n4uf2pv9lm-eclid5
Out[5]=5

They are not equivalent without the condition:

In[6]:=6
✖
https://wolfram.com/xid/0n4uf2pv9lm-hpcajv
Out[6]=6

Typically the forms are longer without conditions:

In[7]:=7
✖
https://wolfram.com/xid/0n4uf2pv9lm-hzerfn
Out[7]=7
In[8]:=8
✖
https://wolfram.com/xid/0n4uf2pv9lm-dgi52e
Out[8]=8

Applications  (1)Sample problems that can be solved with this function

Distribution of Minimal Size  (1)

Compute the minimal DNF representation:

In[1]:=1
✖
https://wolfram.com/xid/0n4uf2pv9lm-dvc206
In[2]:=2
✖
https://wolfram.com/xid/0n4uf2pv9lm-b5casr

Plot the size as a function of index:

In[3]:=3
✖
https://wolfram.com/xid/0n4uf2pv9lm-e8exij
Out[3]=3

Get its distribution:

In[4]:=4
✖
https://wolfram.com/xid/0n4uf2pv9lm-fy7gg2
Out[4]=4

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

In[5]:=5
✖
https://wolfram.com/xid/0n4uf2pv9lm-ferrtc
In[6]:=6
✖
https://wolfram.com/xid/0n4uf2pv9lm-ed3hut
Out[6]=6
In[7]:=7
✖
https://wolfram.com/xid/0n4uf2pv9lm-ct3953
Out[7]=7

Properties & Relations  (4)Properties of the function, and connections to other functions

The output from BooleanMinimize is equivalent to its input:

In[1]:=1
✖
https://wolfram.com/xid/0n4uf2pv9lm-bky3nb
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0n4uf2pv9lm-qitwn
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0n4uf2pv9lm-bjs0y1
Out[3]=3

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

In[1]:=1
✖
https://wolfram.com/xid/0n4uf2pv9lm-gmbo7y
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0n4uf2pv9lm-g7x2t
In[3]:=3
✖
https://wolfram.com/xid/0n4uf2pv9lm-6w4ro
Out[3]=3

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

In[4]:=4
✖
https://wolfram.com/xid/0n4uf2pv9lm-m7i4l
Out[4]=4

They are not equivalent on their own:

In[5]:=5
✖
https://wolfram.com/xid/0n4uf2pv9lm-kydu5
Out[5]=5

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

In[1]:=1
✖
https://wolfram.com/xid/0n4uf2pv9lm-20ws
Out[1]=1

BooleanMinimize will produce an expression of length 3:

In[2]:=2
✖
https://wolfram.com/xid/0n4uf2pv9lm-kae824
Out[2]=2

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

In[3]:=3
✖
https://wolfram.com/xid/0n4uf2pv9lm-dbkter
Out[3]=3
In[4]:=4
✖
https://wolfram.com/xid/0n4uf2pv9lm-teehh
Out[4]=4

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

In[5]:=5
✖
https://wolfram.com/xid/0n4uf2pv9lm-dau3m9
Out[5]=5
In[6]:=6
✖
https://wolfram.com/xid/0n4uf2pv9lm-j1xxhm
Out[6]=6
In[7]:=7
✖
https://wolfram.com/xid/0n4uf2pv9lm-ejjvk
Out[7]=7

Use BooleanConvert when the minimal length form is not required:

In[1]:=1
✖
https://wolfram.com/xid/0n4uf2pv9lm-fr8ncb
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0n4uf2pv9lm-geoabe
Out[2]=2

BooleanConvert can also convert to additional forms:

In[3]:=3
✖
https://wolfram.com/xid/0n4uf2pv9lm-f2nes
Out[3]=3
Wolfram Research (2008), BooleanMinimize, Wolfram Language function, https://reference.wolfram.com/language/ref/BooleanMinimize.html.
✖
Wolfram Research (2008), BooleanMinimize, Wolfram Language function, https://reference.wolfram.com/language/ref/BooleanMinimize.html.

Text

Wolfram Research (2008), BooleanMinimize, Wolfram Language function, https://reference.wolfram.com/language/ref/BooleanMinimize.html.

✖
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.

✖
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

✖
Wolfram Language. (2008). BooleanMinimize. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/BooleanMinimize.html

BibTeX

@misc{reference.wolfram_2025_booleanminimize, author="Wolfram Research", title="{BooleanMinimize}", year="2008", howpublished="\url{https://reference.wolfram.com/language/ref/BooleanMinimize.html}", note=[Accessed: 15-April-2025 ]}

✖
@misc{reference.wolfram_2025_booleanminimize, author="Wolfram Research", title="{BooleanMinimize}", year="2008", howpublished="\url{https://reference.wolfram.com/language/ref/BooleanMinimize.html}", note=[Accessed: 15-April-2025 ]}

BibLaTeX

@online{reference.wolfram_2025_booleanminimize, organization={Wolfram Research}, title={BooleanMinimize}, year={2008}, url={https://reference.wolfram.com/language/ref/BooleanMinimize.html}, note=[Accessed: 15-April-2025 ]}

✖
@online{reference.wolfram_2025_booleanminimize, organization={Wolfram Research}, title={BooleanMinimize}, year={2008}, url={https://reference.wolfram.com/language/ref/BooleanMinimize.html}, note=[Accessed: 15-April-2025 ]}