On non-tabular m-pre-complete classes of formulas in the propositional provability logic
Olga Izbas, Andrei Rusu · 2006
In the present paper we construct an example of an m-pre-complete with respect to functional expressibility class of formulas in the propositional provability logic. There is a well known class of problems in mathematical logic, algebra, discrete mathematics and cybernetics dealing with the possibility of obtaining some functions (operations, formulas) from another ones by means of a fixed set of tools. The notion of expressibility of Boolean functions through other functions by means of superpositions goes back to the works of E. Post[14], [15]. He described all closed (with respect to superpositions) classes of 2-valued Boolean functions. The problem of completeness (with respect to expressibility) which requires to determine the necessary and sufficient conditions for all functions to be expressible via the given system of functions is also investigated. In 1956 ([6, p. 54], [7]) A. V. Kuznetsov established the theorem of completeness according to which we can build a finite set of closed with respect to expressibility classes of functions in the k-valued logics such that any system of functions of this logic is complete if and only if it is not included in any of these classes. In 1965 [19] I. Rosenberg established the criterion of completeness in the k-valued logics formulated in terms of pre-complete classes of functions, i.e. in terms of maximal, incomplete and closed classes of functions.