Top

Journal of Automated Reasoning

Published in:

06-06-2020

Probably Partially True: Satisfiability for Łukasiewicz Infinitely-Valued Probabilistic Logic and Related Topics

Authors: Marcelo Finger, Sandro Preto

Published in: Journal of Automated Reasoning | Issue 7/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We study probabilistic-logic reasoning in a context that allows for “partial truths”, focusing on computational and algorithmic properties of non-classical Łukasiewicz Infinitely-valued Probabilistic Logic. In particular, we study the satisfiability of joint probabilistic assignments, which we call ŁIPSAT. Although the search space is initially infinite, we provide linear algebraic methods that guarantee polynomial size witnesses, placing ŁIPSAT complexity in the NP-complete class. An exact satisfiability decision algorithm is presented which employs, as a subroutine, the decision problem for Łukasiewicz Infinitely-valued (non probabilistic) logic, that is also an NP-complete problem. We investigate efficient representation of rational McNaughton functions in Łukasiewicz Infinitely-valued Logic modulo satisfiability.

previous article Simulating Strong Practical Proof Systems with Extended Resolution

next article Proof-Producing Synthesis of CakeML from Monadic HOL Functions

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

By the term “partial truth” we refer to the concept usually referred in the literature as “degree of truth”, not to be confused with partial valuations or models.

Satisfiability problem in Łukasiewicz Infinitely-valued logic has been shown to be NP-complete [23] and there are some implementations discussed in the literature [3], but there are many implementation options with considerable efficiency differences which are analyzed in [15].

An earlier version of this paper has appeared in [15]. In this work we present proofs of lemmas and theorems that were omitted. Section 5 on representation of rational McNaughton functions is totally new; on the other hand, due to space limitations, implementational and experimental issues have been omitted.

Thus C is more restrictive than the full class of states of an MV-algebra, in the sense of [26], which will not be discussed here.

We abuse the notation by using the same symbols for the propositional variables and for the metavariables in the functions description.

These functions are only different from the Schauder hats in [24] on the values \(\beta _i\in {\mathbb {Q}}\).

Of course, since such classes are identified with rational McNaughton functions, that was already a consequence of Theorem 5.

Aguzzoli, S., Mundici, D.: Weierstrass Approximation Theorem and Łukasiewicz Formulas with One Quantified Variable, pp. 315–335. Physica-Verlag HD, Heidelberg (2003)MATH

Bertsimas, D., Tsitsiklis, J.: Introduction to Linear Optimization. Athena Scientific Series in Optimization and Neural Computation. Athena Scientific, Belmont (1997)

Bofill, M., Manya, F., Vidal, A., Villaret, M.: Finding hard instances of satisfiability in Łukasiewicz logics. In: ISMVL. IEEE, pp. 30–35 (2015)

Boole, G.: An Investigation on the Laws of Thought. Macmillan, London (1854). http://www.gutenberg.org/etext/15114

Borgward, K.H.: The Simplex Method: A Probabilistic Analysis. Algorithms and Combinatorics, vol. 1. Springer, Berlin (1986)

Bova, S., Flaminio, T.: The coherence of Łukasiewicz assessments is NP-complete. Int. J. Approx. Reason. 51(3), 294–304 (2010). https://doi.org/10.1016/j.ijar.2009.10.002CrossRefMATH

Cignoli, R., d’Ottaviano, I., Mundici, D.: Algebraic Foundations of Many-Valued Reasoning. Trends in Logic. Springer, Berlin (2000)CrossRef

de Finetti, B.: La prévision: Ses lois logiques, ses sources subjectives (1937)

de Finetti, B.: Sul significato soggettivo della probabilità. Fundam. Math. 17(1), 298–329 (1931)CrossRef

10.

de Finetti, B.: Theory of Probability: A Critical Introductory Treatment. Translated by Antonio Machí and Adrian Smith. Wiley, Hoboken (2017)CrossRef

11.

Eckhoff, J.: Helly, Radon, and Caratheodory type theorems. In: Gruber, P.M., Wills, J.M. (eds.) Handbook of Convex Geometry, pp. 389–448. Elsevier Science Publishers (1993)

12.

Esteva, F., Godo, L., Montagna, F.: The Ł\(\Pi \) and Ł\(\Pi \frac{1}{2}\) logics: two complete fuzzy systems joining Łukasiewicz and product logics. Arch. Math. Logic 40(1), 39–67 (2001)MathSciNetCrossRef

13.

Finger, M., Bona, G.D.: Probabilistic satisfiability: logic-based algorithms and phase transition. In: Walsh, T. (ed.) IJCAI, IJCAI/AAAI, pp. 528–533 (2011)

14.

Finger, M., De Bona, G.: Probabilistic satisfiability: algorithms with the presence and absence of a phase transition. AMAI 75(3), 351–379 (2015). https://doi.org/10.1007/s10472-015-9466-6MathSciNetCrossRefMATH

15.

Finger, M., Preto, S.: Probably half true: probabilistic satisfiability over Łukasiewicz infinitely-valued logic. In: Galmiche, D., Schulz, S., Sebastiani, R. (eds.) Automated Reasoning, pp. 194–210. Springer, Cham (2018)CrossRef

16.

Georgakopoulos, G., Kavvadias, D., Papadimitriou, C.H.: Probabilistic satisfiability. J. Complex. 4(1), 1–11 (1988). https://doi.org/10.1016/0885-064X(88)90006-4MathSciNetCrossRefMATH

17.

Gerla, B.: Rational Łukasiewicz logic and DMV-algebras. Neural Netw. World 11(6), 579–594 (2001)MathSciNet

18.

Hähnle, R.: Towards an efficient tableau proof procedure for multiple-valued logics. In: Börger, E., Kleine Büning, H., Richter, M.M., Schönfeld, W. (eds.) Computer Science Logic, pp. 248–260. Springer, Heidelberg (1991)CrossRef

19.

Hansen, P., Jaumard, B.: Algorithms for the maximum satisfiability problem. Computing 44, 279–303 (1990). https://doi.org/10.1007/BF02241270MathSciNetCrossRefMATH

20.

Hansen, P., Jaumard, B.: Probabilistic satisfiability. In: Handbook of Defeasible Reasoning and Uncertainty Management Systems, vol. 5, p. 321. Springer (2000)

21.

Kavvadias, D., Papadimitriou, C.H.: A linear programming approach to reasoning about probabilities. AMAI 1, 189–205 (1990). https://doi.org/10.1007/BF01531078CrossRefMATH

22.

McNaughton, R.: A theorem about infinite-valued sentential logic. J. Symb. Logic 16, 1–13 (1951)MathSciNetCrossRef

23.

Mundici, D.: Satisfiability in many-valued sentential logic is NP-complete. Theor. Comput. Sci. 52(1–2), 145–153 (1987)MathSciNetCrossRef

24.

Mundici, D.: A constructive proof of McNaughton’s theorem in infinite-valued logics. J. Symb. Logic 59(2), 596–602 (1994)MathSciNetCrossRef

25.

Mundici, D.: Bookmaking over infinite-valued events. Int. J. Approx. Reason. 43(3), 223–240 (2006). https://doi.org/10.1016/j.ijar.2006.04.004MathSciNetCrossRefMATH

26.

Mundici, D.: Advanced Łukasiewicz Calculus and MV-Algebras. Trends in Logic. Springer, Dordrecht (2011)CrossRef

27.

Nilsson, N.: Probabilistic logic. Artif. Intell. 28(1), 71–87 (1986)MathSciNetCrossRef

28.

Papadimitriou, C., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Dover, New York (1998)MATH

Title: Probably Partially True: Satisfiability for Łukasiewicz Infinitely-Valued Probabilistic Logic and Related Topics
Authors: Marcelo Finger
Sandro Preto
Publication date: 06-06-2020
Publisher: Springer Netherlands
Published in: Journal of Automated Reasoning / Issue 7/2020
Print ISSN: 0168-7433
Electronic ISSN: 1573-0670
DOI: https://doi.org/10.1007/s10817-020-09558-9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 7/2020

Simulating Strong Practical Proof Systems with Extended Resolution

ICE-Based Refinement Type Discovery for Higher-Order Functional Programs

Preface: Special Issue of Selected Extended Papers from IJCAR 2018

Synthesizing Precise and Useful Commutativity Conditions

Proof-Producing Synthesis of CakeML from Monadic HOL Functions

From QBFs to MALL and Back via Focussing

Premium Partner