pith. sign in

arxiv: 1501.02250 · v2 · pith:4EIHRBUSnew · submitted 2015-01-09 · 💻 cs.LO · math.LO

Term satisfiability in FL_ew-algebras

classification 💻 cs.LO math.LO
keywords algebrassatisfiabilitymathrmalgebrapositivesatisfiabletermscase
0
0 comments X
read the original abstract

FL$_\mathrm{ew}$-algebras form the algebraic semantics of the full Lambek calculus with exchange and weakening. We investigate two relations, called satisfiability and positive satisfiability, between FL$_\mathrm{ew}$-terms and FL$_\mathrm{ew}$-algebras. For each FL$_\mathrm{ew}$-algebra, the sets of its satisfiable and positively satisfiable terms can be viewed as fragments of its existential theory; we identify and investigate the complements as fragments of its universal theory. We offer characterizations of those algebras that (positively) satisfy just those terms that are satisfiable in the two-element Boolean algebra providing its semantics to classical propositional logic. In case of positive satisfiability, these algebras are just the nontrivial weakly contractive FL$_\mathrm{ew}$-algebras. In case of satisfiability, we give a characterization by means of another property of the algebra, the existence of a two-element congruence. Further, we argue that (positive) satisfiability problems in FL$_\mathrm{ew}$-algebras are computationally hard. Some previous results in the area of term satisfiability in MV-algebras or BL-algebras are thus brought to a common footing with known facts on satisfiability in Heyting algebras.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.