Abstract
This article reports on research done in the intersection between many-valued logics and logical calculi related to tableaux. A lot of important issues in many-valued logic, such as algebras arising from many-valued logic, many-valued function minimization, philosophical topics, or applications are not discussed here; for these, we refer the reader to general monographs and overviews such as [Rosser and Turquette, 1952; Rescher, 1969; Urquhart, 1986; Bole and Borowik, 1992; Malinowski, 1993; Hähnle, 1994; Panti, to appear]. More questionable, perhaps, than the omissions is the need for a handbook chapter on tableaux for many-valued logics in the first place.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
A. Avron. Natural 3-valued logics—characterization and proof theory. Journal of Symbolic Logic, 56 (1): 276–294, 1991.
M. Baaz and C. G. Fermüller. Nonelementary speedups between different versions of tableaux. In Peter Baumgartner, Reiner Hähnle, and Joachim Posegga, editors, Proc. 4th Workshop on Deduction with Tableaux and Related Methods, St. Goar, Germany, volume 918 of LNCS, pages 217–230. Springer-Verlag, 1995.
M. Baaz and C. G. Fermüller. Resolution-based theorem proving for many-valued logics. Journal of Symbolic Computation, 19 (4): 353–391, April 1995.
M. Baaz and R. Zach. Note on calculi for a three-valued logic for logic programming. Bulletin of the EATCS, 48: 157–164, 1992.
B. Becker and R. Drechsler. Efficient graph-based representation of multi-valued functions with an application to genetic algorithms. In Proc. 24th International Sym- posium on Multiple-Valued Logic, Boston/MA, pages 65–72. IEEE Press, Los Alamitos, May 1994.
B. Beckert, R. Hähnle, K. Geiß, P. Oel, C. Pape, and M. Sulzmann. The Many-Valued Tableau-Based Theorem Prover 374P, Version 4.0. Interner Bericht 3/96, Universität Karlsruhe, Fakultät fur Informatik, 1996.
B. Beckert, R. Hähnle, P. Oel, and M. Sulzmann. The tableau-based theorem prover 3T4P, version 4.0. In Michael McRobbie and John Slaney, editors, Proc. 13th Conference on Automated Deduction, New Brunswick/NJ, USA,volume 1104 of LNCS,pages 303–307. Springer-Verlag, 1996.
B. Beckert, R. Hähnle, and P. H. Schmitt. The even more liberalized 5-rule in free variable semantic tableaux. In G. Gottlob, A. Leitsch, and D. Mundici, editors, Proceedings of the third Kurt Gödel Colloquium KGC’93, Brno, Czech Republic,volume 713 of LNCS,pages 108–119. Springer-Verlag, August 1993.
A. Blikle. Three-valued predicates for software specification and validation. Fundamenta Informaticae, XIV: 387–410, 1991.
A. Bloesch. Tableau style proof systems for various many-valued logics. Technical Report 94–18, Software Verification Research Center, Dept. of Computer Science, University of Queensland, April 1994.
L. Bolc and P. Borowik. Many-Valued Logics. 1: Theoretical Foundations. Springer-Verlag, 1992.
G. Boole. An Investigation of the Laws of Thought. Walton, London, 1854. Reprinted by Dover Books, New York, 1954.
K. S. Brace, R. L. Rudell, and R. E. Bryant. Efficient implementation of a BDD package. In Proc. 27 th ACM/IEEE Design Automation Conference,pages 40–45 IEEE Press, Los Alamitos, 1990.
R. K. Brayton, G. D. Hachtel, C. T. McMullen, and A. L. SangiovanniVincentelli. Logic Minimization Algorithms for VLSI Synthesis. Kluwer, Boston, 1984.
R. K. Brayton, P. C. McGeer, J. V. Sanghavi, and A. L. Sangiovanni-Vincentelli. A new exact minimizer for two-level logic synthesis. In Tsutomu Sasao, editor, Logic Synthesis and Optimization, chapter 1, pages 1–32. Kluwer, Norwell/MA, USA, 1993.
F. M. Brown. Boolean Reasoning. Kluwer, Norwell/MA, USA, 1990.
M. Broy, C. Facchi, R. Grosu, R. Hettler, H. Hussmann, Dieter Nazareth, Franz Regensburger, and Ketil Stolen. The requirement and design specification language Spectrum, an informal introduction, version 1.0. Technical report, Institut fir Informatik, Technische Universität München, March 1993.
R. E. Bryant and C.-J. H. Seger. Formal verification of digital circuits using symbolic ternary system models. In E. M. Clarke and R. P. Kurshan, editors, Computer-Aided Verification: Proc. of the 2nd International Conference CAV’90, LNCS 531, pages 33–43. Springer-Verlag, 1991.
R. E. Bryant. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers, C-35: 677–691, 1986.
J. R. Burch, E. M. Clarke, K. L. McMillan, and D. L. Dill. Sequential circuit verification using symbolic model checking. In Proc. 27th Design Automation Conference (DAC 90),pages 46–51, 1990.
W. Camielli. An algorithm for axiomatizing and theorem proving in finite many-valued propositional logics. Logique et Analyse, 28 (112): 363–368, 1985.
W. A. Camielli. Systematization of finite many-valued logics through the method of tableaux. Journal of Symbolic Logic, 52 (2): 473–493, June 1987.
W. A. Camielli. On sequents and tableaux for many-valued logics. Journal of Non-Classical Logic, 8 (1): 59–76, May 1991.
B. A. Davey and H. A. Priestley. Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press, Cambridge, 1990.
P. Doherty. Preliminary report: NM3 — a three-valued non-monotonic formalism. In Z. Rag, M. Zemankova, and M. Emrich, editors, Proc. of 5th Int. Symposium on Methodologies for Intelligent Systems, Knoxville, TN, pages 498–505. North-Holland, 1990.
P. Doherty. A constraint-based approach to proof procedures for multi-valued logics. In First World Conference on the Fundamentals of Artificial Intelligence WOCFAI-91, Paris, 1991.
P. Doherty. NML3 — A Non-Monotonic Formalism with Explicit Defaults. PhD thesis, University of Linköping, Sweden, 1991.
G. W. Dueck and J. T. Butler. Multiple-valued logic operations with universal literals. In Proc. 24th International Symposium on Multiple-Valued Logic, Boston/MA, pages 73–79. IEEE Press, Los Alamitos, May 1994.
G. Epstein. The lattice theory of Post algebras. Transactions of the American Mathematical Society, 95 (2): 300–317, May 1960.
M. C. Fitting. Bilattices and the semantics of logic programming. Journal of Logic Programming, 11 (2): 91–116, August 1991.
M. C. Fitting. First-Order Logic and Automated Theorem Proving. Springer-Verlag, New York, 1996. First edition, 1990.
S. Gerberding. DT—an automated theorem prover for multiple-valued first-order predicate logics. In Proc. 26th International Symposium on Multiple-Valued Logics, Santiago de Compostela, Spain, pages 284–289. IEEE Press, Los Alamitos, May 1996.
M. L. Ginsberg. Multi-valued logics. Computational Intelligence, 4 (3), 1988.
R. Hähnle. Towards an efficient tableau proof procedure for multiple-valued logics. In Egon Börger, Hans Kleine Büning, Michael M. Richter, and Wolfgang Schönfeld, editors, Selected Papers from Computer Science Logic, CSL’90, Heidelberg, Germany, volume 533 of LNCS, pages 248–260. Springer-Verlag, 1991.
R. Hähnle. Uniform notation of tableaux rules for multiple-valued logics. In Proc. International Symposium on Multiple-Valued Logic, Victoria, pages 238–245. IEEE Press, Los Alamitos, 1991.
R. Hähnle. A new translation from deduction into integer programming. In Jacques Calmet and John A. Campbell, editors, Proc. Int. Conf. on Artificial Intelligence and Symbolic Mathematical Computing AISMC-1, Karlsruhe, Germany, volume 737 of LNCS, pages 262–275. Springer-Verlag, 1992.
R. Hähnle. Automated Deduction in Multiple-Valued Logics, volume 10 of International Series of Monographs on Computer Science. Oxford University Press, 1994.
R. Hähnle. Many-valued logic and mixed integer programming. Annals of Mathematics and Artificial Intelligence, 12 (3,4): 231–264, December 1994.
R. Hähnle. Short conjunctive normal forms in finitely-valued logics. Journal of Logic and Computation, 4 (6): 905–927, 1994.
R. Hähnle. Exploiting data dependencies in many-valued logics. Journal of Applied Non-Classical Logics, 6 (1): 49–69, 1996.
R. Hähnle. Proof theory of many-valued logic—linear optimization—logic design: Connections and interactions. Soft Computing—A Fusion of Foundations, Methodologies and Applications, 1 (3): 107–119, September 1997.
R. Hähnle. Commodious axiomatization of quantifiers in multiple-valued logic. Studia Logica,61(1): 101–121,1998. Special Issue on Many-Valued Logics, their Proof Theory and Algebras.
R. Hähnle and G. Escalada-Imaz. Deduction in many-valued logics: a survey. Mathware & Soft Computing, IV (2): 69–97, 1997.
R. Hähnle and W. Kernig. Verification of switch level designs with many-valued logic. In Andrei Voronkov, editor, Proc. LPAR’93, St. Petersburg, Russia, volume 698 of LNCS, pages 158–169. Springer-Verlag, 1993.
R. Hähnle and P. H. Schmitt. The liberalized 5-rule in free variable semantic tableaux. Journal of Automated Reasoning, 13 (2): 211–222, October 1994.
M. Heisel, W. Reif, and W. Stephan. Formal software development in the KIV system. In L. McCartney, editor, Automating Software Design. AAAI Press, 1991.
A. Hoogewijs and T. M. Elnadi. KARNAK: an automated theorem prover for PPC. The CAGe Reports 10, University of Gent, Computer Algebra Group, 1994.
J. N. Hooker. A quantitative approach to logical inference. Decision Support Systems, 4: 45–69, 1988.
B. Hösli. Robuste Logik. PhD thesis, Eidgenössische Technische Hochschule Zürich, 1993.
R. G. Jeroslow. Logic-Based Decision Support. Mixed Integer Model Formulation. Elsevier, Amsterdam, 1988.
M. Kapetanovic and A. Krapez. A proof procedure for the first-order logic. Publications de l’Institut Mathematiqu, nouvelle série, 59 (45): 3–5, 1989.
M. Kerber and M. Kohlhase. A tableau calculus for partial functions. In Collegium Logicum. Annals of the Kurt-Gödel-Society, volume 2, pages 21–49. Springer-Verlag, Wien New York, 1996.
M. Kifer and V. S. Subrahmanian. Theory of generalized annotated logic programming and its applications. Jornal of Logic Programming, 12: 335–367, 1992.
V. G. Kirin. On the polynomial representation of operators in the n-valued propositional calculus (in Serbocroatian). Glasnik Mat.-Fiz. Astronom. Drustvo Mat. Fiz. Hravtske Ser. II, 18: 312, 1963. Reviewed in MR 29 (1965) p. 420.
V. G. Kirin. Gentzen’s method of the many-valued propositional calculi. Zeitschrift fir mathematische Logik und Grundlagen der Mathematik, 12: 317–332, 1966.
L. Löwenheim. Über die Auflösung von Gleichungen im logischen Gebietekalkül. Mathematische Annalen, 68: 169–207, 1910.
J. J. Lu. Logic programming with signs and annotations. Journal of Logic and Computation, 6 (6): 755–778, 1996.
J. J. Lu, N. V. Murray, and E. Rosenthal. Signed formulas and annotated logics. In Proc. 23rd International Symposium on Multiple-Valued Logics,pages 48–53 IEEE Press, Los Alamitos, 1993.
G. Malinowski. Many-Valued Logics, volume 25 of Oxford Logic Guides. Oxford University Press, 1993.
P. Miglioli, U. Moscato, and M. Omaghi. An improved refutation system for intuitionistic predicate logic. Journal of Automated Reasoning,13(3): 361–374,1994.
P. Miglioli, U. Moscato, and M. Omaghi. Refutation systems for propositional modal logics. In P. Baumgartner, R. Hähnle, and J. Posegga, editors, Proc. 4th Workshop on Deduction with Tableaux and Related Methods, St. Goar, Germany,volume 918 of LNCS,pages 95–105. Springer-Verlag, 1995.
A. Mostowski. On a generalization of quantifiers. Fundamenta Mathematicæ, XLIV: 12–36, 1957.
D. Mundici. Satisfiability in many-valued sentential logic is NP-complete. Theoretical Computer Science, 52: 145–153, 1987.
D. Mundici. A constructive proof of McNaughton’s Theorem in infinite-valued logic. Journal of Symbolic Logic, 59 (2): 596–602, June 1994.
N. V. Murray. Completely non-clausal theorem proving. Artificial Intelligence, 18: 6785, 1982.
N. V. Murray and E. Rosenthal. Improving tableau deductions in multiple-valued logics. In Proceedings 21st International Symposium on Multiple-Valued Logic, Victoria, pages 230–237. IEEE Press, Los Alamitos, May 1991.
N. V. Murray and E. Rosenthal. Resolution and path-dissolution in multiple-valued logics. In Proceedings International Symposium on Methodologies for Intelligent Systems, Charlotte, LNAI. Springer-Verlag, 1991.
N. V. Murray and E. Rosenthal. Adapting classical inference techniques to multiple-valued logics using signed formulas. Fundamenta Informaticae, 21 (3): 237–253, 1994.
M. Areski Nait Abdallah. The Logic of Partial Information. Monographs in Theoretical Computer Science — An EATCS Series. Springer-Verlag, 1995.
P. O’Heam and Z. Stachniak. A resolution framework for finitely-valued first-order logics. Journal of Symbolic Computing, 13: 235–254, 1992.
E. Orlowska. Mechanical proof procedure for the n-valued propositional calculus. Bull. de L’Acad. Pol. des Sci., Série des sci. math., astr. et phys., XV (8): 537–541, 1967.
E. Orlowska. Mechanical proof methods for Post Logics. Logique et Analyse, 28 (110): 173–192, 1985.
G. Panti. Multi-valued logics. In D. Gillies and P. Smets, editors, Handbook of Defensible Reasoning and Uncertainty Management Systems,volume 1, chapter 2. Kluwer, to appear.
M. A. Perkowski. The generalized orthonormal expansion of functions with multiple-valued inputs and some of its application. In Proc. 22nd International Symposium on Multiple-Valued Logic, pages 442–450. IEEE Press, Los Alamitos, May 1992.
D. A. Plaisted and S. Greenbaum. A structure-preserving clause form translation. Journal of Symbolic Computation, 2: 293–304, 1986.
J. Posegga. Deduktion mit Shannongraphen fir Prädikatenlogik erster Stufe. PhD thesis, University of Karlsruhe, 1993. diski 51, infix Verlag.
N. Rescher. Many-Valued Logic. McGraw-Hill, New York, 1969.
J. B. Rosser and A. R. Turquette. Many-Valued Logics. North-Holland, Amsterdam, 1952.
G. Rousseau. Sequents in many valued logic I. Fundamenta Mathematicte, LX: 2333, 1967.
G. Rousseau. Sequents in many valued logic II. Fundamenta Mathematicte, LXVII: 125–131, 1970.
R. Rudell and A. Sangiovanni-Vincentelli. Multiple-valued minimization for PLA optimization. IEEE Transactions on Computer-Aided Design, 6 (5): 727–750, September 1987.
Z. Saloni. Gentzen rules for m-valued logic. Bull. de L’Acad. Pol. des Sci., Série des sci. math., astr. et phys., XX: 819–825, 1972.
G. Salzer. MUltlog: an expert system for multiple-valued logics. In Collegium Logicum. Annals of the Kurt-Gödel-Society, volume 2. Springer-Verlag, Wien New York, 1996.
G. Salzer. Optimal axiomatizations for multiple-valued operators and quantifiers based on semilattices. In Michael McRobbie and John Slaney, editors, Proc. 13th Conference on Automated Deduction, New Brunswick/NJ, USA, volume 1104 of LNCS, pages 688–702. Springer-Verlag, 1996.
T. Sasao. Multiple-valued decomposition of generalized Boolean functions and the complexity of programmable logic arrays. IEEE Transactions on Computers, C-30: 635–643, September 1981.
T. Sasao. Input variable assignment and output phase optimization of PLA’s. IEEE Transactions on Computers, C-33(10): 879–894, October 1984.
T. Sasao. Optimization of multi-valued AND-XOR expressions using multiple-place decision diagrams. In Proc. 22nd International Symposium on Multiple-Valued Logic, pages 451458. IEEE Press, Los Alamitos, May 1992.
T. Sasao. Logic synthesis with EXOR gates. In Tsutomu Sasao, editor, Logic Synthesis and Optimization, chapter 12, pages 259–286. Kluwer, Norwell/MA, USA, 1993.
T. Sasao. Ternary decision diagrams and their applications. In Tsutomu Sasao and Masahiro Fujita, editors, Representations of Discrete Functions, chapter 12, pages 269–292. Kluwer, Norwell/MA, USA, 1996.
A. Schrijver. Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, 1986.
K. Schröter. Methoden zur Axiomatisierung beliebiger Aussagen- und Prädikatenkalkille. Zeitschrift für math. Logik und Grundlagen der Mathematik, 1: 241–251, 1955.
C. E. Shannon. A symbolic analysis of relay and switching circuits. AIEE Transactions, 67: 713–723, 1938.
R. M. Smullyan. First-Order Logic. Dover Publications, New York, second corrected edition, 1995. First published 1968 by Springer-Verlag.
A. Srinivasan, T. Kam, S. Malik, and R. E. Brayton. Algorithms for discrete function manipulation. In Proc. IEEE International Conference on CAD, Santa Clara/CA, USA,pages 92–95. IEEE Press, Los Alamitos, November 1990.
Z. Stachniak. The resolution rule: An algebraic perspective. In Proc. of Algebraic Logic and Universal Algebra in Computer Science Conf, pages 227–242. Springer LNCS 425, Heidelberg, 1988.
Z. Stachniak and P. O’Hearn. Resolution in the domain of strongly finite logics. Fundamenta Informaticae, XIII: 333–351, 1990.
U. Straccia. A sequent calculus for reasoning in four-valued description logics. In Didier Galmiche, editor, Proc. International Conference on Automated Reasoning with Analytic Tableaux and Related Methods, Pont-à-Mousson, France, volume 1227 of LNCS, pages 343–357. Springer-Verlag, 1997.
W. Suchot. La méthode de Smullyan de construire le calcul n-valent de Lukasiewicz avec implication et négation. Reports on Mathematical Logic, Universities of Cracow and Katowice, 2: 37–42, 1974.
S. J. Sunna. An algorithm for axiomatizing every finite logic. In David C. Rine, editor, Computer Science and Multiple-Valued Logics, pages 143–149. North-Holland, Amsterdam, second edition, 1984. Selected Papers from the International Symposium on Multiple-Valued Logics 1974.
M. Takahashi. Many-valued logics of extended Gentzen style I. Science Reports of the Tokyo Kyoiku Daigaku, Section A, 9(231): 95–116, 1967. MR 37.39, Zbl 172.8.
M. Takahashi. Many-valued logics of extended Gentzen style II. Journal of Symbolic Logic, 35 (4): 493–528, December 1970.
A. Thayse, M. Davio, and J.-P. Deschamps. Optimization of multiple-valued decision diagrams. In Proc. International Symposium on Multiple-Valued Logics, ISMVL’79, Rosemont/IL, USA,pages 171–177. IEEE Press, Los Alamitos, 1979.
A. Urquhart. Many-valued logic. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, Vol. III: Alternatives in Classical Logic, chapter 2, pages 71–116. Reidel, Dordrecht, 1986.
Vienna Group for Multiple Valued Logics. MUltiog 1.0: Towards an expert system for many-valued logics. In Michael McRobbie and John Slaney, editors, Proc. 13th Conference on Automated Deduction, New Brunswick/NJ, USA, volume 1104 of LNCS, pages 226–230. Springer-Verlag, 1996.
N. Zabel. Nouvelles Techniques de Déduction Automatique en Logiques Polyvalentes Finies et Infinies du Premier Ordre. PhD thesis, Institut National Polytechnique de Grenoble, April 1993.
R. Zach. Proof theory of finite-valued logics. Master’s thesis, Institut für Algebra und Diskrete Mathematik, TU Wien, September 1993. Available as Technical Report TUW-E185. 2Z. 1–93.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer Science+Business Media Dordrecht
About this chapter
Cite this chapter
Hähnle, R. (1999). Tableaux for Many-Valued Logics. In: D’Agostino, M., Gabbay, D.M., Hähnle, R., Posegga, J. (eds) Handbook of Tableau Methods. Springer, Dordrecht. https://doi.org/10.1007/978-94-017-1754-0_9
Download citation
DOI: https://doi.org/10.1007/978-94-017-1754-0_9
Publisher Name: Springer, Dordrecht
Print ISBN: 978-90-481-5184-4
Online ISBN: 978-94-017-1754-0
eBook Packages: Springer Book Archive