1,721,047 research outputs found
Temi geometrici e di teoria della dimostrazione nelle logiche proposizionali di Łukasiewicz
No full textA note on the representation of McNaughton lines by basic literals
No full textWe introduce a syntactically simple subclass of formulas of the infinite-valued logic of Lukasiewicz, the class of basic literals, whose associated McNaughton functions are truncated lines. We present some properties of these formulas and an application to states of MValgebras
A linear space decision procedure for goedel propositional logic
No full textGödel propositional logic is one of the major tnorm based fuzzy logics. Axiomatically, Gödel propositional logic G arises by extending intuitionistic propositional logic with the prelinearity axiom scheme ( → ψ) ∨ (ψ → ). In [9], Fiorino introduces a tableaux calculus yielding a decision procedure for the theoremhood problem of G that has space complexity O(n log n), where n is the length of the input formula. In this paper we provide a decision procedure that has deterministic space complexity O(n)
The Complexity of McNaughton Functions of One Variable
No full textAbstractMcNaughton functions play the same role in Łukasiewicz logics as Boolean functions do in classical logic. Formulas in one variable are an important ingredient of automated deduction in many-valued logics: the aim of this paper is to establish some results on the complexity of the problems of function representation and formula minimization
An asymptotically tight bound on countermodels for Łukasiewicz logic
No full textAbstractLet ϕ be a formula of Łukasiewicz infinite-valued propositional logic having a total of l many occurrences of n distinct propositional variables (call l the length of ϕ). Results in Aguzzoli and Ciabattoni [Finiteness in infinite-valued Łukasiewicz logic, Journal of Logic, Language and Information, 9 (2000) 5–29] show that if ϕ is not a tautology then there is an MV chain A of cardinality⩽⌊(l/n)n⌋+1 together with an evaluation eA of propositional variables in A, such that eA is a countermodel for ϕ, that is eA(ϕ)<1A. We show that for each integer n>0 the function b(n,l)=(l/n)n+1 yields an asymptotically tight upper bound on the maximum cardinality of the smallest MV algebras having countermodels for formulas of length l
Single chain completeness and some related properties
No full textIn 2010 Franco Montagna investigated two interesting properties of the axiomatic extensions of MTL, the single chain completeness (SCC) and the strong single chain completeness (SSCC). An axiomatic extension L of MTL enjoys the SCC if there is an L-chain A s.t. L is complete w.r.t. A, and L enjoys the SSCC if there is an L-chain A s.t. L is strongly complete w.r.t. A. Clearly the SSCC implies the SCC, whilst the converse implication has been left as an open problem. In this work we show that the SCC does not imply the SSCC, and that the SCC and SSCC are strongly related to some logical and algebraic properties relevant for substructural logics, as Halldén completeness (HC) and Deductive Maksimova variable separation property (DMVP). The HC will provide a logical characterization for the SCC, for every axiomatic extension of MTL, whilst the DMVP will be proved to be equivalent to the SSCC, for the n-contractive axiomatic extensions of BL. We conclude by studying the axiomatic extensions of MTL expanded with the Δ operator, by showing that SCC and SSCC always coincide, even in the first-order case
On some questions concerning the axiomatisation of WNM-algebras and their subvarieties
No full textIn a seminal paper Esteva and Godo introduced monoidal t-norm-based logic MTL and some of its prominent extensions such as NM and WNM. We notice that NM is axiomatisable from IMTL, and hence MTL, with one-variable axioms, by instantiating the WNM axiom over one variable. This observation leads us here to study the logic axiomatised by extending MTL by this one-variable axiom. We shall refer to its equivalent algebraic semantics as the variety of GHP-algebras, for those algebras will be shown to form the largest variety of MTL-algebras such that the falsum-free reducts of the positive cones of their chains are the most general totally ordered Gödel hoops. Among other results we obtain a general description of GHP standard algebras, and use the latter to characterise those extensions of WNM that can be obtained from GHP via the same set of extending axioms
On varieties singly generated by a well-connected FLew-algebra
No full textAbstract In this short note we show that given a variety V of FLew-algebras generated by a well-connected algebra, there always exists a subdirectly irreducible algebra generating V. This solves an open problem first raised in Galatos et al., Residuated lattices: an algebraic glimpse at substructural logics (2007)
On countermodels in basic logic
No full textIn [3] the tautology problem for Hájek's Basic Logic BL is proved to be co-NP-complete by showing that if a formula φ is not a tautology of BL then there exists an integer m > 0, polynomially bounded by the length of φ, such that φ fails to be a tautology in the infinite-valued logic mŁ corresponding to the ordinal sum of m copies of the Łukasiewicz t-norm. In this paper we state that if φ is not a tautology of BL then it already fails to be a tautology of a finite set of finite-valued logics, defined by taking the ordinal sum of m copies of k-valued Łukasiewicz logics, for effectively determined integers m, k > 0 only depending on polynomial-time computable features of φ. This result allows the definition of a calculus for mŁ along the lines of [1], [2], while the analysis of the features of functions associated with formulas of mŁ constitutes a step toward the characterization of finitely generated free BL-algebras as algebras of [0, 1]-valued functions
Finitely Presented MV-algebras with Finite Automorphism Group
No full textWe address the question, which MV-algebras have finite automorphism group. We prove that finitely presented MV-algebras whose maximal spectral space has topological dimension not exceeding 1 do have finite automorphism group. We give examples to show that finite presentability is an essential hypothesis. Our proof produces as an interesting by-product a complete graph–theoretic isomorphism invariant for the class of MV-algebras involved
- …
