Fragments of first-order logic /

A sentence of first-order logic is satisfiable if it is true in some structure, and finitely satisfiable if it is true in some finite structure. The question arises as to whether there exists an algorithm for determining whether a given formula of first-order logic is satisfiable, or indeed finitely...

Ausführliche Beschreibung

Gespeichert in:
1. Verfasser:
Pratt-Hartmann, Ian
Format:
Elektronisch E-Book
Sprache:
Englisch
Veröffentlicht:
Oxford : Oxford University Press, 2023.
Ausgabe:
1st ed.
Zusammenfassung:
A sentence of first-order logic is satisfiable if it is true in some structure, and finitely satisfiable if it is true in some finite structure. The question arises as to whether there exists an algorithm for determining whether a given formula of first-order logic is satisfiable, or indeed finitely satisfiable. This question was answered negatively in 1936 by Church and Turing (for satisfiability) and in 1950 by Trakhtenbrot (for finite satisfiability). In contrast, the satisfiability and finite satisfiability problems are algorithmically solvable for restricted subsets of first-order logic, a fact which is today of considerable interest in Computer Science. This book provides an up-to-date survey of the principal axes of research, charting the limits of decision in first-order logic and exploring the trade-off between expressive power and complexity of reasoning.
Umfang:
1 online resource (673 pages)
Anmerkungen:
Also issued in print: 2023.
Zielpublikum:
Specialized.
Bibliografie:
Includes bibliographical references and index.
ISBN:
0-19-196006-3
0-19-269389-1
Schlagworte:
First-order logic.
Mathematics.
Bezugswerke:
Links: