# A New Calculation for Boolean Derivative Using Cheng Product

Authors: Hao Chen; Jitao Sun
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

The matrix expression and relationships among several definitions of Boolean derivatives are given by using the Cheng product. We introduce several definitions of Boolean derivatives. By using the Cheng product, the matrix expressions of Boolean derivative are given, respectively. Furthermore, the relationships among different definitions are presented. The logical calculation is converted into matrix product. This helps to extend the application of Boolean derivative. At last, an example is given to illustrate the main results.


---

## Body

## 1. Introduction

Boolean algebra was first proposed by George Bole in 1847. It is basic to many aspects of computing. Boolean calculus was first put forward by Daniell in [1]. From then on, great interest has been drawn, and many papers have come out; see [2–5] and references therein. Some forty years after the Boolean calculus was proposed, Boolean derivative was introduced in [6, 7] and applied to switching theory. From then on, Boolean derivative has developed quickly and has been applied in many fields; see [4, 8–13] and references therein. The application of Boolean derivative contains analysis of random Boolean networks [10], design of discrete event systems [11], and cellular automata [12]. Especially, Boolean derivative is widely used in damage spreading and Lyapunov exponents [13] in cellular automata.Recently, the semitensor product or Cheng product of matrices is proposed and it is successfully applied to express and analyze the Boolean networks. The biggest advantage using this new tool is that it can convert a logical system into a classic discrete dynamical system [14]. After the conversation, the calculation can be easily achieved by the Matlab toolbox. However, the logical calculation is hard to realize before this new tool comes out. It has been applied to present many properties of Boolean networks, such as the controllability and observability [15, 16], stabilization [17], and realization of Boolean networks [18].There are several definitions of Boolean derivatives. In this paper, the definitions can be found in [19–21].The Cheng product is the main tool in the present paper. We considered several definitions of Boolean derivatives. By using the Cheng product, formulas for calculating the Boolean derivatives are provided, and the relationships among different definitions of Boolean derivatives are given.The rest of the paper is organized as follows. Section2 introduces some fundamental definitions and some notations used in the paper. In Section 3, several definitions of Boolean derivatives are given, and the relationships among them are presented by using the Cheng product. In Section 4, an example is given to illustrate the main results.


## 2. Preliminary

The semitensor product, that is, Cheng product is the crucial tool in the present paper. The matrix product is assumed to be the semitensor product in the following discussion. In most cases, the symbol⋉ is omitted. A review of basic concepts and notations will be given [14] as follows.(1)
𝒟2:={0,1}.(2)
Δn:={δn1,…,δnn}, where δnk denotes the kth column of the identity matrix In.(3)
Letℳn×s denote the set of n×s matrices. Assume a matrix M=[δnj1,δnj2,…,δnjs]∈ℳn×s, that is, its columns, Col(M)⊂Δn. M is called a logical matrix. We denote it as M=δn[j1,j2,…,js] for simplification. The set of n×m logical matrices is denoted by ℒn×m.(4)
LetX be a row vector of dimension np, and let Y=[y1,y2,…,yp]T be a column vector of dimension p. Then, we split X into p equal-size blocks as X1,…,Xp, which are 1×n rows. Define the semitensor product, denoted by ⋉, as
(2.1)X⋉Y=∑i=1p‍Xiyi∈Rn,YT⋉XT=∑i=1p‍yi(Xi)T∈Rn.(5)
LetM∈ℳm×n and N∈ℳp×q. If n is a factor of p or p is a factor of n, then C=M⋉N is called the semitensor product of M and N, where C consists of m×q blocks as C=(Cij), and
(2.2)Cij=Mi⋉Nj,i=1,2,…,m,j=1,2,…,q,
where Mi=Rowi(M) denotes the ith row of the matrix M, and Nj=Colj(N) denotes the jth column of the matrix N.(6)
To use a matrix expression, we identify1~δ21, 0~δ22. Using this transformation, a logical function f:𝒟k→𝒟 becomes a function f:Δ2k→Δ2.(7)
Consider a fundamental unary logical function: Negation,¬P and five fundamental binary logical functions: Disjunction, P∨Q; Conjunction, P∧Q; Conditional, P→Q; Biconditional, P↔Q; Exclusive OR, P∨-Q. Their structure matrices are as follows:
(2.3)M¬=δ2[2,1];M∨=δ2[1,1,1,2];M∧=δ2[1,2,2,2];M→=δ2[1,2,1,1];M↔=δ2[1,2,2,1];M⊕:=M∨-=δ2[2,1,1,2].(8)
Given a logical functionf(x1,x2,…,xn), there exists a unique 2×2n matrix Mf, called the structure matrix, such that
(2.4)f(x1,x2,…,xn)=Mfx,
where x=⋉i=1nxi∈Δ2n.(9)
Letx∈Rt and A is a given matrix, then xA=(It⊗A)x.


## 3. Main Results

In this section, we will introduce several different definitions of Boolean derivatives. Using the Cheng product, we successfully convert the logical expression into the matrix expression. In addition, the relationships among different definitions of Boolean derivatives are obtained.In the following, we will introduce some definitions of Boolean derivatives for the logical functionf(x1,x2,…,xn).Definition 3.1 (see [19]).
One gets that(3.1)∂f∂xj=f(x1,…,xj,…,xn)⊕f(x1,…,xj⊕1,…,xn),
where P⊕Q denotes the “Exclusive OR” in logical calculation.
This definition has been proposed for a long time, and it can also be described as∂f / ∂xj =f(x1,…,xj-1,0,xj+1,…,xn)⊕f(x1,…,xj-1,1,xj+1,…,xn).Definition 3.2 (see [21]).
Letb be an n-variable vector and b=ei1⊕ei2⊕⋯⊕eik, i1,…,ik∈{1,2,…,n}, i1<i2<⋯<ik, e1=(1,0,0,…,0), e2=(0,1,0,…,0),…,anden=(0,0,…,0,1), define
(3.2)∂bf(x)=f(x)⊕f(x⊕b)=f(x1,…,xi1,…,xik,…,xn)⊕f(x1,…,xi1⊕1,…,xik⊕1,…,xn).Remark 3.3.
It is clear that Definition3.2 is a generalization of Definition 3.1. If k=1, that is, b=ei1, Definition 3.2 then degenerates to Definition 3.1.Definition 3.4 (see [19]).
Therefore,(3.3)∂f∂+xj=(x-j⊕f(x))∂f∂xj,∂f∂-xj=(xj⊕f(x))∂f∂xj.Remark 3.5.
The present Definition3.4 is called the directional Boolean derivative sometimes. This is meaningful. It considered the change in the arguments increase, decrease, or remain constant.
Letf(x)=f(x1,…,xn)=Mfx. Then, according to the definitions of the Boolean derivatives, we obtain the following representations:
(3.4)∂f∂xj=f(x1,…,xj,…,xn)⊕f(x1,…,xj⊕1,…,xn)=Mfx⊕Mfx1⋯M¬xj⋯xn=M⊕MfxMfx1⋯M¬xj⋯xn=M⊕MfxMf(I2j-1⊗M¬)x=M⊕Mf[I2n⊗(Mf(I2j-1⊗M¬))]Φnx,∂bf=f(x)⊕f(x⊕b)=f(x1,…,xi1,…,xik,…,xn)⊕f(x1,…,xi1⊕1,…,xik⊕1,…,xn)=Mfx⊕Mfx1⋯M¬xi1⋯M¬xik⋯xn=M⊕MfxMf(I2i1-1⊗M¬)(I2i2-1⊗M¬)⋯(I2ik-1⊗M¬)x1⋯xn=M⊕MfxMf∏i=i1ik‍(I2i-1⊗M¬)x=M⊕Mf[I2n⊗(Mf∏i=i1ik‍(I2i-1⊗M¬))]Φnx,
where Φn is the power-reducing matrix defined in [14].
In the following, we will discuss the relationships among the different definitions of Boolean derivatives by using the Cheng product.
First, we give a Lemma that will be used in the proof of Theorem3.7.Lemma 3.6.
Assume thata,b∈Δ2, then (a-⊕b)∨(a⊕b)=δ21.Proof.
One assumes that(3.5)(a-⊕b)∨(a⊕b)=MdM⊕a-bM⊕ab=MdM⊕M¬abM⊕ab=MdM⊕M¬(I4⊗M⊕)(ab)2=MdM⊕M¬(I4⊗M⊕)Mr22ab,
where
(3.6)Mr4=(δ4104⋯0404δ42⋯04⋮⋮⋱⋮0404⋯δ44)
is the power-reducing matrix defined in [14].
Throughout directional computation, we get that(3.7)(a-⊕b)∨(a⊕b)=δ21.
This completes the proof.Next, two Theorems are given to illustrate the relationships among the different definitions. Theorem3.7 shows the relationships of Definitions 3.1 and 3.4; Theorem 3.8 states the relationships between Definitions 3.1 and 3.2.Theorem 3.7.
One gets that(3.8)∂f∂+xj∨∂f∂-xj=∂f∂xj.Proof.
Therefore,(3.9)∂f∂+xj∨∂f∂-xj=(x-j⊕f(x))∂f∂xj∨(xj⊕f(x))∂f∂xj=(x-j⊕f(x))∨(xj⊕f(x))∂f∂xj.
According to Lemma3.6, one obtains that
(3.10)∂f∂+xj∨∂f∂-xj=∂f∂xj.
This completes the proof.Theorem 3.8.
Since,(3.11)∂∂x1(∂∂x2(⋯(∂f(x)∂xk)))=⨁1≤l≤kj1<⋯<jlj1,…,jl∈{i1,i2,…,ik}∂j1,…,jlf(x)=M⊕2k-1∏1≤l≤kj1<⋯<jlj1,…,jl∈{i1,i2,…,ik}MfxMf(I2j1-1⊗M¬)⋯(I2jl-1⊗M¬)x=M⊕2k-1∏1≤l≤kj1<⋯<jlj1,…,jl∈{i1,i2,…,ik}Mf[I2n⊗(Mf(I2j1-1⊗M¬)⋯(I2jl-1⊗M¬))]Φnx.Proof.
We prove the statement by induction onk.(1)
The formula is true fork=1,2.
Fork=1, it is obviously true.
Fork=2:
(3.12)∂∂x1(∂∂x2)=∂∂x1(f(x)⊕f(x⊕ei2))=f(x)⊕f(x⊕ei2)⊕f(x⊕ei1)⊕f(x⊕ei2⊕ei1)=M⊕3MfxMf(I2i2-1⊗M¬)xMf(I2i1-1⊗M¬)xMf(I2i1-1M¬)(I2i2-1⊗M¬)x.
While,(3.13)⨁1≤l≤kj1<⋯<jlj1,…,jl∈{i1,i2,…,ik}∂j1,…,jlf(x)=∂i1f(x)⊕∂i2f(x)⊕∂i1,i2f(x)=f(x)⊕f(x⊕ei1)⊕f(x)⊕f(x⊕ei2)⊕f(x)⊕f(x⊕ei1⊕ei2)=f(x)⊕f(x⊕ei1)⊕f(x⊕ei2)⊕f(x⊕ei1⊕ei2)=M⊕3MfxMf(I2i1-1⊗M¬)xMf(I2i1-1⊗M¬)xMf(I2i1-1M¬)(I2i2-1⊗M¬)x.
Thus, it’s true for k=1,2.
Assume that the statement is true fork=m:
(3.14)∂∂x1(∂∂x2(⋯(∂f(x)∂xm)))=⨁1≤l≤mj1<⋯<jlj1,…,jl∈{i1,i2,…,im}∂j1,…,jlf(x)=M⊕2m-1∏1≤l≤mj1<⋯<jlj1,…,jl∈{i1,i2,…,im}MfxMf(I2j1-1⊗M¬)⋯(I2jl-1⊗M¬)x=M⊕2m-1∏1≤l≤mj1<⋯<jlj1,…,jl∈{i1,i2,…,im}Mf[I2n⊗(Mf(I2j1-1⊗M¬)⋯(I2jl-1⊗M¬))]Φnx.
For k=m+1,
(3.15)∂∂x1(∂∂x2(⋯(∂f(x)∂xm+1)))=∂∂xm+1(∂∂x1(⋯(∂f(x)∂xm)))=(∂∂x1(⋯(∂f(x)∂xm)))⊕(∂∂x1(⋯(∂f(x⊕eim+1)∂xm))).
In addition,
(3.16)(∂∂x1(⋯(∂f(x⊕eim+1)∂xm)))=⨁1≤l≤mj1<⋯<jlj1,…,jl∈{i1,i2,…,im}∂j1,…,jlf(x⊕eim+1)=⨁1≤l≤mj1<⋯<jlj1,…,jl∈{i1,i2,…,im}f(x⊕eim+1)⊕f(x⊕ej1⊕⋯⊕ejl⊕eim+1)=M⊕2m-1∏1≤l≤mj1<⋯<jlj1,…,jl∈{i1,i2,…,im}{Mf(I2im+1-1⊗M¬)xMf(I2j1-1⊗M¬)⋯(I2jl-1⊗M¬)(I2im+1-1⊗M¬)x}.
Thus,
(3.17)∂∂x1(∂∂x2(⋯(∂f(x)∂xm+1)))=∂∂xm+1(∂∂x1(⋯(∂f(x)∂xm)))=(∂∂x1(⋯(∂f(x)∂xm)))⊕(∂∂x1(⋯(∂f(x⊕eim+1)∂xm)))=M⊕2m-1∏1≤l≤mj1<⋯<jlj1,…,jl∈{i1,i2,…,im}MfxMf(I2j1-1⊗M¬)⋯(I2jl-1⊗M¬)x⊕M⊕2m-1∏1≤l≤mj1<⋯<jlj1,…,jl∈{i1,i2,…,im}{Mf(I2im+1⊗M¬)xMf(I2j1-1⊗M¬)⋯(I2jl-1⊗M¬)(I2im+1-1⊗M¬)x}=M⊕2*(2m-1)+1∏1≤l≤m+1j1<⋯<jlj1,…,jl∈{i1,i2,…,im+1}MfxMf(I2j1-1⊗M¬)⋯(I2jl-1⊗M¬)x=M⊕2m+1-1∏1≤l≤m+1j1<⋯<jlj1,…,jl∈{i1,i2,…,im+1}MfxMf(I2j1-1⊗M¬)⋯(I2jl-1⊗M¬)x=M⊕2m+1-1∏1≤l≤m+1j1<⋯<jlj1,…,jl∈{i1,i2,…,im+1}Mf[I2n⊗(Mf(I2j1-1⊗M¬)⋯(I2jl-1⊗M¬))]Φnx.
This completes the proof.Remark 3.9.
By converting the logical calculation into matrix product, it is more convenient for the calculation of high-dimensional systems.


## 4. Example

In this part, we will discuss the application of the main results in the present paper. Rule 150 is one of the eight elementary automata rules. It was introduced by Stephen Wolfram in 1983. Vichniac [12] also investigated its property. In the following, we will discuss the rule 150 using the Cheng product method.In peripheral one dimensional cellular automata, the XOR rule is(4.1)xit=xi-1t-1⊕xit-1⊕xi+1t-1.If we define a Boolean cellular automata withN cells by a global mapping
(4.2)F:{0,1}N↦{0,1}N.A local transition rulef of F is given as follows: it consists of its two neighborhood and the considered cell itself
(4.3)f(x1,x2,x3)=x1⊕x2⊕x3,
then
(4.4)f(x1,x2,x3)=M⊕2x1x2x3=Mfx,whereMf=M⊕2,x=x1x2x3.Define the Boolean derivative ofF as the N×N matrix with Fij′=∂xit/∂xjt-1.According to the definition of Boolean derivative, it is easy to see thatFij′=0 for j<i-1andi+1<j.Wheni-1≤j≤i+1, from the definition and the matrix expression of Boolean derivative, one can see that
(4.5)∂f∂xjt-1=M⊕Mfxi-1t-1xit-1xi+1t-1Mf(I2j-1⊗M¬)xi-1t-1xit-1xi+1t-1=M⊕3(I8⊗M⊕2(Ij-1⊗M¬))Mr8xi-1t-1xit-1xi+1t-1.Throughout the directional computation, we can get the following Jacobian matrix:(4.6)F′=[1100⋯011110⋯000111⋯00⋮⋮⋱⋱⋱⋮⋮⋯⋯⋯⋯1111⋯⋯⋯⋯11].From the Jacobian matrix, one can see that the new value of the cell is determined by its two neighbors and the cell itself. In the Jacobian matrix, the 1′s shows us that the rule 150 is linearly dependent of the augments, respectively.


## 5. Discussion

Boolean derivative is an important topic in the research of Boolean function. It has wide applications in different fields. There are several different definitions about the Boolean derivatives. Each definition has its own meaning and application in respective domain. In this paper, we introduce several definitions of Boolean derivatives. Furthermore, the relationships among them are presented. We show the meanings of them, and the matrix expressions of them are also given.Throughout the paper, the main tool used is the semitensor product, that is, Cheng product. It is a very useful tool. It generalizes the matrix product. In classic matrix product, it is necessary to guarantee that the number of columns of the left matrix matches the number of rows of the right matrix. However, it is not necessary in Cheng product. Cheng product has most of the properties of matrix product, and it has many other new advantages. Cheng product has been now used in many research. In this paper, Cheng product is applied in obtaining the relationship among different definitions. The calculation of logic variables has been converted into matrix product. It is interesting and meaningful. Using the results obtained, the application of Boolean derivative in cryptography and other fields might be extended.


## 6. Conclusion

In this paper, firstly we have introduced several definitions of Boolean derivatives. Then, we have given formulas to calculate Boolean derivatives by using the semitensor product, that is, Cheng product. We have also investigated the relationship among different definitions of Boolean derivatives. At last, an application is presented to illustrate the main results.



---

*Source: 748343-2012-10-17.xml*