nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Reconciling First-Order Logic to Algebra

verfasst von : Walter Carnielli, Hugo Luiz Mariano, Mariana Matulovic

Erschienen in: Contradictions, from Consistency to Inconsistency

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We start from the algebraic method of theorem-proving based on the translation of logic formulas into polynomials over finite fields, and adapt the case of first-order formulas by employing certain rings equipped with infinitary operations. This paper defines the notion of M-ring, a kind of polynomial ring that can be naturally associated to each first-order structure and each first-order theory, by means of generators and relations. The notion of M-ring allows us to operate with some kind of infinitary version of Boolean sums and products, in this way expressing algebraically first-order logic with a new gist. We then show how this polynomial representation of first-order sentences can be seen as a legitimate algebraic semantics for first-order logic, an alternative to cylindric and polyadic algebras and closer to the primordial forms of algebraization of logic. We suggest how the method and its generalization could be lifted successfully to n-valued logics and to other non-classical logics helping to reconcile some lost ties between algebra and logic.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Quantitative Logic Reasoning

Nächstes Kapitel Plug and Play Negations

In this paper “ring” always means commutative ring with unity.

Distinct, obviously, from Boolean algebras.

The operator

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-98797-2_13/470618_1_En_13_IEq47_HTML.gif

clearly induces a finitary closure operator \( \overline{( \ )} : Parts(F[X]) \rightarrow Parts(F[X])\), in particular,

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-98797-2_13/470618_1_En_13_IEq49_HTML.gif

iff exists \(S' \subseteq _{fin} S\) such that

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-98797-2_13/470618_1_En_13_IEq51_HTML.gif

The symbol

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-98797-2_13/470618_1_En_13_IEq81_HTML.gif

denotes “reduction by means of polynomial rules”; in order to ease reading, however, we shall use the symbol \(\approx \) everywhere when there is no danger of misunderstanding.

It is convenient to show that any finite function can be expressed by means of polynomials over finite fields using two different methods for this: Lagrange interpolations and by solving linear systems. For more details, see [11, 18].

In more details, \(v^F\) is recursively defined by: \(v^F(P_i) := v(P_i),\ v^F(\alpha \wedge \beta ) := v^F(\alpha ) \wedge v^F(\beta ),\ v^F(\alpha \vee \beta ) := v^F(\alpha ) \vee v^F(\beta ),\ v^F(\alpha \rightarrow \beta ) := v^F(\alpha ) \rightarrow v^F(\beta ),\ v^F(\lnot \alpha ) := \lnot v^F(\alpha )\).

By definition, \(\prod S =1\) whenever \(S = \emptyset \).

In a Boolean ring, \(ab =1\) iff \(a =b=1\). Indeed: if \(ab =1\), then \( 1= ab = a^2b =a(ab) = a.1 =a\).

However, it must be noted that a heterodox proposal to algebraize paraconsistent logics is proposed in [6].

I.e., if \((p,p') \in C\) and \((q,q') \in C\), then: \((-p,-p') \in C\), \((p + q, p' + q') \in C\), \((p . q, p'.q') \in C\).

Note that the gluing \(S_{i,a} : |F(M)| \rightarrow |F(M)|\) preserves rank.

Remember that \(rank(S_{i,a}(r) = rank(r)\).

Remember the identifications in Exercise 27.

This rule is equivalent to \(r \rightarrow r \approx 1\), since \((r\rightarrow r) = r.r+r+1\) and R(M) is, by construction, a ring of characteristic 2, i.e. the “index rule” \(r+r = 0\) is already true in R(M).

I.e., for each M-homomorphism \(\mathscr {M}\)-compatible \(H : R(M) \rightarrow \mathbb {Z}_2\), the left and the right side of the rule have the same image under H.

By the distributive law in \(R(\mathscr {M})\) and \({r + r = 0} \).

By the correct rule \(r .(1+r)\approx 0\).

In fact, \(j^{\star }\) constitutes a contravariant from the category of \(L'\)-structures and \(L'\)-homomorphisms into the category of L-structures and L-homomorphisms: if \(h : \mathscr {M}' \rightarrow \mathscr {N}'\) is a \(L'\)-homomorphism, then the same map \(h : j^{\star }(\mathscr {M}') \rightarrow j^{\star }(\mathscr {N}')\) is an L-homomorphism.

I.e., the class of pairs \(\mathscr {M}= (M, [[-]])\), where M is set, \([[-]]\) is a map \((\phi (x_1, \ldots , x_k) \in Form(L)) \ \mapsto \ ([[\phi (\bar{x})]] : M^k \longrightarrow B_T)\), satisfying the usual (but conditional, since \(B_T\) may not be complete) compatibility requirements of Boolean valued models and, moreover, if \(\phi (x_1, \ldots , x_k) \in T\), then \([[\phi (\bar{x})]] = 1_{B_{T}}\).

Agudelo, J.C., and W.A. Carnielli. 2011. Polynomial Ring Calculus for modal logics: a new semantics and proof method for modalities. The Review of Symbolic Logic 4: 150–170.

Béziau, J. -Y. 2007. Logica Universalis: Towards a general theory of Logic. Springer.

Béziau, J. -Y. 2012. Universal Logic: an Anthology - From Paul Hertz to Dov Gabbay. Springer.

Blok, W.J. and D. Pigozzi. 1989. Algebraizable Logics. Memoirs of the AMS. 396, American Mathematical Society, Providence, USA.

Boole, G. 1847. The Mathematical Analysis of Logic, Being an Essay Towards a Calculus of Deductive Reasoning. Cambridge: Macmillan.

Bueno-Soler, J., and W.A. Carnielli. 2005. Possible-translations algebraization for paraconsistent logics. Bulletin of the Section of Logic 34 (2): 77–92.

Burris, S. 2000. The Laws of Boole’s Thought. Citeseer. https://www.math.uwaterloo.ca/~snburris/htdocs/MYWORKS/PREPRINTS/aboole.pdf.

Carnielli, W.A. 2001. A polynomial proof system for Łukasiewicz logics. In Second Principia International Symposium, pp. 6–10.

Carnielli, W.A. 2005. Polynomial ring calculus for many-valued logics. In Proceedings of the 35th International Symposium on Multiple-Valued Logic, IEEE Computer Society, pp. 20–25.

10.

Carnielli, W.A. 2005. Polynomial Ring Calculus for Logical Inference. CLE e-Prints 5: 1–17.

11.

Carnielli, W.A. 2007. Polynomizing: Logic Inference in Polynomial Format and the Legacy of Boole. In Model-Based Reasoning in Science, Technology, and Medicine, ed. by L. Magnani, P. Li, vol. 64, pp. 349–364. Springer.

12.

Carnielli, W.A. 2010. Formal polynomials, heuristics and proofs in logic. In Logical Investigations, ed. by A.S. Karpenko, vol. 16, pp. 280-294. Institute of Philosophy, Russian Academy of Sciences Publisher.

13.

Carnielli, W.A., M.E. Coniglio, and J. Marcos. 2007. Logics of Formal Inconsistency. In Handbook of Philosophical Logic, ed. by D. Gabbay, F. Guenthner, vol. 14, pp. 15–107. Springer.

14.

Carnielli, W.A., and M. Matulovic. 2014. Non-deterministic semantics in polynomial format. Electronic Notes in Theoretical Computer Science 305: 19–34.CrossRef

15.

Halmos, P.R. 1962. Algebraic Logic. Chelsea Publishing Co.

16.

Henkin, L., J.D. Monk, A. Tarski. 1981. Cylindric Set Algebras and related structures. Lecture Notes in Mathematics, vol. 883, pp. 1–129. Springer.

17.

Henkin, L., J.D. Monk, and A. Tarski. 1985. Cylindric Algebras: Part II. Studies in Logic and the Foundations of Mathematics, vol. 115, North-Holland.

18.

Matulovic, M. 2013. Proofs in the Pocket: Polynomials as a Universal Method of Proof. Ph.D. Thesis State University of Campinas (Unicamp), Brazil.

19.

Moore, G.H. 1988. The emergence of first-order logic. In History and Philosophy of Modern Mathematics, ed. by W. Aspray, P. Kitcher, pp. 95–135. University of Minnesota Press.

20.

Pinter, C.C.A. 1973. A simple algebra of first order logic. Notre Dame Journal of Formal Logic XIV(3): 361–366.

21.

Peckhaus, V. 1998. Hugh MacColl and the German algebra of logic. Nordic Journal of Philosophical Logic 3 (1): 17–34.

22.

Sheffer, H.M. 1913. A set of five independent postulates for Boolean algebras, with application to logical constants. Transactions of the American Mathematical Society 14 (4): 481–488.CrossRef

Titel: Reconciling First-Order Logic to Algebra
verfasst von: Walter Carnielli
Hugo Luiz Mariano
Mariana Matulovic
Verlag: Springer International Publishing
Buch: Contradictions, from Consistency to Inconsistency
Print ISBN: 978-3-319-98796-5

Electronic ISBN: 978-3-319-98797-2

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-98797-2_13

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner