R-Calculus, II: Many-Valued Logics

ISBN-13: 9789811692963 / Angielski / Miękka / 2023

Wei Li;Yuefei Sui

Opis

This second volume of the book series shows R-calculus is a combination of one monotonic tableau proof system and one non-monotonic one. The R-calculus is a Gentzen-type deduction system which is non-monotonic, and is a concrete belief revision operator which is proved to satisfy the AGM postulates and the DP postulates. It discusses the algebraical and logical properties of tableau proof systems and R-calculi in many-valued logics. This book offers a rich blend of theory and practice. It is suitable for students, researchers and practitioners in the field of logic. Also it is very useful for all those who are interested in data, digitization and correctness and consistency of information, in modal logics, non monotonic logics, decidable/undecidable logics, logic programming, description logics, default logics and semantic inheritance networks.  

Spis treści

1 Introduction 11

1.1 Belief revision . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.2 R-calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.3 Contents in the first-volume . . . . . . . . . . . . . . . . . . . 14

1.4 Contents in this volume . . . . . . . . . . . . . . . . . . . . . 17

1.5 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2 R-Calculus For Propositional Logic 24

2.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.2 Monotonic tableau proof systems . . . . . . . . . . . . . . . . 26

2.2.1 Tableau proof system Tf . . . . . . . . . . . . . . . . 26

2.2.2 Tableau proof system Tt . . . . . . . . . . . . . . . . 29

2.3 Nonmonotonic tableau proof systems . . . . . . . . . . . . . . 31

2.3.1 Tableau proof system St . . . . . . . . . . . . . . . . . 32

2.3.2 Tableau proof system Sf . . . . . . . . . . . . . . . . . 34

2.4 R-calculi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.4.1 R-calculus Rt . . . . . . . . . . . . . . . . . . . . . . . 36

2.4.2 R-calculus Rf . . . . . . . . . . . . . . . . . . . . . . . 40

2.5 Projecting R-calculi to tableau proof systems . . . . . . . . . 41

2.6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3 R-Calculus For L3-Valued Propositional Logic 45

3.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . 46

3.2 Monotonic tableau proof systems . . . . . . . . . . . . . . . . 49

3.2.1 Tableau proof system Tt . . . . . . . . . . . . . . . . 49

3.2.2 Tableau proof system Tm . . . . . . . . . . . . . . . . 50

3.2.3 Tableau proof system Tf . . . . . . . . . . . . . . . . 51

3.3 Nonmonotonic tableau proof systems . . . . . . . . . . . . . . 52

3.3.1 Tableau proof system St . . . . . . . . . . . . . . . . . 54

3.3.2 Tableau proof system Sm  . . . . . . . . . . . . . . . . . 55

3.3.3 Tableau proof system Sf  . . . . . . . . . . . . . . . . . 55

3.4 R-calculi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.4.1 R-calculus Rt  . . . . . . . . . . . . . . . . . . . . . . . 57

3.4.2 R-calculus Rm  . . . . . . . . . . . . . . . . . . . . . . . 60

3.4.3 R-calculus Rf  . . . . . . . . . . . . . . . . . . . . . . . 63

3.5 Satisfiability and unsatisfiability . . . . . . . . . . . . . . . . 65

3.5.1 t-satisfiability and t-unsatisfiability . . . . . . . . . . 65

3.5.2 m-satisfiability and m-unsatisfiability . . . . . . . . . . 67

3.5.3 f-satisfiability and f-unsatisfiability . . . . . . . . . . 68

3.6 Projecting R-calculi to tableau proof systems . . . . . . . . . 70

3.7 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

4 R-Calculus For L3-Valued PL,II 75

4.1 Monotonic tableau proof systems . . . . . . . . . . . . . . . . 75

4.1.1 Tableau proof system Tt . . . . . . . . . . . . . . . . 76 

4.1.2 Tableau proof system Tm  . . . . . . . . . . . . . . . . 77

4.1.3 Tableau proof system Tf . . . . . . . . . . . . . . . . 78

4.2 Nonmonotonic tableau proof systems . . . . . . . . . . . . . . 79

4.2.1 Tableau proof system St . . . . . . . . . . . . . . . . . 79

4.2.2 Tableau proof system Sm . . . . . . . . . . . . . . . . . 80

4.2.3 Tableau proof system Sf . . . . . . . . . . . . . . . . . 81

4.3 R-calculi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

4.3.1 R-calculus Rt . . . . . . . . . . . . . . . . . . . . . . . 82

4.3.2 R-calculus Rm . . . . . . . . . . . . . . . . . . . . . . . 85

4.3.3 R-calculus Rf . . . . . . . . . . . . . . . . . . . . . . . 87

4.4 Validity and invalidity . . . . . . . . . . . . . . . . . . . . . . 90

4.4.1 t-invalidity and t-validity . . . . . . . . . . . . . . . . 90

4.4.2 m-invalidity and m-validity . . . . . . . . . . . . . . . . 92

4.4.3 f-invalidity and f-validity . . . . . . . . . . . . . . . . 94

4.5 Projecting R-calculi to tableau proof systems . . . . . . . . . 96

5 R-Calculus For B22-Valued PL 98

5.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . 100

5.2 Monotonic tableau proof systems . . . . . . . . . . . . . . . . 101

5.2.1 Tableau proof system Tt . . . . . . . . . . . . . . . . 103

5.2.2 Tableau proof system Ttop . . . . . . . . . . . . . . . . 104

5.2.3 Tableau proof system T⊥. . . . . . . . . . . . . . . . 105

5.2.4 Tableau proof system Tf . . . . . . . . . . . . . . . . 107

5.3 Nonmonotonic tableau proof systems . . . . . . . . . . . . . . 108

5.3.1 Tableau proof system St  . . . . . . . . . . . . . . . . . 110

5.3.2 Tableau proof system Stop . . . . . . . . . . . . . . . . 112

5.3.3 Tableau proof system S⊥. . . . . . . . . . . . . . . . 113

5.3.4 Tableau proof system Sf . . . . . . . . . . . . . . . . . 114

5.4 R-calculi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

5.4.1 R-calculus Rt . . . . . . . . . . . . . . . . . . . . . . . 117

5.4.2 R-calculus Rtop  . . . . . . . . . . . . . . . . . . . . . . 121

5.4.3 R-calculus R⊥ . . . . . . . . . . . . . . . . . . . . . . 125

5.4.4 R-calculus Rf . . . . . . . . . . . . . . . . . . . . . . . 128

5.5 Projecting R-calculi to tableau proof systems . . . . . . . . . 132

5.6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

6 R-Calculus For B22-Valued PL,II 138

6.1 Monotonic tableau proof systems . . . . . . . . . . . . . . . . 140

6.1.1 Tableau proof system Tt top . . . . . . . . . . . . . . . . 142   

6.1.2 Tableau proof system Tt⊥ . . . . . . . . . . . . . . . . 143  

6.2 Tableau proof systems . . . . . . . . . . . . . . . . . . . . . . 145

6.2.1 Tableau proof system Tt top . . . . . . . . . . . . . . . . 146

6.2.2 Tableau proof system Tt⊥ . . . . . . . . . . . . . . . 148

6.3 Nonmonotonic tableau proof systems . . . . . . . . . . . . . . 149

6.3.1 Tableau proof system St top . . . . . . . . . . . . . . . . 150

6.3.2 Tableau proof system St⊥. . . . . . . . . . . . . . . . 151

6.3.3 Tableau proof system St top . . . . . . . . . . . . . . . . 152

6.3.4 Tableau proof system St⊥. . . . . . . . . . . . . . . . 153

6.4 R-calculi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

6.4.1 R-calculus Rt top . . . . . . . . . . . . . . . . . . . . . . 155

6.4.2 R-calculus Rt⊥. . . . . . . . . . . . . . . . . . . . . . 157

6.4.3 R-calculus Rf top . . . . . . . . . . . . . . . . . . . . . . 159

6.4.4 R-calculus Rf.⊥. . . . . . . . . . . . . . . . . . . . . 161

6.5 Projecting R-calculi to tableau proof systems . . . . . . . . . 163

6.6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

7 Complementary R-Calculus For PL 168

7.1 Co-R-calculi in propositional logic . . . . . . . . . . . . . . . 169

7.1.1 Co-R-calculus Ut . . . . . . . . . . . . . . . . . . . . . 169

7.1.2 Co-R-calculus Uf . . . . . . . . . . . . . . . . . . . . . 171

7.2 Co-R-calculi in L3-valued PL . . . . . . . . . . . . . . . . . . 173

7.2.1 Co-R-calculus Ut . . . . . . . . . . . . . . . . . . . . . 173

7.2.2 Co-R-calculus Um . . . . . . . . . . . . . . . . . . . . . 176

7.2.3 Co-R-calculus Uf . . . . . . . . . . . . . . . . . . . . . 179

7.3 Co-R-calculi in B22-valued propositional logic . . . . . . . . . 181

7.3.1 Co-R-calculus Ut . . . . . . . . . . . . . . . . . . . . . 182

7.4 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187

8 Multisequents and Hypersequents 188

8.1 Tableau proof systems . . . . . . . . . . . . . . . . . . . . . . 189

8.1.1 Tableau-typed proof system Tt . . . . . . . . . . . . . 189

8.1.2 Tableau proof system Tt . . . . . . . . . . . . . . . . 190

8.2 Sequents in L3-valued propositional logic . . . . . . . . . . . . 192

8.2.1 Gentzen deduction system for Δ=>∑. . . . . . . . . 193

8.2.2 Gentzen deduction system for Θ=> Ξ. . . . . . . . . 195

8.2.3 Gentzen deduction system for Γ=> Π. . . . . . . . . . 196

8.3 Multisequents in L3-valued PL . . . . . . . . . . . . . . . . . 197

8.3.1 Multisequents . . . . . . . . . . . . . . . . . . . . . . . 199   

8.3.2 Co-multisequents . . . . . . . . . . . . . . . . . . . . . 202

8.4 Hypersequents in L3-valued PL . . . . . . . . . . . . . . . . . 206

8.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214

9 Product of Two R-Calculi 216

9.1 Tableau proof systems in modalized PL . . . . . . . . . . . . 217

9.1.1 Monotonic tableau proof systems . . . . . . . . . . . . 217

9.1.2 Nonmonotonic tableau proof systems . . . . . . . . . . 218

9.2 Product of B2-valued PLs . . . . . . . . . . . . . . . . . . . . 219

9.2.1 Tableau proof system Pt4 . . . . . . . . . . . . . . . . 222

9.2.2 Tableau proof system P4t . . . . . . . . . . . . . . . . 224

9.2.3 Tableau proof system Qt  . . . . . . . . . . . . . . . . 228

9.3 Product of two R-calculi . . . . . . . . . . . . . . . . . . . . . 231

9.3.1 R-calculi Rt2 and Rf2 . . . . . . . . . . . . . . . . . . . 231

9.3.2 R-calculus Ut4 . . . . . . . . . . . . . . . . . . . . . . . 233

9.4 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238

10 Sum of Two R-Calculi 244

10.1 The sum with one common element . . . . . . . . . . . . . . 245

10.1.1 B2[f; m] ⊕ B2[m; t] . . . . . . . . . . . . . . . . . . . . 245

10.1.2 Operators on tableau proof systems . . . . . . . . . . 246  

10.1.3 Sum of tableau proof systems . . . . . . . . . . . . . . 248   

10.1.4 R-calculi . . . . . . . . . . . . . . . . . . . . . . . . . . 251 

10.1.5 R-calculi in PL . . . . . . . . . . . . . . . . . . . . . . 251 

10.1.6 R-calculi in L3-valued PL . . . . . . . . . . . . . . . . 253 

10.2 The sum without common elements . . . . . . . . . . . . . . 256

10.2.1 L4-valued PL . . . . . . . . . . . . . . . . . . . . . . . 256

10.2.2 Equivalences . . . . . . . . . . . . . . . . . . . . . . . 257

10.2.3 Tableau proof system Tt4 . . . . . . . . . . . . . . . . 259

10.2.4 Tableau proof system Ttop4 . . . . . . . . . . . . . . . . 260

10.2.5 Tableau proof system T⊥4. . . . . . . . . . . . . . . . 262

10.2.6 Tableau proof system Tf4 . . . . . . . . . . . . . . . . 263

10.2.7 Sum of tableau proof systems: Tt4=~2 (Tt2) ⊕ Tt2. . 264

10.2.8 Sum of tableau proof systems: T4t= T2⊥⊕ T2t. . . . . 266

10.2.9 Sum of tableau proof systems: St4= S⊥2⊕ St2 . . . . . 268

10.2.10 Sum of R-calculi: Rt4= R⊥2⊕ Rt2. . . . . . . . . . . . 269

10.3 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273

O autorze

Wei Li, is a Professor in the School of Computer Science and Engineering, Beihang University, Beijing, China and is a member of the Chinese Academy of Sciences. Prof. Li is mostly engaged in the applied research of Computer Software and Theory, and the Internet, including programming languages, software development, artificial intelligence, and integrated circuit design.

Yuefei Sui, is a Professor in the Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China. His main interests include knowledge representation, applied logic and the theory of computability.