Fragments of First-Order Logic

— —

Ian Pratt-Hartmann (Senior Lecturer, University of Manchester Professor of Mathematical Sciences, University of Opole)

Fragments of First-Order Logic

Ian Pratt-Hartmann (Senior Lecturer, University of Manchester Professor of Mathematical Sciences, University of Opole)

$283

Hardback

Not in-store but you can order this
How long will it take?

Availability Information

We source books from suppliers in Australia and overseas. For books we don't currently have in stock, the time it takes to get them from our suppliers can vary widely - from a few days to a few months - so we check each book with each supplier to determine the expected time it will take to be supplied to us.

We then advise you accordingly. If the time taken to get any book is too long for you, you can let us know and we will cancel or adjust your order, and refund as required.

To find out the anticipated arrival time for specific items prior to ordering, please contact us by phone or email:

Phone +61 2 9264 3111, or 1800 4 BOOKS (1800 4 26657) if outside Sydney:
option 1 Abbey's Bookshop (Crime, History, Science, Kids & more) • info@abbeys.com.au
option 2 Language Book Centre (ESL & Foreign Languages) • language@abbeys.com.au
option 3 Galaxy Bookshop (Sci-fi, Fantasy, Romance, Graphic Novels) • sf@galaxybooks.com.au

QTY:

English

Oxford University Press
04 April 2023

Mathematical foundations; Mathematical logic; Mathematical modelling

Series: Oxford Logic Guides

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---or, as we say, fragments---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. Divided into three parts, the book considers for which fragments of first-order logic there is an effective method for determining satisfiability or finite satisfiability.

Furthermore, if these problems are decidable for some fragment, what is their computational complexity? Part I focusses on fragments defined by restricting the set of available formulas. Topics covered include the Aristotelian syllogistic and its relatives, the two-variable fragment, the guarded fragment, the quantifier-prefix fragments and the fluted fragment. Part II investigates logics with counting quantifiers. Starting with De Morgan's numerical generalization of the Aristotelian syllogistic, we proceed to the two-variable fragment with counting quantifiers and its guarded subfragment, explaining the applications of the latter to the problem of query answering in structured data. Part III concerns logics characterized by semantic constraints, limiting the available interpretations of certain predicates. Taking propositional modal logic and graded modal logic as our cue, we return to the satisfiability problem for two-variable first-order logic and its relatives, but this time with certain distinguished binary predicates constrained to be interpreted as equivalence relations or transitive relations. The work finishes, slightly breaching the bounds of first-order logic proper, with a chapter on logics interpreted over trees.

By: Ian Pratt-Hartmann (Senior Lecturer University of Manchester Professor of Mathematical Sciences University of Opole)
Imprint: Oxford University Press
Country of Publication: United Kingdom
Dimensions: Height: 240mm, Width: 160mm, Spine: 36mm
Weight: 1.240kg
ISBN: 9780192867964
ISBN 10: 0192867962
Series: Oxford Logic Guides
Pages: 672
Publication Date: 04 April 2023
Audience: Professional and scholarly , Undergraduate
Format: Hardback
Publisher's Status: Active

Preface Acknowledgements 1: Introduction Part I: Syntactic Restrictions 2: Roots 3: Variables 4: Guards 5: Prefixes 6: Fluting Part II: Counting Quantifiers 7: Counting with one variable 8: Counting with two variables 9: Guarded counting 10: Omitting graphs Part III: Semantic Constraints 11: Modalities 12: Equivalence 13: Equivalence and counting 14: Transitivity 15: Trees

Ian Pratt-Hartmann studied mathematics and philosophy at Brasenose College, Oxford, and philosophy at Princeton and Stanford Universities, gaining his PhD from Princeton in 1987. He is currently Senior Lecturer in the Department of Computer Science at the University of Manchester as well as Professor of Mathematical Sciences in the Institute of Computer Science at the University of Opole, and recently held an appointment as Visiting Professor at the Department of Mathematics, Computer Science and Mechanics at the University of Warsaw.