({{, (RefLink[BooleanFunction, paclet:ref/BooleanFunction])[k,n]
represents the k(^th) Boolean function in n variables.}, {, (RefLink[BooleanFunction, paclet:ref/BooleanFunction])[values]
represents the Boolean function corresponding to the specified vector of truth values.}, {, (RefLink[BooleanFunction, paclet:ref/BooleanFunction])[{{(Subscript[i, 11]),(Subscript[i, 12]),…}->(Subscript[o, 1]),…}]
represents the Boolean function defined by the specified mapping from inputs to outputs.}, {, (RefLink[BooleanFunction, paclet:ref/BooleanFunction])[spec,{(Subscript[a, 1]),(Subscript[a, 2]),…}]
gives the Boolean expression in variables (Subscript[a, i]) corresponding to the Boolean function specified by spec.}, {, (RefLink[BooleanFunction, paclet:ref/BooleanFunction])[spec,{(Subscript[a, 1]),(Subscript[a, 2]),…},form]
gives the Boolean expression in the form specified by form.}})

OpenersNotesSection(Spacer1)Details

(RefLink[BooleanFunction, paclet:ref/BooleanFunction])[spec] gives a Boolean function object that works like (RefLink[Function, paclet:ref/Function]).

(RefLink[BooleanFunction, paclet:ref/BooleanFunction])[spec][(Subscript[a, 1]),(Subscript[a, 2]),…] gives an implicit representation equivalent to the explicit Boolean expression (RefLink[BooleanFunction, paclet:ref/BooleanFunction])[spec,{(Subscript[a, 1]),(Subscript[a, 2]),…}].

(RefLink[BooleanConvert, paclet:ref/BooleanConvert]) converts (RefLink[BooleanFunction, paclet:ref/BooleanFunction])[spec][vars] to an explicit Boolean expression.

In (RefLink[BooleanFunction, paclet:ref/BooleanFunction])[values] etc., values can be specified either as (RefLink[True, paclet:ref/True]) and (RefLink[False, paclet:ref/False]) or as 1 and 0.

The functions represented by (RefLink[BooleanFunction, paclet:ref/BooleanFunction]) always return (RefLink[True, paclet:ref/True]) or (RefLink[False, paclet:ref/False]).

In (RefLink[BooleanFunction, paclet:ref/BooleanFunction])[values], the values are specified in binary order starting with 111, ….

(RefLink[BooleanFunction, paclet:ref/BooleanFunction])[k,n] is equivalent to (RefLink[BooleanFunction, paclet:ref/BooleanFunction])[(RefLink[IntegerDigits, paclet:ref/IntegerDigits])[k,2,2^n]].

In (RefLink[BooleanFunction, paclet:ref/BooleanFunction])[values], each value can be a list, representing a vector-valued Boolean function.

In (RefLink[BooleanFunction, paclet:ref/BooleanFunction])[{{(Subscript[i, 11]),(Subscript[i, 12]),…}->(Subscript[o, 1]),…}] the (Subscript[o, i]) can be lists, representing vector-valued Boolean functions.

Elements of both inputs and outputs can be specified either as (RefLink[True, paclet:ref/True]) and (RefLink[False, paclet:ref/False]) or as 1 and 0.

Elements of inputs and outputs can also include any number of _, representing "don't cares".

They can also include up to one __, representing a sequence of "don't cares".

In (RefLink[BooleanFunction, paclet:ref/BooleanFunction])[spec,{(Subscript[a, 1]),(Subscript[a, 2]),…},form], the possible forms are as given for (RefLink[BooleanConvert, paclet:ref/BooleanConvert]).

(RefLink[BooleanFunction, paclet:ref/BooleanFunction])[spec,{(Subscript[a, 1]),(Subscript[a, 2]),…}] by default gives an expression in DNF.

(RefLink[BooleanFunction, paclet:ref/BooleanFunction])[k] gives the k(^th) Boolean function in n variables, where n has the smallest value for which k<(2^(2^n)).

The numbering of Boolean functions in (RefLink[BooleanFunction, paclet:ref/BooleanFunction])[k,…] is consistent with (RefLink[CellularAutomaton, paclet:ref/CellularAutomaton]).

(RefLink[BooleanFunction, paclet:ref/BooleanFunction])[(RefLink[CellularAutomaton, paclet:ref/CellularAutomaton])[n]] is equivalent to (RefLink[BooleanFunction, paclet:ref/BooleanFunction])[n,3].

(RefLink[BooleanFunction, paclet:ref/BooleanFunction])[(RefLink[CellularAutomaton, paclet:ref/CellularAutomaton])[{n,2,r}]] is equivalent to (RefLink[BooleanFunction, paclet:ref/BooleanFunction])[n,2r+1].

Operations such as (RefLink[BooleanMinimize, paclet:ref/BooleanMinimize]), (RefLink[BooleanTable, paclet:ref/BooleanTable]), etc. can operate directly on (RefLink[BooleanFunction, paclet:ref/BooleanFunction]) objects.

(RefLink[BooleanFunction, paclet:ref/BooleanFunction]) objects can be applied to variables just like other Boolean functions such as (RefLink[And, paclet:ref/And]), (RefLink[Or, paclet:ref/Or]), etc.

In (RefLink[StandardForm, paclet:ref/StandardForm]) and related formats, (RefLink[BooleanFunction, paclet:ref/BooleanFunction]) objects are printed in elided form, with only their number of variables displayed.

(RefLink[BooleanVariables, paclet:ref/BooleanVariables]) gives the number of variables of a (RefLink[BooleanFunction, paclet:ref/BooleanFunction]) object.

OpenersPrimaryExamplesSection(Spacer1)Examples  (28)

OpenersExampleSection0(Spacer1)Basic Examples  (3)

Generate the 30(^th) Boolean function of 3 variables:

f=BooleanFunction[30,3]

Use f like any other Boolean operator:

f[True,False,True]

Convert to a DNF expression:

BooleanConvert[f[x,y,z],"DNF"]

Generate the formula directly:

BooleanFunction[30,{x,y,z}]

Specify a Boolean function based on a table of truth rules:

BooleanFunction[{{False,False}->True,{False,True}->False,{True,False}->True,{True,True}->True},{x,y}]

Use an incompletely specified truth table:

BooleanFunction[{{True,True,False}->True,{False,__}->False},{x,y,z}]

Convert a Boolean expression to a (RefLink[BooleanFunction, paclet:ref/BooleanFunction]):

f=BooleanConvert[Xor[x,y,z],"BooleanFunction"]

Test that they represent the same function:

BooleanTable[{f,Xor[x,y,z]},{x,y,z}]

OpenersExampleSection1(Spacer1)Scope  (14)

OpenersExampleSubsection0(Spacer1)Basic Uses  (3)

Create a (RefLink[BooleanFunction, paclet:ref/BooleanFunction]) with two arguments by indexing:

f=BooleanFunction[11,2]

Compute its value for particular arguments:

f[False,True]

The function remains unevaluated for symbolic arguments:

f[x,y]

(RefLink[BooleanFunction, paclet:ref/BooleanFunction]) can be used just like any other Boolean operator:

FindInstance[f[x,y],{x,y},Booleans]

RegionPlot[f[x^2+y<1,x-y^2>0],{x,-2,2},{y,-2,2}]

Integrate[Boole[f[x^2+y<1,x-y^2>0]],{x,0,2},{y,0,2}]

Reduce[f[x+y<1,x+y^2>0],{x,y}]

Sum[Boole[f[x^2+y<1,x-y^2>0]],{x,0,10},{y,0,10}]

Any Boolean expression can be converted to a (RefLink[BooleanFunction, paclet:ref/BooleanFunction]) expression:

BooleanConvert[x&&(y||z),"BFF"]

Including combinations of (RefLink[BooleanFunction, paclet:ref/BooleanFunction]) expressions:

BooleanConvert[f[%,w],"BFF"]

A (RefLink[BooleanFunction, paclet:ref/BooleanFunction]) expression that is equivalent to (RefLink[True, paclet:ref/True]) or (RefLink[False, paclet:ref/False]) automatically simplifies:

{g,h}={BooleanFunction[0,10],BooleanFunction[2^2^10-1,10]}

g@@Array[x,10]

h@@Array[x,10]

(RefLink[BooleanFunction, paclet:ref/BooleanFunction]) is a canonical representation, and equivalence can be tested using (RefLink[SameQ, paclet:ref/SameQ]):

g=BooleanConvert[a&&b,"BFF"]

h=BooleanConvert[x&&y,"BFF"]

Head[g]===Head[h]

OpenersExampleSubsection1(Spacer1)Working with Truth Tables  (7)

Create a truth table in standard order:

f1=x&&(y||z);

t1=BooleanTable[f1,{x,y,z}]

Create an equivalent (RefLink[BooleanFunction, paclet:ref/BooleanFunction]) expression:

f2=BooleanFunction[t1][x,y,z]

Show that they are equivalent:

TautologyQ[Equivalent[f1,f2]]

Alternatively, show that the resulting truth tables are the same:

t2=BooleanTable[f2,{x,y,z}]

t1===t2

Create a complete list of truth rules:

f1=x&&(y||z);

t1=BooleanTable[{x,y,z}->f1,{x,y,z}]

Create the corresponding (RefLink[BooleanFunction, paclet:ref/BooleanFunction]) expression:

f2=BooleanFunction[t1][x,y,z]

The ordering of truth rules for complete lists has no effect:

f3=BooleanFunction[Reverse[t1]][x,y,z]

TautologyQ[Equivalent[f1,f2,f3]]

Use _ to indicate "don't cares" in a truth table:

t1={False,_,_,True};

Create a (RefLink[BooleanFunction, paclet:ref/BooleanFunction]):

f1=BooleanFunction[t1][x,y]

The resulting truth table matches the original specification:

t2=BooleanTable[f1,{x,y}]

MatchQ[t2,t1]

Use _ and __ to indicate "don't cares" in truth rules:

r1={{True,True,_}->True,{__}->False};

Create a (RefLink[BooleanFunction, paclet:ref/BooleanFunction]):

f1=BooleanFunction[r1][x,y,z]

r2=BooleanTable[{x,y,z}->f1,{x,y,z}]

The original rules completely specify the function and the resulting truth tables are identical:

Replace[Tuples[{True,False},3],r1,{1}]

Replace[Tuples[{True,False},3],r2,{1}]

Use lists of lists to indicate a vector-valued truth table:

t1={{True,False},{__},{_,False},{False,True}};

Create a (RefLink[BooleanFunction, paclet:ref/BooleanFunction]):

f1=BooleanFunction[t1][x,y]

The resulting output matches the original specification:

t2=BooleanTable[f1,{x,y}]

MatchQ[t2,t1]

Use vector-valued truth rules:

r1={{True,True,False}->{False,True},{False,__}->{True,False}};

Create a (RefLink[BooleanFunction, paclet:ref/BooleanFunction]):

f1=BooleanFunction[r1][x,y,z]

r2=BooleanTable[{x,y,z}->f1,{x,y,z}]

The resulting truth rules match the original specification:

t1=Replace[Tuples[{True,False},3],Append[r1,_->_],{1}]

t2=Replace[Tuples[{True,False},3],r2,{1}]

MatchQ[t2,t1]

Truth tables can also be given using 0 in place of (RefLink[False, paclet:ref/False]) and 1 in place of (RefLink[True, paclet:ref/True]):

t1=RandomInteger[{0,1},8]

f=BooleanFunction[t1][x,y,z]

t2=Boole@BooleanTable[f,{x,y,z}]

The resulting truth tables are identical:

t1===t2

OpenersExampleSubsection2(Spacer1)Working with Other Representations  (4)

Convert any Boolean expression to a (RefLink[BooleanFunction, paclet:ref/BooleanFunction]) expression:

f1=Nand[Nor[x,y],Xor[y,z]];

f2=BooleanConvert[f1,"BFF"]

Show that they are equivalent:

TautologyQ[Equivalent[f1,f2]]

Convert expressions involving any Boolean operators:

f1=BooleanMinterms[{1,4,7},3][x,BooleanFunction[110,3][x,y,z],BooleanCountingFunction[{3,5},5][x,y,x,y,z]]

f2=BooleanConvert[f1,"BFF"]

Show that they are equivalent:

TautologyQ[Equivalent[f1,f2]]

Convert a (RefLink[BooleanFunction, paclet:ref/BooleanFunction]) expression to other standard forms:

f=BooleanFunction[123,3][x,y,z]

A number of different standard forms:

BooleanConvert[f,"DNF"]

BooleanConvert[f,"CNF"]

BooleanConvert[f,"ANF"]

BooleanConvert[f,"NAND"]

BooleanConvert[f,"NOR"]

BooleanConvert[f,"Implies"]

As well as a truth table:

BooleanTable[f,{x,y,z}]

Or truth rules:

BooleanTable[{x,y,z}->f,{x,y,z}]

Specify (RefLink[BooleanFunction, paclet:ref/BooleanFunction]) using (RefLink[CellularAutomaton, paclet:ref/CellularAutomaton]):

BooleanFunction[CellularAutomaton[77]]

%===BooleanFunction[77,3]

BooleanFunction[CellularAutomaton[{123,2,7/2}]]

%===BooleanFunction[123,2 7/2+1]

OpenersExampleSection3(Spacer1)Applications  (4)

OpenersExampleSubsection3(Spacer1)Enumerating Boolean Functions  (2)

Enumerate all 2-variable Boolean functions:

Table[ArrayPlot[BooleanTable[BooleanFunction[i,2][x,y],{x},{y}],ColorRules->{False->White,True->Black},ImageSize->15,PlotLabel->Style[i,Small]],{i,0,15}]

All 3-variable Boolean functions:

Table[ArrayPlot[BooleanTable[BooleanFunction[i,3][x,y,z],{x},{y,z}],ColorRules->{False->White,True->Black},ImageSize->25,PlotLabel->Style[i,Small]],{i,0,255}]

Randomly sample 50 functions of 4 variables:

Table[ArrayPlot[BooleanTable[BooleanFunction[i,4][x,y,z,w],{x,y},{z,w}],ColorRules->{False->White,True->Black},ImageSize->30,PlotLabel->Style[i,Small]],{i,RandomInteger[{0,2^2^4-1},50]}]

Compare the sizes of Boolean functions in their standard and minimized forms:

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

Three variables:

Tally@Table[size@BooleanFunction[i,{x,y,z}],{i,0,2^2^3-1}]

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

ListLinePlot[{%%,%}]

Four variables, the first 1000 functions:

Tally@Table[size@BooleanFunction[i,{x,y,z,w}],{i,0,1000}]

Tally@Table[size@BooleanMinimize[BooleanFunction[i,{x,y,z,w}]],{i,0,1000}]

ListLinePlot[{%%,%}]

OpenersExampleSubsection4(Spacer1)Creating New Primitives  (1)

Create new Boolean primitives corresponding to ≤, ≥, <, and >:

BooleanLessEqual=BooleanFunction[{{0,0}->1,{0,1}->1,{1,0}->0,{1,1}->1}];

BooleanGreaterEqual=BooleanFunction[{{0,0}->1,{0,1}->0,{1,0}->1,{1,1}->1}];

BooleanLess=BooleanFunction[{{0,0}->0,{0,1}->1,{1,0}->0,{1,1}->0}];

BooleanGreater=BooleanFunction[{{0,0}->0,{0,1}->0,{1,0}->1,{1,1}->0}];

These are closely related:

TautologyQ[Equivalent[Not[BooleanLessEqual[x,y]],BooleanGreater[x,y]]]

TautologyQ[Equivalent[Not[BooleanGreaterEqual[x,y]],BooleanLess[x,y]]]

(RefLink[Implies, paclet:ref/Implies]) is equivalent to x<=y:

TautologyQ[Equivalent[BooleanLessEqual[x,y],Implies[x,y]]]

Define a relation for Boolean functions f≼g iff (Underscript[∧, u∈(𝔹^n)])f[u]≤g[u]:

Conjunction[BooleanLessEqual[x,x∨y],{x,y}]

Here you have x≼x∨y as reflected in the truth tables:

BooleanTable[{x,x∨y},{x,y}]

BooleanLessEqual@@@%

Using standard inequalities:

Boole@BooleanTable[{x,x∨y},{x,y}]

LessEqual@@@%

For all Boolean functions f and g, f∧g≼f≼f∨g:

Conjunction[BooleanLessEqual[f∧g,f],{f,g}]

Conjunction[BooleanLessEqual[f,f∨g],{f,g}]

This proves that f≼g iff f∧g⇔f:

TautologyQ[Equivalent[BooleanLessEqual[f,g],Equivalent[f∧g,f]]]

And similarly f≼g iff f∨g⇔g:

TautologyQ[Equivalent[BooleanLessEqual[f,g],Equivalent[f∨g,g]]]

Or that f≼g and g≼h implies f≼h:

TautologyQ[Implies[BooleanLessEqual[f,g]∧BooleanLessEqual[g,h],BooleanLessEqual[f,h]]]

OpenersExampleSubsection5(Spacer1)Cellular Automata  (1)

Generate the rule 30 elementary cellular automaton rule:

f=Function[{v,i},BooleanFunction[30,3]@@v]

Simulate it:

CellularAutomaton[{f,{},1},{False,False,True,False,False},2]

Compare to the standard encoding:

Boole[%]

CellularAutomaton[30,{0,0,1,0,0},2]

OpenersExampleSection4(Spacer1)Properties & Relations  (7)

(RefLink[BooleanFunction, paclet:ref/BooleanFunction]) displays in an elided form indicating the number of arguments:

f=BooleanFunction[30,3]

It is an atomic object:

{AtomQ[f],Length[f]}

The (RefLink[InputForm, paclet:ref/InputForm]) gives an encoding that can be used to reconstruct the object:

InputForm[f]

Use the encoding to construct a (RefLink[BooleanFunction, paclet:ref/BooleanFunction]):

g=BooleanFunction["BDD"->{-3,0,2,-2,1,1,3,2,1,-1}]

The result is identical to the original:

f===g

The order of values for (RefLink[BooleanFunction, paclet:ref/BooleanFunction]) is the same as (RefLink[BooleanTable, paclet:ref/BooleanTable]):

t1=BooleanTable[Xor[x,y],{x,y}]

The corresponding (RefLink[BooleanFunction, paclet:ref/BooleanFunction]) has an identical truth table:

f=BooleanFunction[t1]

BooleanTable[f[x,y],{x,y}]

The ordering is consistent with (RefLink[Tuples, paclet:ref/Tuples]):

f@@@Tuples[{True,False},2]

Indexing of (RefLink[BooleanFunction, paclet:ref/BooleanFunction]) is consistent with (RefLink[IntegerDigits, paclet:ref/IntegerDigits]):

With[{m=1234,k=5},BooleanFunction[m,k]===BooleanFunction[IntegerDigits[m,2,2^k]]]

Convert from a (RefLink[BooleanFunction, paclet:ref/BooleanFunction]) to its index:

f=BooleanFunction[1234,5]

FromDigits[Boole@BooleanTable[f],2]

Convert from any Boolean expression to its index:

FromDigits[Boole@BooleanTable[Xor[x,y,x||z],{x,y,z}],2]

Show that it is equivalent with the indexed (RefLink[BooleanFunction, paclet:ref/BooleanFunction]) expression:

TautologyQ[Equivalent[BooleanFunction[%,3][x,y,z],Xor[x,y,x||z]]]

The indexing of Boolean functions agrees with the indexing of cellular automata:

CellularAutomaton[30,#][[2]]&/@Tuples[{1,0},3]

Boole@BooleanTable[BooleanFunction[30,3]]

More generally, for (RefLink[CellularAutomaton, paclet:ref/CellularAutomaton])[{k,2,r}] with integer k and 2 r, the relation reads:

With[{k=123,r=5/2},CellularAutomaton[{k,2,r},#][[Ceiling[r]+1]]&/@Tuples[{1,0},2r+1]===Boole@BooleanTable[BooleanFunction[k,2r+1]]]

(RefLink[CellularAutomaton, paclet:ref/CellularAutomaton]) satisfying the preceding properties can be used to specify (RefLink[BooleanFunction, paclet:ref/BooleanFunction]):

BooleanFunction[CellularAutomaton[30]]===BooleanFunction[30,3]

BooleanFunction[CellularAutomaton[{123,2,5/2}]]===BooleanFunction[123,6]

(RefLink[BooleanMinterms, paclet:ref/BooleanMinterms]) can also represent any (RefLink[BooleanFunction, paclet:ref/BooleanFunction]):

f1=BooleanMinterms[{1,5,7},3]

f2=BooleanFunction[FromDigits[{1,0,1,0,0,0,1,0},2],3]

f1===f2

The mapping from minterms to index:

mindex[l_,k_]:=FromDigits[Table[If[MemberQ[l,i],1,0],{i,2^k-1,0,-1}],2]

mindex[{1,5,7},3]

The mapping from index to minterms:

indmin[m_,k_]:=Flatten@Position[Reverse[IntegerDigits[m,2,2^k]],1]-1

indmin[162,3]

Using bit vectors:

With[{m=123,k=4},BooleanMinterms[Select[Range[0,(2^k)-1],BitAnd[(2^(#)),m]≠0&],k]===BooleanFunction[m,k]]

Use (RefLink[BooleanConvert, paclet:ref/BooleanConvert]) to convert to (RefLink[BooleanFunction, paclet:ref/BooleanFunction]) from other forms:

f1=Xor[x,y&&z];

f2=BooleanConvert[f1,"BFF"]

Also use (RefLink[BooleanConvert, paclet:ref/BooleanConvert]) to convert from (RefLink[BooleanFunction, paclet:ref/BooleanFunction]) to other forms:

f3=BooleanConvert[f2,"NAND"]

Show that they are all equivalent:

TautologyQ[Equivalent[f1,f2,f3]]

Use (RefLink[BooleanTable, paclet:ref/BooleanTable]) to convert (RefLink[BooleanFunction, paclet:ref/BooleanFunction]) to truth tables:

f=BooleanFunction[23,3]

BooleanTable[f]

Or convert to truth rules:

BooleanTable[{x,y,z}->f[x,y,z],{x,y,z}]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[BooleanMinterms, paclet:ref/BooleanMinterms])  ▪  (RefLink[BooleanMaxterms, paclet:ref/BooleanMaxterms])  ▪  (RefLink[BooleanCountingFunction, paclet:ref/BooleanCountingFunction])  ▪  (RefLink[BooleanConsecutiveFunction, paclet:ref/BooleanConsecutiveFunction])  ▪  (RefLink[BooleanTable, paclet:ref/BooleanTable])  ▪  (RefLink[BooleanConvert, paclet:ref/BooleanConvert])  ▪  (RefLink[BooleanVariables, paclet:ref/BooleanVariables])  ▪  (RefLink[BooleanMinimize, paclet:ref/BooleanMinimize])  ▪  (RefLink[CellularAutomaton, paclet:ref/CellularAutomaton])  ▪  (RefLink[And, paclet:ref/And])  ▪  (RefLink[Or, paclet:ref/Or])  ▪  (RefLink[Not, paclet:ref/Not])  ▪  (RefLink[Nand, paclet:ref/Nand])}})}})

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