618.indd FACTA UNIVeRSITATIS Series: electronics and energetics Vol. 28, No 1, March 2015, pp. 101 - 125 BOOLEAN DIFFERENTIAL EQUATIONS - A COMMON MODEL FOR CLASSES, LATTICES, AND ARBITRARY SETS OF BOOLEAN FUNCTIONS Bernd Steinbach1 and Christian Posthoff2 1Institute of Computer Science, Freiberg University of Mining and Technology, Bernhard-von-Cotta-Str. 2, D-09596 Freiberg, Germany 2Department of Computing and Information Technology, The University of the West Indies, Trinidad & Tobago Abstract: The Boolean Differential Calculus (BDC) significantly extends the Boolean Algebra because not only Boolean values 0 and 1, but also changes of Boolean val- ues or Boolean functions can be described. A Boolean Differential Equation (BDe) is a Boolean equation that includes derivative operations of the Boolean Differential Calculus. This paper aims at the classification of BDEs, the characterization of the respective solutions, algorithms to calculate the solution of a BDe, and selected appli- cations. We will show that not only classes and arbitrary sets of Boolean functions but also lattices of Boolean functions can be expressed by Boolean Differential equations. In order to reach this aim, we give a short introduction into the BDC, emphasize the general difference between the solutions of a Boolean equation and a BDE, ex- plain the core algorithms to solve a BDe that is restricted to all vectorial derivatives of f (x) and optionally contains Boolean variables. We explain formulas for transform- ing other derivative operations to vectorial derivatives in order to solve more general BDEs. New fields of applications for BDEs are simple and generalized lattices of Boolean functions. We describe the construction, simplification and solution. Manuscript received November 17, 2014 *An earlier version of this paper was presented as Invited Paper at the the 13th Serbian Mathematical Congress (SMC 2014), May 22-25, 2014, in Vrnjačka Banja, Serbia. Corresponding author: Bernd Steinbach Institute of Computer Science, Freiberg University of Mining and Technology, Bernhard-von-Cotta- Str. 2, D-09596 Freiberg, Germany (e-mail: steinb@informatik). 101 FACTA UNIVeRSITATIS Series: electronics and energetics Vol. 28, No 1, March 2015, pp. 101 - 125 BOOLEAN DIFFERENTIAL EQUATIONS - A COMMON MODEL FOR CLASSES, LATTICES, AND ARBITRARY SETS OF BOOLEAN FUNCTIONS Bernd Steinbach1 and Christian Posthoff2 1Institute of Computer Science, Freiberg University of Mining and Technology, Bernhard-von-Cotta-Str. 2, D-09596 Freiberg, Germany 2Department of Computing and Information Technology, The University of the West Indies, Trinidad & Tobago Abstract: The Boolean Differential Calculus (BDC) significantly extends the Boolean Algebra because not only Boolean values 0 and 1, but also changes of Boolean val- ues or Boolean functions can be described. A Boolean Differential Equation (BDe) is a Boolean equation that includes derivative operations of the Boolean Differential Calculus. This paper aims at the classification of BDEs, the characterization of the respective solutions, algorithms to calculate the solution of a BDe, and selected appli- cations. We will show that not only classes and arbitrary sets of Boolean functions but also lattices of Boolean functions can be expressed by Boolean Differential equations. In order to reach this aim, we give a short introduction into the BDC, emphasize the general difference between the solutions of a Boolean equation and a BDE, ex- plain the core algorithms to solve a BDe that is restricted to all vectorial derivatives of f (x) and optionally contains Boolean variables. We explain formulas for transform- ing other derivative operations to vectorial derivatives in order to solve more general BDEs. New fields of applications for BDEs are simple and generalized lattices of Boolean functions. We describe the construction, simplification and solution. Manuscript received November 17, 2014 *An earlier version of this paper was presented as Invited Paper at the the 13th Serbian Mathematical Congress (SMC 2014), May 22-25, 2014, in Vrnjačka Banja, Serbia. Corresponding author: Bernd Steinbach Institute of Computer Science, Freiberg University of Mining and Technology, Bernhard-von-Cotta- Str. 2, D-09596 Freiberg, Germany (e-mail: steinb@informatik). 101 FACTA UNIVERSITATIS Series: Electronics and Energetics Vol. 28, No 1, March 2015, pp. 51 - 76 DOI: 10.2298/FUEE1501051S Received November 17, 2014 *An earlier version of this paper was presented as Invited Paper at the the 13th Serbian Mathematical Congress (SMC 2014), May 22-25, 2014, in Vrnjačka Banja, Serbia. Corresponding author: Bernd Steinbach Institute of Computer Science, Freiberg University of Mining and Technology, Bernhard-von-Cotta-Str. 2, D-09596 Freiberg, Germany (e-mail: steinb@informatik) 102 B. STeINBACh AND C. PoSThoFF The basic operations of XBOOLE are sufficient to solve BDEs. We demonstrate how a XBooLe-problem program (PRP) of the freely available XBooLe-Monitor quickly solves some BDes. Keywords: Boolean Differential Calculus, Boolean Differential equation (BDe), classes of Boolean functions, lattices of Boolean functions, arbitrary sets of Boolean functions, Lattice-BDe, XBooLe. 1 INTRoDUCTIoN Boolean variables are the simplest variables. A Boolean variable carries only one element of the set B = {0, 1}. These two values can be easily distinguished from each other in technical systems. Therefore we get more and more digital systems. Boolean functions, the operations of the Boolean Algebra, and Boolean equa- tions [1] are well known to solve many tasks for digital systems. The solution of a Boolean equation is a set of Boolean vectors which describes, e.g., the behavior of a circuit. However, this theory is restricted to fixed values for a given point in time. The Boolean Differential Calculus (BDC) [1–3] allows us to study the change of the values of Boolean variables and Boolean functions. The substitution of the derivative operations of the BDC into a Boolean equation leads to a Boolean Dif- ferential Equation (BDe) [4, 5]. A BDE has a more general solution and consequently opens a wider field of applications. We show in this paper how lattices of Boolean functions can be ex- pressed by BDes. We will show that additionally to the well known lattices of incompletely specified functions also more general lattices of Boolean functions can be described in an easy way using the new special Lattice-BDE. The general- ized lattices of Boolean functions open a new field of applications. The rest of this paper is organized as follows. Section 2 defines the derivative operations of the BDC and briefly explains their meaning. Section 3 summarizes the known theory of Boolean Differential equations, introduces algorithms that calculates either sets of classes of Boolean functions or arbitrary sets of Boolean functions as the solution of a BDE, explains a method to map a more general BDE into the form needed for one of these algorithms, and shows how a XBooLe- problem programs (PRP) can solve a BDe in the XBooLe-Monitor. Lattices of Boolean functions are discussed in Section 4 as a new field of ap- plications of BDes. Both the well known lattices that describe incompletely spec- ified functions (ISF) and a more general type of lattices of Boolean functions are uniquely described using Lattice-BDEs. Several examples show that the known algorithm can be used to solve different types of Lattice-BDEs. Finally, Section 5 concludes this paper. 102 B. STeINBACh AND C. PoSThoFF The basic operations of XBOOLE are sufficient to solve BDEs. We demonstrate how a XBooLe-problem program (PRP) of the freely available XBooLe-Monitor quickly solves some BDes. Keywords: Boolean Differential Calculus, Boolean Differential equation (BDe), classes of Boolean functions, lattices of Boolean functions, arbitrary sets of Boolean functions, Lattice-BDe, XBooLe. 1 INTRoDUCTIoN Boolean variables are the simplest variables. A Boolean variable carries only one element of the set B = {0, 1}. These two values can be easily distinguished from each other in technical systems. Therefore we get more and more digital systems. Boolean functions, the operations of the Boolean Algebra, and Boolean equa- tions [1] are well known to solve many tasks for digital systems. The solution of a Boolean equation is a set of Boolean vectors which describes, e.g., the behavior of a circuit. However, this theory is restricted to fixed values for a given point in time. The Boolean Differential Calculus (BDC) [1–3] allows us to study the change of the values of Boolean variables and Boolean functions. The substitution of the derivative operations of the BDC into a Boolean equation leads to a Boolean Dif- ferential Equation (BDe) [4, 5]. A BDE has a more general solution and consequently opens a wider field of applications. We show in this paper how lattices of Boolean functions can be ex- pressed by BDes. We will show that additionally to the well known lattices of incompletely specified functions also more general lattices of Boolean functions can be described in an easy way using the new special Lattice-BDE. The general- ized lattices of Boolean functions open a new field of applications. The rest of this paper is organized as follows. Section 2 defines the derivative operations of the BDC and briefly explains their meaning. Section 3 summarizes the known theory of Boolean Differential equations, introduces algorithms that calculates either sets of classes of Boolean functions or arbitrary sets of Boolean functions as the solution of a BDE, explains a method to map a more general BDE into the form needed for one of these algorithms, and shows how a XBooLe- problem programs (PRP) can solve a BDe in the XBooLe-Monitor. Lattices of Boolean functions are discussed in Section 4 as a new field of ap- plications of BDes. Both the well known lattices that describe incompletely spec- ified functions (ISF) and a more general type of lattices of Boolean functions are uniquely described using Lattice-BDEs. Several examples show that the known algorithm can be used to solve different types of Lattice-BDEs. Finally, Section 5 concludes this paper. 52 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 53 102 B. STeINBACh AND C. PoSThoFF The basic operations of XBOOLE are sufficient to solve BDEs. We demonstrate how a XBooLe-problem program (PRP) of the freely available XBooLe-Monitor quickly solves some BDes. Keywords: Boolean Differential Calculus, Boolean Differential equation (BDe), classes of Boolean functions, lattices of Boolean functions, arbitrary sets of Boolean functions, Lattice-BDe, XBooLe. 1 INTRoDUCTIoN Boolean variables are the simplest variables. A Boolean variable carries only one element of the set B = {0, 1}. These two values can be easily distinguished from each other in technical systems. Therefore we get more and more digital systems. Boolean functions, the operations of the Boolean Algebra, and Boolean equa- tions [1] are well known to solve many tasks for digital systems. The solution of a Boolean equation is a set of Boolean vectors which describes, e.g., the behavior of a circuit. However, this theory is restricted to fixed values for a given point in time. The Boolean Differential Calculus (BDC) [1–3] allows us to study the change of the values of Boolean variables and Boolean functions. The substitution of the derivative operations of the BDC into a Boolean equation leads to a Boolean Dif- ferential Equation (BDe) [4, 5]. A BDE has a more general solution and consequently opens a wider field of applications. We show in this paper how lattices of Boolean functions can be ex- pressed by BDes. We will show that additionally to the well known lattices of incompletely specified functions also more general lattices of Boolean functions can be described in an easy way using the new special Lattice-BDE. The general- ized lattices of Boolean functions open a new field of applications. The rest of this paper is organized as follows. Section 2 defines the derivative operations of the BDC and briefly explains their meaning. Section 3 summarizes the known theory of Boolean Differential equations, introduces algorithms that calculates either sets of classes of Boolean functions or arbitrary sets of Boolean functions as the solution of a BDE, explains a method to map a more general BDE into the form needed for one of these algorithms, and shows how a XBooLe- problem programs (PRP) can solve a BDe in the XBooLe-Monitor. Lattices of Boolean functions are discussed in Section 4 as a new field of ap- plications of BDes. Both the well known lattices that describe incompletely spec- ified functions (ISF) and a more general type of lattices of Boolean functions are uniquely described using Lattice-BDEs. Several examples show that the known algorithm can be used to solve different types of Lattice-BDEs. Finally, Section 5 concludes this paper. Boolean Differential equations - a Common Model for Classes, Lattices, ... 103 2 DeRIVATIVe oPeRATIoNS oF The BooLeAN DIFFeReNTIAL CAL- CULUS The BDC defines the Boolean Differential dx which is also a Boolean variable that is equal to 1 in the case that x changes its value. Additionally, the BDC defines several differential operations of Boolean functions which describe certain general properties depending on possible directions of change. We confine ourselves to derivatives of the BDC where the direction of change is fixed. For simple derivative operations the direction of change is restricted to a single variable xi. The (simple) derivative ∂ f (xi, x1) ∂ xi = f (xi = 0, x1) ⊕ f (xi = 1, x1) (1) is equal to 1 if the function f (xi, x1) changes its value when the value of xi changes. The (simple) minimum min xi f (xi, x1) = f (xi = 0, x1) ∧ f (xi = 1, x1) (2) is equal to 1 when the value of the function f (xi, x1) remains unchanged equal to 1 while the value of xi changes. The (simple) maximum max xi f (xi, x1) = f (xi = 0, x1) ∨ f (xi = 1, x1) (3) is equal to 0 when the value of the function f (xi, x1) remains unchanged equal to 0 while the value of xi changes. Vectorial derivative operations similarly describe cases where all variables of the vector x0 change their values at the same point in time. The following formulas define the vectorial derivative, the vectorial minimum, and the vectorial maximum: ∂ f (x0, x1) ∂ x0 = f (x0, x1) ⊕ f (x0, x1) , (4) min x0 f (x0, x1) = f (x0, x1) ∧ f (x0, x1) , (5) max x0 f (x0, x1) = f (x0, x1) ∨ f (x0, x1) . (6) The simple derivative operations can sequentially be executed with regard to different variables of a subset x0. Such m-fold derivative operations describe a special property for subspaces x1 = const. The following formulas define the m- fold derivative, the m-fold minimum, the m-fold maximum, and the ∆-operation: 52 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 53 104 B. STeINBACh AND C. PoSThoFF ∂ m f (x0, x1) ∂ x1∂ x2 . . . ∂ xm = ∂ ∂ xm ( . . . ( ∂ ∂ x2 ( ∂ f (x0, x1) ∂ x1 )) . . . ) , (7) min x0 m f (x0, x1) = min xm ( . . . ( min x2 ( min x1 f (x0, x1) )) . . . ) , (8) max x0 m f (x0, x1) = max xm ( . . . ( max x2 ( max x1 f (x0, x1) )) . . . ) , (9) ∆x0 f (x0, x1) = minx0 m f (x0, x1) ⊕ max x0 m f (x0, x1) . (10) Because of the limited space, we skip all theorems about relations between certain derivative operations and refer to [3, 6]. 3 BooLeAN DIFFeReNTIAL eQUATIoNS 3.1 An Introductory Example If we know the function f (x) and need the result of any derivative operation then we simply apply the definition and get as result an uniquely specified Boolean function. Example 1. We take the Boolean function: f (x) = f (x1, x2, x3) = x1 ∨ x2 x3 (11) and use Definition (4) to calculate the vectorial derivative of f(x) with regard to (x1, x3): ∂ f (x1, x2, x3) ∂ (x1, x3) = f (x1, x2, x3) ⊕ f (x1, x2, x3) = (x1 ∨ x2 x3) ⊕ (x1 ∨ x2 x3) = x1 ⊕ x2 x3 ⊕ x1 x2 x3 ⊕ x1 ⊕ x2 x3 ⊕ x1 x2 x3 = (x1 ⊕ x1) ⊕ x2 (x3 ⊕ x3) ⊕ x2 (x1 x3 ⊕ x1 x3) = x2 ⊕ x2 (x1 ⊕ x3) = x2 ∨ (x1 ⊕ x3) , and get as result the unique Boolean function: g(x1, x2, x3) = x2 ∨ (x1 ⊕ x3) . (12) Arrows in Figure 1 illustrate the pairs of function values which determine the result of this vectorial derivative. Different function values in these pairs lead to function values 1 in the calculated vectorial derivative. 54 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 55 104 B. STeINBACh AND C. PoSThoFF ∂ m f (x0, x1) ∂ x1∂ x2 . . . ∂ xm = ∂ ∂ xm ( . . . ( ∂ ∂ x2 ( ∂ f (x0, x1) ∂ x1 )) . . . ) , (7) min x0 m f (x0, x1) = min xm ( . . . ( min x2 ( min x1 f (x0, x1) )) . . . ) , (8) max x0 m f (x0, x1) = max xm ( . . . ( max x2 ( max x1 f (x0, x1) )) . . . ) , (9) ∆x0 f (x0, x1) = minx0 m f (x0, x1) ⊕ max x0 m f (x0, x1) . (10) Because of the limited space, we skip all theorems about relations between certain derivative operations and refer to [3, 6]. 3 BooLeAN DIFFeReNTIAL eQUATIoNS 3.1 An Introductory Example If we know the function f (x) and need the result of any derivative operation then we simply apply the definition and get as result an uniquely specified Boolean function. Example 1. We take the Boolean function: f (x) = f (x1, x2, x3) = x1 ∨ x2 x3 (11) and use Definition (4) to calculate the vectorial derivative of f(x) with regard to (x1, x3): ∂ f (x1, x2, x3) ∂ (x1, x3) = f (x1, x2, x3) ⊕ f (x1, x2, x3) = (x1 ∨ x2 x3) ⊕ (x1 ∨ x2 x3) = x1 ⊕ x2 x3 ⊕ x1 x2 x3 ⊕ x1 ⊕ x2 x3 ⊕ x1 x2 x3 = (x1 ⊕ x1) ⊕ x2 (x3 ⊕ x3) ⊕ x2 (x1 x3 ⊕ x1 x3) = x2 ⊕ x2 (x1 ⊕ x3) = x2 ∨ (x1 ⊕ x3) , and get as result the unique Boolean function: g(x1, x2, x3) = x2 ∨ (x1 ⊕ x3) . (12) Arrows in Figure 1 illustrate the pairs of function values which determine the result of this vectorial derivative. Different function values in these pairs lead to function values 1 in the calculated vectorial derivative. Boolean Differential equations - a Common Model for Classes, Lattices, ... 105 x2 x3 f (x) 0 0 0 1 0 1 0 1 1 1 1 1 1 0 0 1 0 1 x1 x2 x3 f (x) 0 0 ����0 1 ���� 1 1 ����1 0 ���� 0 1 x1 x2 x3 g(x) 0 0 1 1 0 1 1 1 1 1 0 1 1 0 1 0 0 1 x1 � � Fig. 1. Related function values of the vectorial derivative of Example 1 Tab. 1. Pairs of functions values and their result of: ∂ f (x0,x1) ∂ x0 = g(x0, x1) f (x0, x1 = const.) f (x0, x1 = const.) g(x0, x1 = const.) g(x0, x1 = const.) 0 0 0 0 1 1 0 0 0 1 1 1 1 0 1 1 Now we consider the reverse situation that we know g(x) and want to find the function f (x) such that g(x) is the result of a derivative operation of the unknown function f (x). From Figure 1, we can conclude that the vectorial derivative of several functions f (x) with regard to (x1, x3) result in the same function g(x) (12). Table 1 shows that two different patterns of function values of f (x) result for a vectorial derivative in the same pair of patterns of function values of g(x). In the special case of Example 1 (see also Figure 1), the two possible patterns of pairs of function values for each of the four pairs lead to 42 = 16 different function f (x) with the same function g(x1, x2, x3) (12) as result of the vectorial derivative with regard to (x1, x3). Figure 2 shows the Karnaugh-maps of these 16 functions using the same encoding of the leftmost Karnaugh-maps for all of them. The original function f (x1, x2, x3) belongs to this set of functions and is labeled as f3(x1, x2, x3) in Figure 2. Another interesting question: is there for each given function g(x0, x1) at least one solution function f (x0, x1) of the simple BDe ∂ f (x0, x1) ∂ x0 = g(x0, x1) ? (13) Due to the commutativity of the ⊕-operations we have g(x0, x1) = ∂ f (x0, x1) ∂ x0 = f (x0, x1) ⊕ f (x0, x1) = ∂ f (x0, x1) ∂ x0 = g(x0, x1) . (14) 54 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 55 106 B. STeINBACh AND C. PoSThoFF ∂ f (x1,x2,x3) ∂ (x1,x3) = g(x1, x2, x3) x2 x3 f1(x) 0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 0 0 1 x1 f2(x) 0 1 0 1 0 0 1 0 f3(x) 0 1 0 1 1 1 0 1 f4(x) 0 1 0 1 1 0 1 1 f5(x) 0 0 1 1 0 1 0 0 f6(x) 0 0 1 1 0 0 1 0 f7(x) 0 0 1 1 1 1 0 1 f8(x) 0 0 1 1 1 0 1 1 x2 x3 f9(x) 0 0 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 x1 f10(x) 1 1 0 0 0 0 1 0 f11(x) 1 1 0 0 1 1 0 1 f12(x) 1 1 0 0 1 0 1 1 f13(x) 1 0 1 0 0 1 0 0 f14(x) 1 0 1 0 0 0 1 0 f15(x) 1 0 1 0 1 1 0 1 f16(x) 1 0 1 0 1 0 1 1 x2 x3 g(x) 0 0 1 1 0 1 1 1 1 1 0 1 1 0 1 0 0 1 x1 � Fig. 2. Sixteen functions with the same vectorial derivative g(x1, x2, x3) (12). Therefore a function f (x0, x1) exists only in the case g(x0, x1) = g(x0, x1) g(x0, x1) ⊕ g(x0, x1) = g(x0, x1) ⊕ g(x0, x1) g(x0, x1) ⊕ g(x0, x1) = 0 ∂ g(x0, x1) ∂ x0 = 0 . (15) We call (15) the integrability condition and can conclude: the functions f (x0, x1) of the BDE (13) exist if and only if g(x0, x1) satisfies the integrability condition (15). All solution functions of the BDe (13) are given by fi(x0, x1) = xi ∧ g(x0, x1) ⊕ h j(x0, x1) (16) with x0 = (x1, . . . , xi, . . . , xk), x1 = (xk+1, . . . , xn), and ∂ h j(x0, x1) ∂ x0 = 0 . (17) We learn from this example: 1. A Boolean Differential equation ∂ f (x1,x2,x3)∂ (x1,x3) = g(x1, x2, x3) includes the un- known function f (x1, x2, x3). 2. There are solutions of a BDe only if the right-hand function g(x1, x2, x3) satisfies a special integrability condition. 56 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 57 Boolean Differential equations - a Common Model for Classes, Lattices, ... 107 3. The general solution of an inhomogeneous BDe is built using a single spe- cial solution of the inhomogeneous BDe and the set of all solutions of the associated homogeneous BDe. The associated homogeneous BDe is built by replacing the right-hand side of an inhomogeneous BDe by 0. 4. Generally, the solution of a Boolean Differential Equation is a set of Boolean functions. This is a significant difference to Boolean equations. The solution of a Boolean equation is a set of Boolean vectors. 3.2 BDEs of Simple and Vectorial Derivatives - Separation of Classes Generally, a Boolean Differential equation (BDe) is an equation in which deriva- tive operations of an unknown function f (x) occur. In order to find a convenient solution method, we restrict in this subsection BDes such that only the function f (x) and all its simple and vectorial derivatives are allowed in expressions on both sides of an equation: Dl ( f (x), ∂ f (x) ∂ x1 , ∂ f (x) ∂ x2 , . . . , ∂ f (x0, x1) ∂ x0 , . . . , ∂ f (x) ∂ x ) = Dr ( f (x), ∂ f (x) ∂ x1 , ∂ f (x) ∂ x2 , . . . , ∂ f (x0, x1) ∂ x0 , . . . , ∂ f (x) ∂ x ) . (18) Using the ⊕-operation, each BDe(18) can be transformed into a homogeneous restrictive BDe: D ( f (x), ∂ f (x) ∂ x1 , ∂ f (x) ∂ x2 , . . . , ∂ f (x0, x1) ∂ x0 , . . . , ∂ f (x) ∂ x ) = 0 . (19) The following definition supports the description of the solution procedure. Definition 1. Let g(x) be a solution function of (19). Then 1. [ g(x), ∂ g(x) ∂ x1 , ∂ g(x) ∂ x2 , . . . , ∂ g(x) ∂ x ] x=c (20) is a local solution for x = c, 2. D(u0, u1, . . . , u2n−1) = 0 (21) is the Boolean equation, associated to the Boolean Differential Equation (19), and has the set of local solutions SLS. 56 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 57 108 B. STeINBACh AND C. PoSThoFF ��������01 dx1 dx2 �� dx1 dx2 �� dx1 dx2 ��� � � � � � � � � � � � � � � � � ����������������11�� dx1 dx2 ��dx1 dx2�� ����������������00 ���� dx1 dx2 �� ����������������10 �� �� ��� � � � � � � � � � � � � � � � � (x1, x2) Fig. 3. Values of the function g(x1, x2) = x1 ∨ x2 and their simple and vectorial derivatives for (x1, x2) = (1, 1). 3. ∇g(x) = ( g(x), ∂ g(x) ∂ x1 , ∂ g(x) ∂ x2 , . . . , ∂ g(x) ∂ x ) (22) The local solutions (20) are the key to solve a BDe. The values of the simple and vectorial derivatives in a single selected point of the Boolean space specify the function values in all other points of this space. Figure 3 shows the function g(x1, x2) = x1 ∨ x2 where function values 1 are indicated by double circles, values 1 of derivatives are indicated by solid arrows, and values 0 of derivatives are indicated by dotted arrows. Example 2. Assume, we know the local solution for (x1, x2) = (1, 1) as depicted in Figure 3. Then we can conclude: • due to the known point: g(x)|(x1,x2)=(11) = 1 → g(1, 1) = 1 , • due to the direction of change dx1 dx2: ∂ g(x) ∂ x1 ∣ ∣ ∣ (x1,x2)=(11) = 1 → g(0, 1) = 0 , • due to the direction of change dx1 dx2: ∂ g(x) ∂ x2 ∣ ∣ ∣ (x1,x2)=(11) = 0 → g(1, 0) = 1 , and • due to the direction of change dx1 dx2: ∂ g(x) ∂ (x1,x2) ∣ ∣ ∣ (x1,x2)=(11) = 0 → g(0, 0) = 1 . Hence, a possible solution function g(x) = x1 ∨ x2 could be reconstructed based on the knowledge of the local solution in a single point of the Boolean space. The BDe (19) contains all elements of ∇ f (x) either in non-negated or negated form. hence, all these elements can be encoded by Boolean variables ui as shown in Table 2. 58 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 59 108 B. STeINBACh AND C. PoSThoFF ��������01 dx1 dx2 �� dx1 dx2 �� dx1 dx2 ��� � � � � � � � � � � � � � � � � ����������������11�� dx1 dx2 ��dx1 dx2�� ����������������00 ���� dx1 dx2 �� ����������������10 �� �� ��� � � � � � � � � � � � � � � � � (x1, x2) Fig. 3. Values of the function g(x1, x2) = x1 ∨ x2 and their simple and vectorial derivatives for (x1, x2) = (1, 1). 3. ∇g(x) = ( g(x), ∂ g(x) ∂ x1 , ∂ g(x) ∂ x2 , . . . , ∂ g(x) ∂ x ) (22) The local solutions (20) are the key to solve a BDe. The values of the simple and vectorial derivatives in a single selected point of the Boolean space specify the function values in all other points of this space. Figure 3 shows the function g(x1, x2) = x1 ∨ x2 where function values 1 are indicated by double circles, values 1 of derivatives are indicated by solid arrows, and values 0 of derivatives are indicated by dotted arrows. Example 2. Assume, we know the local solution for (x1, x2) = (1, 1) as depicted in Figure 3. Then we can conclude: • due to the known point: g(x)|(x1,x2)=(11) = 1 → g(1, 1) = 1 , • due to the direction of change dx1 dx2: ∂ g(x) ∂ x1 ∣ ∣ ∣ (x1,x2)=(11) = 1 → g(0, 1) = 0 , • due to the direction of change dx1 dx2: ∂ g(x) ∂ x2 ∣ ∣ ∣ (x1,x2)=(11) = 0 → g(1, 0) = 1 , and • due to the direction of change dx1 dx2: ∂ g(x) ∂ (x1,x2) ∣ ∣ ∣ (x1,x2)=(11) = 0 → g(0, 0) = 1 . Hence, a possible solution function g(x) = x1 ∨ x2 could be reconstructed based on the knowledge of the local solution in a single point of the Boolean space. The BDe (19) contains all elements of ∇ f (x) either in non-negated or negated form. hence, all these elements can be encoded by Boolean variables ui as shown in Table 2. Boolean Differential equations - a Common Model for Classes, Lattices, ... 109 Tab. 2. Mapping of the BDe into the associated Boolean equation index binary code ui associated element 0 (0 . . . 00) u0 f (x) 1 (0 . . . 01) u1 ∂ f (x) ∂ x1 2 (0 . . . 10) u2 ∂ f (x) ∂ x2 3 (0 . . . 11) u3 ∂ f (x) ∂ (x1,x2) : : : : 2n − 1 (1 . . . 11) u2n−1 ∂ f (x) ∂ x The result of this substitution is an associated Boolean equation D(u) = 0. The solution of this Boolean equation is the set of all local solutions SLS(u). There are local solutions for which no global solution functions of the BDE (19) exist. The sufficient condition for a global solution function of the BDE (19) is that a local solution exists for each point of the Boolean space Bn: ∀c ∈ Bn ∇ f (x) |x=c ∈ SLS(u) . (23) An important consequence of (23) is that the solutions of the BDe (19) consist of classes of Boolean functions as characterized by Theorem 1; the proof is given in [4, 5]. Theorem 1. If the Boolean function f (x) is a solution function of the Boolean Differential Equation (19), then all Boolean functions f (x1, x2, ..., xn) = f (x1 ⊕ c1, x2 ⊕ c2, ..., xn ⊕ cn) (24) for c = (c1, . . . , cn) ∈ Bn are also solution functions of (19). The set of local solutions SLS(u) expresses by u0 the function value in one point of Bn and by ui, 0 < i < 2n, the values of changes with regard to all the other points of Bn. The separation of function classes becomes easier when the function value in all points of Bn are uniquely given. The function d2v (derivative to value) uses (25) to transform the set SLS(u) into the set SLS′(v). v0 = u0 , vi = u0 ⊕ ui , with i = 1, 2, ..., 2n − 1 . (25) 58 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 59 110 B. STeINBACh AND C. PoSThoFF Due to (24), the exchange of xi and xi does not change the set of solution func- tions. The function epv (exchange of pairs of values) realizes this exchange: SLST(v) = epv(SLS′(v), i) . (26) Applied to variables vi this exchange is described by: v(m+2 k·2i−1) ⇐⇒ v(m+(2 k+1)·2i−1) , (27) with i = 1, 2, ..., n , m = 0, 1, ..., 2i−1 − 1 , k = 0, 1, ..., 2n−i − 1 . Table 3 enumerates the index pairs which are used in the function epv for Boolean spaces up to B4. Tab. 3. Index pairs defined by (27) for the exchange of function values i = 1 i = 2 i = 3 i = 4 0 ⇔ 1 0 ⇔ 2 0 ⇔ 4 0 ⇔ 8 2 ⇔ 3 1 ⇔ 3 1 ⇔ 5 1 ⇔ 9 4 ⇔ 5 4 ⇔ 6 2 ⇔ 6 2 ⇔ 10 6 ⇔ 7 5 ⇔ 7 3 ⇔ 7 3 ⇔ 11 8 ⇔ 9 8 ⇔ 10 8 ⇔ 12 4 ⇔ 12 10 ⇔ 11 9 ⇔ 11 9 ⇔ 13 5 ⇔ 13 12 ⇔ 13 12 ⇔ 14 10 ⇔ 14 6 ⇔ 14 14 ⇔ 15 13 ⇔ 15 11 ⇔ 15 7 ⇔ 15 The intersection of the given set SLS′(v) with the exchanged set SLST(v) for all variables xi separates the set of global solution functions from the local solutions which are not sufficient. Algorithm 1 describes the procedure to solve the BDe (19) in detail. The solution vectors v of Algorithm 1 specify, substituted into (28), all solution functions of the BDe (19). f (x1, x2, . . . , xn) = x1 x2 . . . xn ∧ v0 ∨ x1 x2 . . . xn ∧ v1 ∨ . . . ∨ (28) x1 x2 . . . xn ∧ v2n−1 3.3 BDEs of Simple and Vectorial Derivatives as well as Variables - Separa- tion of Arbitrary Function Sets The solution of a Boolean Differential equation of the type (18) is a set of function classes characterized by (24). Additional Boolean variables x in a Boolean Dif- ferential equation of the type (29) restrict the derivatives to certain points of the 60 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 61 110 B. STeINBACh AND C. PoSThoFF Due to (24), the exchange of xi and xi does not change the set of solution func- tions. The function epv (exchange of pairs of values) realizes this exchange: SLST(v) = epv(SLS′(v), i) . (26) Applied to variables vi this exchange is described by: v(m+2 k·2i−1) ⇐⇒ v(m+(2 k+1)·2i−1) , (27) with i = 1, 2, ..., n , m = 0, 1, ..., 2i−1 − 1 , k = 0, 1, ..., 2n−i − 1 . Table 3 enumerates the index pairs which are used in the function epv for Boolean spaces up to B4. Tab. 3. Index pairs defined by (27) for the exchange of function values i = 1 i = 2 i = 3 i = 4 0 ⇔ 1 0 ⇔ 2 0 ⇔ 4 0 ⇔ 8 2 ⇔ 3 1 ⇔ 3 1 ⇔ 5 1 ⇔ 9 4 ⇔ 5 4 ⇔ 6 2 ⇔ 6 2 ⇔ 10 6 ⇔ 7 5 ⇔ 7 3 ⇔ 7 3 ⇔ 11 8 ⇔ 9 8 ⇔ 10 8 ⇔ 12 4 ⇔ 12 10 ⇔ 11 9 ⇔ 11 9 ⇔ 13 5 ⇔ 13 12 ⇔ 13 12 ⇔ 14 10 ⇔ 14 6 ⇔ 14 14 ⇔ 15 13 ⇔ 15 11 ⇔ 15 7 ⇔ 15 The intersection of the given set SLS′(v) with the exchanged set SLST(v) for all variables xi separates the set of global solution functions from the local solutions which are not sufficient. Algorithm 1 describes the procedure to solve the BDe (19) in detail. The solution vectors v of Algorithm 1 specify, substituted into (28), all solution functions of the BDe (19). f (x1, x2, . . . , xn) = x1 x2 . . . xn ∧ v0 ∨ x1 x2 . . . xn ∧ v1 ∨ . . . ∨ (28) x1 x2 . . . xn ∧ v2n−1 3.3 BDEs of Simple and Vectorial Derivatives as well as Variables - Separa- tion of Arbitrary Function Sets The solution of a Boolean Differential equation of the type (18) is a set of function classes characterized by (24). Additional Boolean variables x in a Boolean Dif- ferential equation of the type (29) restrict the derivatives to certain points of the Boolean Differential equations - a Common Model for Classes, Lattices, ... 111 Algorithm 1 Separation of function classes Require: BDe (19) with function f (x) containing n variables Ensure: set of Boolean vectors v = (v0, v1, . . . , v2n−1) that describe, substituted in (28), the set of all solution functions of the BDe (19) 1: SLS(u) ← solution of Be (21) associated with BDe (19) 2: SLS′(v) ← d2v(SLS(u)) 3: for i ← 1 to n do 4: SLST(v) ← epv(SLS′(v), i) 5: SLS′(v) ← SLS′(v) ∩SLST(v) 6: end for Boolean space. Therefore, selected functions of the function classes can belong to the set of solution functions. hence, a BDe (29) has an arbitrary set of Boolean functions as solution. Dl ( f (x), ∂ f (x) ∂ x1 , ∂ f (x) ∂ x2 , . . . , ∂ f (x0, x1) ∂ x0 . . . , ∂ f (x) ∂ x , x ) = Dr ( f (x), ∂ f (x) ∂ x1 , ∂ f (x) ∂ x2 , . . . , ∂ f (x0, x1) ∂ x0 . . . , ∂ f (x) ∂ x , x ) . (29) A BDE (29) can be solved using a slightly modified algorithm. The variables x remain in the associated Boolean equation (30) associated to (29): Dl (u0, u1, . . . , u2n−1, x1, x2, . . . , xn) = Dr(u0, u1, . . . , u2n−1, x1, x2, . . . , xn) . (30) A detailed analysis in [4] reveals that the local solutions must be split into the cofactors S0 for xi = 0 and S1 for xi = 1 and the exchange of function pairs must be restricted to S1. Algorithm 2 describes the detailed steps to solve a BDe (29). 3.4 More General Boolean Differential Equations In addition to the simple and vectorial derivatives all other derivative operations can be used within a BDe. We do not need special solution algorithms for such more general Boolean Differential equations because the theorems of the BDC allow us the transformation of all types of derivative operations into the elements of ∇ f (x) 60 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 61 112 B. STeINBACh AND C. PoSThoFF Algorithm 2 Separation of functions Require: BDe (29) in which the function f (x) depends on n variables Ensure: set S of Boolean vectors v = (v0, v1, . . . , v2n−1) that describe, substituted in (28), the set of all solution functions of the BDe (29) 1: SLS(u, x) ← solution of the Be (30) associated with BDe (29) 2: S(v, x) ← d2v(SLS(u, x)) 3: for i ← 1 to n do 4: S0(v, x \ (x1, . . . , xi)) ← maxxi [xi ∧S(v, xi, . . . , xn)] 5: S1(v, x \ (x1, . . . , xi)) ← maxxi [xi ∧S(v, xi, . . . , xn)] 6: ST1(v, x \ (x1, . . . , xi)) ← epv(S1(v, x \ (x1, . . . , xi)), i) 7: S(v, x \ (x1, . . . , xi)) ← S0(v, x \ (x1, . . . , xi)) ∩ST1(v, x \ (x1, . . . , xi)) 8: end for (22). min xi f (x) = f (x) ∧ ∂ f (x) ∂ xi (31) max xi f (x) = f (x) ∨ ∂ f (x) ∂ xi (32) min x0 f (x0, x1) = f (x0, x1) ∧ ∂ f (x0, x1) ∂ x0 (33) max x0 f (x0, x1) = f (x0, x1) ∨ ∂ f (x0, x1) ∂ x0 (34) min (x1,x2) 2 f (x) = f (x) ∧ ∂ f (x) ∂ x1 ∧ ∂ f (x) ∂ x2 ∧ ∂ f (x) ∂ (x1, x2) (35) max (x1,x2) 2 f (x) = f (x) ∨ ∂ f (x) ∂ x1 ∨ ∂ f (x) ∂ x2 ∨ ∂ f (x) ∂ (x1, x2) (36) ∂ 2 f (x) ∂ x1∂ x2 = ∂ f (x) ∂ x1 ⊕ ∂ f (x) ∂ x2 ⊕ ∂ f (x) ∂ (x1, x2) (37) ∆(x1,x2) f (x) = ∂ f (x) ∂ x1 ∨ ∂ f (x) ∂ x2 ∨ ∂ f (x) ∂ (x1, x2) (38) General formulas to express the simple or vectorial minimum or maximum by the function f (x) and simple or vectorial derivatives are given in (31),. . . , (34). The equations (35),. . . , (38) describe how all 2-fold derivative operations can be trans- formed into expressions that contain only the function f (x) and simple or vectorial derivatives. These formulas can be generalized for any m ≤ n of functions in Bn [6]. Using these transformations each more general BDe results either in the BDe 62 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 63 112 B. STeINBACh AND C. PoSThoFF Algorithm 2 Separation of functions Require: BDe (29) in which the function f (x) depends on n variables Ensure: set S of Boolean vectors v = (v0, v1, . . . , v2n−1) that describe, substituted in (28), the set of all solution functions of the BDe (29) 1: SLS(u, x) ← solution of the Be (30) associated with BDe (29) 2: S(v, x) ← d2v(SLS(u, x)) 3: for i ← 1 to n do 4: S0(v, x \ (x1, . . . , xi)) ← maxxi [xi ∧S(v, xi, . . . , xn)] 5: S1(v, x \ (x1, . . . , xi)) ← maxxi [xi ∧S(v, xi, . . . , xn)] 6: ST1(v, x \ (x1, . . . , xi)) ← epv(S1(v, x \ (x1, . . . , xi)), i) 7: S(v, x \ (x1, . . . , xi)) ← S0(v, x \ (x1, . . . , xi)) ∩ST1(v, x \ (x1, . . . , xi)) 8: end for (22). min xi f (x) = f (x) ∧ ∂ f (x) ∂ xi (31) max xi f (x) = f (x) ∨ ∂ f (x) ∂ xi (32) min x0 f (x0, x1) = f (x0, x1) ∧ ∂ f (x0, x1) ∂ x0 (33) max x0 f (x0, x1) = f (x0, x1) ∨ ∂ f (x0, x1) ∂ x0 (34) min (x1,x2) 2 f (x) = f (x) ∧ ∂ f (x) ∂ x1 ∧ ∂ f (x) ∂ x2 ∧ ∂ f (x) ∂ (x1, x2) (35) max (x1,x2) 2 f (x) = f (x) ∨ ∂ f (x) ∂ x1 ∨ ∂ f (x) ∂ x2 ∨ ∂ f (x) ∂ (x1, x2) (36) ∂ 2 f (x) ∂ x1∂ x2 = ∂ f (x) ∂ x1 ⊕ ∂ f (x) ∂ x2 ⊕ ∂ f (x) ∂ (x1, x2) (37) ∆(x1,x2) f (x) = ∂ f (x) ∂ x1 ∨ ∂ f (x) ∂ x2 ∨ ∂ f (x) ∂ (x1, x2) (38) General formulas to express the simple or vectorial minimum or maximum by the function f (x) and simple or vectorial derivatives are given in (31),. . . , (34). The equations (35),. . . , (38) describe how all 2-fold derivative operations can be trans- formed into expressions that contain only the function f (x) and simple or vectorial derivatives. These formulas can be generalized for any m ≤ n of functions in Bn [6]. Using these transformations each more general BDe results either in the BDe Boolean Differential equations - a Common Model for Classes, Lattices, ... 113 (18) for which the solution classes can be calculated using Algorithm 1, or it results in the BDe (29) so that the arbitrary solution set is found using Algorithm 2. 3.5 Solving a Boolean Differential Equations Using a XBOOLE PRP The XBooLe-Monitor can be downloaded (for free) from: http://www.informatik.tu-freiberg.de/xboole/ and provides many operations which can be applied to sets of Boolean functions. All XBOOLE-operations are explained in the help-system of the XBOOLE-Moni- tor. We summarize here some XBooLe-operations needed to solve a BDe. All XBooLe-objects are indicated by numbers. The XBooLe-operations can be ex- ecuted in the XBooLe-Monitor by means of 1. a selected and parametrized menu item, 2. a tool-bar button followed by the same dialog to specify the parameters, 3. a XBOOLE-command that specifies both the operation and the objects, and 4. a XBooLe-problem program (PRP) that contains a sequence of commands. The main data structure is the ternary vector list (TVL). All XBooLe-opera- tions are executed in a Boolean space. The user must specify the number of Boolean variables which can be used in a Boolean space using the XBooLe-command: space vmax sno where vmax is the number of variables and sno is the number of the space. Variables in a wanted order can be attached to an XBooLe-space using: avar sni where on the next lines the names of the variables separated by a space and finished by a point (.) are declared. A Boolean equation or a system of Boolean equations is solved using: sbe sni tno where tno is the object number of the result TVL and the Boolean equation is given on the following lines finished by a point (.) using the operation signs ‘/’ for the negation, ‘&’ for the conjunction ∧, ‘+’ for the disjunction ∨, ‘#’ for the antivalence ⊕, ‘=’ for the equivalence ⊙ as well as for separating both sides of the equation, and ‘,’ to separate the equations within a system of Boolean equations. Logic operations for the input TVL (tni, tni1, tni2) and the calculation of the output TVL (tno) are given by: • negation fo = f (complement): cpl tni tno 62 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 63 114 B. STeINBACh AND C. PoSThoFF • conjunction fo = f1 ∧ f2 (intersection): isc tni1 tni2 tno • disjunction fo = f1 ∨ f2 (union): uni tni1 tni2 tno • antivalence fo = f1 ⊕ f2 (symmetric difference): syd tni1 tni2 tno • equivalence fo = f1 ⊙ f2 (complement of the symmetric difference): csd tni1 tni2 tno An ordered set of variables can be defined as a XBOOLE-object called vari- ables tuple (VT) using: vtin sni vtno followed by the variable in the needed order as in the case of the command avar. Two such VTs define ordered pairs of variables which can be changed using: cco tni vtni1 vtni2 tno where the exchange of columns of tni is realized for all defined pair of vari- ables. Alternatively the VTs can be directly specified within a special XBOOLe- command: cco tni tno which exchanges, e.g., column x1 with column x8 and column x2 with column x9. A single VT is used to specify the variables for a vectorial or m-fold derivative operation; e.g.: maxk tni vtni tno calculates the k-fold maximum with regard to all variables specified in VT vtni and maxk tni tno calculates the 2-fold maximum with regard to (x1, x2). Example 3. Bent functions [7–9] are the most non-linear functions which are needed in cryptography. The simplest bent functions are specified by the BDE: ∂ 2 f (x1, x2) ∂ x1∂ x2 = 1 . (39) Using (37) we get the equivalent BDE: ∂ f (x1, x2) ∂ x1 ⊕ ∂ f (x1, x2) ∂ x2 ⊕ ∂ f (x1, x2) ∂ (x1, x2) = 1 . (40) 64 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 65 114 B. STeINBACh AND C. PoSThoFF • conjunction fo = f1 ∧ f2 (intersection): isc tni1 tni2 tno • disjunction fo = f1 ∨ f2 (union): uni tni1 tni2 tno • antivalence fo = f1 ⊕ f2 (symmetric difference): syd tni1 tni2 tno • equivalence fo = f1 ⊙ f2 (complement of the symmetric difference): csd tni1 tni2 tno An ordered set of variables can be defined as a XBOOLE-object called vari- ables tuple (VT) using: vtin sni vtno followed by the variable in the needed order as in the case of the command avar. Two such VTs define ordered pairs of variables which can be changed using: cco tni vtni1 vtni2 tno where the exchange of columns of tni is realized for all defined pair of vari- ables. Alternatively the VTs can be directly specified within a special XBOOLe- command: cco tni tno which exchanges, e.g., column x1 with column x8 and column x2 with column x9. A single VT is used to specify the variables for a vectorial or m-fold derivative operation; e.g.: maxk tni vtni tno calculates the k-fold maximum with regard to all variables specified in VT vtni and maxk tni tno calculates the 2-fold maximum with regard to (x1, x2). Example 3. Bent functions [7–9] are the most non-linear functions which are needed in cryptography. The simplest bent functions are specified by the BDE: ∂ 2 f (x1, x2) ∂ x1∂ x2 = 1 . (39) Using (37) we get the equivalent BDE: ∂ f (x1, x2) ∂ x1 ⊕ ∂ f (x1, x2) ∂ x2 ⊕ ∂ f (x1, x2) ∂ (x1, x2) = 1 . (40) Boolean Differential equations - a Common Model for Classes, Lattices, ... 115 This BDE contains two simple and and one vectorial derivative. Hence, it can be solved using Algorithm 1. The associated Boolean equation of (40) is u1 ⊕ u2 ⊕ u3 = 1 . (41) 1 s p a c e 32 1 2 a v a r 1 3 u0 u1 u2 u3 v0 v1 v2 v3 . 4 s b e 1 1 5 u1 # u2 # u3 = 1 . 6 s b e 1 2 7 v0 =u0 , 8 v1 = u0 # u1 , 9 v2 = u0 # u2 , 10 v3 = u0 # u3 . 11 i s c 1 2 3 12 v t i n 1 4 13 u0 u1 u2 u3 . 14 maxk 3 4 5 15 v t i n 1 6 16 v0 v2 . 17 v t i n 1 7 18 v1 v3 . 19 c c o 5 6 7 8 20 i s c 5 8 9 21 v t i n 1 10 22 v0 v1 . 23 v t i n 1 11 24 v2 v3 . 25 c c o 9 10 11 12 26 i s c 9 12 13 Fig. 4. Listing of the PRP to solve the BDe (40). Figure 4 show the PRP that can be used by the XBOOLE-Monitor to solve BDE (40). The solution of (41) is stored as XBOOLE-object 1. The lines 6 to 14 in Figure 4 realize the d2v-transformation of line 2 of Algorithm 1 so that the XBOOLE-object 5 stores SLS′(v). The first sweep of the loop in lines 3 to 6 of Algorithm 1 is executed in lines 15 to 20 and the second sweep of this loop leads to the XBOOLE-object 13 as final result in lines 21 to 26 of Figure 4. Table 4 shows in the left part the solution TVL of BDE (40). The eight v-vectors describe two classes of Boolean functions. The expressions of these functions are built by the substitution of the v-vectors of the solution into (28). Table 4 shows these functions in the right part associated to the classes 1 and 2. 4 BooLeAN DIFFeReNTIAL eQUATIoNS FoR LATTICeS oF BooLeAN FUNCTIoNS 4.1 Lattices of Incompletely Specified Boolean Functions A lattice of Boolean function is a special set of functions that has the following properties: • if both f1(x) and f2(x) belong to the lattice then f (x) = f1(x)∧ f2(x) belongs also to this lattice of Boolean functions, and 64 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 65 116 B. STeINBACh AND C. PoSThoFF Tab. 4. Solution functions of BDe (40) v0 v1 v2 v3 class 1 class 2 0 1 1 1 x1 ∨ x2 1 0 0 0 x1 ∧ x2 1 0 1 1 x1 ∨ x2 0 1 0 0 x1 ∧ x2 0 0 0 1 x1 ∧ x2 1 1 1 0 x1 ∨ x2 1 1 0 1 x1 ∨ x2 0 0 1 0 x1 ∧ x2 • if both f1(x) and f2(x) belong to the lattice then f (x) = f1(x)∨ f2(x) belongs also to this lattice of Boolean functions. A lattice of Boolean function is very often used for the design of a digital circuit. Based on another point of view, such a lattice is sometimes called incompletely specified function (ISF). one method to describe the lattice of functions of an ISF uses two mark func- tions called: 1. oN-set q(x): all functions of the lattice must be equal to one for q(x) = 1, and 2. oFF-set r(x): all functions of the lattice must be equal to zero for r(x) = 1. Using these known mark functions each function f (x) of the set of functions { fi(x)} must hold the inequalities: f (x) ≥ q(x) , (42) f (x) ≤ r(x) , (43) which can be transformed into the equivalent restrictions: f (x) ∧ q(x) = 0 , (44) f (x) ∧ r(x) = 0 . (45) The system of equations (44) and (45) can be merged into a single Boolean equation: f (x) ∧ q(x) ∨ f (x) ∧ r(x) = 0 . (46) 66 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 67 116 B. STeINBACh AND C. PoSThoFF Tab. 4. Solution functions of BDe (40) v0 v1 v2 v3 class 1 class 2 0 1 1 1 x1 ∨ x2 1 0 0 0 x1 ∧ x2 1 0 1 1 x1 ∨ x2 0 1 0 0 x1 ∧ x2 0 0 0 1 x1 ∧ x2 1 1 1 0 x1 ∨ x2 1 1 0 1 x1 ∨ x2 0 0 1 0 x1 ∧ x2 • if both f1(x) and f2(x) belong to the lattice then f (x) = f1(x)∨ f2(x) belongs also to this lattice of Boolean functions. A lattice of Boolean function is very often used for the design of a digital circuit. Based on another point of view, such a lattice is sometimes called incompletely specified function (ISF). one method to describe the lattice of functions of an ISF uses two mark func- tions called: 1. oN-set q(x): all functions of the lattice must be equal to one for q(x) = 1, and 2. oFF-set r(x): all functions of the lattice must be equal to zero for r(x) = 1. Using these known mark functions each function f (x) of the set of functions { fi(x)} must hold the inequalities: f (x) ≥ q(x) , (42) f (x) ≤ r(x) , (43) which can be transformed into the equivalent restrictions: f (x) ∧ q(x) = 0 , (44) f (x) ∧ r(x) = 0 . (45) The system of equations (44) and (45) can be merged into a single Boolean equation: f (x) ∧ q(x) ∨ f (x) ∧ r(x) = 0 . (46) Boolean Differential equations - a Common Model for Classes, Lattices, ... 117 The functions q(x) and r(x) in (46) are known and can be represent by expres- sions of Boolean variables connected by Boolean operations. The term f (x) in (46) describes the unknown functions of the lattice. Hence, the equation (46) fits to the type of Boolean Differential equations (29), where only f (x) and variables xi but no simple or vectorial derivatives occur. All functions of a lattice which is specified by the BDe (46) can be calculated using Algorithm 2. Example 4. Let q(x) = x1 x3 ∨ x2 x3 and r(x) = x1 x2 be the given mark functions of a lattice of Boolean functions f (x). Using (46), we get the BDE of this lattice: f (x) ∧ (x1 x3 ∨ x2 x3) ∨ f (x) ∧ x1 x2 = 0 (47) and the associated Boolean equation: u0 ∧ (x1 x3 ∨ x2 x3) ∨ u0 ∧ x1 x2 = 0 . (48) Figure 5 shows the PRP that is used in the XBOOLE-Monitor to solve the BDE (47). After the definition of the Boolean space B32 in line 1; the used variables are defined in lines 2 to 5, and the associated Boolean equation is solved in lines 6 to 8. The BDE (47) contains only f(x) out of the vector ∇ f (x) so that the transformation d2v can be restricted to the mapping of u0 to v0 in lines 9 to 14. Due to the existing variables xi Algorithm 2 must be used to separate the set of solution functions. All steps of the loop of lines 3 to 8 of Algorithm 2 are realized in lines 15 to 53 of the PRP in Figure 5. The lines 15 to 27 of the PRP describe the first sweep of this loop for x1. The indices of the variables vi are taken from the first four rows of column i = 1 of Table 3 where the VT 11 uses the left values and the VT 12 the right values. The intermediate solution of this sweep is stored into the same XBOOLE-object 5 that represent the function S of Algorithm 2. Hence, the fragment of lines 15 to 27 of the first sweep of the loop can be reused in lines 28 to 40 for the second sweep with x2 and the VTs specified by column i = 2 of Table 3 and in lines 41 to 53 for the third sweep with x3 and the VTs specified by column i = 3 of Table 3, respectively. Tab. 5. Solution functions of BDe (47) v0 v1 v2 v3 v4 v5 v6 v7 solution functions 1 1 0 1 1 1 0 1 f1(x) = x1 ∨ x2 1 1 0 1 0 1 0 1 f2(x) = x1 ∨ x2 x3 1 1 0 0 1 1 0 1 f3(x) = x1 x3 ∨ x2 1 1 0 0 0 1 0 1 f4(x) = x1 x3 ∨ x2 x3 66 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 67 118 B. STeINBACh AND C. PoSThoFF 1 s p a c e 32 1 2 a v a r 1 3 u0 4 v0 v1 v2 v3 v4 v5 v6 v7 5 x1 x2 x3 . 6 s b e 1 1 7 / u0 &( x1&x3 + / x2 &/ x3 ) + 8 u0 & ( / x1&x2 ) = 0 . 9 s b e 1 2 10 v0 = u0 . 11 i s c 1 2 3 12 v t i n 1 4 13 u0 . 14 maxk 3 4 5 15 s b e 1 6 16 x1 = 0 . 17 i s c 5 6 7 18 maxk 7 6 8 19 c p l 6 6 20 i s c 5 6 9 21 maxk 9 6 10 22 v t i n 1 11 23 v0 v2 v4 v6 . 24 v t i n 1 12 25 v1 v3 v5 v7 . 26 c c o 10 11 12 13 27 i s c 8 13 5 28 s b e 1 6 29 x2 = 0 . 30 i s c 5 6 7 31 maxk 7 6 8 32 c p l 6 6 33 i s c 5 6 9 34 maxk 9 6 10 35 v t i n 1 11 36 v0 v1 v4 v5 . 37 v t i n 1 12 38 v2 v3 v6 v7 . 39 c c o 10 11 12 13 40 i s c 8 13 5 41 s b e 1 6 42 x3 = 0 . 43 i s c 5 6 7 44 maxk 7 6 8 45 c p l 6 6 46 i s c 5 6 9 47 maxk 9 6 10 48 v t i n 1 11 49 v0 v1 v2 v3 . 50 v t i n 1 12 51 v4 v5 v6 v7 . 52 c c o 10 11 12 13 53 i s c 8 13 5 Fig. 5. Listing of the PRP to solve the BDe (47). Table 5 enumerates the four solution functions of the BDE (47) calculated by the XBOOLE-Monitor using the PRP of Figure 5. The columns v3 and v4 show that this lattice contains all functions which are smaller or equal to the supremum function f1(x) and greater or equal to the infimum function f4(x). 4.2 Generalized Lattices of Boolean Functions each derivative operation transforms a given lattice of Boolean functions into an- other lattice of Boolean functions. The resulting lattices are more general because the function values 0 and 1 cannot only be chosen for a single x-pattern, but also for 68 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 69 118 B. STeINBACh AND C. PoSThoFF 1 s p a c e 32 1 2 a v a r 1 3 u0 4 v0 v1 v2 v3 v4 v5 v6 v7 5 x1 x2 x3 . 6 s b e 1 1 7 / u0 &( x1&x3 + / x2 &/ x3 ) + 8 u0 & ( / x1&x2 ) = 0 . 9 s b e 1 2 10 v0 = u0 . 11 i s c 1 2 3 12 v t i n 1 4 13 u0 . 14 maxk 3 4 5 15 s b e 1 6 16 x1 = 0 . 17 i s c 5 6 7 18 maxk 7 6 8 19 c p l 6 6 20 i s c 5 6 9 21 maxk 9 6 10 22 v t i n 1 11 23 v0 v2 v4 v6 . 24 v t i n 1 12 25 v1 v3 v5 v7 . 26 c c o 10 11 12 13 27 i s c 8 13 5 28 s b e 1 6 29 x2 = 0 . 30 i s c 5 6 7 31 maxk 7 6 8 32 c p l 6 6 33 i s c 5 6 9 34 maxk 9 6 10 35 v t i n 1 11 36 v0 v1 v4 v5 . 37 v t i n 1 12 38 v2 v3 v6 v7 . 39 c c o 10 11 12 13 40 i s c 8 13 5 41 s b e 1 6 42 x3 = 0 . 43 i s c 5 6 7 44 maxk 7 6 8 45 c p l 6 6 46 i s c 5 6 9 47 maxk 9 6 10 48 v t i n 1 11 49 v0 v1 v2 v3 . 50 v t i n 1 12 51 v4 v5 v6 v7 . 52 c c o 10 11 12 13 53 i s c 8 13 5 Fig. 5. Listing of the PRP to solve the BDe (47). Table 5 enumerates the four solution functions of the BDE (47) calculated by the XBOOLE-Monitor using the PRP of Figure 5. The columns v3 and v4 show that this lattice contains all functions which are smaller or equal to the supremum function f1(x) and greater or equal to the infimum function f4(x). 4.2 Generalized Lattices of Boolean Functions each derivative operation transforms a given lattice of Boolean functions into an- other lattice of Boolean functions. The resulting lattices are more general because the function values 0 and 1 cannot only be chosen for a single x-pattern, but also for Boolean Differential equations - a Common Model for Classes, Lattices, ... 119 pairs of x-patterns. The proof that all derivative operations of any lattice result in such a generalized lattice is given for the first time in [10]. The generalized lattices are described in [10] by the mark function q(x) and r(x) as well as an independence matrix (IDM) that have the shape of an echelon and elements below the main diag- onal are equal to 0. The IDM describes all independent directions of change where no function of the lattice changes its values. Associated to the independence ma- trix IDM an independence function f id (x) is defined in [10]. Knowing the mark functions q(x) and r(x) and the independence function f id (x), a Boolean equation given in [10] allows us to check for each function f (x) whether it belongs to the generalized lattice or not. Instead of the two mark functions and the independence matrix we suggest here a single Boolean Differential Equation to describe a generalized lattice of Boolean functions. The directions, in which no function of the lattice changes its values, are described in a restrictive BDe by simple and vectorial derivatives which are connected by disjunctions (∨): n ∨ i=1 ∂ f (x) ∂ x0i = 0 , (49) where • i is the row index of the IDM, • values 1 in the row of IDM specify the variables of x0i, and • ∂ f (x) ∂ x0i = 0 if all elements of the i-th row in IDM(f) are equal to 0. A BDe (50) can be solved by Algorithm 1, and the special structure of the BDe ensures that the set of classes of solution function describes a lattice of Boolean functions. Example 5. The generalized lattice of the Boolean function f(x1, x2, x3) in which all functions do not change their function values if either x1 and x3 or x2 and x3 are commonly changed at the same point in time can be described by the BDE: ∂ f (x) ∂ (x1, x3) ∨ ∂ f (x) ∂ (x2, x3) = 0 (50) and the associated Boolean equation: u5 ∨ u6 = 0 . (51) Figure 6 shows the PRP that is used in the XBOOLE-Monitor to solve the BDE (50). After the definition of the Boolean space B32 in line 1; the used variables are 68 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 69 120 B. STeINBACh AND C. PoSThoFF 1 s p a c e 32 1 2 a v a r 1 3 u0 u5 u6 4 v0 v1 v2 v3 v4 v5 v6 v7 . 5 s b e 1 1 6 u5 + u6 = 0 . 7 s b e 1 2 8 v0 =u0 , 9 v5 = u0 # u5 , 10 v6 = u0 # u6 . 11 i s c 1 2 3 12 v t i n 1 4 13 u0 u5 u6 . 14 maxk 3 4 5 15 v t i n 1 6 16 v0 v2 v4 v6 . 17 v t i n 1 7 18 v1 v3 v5 v7 . 19 c c o 5 6 7 8 20 i s c 5 8 5 21 v t i n 1 6 22 v0 v1 v4 v5 . 23 v t i n 1 7 24 v2 v3 v6 v7 . 25 c c o 5 6 7 8 26 i s c 5 8 5 27 v t i n 1 6 28 v0 v1 v2 v3 . 29 v t i n 1 7 30 v4 v5 v6 v7 . 31 c c o 5 6 7 8 32 i s c 5 8 5 Fig. 6. Listing of the PRP to solve the BDe (50). Tab. 6. Solution functions of BDe (50) v0 v1 v2 v3 v4 v5 v6 v7 class 1 class 2 class 3 1 1 1 1 1 1 1 1 f1(x) = 1 1 0 0 1 0 1 1 0 f2(x) = x1 ⊕ x2 ⊕ x3 0 1 1 0 1 0 0 1 f3(x) = x1 ⊕ x2 ⊕ x3 0 0 0 0 0 0 0 0 f4(x) = 0 defined in lines 2 to 4, and the associated Boolean equation is solved in lines 5 to 6. The BDE (50) contains only two vectorial derivatives out of the vector ∇ f (x) so that the transformation d2v can be restricted to the mapping of u5 to v5 and u6 to v6 in lines 7 to 14, where u0 is needed as counterpart to v0. Due to missing variables xi Algorithm 1 can be used to separate the classes of solution functions. All steps of the loop of lines 3 to 6 of Algorithm 1 are realized in lines 15 to 32 of the PRP in Figure 6. The lines 15 to 20 of the PRP describe the first sweep of this loop for the exchange of x1. The indices of the variables vi are taken from the first four rows of column i = 1 of Table 3 where the VT 6 uses the left values and the VT 7 the right values. The intermediate solution of this sweep is stored into the same XBOOLE-object 5 that represents the function SLS′ of Algorithm 1. Hence, the fragment of lines 15 to 20 of the first sweep of the loop can be reused in lines 21 to 26 for the second sweep with regard to x2 and the VTs specified by column i = 2 of Table 3 and in lines 27 to 32 for the third sweep with regard to x3 and the VTs specified by column i = 3 of Table 3, respectively. 70 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 71 120 B. STeINBACh AND C. PoSThoFF 1 s p a c e 32 1 2 a v a r 1 3 u0 u5 u6 4 v0 v1 v2 v3 v4 v5 v6 v7 . 5 s b e 1 1 6 u5 + u6 = 0 . 7 s b e 1 2 8 v0 =u0 , 9 v5 = u0 # u5 , 10 v6 = u0 # u6 . 11 i s c 1 2 3 12 v t i n 1 4 13 u0 u5 u6 . 14 maxk 3 4 5 15 v t i n 1 6 16 v0 v2 v4 v6 . 17 v t i n 1 7 18 v1 v3 v5 v7 . 19 c c o 5 6 7 8 20 i s c 5 8 5 21 v t i n 1 6 22 v0 v1 v4 v5 . 23 v t i n 1 7 24 v2 v3 v6 v7 . 25 c c o 5 6 7 8 26 i s c 5 8 5 27 v t i n 1 6 28 v0 v1 v2 v3 . 29 v t i n 1 7 30 v4 v5 v6 v7 . 31 c c o 5 6 7 8 32 i s c 5 8 5 Fig. 6. Listing of the PRP to solve the BDe (50). Tab. 6. Solution functions of BDe (50) v0 v1 v2 v3 v4 v5 v6 v7 class 1 class 2 class 3 1 1 1 1 1 1 1 1 f1(x) = 1 1 0 0 1 0 1 1 0 f2(x) = x1 ⊕ x2 ⊕ x3 0 1 1 0 1 0 0 1 f3(x) = x1 ⊕ x2 ⊕ x3 0 0 0 0 0 0 0 0 f4(x) = 0 defined in lines 2 to 4, and the associated Boolean equation is solved in lines 5 to 6. The BDE (50) contains only two vectorial derivatives out of the vector ∇ f (x) so that the transformation d2v can be restricted to the mapping of u5 to v5 and u6 to v6 in lines 7 to 14, where u0 is needed as counterpart to v0. Due to missing variables xi Algorithm 1 can be used to separate the classes of solution functions. All steps of the loop of lines 3 to 6 of Algorithm 1 are realized in lines 15 to 32 of the PRP in Figure 6. The lines 15 to 20 of the PRP describe the first sweep of this loop for the exchange of x1. The indices of the variables vi are taken from the first four rows of column i = 1 of Table 3 where the VT 6 uses the left values and the VT 7 the right values. The intermediate solution of this sweep is stored into the same XBOOLE-object 5 that represents the function SLS′ of Algorithm 1. Hence, the fragment of lines 15 to 20 of the first sweep of the loop can be reused in lines 21 to 26 for the second sweep with regard to x2 and the VTs specified by column i = 2 of Table 3 and in lines 27 to 32 for the third sweep with regard to x3 and the VTs specified by column i = 3 of Table 3, respectively. Boolean Differential equations - a Common Model for Classes, Lattices, ... 121 Table 6 enumerates the four solution functions of the BDE (50) calculated by the XBOOLE-Monitor using the PRP of Figure 6. The solution of the BDE (50) consists of three classes of Boolean functions. The class 1 only contains the function f1(x) = 1 that is the supremum r(x) of the lattice. Due to (24) a solution class in B3 generally contains 23 = 8 functions. Two times four of these functions are identical in case of class 2: f2(x) = x1 ⊕ x2 ⊕ x3 = x1 ⊕ x2 ⊕ x3 = x1 ⊕ x2 ⊕ x3 = x1 ⊕ x2 ⊕ x3 , f3(x) = x1 ⊕ x2 ⊕ x3 = x1 ⊕ x2 ⊕ x3 = x1 ⊕ x2 ⊕ x3 = x1 ⊕ x2 ⊕ x3 . The class 3 only contains the function f4(x) = 0 that is the infimum q(x) of the lattice. The solution lattice contains only two of 28 − 2 = 254 functions of B3 which are greater than q(x) = 0 and smaller than r(x) = 1. Nevertheless, the four function of Table 6 constitute a lattice—both the conjunction and the disjunction of any pair of these function result in one of these functions. It should be mentioned that there are four different BDe having the same lattice of solutions shown in Table 6. The most extended BDE with this solution lattice is: ∂ f (x) ∂ (x1, x2) ∨ ∂ f (x) ∂ (x1, x3) ∨ ∂ f (x) ∂ (x2, x3) = 0 . (52) The equivalent other three BDe with the same solution are built by omitting one of the three vectorial derivatives: ∂ f (x) ∂ (x1, x3) ∨ ∂ f (x) ∂ (x2, x3) = 0 , (53) ∂ f (x) ∂ (x1, x2) ∨ ∂ f (x) ∂ (x2, x3) = 0 , (54) ∂ f (x) ∂ (x1, x2) ∨ ∂ f (x) ∂ (x1, x3) = 0 , (55) where (53) is identical with (50) and used in Example 5. The reason for these al- ternative BDe with the same solution lattice is that only two of the three directions of change in (52) of the vectorial derivatives are linearly independent. Two algo- rithms in [10] describe how the unique independent directions of change can be found. The BDe (53) is the unique representative BDe for the solution lattice of Table 6. Example 5 explores a generalized lattice with the special mark functions q(x) = 0 and r(x) = 0, in order to emphasize that only a special subset of functions between these two mark function belong to the lattice. however, this restriction is not nec- essary. The BDe (46) can be combined with the BDe (49) to the BDe of a most 70 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 71 122 B. STeINBACh AND C. PoSThoFF general lattice: f (x) ∧ q(x) ∨ f (x) ∧ r(x) ∨ n ∨ i=1 ∂ f (x) ∂ x0i = 0 . (56) Example 6. We assume that a generalized lattice of the Boolean function f(x) is described by the BDE: f (x) ∧ ((x1 ⊕ x3) ∧ (x2 ⊕ x4)) ∨ f (x) ∧ ((x1 ⊕ x3) ∧ (x2 ⊕ x4))∨ ∂ f (x) ∂ (x1, x3) ∨ ∂ f (x) ∂ (x2, x4) = 0 (57) which has the associated Boolean equation: f (x) ∧ ((x1 ⊕ x3) ∧ (x2 ⊕ x4)) ∨ f (x) ∧ ((x1 ⊕ x3) ∧ (x2 ⊕ x4)) ∨ u5 ∨ u10 = 0 . (58) Figure 7 shows the PRP that is used to solve the BDE (57) of a most general lattice of Boolean functions. After the definition of the Boolean space B32 in line 1; the used variables are defined in lines 2 to 8, and the associated Boolean equation is solved in lines 9 to 12. The BDE (57) contains only f (x) and two vectorial derivatives out of the vector ∇ f (x) so that the transformation d2v can be restricted to the mapping of u0 to v0, u5 to v5, and u10 to v10, in lines 13 to 20. Due to the existing variables xi Algorithm 2 must be used to separate the set of solution functions which have the structure of a lattice due to the structure of the BDE to be solved. All steps of the loop of lines 3 to 8 of Algorithm 2 are realized in lines21 to80of thePRPinFigure 7. The lines21 to35of thePRPdescribe thefirst sweep of this loop for x1. The indices of the variables vi are taken from the column i = 1 of Table 3 where the VT 11 uses the left values and the VT 12 the right values. The intermediate solution of this sweep is stored to the same XBOOLE-object 5 that represent the function S of Algorithm 2. Hence, the fragment of lines 21 to 35 of the first sweep of the loop can be reused in lines 36 to 50 for the second sweep with x2 and the VTs specified by column i = 2 of Table 3, in lines 51 to 65 for the third sweep with x3 and the VTs specified by column i = 3, and finally in lines 66 to 80 for the fourth sweep with x4 and the VTs specified by column i = 4 of Table 3, respectively. Table 7 enumerates the four solution functions of the BDE (57) calculated by the XBOOLE-Monitor using the PRP of Figure 7. The function values in the columns v0, . . . , v15 confirm that the calculated four functions form a lattice. It can also be seen in these columns that not all functions which are smaller than the supremum f1 and larger than the infimum f4 belong to this generalized lattice of Boolean functions. 72 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 73 122 B. STeINBACh AND C. PoSThoFF general lattice: f (x) ∧ q(x) ∨ f (x) ∧ r(x) ∨ n ∨ i=1 ∂ f (x) ∂ x0i = 0 . (56) Example 6. We assume that a generalized lattice of the Boolean function f(x) is described by the BDE: f (x) ∧ ((x1 ⊕ x3) ∧ (x2 ⊕ x4)) ∨ f (x) ∧ ((x1 ⊕ x3) ∧ (x2 ⊕ x4))∨ ∂ f (x) ∂ (x1, x3) ∨ ∂ f (x) ∂ (x2, x4) = 0 (57) which has the associated Boolean equation: f (x) ∧ ((x1 ⊕ x3) ∧ (x2 ⊕ x4)) ∨ f (x) ∧ ((x1 ⊕ x3) ∧ (x2 ⊕ x4)) ∨ u5 ∨ u10 = 0 . (58) Figure 7 shows the PRP that is used to solve the BDE (57) of a most general lattice of Boolean functions. After the definition of the Boolean space B32 in line 1; the used variables are defined in lines 2 to 8, and the associated Boolean equation is solved in lines 9 to 12. The BDE (57) contains only f (x) and two vectorial derivatives out of the vector ∇ f (x) so that the transformation d2v can be restricted to the mapping of u0 to v0, u5 to v5, and u10 to v10, in lines 13 to 20. Due to the existing variables xi Algorithm 2 must be used to separate the set of solution functions which have the structure of a lattice due to the structure of the BDE to be solved. All steps of the loop of lines 3 to 8 of Algorithm 2 are realized in lines21 to80of thePRPinFigure 7. The lines21 to35of thePRPdescribe thefirst sweep of this loop for x1. The indices of the variables vi are taken from the column i = 1 of Table 3 where the VT 11 uses the left values and the VT 12 the right values. The intermediate solution of this sweep is stored to the same XBOOLE-object 5 that represent the function S of Algorithm 2. Hence, the fragment of lines 21 to 35 of the first sweep of the loop can be reused in lines 36 to 50 for the second sweep with x2 and the VTs specified by column i = 2 of Table 3, in lines 51 to 65 for the third sweep with x3 and the VTs specified by column i = 3, and finally in lines 66 to 80 for the fourth sweep with x4 and the VTs specified by column i = 4 of Table 3, respectively. Table 7 enumerates the four solution functions of the BDE (57) calculated by the XBOOLE-Monitor using the PRP of Figure 7. The function values in the columns v0, . . . , v15 confirm that the calculated four functions form a lattice. It can also be seen in these columns that not all functions which are smaller than the supremum f1 and larger than the infimum f4 belong to this generalized lattice of Boolean functions. Boolean Differential equations - a Common Model for Classes, Lattices, ... 123 1 s p a c e 32 1 2 a v a r 1 3 u0 u5 u10 4 v0 v1 v2 v3 5 v4 v5 v6 v7 6 v8 v9 v1 0 v 11 7 v1 2 v 13 v14 v15 8 x1 x2 x3 x4 . 9 s b e 1 1 10 / u0 & ( / ( x1 # x3 ) & ( x2 # x4 ) ) + 11 u0 & ( ( x1 # x3 ) & ( x2 # x4 ) ) + 12 u5 + u10 = 0 . 13 s b e 1 2 14 v0 =u0 , 15 v5 = u0 # u5 , 16 v1 0 = u0 # u10 . 17 i s c 1 2 3 18 v t i n 1 4 19 u0 u5 u10 . 20 maxk 3 4 5 21 s b e 1 6 22 x1 = 0 . 23 i s c 5 6 7 24 maxk 7 6 8 25 c p l 6 6 26 i s c 5 6 9 27 maxk 9 6 10 28 v t i n 1 11 29 v0 v2 v4 v6 30 v8 v10 v12 v1 4 . 31 v t i n 1 12 32 v1 v3 v5 v7 33 v9 v11 v13 v1 5 . 34 c c o 10 11 12 13 35 i s c 8 13 5 36 s b e 1 6 37 x2 = 0 . 38 i s c 5 6 7 39 maxk 7 6 8 40 c p l 6 6 41 i s c 5 6 9 42 maxk 9 6 10 43 v t i n 1 11 44 v0 v1 v4 v5 45 v8 v9 v12 v13 . 46 v t i n 1 12 47 v2 v3 v6 v7 48 v10 v11 v14 v15 . 49 c c o 10 11 12 13 50 i s c 8 13 5 51 s b e 1 6 52 x3 = 0 . 53 i s c 5 6 7 54 maxk 7 6 8 55 c p l 6 6 56 i s c 5 6 9 57 maxk 9 6 10 58 v t i n 1 11 59 v0 v1 v2 v3 60 v8 v9 v10 v11 . 61 v t i n 1 12 62 v4 v5 v6 v7 63 v12 v13 v14 v15 . 64 c c o 10 11 12 13 65 i s c 8 13 5 66 s b e 1 6 67 x4 = 0 . 68 i s c 5 6 7 69 maxk 7 6 8 70 c p l 6 6 71 i s c 5 6 9 72 maxk 9 6 10 73 v t i n 1 11 74 v0 v1 v2 v3 75 v4 v5 v6 v7 . 76 v t i n 1 12 77 v8 v9 v10 v11 78 v12 v13 v14 v15 . 79 c c o 10 11 12 13 80 i s c 8 13 5 Fig. 7. Listing of the PRP to solve the BDe (57). 72 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 73 124 B. STeINBACh AND C. PoSThoFF Tab. 7. Solution functions of BDe (57) v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 solution functions 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 f1(x) = (x1 ⊕ x3) ∨ (x2 ⊕ x4) 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 f2(x) = x1 ⊕ x3 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 f3(x) = x1 ⊕ x2 ⊕ x3 ⊕ x4 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 f4(x) = (x1 ⊕ x3) ∧ (x2 ⊕ x4) 5 CoNCLUSIoNS The Boolean Differential Calculus extends the field of application of the Boolean Algebra significantly. Simple and vectorial derivative operations evaluate pairs of function values in the selected direction of change. The values of m-fold derivative operations depend on values of the given function in whole subspaces. An unknown function f (x) and derivative operations of this function appear in Boolean expressions on both sides of a Boolean Differential Equation (BDe). The solution of each BDE is a set of Boolean functions. This is an important extension to a Boolean equation which has a set of binary vectors as solution. The explored algorithms allow us to solve BDEs which describe either sets of classes of Boolean functions or arbitrary sets of Boolean functions. We demon- strated that these algorithms can easily be implemented using the XBooLe-Moni- tor. The used problem programs (PRP) show all details of the introduced algorithms to solve a BDe. Using the XBooLe-Library all these steps can be wrapped by special programs such that the set of solution functions of a BDe is automatically created. The algorithms known from [4,5] are able to separate (depending on the type of the BDe) either classes of solution functions or arbitrary sets of solution functions. We presented in this paper special types of BDes which either combine certain classes to a lattice of Boolean functions or restrict the arbitrary sets of solutions to a lattice of Boolean functions. There is a wide field of applications of BDEs. Many examples are explained in [4]. here, we introduced three new types of BDes. All of them describe lattices of Boolean functions. 1. A BDe of the type (46) describes a well known and widely used lattice of Boolean functions that can alternatively be expressed by an incompletely specified function. Such a BDE can be solved using Algorithm 2. 2. A BDE of the type (49) describes a lattice with the infimum function q(x) = 0 and the supremum function r(x) = 1 and can be solved using Algorithm 74 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 75 124 B. STeINBACh AND C. PoSThoFF Tab. 7. Solution functions of BDe (57) v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 solution functions 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 f1(x) = (x1 ⊕ x3) ∨ (x2 ⊕ x4) 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 f2(x) = x1 ⊕ x3 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 f3(x) = x1 ⊕ x2 ⊕ x3 ⊕ x4 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 f4(x) = (x1 ⊕ x3) ∧ (x2 ⊕ x4) 5 CoNCLUSIoNS The Boolean Differential Calculus extends the field of application of the Boolean Algebra significantly. Simple and vectorial derivative operations evaluate pairs of function values in the selected direction of change. The values of m-fold derivative operations depend on values of the given function in whole subspaces. An unknown function f (x) and derivative operations of this function appear in Boolean expressions on both sides of a Boolean Differential Equation (BDe). The solution of each BDE is a set of Boolean functions. This is an important extension to a Boolean equation which has a set of binary vectors as solution. The explored algorithms allow us to solve BDEs which describe either sets of classes of Boolean functions or arbitrary sets of Boolean functions. We demon- strated that these algorithms can easily be implemented using the XBooLe-Moni- tor. The used problem programs (PRP) show all details of the introduced algorithms to solve a BDe. Using the XBooLe-Library all these steps can be wrapped by special programs such that the set of solution functions of a BDe is automatically created. The algorithms known from [4,5] are able to separate (depending on the type of the BDe) either classes of solution functions or arbitrary sets of solution functions. We presented in this paper special types of BDes which either combine certain classes to a lattice of Boolean functions or restrict the arbitrary sets of solutions to a lattice of Boolean functions. There is a wide field of applications of BDEs. Many examples are explained in [4]. here, we introduced three new types of BDes. All of them describe lattices of Boolean functions. 1. A BDe of the type (46) describes a well known and widely used lattice of Boolean functions that can alternatively be expressed by an incompletely specified function. Such a BDE can be solved using Algorithm 2. 2. A BDE of the type (49) describes a lattice with the infimum function q(x) = 0 and the supremum function r(x) = 1 and can be solved using Algorithm Boolean Differential equations - a Common Model for Classes, Lattices, ... 125 1. Such a lattice contains not all functions which are greater than q(x) and smaller than r(x). 3. A BDe of the more general type (56) merges the BDes of the cases 1 and 2. Such a BDe must be solved using Algorithm 2 because the mark functions q(x) and r(x) are not limited to the case 2. It can be very difficult to find a BDE for a needed set of Boolean functions. however, it is an advantage that BDes for lattices can be built in a straight manner based on the mentioned types. Therefore, we call BDes of the types (46), (49), and (56) Lattice-BDEs. The result of a Lattice-BDe (49) or (56) is a generalized lattice of Boolean functions that cannot be expressed by an incompletely specified function. In this way these Lattice-BDEs opens many new fields of applications, e.g., in circuit de- sign. Vice versa, the Lattice-BDe (46) is a sub-type of the most general Lattice- BDE (56) so that the so far widely used lattices of Boolean functions fitting to an incompletely specified Boolean function are integrated in the new theory in a nat- ural manner. It is a challenge for the future to utilize Lattice-BDes for specific applications. ReFeReNCeS [1] C. Posthoff and B. Steinbach, Logic Functions and Equations - Binary Models for Computer Science. Dordrecht: Springer, 2004. [2] B. Steinbach and C. Posthoff, “Boolean Differential Calculus,” in Progress in Appli- cations of Boolean Functions. Morgan & Claypool Publishers, San Rafael, CA - USA, 2010, pp. 55–78. [3] ——, “Boolean Differential Calculus - theory and applications,” Journal of Compu- tational and Theoretical Nanoscience, vol. 7, no. 6, pp. 933–981, 2010. [4] ——, Boolean Differential Equations. Morgan & Claypool Publishers, 2013. [5] B. Steinbach, “Lösung binärer Differentialgleichungen und ihre Anwendung auf binäre Systeme,” Ph.D. dissertation, TH Karl-Marx-Stadt (Germany), 1981. [6] D. Bochmann and C. Posthoff, Binre dynamische Systeme. Munich, Vienna: old- enbourg, 1981. [7] o. S. Rothaus, “on ”bent” functions,” J.CombinatorialTheory, vol. 20, pp. 300–305, 1976. [8] B. Steinbach and C. Posthoff, “Classification and generation of bent functions,” in Proceedings Reed-Muller 2011 Workshop, Gustavelund Conference Centre, Tuusula, Finnland, 2011, pp. 81–91. 74 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... 75 126 B. STeINBACh AND C. PoSThoFF [9] ——, “Classes of bent functions identified by specific normal forms and generated using boolean differential equations,” FACTA UNIVERSITATIS (NIŠ), vol. 24, no. 3, pp. 357–383, 2011. [10] B. Steinbach, “Generalized lattices of boolean functions utilized for derivative oper- ations,” in Materiały konferencyjne KNWS’13, Łagów, Poland, 2013, pp. 1–17. 76 B. STeINBACh, C. PoSThoFF Boolean Differential equations – a Common Model for Classes, Lattices... PB