Namespaces
Variants
Actions

Difference between revisions of "Boolean differential calculus"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
b1107601.png
 +
$#A+1 = 70 n = 0
 +
$#C+1 = 70 : ~/encyclopedia/old_files/data/B110/B.1100760 Boolean differential calculus
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
A branch of mathematics dealing with the concepts of differentials and derivatives of Boolean functions (cf. [[Boolean function|Boolean function]]) and the manner of using these in the study of such functions.
 
A branch of mathematics dealing with the concepts of differentials and derivatives of Boolean functions (cf. [[Boolean function|Boolean function]]) and the manner of using these in the study of such functions.
  
Line 5: Line 17:
 
Many concepts in Boolean differential calculus are in analogy to those of classical [[Differential calculus|differential calculus]] for real-valued functions of one or more real variables; such are, e.g., the concept of a differential, describing the change of the value of a function and variables, and the concept of a derivative, describing how the value of a function depends on changes of its argument(s).
 
Many concepts in Boolean differential calculus are in analogy to those of classical [[Differential calculus|differential calculus]] for real-valued functions of one or more real variables; such are, e.g., the concept of a differential, describing the change of the value of a function and variables, and the concept of a derivative, describing how the value of a function depends on changes of its argument(s).
  
The simplest and (with regard to applications) most important case is based on the two-element Boolean algebra with carrier set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b1107601.png" />, on Boolean or binary variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b1107602.png" />, and on vectors of variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b1107603.png" /> in a Boolean space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b1107604.png" />. A Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b1107605.png" /> is a mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b1107606.png" />, and a set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b1107607.png" /> functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b1107608.png" /> can be represented as a mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b1107609.png" />.
+
The simplest and (with regard to applications) most important case is based on the two-element Boolean algebra with carrier set $  B = \{ 0, 1 \} $,
 +
on Boolean or binary variables $  x \in \{ 0, 1 \} $,
 +
and on vectors of variables $  {\overline{x}\; } = ( x _ {1} \dots x _ {k} ) $
 +
in a Boolean space $  B  ^ {k} $.  
 +
A Boolean function $  f ( {\overline{x}\; } ) $
 +
is a mapping $  f : {B  ^ {k} } \rightarrow B $,  
 +
and a set of $  n $
 +
functions $  F = \{ f _ {1} \dots f _ {n} \} $
 +
can be represented as a mapping $  F : {B  ^ {k} } \rightarrow {B  ^ {n} } $.
  
A Boolean equation of the general form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076010.png" /> can always be written in homogeneous form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076011.png" />, with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076012.png" />, and a set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076013.png" /> simultaneous equations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076014.png" /> can always be combined into one single equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076015.png" />. Here and below, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076016.png" /> denotes addition modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076017.png" />, or the operation of exclusive or, and the symbols <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076018.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076019.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076020.png" /> stand for disjunction, conjunction and negation, respectively.
+
A Boolean equation of the general form $  f _ {i} ( {\overline{x}\; } ) = f _ {j} ( {\overline{x}\; } ) $
 +
can always be written in homogeneous form $  f ( {\overline{x}\; } ) = 0 $,  
 +
with $  f ( {\overline{x}\; } ) = f _ {i} ( {\overline{x}\; } ) \oplus f _ {j} ( {\overline{x}\; } ) $,  
 +
and a set of $  n $
 +
simultaneous equations $  \{ f _ {1} = 0 \dots f _ {n} = 0 \} $
 +
can always be combined into one single equation $  f _ {1} + \dots + f _ {n} = 0 $.  
 +
Here and below, $  \oplus $
 +
denotes addition modulo $  2 $,  
 +
or the operation of exclusive or, and the symbols $  + $,  
 +
$  \cdot $
 +
and $  {}  ^  \prime  $
 +
stand for disjunction, conjunction and negation, respectively.
  
 
==Derivatives.==
 
==Derivatives.==
Suppose <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076021.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076022.png" />. The (Boolean) derivative <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076023.png" /> of a Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076024.png" /> with respect to the variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076025.png" /> is the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076026.png" /> given by
+
Suppose $  x \in B $
 +
and $  {\overline{y}\; } \in B  ^ {m} $.  
 +
The (Boolean) derivative $  { {\partial  f ( x, {\overline{y}\; } ) } / {\partial  x } } $
 +
of a Boolean function $  f ( x, {\overline{y}\; } ) $
 +
with respect to the variable $  x $
 +
is the function $  { {{\partial  f } / {\partial  x } } } : {B  ^ {m} } \rightarrow B $
 +
given by
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076027.png" /></td> </tr></table>
+
$$
 +
{
 +
\frac{\partial  f }{\partial  x }
 +
} = f ( 0, {\overline{y}\; } ) \oplus f ( 1, {\overline{y}\; } )
 +
$$
  
 
or, equivalently,
 
or, equivalently,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076028.png" /></td> </tr></table>
+
$$
 +
{
 +
\frac{\partial  f }{\partial  x }
 +
} = f ( x, {\overline{y}\; } ) \oplus f ( x  ^  \prime  , {\overline{y}\; } ) .
 +
$$
  
It has the value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076029.png" /> if and only if a change in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076030.png" /> changes the value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076031.png" />.
+
It has the value $  1 $
 +
if and only if a change in $  x $
 +
changes the value of $  f $.
  
The maximum and the minimum of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076032.png" /> with respect to the variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076033.png" /> is defined as:
+
The maximum and the minimum of the function $  f ( x, {\overline{y}\; } ) $
 +
with respect to the variable $  x $
 +
is defined as:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076034.png" /></td> </tr></table>
+
$$
 +
\max  _ { x } f = f ( x, {\overline{y}\; } ) + f ( x  ^  \prime  , {\overline{y}\; } ) ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076035.png" /></td> </tr></table>
+
$$
 +
{ \mathop{\rm min} } _ { x } f = f ( x, {\overline{y}\; } ) \cdot f ( x  ^  \prime  , {\overline{y}\; } ) .
 +
$$
  
Suppose <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076036.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076037.png" />. The derivative <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076038.png" /> of a Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076039.png" /> with respect to the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076040.png" /> variables in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076041.png" /> is the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076042.png" />,
+
Suppose $  {\overline{x}\; } \in B  ^ {k} $
 +
and $  {\overline{y}\; } \in B  ^ {m} $.  
 +
The derivative $  { {\partial  ^ {k} f ( {\overline{x}\; } , {\overline{y}\; } ) } / {\partial  {\overline{x}\; } } } $
 +
of a Boolean function $  f ( {\overline{x}\; } , {\overline{y}\; } ) $
 +
with respect to the $  k $
 +
variables in $  {\overline{x}\; } $
 +
is the function $  { {{\partial  ^ {k} f } / {\partial  {\overline{x}\; } } } } : {B  ^ {m} } \rightarrow B $,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076043.png" /></td> </tr></table>
+
$$
 +
{
 +
\frac{\partial  ^ {k} f }{\partial  {\overline{x}\; } }
 +
} = {
 +
\frac{\partial  ^ {k} f }{\partial  x _ {1} \dots \partial  x _ {k} }
 +
} = {
 +
\frac \partial {\partial  x _ {1} }
 +
} \left ( \dots {
 +
\frac{\partial  f }{\partial  x _ {k} }
 +
} \right ) .
 +
$$
  
 
Maxima and minima of a function with respect to more than one of its variables are defined accordingly.
 
Maxima and minima of a function with respect to more than one of its variables are defined accordingly.
  
 
==Differentials.==
 
==Differentials.==
The variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076044.png" /> defined by
+
The variable $  dx $
 +
defined by
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076045.png" /></td> </tr></table>
+
$$
 +
dx = \left \{
 +
\begin{array}{l}
 +
{1 \  \textrm{ if  }  x  \textrm{ changes  its  value  } , } \\
 +
{0 \  \textrm{ if  }  x  \textrm{ remains  constant  } , }
 +
\end{array}
 +
\right .
 +
$$
  
is called the differential of the variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076046.png" />, and describes changes in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076047.png" />. Likewise, the vector
+
is called the differential of the variable $  x $,  
 +
and describes changes in $  x $.  
 +
Likewise, the vector
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076048.png" /></td> </tr></table>
+
$$
 +
d {\overline{x}\; } = {\overline{x}\; } \oplus {\overline{x}\; }  ^ {*}
 +
$$
  
is called the differential of the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076049.png" />, and describes the changes that occur in the components of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076050.png" /> when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076051.png" /> changes to some other value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076052.png" />; here, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076053.png" /> denotes component-wise exclusive-or. In <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076054.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076055.png" /> is a point, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076056.png" /> is the direction from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076057.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076058.png" />. The (total) differential of a Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076059.png" /> is given by
+
is called the differential of the vector $  {\overline{x}\; } $,  
 +
and describes the changes that occur in the components of $  {\overline{x}\; } $
 +
when $  {\overline{x}\; } $
 +
changes to some other value $  {\overline{x}\; }  ^ {*} $;  
 +
here, $  \oplus $
 +
denotes component-wise exclusive-or. In $  B  ^ {k} $,  
 +
$  {\overline{x}\; } $
 +
is a point, and $  d {\overline{x}\; } $
 +
is the direction from $  {\overline{x}\; } $
 +
to $  {\overline{x}\; }  ^ {*} $.  
 +
The (total) differential of a Boolean function $  f ( {\overline{x}\; } ) $
 +
is given by
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076060.png" /></td> </tr></table>
+
$$
 +
df = f ( {\overline{x}\; } ) \oplus f ( {\overline{x}\; } \oplus d {\overline{x}\; } ) ,
 +
$$
  
the partial differential of a Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076061.png" /> with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076062.png" /> is given by
+
the partial differential of a Boolean function $  f ( {\overline{x}\; } , {\overline{y}\; } ) $
 +
with respect to $  {\overline{x}\; } $
 +
is given by
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076063.png" /></td> </tr></table>
+
$$
 +
d _ { {\overline{x}\; }  } f = df \mid  _ {d {\overline{y}\; = 0 } ,
 +
$$
  
and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076065.png" />th partial differential of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076066.png" /> with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076067.png" /> is given by
+
and the $  k $
 +
th partial differential of $  f ( {\overline{x}\; } , {\overline{y}\; } ) $
 +
with respect to $  {\overline{x}\; } $
 +
is given by
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076068.png" /></td> </tr></table>
+
$$
 +
d _ { {\overline{x}\; }  }  ^ {k} f = d _ {x _ {1}  } ( \dots d _ {x _ {k}  } f ( {\overline{x}\; } , {\overline{y}\; } ) ) .
 +
$$
  
 
Other useful operators include the various differential minima and maxima that can be derived from the various differentials of functions by replacing  ""  with  ""  or  "+" .
 
Other useful operators include the various differential minima and maxima that can be derived from the various differentials of functions by replacing  ""  with  ""  or  "+" .
  
Boolean differential equations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076069.png" />, as well as Boolean equations, can be solved and investigated with the aid of differential operators. Numerical tools may operate on the solution sets of equations rather than on the equations themselves. A compact representation of solution sets uses <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076070.png" />-, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110760/b11076071.png" />-, and  "do-not-care" -elements in ternary-valued tables.
+
Boolean differential equations $  f ( {\overline{x}\; } , d {\overline{x}\; } ) = 0 $,  
 +
as well as Boolean equations, can be solved and investigated with the aid of differential operators. Numerical tools may operate on the solution sets of equations rather than on the equations themselves. A compact representation of solution sets uses $  1 $-,  
 +
0 $-,  
 +
and  "do-not-care" -elements in ternary-valued tables.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  S.B. Akers,  "On a theory of Boolean functions"  ''SIAM J.'' , '''7'''  (1959)  pp. 487–498</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  A.D. Talantsev,  "On the analysis and synthesis of certain electrical circuits by means of special logical operators"  ''Avtomat. i Telemeh.'' , '''20'''  (1959)  pp. 898–907  (In Russian)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A. Thayse,  "Boolean differential calculus"  ''Philips Res. Rep.'' , '''26'''  (1971)  pp. 229–246</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  D. Bochmann,  "Boolean differential calculus (a survey)"  ''Engin. Cybernet.'' , '''15''' :  5  (1977)  pp. 67–75</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  D. Bochmann,  C. Posthoff,  "Binäre dynamische Systeme" , R. Oldenbourg  (1981)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  A. Thayse,  "Boolean calculus of differences" , ''Lecture Notes in Computer Science'' , '''101''' , Springer  (1981)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  R. Scheuring,  H. Wehlan,  "On the design of discrete event dynamic systems by means of the Boolean differential calculus"  D. Franke (ed.)  F. Kraus (ed.) , ''Design Methods of Control Systems'' , '''2''' , Pergamon  (1991)  pp. 723–728</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  S.B. Akers,  "On a theory of Boolean functions"  ''SIAM J.'' , '''7'''  (1959)  pp. 487–498</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  A.D. Talantsev,  "On the analysis and synthesis of certain electrical circuits by means of special logical operators"  ''Avtomat. i Telemeh.'' , '''20'''  (1959)  pp. 898–907  (In Russian)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A. Thayse,  "Boolean differential calculus"  ''Philips Res. Rep.'' , '''26'''  (1971)  pp. 229–246</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  D. Bochmann,  "Boolean differential calculus (a survey)"  ''Engin. Cybernet.'' , '''15''' :  5  (1977)  pp. 67–75</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  D. Bochmann,  C. Posthoff,  "Binäre dynamische Systeme" , R. Oldenbourg  (1981)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  A. Thayse,  "Boolean calculus of differences" , ''Lecture Notes in Computer Science'' , '''101''' , Springer  (1981)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  R. Scheuring,  H. Wehlan,  "On the design of discrete event dynamic systems by means of the Boolean differential calculus"  D. Franke (ed.)  F. Kraus (ed.) , ''Design Methods of Control Systems'' , '''2''' , Pergamon  (1991)  pp. 723–728</TD></TR></table>

Latest revision as of 06:28, 30 May 2020


A branch of mathematics dealing with the concepts of differentials and derivatives of Boolean functions (cf. Boolean function) and the manner of using these in the study of such functions.

Boolean differential calculus originated from the treatment of electrical engineering problems in the areas of error-correcting codes (cf. Error-correcting code) and of design and testing of switching circuits; development into a self-contained mathematical theory was achieved in 1959 [a1], [a2], and continued in the time thereafter [a3], [a4], [a5], [a6]. Boolean differential calculus has also found other engineering applications: e.g., it can be used as a unifying framework for the modeling and investigation of finite automata (cf. Automaton, finite) and of discrete event dynamical systems [a7] (cf. also Discrete event system), i.e., dynamical systems with discrete states and changes of states called events; such systems arise e.g. in digital network communication protocols.

Many concepts in Boolean differential calculus are in analogy to those of classical differential calculus for real-valued functions of one or more real variables; such are, e.g., the concept of a differential, describing the change of the value of a function and variables, and the concept of a derivative, describing how the value of a function depends on changes of its argument(s).

The simplest and (with regard to applications) most important case is based on the two-element Boolean algebra with carrier set $ B = \{ 0, 1 \} $, on Boolean or binary variables $ x \in \{ 0, 1 \} $, and on vectors of variables $ {\overline{x}\; } = ( x _ {1} \dots x _ {k} ) $ in a Boolean space $ B ^ {k} $. A Boolean function $ f ( {\overline{x}\; } ) $ is a mapping $ f : {B ^ {k} } \rightarrow B $, and a set of $ n $ functions $ F = \{ f _ {1} \dots f _ {n} \} $ can be represented as a mapping $ F : {B ^ {k} } \rightarrow {B ^ {n} } $.

A Boolean equation of the general form $ f _ {i} ( {\overline{x}\; } ) = f _ {j} ( {\overline{x}\; } ) $ can always be written in homogeneous form $ f ( {\overline{x}\; } ) = 0 $, with $ f ( {\overline{x}\; } ) = f _ {i} ( {\overline{x}\; } ) \oplus f _ {j} ( {\overline{x}\; } ) $, and a set of $ n $ simultaneous equations $ \{ f _ {1} = 0 \dots f _ {n} = 0 \} $ can always be combined into one single equation $ f _ {1} + \dots + f _ {n} = 0 $. Here and below, $ \oplus $ denotes addition modulo $ 2 $, or the operation of exclusive or, and the symbols $ + $, $ \cdot $ and $ {} ^ \prime $ stand for disjunction, conjunction and negation, respectively.

Derivatives.

Suppose $ x \in B $ and $ {\overline{y}\; } \in B ^ {m} $. The (Boolean) derivative $ { {\partial f ( x, {\overline{y}\; } ) } / {\partial x } } $ of a Boolean function $ f ( x, {\overline{y}\; } ) $ with respect to the variable $ x $ is the function $ { {{\partial f } / {\partial x } } } : {B ^ {m} } \rightarrow B $ given by

$$ { \frac{\partial f }{\partial x } } = f ( 0, {\overline{y}\; } ) \oplus f ( 1, {\overline{y}\; } ) $$

or, equivalently,

$$ { \frac{\partial f }{\partial x } } = f ( x, {\overline{y}\; } ) \oplus f ( x ^ \prime , {\overline{y}\; } ) . $$

It has the value $ 1 $ if and only if a change in $ x $ changes the value of $ f $.

The maximum and the minimum of the function $ f ( x, {\overline{y}\; } ) $ with respect to the variable $ x $ is defined as:

$$ \max _ { x } f = f ( x, {\overline{y}\; } ) + f ( x ^ \prime , {\overline{y}\; } ) , $$

$$ { \mathop{\rm min} } _ { x } f = f ( x, {\overline{y}\; } ) \cdot f ( x ^ \prime , {\overline{y}\; } ) . $$

Suppose $ {\overline{x}\; } \in B ^ {k} $ and $ {\overline{y}\; } \in B ^ {m} $. The derivative $ { {\partial ^ {k} f ( {\overline{x}\; } , {\overline{y}\; } ) } / {\partial {\overline{x}\; } } } $ of a Boolean function $ f ( {\overline{x}\; } , {\overline{y}\; } ) $ with respect to the $ k $ variables in $ {\overline{x}\; } $ is the function $ { {{\partial ^ {k} f } / {\partial {\overline{x}\; } } } } : {B ^ {m} } \rightarrow B $,

$$ { \frac{\partial ^ {k} f }{\partial {\overline{x}\; } } } = { \frac{\partial ^ {k} f }{\partial x _ {1} \dots \partial x _ {k} } } = { \frac \partial {\partial x _ {1} } } \left ( \dots { \frac{\partial f }{\partial x _ {k} } } \right ) . $$

Maxima and minima of a function with respect to more than one of its variables are defined accordingly.

Differentials.

The variable $ dx $ defined by

$$ dx = \left \{ \begin{array}{l} {1 \ \textrm{ if } x \textrm{ changes its value } , } \\ {0 \ \textrm{ if } x \textrm{ remains constant } , } \end{array} \right . $$

is called the differential of the variable $ x $, and describes changes in $ x $. Likewise, the vector

$$ d {\overline{x}\; } = {\overline{x}\; } \oplus {\overline{x}\; } ^ {*} $$

is called the differential of the vector $ {\overline{x}\; } $, and describes the changes that occur in the components of $ {\overline{x}\; } $ when $ {\overline{x}\; } $ changes to some other value $ {\overline{x}\; } ^ {*} $; here, $ \oplus $ denotes component-wise exclusive-or. In $ B ^ {k} $, $ {\overline{x}\; } $ is a point, and $ d {\overline{x}\; } $ is the direction from $ {\overline{x}\; } $ to $ {\overline{x}\; } ^ {*} $. The (total) differential of a Boolean function $ f ( {\overline{x}\; } ) $ is given by

$$ df = f ( {\overline{x}\; } ) \oplus f ( {\overline{x}\; } \oplus d {\overline{x}\; } ) , $$

the partial differential of a Boolean function $ f ( {\overline{x}\; } , {\overline{y}\; } ) $ with respect to $ {\overline{x}\; } $ is given by

$$ d _ { {\overline{x}\; } } f = df \mid _ {d {\overline{y}\; } = 0 } , $$

and the $ k $ th partial differential of $ f ( {\overline{x}\; } , {\overline{y}\; } ) $ with respect to $ {\overline{x}\; } $ is given by

$$ d _ { {\overline{x}\; } } ^ {k} f = d _ {x _ {1} } ( \dots d _ {x _ {k} } f ( {\overline{x}\; } , {\overline{y}\; } ) ) . $$

Other useful operators include the various differential minima and maxima that can be derived from the various differentials of functions by replacing "" with "" or "+" .

Boolean differential equations $ f ( {\overline{x}\; } , d {\overline{x}\; } ) = 0 $, as well as Boolean equations, can be solved and investigated with the aid of differential operators. Numerical tools may operate on the solution sets of equations rather than on the equations themselves. A compact representation of solution sets uses $ 1 $-, $ 0 $-, and "do-not-care" -elements in ternary-valued tables.

References

[a1] S.B. Akers, "On a theory of Boolean functions" SIAM J. , 7 (1959) pp. 487–498
[a2] A.D. Talantsev, "On the analysis and synthesis of certain electrical circuits by means of special logical operators" Avtomat. i Telemeh. , 20 (1959) pp. 898–907 (In Russian)
[a3] A. Thayse, "Boolean differential calculus" Philips Res. Rep. , 26 (1971) pp. 229–246
[a4] D. Bochmann, "Boolean differential calculus (a survey)" Engin. Cybernet. , 15 : 5 (1977) pp. 67–75
[a5] D. Bochmann, C. Posthoff, "Binäre dynamische Systeme" , R. Oldenbourg (1981)
[a6] A. Thayse, "Boolean calculus of differences" , Lecture Notes in Computer Science , 101 , Springer (1981)
[a7] R. Scheuring, H. Wehlan, "On the design of discrete event dynamic systems by means of the Boolean differential calculus" D. Franke (ed.) F. Kraus (ed.) , Design Methods of Control Systems , 2 , Pergamon (1991) pp. 723–728
How to Cite This Entry:
Boolean differential calculus. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Boolean_differential_calculus&oldid=46114
This article was adapted from an original article by H. Wehlan (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article