Logical Foundations for Rule-Based Systems

Cover......Page 1
Studies in Computational Intelligence, Volume 11......Page 3
Logical Foundations
for Rule-Based Systems......Page 4
ISBN-13 9783540291176......Page 5
Preface......Page 6
Acknowledgment......Page 12
Contents......Page 15
Part I Logical Foundations of Rule-Based Systems......Page 21
1.1 Alphabet of Propositional Calculus......Page 23
1.2 Syntax of Propositional Logic......Page 24
1.3 Semantics of Propositional Logic......Page 25
1.5 Applications......Page 29
1.6.1 Minterms: Simple Conjunctive Formulae......Page 31
1.6.2 Maxterms, Clauses and Rules......Page 33
1.6.3 Conjunctive Normal Form......Page 35
1.6.4 Disjunctive Normal Form......Page 36
1.6.5 Transformation of a Formula into CNF/DNF......Page 38
1.6.6 Example......Page 39
1.7 Logical Consequence and Deduction......Page 40
1.8 Inference Modes: Deduction, Abduction and Induction......Page 42
1.8.1 Deduction Rules for Propositional Logic......Page 43
1.8.2 Resolution Rule......Page 45
1.8.3 Dual Resolution Rule......Page 47
1.9.1 Abduction......Page 50
1.9.2 Induction......Page 52
1.10 Generic Tasks of Propositional Logic......Page 53
1.10.3 Minimization of Propositional Formulae......Page 54
2.1 Alphabet and Notation......Page 56
2.1.1 The Role of Variables......Page 57
2.2 Terms in First-Order Logic......Page 58
2.2.1 Applications of Terms......Page 59
2.3 Formulae......Page 60
2.4 Special Forms of Formulae......Page 62
2.5 Semantics of First-Order Logic......Page 65
2.5.1 Herbrand Interpretation......Page 67
3 Attribute Logic......Page 70
3.1 Alphabet and Notation......Page 71
3.1.1 The Role of Variables......Page 72
3.2 Atomic Formulae......Page 73
3.3 Formulae in Attribute Logic......Page 74
3.4 Semantics of Attribute Logic......Page 76
3.5.1 Internal Conjunction......Page 78
3.5.2 Internal Disjunction......Page 79
3.5.3 Explicit and Implicit Negation......Page 80
3.6 Inference Rules Specific to Attributive Logic......Page 81
4.1.1 Substitutions......Page 83
4.1.2 Unification......Page 85
4.1.3 Algorithm for Unification......Page 86
4.2 Clausal Form......Page 87
4.3 Resolution Rule......Page 88
5.1 Minterm Form......Page 91
5.2 Introduction to Dual Resolution......Page 93
5.3 Dual Resolution Rule......Page 94
5.4 BD-Derivation......Page 96
5.5 Properties of BD-Resolution......Page 97
5.5.1 Soundness of BD-Resolution......Page 98
5.5.2 Completeness of BD-Resolution......Page 99
5.6 Generalized Dual Resolution Rule......Page 104
Part II Principles of Rule-Based Systems......Page 107
6 Basic Structure of Rule-Based Systems......Page 109
6.1 Basic Concepts in Rule-Based Systems......Page 110
7.1 Notation for Propositional Rule-Based Systems......Page 115
7.2 Basic Propositional Rules......Page 116
7.3 Propositional Rules with Complex Precondition Formulae......Page 118
7.4 Activation of Rules......Page 119
7.5 Deducibility and Transitive Closure of Fact Knowledge Base......Page 120
7.6 Various Forms of Propositional Rule-Based Systems......Page 123
7.6.1 Example......Page 126
7.6.2 Binary Decision Tables......Page 127
7.6.3 Binary Decision Lists......Page 130
7.6.4 Binary Decision Rules with Control Statements......Page 133
7.6.5 Binary Decision Trees......Page 134
7.6.6 Binary Decision Diagrams......Page 140
7.7 Dynamic and Non-Monotonic Systems......Page 145
8 Rule-Based Systems in Attributive Logic......Page 146
8.1 Attributive Decision Tables......Page 147
8.1.1 Basic Attributive Decision Tables......Page 148
8.1.2 Information Systems......Page 149
8.1.3 Attributive Decision Tables with Atomic Values of Attributes......Page 151
8.1.4 Example: Opticians Decision Table......Page 152
8.2 Extended Attributive Decision Systems......Page 154
8.4 Attributive Rule-Based Systems......Page 156
8.4.1 Rule Format......Page 157
8.4.2 Rule Firing......Page 158
8.5.1 Cells......Page 160
8.5.2 Rules......Page 161
8.5.3 XT --- Extended Table......Page 162
8.5.4 Connections and Their Properties......Page 163
8.6 Example: Thermostat......Page 164
9.1 Basic Form of Rules......Page 171
9.2 FOPC Rule-Base Example: Thermostat......Page 172
9.3 Extended Form of FOPC Rules......Page 173
9.4 Further Extensions in Rule Format......Page 176
10 Inference Control in Rule-Based Systems......Page 179
10.1.1 Basic Problem Formulation......Page 180
10.1.2 Advanced Problem Formulation......Page 181
10.2 Rule Interpretation Algorithm......Page 183
10.3 Inference Control at the Rules Level: Advanced Problem......Page 185
10.3.1 A Simple Linear Strategy......Page 186
11 Logic Programming and Prolog......Page 188
11.1 Introductory Example......Page 190
11.2 Prolog Syntax......Page 192
11.3 Unification in Prolog......Page 193
11.4 Resolution in Prolog......Page 194
11.5 Prolog Inference Strategy......Page 195
11.6 Inference Control and Negation in Prolog......Page 196
11.6.2 The fail Predicate......Page 197
11.7 Dynamic Global Memory in Prolog......Page 198
11.8 Lists in Prolog......Page 199
11.9 Rule Interpreters in Prolog......Page 200
Part III Verification of Rule-Based Systems......Page 204
12 Principles of Verification of Rule-Based Systems......Page 206
12.1 Validation, Verification, Testing and Optimization of Rule-Based Systems......Page 207
12.2 Verification: from General Requirements to Verifiable Characteristics......Page 208
12.3.1 Verification of RBS: a Short Review......Page 210
12.3.2 Functional Quality Assignment......Page 211
12.4 A Taxonomy of Verifiable Characteristics......Page 212
13.1 Redundancy of Knowledge Representation......Page 214
13.2 Subsumption......Page 216
13.2.2 Subsumption in Tabular Systems......Page 217
13.3 Verification of Subsumption in XTT --- a Prolog Code......Page 218
14.1 Indeterminism and Inconsistency of Rules......Page 222
14.2 Consistency Analysis......Page 223
14.2.2 Conflict and Inconsistency......Page 224
14.3 Verification of Indeterminism: a Prolog Code......Page 225
15 Reduction of Rule-Based Systems......Page 227
15.1.1 Total and Partial Reduction......Page 228
15.1.2 Specific Partial Reduction......Page 230
15.2 Reduction of Tabular Systems --- a Prolog Code Example......Page 231
16.1 Completeness of Rules......Page 233
16.2 Verification of Completeness......Page 234
16.2.1 Logical Completeness of Rule-Based Systems......Page 235
16.2.2 Specific Completeness of Rule-Based Systems......Page 236
16.2.3 Missing Precondition Identification......Page 238
16.3 Verification of Completeness in XTT --- a Prolog Code......Page 240
Part IV Design of Rule-Based Systems......Page 243
17.1 Problems of Rule-Based Systems Design......Page 245
17.2 Knowledge Engineering......Page 247
17.2.1 Knowledge Acquisition......Page 248
17.3 Design of Rule-Based Systems: Abstract Methodology......Page 249
17.4 Rule-Based Systems Design: Basic Stages......Page 252
18.1 An Intuitive Introductory Example......Page 255
18.2 The -Trees for Design Support......Page 258
18.2.1 Osiris --- a Design Tool......Page 262
19.1 Principles the ARD/XTT Approach......Page 264
19.2 Principles of the Integrated Design Process......Page 265
19.3 Conceptual Design Phase with ARD Diagrams......Page 266
19.3.1 Conceptual Modelling using ARD......Page 267
19.3.2 Attributes Definition with the Attribute Creator......Page 270
19.4 Logical Design Phase with XTT......Page 271
19.5 The Analysis and Verification Framework......Page 272
19.6.2 Debugging the Prototype......Page 273
19.6.3 Generating Stand-Alone Application......Page 274
20 Design Example: Thermostat......Page 275
20.1 Thermostat Control System......Page 276
21 Concluding Remarks......Page 288
Part V
Closing Remarks and Appendices......Page 291
A Selected Rule-Based Systems and Tools......Page 292
B
Selected Web Resources......Page 298
References......Page 305
Index......Page 314