Notions and theorems of elementary formal logic

Front Cover......Page 1
Title Page......Page 4
Copyright Page......Page 5
Table of Contents......Page 6
List of Main Entries......Page 8
Introduction......Page 20
Terminological Remarks......Page 22
Abstract logics......Page 28
Algebra of formal expressions......Page 29
Algebra of switching circuits......Page 30
Algorithm......Page 32
Algorithmic logic......Page 33
Amalgamation property......Page 34
Aristotle's syllogistic......Page 35
Arithmetization......Page 36
Atomic formula......Page 37
Atomic theory......Page 38
Axiom......Page 39
Axiom systems for intuitionistic propositional logic......Page 40
Axiom system for intuitionistic quantification theory......Page 42
Axiom systems for the first-order quantification theory......Page 43
Axiom systems for two-valued propositional logic......Page 46
Axiomatic methodology of deductive sciences......Page 49
Axiomatics......Page 52
Axiomatizability......Page 53
Axiomatizability of class of relational systems......Page 55
Axiomatizability of logical matrix......Page 57
Beth's theorem......Page 58
Boolean algebra......Page 59
Boolean realization of S_1......Page 60
Bracketless symbolism......Page 62
Calculus of systems......Page 63
Categoricity......Page 66
Chain of interpretations......Page 68
Choice rule......Page 69
Church's purely implicational logic......Page 71
Classical propositional logic......Page 72
Classical quantification theory......Page 74
Classical quantification theory in purely derivative formalization......Page 76
Closure system......Page 77
Compactness theorem......Page 78
Completeness. General remarks......Page 79
Completeness in S_0......Page 80
Completeness in S_1......Page 81
Completeness test......Page 82
Consequence operation......Page 83
Consequence operation connected with classical quantification theory......Page 85
Consequence operation connected with logical system......Page 86
Consequence operation generated by a set of logical matrices......Page 87
Consequence operator of the two-valued propositional logic......Page 88
Consequence relation......Page 90
Conservative logic......Page 91
Consistency......Page 92
Constructive theory......Page 93
Contradiction......Page 94
Creativity of definitions - Lukasiewicz's example......Page 95
Cut rule......Page 97
Decidability......Page 99
Deduction theorem......Page 101
Deductive system......Page 102
Definability in S_0......Page 103
Definability in S_1......Page 105
Definition ally complete sets of two-valued connectives......Page 107
Definitions of new individual constants......Page 108
Degree of completeness of propositional logic......Page 109
Derivable rule......Page 111
Description......Page 112
Discussive logic......Page 113
Disjunction property......Page 116
Duality......Page 117
Elementary class......Page 118
Elementary embedding of interpretations......Page 119
Elementary equivalence......Page 120
Elementary extension......Page 121
Elementary ontology of Lesniewski......Page 122
Elementary protothetics of Lesniewski......Page 125
Elementary substructure......Page 132
Equivalence of logical systems......Page 133
Equivalence of the Boolean representation theorem and Gödel's completeness theorem......Page 134
Extension of a consequence operation......Page 135
Filter-consequence operation......Page 137
Finite model property......Page 139
First-order property......Page 140
First-order theories......Page 141
Frayne-Morel-Scott theorem......Page 142
Frayne's theorem......Page 143
Function letters......Page 144
Fuzzy logic......Page 145
Generalization......Page 146
Generalized connectives of conjunction and disjunction......Page 147
Generalized interpolation theorem for propositional logic......Page 149
Gentzen's formalism. General remarks......Page 150
Gentzen's formalism. Classical propositional formalism......Page 151
Gentzen's formalism for quantification theory......Page 154
Gödel's completeness theorem......Page 157
Gödel's first theorem. Theorem on undeciclability of arithmetic......Page 158
Gödel's second theorem......Page 161
Gödel-Malcev propositional theorem......Page 162
Grammar of formal language......Page 163
Hauber's propositional theorem......Page 164
Herbrand's theorem......Page 165
Herbrand-Gentzen theorem......Page 166
Hilbert's e-theorem......Page 168
Hilbert's purely implicational logic......Page 169
Hilbert's theorem on deduction......Page 170
Hilbert's thesis......Page 171
Hypothesis......Page 172
Identity......Page 173
Inconsistency......Page 174
Independence......Page 175
Indirect proof......Page 176
Inferential equivalence......Page 177
Infinite-valued logic......Page 178
Interpolation theorem in propositional logic......Page 180
Interpretation of the language S_1......Page 181
Intuitionistic logic of quantifiers......Page 183
Intuitionistic propositional calculus......Page 187
Isomorphism of interpretations ,......Page 194
Isomorphic embedding of interpretations......Page 195
Jaskowski's operation on implicative lattices......Page 196
Keisler's ultrapower theorem......Page 197
Kreisel-Putnam logic......Page 198
Kripke models for intuitionistic logic......Page 199
Kripke models for modal logics......Page 202
k-valued propositional logics of Lukasiewicz......Page 203
Lambda-operator. Combinatory logic......Page 207
Language of elementary theory......Page 209
Language of formal logic......Page 210
Lattices used in logic. Basic structures......Page 212
Lindenbaum algebra......Page 215
Lindenbaum's lemma......Page 219
Lindenbaum's theorem on logical matrices......Page 220
Linear logic of Dummet......Page 221
Logic. General remarks......Page 223
Logic of provability......Page 226
Logic of strict implication......Page 229
Logic of strong (rigorous) implication. Ackermann's system......Page 232
Logic with relevant implication......Page 235
Logic with semi-negation......Page 236
Logical antinomy......Page 238
Logical consequence......Page 240
Logical laws. Introductory remarks......Page 242
Law of commutation......Page 243
Law of double negation......Page 244
Law of Duns Scotus......Page 245
Law of Duns Scotus in implicational form......Page 246
Law of existential quantification......Page 247
Law of excluded middle......Page 248
Law of particularization......Page 249
Law of reductio ad absurdum......Page 250
Law of repetition......Page 251
Law of simplification......Page 252
Law of transitivity of implication......Page 253
Laws defining disjunction......Page 254
Laws of composition......Page 256
Laws of mutual definability of quantifiers......Page 258
Laws of negation of complex formulas......Page 259
Laws of transposition......Page 260
Logical necessity. General remarks......Page 261
Logical necessity. Axiomatic description......Page 263
Logical notion of information......Page 266
Logical rule of Hilbert's type......Page 268
Logical semantics. General remarks......Page 269
Logical system......Page 272
Logical truth in the language S_0......Page 274
Logical truth in the language S_1......Page 275
Logical value......Page 277
Logicism......Page 278
Löb's theorem......Page 280
Lyndon's homomorphism theorem......Page 282
Los-Suszko theorem on matrix consequence......Page 283
Los's theorem on ultraproduct of interpretations......Page 284
Lukasiewicz's programme of logical reconstruction of philosophy......Page 285
Main propositional metatheorem......Page 287
Many-valued logics. General remarks......Page 290
Matrix completeness......Page 291
Matrix models for propositional logics......Page 293
Minimal propositional logic of Hilbert's type......Page 295
Minimal propositional logic of non-Hilbert's type......Page 299
Modal algebraic semantics......Page 301
Model completeness......Page 302
Models of the language S_0......Page 303
Models of the language S_1......Page 304
Modular logic......Page 305
Modus ponens rule......Page 307
Natural deduction. General remarks......Page 309
Natural deduction in S_0......Page 310
Natural deduction in S_1......Page 311
Non-axiomatizability of finite matrices......Page 313
Non-standard consequence operations......Page 314
Non-reflexive consequence operation......Page 315
Non-monotonic consequence operation......Page 316
Non-idempotent consequence operation......Page 317
Normal form in S_0......Page 319
Normal form in S_1. Prenex normal form......Page 320
Normal modal logic......Page 321
Normal rule......Page 323
n-valued Gödel-Thomas propositional logics......Page 324
Omitting types theorem......Page 327
Operation of abstraction......Page 329
Operation of rejection......Page 330
Optimal and minimal propositional formulas......Page 331
Ordered set......Page 332
\omega-saturated models......Page 333
Paraconsistent logic......Page 335
Paradoxes of implication......Page 338
Permissible rule......Page 339
Philosophical logic......Page 340
Deontic logic......Page 342
Epistemic logic......Page 343
Modal logic......Page 344
Non-Fregean logic......Page 347
Temporal logic......Page 348
Logic of negligence......Page 349
Positive logic. Hilbert's logic......Page 350
Post-completeness theorem for classical propositional logic......Page 353
Predicate......Page 354
Preservation theorems......Page 356
Primitive rule......Page 357
Product of logical matrices......Page 358
Proof......Page 359
Propositional calculus......Page 360
Biconditional (equivalence)......Page 361
Conjunction......Page 362
Disjunction......Page 363
Implication......Page 364
Negation......Page 365
Sheffer's stroke......Page 366
Many-argument connectives......Page 367
Propositional connectives of classical propositional logic......Page 368
Propositional logic with quantifiers......Page 370
Pseudo-boolean interpretation......Page 372
Pure quantification theory......Page 373
Quantifier......Page 374
Quotation marks......Page 376
Reconstructability of the two-valued propositional logic in non-classical logics......Page 377
Recursively enumerable set......Page 379
Reduction of substitution to the axioms in propositional logic......Page 380
Reichenbach's propositional logic. Quantum logic......Page 381
Relatedness logic......Page 383
Relational structure......Page 387
Relational structure. A list of most important derivative notions......Page 388
Relational structures. Many sorted structures......Page 390
Relevance......Page 391
Relevant logic - system E. Logic of entailment......Page 392
Relevant logic - system R. Logic of the conditional......Page 397
Representation theorem for classical two-valued matrix......Page 401
Robinson's theorem......Page 402
Rule of extensionality......Page 403
Rule of \omega-induction......Page 404
Satisfiability by a finite sequence......Page 405
Satisfiability in the language S_x......Page 406
Second order logic......Page 408
Semantical completeness theorem for classical propositional logic......Page 414
Semantical completeness theorem for classical quantification theory......Page 415
Semantical consequence operation in S_0......Page 417
Semantical consequence operation in S_1......Page 419
Set-theoretical foundations of logic......Page 421
Short history of formal logic......Page 423
Short survey of notions connected with the notion of embeddability of interpretations......Page 426
Similarity of formulas......Page 427
Single axioms for some propositional logics......Page 428
Skolem-Löwenheim-Tarski theorem......Page 430
Skolem's theorem on elimination of existential quantifiers......Page 431
Standard formalization of logic of quantifiers......Page 432
Standard rule in S_0......Page 433
Strong completeness theorem for the first-order logic......Page 434
Structural completeness......Page 435
Structural rule......Page 437
Substitution rule for individual variables......Page 438
Substitution rule for predicative expressions......Page 439
Substitution rule for propositional variables......Page 441
Substructure of interpretation (submodel)......Page 442
Tarski's theorem on undefinability of the notion of arithmetical truth......Page 443
Tautology......Page 444
Theorem on axiomatizability of a class of relational structures......Page 445
Theorem on isomorphic embedding of interpretations......Page 446
Theorem on logical consequence......Page 447
Theorem on non distinguishing of individual constants......Page 448
Theorem on structural completeness of classical logic......Page 449
Theorem on the union and intersection of theories......Page 451
Theorems on cardinality of models......Page 452
Theorems on interpret ability of intuitionistic propositional logic in modal logic SG_4......Page 453
Theorems on preservation under homomorphisms......Page 454
Theory......Page 455
Theory from the point of view of the consequence operator......Page 456
Theory of relational structure......Page 457
Theory of types......Page 458
Three-valued propositional Gödel's logic......Page 461
Three-valued propositional Lukasiewicz's logic......Page 463
Transformation of bound variables......Page 466
True and false sentences......Page 467
Turing machine......Page 468
Two-argument negation......Page 470
Two-valued classical matrix......Page 471
Two-valued implicational propositional logic......Page 472
Two-valued propositional logic......Page 473
Two-valued propositional logic in Church's formalization......Page 474
Two-valued propositional logic with implication and negation......Page 476
Two-valued propositional logic with strongly operating rules......Page 477
Two-valued purely equivalential Lukasiewicz's logic......Page 480
Two-valuedness hypothesis......Page 482
Type of a theory......Page 484
Ultraproduct of interpretations......Page 485
Undecidability of classical quantification logic......Page 487
Unfailing rules......Page 488
Uniqueness of the Lindenbaum's extensions......Page 489
Universal sentence......Page 490
Variable functor......Page 491
Vaught's test......Page 494
Well-formed formula......Page 495
Bibliography......Page 496
Notation......Page 505
General Index......Page 511
Back Cover......Page 528