The Decision Problem On Sheffer Functions In Partial K-Valued Logic

Multiple-valued logic is an important branch of computer science and technology. Although the research on multiple-valued logic covers many aspects, it can be divided into three respects, i.e., multiple-valued logic theory, multiple-valued circuit and system, and application of multiple-valued logic.One important problem in multiple-valued logic theory is the decision on Sheffer functions, which depends on deciding all precomplete sets, and the solution can be reduced to determining the minimal covering of precomplete sets. In this thesis, we mainly study the decision on Sheffer functions in partial k-valued logic.At the beginning, this thesis makes an analysis on the structure theory of complete and partial multiple-valued logic function and in-depth discussion on complete 2-valued logic functions precomplete sets and its minimal covering, and the precomplete sets in complete and partial k-valued logic functions.For the decision on Sheffer functions in partial 2-valued logic, this thesis first uses function sets preserving relations to represent two precomplete sets T(No) and T (N₁) in P₂^* , and then we determine five precomplete sets of eight sets in P₂^* by making use of the idea of "preserving relations".For the decision on Sheffer functions in partial k-valued logic function sets denoted by P_k^*, the thesis first raises the concept about similar relationship between two precomplete sets, and proves that any two precomplete sets persevering similar relationship are either the member of the minimal covering or are not, which provides more simple and convenient methods for the decision on Sheffer functions.According to the completeness theory of partial k-valued logic, the thesis proves that there are three precomplete sets of seven precomplete sets in partial k-valued logic, i.e., function class T_E persevering E, L-type functions class L_G4,2, and pseudo linear function class, which are all the member of the minimal covering.For the other three precomplete classes, the thesis mainly provides us with the sufficient conditions that F_S,m,S_I,m, and S_R,m must meet when m=2,respectively.