报告——逻辑系统的代数状态空间表示.pdf
报告——逻辑系统的代数状态空间表示.pdf
Algebraic State Space Representation of Logical Systems Series One, Lesson Two Lecturer: Jun-e Feng (School of Mathematics, Shandong University) Center of STP Theory and Its Applications August 15-23, 2020 LiaoCheng University, LiaoCheng, Shandong, P.R. China Outline 1 Preliminaries 2 Propositional logic 3 Structure matrix of a logical function 4 Algebraic expression of logical systems 5 Example and Homework 6 References 2 / 59 1. Preliminaries + Notations • D := {0, 1}, where 1 ∼ T and 0 ∼ F. 1 • Dk := {0, k−1 , . . . , k−2 k−1 , 1}, D2 = D. • δni : the i-th column of the identity matrix In . • ∆k := {δk1 , . . . , δkk }. Denote ∆ := ∆2 . • For a matrix L ∈ Mm×n , Coli (L) := Lδni , Rowj (L) := (δmj )T L, Col(L) := {Coli (L), i = 1, . . . , n}, Row(L) := {Rowj (L), j = 1, . . . , m}. • Ln×r := {L : L ∈ Mn×r and Col(L) ⊂ ∆n }. And any matrix L ∈ Ln×r is called a logical matrix. • If L ∈ Ln×r , then it is expressed and briefly denoted as L = [δni1 , δni2 , . . . , δnir ] and L = δn [i1 , i2 , . . . , ir ]. • ⊗: the Kronecker product. 3 / 59 + Review of several matrix products Traditional matrix product Assume A = (aij ) ∈ Mm×n , B = (bij ) ∈ Mn×q §define the traditional product of matrices A and B as AB = (cij ) ∈ Mm×q where cij = (1) Pn i=1 aik bkj §i = 1, 2, · · · m; j = 1, 2, · · · q. 4 / 59 Kronecker product Assume A = (aij ) ∈ Mm×n , B = (bij ) ∈ Mp×q §then the Kronecker product of matrices A and B as a11 B a12 B . . . a1n B a21 B a22 B . . . a2n B A⊗B= . (2) .. .. ∈ Mmp×nq . .. .. . . . am1 B am2 B ... amn B 5 / 59 Property 1 of Kronecker product If A ∈ Mm×n , B ∈ Mp×q , C ∈ Mn×r , D ∈ Mq×s §then (A ⊗ B)(C ⊗ D) = (AC) ⊗ (BD), particularly, A ⊗ B = (A ⊗ Ip )(In ⊗ B). Property 2 of Kronecker product 1 Given two vectors X ∈ Rn , Y ∈ Rn , we have Vc (XY T ) = Y ⊗ X. 2 If A ∈ Mm×p , B ∈ Mp×q , C ∈ Mq×n , then Vc (ABC) = (CT ⊗ A)Vc (B). Vc (A) = (Col1 (A)T , Col2 (A)T , . . . , Colp (A)T )T . 6 / 59 Khatri-Rao product Assume n, m, p, q, ni , mj , pi , qj , (i = 1 · · · r, j = 1 · · · s) are all positive integer§and satisfy r X mi = m, s X nj = n, j=1 i=1 r X pi = p, i=1 s X qj = q. j=1 A = (Aij ) ∈ Mm×n , B = (Bij ) ∈ Mp×q are block matrices, where Aij ∈ Mmi ×nj , Bij ∈ Mpi ×qj , that is, A11 A21 A= . .. A12 A22 .. . ··· ··· .. . A1s B11 B21 A2s .. , B = .. . . B12 B22 .. . ··· ··· .. . B1s B2s .. . . Ar1 Ar2 ··· Ars Br2 ··· Brs Br1 Define the Khatri-Rao product of matrices A and B asµ A ∗ B = (Aij ⊗ Bij ) ∈ Mu×v , Pr Ps where u = i=1 mi pi , v = j=1 nj qj . (3) 7 / 59 Remark about Khatri-Rao product 1 2 If r = s = 1, then A ∗ B = A ⊗ B; If A ∈ Mm×r , B ∈ Mn×r §A = B1 B2 · · · Br , then A1 A2 A ∗ B = A1 ⊗ B1 ··· Ar ⊗ Br . A2 ⊗ B2 ··· Ar , B = 8 / 59 Hadamard product Assume A = (aij ), B = (bij ) ∈ Mm×n §then the Hadamard product of A and B is defined as A B = (aij bij ) ∈ Mm×n . (4) Particularly, if m = p, n = q, m1 = m2 = · · · = mr = n1 = n2 = · · · = ns = 1 in the definition of Khatri-Rao product, then A ∗ B = A B. 9 / 59 + Semi-tensor product Definition 1 Let A ∈ Mm×n , B ∈ Mp×q , t = lcm(n, p). Then the semi-tensor product (STP) of A and B is A n B := (A ⊗ It/n )(B ⊗ It/p ), where lcm(n, p) represents the least common multiple of n and p. Problem 1 In Definition 1, what does happen to the product above if t is any other common multiple of n and p? 10 / 59 + Pseudo-Commutativity Lemma 1 (1) Given a matrix A ∈ M and a column vector x ∈ Vt . Then x n A = (It ⊗ A)x, A n x = x(It ⊗ A). (2) Given two column vectors x ∈ Vn , y ∈ Vm . Then W[n,m] n x n y = y n x, x n y n W[n,m] = y n x, where W[n,m] is a swap matrix. 11 / 59 2. Propositional logic + Propositions Example 1 Consider the following statements. 1. A dog has 4 legs; 2. The snow is black; 3. There is another human in the universe. 4. Bridge, stream, village. It is not hard to find that statement 1 is “true” and statement 2 is “false”. Statement 3 may be “true” or “false”, although we still do not know the answer. Thus, statements 1-3 are all propositions. Statement 4 is not a proposition, because neither “true” nor “false” is meaningfully applied to it. 12 / 59 + Logical operators • Negation ¬ (Ä). The negation of proposition A, denoted by ¬A, is its opposite. A is true if and only if ¬A is false, and vice versa. • Conjunction ∧(Ü ). The conjunction of A and B, denoted by A ∧ B, is a proposition that is true only if A and B are true. • Disjunction ∨(Û ). The disjunction of A and B, denoted by A ∨ B, is a proposition that is true if at least one of A and B is true. • Conditional →(%º). The conditional of A and B, denoted by A → B, means that A implies B, i.e., if A then B. • Biconditional ↔( Š). The biconditional of A and B, denoted by A ↔ B, means that A is true if and only if B is true. • ······ 13 / 59 + Logical function Definition 2 1. A logical variable is a variable which takes value from D. 2. A set of logical variables x1 , . . . , xn are independent, if for any fixed values xj , j 6= i, the logical variable xi can still take value either 1 or 0. 3. A logical function of logical variable x1 , . . . , xn is a logical expression involving x1 , . . . , xn and some possible statements (called constants), joined by logical operators. Hence, a logical function is mapping f : Dn → D. It is also called an n-ary operator. Example 2 f (p, q, r) = (¬p) → (q ∨ r) is a logical function of p, q, r. 14 / 59 ¯ , ↑ and ↓ Table 1: Truth table of ¬, ∧, ∨, →, ↔, ∨ x y ¬x ¬y ∧ ∨ → ↔ ¯ ∨ ↑ ↓ 1 1 0 0 1 0 1 0 0 0 1 1 0 1 0 1 1 0 0 0 1 1 1 0 1 0 1 1 1 0 0 1 0 1 1 0 0 1 1 1 0 0 0 0 ¯ is logical operator “exclusive or”(EOR ɽ); ∨ ↑ is “not and”(NAND †š); ↓ is “not or”(NOR ½š). Problem 2 Is there any other 2−ary logical operator? How many? 15 / 59 + Normal Form Definition 3 Let {p1 , p2 , . . . , pn } be a set of logical variables. Define a set of logical variables by also including their negations, as follows: P := {p1 , ¬p1 , p2 , ¬p2 , . . . , pn , ¬pn }. 1. If c := Vs 2. If d := Ws i=1 ai , ai ∈ P, then c is called a basic conjunctive form. i=1 ai , ai ∈ P, then d is called a basic disjunctive form. Ws 3. If m := i=1 ci , where ci are basic conjunctive form, then m is called a disjunctive form. Vs 4. If n := i=1 di , where di are basic disjunctive form, then m is called a conjunctive form. 16 / 59 Lemma 2 Any logical expression can be expressed in disjunctive normal form as well as conjunctive normal form. (about the proof, see page 12 of [1]) Example 3 Consider f (p, q, r) = ((p ∨ q) → ¬r) → ((r → p) ∧ (r ∨ q)). Its disjunctive normal form is: f = (p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r) ∨ (p ∧ ¬q ∧ r) ∨ (¬p ∧ q ∧ r) ∨ (¬p ∧ q ∧ ¬r), and its conjunctive normal form is: f = (¬p ∨ q ∨ r) ∧ (p ∨ q ∨ ¬r) ∧ (p ∨ q ∨ r). [1] D. Z. Cheng, H. S. Qi, Z. Q. Li, Analysis and Control of Boolean Networks: A Semi-tensor Product Approach, London, Springer, 2011. 17 / 59 3. Structure matrix of a logical function + Structure matrix of a logical operator To use matrix expression of logic, we identify 1 0 1 ∼ δ21 = , 0 ∼ δ22 = , 0 1 and call them the vector forms of logic values. Then in vector form, an n-ary logical function f becomes a mapping f : ∆n → ∆. That is, D ∼ ∆, Similarly, f : Dn → D ⇔ f : ∆n → ∆. 18 / 59 Definition 5 Let f (x1 , . . . , xn ) be an n-ary logical function. Lf ∈ L2×2n is called the structure matrix of f , if in vector form we have f (x1 , . . . , xn ) = Lf nni=1 xi . (5) 19 / 59 The structure matrices of some fundamental operators: M¬ := Mn = δ2 [2 1], M∨ := Md = δ2 [1 1 1 2], M∧ := Mc = δ2 [1 2 2 2], M→ := Mi = δ2 [1 2 1 1], M↔ := Me = δ2 [1 2 2 1]. To check the first one Check the vector equation ¬p = Mn p, where p is the vector form of a logical variable, and 0 1 Mn = δ2 [2 1] = . 1 0 1) When p = T, we have p = T ∼ δ21 =⇒ Mn p = δ22 ∼ F. 2) When p = F, we have p = F ∼ δ22 =⇒ Mn p = δ21 ∼ T. 20 / 59 + Power-reducing matrices Lemma 3 Given a logical variable x ∈ ∆. Then x2 = Mr x, where Mr := δ4 [1 4] is called the power-reducing matrix. To check Lemma 3 1) When x = δ21 , then 1 1 0 0 1 1 2 x = = 0 = 0 0 0 0 0 0 0 1 = Mr x, 0 0 1 2) When x = δ22 , the proof is omitted. Problem 3 If x ∈ ∆k , write the corresponding power-reducing matrix Mr,k . 21 / 59 Definition 6 A matrix L ∈ Ln×r is called logical matrix, if Coli (L) ∈ ∆n for any 1 ≤ i ≤ r. Lemma 4 1. A swap matrix is a logical matrix, i.e., W[m,n] ∈ Lmn×mn ; 2. The identity matrix is a logical matrix, i.e., Im ∈ Lm×m ; 3. The power-reducing matrix is a logical matrix, i.e., Mr ∈ L4×2 ; 4. If L ∈ L, then L ⊗ In ∈ L, In ⊗ L ∈ L; 5. If A, B ∈ L, then A n B ∈ L. (For any A ∈ Rm×n , we have Aδni = Coli (A)) 22 / 59 Proposition 1 Let f (x1 , . . . , xn ) be an n-ary logical function with logical variables x1 , . . . , xn . Then, f can be expressed as f (x1 , . . . , xn ) = ni ξi , where ξi ∈ {Mn , Md , Mc , x1 , . . . , xn }. Proof outline of Proposition 1 1. disjunctive (conjunctive) form; 2. the structure matrices of logical operators ∨, ∧ and ¬. 23 / 59 Example 4 Let f (p, q, r) = (p ∧ ¬q) ∨ (r ∧ p). Then in vector form we have f (p, q, r) = (p ∧ ¬q) ∨ (r ∧ p) = Md (Mc p(Mn q))(Mc rp) = Md Mc pMn qMc rp. 24 / 59 Based on Proposition 1, we have Proposition 2 Let f (x1 , . . . , xn ) be an n-ary logical function. Then there exists a unique structure matrix Lf ∈ L2×2n such that (5) holds. Proof outline of Proposition 2 1. Using xi M = (I ⊗ M)xi to move all variables xi to the rear; 2. Using swap matrix to change the order of two variables xi and xj ; 3. Using power-reducing matrix to reduce the powers of xi to 1; 4. Prove Lf ∈ L2×2n ; 5. Prove the uniqueness. 25 / 59 Example 5 In Example 4 we have already have f (p, q, r) = Md Mc pMn qMc rp. We continue by converting this into canonical form: f (p, q, r) = Md Mc pMn qMc rp = Md Mc (I2 ⊗ Mn )pqMc rp = Md Mc (I2 ⊗ Mn )(I4 ⊗ Mc )pqrp = Md Mc (I2 ⊗ Mn )(I4 ⊗ Mc )pW[2,4] pqr = Md Mc (I2 ⊗ Mn )(I4 ⊗ Mc )(I2 ⊗ W[2,4] )p2 qr = Md Mc (I2 ⊗ Mn )(I4 ⊗ Mc )(I2 ⊗ W[2,4] )Mr pqr = Mf pqr. 26 / 59 Remark 1 Disjunctive (conjunctive) form is not necessary. Example 6 Let f (x, y) = (x ∨ y) → (x ∧ y). Then in vector form we have f (x, y) = (x ∨ y) → (x ∧ y) = Mi Md xyMc xy = Mi Md (I4 ⊗ Mc )xyxy = Mi Md (I4 ⊗ Mc )xW[2] xy2 = Mi Md (I4 ⊗ Mc )(I2 ⊗ W[2] )x2 y2 . Using the power-reducing matrix, we have f (x, y) = Mi Md (I4 ⊗ Mc )(I2 ⊗ W[2] )x2 y2 = Mi Md (I4 ⊗ Mc )(I2 ⊗ W[2] )Mr xMr y = Mi Md (I4 ⊗ Mc )(I2 ⊗ W[2] )Mr (I2 ⊗ Mr )xy. Thus, L = Mi Md (I4 ⊗ Mc )(I2 ⊗ W[2] )Mr (I2 ⊗ Mr ) is the structure matrix of f (x, y). 27 / 59 + Another computation of structure matrix Example 7 Let f (p, q, r) = (¬p) → (q ∨ r). The truth table is derived about logical function f (p, q, r). Table 2: Truth table of f (p, q, r) p q r ¬p q∨r f 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 28 / 59 Definition 4 Let f (x1 , . . . , xn ) be an n-ary logical function. Denote the column of f in its truth table by Tf , and call it the truth vector of f . Computation of structure matrix Lf Row1 (Lf ) := TfT , Row2 (Lf ) := ¬Row1 (Lf ), where ¬Row1 (Lf ) is derived by taking negation on each elements of Row1 (Lf ), and Tf is the truth vector of logical operator f . 29 / 59 Example 7 (continuing) From Table 2, we have the truth vector of f Tf = [1 1 1 1 1 1 1 0]T . Thus the structure matrix of f is obtained 1 1 1 1 1 1 Lf = 0 0 0 0 0 0 1 0 0 1 = δ2 [1, 1, 1, 1, 1, 1, 1, 2] Notice that the value order of all variables in the truth table can not be changed when using truth vector to deduce the structure matrix. 30 / 59 Example 7 (continuing) In vector form, we have f (p, q, r) = Lf (p n q n r) 1 1 1 1 = 0 0 0 0 1 0 1 0 1 0 0 1 pnqnr Table 3: Truth table of f (p, q, r) (p, q, r) pnqnr f (1, 1, 1) ∼ (δ21 , δ21 , δ21 ) (1, 1, 0) ∼ (δ21 , δ21 , δ22 ) (1, 0, 1) ∼ (δ21 , δ22 , δ21 ) (1, 0, 0) ∼ (δ21 , δ22 , δ22 ) (0, 1, 1) ∼ (δ22 , δ21 , δ21 ) (0, 1, 0) ∼ (δ22 , δ21 , δ22 ) (0, 0, 1) ∼ (δ22 , δ22 , δ21 ) (0, 0, 0) ∼ (δ22 , δ22 , δ22 ) δ81 δ82 δ83 δ84 δ85 δ86 δ87 δ88 1 ∼ δ21 1 ∼ δ21 1 ∼ δ21 1 ∼ δ21 1 ∼ δ21 1 ∼ δ21 1 ∼ δ21 0 ∼ δ22 31 / 59 + Dummy matrices The dummy matrices are defined as Mu = δ2 [1 1 2 2], Mv = δ2 [1 2 1 2]. Lemma 5 In vector form we have Mu xy = x, Mv xy = y. 32 / 59 Check Lemma 5 1) When x = δ21 , then 1 1 0 Mu xy = 0 0 1 0 1 2) When x = δ22 , then 1 1 0 Mu xy = 0 0 1 0 1 1 0 0 1 y= y= 1 0 1 0 0 1 0 1 y= y= 1 0 0 1 = x, = x, Therefore, Mu xy = x is proved. 3) No matter x = δ21 or x = δ22 , we all have Mv x = I2 . Hence, it is easy to have Mv xy = y. Problem 4 In Lemma 5, if vectors x and y are all in ∆k , then write the dummy matrices. 33 / 59 Example 8 Consider logical functions f1 (x1 , x2 , x3 ) = x1 ∧ x2 , f2 (x1 , x2 , x3 ) = x2 ∨ x3 . Using dummy matrices, the vector forms of f1 (x1 , x2 , x3 ) and f2 (x2 , x2 , x3 ) can be expressed as f1 (x1 , x2 , x3 ) = Mc x1 x2 = Mc x1 Mu x2 x3 = Mc (I2 ⊗ Mu )x1 x2 x3 , f2 (x1 , x2 , x3 ) = Md x2 x3 = Md Mv x1 x2 x3 . 34 / 59 + Algebraic form⇒ Logical form How can we get the logical form for a given algebraic form? f (x1 , x2 , · · · , xn ) = Mf nni=1 xi . Algorithm 1 Let f (x1 , x2 , · · · , xn ) be logical form. Its algebraic form is f (x1 , x2 , · · · , xn ) = Mf nni=1 xi , where Mf = δ2 [a1 , a2 , · · · , a2n ]. Its logical form can be calculated as follows: 35 / 59 Step 1: Split the structure matrix into 2n−1 equal blocks as Mf = [δ2 [a1 , a2 ], δ2 [a3 , a4 ], · · · , δ2 [a2n −1 , a2n ]] := [L1 , L2 , · · · , L2n−1 ]. Step 2: For every j = {1, 2, . . . , 2n−1 }, factorize δ2j n−1 as αj αj αj δ2j n−1 = δ2 1 δ2 2 · · · δ2 n−1 . 36 / 59 Step 3: The logical (disjunctive normal) form of f (x1 , x2 , · · · , xn ) is constructed as f (x1 , x2 , · · · , xn ) = n−1 2_ ^ n−1 j=1 i=1 λji xi ^ φj (xn ) , where λji xi = xi , αij = 1 ¬xi , αij = 2, 1, Lj = δ2 [1, 1] xn , Lj = δ2 [1, 2] φj (xn ) = ¬xn , Lj = δ2 [2, 1] 0, Lj = δ2 [2, 2]. Remark 2 Logical expression of a logical function is not unique. 37 / 59 Example 9 Given ¯ x2 ) → (¬x2 ↔ x3 ), f (x1 , x2 , x3 ) = (x1 ∨ find its disjunctive normal form. Derive its structure matrix first: Mf = δ2 [1, 1, 1, 2, 2, 1, 1, 1]. Then f (x1 , x2 , x3 ) = [x1 ∧ x2 ∧ φ1 (x3 )]∨ [x1 ∧ ¬x2 ∧ φ2 (x3 )]∨ [¬x1 ∧ x2 ∧ φ3 (x3 )]∨ [¬x1 ∧ ¬x2 ∧ φ4 (x3 )]. 38 / 59 Example 9 (continuing) According to Algorithm 1, we have φ1 = φ4 = 1, φ2 = x3 , φ3 = ¬x3 . Thus we have f (x1 , x2 , x3 ) = [x1 ∧ x2 ]∨ [x1 ∧ ¬x2 ∧ x3 ]∨ [¬x1 ∧ x2 ∧ ¬x3 ]∨ [¬x1 ∧ ¬x2 ]. 39 / 59 4. Algebraic expression of logical systems Definition 7 A static logical equations is expressed as f1 (x1 , . . . , xn ) = c1 , f2 (x1 , . . . , xn ) = c2 , .. . fm (x1 , . . . , xn ) = cm , (6) where fi is a logical function, xi is a logical argument (unknown), and ci is a logical constant. A set of logical constants di , i = 1, . . . , n, which makes xi = di satisfying (6), is said to be a solution of logical equations (6). 40 / 59 Lemma 6 Assume y = My nni=1 xi , z = Mz nni=1 xi , where xi ∈ ∆, i = 1, 2, . . . , n, My ∈ L2×2n and Mz ∈ L2×2n . Then yz = (My ∗ Mz ) nni=1 xi , where My ∗ Mz := [Col1 (My ) ⊗ Col1 (Mz ), . . . , Col2n (My ) ⊗ Col2n (Mz )]. Remark 3 Result in Lemma 6 can be extend to multiple case or logical equations (6). 41 / 59 Proof outline of Lemma 6 1. yz = My nni=1 xi Mz nni=1 xi = My (I2n ⊗ Mz )Mr,2n nni=1 xi = Myz nni=1 xi , where Myz ∈ L4×2n . 2. Assuming nni=1 xi = δ2r n (1 ≤ r ≤ 2n is arbitrary), have y = Colr (My ) and z = Colr (Mz ). 3. Colr (Myz ) = yz = Colr (My ) n Colr (Mz ) = Colr (My ) ⊗ Colr (Mz ). 42 / 59 Example 10 Consider the following logical equations x1 ∧ x2 = 0, x2 ∨ x3 = 1, x3 ↔ x1 = 1. (7) Denote x = x1 x2 x3 . Then the vector form of each equation is expressed as L1 x = Mc (I2 ⊗ Mu )x = δ22 , L2 x = Md Mv x = δ21 , L3 x = Me W[2] Mu x = δ21 . According to Lemma 6, the vector form of equations (7) is Lx = (L1 ∗ L2 ∗ L3 )x = δ85 . 43 / 59 + Logical dynamic systems Boolean network (BN) C A A(t + 1) = B(t) ∧ C(t) B(t + 1) = ¬A(t) C(t + 1) = B(t) ∨ C(t) B Figure 1: BN Boolean control network (BCN) u1 A C u2 B y A(t + 1) = B(t) ∧ u1 (t) B(t + 1) = C(t) ∨ u2 (t) C(t + 1) = A(t) y(t) = ¬C(t) Figure 2: BCN 44 / 59 Boolean network x (t + 1) = f1 (x1 (t), · · · , xn (t)) 1 .. . x (t + 1) = f (x (t), · · · , x (t)), x ∈ D, n n 1 n (8) i Boolean control network x1 (t + 1) = f1 (x1 (t), · · · , xn (t), u1 (t), · · · , um (t)) .. . xn (t + 1) = fn (x1 (t), · · · , xn (t), u1 (t), · · · , um (t)), yj (t) = hj (x(t)), j = 1, · · · , p, (9) where xi , ui , yi ∈ D. 45 / 59 Proposition 3 (Algebraic form of dynamic logical network) Boolean network (8) has algebraic form x(t + 1) = Lx(t), (10) where x(t) = nni=1 xi (t), L ∈ L2n ×2n . Boolean control network (9) has algebraic form ( x(t + 1) = Lu(t)x(t), y(t) = Hx(t), (11) p where x(t) = nni=1 xi (t), u(t) = nm i=1 ui (t), y(t) = ni=1 yi (t), L ∈ L2n ×2n+m , H ∈ L2p ×2n . 46 / 59 Proof outline of BN case in Proposition 3 1. xi (t + 1) = Li nni=1 xi . 2. nni=1 xi (t +1) = (L1 nni=1 xi )n(L2 nni=1 xi )n· · ·n(Ln nni=1 xi ) := Lnni=1 xi . 3. Assuming nni=1 xi = δ2r n (1 ≤ r ≤ n), have xi (t + 1) = Colr (Li ) . 4. Colr (L) = nni=1 xi (t + 1) = nni=1 Colr (Li ) = ⊗ni=1 Colr (Li ). 47 / 59 Example 11 Consider the Boolean network in Figure 1, we have L = δ8 3 7 7 8 1 5 5 6 . Consider the Boolean control network in Figure 2, we have L = δ8 [1 1 5 5 2 2 6 6 1 3 5 7 2 4 6 8 5 5 5 5 6 6 6 6 5 7 5 7 6 8 6 8]; H = δ2 [2 1 2 1 2 1 2 1]. 48 / 59 + General logical networks I k-valued logical networks x1 (t + 1) = f1 (x1 (t), · · · , xn (t)) .. . x (t + 1) = f (x (t), · · · , x (t)), n n 1 (12) n where xi ∈ Dk . k-valued logical network (12) has algebraic form x(t + 1) = Lx(t), (13) where x(t) = nni=1 xi (t), L ∈ Lkn ×kn . 49 / 59 + General logical networks II Mix-valued logical networks x1 (t + 1) = f1 (x1 (t), · · · , xn (t)) .. . x (t + 1) = f (x (t), · · · , x (t)), n n 1 (14) n where xi ∈ Dki . Mix-valued logical network (14) has algebraic form (15) x(t + 1) = Lx(t), where x(t) = nni=1 xi (t), L ∈ Lkn ×kn and k = Qn i=1 ki . 50 / 59 + Appendix 1 Defined the k-value power-reducing matrix as 1 δk 0 · · · 0 0 δk2 · · · 0 1 2 k Mr,k = . .. . . .. = diag{δk , δk , · · · , δk } .. . . . 0 0 ··· δkk Lemma 7 Given a logical variable x ∈ ∆r,k . Then x2 = Mr,k x. 51 / 59 Proof of Lemma 7 Assume x = δki , then it is easy to have 0 0 .. i − 1 ... i−1 . 0 0 2 = 1 x = 1 0 0 . k − i ... k−i .. 0 0 0k .. . i − 1 0k i , δk 0k .. k − i . 0k 52 / 59 Proof of Lemma 7 (continuning) δk1 0 .. . Mr,k x = 0 . .. 0 0 δk2 .. . ··· ··· .. . 0 0 .. . ··· ··· .. . 0 .. . ··· .. . δki .. . ··· .. . 0 ··· 0 ··· 0 0 .. . δki = 0 .. . k δk 0k .. . i − 1 0k i . δk 0k .. k − i . 0k 53 / 59 + Appendix 2 A swap matrix of dimension (m, n)-is defined as follows: W[m,n] : = In ⊗ δm1 , In ⊗ δm2 , · · · , In ⊗ δmm = δn1 n δm1 · · · δnn n δm1 · · · δn1 n δmm · · · δnn n δmm Im ⊗ (δn1 )T .. = . . Im ⊗ (δnn )T Swap matrices have many properties, see pp:38-41 of reference [1]. For example (11) W[2,3] = (12) (13) (21) (22) (23) (11) 1 0 0 0 0 0 0 0 0 1 0 0 (21) 0 1 0 0 0 0 (12) 0 0 0 0 1 0 (22) 0 0 1 0 0 0 (13) (23) 0 0 0 0 0 1 54 / 59 5. Example and Homework Example 12 A says “B is a liar”, B says “C is a liar”, C says “Both A and B are liars”. Who is a liar? Denote T ∼ 1 ∼ δ21 and D ∼ 0 ∼ δ22 representing honest and not being honest, respectively. 1 Define three logical variables: p: A is honest, or not; q: B is honest, or not; r: c is honest, or not. 2 Have p ↔ ¬q; q ↔ ¬r; r ↔ (¬p ∧ ¬q). 3 The problem is equivalent to when the following logical equation has solution. (p ↔ ¬q) ∧ (q ↔ ¬r) ∧ (r ↔ (¬p ∧ ¬q)) = 1. 55 / 59 Example (continuing) 4 The algebraic form of the logical equation above is Mc2 Me pMn qMe qMn rMe rMn pMn q = δ21 . 5 Via computing, derive that Lpqr = δ21 with 0 0 0 0 0 1 0 L= 1 1 1 1 1 0 1 0 1 . 6 It is clear that the algebraic equation above has unique solution: 0 1 0 p= , q= , r= , 1 0 1 that is to say, A and C are both liars, only B is honest. 56 / 59 Homework 1 Answer Problems 1-4 above. 2 Prove the algebraic forms of k (or mix) valued logical networks. 3 Given an algebraic form Lx with x = nni=1 xi and L ∈ L2n ×2n . a. Can we derive its logical conjunctive normal form? b. How to get it? 57 / 59 6. References [1] D. Z. Cheng, H. S. Qi, Z. Q. Li, Analysis and Control of Boolean Networks: A Semi-tensor Product Approach, London, Springer, 2011. [2] D. Z. Cheng, H. S. Qi, Y. Zhao, An introduction to semi-tensor product of matrices and its application, Singapore, World Scientific, 2012. [3] §“Чàö‘§Ý §2007. ŒÜþÈ: n؆A^§ ®§‰Æч [4] http://lsc.amss.ac.cn/ dcheng/ (Publications, STP Toolbox, Courses, Preprint) 58 / 59 Thanks for your attention! Q&A 59 / 59