Jeffrey Beckman and T. C. Wesselkamper
The City University of New York
If f is a two place function over E(k) that is either Sheffer or Sheffer with constants, then the radius of f is that least natural number r such that each two-place function over E(k) that can be defined as a composition of r or fewer copies of f. The radii of the 322 isotopy classes of Sheffer functions over E(3) are calculated. A sequence of useful conditions that a Shaffer function have small radius is developed; a sequence of useful conditions that a symmetric Sheffer function have small radius is developed.
Grant Pogosyan
International Christian University
Mitaka, Tokyo-181, Japan
E-mail: grant@icu.ac.jp
Akihiro Nozaki
Otsuma Women's University
Tama, Tokyo, Japan
E-mail: nozaki@csc.otsuma.ac.jp
We study a problem of representation for the lattice of clones of multiple valued logic functions. It is a problem of description of a generating system of clones, from which the whole lattice, or a given sublattice, can be reconstructed by synthesis. The "synthetic means" considered is the join operation for lattice elements. The generating set of clones is defined to be the set of all join-irreducible elements. All atoms of the lattice are among them, which "automatically" makes the problem difficult. We give a criterion for a clone to be join-irreducible. The problem is easier for the particular case of transformation monoids, i.e. for the sublattice of clones that contain only essentially unary functions. We find constructive criteria for monoids and atoms, that are join-irreducible. We show a graph theoretical property of the lattice, which in general case is different from that of the binary case. Finally, we see that any one-variable function of k-valued logic, with k<5, generates a join-irreducible clone.
Keywords: multi-valued logic, clone lattice, monoid
Zuoquan Lin
Shantou University, Shantou 515063, P.R.China
In this paper we describe paraconsistent circumscription by application of predicate circumscription in a paraconsistent logic. In addition to circumscribe the predicates, we also circumscribe the inconsistency. Paraconsistent circumscription can be well characterized by the minimal semantics that is both nonmonotonic and paraconsistent. It brings us advantages at least in two respects: nonmonotonic logic would be nontrivial while there was a contradiction, and paraconsistent logic would be equivalent to classical logic while there was no direct effect of a contradiction.
Keywords: paraconsistent logic, logic of paradox, nonmonotonic logic, circumscription, minimal model
Zuoquan Lin and Wei Li
Shantou University, Shantou 515063, P.R.China
Priest introduced nonmonotonicity into a paraconsistent logic, so-called logic of paradox LP, that yields a solution to the weakness of paraconsistent logic. The resulting logic (of minimal paradox) LP_m is nonmonotonic in the sense that inconsistency is minimal. The problem of proof theory of logic LP_m left open because the base logic LP is paraconsistent so that syntactic formulations of nonmonotonic logic are not available for LP_m, though LP_m is well characterized by minimal semantics. In this paper, we will provide a minimal tableaux as a satisfactory proof theory for LP_m. We first present a signed tableaux for LP. Then minimal tableaux for LP_m is obtained by revising signed tableaux for LP to fit LP_m in which the branches of non-minimally-inconsistent models of the tableaux are eliminated. The soundness and completeness theorems of the tableaux with respect to the semantics of LP and LP_m are proved, respectively.
Keywords: tableaux, logic of paradox, paraconsistent logic, minimal inconsistent model, nonmonotonicity
Hiroaki Kikuchi, Noboru Takagi, Shohachiro Nakanishi and Masao Mukaidono
A multiple-valued Kleenean function is a mapping f:[0,1]^n into [0,1], which is representable by a logic formula consisting n variables, three logical connectives, and any constant value of [0,1]. In this paper, some properties of the partially specified multiple-valued Kleenean functions by a subset A of [0,1] are investigated and the identification problem of logic formula is solved. The main result is a necessary and sufficient condition that a mapping f:A into [0,1] to be a unique Kleenean function.
A.K. Jain
Canadian Microelectronics Corp.
Queen's University
M.H. Abd-El-Barr
King Fahd Univ. of Petroleum & Minerals
R.J. Bolton
Univ. of Saskatchewan
In the past, several heuristic-based programs have been reported to obtain an efficient sum-of-product (SOP) form expression for a given MVL function using the literal, min, and tsum set of operators. HAMLET, one of these programs, includes implementation of many earlier reported heuristic-based algorithms. In HAMLET, the Gold heuristic chooses the best realization after applying all other heuristics implemented. In this paper a new heuristic-based program is reported for the realization of MVL functions in SOP form using the literal, cycle, complement of literal, complement of cycle, min, and tsum set of operators. It is known that the cost, in terms of the number of transistors, of realizing this set of operators (in current-mode CMOS) and that of existing sets of operators is comparable [1]. For a random sample of 4-valued, 2-variable functions the realizations have been compared for the developed program and HAMLET (Gold). The average number of PTs required by the developed program and HAMLET (Gold) were 5.53 and 6.62, respectively.
Keywords: Current-Mode CMOS, MVL Operators, Minimization, Direct Cover, Heuristic Algorithm
Satoshi Sakurai, Takafumi Aoki , and Tatsuo Higuchi
Tohoku University
sakurai@higuchi.ecei.tohoku.ac.jp
This paper presents wire-free computing circuits using optical wave-casting to provide a solution to the interconnection problems in parallel processing. The ``wave-casting'' implies wire-free communication scheme, where intensity-modulated optical signals are employed as information carriers and their frequencies represent the information in the system. In wave-casting-based parallel processing, each processing element broadcasts its output in its unique frequency. The frequencies thus produced are multiplexed in free space, and are selectively received at the specified destination to achieve wire-free communication among the processing elements. This paper discusses the design of wire-free logic circuits based on this principle and its application to a fully parallel visual processing system.
Yuji Ohi, Takafumi Aoki, and Tatsuo Higuchi
Tohoku University
Fax number : (+81)22-263-9406
E-mail add. : ohi@higuchi.ecei.tohoku.ac.jp
This paper presents Redundant Complex Number Systems (RCNSs) --- new complex number representations for high-speed arithmetic circuits. RCNS is a positional number system that has a complex radix rj and a digit set {-a,...,0,...,a}, where r>=2 and (r^2 -1)/2 <= a <= r^2 -1. The use of complex radix rj allows additions and multiplications of complex numbers to be done without treating real part and imaginary part separately. Also the redundancy in the number representation enables carry-free addition as well as binary-tree multiple-operand addition. This paper discusses the basic arithmetic algorithms of RCNSs and their implementations.
Takao Waho
NTT LSI Laboratories
Progress in multiple-valued logic (MVL) depends much on the development of devices that are inherently suitable for MVL operation. With their multiple stable states, resonant tunneling devices are promising candidates. Although not at a matured stage yet, resonant tunneling transistors (RTTs), as well as diodes (RTDs), are expected to be indispensable for MVL practical applications in the near future. In this paper, state-of-the-art RTT technology is reviewed with some issues to be solved. Possible applications are also discussed in terms of coupled-quantum-well base RTTs and monostable-multistable logic circuits.
Keywords: resonant tunneling, quantum functional device, quantum well, negative differential resistance, multiple stable states
Morihiro Ryu and Michitaka Kameyama
Tohoku University
ryu@kameyama.ecei.tohoku.ac.jp
Design of highly parallel multiple-valued circuits for k-ary operations with minimum critical path delay is discussed. The linear circuit for a k-ary operation can be designed by superposition of k unary operations. The code assignment of the symbols must be consistent in all the unary operations. Moreover, a set of the sparse representation matrices must be found to make the circuit parallel. In this paper, a new design method is proposed based on the extended representation matrices having the same degree of sparseness with the companion matrices. As a fundamental of a general case, the k-ary operations composed of non-permutation unary operations are discussed. In the non-permutation circuit, the output digit is connected with either of a constant or an input digit. The determination of the directly connected digits based on the concepts of "successor" and "predecessor" is effectively employed for the consistent code assignment in the decomposed unary operations.
Keywords: Linear digital circuit, K-ary operation, Sparse matrix, Code condition
Jens K. Madsen
Technical University of Denmark
Email: jkm@emi.dtu.dk
Stephen I. Long
University of California, Santa Barbara
Email: long@ece.ucsb.edu
This paper describes the design and implementation of a high-speed Interconnect Network (ICN) for a Multiprocessor System using ternary logic. By using ternary logic and a fast point-to-point technique called STARI (Self-Timed At Receiver's Input), the communication between the processors is free of clock skew and insensitive to any delay differences in buffers and wires. In addition, the number of signal wires and pins are reduced by 50 percent in comparison with a similar binary implementation. The ICN architecture is based on crossbar topology and the high-speed part consists of two LSI GaAs chips, Interface and Crossbar, which were implemented in a 0.8 um MESFET process. In a 4x4 ICN, communication at 300 Mbit/s per wire was demonstrated, which is twice as fast as pure synchronous and four times faster than pure asynchronous communication in the specific test set-up.
Keywords: Ternary Logic, Interprocessor Communication, Self-Timed, High-Speed, GaAs
T. C. Wesselkamper
Hunter College and The Graduate School and University Center
The City University of New York
Joshua Danowitz
Hunter College
The City University of New York
This paper describes each of the operations involved in a genetic algorithm: reproduction, mutation, and selection, and discusses each in the language of classical multiple-valued logic. The differences among forms of reproduction that have been used by various researchers are examined and the relative importance of each of the operations in searching for highly fit members of a population is evaluated. The role of mutation in ensuring the completeness of the set of genetic operators is established. A recently proposed form of selection is shown to force convergence of the genetic algorithm, independently of reproduction and mutation. Finally, the theorems developed are applied to practical problems in the use of genetic algorithms.
Zheng Tang, Okihiko Ishizuka, and Koichi Tanno
Miyazaki University
tang@esl.miyazaki-u.ac.jp
This paper describes a learning multiple-valued logic (MVL) network based on back propagation. The learning MVL network is derived directly from a canonical realization of MVL functions and therefore its functional completeness is guaranteed. We extend traditional back propagation to include the prior human knowledge on the MVL networks, for example, the architecture and the number of hidden units and layers. The prior knowledge from the MVL canonical form can be used as initial parameters of the learning MVL network in its learning process. As a result, the prior knowledge can guide the back propagation learning process to get started from a point in the parameter space that is not far from the optimal one, thus, back propagation can fine-tune the prior knowledge for achieving a desired output. This cooperative relation between the prior knowledge and the back propagation learning process is not always present in neural networks. Simulation results are also given to confirm the effectiveness of the methods.
Keywords: Multiplie-valued logic, Learning, Back propagation, Networks
E.V. Dubrova, D.B. Gurov, and J.C. Muzio
University of Victoria
The evaluation of a method for test generation for MVL circuits, based on the notion of full sensitivity, is given. The estimation is made on the functional level, by establishing a lower bound on the number of m-valued n-variable functions that are fully sensitive to all their variables. It is shown, that for practical values of m and n, the fraction of functions not fully sensitive to all their variables is extremely small. The consequences of this result in terms of test generation are discussed.
Keywords: multiple-valued logic circuits, test generation, full sensitivity
Hajime Machida
Hitotsubashi University
E-mail: machida@math2.mori.hit-u.ac.jp
Let O_k denote the set of all multi-variable functions over E_k into E_k where E_k is a k-element set (k\geq 2). A clone over E_k is a subset of O_k which is closed under composition. The set L_k of all clones over E_k is called the clone space. The structure of L_2 is completely known since E. Post, but, for k \geq 3, the structure of L_k seems extremely complicated and is still mostly unknown. In this paper, in order to get better perspective on L_k, we firstly propose to define finitary approximation of L_k, which is some simplified structure of L_k. Then, motivated by this concept, a metric function is introduced into the clone space L_k. As a metric space, L_k is shown to have such properties as completeness, totally-boundedness and compactness. Moreover, it is shown that if a clone C is an isolated point in L_k, it is finitely generated.
Keywords: Clone of multiple-valued functions, Post lattice, Metric space
Rolf Drechsler, Rolf Krieger, and Bernd Becker
Johann Wolfgang Goethe-University
email:
In this paper we present a fault simulator for Multi-Valued Logic Networks (MVLN). With this tool we investigate their Random Pattern Testability (RPT). We show for a restricted class of multi-valued circuits that the RPT is better than for two-valued circuits. We point out the relation between redundancies in two- and multi-valued logic networks. Moreover we show that the role of fault simulation for MVLNs is more important than in the binary case. A set of experimental results for large circuits emphasizes the efficiency of our approach.
Xiaowei Deng, Takahiro Hanyu, and Michitaka Kameyama
Graduate School of Information Sciences
Tohoku University
Aoba, Aramaki, Aoba-ku, Sendai 980-77, Japan
The investigation of the device functions required from the systems point of view is important for the development of the next generation of VLSI devices and systems. A super pass transistor (SPT) model is presented as a quantum device candidate for future multiple-valued VLSI systems. Since it has the powerful capability of multiple-signal-level detection, the SPT will be useful for implementing highly compact multiple-valued VLSI systems. To efficiently exploit the functionality of the SPT, a super pass gate (SP-gate) corresponding to a single SPT is proposed as a multiple-valued universal logic module. Mathematical properties of the SP-gate and a method for designing SP-gate networks are described. An application of SP-gates to a multiple-valued image processing system is also demonstrated.
Keywords: Multiple-valued logic, Super pass gate, Super pass transistor model, Quantum devices, Logic design