Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Introduction Read chapter Read first chapter

2012 | OriginalPaper | Chapter

12. First-Order Logic: Undecidability and Model Theory *

Author : Prof. Mordechai Ben-Ari

Published in: Mathematical Logic for Computer Science

Publisher: Springer London

Log in

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

search-config
loading …

Abstract

The chapter surveys several important theoretical results in first-order logic. In Sect. 12.1 we prove that validity in first-order logic is undecidable, a result first proved by Alonzo Church. Validity is decidable for several classes of formulas defined by syntactic restrictions on their form (Sect. 12.2). Next, we introduce model theory (Sect. 12.3): the fact that a semantic tableau has a countable number of nodes leads to some interesting results. Finally, Sect. 12.4 contains an overview of Gödel’s surprising incompleteness result.

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 "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

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
previous chapter First-Order Logic: Logic Programming
next chapter Temporal Logic: Formulas, Models, Tableaux
Literature
B. Dreben and W.D. Goldfarb. The Decision Problem: Solvable Classes of Quantificational Formulas. Addison-Wesley, Reading, MA, 1979. MATH
J.E. Hopcroft, R. Motwani, and J.D. Ullman. Introduction to Automata Theory, Languages and Computation (Third Edition). Addison-Wesley, 2006.
H.R. Lewis. Unsolvable Classes of Quantificational Formulas. Addison-Wesley, Reading, MA, 1979. MATH
Z. Manna. Mathematical Theory of Computation. McGraw-Hill, New York, NY, 1974. Reprinted by Dover, 2003. MATH
E. Mendelson. Introduction to Mathematical Logic (Fifth Edition). Chapman & Hall/CRC, 2009. MATH
M.L. Minsky. Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs, NJ, 1967. MATH
R.M. Smullyan. What Is the Name of This Book?—The Riddle of Dracula and Other Logical Puzzles. Prentice-Hall, 1978. MATH
Metadata
Title
First-Order Logic: Undecidability and Model Theory *
Author
Prof. Mordechai Ben-Ari
Copyright Year
2012
Publisher
Springer London
Book
Mathematical Logic for Computer Science

Print ISBN: 978-1-4471-4128-0

Electronic ISBN: 978-1-4471-4129-7

Copyright Year: 2012

DOI
https://doi.org/10.1007/978-1-4471-4129-7_12

Premium Partner

    Image Credits