Search

In this paper we give two theorems from the Propositional Calculus of the Boolean Logic with their consequences and applications and we prove them axiomatically., Comment: 4 pages

In this communication we propose two logically sound fuzzification and defuzzifi- cation techniques for implementing a credibility calculus on a set of propositional expressions. Both rely on a credibility evaluation domain using the rational in- terval [−1, 1] where the sign carries a split truth/falseness denotation. The first technique implements the classic min and max operators where as the second technique implements Bochvar-like operators. Main interest in the communica- tion is given to the concept of natural fuzzification of a propositional calculus. A formal definition is proposed and the demonstration that both fuzzification techniques indeed verify this definition is provided.

After a short introduction to the assembly systems and different representations of assembly process, this work presents three types of models : assembly graphs, precedence graphs and ASTD. The precedence graphs being currently used by assembly line balancing methods in order to assembly systems determination, the objective of this work is to propose an easy and effective method of precedence graphs generation from a set of assembly sequences. Two methods of generation of precedence graphs are presented here : the first one based on graph transformations and the second one based directly boolean logic. The graph transformation method gives a precedence graph if the set of the assembly sequences can be represented by one and only one precedence graph. In the opposite cas, with some ameliorations, it is possible to obtain either a set of precedence graphs or a single precedence hypergraph. With the second method, we can obtain directly a set of precedence graphs or of precedence hypergraphs depending upon the set of assembly sequences. The evaluation of complexity of respective algorithms allows to say that they are polynomial., Après une rapide présentation des systèmes d'assemblage et des différentes représentations des processus d'assemblage, ce travail de recherche présente plus précisément trois grands types de modélisation : les graphes d'assemblage, les graphes de précédence et les ASTD. Les graphes de précédence étant très utilisés avec les méthodes d'équilibrage ou de conception des lignes d'assemblage, l'objectif de ce travail est de proposer une méthode de génération des graphes de précédence simple et efficace à partir d'un ensemble de graphes d'assemblage préalablement établis. Deux méthodes de génération de graphe de précédence sont proposées dans ce travail : une par transformation de graphes et une directement basée sur la logique booléenne. La méthode par transformation de graphes permet d'obtenir un graphe de précédence si l'ensemble des séquences d'enchaînement peut être représenté par un unique graphe de précédence. Dans le cas contraire, avec les améliorations apportées à la méthode, il est possible d'obtenir soit un ensemble de graphes de précédence soit un hypergraphe de précédence. La deuxième de ces méthodes permet d'obtenir directement un ensembl e de graphes de précédence ou d'hypergraphes de précédence selon le niveau de complexité du problème. Un calcul des complexités des algorithmes respectifs montre qu'ils sont polynomiaux.

Zadeh's paper on fuzzy sets introduced the concept of a class with unsharp boundaries and provided a new qualitative approach to the analysis of complex systems in which linguistic rather than numerical variables are employed to describe system behavior and performance.

A critical study of the morphological data sets used for the most recent analyses of metazoan cladistics exposes a rather cavalier attitude towards character coding. Binary absence/presence coding is ubiquitous, but without any explicit justification. This uncompromising application of Boolean logic in character coding is remarkable since several recent investigations have nominated absence/presence coding as the most problematic coding method available for standard cladistic analysis. Moreover, the prevalence of unspecified “absence” character states in the published data sets introduces a discrepancy between the theoretical foundations of phylogenetic parsimony and current practices in metazoan cladistics. Because phylogenetic parsimony assumes transformation of character states, its effective operation breaks down when not all character states are carefully delimited. Examples of resulting meaningless character state transformations are discussed in two categories: 1) when unspecified “absence” states are plesiomorphic; and 2) when unspecified “absence” states are apomorphic (character reversals). To facilitate future progress in metazoan cladistics, the mandatory link between comparative morphology and character coding needs to be reestablished through a more explicit study of morphological variation prior to character coding, and through a more explicitly experimental approach to character coding.

Deciding the satisfiability of a Quantified Boolean Formula (QBF) is an important research issue in Artificial Intelligence. Many reasoning tasks involving planning [1], abduction, reasoning about knowledge, non monotonic reasoning [2], can be directly mapped into the problem of deciding the satisfiability of a QBF. In this paper we present QuBE, a system for deciding QBFs satisfiability.

The note presents some personal thoughts on Professor S. Rudeanu's scientific and human personality. 1 C.S.Calude and G.Stefanescu (eds.). Automata, Logic, and Computability. Special issue dedicated to Professor Sergiu Rudeanu Festschrift.

NOTE: Text or symbols not renderable in plain ASCII are indicated by [...]. Abstract is included in .pdf document. Human brains are by far superior to computers in solving hard problems like combinatorial optimization and image and speech recognition, although their basic building blocks are several orders of magnitude slower. This observation has boosted interest in the field of artificial networks [20], [37]. The latter are built by interconnecting artificial neurons whose behavior is inspired by that of biological neurons. In this thesis we consider the Boolean version of an artificial neuron, namely, a Linear Threshold (LT) element, which computes a neural-like Boolean function of n binary inputs [32]. An LT element outputs the sign of a weighted sum of its Boolean inputs. The main issues in the study of networks (circuits) consisting of LT elements, called LT circuits, include the estimation of their computational capabilities and limitations and the comparison of their properties with those of traditional Boolean logic circuits based on AND, OR and NOT gates (called AON circuits). For example, there is a strong evidence that LT circuits are more efficient than AON circuits in implementing a number of important functions including the addition, product and division of integers [44], [45]. It is easy to see that an LT element is more powerful than an AON gate, simply because of the freedom one has in selecting the weights. Indeed, different choices of weights produce different Boolean functions. As a matter of fact, the number of n-input Boolean functions that can be implemented by a single LT element is of the order of […], [42], [22]. That additional power comes at the cost of added complexity. Some LT functions require weights that are very different in magnitude, potentially rendering difficult hardware or software implementations of the corresponding LT elements. For that reason, theoretical research in the field of LT circuits has focused on the weights, in particular the power of LT elements with restricted weights. As early as 1971, Muroga, [32], proved that any linear threshold element can be implemented with integer weights. That is, by restricting the magnitudes of the weights to natural numbers, one does not lose any power of the original LT element. We generalize this result to arbitrary subsets of the set of real numbers. For example, we show that one can restrict the weights to be the square of integers, and still be able to realize all LT functions. We ask the following question. What are the conditions on the subset […] which guarantee that all LT functions can be implemented with weights drawn from it? Another aspect of the complexity of the weights is their growth as the number of inputs increases. It has been shown [17], [33], [38], [43] that there exist linear threshold functions that can be implemented by a single threshold element with exponentially growing weights, but cannot be implemented by a threshold element with smaller polynomialy growing weights. In light of that result the above question was dealt with by defining a class, called […], within the set of linear threshold functions: the class of functions with "small" (i.e. polynomialy growing) weights [43]. We focus on a single LT element. Our contribution consists in two novel methods for constructing threshold functions with minimal weights, which allow us to fill up the gap between polynomial and exponential weight growth by further refining the separation. Namely, we prove that the class of linear threshold functions with polynomial-size weights can be divided into subclasses […], according to the degree, d, of the polynomial. In fact, we prove a more general result-—that there exists a linear threshold function for any arbitrary number of inputs and any weight size. Even though some LT functions require weights that grow exponentially with the number of input variables, it has been shown recently, in [13], [18], that such functions can be replaced by a two-layer circuit composed of LT gates with polynomially growing, i.e., small weights. We improve the best known bound on the size of that circuit, presented in [18] by focusing on a particular function with large coefficients. We also derive explicit two-layer circuits. Two layer LT circuits are in general composed of different linear threshold elements, but for some useful Boolean functions, such as parity, addition and product, the gates of the first layer are almost identical. To take advantage of this fact we introduce a new Boolean computing element. Instead of the sign function, it computes an arbitrary (with polynomialy many transitions) Boolean function of the weighted sum of its inputs. We call the new computing element an LTM element, which stands for Linear Threshold with Multiple transitions. The advantages of LTM become apparent in the context of VLSI implementation. Indeed, this new model reduces the layout area of the corresponding symmetric function from […] to O(n). We present a VLSI implementations of both LT and LTM elements. Two kinds of elements were fabricated, programmable and hardwired. The programmable elements use the charge on a floating gate in order to store the values of the weights. For many years, the topic of linear threshold logic, has been approached in two different ways, theory, i.e. computational circuit complexity, [38], [56], and hardware implementation, [48], [40]. Surprisingly, there has been very little interaction between those two approaches. As a whole, the present thesis is one step towards establishing a connection between the theory and implementation of threshold circuits. Its contributions are at three levels. At the theoretical level, new classes of functions such as […] and LTM are defined and their computational power is estimated. At the algorithmic level, we show how to convert real weights to weights drawn from arbitrary subset of the real numbers, e.g., integer weights, we also show how to construct LT functions with minimal weights, and finally we present an algorithm that produces an […] circuit (circuit composed of gates with small weights), that computes the comparison function, COMP. We also present LTM circuits computing useful functions, such as XOR, ADD, PRODUCT. At the implementation level, we show the design, layout and testing of the VLSI implementation of LT and LTM. Establishing a connection between the theoretical and practical aspects of threshold logic will profit both domains by providing solutions for practical problems and by defining new theoretical questions inspired by implementation issues.

Background Apoptosis is a tightly regulated process: cellular survive-or-die decisions cannot be accidental and must be unambiguous. Since the suicide program may be initiated in response to numerous stress stimuli, signals transmitted through a number of checkpoints have to be eventually integrated. Results In order to analyze possible mechanisms of the integration of multiple pro-apoptotic signals, we constructed a simple model of the Bcl-2 family regulatory module. The module collects upstream signals and processes them into life-or-death decisions by employing interactions between proteins from three subgroups of the Bcl-2 family: pro-apoptotic multidomain effectors, pro-survival multidomain restrainers, and pro-apoptotic single domain BH3-only proteins. Although the model is based on ordinary differential equations (ODEs), it demonstrates that the Bcl-2 family module behaves akin to a Boolean logic gate of the type dependent on levels of BH3-only proteins (represented by Bad) and restrainers (represented by Bcl-xL). A low level of pro-apoptotic Bad or a high level of pro-survival Bcl-xL implies gate AND, which allows for the initiation of apoptosis only when two stress stimuli are simultaneously present: the rise of the p53 killer level and dephosphorylation of kinase Akt. In turn, a high level of Bad or a low level of Bcl-xL implies gate OR, for which any of these stimuli suffices for apoptosis. Conclusions Our study sheds light on possible signal integration mechanisms in cells, and spans a bridge between modeling approaches based on ODEs and on Boolean logic. In the proposed scheme, logic gates switching results from the change of relative abundances of interacting proteins in response to signals and involves system bistability. Consequently, the regulatory system may process two analogous inputs into a digital survive-or-die decision.

Two low complexity methods for neural network construction, that are applicable to various neural network models, are introduced and evaluated for high order perceptrons. The methods are based on a Boolean approximation of real-valued data. This approximation is used to construct an initial neural network topology which is subsequently trained on the original (real-valued) data. The methods are evaluated for their effectiveness in reducing the network size and increasing the network's generalization capabilities in comparison to fully connected high order perceptrons.