Access the full text.
Sign up today, get an introductory month for just $19.
N. Bshouty (1995)
Exact Learning Boolean Function via the Monotone TheoryInf. Comput., 123
M. Davio, J. Deschamps, A. Thayse (1978)
Discrete and switching functions
W. Gottschalk (1953)
The theory of quaternialtyJournal of Symbolic Logic, 18
O. Ekin, S. Foldes, P. Hammer, L. Hellerstein (2000)
Equational characterizations of Boolean function classesDiscret. Math., 211
P. Hammer, S. Rudeanu (1968)
Boolean Methods in Operations Research and Related Areas
S. Foldes, P. Hammer (2002)
Disjunctive and conjunctive representations in finite lattices and convexity spacesDiscret. Math., 258
P. Hammer, A. Kogan (1992)
Horn Functions and Their DNFsInf. Process. Lett., 44
(1992)
Horn functions and their DNF's. Information Processing Lette
E. Boros, P. Hammer, M. Minoux, David Rader (1999)
Optimal Cell Flipping to Minimize Channel Density in VLSI Design and Pseudo-Boolean OptimizationDiscret. Appl. Math., 90
W. Quine (1955)
A Way to Simplify Truth FunctionsAmerican Mathematical Monthly, 62
S. Foldes, P. Hammer (2000)
Monotone, Horn and Quadratic Pseudo-Boolean FunctionsJ. Univers. Comput. Sci., 6
Horand Störmer (1990)
Binary functions and their applications
A. Fraenkel, P. Hammer (1984)
Pseudo-Boolean Functions and Their GraphsNorth-holland Mathematics Studies, 87
E. Boros, T. Ibaraki, K. Makino (1999)
Logical Analysis of Binary Data with Missing BitsArtif. Intell., 107
E. Boros, Y. Crama, P. Hammer (1990)
Polynomial-time inference of all valid implications for Horn and related formulaeAnnals of Mathematics and Artificial Intelligence, 1
E. Boros, V. Gurvich, P. Hammer, T. Ibaraki, A. Kogan (1995)
Decomposability of Partially Defined Boolean FunctionsDiscret. Appl. Math., 62
(1979)
A generalized consensus approach to non-linear 0-1 optimization
Van Vel (1993)
Theory of convex structures
(2011)
627-631 Fuzzy Inf
Fuzzy Inf. Eng. (2011) 3: 275-291 DOI 10.1007/s12543-011-0083-8 ORIGINAL ARTICLE Properties of Quasi-Boolean Function on Quasi-Boolean Algebra Yang-jin Cheng · Lin-xi Xu Received: 26 February 2010/ Revised: 29 July 2011/ Accepted: 15 August 2011/ © Springer-Verlag Berlin Heidelberg and Fuzzy Information and Engineering Branch of the Operations Research Society of China Abstract In this paper, we investigate the following problem: give a quasi-Boolean function Ψ(x ,··· , x ) = (a ∧ C) ∨ (a ∧ C )∨···∨ (a ∧ C ), the term (a ∧ C) 1 n 1 1 p p can be deleted from Ψ(x ,··· , x )? i.e., (a ∧ C) ∨ (a ∧ C )∨···∨ (a ∧ C ) = 1 n 1 1 p p (a ∧ C )∨···∨ (a ∧ C )? When a = 1 : we divide our discussion into two cases. 1 1 p p (1) (Ψ, C) = ∅, C can not be deleted ; (Ψ, C) ∅, if S ∅ (1 ≤ i ≤ q), 1 1 then C can not be deleted, otherwise C can be deleted. When a = m : we prove the following results: (m∧C)∨(a ∧C )∨···∨(a ∧C ) = (a ∧C )∨···∨(a ∧C ) ⇐⇒ 1 1 p p 1 1 p p (m∧ C)∨ C ∨···∨ C = C ∨···∨ C . Two possible cases are listed as follows, (1) 1 p 1 p (ψ, C) = ∅, the term (m∧C) can not be deleted; (2) (Ψ, C) ∅, if (∃i ) such that 2 2 0 S = ∅, then (m∧C) can be deleted, otherwise ((m∧C)∨C ∨···∨C )(v ,··· , v ) = 1 q 1 n (C ∨···∨ C )(v ,··· , v )(∀(v ,··· , v ) ∈ L ) ⇐⇒ (C ∨···∨ C )(u ,··· , u ) = 1 q 1 n 1 n q 1 q 3 1 1(∀(u ,··· , u ) ∈ B ). 1 q Keywords Lattice· Boolean function· Quasi-Boolean algebra· Quasi-Boolean func- tion. 1. Introduction Boolean function and Boolean equation have been successfully deployed in automati- cal control systems, computer science, operation research of real world and so on. For instance: The problem of improving the computational performance of propositional expert systems is being actively investigated, and much attention is given to the anal- ysis and simpliﬁcation of production rule knowledge basis. Due to the dependence of the complexity of queries on the length of the knowledge base, the use of the “short- est” representation of a given knowledge base reduces the memory requirements and increases the computational eﬃciency of expert systems. Obviously, the production Yang-jin Cheng () · Lin-xi Xu School of Mathematics and Computational Science, Xiangtan University, Hunan, 411105, P.R.China email: yjcheng@xtu.edu.cn 276 Yang-jin Cheng · Lin-xi Xu (2011) n m n m rule q → r and the clause ( ¬q ) ( r ) are logically equivalent, i.e., they i j i j i=1 j=1 i=1 j=1 have the same set of models (satisfying truth assignments). Therefore, production value knowledge bases are in fact sets of clauses(conjunctive normal form). To a set of models, a knowledge base we associate a Boolean function, which assumes the value 1 exactly on the 0-1 vectors corresponding to the models, and assume the value 0, elsewhere 1, if α is a model, f (α) = 0, otherwise. The Boolean function corresponding to a knowledge base may admit other equivalent conjunctive normal form from representations which may be shorter than the initial one. Therefore, the transformation of a given knowledge base of minimized a size is a Boolean function minimization problem. The discipline of fuzzy logic, fuzzy systems and fuzzy modeling has witnessed its greatest success in automatical control applications of the real world, including sub- way control, autonomous robot navigation, autofocus cameras, image analysis, and diagnosis systems of real world. Information processing based on fuzzy logic theory requires extensive computation and, hence, the computation time becomes a critical issue. The literature records a number of research eﬀorts by the fuzzy logic com- munity aiming at developing advanced hardware for fast execution of fuzzy logic. In addition, a number of commercial vendors oﬀer a combination of hardware and software for developing fuzzy systems. They include Accel Infotech Spore Pte Ltd., Adaptive Information System, American NeuraLogix, Aptronix, ByteCraft Ltd. Fril Systems Ltd., Fujitsu, FuziWare, FuzzySoft AG. Fuzzy System Engineering, Hyper- Logic, Inc., Inform, Metus Systems Group, Modico, Oki Electric, Togai InfraLogic, Inc., Toshiba, TransferTech GmbH, Honeywell IAC, Integrated Systems Inc., SGS- Thomson, Siemens, and others. So far there has not been a proper algebraic structure corresponding to fuzzy logic. In this paper, we propose an algebraic structure called quasi-Boolean algebra, denoted by L , with “nice” properties, and obtain a method for simplifying quasi-Boolean function. 2. Basic Properties of Quasi-Boolean Algebra and Quasi-Boolean Functions Let L = {0, m, 1}, where m is a number which is between 0 and 1, so we have 0 < m < 1. Now deﬁne two binary operations called “or”, “and”, denoted by “∨”, “∧”, respectively, and one unary operation called “negation” denoted by “¬”. Table 1: Operation of “or”. a 000 mmm 111 b 0 m 10 m 10 m 1 a∨ b 0 m 1 mm 1111 Fuzzy Inf. Eng. (2011) 3: 275-291 277 Table 2: Operation of “and”. a 000 mmm 111 b 0 m 10 m 10 m 1 a∧ b 0000 mm 0 m 1 Table 3: Operation of “negation”. a 0 m 1 ¬a 1 m 0 (L ,∨,∧,¬) is called a 3 quasi-Boolean algebra, denoted simply by L . 3 3 By computing truth value table, we can obtain the following results: Theorem 2.1 ∀a, b, c ∈ L 1) a∨ a = a, a∧ a = a (Idempotent); 2) a∨ b = b∨ a, a∧ b = b∧ a (Commutativity ); 3) (a∨ b)∨ c = a∨ (b∨ c), (a∧ b)∧ c = a∧ (b∧ c) (Associativity); 4) a∨ (a∧ b) = a, a∧ (a∨ b) = a (Absorption); 5) a∨ 0 = a, a∨ 1 = 1, a∧ 0 = 0, a∧ 1 = a (0-1 law); 6) a∧ (b∨ c) = (a∧ b)∨ (a∧ c), a∨ (b∧ c) = (a∨ b)∧ (a∨ c) (Distributive law); 7) ¬(a∨ b) = ¬a∧¬b (De.Morgan law); 8) ¬(¬a) = a (Double negation law). Theorem 2.2 ∀a, b, c ∈ L , if a ≤ b, then a∨ c ≤ b∨ c, and a∧ c ≤ b∧ c (Monotony). Now we propose the deﬁnition of quasi-Boolean function and give their properties. Firstly, we deﬁne two functions denoted by P ,Ψ , respectively, where a ∈ L , 1 ≤ k a 3 k ≤ n, n n P : L −→ L , P (x ,··· , x ) = x (∀(x ,··· , x ) ∈ L )(1 ≤ k ≤ n), k 3 k 1 n k 1 n 3 3 n n Ψ : L −→ L , Ψ (x ,··· , x ) = a (∀(x ,··· , x ) ∈ L ). a 3 a 1 n 1 n 3 3 Deﬁnition 2.1 Quasi-Boolean function is deﬁned as follows: 1) Ψ , P (1 ≤ k ≤ n) are quasi-Boolean functions. a k 278 Yang-jin Cheng · Lin-xi Xu (2011) 2) If Ψ ,Ψ are quasi-Boolean functions, then Ψ ∨Ψ ,Ψ ∧Ψ ,¬Ψ are quasi- 1 2 1 2 1 2 1 Boolean functions, where (Ψ ∨Ψ )(x ,··· , x )=Ψ (x ,··· , x )∨Ψ (x ,··· , x )(∀(x ,··· , x ) ∈ L ), 1 2 1 n 1 1 n 2 1 n 1 n (Ψ ∧Ψ )(x ,··· , x )=Ψ (x ,··· , x )∧Ψ (x ,··· , x )(∀(x ,··· , x ) ∈ L ), 1 2 1 n 1 1 n 2 1 n 1 n ¬(Ψ (x ,··· , x )) = 1−Ψ (x ,··· , x )(∀(x ,··· , x ) ∈ L ). 1 1 n 1 1 n 1 n 3) Any quasi-Boolean function can be obtained by applying ﬁnite two rules above. After giving the deﬁnition of quasi-Boolean function, we begin to discuss the normal form of quasi-Boolean function Ψ(x ,··· , x ). By applying Theorem 2.1 to 1 n Ψ(x ,··· , x ) again and again, we have the following results. 1 n Theorem 2.3 The following statements are equivalent. ,··· , x ) is quasi-Boolean function; 1) Ψ(x 1 n 2) Ψ(x ,··· , x ) = (a ∧ C )∨···∨ (a ∧ C ); 1 n 1 1 p p 3) Ψ(x ,··· , x ) = (b ∨ D )∧···∧ (b ∨ D ). 1 n 1 1 q q (a ∧C )∨···∨(a ∧C ) is called a disjunctive normal form (DNF) of quasi-Boolean 1 1 p p function; Ψ(x ,··· , x ), C (1 ≤ i ≤ p) is called an elementary disjunctive term; 1 n i (b ∨D )∧···∧(b ∨D ) a conjunctive normal form (CNF) of quasi-Boolean function; 1 1 q q Ψ(x ,··· , x ), D (1 ≤ j ≤ q) an elementary conjunctive clause. Variable x (1 ≤ k ≤ 1 n j k n) and its negation ¬x (1 ≤ k ≤ n) are called literals. In this paper, we only discuss whether the term of quasi-Boolean function, which is a disjunctive normal form, can be deleted or not. Without losing generality, we suppose that Ψ(x ,··· , x ) = (a ∧ 1 n C)∨ (a ∧ C )∨···∨ (a ∧ C ). 1 1 p p Deﬁnition 2.2 If ∀(v ,··· , v ) ∈ L we have the following: 1 n ((a∧ C)∨ (a ∧ C )∨···∨ (a ∧ C ))(v ,··· , v ) 1 1 p p 1 n = ((a ∧ C )∨···∨ (a ∧ C ))(v ,··· , v ). 1 1 p p 1 n We call the term (a∧ C) of quasi-Boolean function Ψ(x ,··· , x ) can be deleted. 1 n The set of all literals belonging to the term C , is denoted by S (1 ≤ i ≤ p), i i similarly, the set of all literals belonging to the term C is denoted by S . Now we start to further study the above problem. Note that, if a = 1, then we always suppose that ∀k (1 ≤ k ≤ n),{x ,¬x } S ; i k k i if a = m, then we have ∃k (1 ≤ k ≤ n), such that {x ,¬x }⊆ S , or ∀k (1 ≤ k ≤ i 0 0 k k i 0 0 n),{x ,¬x } S . k k i 3. The Term with Coeﬃcient 1 in Quasi-Boolean Function Let Ψ(x ,··· , x ) = C ∨ (a ∧ C )∨···∨ (a ∧ C ). Deﬁne (Ψ, C) = {(a ∧ C ): 1 n 1 1 p p 1 i i a = 1}, and S = S ∼ S (1 ≤ i ≤ p). We divide our discussion into two cases: i i 1) (Ψ, C) = ∅, i.e., a = m (∀i, 1 ≤ i ≤ p), and so Ψ(x ,··· , x ) = C ∨ (m∧ 1 i 1 n C )∨···∨ (m∧ C ). 1 p Fuzzy Inf. Eng. (2011) 3: 275-291 279 2) (Ψ, C) ∅, i.e.,∃i (1 ≤ i ≤ p), such that a = 1, without losing generality, 1 0 0 i we suppose that Ψ(x ,··· , x ) = C∨C ∨···∨C ∨(m∧C )∨···∨(m∧C )(q ≥ 1 n 1 q q+1 p 1). Now we propose the following lemma ﬁrst. Lemma 1 Let Ψ(x ,··· , x ) = C ∨ C ∨···∨ C , the following two statements are 1 n 1 p equivalent 1) C ∨ C ∨···∨ C = C ∨···∨ C ; 1 p 1 p 2) ∀ f ∈ S , there must be i (1 ≤ i ≤ p) such that f (i ) ∈ S. i 0 0 0 i=1 Proof 1) =⇒ 2): Suppose that there is f ∈ S , such that f (i) S (∀i(1 ≤ i ≤ p)). 0 i 0 i=1 Select vector V = (v ,··· , v ) ∈ L as follows: 1 n 1, x ∈ S, v = 0, ¬x ∈ S, k ⎪ k m, otherwise. Since S ∩{ f (1),··· , f (p)} = ∅, we have f (i) = m,∀i (1 ≤ i ≤ p). 0 0 0 (C ∨ C ∨···∨ C )(v ,··· , v ) 1 p 1 n = C(v ,··· , v )∨ C (v ,··· , v )∨···∨ C (v ,··· , v ) 1 n 1 1 n p 1 n ≥ C(v ,··· , v ) 1 n = 1. But (C ∨···∨ C )(v ,··· , v ) 1 p 1 n = C (v ,··· , v )∨···∨ C (v ,··· , v ) 1 1 n p 1 n ≤ f (1)(v ,··· , v )∨···∨ f (p)(v ,··· , v ) 0 1 n 0 1 n = m∨···∨ m = m. Hence we have (C ∨ C ∨···∨ C )(v ,··· , v ) (C ∨···∨ C )(v ,··· , v ). A 1 p 1 n 1 p 1 n contradiction. 2) =⇒ 1) C ∨ C ∨···∨ C 1 p = C ∨ C ∨···∨ C 1 p = C ∨ (∧ ( f (1)∨···∨ f (p))) = C ∨ (∧ ( f (1)∨···∨ f (i − 1)∨ f (i )∨ f (i + 1)···∨ f (p))) f 0 0 0 = ∧ (C ∨ ( f (1)∨···∨ f (i − 1)∨ f (i )∨ f (i + 1)···∨ f (p))) f 0 0 0 = ∧ (C ∨ f (1)∨···∨ f (i − 1)∨ f (i )∨ f (i + 1)···∨ f (p)) f 0 0 0 = ∧ ( f (1)∨···∨ f (i − 1)∨ (C ∨ f (i ))∨ f (i + 1)···∨ f (p)) f 0 0 0 = ∧ ( f (1)∨···∨ f (i − 1)∨ f (i )∨ f (i + 1)···∨ f (p)) f 0 0 0 = C ∨···∨ C . 1 p 280 Yang-jin Cheng · Lin-xi Xu (2011) When (Ψ, C) = ∅, we can prove the following theorem. Theorem 3.1 If (Ψ, C) = ∅, then term C can not be deleted. Proof Deﬁne a vector V = (v ,··· , v ) ∈ L , as follows: 1 n 1, x ∈ S, ⎪ k v = 0, ¬x ∈ S, k ⎪ m, otherwise. Since ∀k (1 ≤ k ≤ n),{x ,¬x } S, and so deﬁnition of the vector V is consistent. k k (C ∨ (m∧ C )∨···∨ (m∧ C ))(v ,··· , v ) 1 p 1 n = C(v ,··· , v )∨ (m∧ C )(v ,··· , v )∨···∨ (m∧ C )(v ,··· , v ) 1 n 1 1 n p 1 n ≥ C(v ,··· , v ) 1 n = 1. But ((m∧ C )∨···∨ (m∧ C ))(v ,··· , v ) 1 p 1 n = (m∧ C )(v ,··· , v )∨···∨ (m∧ C )(v ,··· , v ) 1 1 n p 1 n = (m∧ C (v ,··· , v ))∨···∨ (m∧ C (v ,··· , v )) 1 1 n p 1 n ≤ m∨···∨ m = m. And so, (C∨ (m∧C )∨···∨ (m∧C ))(v ,··· , v ) ((m∧C )∨···∨ (m∧C ))(v ,··· , v ), 1 p 1 n 1 p 1 n we conclude that C can not be deleted. When (Ψ, C) ∅, i.e.,∃i (1 ≤ i ≤ p), such that a = 1, note that Ψ(x ,··· , x ) 1 0 0 i 1 n = C∨ C ∨···∨ C ∨ (m∧ C )∨···∨ (m∧ C )(q ≥ 1). By the following theorem, 1 q q+1 p we can simplify the problem. Theorem 3.2 The following two statements are equivalent, 1) C∨ C ∨···∨ C ∨ (m∧ C )∨···∨ (m∧ C ) = C ∨···∨ C ∨ (m∧ C )∨ 1 q q+1 p 1 q q+1 ···∨ (m∧ C ); 2) C ∨ C ∨···∨ C = C ∨···∨ C . 1 q 1 q Proof 1) =⇒ 2) Suppose that C ∨ C ∨···∨ C C ∨···∨ C . By Lemma 1, 1 q 1 q we conclude that ∃ f ∈ S , such that f (i) S,∀i (1 ≤ i ≤ q). According to the 0 i 0 i=1 followings, we obtain a vector V = (v ,··· , v ) ∈ L , 1 n ⎪ 1, x ∈ S, ⎪ k 0, ¬x ∈ S, v = 0, x ∈{ f (1),··· , f (q)}, k ⎪ k 0 0 ⎪ 1, ¬x ∈{ f (1),··· , f (q)}, k 0 0 m, otherwise. Fuzzy Inf. Eng. (2011) 3: 275-291 281 Since ∀k (1 ≤ k ≤ n),{x ,¬x } S, and {x ,¬x } { f (1),··· , f (q)}, as well k k k k 0 0 as S ∩{ f (1),··· , f (q)} = ∅, it is easy to see that the deﬁnition of the vector V is 0 0 consistent. Because (C ∨ C ∨···∨ C ∨ (m∧ C )∨···∨ (m∧ C ))(v ,··· , v ) 1 q q+1 p 1 n = C(v ,··· , v )∨ C (v ,··· , v )∨···∨ C (v ,··· , v ) 1 n 1 1 n q 1 n ∨(m∧ C )(v ,··· , v )∨···∨ (m∧ C )(v ,··· , v ) q+1 1 n p 1 n ≥ C(v ,··· , v ) 1 n = 1. But (C ∨···∨ C ∨ (m∧ C )∨···∨ (m∧ C ))(v ,··· , v ) 1 q q+1 p 1 n = C (v ,··· , v )∨···∨ C (v ,··· , v ) 1 1 n q 1 n ∨(m∧ C )(v ,··· , v )∨···∨ (m∧ C )(v ,··· , v ) q+1 1 n p 1 n = C (v ,··· , v )∨···∨ C (v ,··· , v ) 1 1 n q 1 n ∨(m∧ C (v ,··· , v ))∨···∨ (m∧ C (v ,··· , v )) q+1 1 n p 1 n ≤ f (1)(v ,··· , v )∨···∨ f (q)(v ,··· , v ) 0 1 n 0 1 n ∨(m∧ C (v ,··· , v ))∨···∨ (m∧ C (v ,··· , v )) q+1 1 n p 1 n = (m∧ C (v ,··· , v ))∨···∨ (m∧ C (v ,··· , v )) q+1 1 n p 1 n ≤ m∨···∨ m = m. Therefore, we obtain (C ∨ C ∨···∨ C ∨ (m∧ C )∨···∨ (m∧ C ))(v ,··· , v ) 1 q q+1 p 1 n (C ∨···∨ C ∨ (m∧ C )∨···∨ (m∧ C ))(v ,··· , v ). 1 q q+1 p 1 n Contradicting the assumption. 2) =⇒ 1) : C ∨ C ∨···∨ C ∨ (m∧ C )∨···∨ (m∧ C ) 1 q q+1 p = (C ∨ C ∨···∨ C )∨ ((m∧ C )∨···∨ (m∧ C )) 1 q q+1 p = (C ∨···∨ C )∨ ((m∧ C )∨···∨ (m∧ C )) 1 q q+1 p = C ∨···∨ C ∨ (m∧ C )∨···∨ (m∧ C ). 1 q q+1 p Theorem 3.2 denotes that it is enough for us to investigate the problem, whether the term C for quasi-Boolean function C∨ C ∨···∨ C can be deleted or not. Now 1 q we investigate the cases in detail respectively: 1) S ∅ (1 ≤ i ≤ q); 2) ∃i (1 ≤ i ≤ q), such that S = ∅. 0 0 Theorem 3.3 If S ∅ (1 ≤ i ≤ q), then C can not be deleted. 0 0 Proof Because S ∅ (1 ≤ i ≤ q), where S = S ∼ S, then ∃y ∈ S , and i i i i i y S. We deﬁne f ∈ S , according to the followings: f (i) = y. By Lemma 1, we i i i i=1 conclude that C ∨ C ∨···∨ C C ∨···∨ C . 1 q 1 q Theorem 3.4 If ∃i (1 ≤ i ≤ q), such that S = ∅, then C can be deleted. 0 0 Proof Without losing generality, we suppose that S = {y ,··· , y }. Since S = ∅, i 1 r 0 i S ⊇ S = {y ,··· , y }. It is clear that C ∨ C = C . Therefore i 1 r i i 0 0 0 282 Yang-jin Cheng · Lin-xi Xu (2011) Ψ (x ,··· , x )= C ∨ C ∨···∨ C 1 1 n 1 q = C ∨ C ∨···∨ C ∨ C ∨ C ∨···∨ C 1 i −1 i i +1 q 0 0 0 = C ∨···∨ C ∨ (C ∨ C )∨ C ∨···∨ C 1 i −1 i i +1 q 0 0 0 = C ∨···∨ C ∨ C ∨ C ∨···∨ C 1 i −1 i i +1 q 0 0 0 = C ∨···∨ C . 1 q Hence we can conclude that C can be deleted. 4. The Term with Coeﬃcient m in a Quasi-Boolean Function Let Ψ(x ,··· , x ) = (m∧ C)∨ (a ∧ C )∨···∨ (a ∧ C ). Because coeﬃcient a (1 ≤ 1 n 1 1 p p i i ≤ p) of term (a ∧ C )(1 ≤ i ≤ p) in the quasi-Boolean function Ψ(x ,··· , x )is i i 1 n either 1 or m, without losing generality, we can suppose that Ψ(x ,··· , x ) = (m∧ C)∨ C ∨···∨ C ∨ (m∧ C )∨···∨ (m∧ C ). 1 n 1 q q+1 p Now ﬁrstly, we propose the following lemma. Lemma 2 Let Ψ(x ,··· , x ) = (m∧ C)∨ C ···∨ C . Two statements are equivalent 1 n 1 p as follows, 1) (m∧ C)∨ C ∨···∨ C = C ∨···∨ C ; 1 p 1 p 2) ∀ f ∈ S , we have either there is i (1 ≤ i ≤ p) such that f (i ) ∈ S or there i 0 0 0 i=1 is k (1 ≤ k ≤ n) such that {x ,¬x }⊆{ f (1),··· , f (p)}. 0 0 k k 0 0 Proof 1) =⇒ 2) Suppose that ∃ f ∈ S such that both f (i) S (∀i, 1 ≤ i ≤ p) 0 i 0 i=1 and {x ,¬x } { f (1),··· , f (p)} (∀k, 1 ≤ k ≤ n). According to the followings, we k k 0 0 can obtain the vector V = (v ,··· , v ) ∈ L . 1 n ⎪ 1, x ∈ S,¬x S, ⎪ k k 0, x S,¬x ∈ S, ⎪ k k m, x ∈ S,¬x ∈ S, ⎨ k k v = k ⎪ ⎪ 0, x ∈{ f (1),··· , f (p)}, k 0 0 ⎪ 1, ¬x ∈{ f (1),··· , f (p)}, k 0 0 m, otherwise. Note that S ∩{ f (1),··· , f (p)} = ∅ and {x ,¬x } { f (1),··· , f (p)} (∀k, 1 ≤ 0 0 k k 0 0 k ≤ n), it is clear that the vector V is consistent. We have the following result ((m∧ C)∨ C ∨···∨ C )(v ,··· , v ) 1 p 1 n = (m∧ C)(v ,··· , v )∨ C (v ,··· , v )∨···∨ C (v ,··· , v ) 1 n 1 1 n p 1 n ≥ (m∧ C)(v ,··· , v ) 1 n = m∧ C(v ,··· , v ) 1 n = m∧ 1 = m, Fuzzy Inf. Eng. (2011) 3: 275-291 283 (C ∨···∨ C )(v ,··· , v ) 1 p 1 n = C (v ,··· , v )∨···∨ C (v ,··· , v ) 1 1 n p 1 n ≤ f (1)(v ,··· , v )∨···∨ f (p)(v ,··· , v ) 0 1 n 0 1 n = 0. This is a contradiction. 2) =⇒ 1) By applying distributive law, we have (m∧ C)∨ C ∨···∨ C 1 p = (m∧ C)∨ (∧ ( f (1)∨···∨ f (p))) = ∧ ((m∧ C)∨ ( f (1)∨···∨ f (p))) = ∧ ((m∧ C)∨ f (1)∨···∨ f (p))(By hypothesis) = ∧ ( f (1)∨···∨ f (p)) = C ∨···∨ C . 1 p The following theorem tell us that it is unnecessary for us to deal with the problem for deleting a term together with coeﬃcient. Theorem 4.1 The following statements are equivalent: 1) (m∧ C)∨ C ∨···∨ C ∨ (m∧ C )∨···∨ (m∧ C ) 1 q q+1 p = C ∨···∨ C ∨ (m∧ C )∨···∨ (m∧ C ); 1 q q+1 p 2) (m∧ C)∨ C ∨···∨ C = C ∨···∨ C . 1 q 1 q Proof 1) =⇒ 2) Suppose that (m∧C)∨C ∨···∨C C ∨···∨C . By Lemma 2, we 1 q 1 q conclude that there must be f ∈ S such that both f (i) S (∀i, 1 ≤ i ≤ p) and 0 i 0 i=1 {x ,¬x } { f (1),··· , f (p)} (∀k, 1 ≤ k ≤ n). We deﬁne a vector V = (v ,··· , v ) ∈ k k 0 0 1 n L as follows, ⎪ 1, x ∈ S,¬x S, ⎪ k k 0, x S,¬x ∈ S, ⎪ k k m, x ∈ S,¬x ∈ S, ⎨ k k v = k ⎪ ⎪ 0, x ∈{ f (1),··· , f (p)}, k 0 0 1, ¬x ∈{ f (1),··· , f (p)}, k 0 0 m, otherwise. Since S∩{ f (1),··· , f (p)} = ∅, the vector V is consistent. We have the following: 0 0 ((m∧ C)∨ C ∨···∨ C ∨ (m∧ C )∨···∨ (m∧ C ))(v ,··· , v ) 1 q q+1 p 1 n = (m∧ C)(v ,··· , v )∨ C (v ,··· , v )∨···∨ C (v ,··· , v ) 1 n 1 1 n q 1 n ∨(m∧ C )(v ,··· , v )∨···∨ (m∧ C )(v ,··· , v ) q+1 1 n p 1 n ≥ (m∧ C)(v ,··· , v ) 1 n = m∧ C(v ,··· , v ) 1 n ≥ m∧ m = m. But 284 Yang-jin Cheng · Lin-xi Xu (2011) (C ∨···∨ C ∨ (m∧ C )∨···∨ (m∧ C ))(v ,··· , v ) 1 q q+1 p 1 n = C (v ,··· , v )∨···∨ C (v ,··· , v ) 1 1 n q 1 n ∨(m∧ C )(v ,··· , v )∨···∨ (m∧ C )(v ,··· , v ) q+1 1 n p 1 n ≤ f (1)(v ,··· , v )∨···∨ f (q)(v ,··· , v ) 0 1 n 0 1 n ∨ f (q+ 1)(v ,··· , v )∨···∨ f (p)(v ,··· , v ) 0 1 n 0 1 n = 0. Hence we conclude that ((m ∧ C) ∨ C ∨ ··· ∨ C ∨ (m ∧ C )∨···∨ (m ∧ 1 q q+1 C ))(v ,··· , v ) (C ∨···∨C ∨(m∧C )∨···∨(m∧C ))(v ,··· , v ). Contradicting p 1 n 1 q q+1 p 1 n the assumption. 2) =⇒ 1) By applying properties of quasi-Boolean algebra and quasi-Boolean function, we have the following (m∧ C)∨ C ∨···∨ C ∨ (m∧ C )∨···∨ (m∧ C ) 1 q q+1 p = ((m∧ C)∨ C ∨···∨ C )∨ ((m∧ C )∨···∨ (m∧ C )) 1 q q+1 p = ((m∧ C)∨ C ∨···∨ C )∨ (m∧ (C ∨···∨ C )) 1 q q+1 p = (((m∧ C)∨ C ∨···∨ C )∨ m) 1 q ∧(((m∧ C)∨ C ∨···∨ C )∨ (C ∨···∨ C )) 1 q q+1 p = (m∨ C ∨···∨ C )∧ (((m∧ C)∨ C ∨···∨ C )∨ (C ∨···∨ C )) 1 q 1 q q+1 p = (m∨ (C ∨···∨ C ))∧ (C ∨···∨ C ∨ C ∨···∨ C ) 1 q 1 q q+1 p = (m∧ (C ∨···∨ C ∨ C ∨···∨ C )) 1 q q+1 p ∨((C ∨···∨ C )∧ (C ∨···∨ C ∨ C ∨···∨ C )) 1 q 1 q q+1 p = (m∧ (C ∨···∨ C ∨ C ∨···∨ C ))∨ (C ∨···∨ C ) 1 q q+1 p 1 q = ((m∧ C )∨···∨ (m∧ C )∨ (m∧ C )∨···∨ (m∧ C ))∨ (C ∨···∨ C ) 1 q q+1 p 1 q = (m∧ C )∨···∨ (m∧ C )∨ (m∧ C )∨···∨ (m∧ C )∨ C ∨···∨ C 1 q q+1 p 1 q = C ∨···∨ C ∨ (m∧ C )∨···∨ (m∧ C ). 1 q q+1 p Without losing generality, we suppose that Ψ(x ,··· , x ) = (m∧ C)∨ C ∨···∨ C ∨ C ∨···∨ C . 1 n 1 q q+1 p ∗ ∗ Deﬁne S = {y : y ∈ S ;¬y ∈ S}, S = {y : y ∈ S ;¬y ∈ S } (1 ≤ i ≤ p), i i ∗ ∗ (Ψ, C) = {C : S ⊆ S , 1 ≤ i ≤ p}. Without losing generality, we always suppose 2 i that (Ψ, C) = {C ,··· , C }. We further study the following cases respectively: 2 1 q 1) (Ψ, C) = ∅; 2) (Ψ, C) ∅. The following theorem give an answer to Case 1). Theorem 4.2 If (Ψ, C) = ∅, then the term (m∧ C) can not be deleted. Proof Let Ψ(x ,··· , x ) = (m∧ C)∨ C ∨···∨ C . Since (Ψ, C) = ∅, we obtain 1 n 1 p 2 ∗ ∗ ∗ ∗ S S . We denote the elements of the set S ∼ S by {y ,¬y ,··· , y ,¬y }, i i i i 1 1 k(i) k(i) i i ∗ ∗ and denote all elements of the set (S ∼ S )by {y ,¬y ,··· , y ,¬y }. It is clear 1 1 r r i=1 that {y ,¬y } S (∀ j, 1 ≤ j ≤ r), i.e., given j(1 ≤ j ≤ r), there is at least one j j element denoted by z such that z S . Without losing generality, we suppose that j j Fuzzy Inf. Eng. (2011) 3: 275-291 285 given i (1 ≤ i ≤ p), we have both z ∈ S and z S , and so S ∩{z ,··· , z } = ∅. i i 1 p Deﬁne a vector V = (v ,··· , v ) ∈ L as follows: 1 n ⎪ 1, x ∈ S,¬x S, ⎪ k k 0, x S,¬x ∈ S, ⎪ k k m, x ∈ S,¬x ∈ S, ⎨ k k v = k ⎪ ⎪ 0, x ∈{z ,··· , z }, k 1 p ⎪ 1, ¬x ∈{z ,··· , z }, k 1 p m, otherwise. We have ((m∧ C)∨ C ∨···∨ C )(v ,··· , v ) 1 p 1 n = (m∧ C)(v ,··· , v )∨ C (v ,··· , v )∨···∨ C (v ,··· , v ) 1 n 1 1 n p 1 n ≥ (m∧ C)(v ,··· , v ) 1 n = m∧ C(v ,··· , v ) 1 n ≥ m∧ m = m. Furthermore (C ∨···∨ C )(v ,··· , v ) 1 p 1 n = C (v ,··· , v )∨···∨ C (v ,··· , v ) 1 1 n p 1 n ≤ z (v ,··· , v )∨···∨ z (v ,··· , v ) 1 1 n p 1 n = 0. Hence we obtain ((m∧C)∨C ∨···∨C )(v ,··· , v ) (C ∨···∨C )(v ,··· , v ), 1 p 1 n 1 p 1 n i.e., the term (m∧ C) can not be deleted. Theorem 4.3 (m∧ C)∨ C ∨···∨ C = C ∨···∨ C ⇐⇒ (m∧ C)∨ C ∨···∨ C = 1 p 1 p 1 q C ∨···∨ C . 1 q Proof =⇒ Suppose that (m ∧ C) ∨ C ∨···∨ C C ∨···∨ C . By Lemma 2, 1 q 1 q we conclude ∃ f ∈ S , such that both f (i) S (∀i, 1 ≤ i ≤ q) and {x ,¬x } 0 i 0 k k i=1 { f (1),··· , f (q)} (∀k, 1 ≤ k ≤ n). We construct g ∈ S as follows: 0 0 i i=1 1) Deﬁne g(i) = f (i)(∀i, 1 ≤ i ≤ q). 2) According to the following, we deﬁne g(i), (q + 1 ≤ i ≤ p). Firstly, consider the term C , by the deﬁnition of (Ψ, C), we can conclude that ∃z, ¬z q+1 2 and{z,¬z}⊆ S such that{z,¬z} S : q+1 (a) z S, ¬z ∈ S . Let g(q + 1) = z. It is clear that g(q + 1) S ; because S∩{g(1),··· , g(q)} = ∅, and we have ¬z {g(1),··· , g(q)}. We conclude that {z, ¬z} {g(1),··· , g(q+ 1)}. (b) z ∈ S, ¬z S . Let g(q+ 1) = ¬z. It is clear that g(q+ 1) S ; because S ∩{g(1),··· , g(q)} = ∅,so we have z {g(1),··· , g(q)}. We conclude that {z, ¬z} {g(1),··· , g(q+ 1)}. 286 Yang-jin Cheng · Lin-xi Xu (2011) (c) z S, ¬z S.If z ∈{g(1),··· , g(q)}, then let g(q + 1) = z.If ¬z ∈ {g(1),··· , g(q)}, then let g(q + 1) = ¬z.If z, ¬z {g(1),··· , g(q)}, then let g(q+ 1) = z or ¬z. Similarly, we may construct g(i)(q+ 2 ≤ i ≤ p). It is obvious that g ∈ S satisﬁes the following: i=1 1) g(i) = f (i)(∀i, 1 ≤ i ≤ q); 2) g(i) S (∀i, 1 ≤ i ≤ p); 3) {x ,¬x } {g(1),··· , g(p)} (∀k, 1 ≤ k ≤ n). k k Deﬁne vector V = (v ,··· , v ) ∈ L , 1 n 1, x ∈ S,¬x S, k k 0, x S,¬x ∈ S, ⎪ k k m, x ∈ S,¬x ∈ S, k k v = k ⎪ 0, x ∈{g(1),··· , g(p)}, ⎪ 1, ¬x ∈{g(1),··· , g(p)}, m, otherwise. We obtain the following: ((m∧ C)∨ C ∨···∨ C )(v ,··· , v ) 1 p 1 n = (m∧ C)(v ,··· , v )∨ C (v ,··· , v )∨···∨ C (v ,··· , v ) 1 n 1 1 n p 1 n ≥ (m∧ C)(v ,··· , v ) 1 n = m∧ C(v ,··· , v ) 1 n ≥ m∧ m = m. Furthermore (C ∨···∨ C )(v ,··· , v ) 1 p 1 n = C (v ,··· , v )∨···∨ C (v ,··· , v ) 1 1 n p 1 n ≤ g(1)(v ,··· , v )∨···∨ g(p)(v ,··· , v ) 1 n 1 n = 0. Contradicting the assumption. ⇐= By applying properties of quasi-Boolean algebra and quasi-Boolean function, we obtain (m∧ C)∨ C ∨···∨ C 1 p = (m∧ C)∨ C ∨···∨ C ∨ C ∨···∨ C 1 q q+1 p = ((m∧ C)∨ C ∨···∨ C )∨ C ∨···∨ C 1 q q+1 p = (C ∨···∨ C )∨ C ∨···∨ C 1 q q+1 p = C ∨···∨ C . 1 p Fuzzy Inf. Eng. (2011) 3: 275-291 287 Now, let S = S ∼ S , we discuss in detail the following two cases respectively, 1) ∃i (1 ≤ i ≤ q), such that S = ∅; 0 0 2) S ∅ (1 ≤ i ≤ p). Theorem 4.4 If ∃i (1 ≤ i ≤ q) such that S = ∅, then the term (m ∧ C) can be 0 0 deleted. Proof Since S = ∅ (∃i , 1 ≤ i ≤ q), we have (m∧ C)∨ C = C . Hence 0 0 i i 0 0 (m∧ C)∨ C ∨···∨ C 1 q = (m∧ C)∨ C ∨···∨ C ∨···∨ C 1 i q = C ∨···∨ C ∨···∨ C . 1 i q Theorem 4.5 If S ∅ (∀i, 1 ≤ i ≤ q), then (m∧C)∨C ∨···∨C = C ∨···∨C ⇐⇒ 1 q 1 q C ∨···∨ C ≥ m, where S = S ∼ S (∀i, 1 ≤ i ≤ q). 1 q i Proof =⇒ Because C ∨···∨ C = ∧ ( f (1)∨···∨ f (q)), we have f ∈ S and f i i=1 f (i) S . By Lemma 2, we conclude that ∃k , 1 ≤ k ≤ q such that {x ,¬x }⊆ f f k k f f { f (1),··· , f (q)}, (C ∨···∨ C )(v ,··· , v )(∀(v ,··· , x ) ∈ L ) 1 q 1 q 1 3 = (∧ ( f (1)∨···∨ f (q)))(v ,··· , v ) f 1 q = ∧ ( f (1)∨···∨ f (q))(v ,··· , v ) f 1 q ≥∧ (x ∨¬x ) f k k f f ≥∧ m = m. ⇐= ∀ f ∈ S ,if ∃i( f ) such that f (i( f )) ∈ S. By Lemma 2, we can obtain the i=1 above results; if f (i) S , we can conclude that f (i) ∈ S (1 ≤ i ≤ q), so there must be ∃k( f ), such that {x ,¬x }⊆{ f (1),··· , f (q)}. k( f ) k( f ) Suppose that {x ,¬x } { f (1),··· , f (q)}. Deﬁne vector V = (v ,··· , v ) ∈ L , k k 1 n 0, x ∈{ f (1),··· , f (q)}, ⎪ k v = ⎪ 1, ¬x ∈{ f (1),··· , f (q)}, k k m, otherwise. We have the following (C ∨···∨ C )(v ,··· , v ) 1 n = C (v ,··· , v )∨···∨ C (v ,··· , v ) 1 n 1 n ≤ f (1)(v ,··· , v )∨···∨ f (q)(v ,··· , v ) 1 n 1 n = 0. This is a contradiction. By Lemma 2, the theorem can be proved. The following theorem tells us that a judgement problem for deleting a term in quasi-Boolean function sum up whether a Boolean expression is always true or not. 288 Yang-jin Cheng · Lin-xi Xu (2011) Theorem 4.6 C ∨··· ∨ C ≥ m (∀(v ,··· , v ) ∈ L ) ⇐⇒ C ∨···∨ C = 1 n q q 1 3 1 1(∀(u ,··· , u ) ∈ B ). 1 n Proof =⇒∀ f ∈ S , then ∃k , such that {x ,¬x }⊆{ f (1),··· , f (q)}. ∀(u ,··· , f k k 1 f f i=1 u ) ∈ B , (C ∨···∨ C )(u ,··· , u ) 1 n = C (u ,··· , u )∨···∨ C (u ,··· , u ) 1 n 1 n = ∧ ( f (1)(u ,··· , u )∨···∨ f (q)(u ,··· , u )) f 1 n 1 n ≥∧ (x ∨¬x ) f k k f f = 1. So we have C ∨···∨ C = 1. ⇐= Suppose that ∃ f such that {x ,¬x } { f (1),··· , f (q)}. Deﬁne vector 0 k k 0 0 V = (u ,··· , u ) ∈ B , 1 n 1, x ∈{ f (1),··· , f (q)}, ⎪ k 0 0 v = 0, ¬x ∈{ f (1),··· , f (q)}, k ⎪ k 0 0 1, otherwise. We obtain the following (C ∨···∨ C )(u ,··· , u ) 1 n 1 q = C (u ,··· , u )∨···∨ C (u ,··· , u ) 1 n 1 n 1 q = ∧ ( f (1)(u ,··· , u )∨···∨ f (q)(u ,··· , u )) f 1 n 1 n ≤ f (1)(u ,··· , u )∨···∨ f (q)(u ,··· , u ) 0 1 n 0 1 n = 0. Contradicting the assumption. 5. Algorithm and Examples Let Ψ(x ,··· , x ) = (a∧ C)∨ (a ∧ C )∨···∨ (a ∧ C ). Now we may summarize 1 n 1 1 p p the following algorithm: Step 1: a = 1? Yes: Find S and (ψ, C). No: Go to Step 4. Step 2: (ψ, C) = ∅? Yes: The term C can not be deleted, stop. No: Computing S = S ∼ S (∀i, 1 ≤ i ≤ q). Step 3: ∃i (1 ≤ i ≤ q), such that S = ∅? 0 0 Yes: C can be deleted, stop. No: C can not be deleted, stop. Step 4: Find S and S , as well as (ψ, C). Step 5: (ψ, C) = ∅? Yes: C can not be deleted, stop. No: Computing S = S ∼ S (1 ≤ i ≤ q). Step 6: Constructing Boolean expression Fuzzy Inf. Eng. (2011) 3: 275-291 289 Ψ= ( y). i=1 y∈S Step 7: Ψ(u ,··· , u ) = 1(∀(u ,··· , u ) ∈ B )? 1 n 1 n Yes: C can be deleted, stop. No: C can not be deleted, stop. Now we give some examples for applying the algorithm. Example 1 Let Ψ(x ,··· , x ) = (m∧ x ∧¬x ∧ x ∧¬x )∨ (¬x ∧ x ∧ x ∧ x )∨ 1 6 2 2 3 4 2 3 5 6 (m∧ x ∧¬x ∧ x ∧¬x )∨ (m∧¬x ∧¬x ∧¬x ∧ x )∨ (¬x ∧ x ∧¬x ∧¬x ). 2 4 5 6 2 4 5 6 2 3 5 6 Consider the term (m∧ x ∧¬x ∧ x ∧¬x ). 2 2 3 4 Step 1: Since a = m, so S = {x ,¬x , x ,¬x } and S = {x ,¬x }, as well as 2 2 3 4 2 2 Ψ (, C) = {S , S , S , S }, where 2 1 2 3 4 S = {¬x , x , x , x }, S = {x ,¬x , x ,¬x }, 1 2 3 5 6 2 2 4 5 6 S = {¬x ,¬x ,¬x , x }, S = {¬x , x ,¬x ,¬x }. 3 2 4 5 6 4 2 3 5 6 Step 2: Computing S (1 ≤ i ≤ q), where S = {x , x }, S = {x ,¬x }, 5 6 5 6 1 2 S = {¬x , x }, S = {¬x ,¬x }. 5 6 5 6 3 4 Step 3: Constructing a Boolean expression Ψ= (x ∧ x )∨ (x ∧¬x )∨ (¬x ∧ x )∨ (¬x ∧¬x ). 5 6 5 6 5 6 5 6 Step 4: Since Ψ= (x ∧ x )∨(x ∧¬x )∨(¬x ∧ x )∨(¬x ∧¬x ) = ((x ∧ x )∨(x ∧ 5 6 5 6 5 6 5 6 5 6 5 ¬x ))∨((¬x ∧ x )∨(¬x ∧¬x )) = x ∨¬x = 1, so the term (m∧ x ∧¬x ∧ x ∧¬x ) 6 5 6 5 6 5 5 2 2 3 4 can be deleted. Example 2 LetΨ(x ,··· , x ) = (m∧¬x ∧¬x ∧¬x ∧ x )∨ (m∧ x ∧¬x ∧ x ∧ 1 6 2 4 5 6 2 2 3 ¬x )∨ (¬x ∧ x ∧ x ∧ x )∨ (m∧ x ∧¬x ∧ x ∧¬x )∨ (¬x ∧ x ∧¬x ∧¬x ). 4 2 3 5 6 2 4 5 6 2 3 5 6 Consider the term (m∧¬x ∧¬x ∧¬x ∧ x ). 2 4 5 6 Step 1: Since a = m ,so S = {¬x ,¬x ,¬x , x } and S = ∅, as well as Ψ (, C) = 2 4 5 6 2 {S , S , S }, where 2 3 4 S = {¬x , x , x , x }, 2 2 3 5 6 S = {x ,¬x , x ,¬x }, S = {¬x , x ,¬x ,¬x }. 3 2 4 5 6 4 2 3 5 6 Step 2: Computing S (2 ≤ i ≤ q), where S = {x , x }, 3 5 S = {x , x ,¬x }, S = {x ,¬x }. 2 5 6 3 6 3 4 Step 3: Constructing a Boolean expression Ψ= (x ∧ x )∨ (x ∧ x ∧¬x )∨ (x ∧¬x ). 3 5 2 5 6 3 6 Step 4: Since Ψ(1, 1, 0, 1, 0, 1) = 0, the term (m∧¬x ∧¬x ∧¬x ∧ x ) can not be 2 4 5 6 deleted. 290 Yang-jin Cheng · Lin-xi Xu (2011) Example 3 Let Ψ= (x ∧¬x ∧ x ∧ x )∨ (x ∧¬x ∧ x )∨ (x ∧¬x ∧ x ∧ x )∨ 1 1 3 4 1 1 2 1 2 3 4 (m∧ x ∧¬x ∧¬x ). Consider the term (x ∧¬x ∧ x ∧ x ). 2 2 3 1 1 3 4 Step 1: Since a=, S = {x ,¬x , x , x } and Ψ (, C) = {S , S }, where 1 1 3 4 1 1 2 S = {x ,¬x , x }, S = {x ,¬x , x , x }. 1 1 1 2 2 1 2 3 4 Step 2: Computing S (i = 1, 2) 0 0 S = {x , x }, S = {¬x }. 3 4 1 1 2 Step 3: Since S ∅ (i = 1, 2), so (x ∧¬x ∧ x ∧ x ) can not be deleted. 1 1 3 4 6. Conclusion In this paper, we present deﬁnitions of quasi-Boolean algebra and quasi-Boolean function. We divide our discussion into two cases: a = 1, a = m , and discuss in detail, respectively, and obtain some properties of quasi-Boolean function. We estab- lish a algorithm for simplifying a quasi-Boolean function, and furthermore give some examples. Acknowledgments The authors are thankful to one of the referees for his remarks and suggestions that have improved an earlier version of the paper. References 1. Hammer P L, Rudeanu S (1968) Boolean methods in operations research and related areas. Springer- Verlag, Berlin 2. Hammer P L, Kogan A (1992) Horn functions and their DNF’s. Information Processing Lette. 44: 23-29 3. Boros E, Ibaraki T and Makino K (1999) Logical analysis of binary data with missing bits. Artiﬁcial Intelligence 107: 219-263 4. Bshouty N H (1995) Exact learning Boolean functions via the monotone theory. Information and Computation 123: 146-153 5. Boros E, Crama Y, Hammer P L (1990) Polynomial time inference of all valid implications for horn and related formulae. Annals of Mathematics and Artiﬁcial Intelligence 1: 21-32 6. Boros E, Gurrich V, Hammer P L, Ibaraki T and Kogan A (1995) Decompositions of partially deﬁned Boolean functions. Discrete Applied Mathematics 62: 51-75 7. Boros E, Hammer P L, Minoux M, Rader D (1999) Optimal cell ﬂipping to minimize channel density in VLSI design and pseudo-Boolean optimization. Discrete Applied Mathematics 90: 69-88 8. Ekin O, Foldes S, Hammer P L, Hellerstein L (2000) Equational characterizations of Boolean function classes. Discrete Mathematics 211: 27-51 9. Fraenkel A S, Hammer P L (1984) Pseudo-Boolean functions and their graphs. Annals of Discrete Mathematics 20: 137-146 10. Simeone B (1979) A generalized consensus approach to non-linear 0-1 optimization. Research Re- port, University of Waterloo, Department of Combinatorics and Optimization: 79-83 11. Davio M, Deschamps J P, Thayse A(1978) Discrete and switching functions. McGraw Hill. 12. Foldes S, Hammer P L (2000) Monotone, horn and quadratic pseudo-Boolean functions. Journal Of Universal Computer Science 6(1): 97-104 13. Foldes S, Hammer P L (2000) Disjunctive and conjunctive representations in ﬁnite lattices and con- vexity spaces. Rutgers University, RUTCOR Research Reports, RRR12-2000 14. Quine W V (1955) A way to simplify truth function. American Mathematical Monthly 62: 627-631 Fuzzy Inf. Eng. (2011) 3: 275-291 291 15. Van de Vel M (1993) Theory of convex structures. North-Holland 16. Stormer ¨ H (1990) Binary functions and their applications. Springer-Verlag, Berlin 17. Hammer P L, Rosenberg I G, Rudeanu S (1963) On the minimization of pseudo-Boolean function. Stud. Cerc. Matem. 14: 359-364 18. Gottschalk W H (1953) The theory of quaternality. Jounal of Symbolic Logic 18: 193-196
Fuzzy Information and Engineering – Taylor & Francis
Published: Sep 1, 2011
Keywords: Lattice; Boolean function; Quasi-Boolean algebra; Quasi-Boolean function
You can share this free article with as many people as you like with the url below! We hope you enjoy this feature!
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get an introductory month for just $19.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.