Generalizing Truth-Functionality
João Marcos · 2006
A common standard for the interpretation of classical propositional logic is set by the functionally complete collection of 2-valued truth-tables. The structure of the free algebra of formulas is faithfully mirrored in the semantics: In each admissible model, each sentential letter freely ranges over the set of truth-values, and to each n-ary logical constant there corresponds a convenient n-ary operator over those same truth-values. The whole approach is easily generalizable so as to define the class of truth-functional logics, i.e., many-valued logics whose operators can be characterized by truth-tables over some convenient set of truth-values. A further interesting generalization of the above idea is produced by the so-called nondeterministic truth-tabular semantics (N-truth-tables), where each n-ary operator is allowed to choose in between a number of possible outputs for each given n-uple of inputs. The set of admissible models may thus be enlarged, allowing for the natural adequate interpretation of more generous classes of non-classical logics. Yet another generalization of the same idea is given by the so-called possible-translations semantics with many-valued ingredients (Manyvalued PTS), where each model of a logic L is given by an admissible translation of L into an appropriate many-valued logic Lk coupled with a standard many-valued valuation from Lk. In the finite-valued case, logics with truth-tabular or N-truth-tabular semantics share interesting meta-properties such as compacity and decidability. Finite-valued PTS are also guaranteed to share those properties as soon as all the corresponding admissible translations are recursively defined. However, several logics known to be uncharacterizable by finite-valued truth-tables can be adequately characterized by finite-valued N-truth-tables, and several logics that have no finite-valued N-truth-tabular characterization can be characterized by finite-valued PTS. The present contribution will examine and illustrate the multiple relations between the three above mentioned alternative styles of semantics. Research developed also under the scope of the cooperation agreement 24P-22335/04 between CLE-UNICAMP and CLC-UTL, with partial support from EU FEDER and FCT. The author is greatly indebted to Arnon Avron, who kindly agreed to present the contribution during the 2005 ASL Winter Meeting.