Formulas of n variables of Lukasiewicz sentential calculus can be represented, via McNaughton's theorem, by piecewise linear functions, with integer coefficients, from hypercube [0,1]n to [0,1], called McNaughton functions. As a consequence of McNaughton representation, a canonical form of a formula is obtained. Indeed, up to logical equivalence, any formula can be written as an infimum of finite suprema of formulas associated to McNaughton functions which are truncated functions to [0,1] of the restriction to [0,1]n of single hyperplanes, for short, called simple McNaughton functions. In the present paper the authors concern with the problem of presenting formulas of Lukasiewicz sentential calculus in normal from. The main results are: a) an axiomatic description of some classes of formulas having the property to be canonically mapped one-to-one onto the class of simple Mc Naughton functions; b) a normal form for Lukasiewicz sentential calculus, making use of formulas defined in (a); c) the polynomial complexity of formulas, in normal form, coming from a certain class described as in (a) is proved; d) the results described in (a), (b) and (c) are extended to Rational Lukasiewicz logic.
On Normal Forms in Lukasiewicz's Logic / DI NOLA, A; Lettieri, Ada. - In: ARCHIVE FOR MATHEMATICAL LOGIC. - ISSN 0933-5846. - STAMPA. - 43:(2004), pp. 795-823. [10.1007/s00153-004-0230-6]
On Normal Forms in Lukasiewicz's Logic
LETTIERI, ADA
2004
Abstract
Formulas of n variables of Lukasiewicz sentential calculus can be represented, via McNaughton's theorem, by piecewise linear functions, with integer coefficients, from hypercube [0,1]n to [0,1], called McNaughton functions. As a consequence of McNaughton representation, a canonical form of a formula is obtained. Indeed, up to logical equivalence, any formula can be written as an infimum of finite suprema of formulas associated to McNaughton functions which are truncated functions to [0,1] of the restriction to [0,1]n of single hyperplanes, for short, called simple McNaughton functions. In the present paper the authors concern with the problem of presenting formulas of Lukasiewicz sentential calculus in normal from. The main results are: a) an axiomatic description of some classes of formulas having the property to be canonically mapped one-to-one onto the class of simple Mc Naughton functions; b) a normal form for Lukasiewicz sentential calculus, making use of formulas defined in (a); c) the polynomial complexity of formulas, in normal form, coming from a certain class described as in (a) is proved; d) the results described in (a), (b) and (c) are extended to Rational Lukasiewicz logic.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.