(p,q)論理関数の出力s固定,p-s閉集合のs-(p,q)論理完全性について

Abstract

The multiple-valued logic (M-V Logic) has been studied in various points of view. Above all, as VLSI has become important in constructing computers, problems such as the complexity of the interconnections in VLSI and the severe restriction of the number of pins have become very important, and their solution is expected to require, for example, M-V Logic. Therefore, we have proposed the idea of the p-valued input, q-valued output logic ((p, q)-Logic), where 2≦q≦p, 3≦p. The idea stems from the considerations that (1) the inputs of the threshold elements can be very easily extended to the p-valued case, while (2) the extention of the outputs of the threshold elements to the p-valued case is difficult because the number of necessary thresholds increases. In this paper, the condition of the s-(p, q)-logical completeness for the output s-coherent, (p, s)-closed set of the (p, q)-logical functions is discussed. As a result, the condition is seen to be almost equivalent to the q-valued one. From the result, it may be expected that the studies and the costs of networks in M-V Logic are almostly reduced to the 2-valued one by selecting q≳2.