The book gives all interested in computer science, a deep review of relevant aspects of logic. In its scope are classical and non-classical logics. The content will be valid as well for those interested in linguistic, philosophy and many other areas of research both in humane and technical branches of science as logic permeates all genuine realms of science. The book contains a substantial part of classical results in logic like those by Gödel, Tarski, Church and Rosser as well as later developments like many-valued logics, logics for knowledge engineering, first-order logics plus inductive definitions.
The exposition is rigorous yet without unnecessary abstractionism, so it should be accessible to readers from many disciplines of science. Each chapter contains a problem section, and problems are borrowed from research publications which allows for passing additional information, and it allows readers to test their skills. Extensive bibliography of 270 positions directs readers to research works of importance.
Author(s): Lech T. Polkowski
Series: Intelligent Systems Reference Library, 245
Edition: 1
Publisher: Springer
Year: 2023
Language: English
Commentary: Publisher PDF | Published: 04 October 2023
Pages: xxxiii, 461
City: Cham
Tags: Data Sciences; Logics; Computational Intelligence; Propositional Modal Logic; Epistemic; Default Logic; Dynamic Logic; Computational Intelligence; Data Engineering; Propositional Logic; Temporal Logics; Artificial Intelligence; Logic; First-Order Logic; Many-Valued Logics; Approximate Reasoning
Foreword
Preface
Contents
List of Figures
List of Tables
1 Introduction: Prerequisites
1.1 Set Theory Recapitulated
1.1.1 ZFC Set Theory. Basic Constructs
1.1.2 Equipollence and well-Ordered Sets. Cardinal and Ordinal Numbers
1.1.3 Graph Structures
1.2 Rewriting Systems
1.3 Computability
1.4 Arithmetization of Turing Machines
1.5 Recursively Enumerable Sets
1.6 Undecidability
1.7 Incompleteness. Non-provability of Truth
1.8 Complexity
1.9 Algebraic Structures
1.10 Topological Structures
References
2 Sentential Logic (SL)
2.1 A Bit of History
2.2 Syntax of Sentential Logic
2.3 Semantics of Sentential Logic
2.4 Normal Forms
2.5 Sentential Logic as an Axiomatic Deductive System
2.6 Natural Deduction
2.7 Natural Deduction: Decomposition Diagrams
2.8 Tableaux
2.9 Meta-Theory of Sentential Logic. Part I
2.10 Meta-Theory of Sentential Logic. Part II
2.11 Resolution, Logical Consequence
2.12 Horn Clauses. Forward and Backward Chaining
2.13 Satisfiability, Validity and Complexity in Sentential Logic. Remarks …
2.14 Physical Realization of SL. Logic Circuits, Threshold Logic
2.15 Problems
References
3 Rudiments of First-Order Logic (FO)
3.1 Introduction to Syntax of FO
3.2 Introduction to Semantics of FO
3.3 Natural Deduction: Sequents
3.4 Natural Deduction: Diagrams of Formulae
3.5 Natural Deduction: Tableaux
3.6 Meta-Theory of Predicate Logic. Part I
3.6.1 Tableau-Completeness of Predicate Logic
3.7 Analytic Tableaux Versus Sequents
3.8 Normal Forms
3.9 Resolution in Predicate Calculus
3.10 Horn Clauses and SLD-Resolution
3.11 Meta-Theory of FO. Part II
3.11.1 Undecidability of Satisfiability and Validity Decision Problems
3.12 Complexity Issues for Predicate Logic
3.13 Monadic Predicate Logic
3.14 The Theory of Herbrand
3.15 The Gödel Completeness Theorem. The Henkin Proof
3.16 The Tarski Theorem on Inexpressibility of Truth
3.17 Gödel Incompleteness Theorems
3.18 The Rosser Incompleteness Theorem. The Rosser Sentence
3.19 Finite FO Structures
3.20 Ehrenfeucht Games
3.21 The General form of Deduction Theorem for FO
3.22 Craig's Interpolation Theorem. Beth's Definability Theorem
3.23 Problems
References
4 Modal and Intuitionistic Logics
4.1 Sentential Modal Logic (SML)
4.2 Semantics of the Modal System K
4.3 Natural Deduction: Analytic Tableaux for Modal Logics
4.4 Meta-Theory of Modal Logics: Part I: K,T,S4
4.5 Natural Deduction: Modal Sequent Calculus
4.6 Meta-Theory of Modal Logics. Part II
4.7 Model Existence Theorem and Strong Completeness
4.8 Small Model Property, Decidability
4.9 Satisfiability, Complexity
4.10 Quantified Modal Logics (QML)
4.11 Natural Deduction: Tableaux for Quantified Modal Logics
4.12 Sentential Intuitionistic Logic (SIL)
4.13 Natural Deduction: Tableaux for SIL
4.14 Consistency of Intuitionistic Sentential Logic
4.15 First-Order Intuitionistic Logic (FOIL)
4.16 Natural Deduction: FOIL-Tableaux
4.17 Problems
References
5 Temporal Logics for Linear and Branching Time and Model Checking
5.1 Temporal Logic of Prior
5.2 Linear Temporal Logic (LTL)
5.3 Computational Tree Logic (CTL)
5.4 Full Computational Tree Logic (CTL*)
5.5 Meta-theory of Temporal Logics
5.6 Linear Time Logic with PAST (LTL+PAST)
5.7 Properties of Systems, Model Checking by Means of Automata
5.8 Natural Deduction: Tableaux for LTL
5.9 Tableaux Construction for Linear Temporal Logic
5.10 Tableaux for Computational Tree Logic CTL
5.11 Non-deterministic Automata on Infinite Words
5.12 Decision Problems for Automata
5.13 Alternation. Alternating Automata on Infinite Words
5.14 From LTL to Büchi Automata on Infinite Words
5.15 LTL Model Checking
5.16 Model Checking for Branching-time Logics
5.17 Symbolic Model Checking: OBDD (Ordered Binary Decision Diagram)
5.18 Problems
References
6 Finitely and Infinitely Valued Logics
6.1 3-Valued Logic of Łukasiewicz (3L). Introduction
6.2 T-Norms, T-Co-norms
6.3 Basic Logic (BL)
6.4 Meta-Theory of BL
6.5 Meta-Theory of 3L
6.6 Some Other Proposals for 3,4-Valued Logics
6.7 The n-Valued Logic nL: The Rosser-Tourquette Theory
6.8 The Post Logics
6.9 Infinite-Valued Logics
6.10 Infinite-Valued Logic [0,1]L of Łukasiewicz
6.11 Wajsberg Algebras
6.12 MV-Algebras
6.13 Ideals in MV-Algebras
6.14 The Chang Representation Theorem
6.15 The Chang Completeness Theorem
6.16 Wajsberg Algebras, MV-Algebras and the Łukasiewicz [0,1]L Logic
6.17 The Completeness Theorem for Infinite-Valued Sentential Logic [0,1]L
6.18 Remarks on Goguen and Gödel Infinite-Valued Logics
6.19 Complexity of Satisfiability Decision Problem for Infinite-Valued Logics
6.20 Problems
References
7 Logics for Programs and Knowledge
7.1 Sentential Dynamic Logic (SDL)
7.2 Epistemic Logics
7.3 Mereology Based Logic for Granular Computing and Fuzzy Reasoning
7.4 Rough Mereology. Rough Inclusions
7.5 Knowledge as an Ability to Classify. Information/Decision Systems
7.6 The Logic of Functional Dependence (FD-Logic)
7.7 Boolean Reasoning in Data Analysis
7.8 Information Logic (IL)
7.9 Pavelka's Fuzzy Sentential Logic
7.10 Problems
References
8 Beyond FO Within SO
8.1 Introduction: Expressive Power of FO. Recapitulation
8.2 Syntax and Semantics of Second-Order Logic (SO)
8.3 Graph Structures in MSO
8.4 Strings in FO and MSO
8.5 Theorems of Trakhtenbrot and Fagin
8.6 FO+Inductive Definitions. Fixed Point Logics
8.7 Logics with Counting (FO+Count)
8.8 FO+Transitive Closure (FO+TC)
8.9 Logics with a Finite Number of Variables
8.10 Definability Versus Locality
8.11 0-1 Laws
8.12 BIT Relational Symbol. Random Graph
8.13 Games on Graphs and Transition Systems
8.14 Modal µ-Calculus (Lµ)
8.15 µ-Calculus Model Checking
8.16 DATALOG
8.17 Problems
References
Author Index
Index
