|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Hein J.L. — Discrete Structures, Logic, and Computability |
|
|
|
| Предметный указатель |
LR(k) grammar 673
LR(k) parsing 672—684
Lub see “Least upper bound”
Lucas numbers 243 247
Lucas, Edouard 243 293
Lukasiewicz, J. 349 847
Lusk, E. 475 849
Mallows, C.L. 169 847
Manna, Z. 847
map function 84 157
Mapping see “Function”
Markov algorithm 724
Markov, A.A. 726 847
Mathematical induction 231 237
Matiyasevich, Y. 745
Matrix 33
Matrix algebra 514
max function 83
Maximal element 214
McAllister, D.F. 849
Mealy machine 597
Mealy, G.H. 597 848
Meaning of a wff 313 360
Member 10 30 535
Memoization 766
Mendelson, E. 848
Mgu see “Most general unifier”
Minimal CNF 527
Minimal DNF 527
Minimal element 214
Minimal spanning tree 5
Minimalization rule 722
Minimum condition 221
Minimum-state DFAs 617—624
Minsky, M.L. 848
MOD function 69
Modal logic 350
Model 362 712
modus ponens 306 330
Monadic logic 476
Monoid 511
Monomorphism 567
Monotonic 229 768
Monus operation 543
Moore machine 597
Moore, E.F. 597 848
Morphism 567 564—571
Morphism, epimorphism 567
Morphism, homomorphism 567
Morphism, isomorphism 567
Morphism, language 570 572 635 636 693 694
Morphism, monomorphism 567
Most general unifier 465
MP see “Modus ponens”
MT see “Modus tollens”
Mult operation 533
Multigraph 43
Multiset 24
Myhill, J. 618 848
n-ary relation 40
n-colorable graph 42
n-ovals problem 275
n-tuple 31
n-valued logic 349
Nagel, E. 443 848
Natural deduction 365
Natural numbers 12 111—113 148—151 355 530—534 762
Necessary condition 3
Negation 2 309 517
Negative literal 455
Nerode, A. 618 848
Newman, J.R. 443 848
Newton — Raphson method 171
NFA see “Nondeterminist finite automaton”
NFA to DFA algorithm 614
NFA to regular grammar 628
Nil process 548
Nivat, M. 772 M5
Node 41 48
Noether, Emmy 221
Non sequitur 307
Nondeterministic finite automaton 588
Nondeterministic finite automaton as an algebra 605
Nondeterministic PDA 643
Nondeterministic Turing machine 706
Nonregular languages 631
Nonterminals 134
NOR see “Normal order reduction”
Normal form 318—326 374—377 756
Normal form, conjunctive 322
Normal form, disjunctive 320
Normal form, full conjunctive 322
Normal form, full disjunctive 321
Normal form, fundamental conjunction 320
Normal form, fundamental disjunction 322
Normal form, prenex 374
Normal form, prenex conjunctive 376
Normal form, prenex disjunctive 376
Normal order reduction 757
NOT see “Negation”
NOT gate 522
nth-order logic 441
Null set 11
Numeral 37
Numeral, binary 37 125 146
Numeral, decimal 37 113 126 127 140 142 146
Numeral, even decimal 141
Numeral, finite rational 142
Numeral, Roman 37
Object 10 30
One-to-one correspondence 92
One-to-one function 90
Onto function 91
Operation table 510
Operations on sets 15—21
Operator see “Function”
Optimal algorithm, average case 271
Optimal algorithm, problem 250
Optimal algorithm, worst case 251
OR see “Disjunction”
OR gate 522
Order of a predicate 439
Order of a quantifier 440
Order of a wff 440
Order relation 209—227
Order, lower 300
Ordered pair 31
Ordered tree 48
Ordered triple 31
Ordinal numbers 226—227
Ordinal numbers, finite 226
Ordinal numbers, infinite 226
Ordinal numbers, limit 227
Outdegree 45
Outermost redex 757
Overbeek, R. 475 849
P (premise) 333
P for IP 339
Pairs function 74 154
Palindrome 125 142
Pan, V. 252 848
Pancake recipe 209
Parallel computation 210 732
Parallel language 732
Paramodulation 475
Parent 48
parse 130
Parse tree 131
Parsing 659—684
Parsing, bottom-up 659
| Parsing, first set 667
Parsing, follow set 668
Parsing, handle 672
Parsing, item 679
Parsing, LL(1) parse table 669
Parsing, LL(k) 659—672
Parsing, lookahead symbol 659
Parsing, LR(1) 674
Parsing, LR(1) table 679—684
Parsing, LR(k) 672—684
Parsing, recursive descent 665
Parsing, shift-reduce 677
Parsing, top-down 659
Partial correctness 430
Partial fraction 287
Partial function 74
Partial order 210—227
Partial order theory 411
Partial order, ascending chain 212
Partial order, chain 212
Partial order, descending chain 212
Partial order, greatest element 214
Partial order, greatest lower bound 214
Partial order, Hasse diagram 213
Partial order, immediate predecessor 213
Partial order, immediate successor 213
Partial order, irreflexive 212
Partial order, least element 214
Partial order, least upper bound 214
Partial order, lower bound 214
Partial order, maximal element 214
Partial order, minimal element 214
Partial order, minimum condition 221
Partial order, poset diagram 213
Partial order, predecessor 212
Partial order, reflexive 212
Partial order, set, poset 210
Partial order, sorting problem 216
Partial order, successor 212
Partial order, topological sorting problem 216
Partial order, topologically sorted 217
Partial order, upper bound 214
Partial recursive functions 723 717—724
Partially decidable 365 745
Partially ordered set 210 529
Partially ordered structure 412
Partially solvable 365 745
Partition 194 194—200
Partition, coarser 198
Partition, equivalence class 194
Partition, finer 198
Partition, refinement 198
Partsch, H. 848
Pascal, Blaise, xviii 262
Pascals triangle 262
Patashnik, O. 304 846
Paterson, M.S. 475 848
Path 45
Path problems 183—189
Path, cycle, circuit 45
Path, Euler 46
Path, Euler circuit 46
Path, length 45
Pattern-matching definition 148
Paulson, L.C. 848
PDA see “Pushdown automata”
Peano, Giuseppe 112 531
Pepper, P. 848
permutations 257—261
Permutations, bag 259
Permutations, with replacement 258
Permutations, without replacement 258
Phrase-structure grammar 749
Pigeonhole Principle 93 137 631
Planar graph 42
Plus operation 531 719
Polish notation 349
Polynomial algebra 514
Pop operation 537
Pope, Alexander 575
POSET see “Partially ordered set”
Poset diagram 213
Positive literal 455
Post algorithm 726
Post canonical system 728
Post system 728
Post, E.L. 726 743 848
Post-computable 729
Postcondition 415
Postfix evaluation 538
Postorder 162 544
Posts correspondence problem 743
Power series algebra 515
Power set 13
Power set problem 163
Pre-image 62
Precedence hierarchy 311 357 549 578
Precondition 415
Predecessor 212 532
Predicate 352
Predicate constants 356
Predicate, order of 439
Prefix-closed 549
Premise 309 329
Prenex, conjunctive normal form 376
Prenex, disjunctive normal form 376
Prenex, disjunctive/conjunctive normal form algorithm 376
Prenex, normal form 374
Prenex, normal form algorithm 375
Preorder 160 544
Preserve, a relation 558
Preserve, an operation 566
Prim, R.C. 52 848
Prime number 5
Primitive recursion rule 719
Primitive recursive function 722
Prim’s algorithm 52
Principle of inclusion exclusion 22
Priority queue 542
probability 265—273
Probability of an event 267
Probability, average case 270
Probability, distribution 267
Probability, event 267
Probability, expected value 271
Probability, sample point 267
Probability, sample space 267
Procedure 147 152 161
Procedure, recursively defined 47 146—169
Process 548
Process algebra 548—550
Process algebra, action 548
Process algebra, nil 548
Process algebra, nondeterminism 549
Process algebra, prefixing 548
Process algebra, process 548
Product as arrays 33
Product as records 34
Product of sets 32
Product, cartesian 32
Product, counting rule 53
Product, cross 32
Product, language 128
Product, notation 150
Product, set 122—124
Production 132
Production, indirectly recursive 137
Production, recursive 137
Production, unit 687
Program correctness 414—433
|
|
|
| Реклама |
|
|
|
|
|
О проекте