Πρόλογος 17
Σημείωμα προς τον φοιτητή 20
Πρόλογος ελληνικής έκδοσης 21
ΚΕΦΑΛΑΙΟ 1 Τυπική λογική 23
1.1 Προτάσεις, συμβολική αναπαράσταση και ταυτολογίες 24
Σύνδεσμοι και τιμές αληθείας 24
Ταυτολογίες 29
Λογικοί σύνδεσμοι στον πραγματικό κόσμο 31
Ένας αλγόριθμος 32
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
ΣΕΛΙΔΑ ΙΔΙΑΙΤΕΡΟΥ ΕΝΔΙΑΦΕΡΟΝΤΟΣ Μπορεί το «και» κάποτε να γίνει «ή»; 35 ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
ENOTHTA 1.1 Ανασκόπηση 36
ΑΣΚΗΣΕΙΣ 1.1 36
1.2 Προτασιακή λογική 44
Έγκυρα επιχειρήματα 44
Παραγωγικοί κανόνες της προτασιακής λογικής 46
Παραγωγική μέθοδος και άλλοι κανόνες 50
Λεκτικά επιχειρήματα 51
ENOTHTA 1.2 Ανασκόπηση 53
ΑΣΚΗΣΕΙΣ 1.2 53
1.3 Ποσοδείκτες, κατηγορήματα και εγκυρότητα 57
Ποσοδείκτες και κατηγορήματα 57
Μετατροπή 60
Εγκυρότητα 64
ENOTHTA 1.3 Ανασκόπηση 66
ΑΣΚΗΣΕΙΣ 1.3 66
1.4 Κατηγορηματική λογική 72
Παραγωγικοί κανόνες της κατηγορηματικής λογικής 73
Καθολικός προσδιορισμός 74
Υπαρξιακός προσδιορισμός 75
Καθολική γενίκευση 75
Υπαρξιακή γενίκευση 77
Περισσότερη δουλειά με τους κανόνες 77
Λεκτικά επιχειρήματα 81
Συμπέρασμα 82
ENOTHTA 1.4 Ανασκόπηση 83
ΑΣΚΗΣΕΙΣ 1.4 83
Περιεχόμενα
1.5 Λογικός προγραμματισμός 86
Prolog 86
Όροι Horn και επίλυση 88
Αναδρομή 91
Έμπειρα συστήματα 93
ENOTHTA 1.5 Ανασκόπηση 94
ΑΣΚΗΣΕΙΣ 1.5 94
1.6 Απόδειξη της ορθότητας 96
Ισχυρισμοί 97
Κανόνας εκχώρησης 98
Υπό συνθήκη κανόνας 100
ENOTHTA 1.6 Ανασκόπηση 102
ΑΣΚΗΣΕΙΣ 1.6 103
ΚΕΦΑΛΑΙΟ 1 Ανασκόπηση 105
ΣΤΟΝ ΥΠΟΛΟΓΙΣΤΗ 106
ΚΕΦΑΛΑΙΟ 2 Αποδείξεις, επαγωγή και θεωρία αριθμών 107
2.1 Τεχνικές απόδειξης 108
Θεωρήματα και μη τυπικές αποδείξεις 108
Να αποδείξουμε ή να μην αποδείξουμε 108
Εξαντλητική απόδειξη 109
Άμεση απόδειξη 111
Αντιθετοαντιστροφή 112
Απαγωγή σε άτοπο 114
Συγκυριακή απόδειξη 115
Συνήθεις ορισμοί 116
ENOTHTA 2.1 Ανασκόπηση 117
ΑΣΚΗΣΕΙΣ 2.1 117
2.2 Επαγωγή 119
Πρώτη αρχή της επαγωγής 119
Αποδείξεις με μαθηματική επαγωγή 121
Δεύτερη αρχή της επαγωγής 126
ENOTHTA 2.2 Ανασκόπηση 130
ΑΣΚΗΣΕΙΣ 2.2 130
2.3 Περισσότερα πάνω στην απόδειξη της ορθότητας αλγορίθμων 135
Κανόνας βρόχου 136
Ευκλείδειος αλγόριθμος 139
–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
ΣΕΛΙΔΑ ΙΔΙΑΙΤΕΡΟΥ ΕΝΔΙΑΦΕΡΟΝΤΟΣ Ανάπτυξη ασφαλέστερου λογισμικού 141 –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
ENOTHTA 2.3 Ανασκόπηση 142
ΑΣΚΗΣΕΙΣ 2.3 142
2.4 Θεωρία αριθμών 147
Το Θεμελιώδες Θεώρημα της Αριθμητικής 148
Περισσότερα για τους πρώτους αριθμούς 151
Συνάρτηση φ του Euler 153
ENOTHTA 2.4 Ανασκόπηση 155
ΑΣΚΗΣΕΙΣ 2.4 155
ΚΕΦΑΛΑΙΟ 2 Ανασκόπηση 158
ΣΤΟΝ ΥΠΟΛΟΓΙΣΤΗ 158
ΚΕΦΑΛΑΙΟ 3 Αναδρομή, αναδρομικές σχέσεις και ανάλυση αλγορίθμων 160
3.1 Αναδρομικοί ορισμοί 161
Ακολουθίες που ορίζονται αναδρομικά 161
10 ΠΕΡΙΕΧΟΜΕΝΑ
Σύνολα που ορίζονται αναδρομικά 164
Πράξεις που ορίζονται αναδρομικά 167
Αλγόριθμοι που ορίζονται αναδρομικά 168
ENOTHTA 3.1 Ανασκόπηση 172
ΑΣΚΗΣΕΙΣ 3.1 173
3.2 Αναδρομικές σχέσεις 180
Γραμμικές αναδρομικές σχέσεις πρώτης τάξης 180
Γραμμικές αναδρομικές σχέσεις δεύτερης τάξης 187
Αναδρομικές σχέσεις διαίρει και βασίλευε 191
ENOTHTA 3.2 Ανασκόπηση 195
ΑΣΚΗΣΕΙΣ 3.2 195
3.3 Ανάλυση αλγορίθμων 200
Η γενική ιδέα 200
Ανάλυση με χρήση αναδρομικών σχέσεων 203
Άνω φράγμα (Ευκλείδειος αλγόριθμος) 206 ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
ΣΕΛΙΔΑ ΙΔΙΑΙΤΕΡΟΥ ΕΝΔΙΑΦΕΡΟΝΤΟΣ Δέντρα… και τηγανίτες 207 ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
ENOTHTA 3.2 Ανασκόπηση 208
ΑΣΚΗΣΕΙΣ 3.3 208
ΚΕΦΑΛΑΙΟ 3.3 Ανασκόπηση 213
ΣΤΟΝ ΥΠΟΛΟΓΙΣΤΗ 214
ΚΕΦΑΛΑΙΟ 4 Σύνολα, συνδυαστική και πιθανότητα 215
4.1 Σύνολα 216
Συμβολισμός 216
Σχέσεις μεταξύ συνόλων 218
Σύνολα συνόλων 220
Διμελείς και μονομελείς πράξεις 221
Πράξεις πάνω σε σύνολα 223
Συνολοθεωρητικές ταυτότητες 226
Αριθμήσιμα και μη αριθμήσιμα σύνολα 228
ENOTHTA 4.1 Ανασκόπηση 231
ΑΣΚΗΣΕΙΣ 4.1 232
4.2 Απαρίθμηση 242
Αρχή του γινομένου 242
Αρχή του αθροίσματος 244
Χρησιμοποιώντας τις δύο αρχές μαζί 246
Δέντρα απόφασης 248
ENOTHTA 4.2 Ανασκόπηση 249
ΑΣΚΗΣΕΙΣ 4.2 249
4.3 Αρχή εγκλεισμού-αποκλεισμού, αρχή του περιστερώνα 253
Αρχή εγκλεισμού-αποκλεισμού 254
Αρχή του περιστερώνα 258
ENOTHTA 4.3 Ανασκόπηση 259
ΑΣΚΗΣΕΙΣ 4.3 259
4.4 Μεταθέσεις και συνδυασμοί 261
Μεταθέσεις 261
Συνδυασμοί 263
Εξάλειψη των διπλότυπων 266
Μεταθέσεις και συνδυασμοί με επαναλήψεις 268
Παράγοντας μεταθέσεις και συνδυασμούς 269
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
ΣΕΛΙΔΑ ΙΔΙΑΙΤΕΡΟΥ ΕΝΔΙΑΦΕΡΟΝΤΟΣ Ο Αρχιμήδης και το «Οστομάχιον» 274 ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
ΠΕΡΙΕΧΟΜΕΝΑ 11
ENOTHTA 4.4 Ανασκόπηση 275
ΑΣΚΗΣΕΙΣ 4.4 275
4.5 Το Διωνυμικό Θεώρημα 280
Το τρίγωνο του Πασκάλ 281
Το Διωνυμικό Θεώρημα και η απόδειξή του 282
Εφαρμογές του Διωνυμικού Θεωρήματος 283
ENOTHTA 4.5 Ανασκόπηση 284
ΑΣΚΗΣΕΙΣ 4.5 284
4.6 Πιθανότητα 287
Εισαγωγή στην πεπερασμένη πιθανότητα 287
Κατανομές πιθανότητας 288
Δεσμευμένη πιθανότητα 291
Το Θεώρημα του Bayes 292
Αναμενόμενη τιμή 294
Διωνυμικές κατανομές 296
Ανάλυση μέσης περίπτωσης των αλγορίθμων 297
ENOTHTA 4.6 Ανασκόπηση 298
ΑΣΚΗΣΕΙΣ 4.6 299
ΚΕΦΑΛΑΙΟ 4 Ανασκόπηση 305
ΣΤΟΝ ΥΠΟΛΟΓΙΣΤΗ 307
ΚΕΦΑΛΑΙΟ 5 Σχέσεις, συναρτήσεις και πίνακες 309
5.1 Σχέσεις 310
Διμελείς σχέσεις 310
Ιδιότητες των σχέσεων 313
Κλειστότητες των σχέσεων 315
Μερικές διατάξεις 317
Σχέσεις ισοδυναμίας 319
ENOTHTA 5.1 Ανασκόπηση 324
ΑΣΚΗΣΕΙΣ 5.1 324
5.2 Τοπολογική ταξινόμηση 334
ENOTHTA 5.2 Ανασκόπηση 339
ΑΣΚΗΣΕΙΣ 5.2 339
5.3 Σχέσεις και βάσεις δεδομένων 342
Υπόδειγμα οντοτήτων-συσχετίσεων 342
Σχεσιακό υπόδειγμα 343
Πράξεις με σχέσεις 346
Τιμές NULL και η λογική τριών τιμών 350
Ακεραιότητα βάσεων δεδομένων 351
ENOTHTA 5.3 Ανασκόπηση 352
ΑΣΚΗΣΕΙΣ 5.3 352
5.4 Συναρτήσεις 357
Ορισμός 357
Ιδιότητες των συναρτήσεων 362
Συναρτήσεις ένα προς ένα 364
Αμφιμονοσήμαντες συναρτήσεις 366
Αντίστροφες συναρτήσεις 367
Συναρτήσεις μεταθέσεων 369
Πλήθος συναρτήσεων 371
Ισοδύναμα σύνολα 374
ENOTHTA 5.4 Ανασκόπηση 375
ΑΣΚΗΣΕΙΣ 5.4 376
12 ΠΕΡΙΕΧΟΜΕΝΑ
5.5 Τάξη μεγέθους 385
Αύξηση συνάρτησης 385
Περισσότερα για την ανάλυση αλγορίθμων 387
Το Θεώρημα Κυριαρχίας 389
Απόδειξη του Θεωρήματος Κυριαρχίας 391
ENOTHTA 5.5 Ανασκόπηση 392
ΑΣΚΗΣΕΙΣ 5.5 393
5.6 Η συνάρτηση MOD 395
Κατακερματισμός 395
Ασφάλεια υπολογιστών 308
Κρυπτογραφία 308
Κατακερματισμός για την κρυπτογράφηση κωδικού πρόσβασης 404
Διάφορες εφαρμογές 405
Αναγνωριστικοί κωδικοί 405
Παράγοντας και αποσυνθέτοντας ακέραιους αριθμούς 407
Αρθρωτά αριθμητικά σχέδια 408
ENOTHTA 5.6 Ανασκόπηση 410
ΑΣΚΗΣΕΙΣ 5.6 410
5.7 Πίνακες 414
Ορολογία 414
Πράξεις με πίνακες 417
Απαλοιφή Gauss 421
Πίνακες Boole 425
–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
ΣΕΛΙΔΑ ΙΔΙΑΙΤΕΡΟΥ ΕΝΔΙΑΦΕΡΟΝΤΟΣ Λύστε εκατομμύρια εξισώσεις πιο γρήγορα από τον Gauss 426 –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
ENOTHTA 5.7 Ανασκόπηση 427
ΑΣΚΗΣΕΙΣ 5.7 427
ΚΕΦΑΛΑΙΟ 5 Ανασκόπηση 434
ΣΤΟΝ ΥΠΟΛΟΓΙΣΤΗ 437
ΚΕΦΑΛΑΙΟ 6 Γραφήματα και δέντρα 439
6.1 Τα γραφήματα και οι αναπαραστάσεις τους 440
Ορισμοί ενός γραφήματος 440
Εφαρμογές των γραφημάτων 442
Ορολογία γραφημάτων 444
Ισομορφικά γραφήματα 447
Επίπεδα γραφήματα 450
Αναπαράσταση γραφημάτων σε υπολογιστή 455
Πίνακας γειτνίασης 455
Λίστα γειτνίασης 456
–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
ΣΕΛΙΔΑ ΙΔΙΑΙΤΕΡΟΥ ΕΝΔΙΑΦΕΡΟΝΤΟΣ Iσομορφικά γραφήματα πρωτεΐνης 459 –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
ENOTHTA 6.1 Ανασκόπηση 460
ΑΣΚΗΣΕΙΣ 6.1 460
6.2 Δέντρα και αναπαραστάσεις αυτών 470
Ορολογία δέντρων 470
Εφαρμογές των δέντρων 472
Αναπαράσταση δυαδικού δέντρου 473
Αλγόριθμοι διάσχισης δέντρου 474
Αποτελέσματα σχετικά με τα δέντρα 478
ENOTHTA 6.2 Ανασκόπηση 480
ΑΣΚΗΣΕΙΣ 6.2 480
ΠΕΡΙΕΧΟΜΕΝΑ 13
6.3 Δέντρα απόφασης 487
Αναζήτηση 488
Κάτω φράγματα στην αναζήτηση 490
Αναζήτηση σε δυαδικό δέντρο 491
Ταξινόμηση 493
ENOTHTA 6.3 Ανασκόπηση 494
ΑΣΚΗΣΕΙΣ 6.3 494
6.4 Κώδικες Huffman 497
Το πρόβλημα και η δοκιμαστική λύση 497
Αλγόριθμος κωδικοποίησης Huffman 499
Αιτιολόγηση 502
Εφαρμογές των κωδικών Huffman 503
ENOTHTA 6.4 Ανασκόπηση 504
ΑΣΚΗΣΕΙΣ 6.4 504
ΚΕΦΑΛΑΙΟ 6 Ανασκόπηση 507
ΣΤΟΝ ΥΠΟΛΟΓΙΣΤΗ 508
ΚΕΦΑΛΑΙΟ 7 Αλγόριθμοι γραφημάτων 509
7.1 Κατευθυνόμενα γραφήματα και διμελείς σχέσεις. Ο αλγόριθμος του Warshall 510
Κατευθυνόμενα γραφήματα και διμελείς σχέσεις 511
Προσπελασιμότητα 513
Ο αλγόριθμος του Warshall 517
ENOTHTA 7.1 Ανασκόπηση 521
ΑΣΚΗΣΕΙΣ 7.1 521
7.2 Μονοπάτια Euler και κυκλώματα Hamilton 525
Το πρόβλημα του μονοπατιού Euler 525
Το πρόβλημα του κυκλώματος Hamilton 529
ENOTHTA 7.2 Ανασκόπηση 530
ΑΣΚΗΣΕΙΣ 7.2 531
7.3 Συντομότερο μονοπάτι και ελάχιστο επικαλύπτον δέντρο 534
Το πρόβλημα του συντομότερου μονοπατιού 534
Το πρόβλημα του ελάχιστου επικαλύπτοντος δέντρου 539
–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
ΣΕΛΙΔΑ ΙΔΙΑΙΤΕΡΟΥ ΕΝΔΙΑΦΕΡΟΝΤΟΣ Aναζήτηση μονοπατιού 541 –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
ENOTHTA 7.3 Ανασκόπηση 542
ΑΣΚΗΣΕΙΣ 7.3 542
7.4 Αλγόριθμοι διάσχισης 548
Αναζήτηση κατά βάθος 548
Αναζήτηση κατά πλάτος 550
Ανάλυση 553
Εφαρμογές 553
ENOTHTA 7.4 Ανασκόπηση 555
ΑΣΚΗΣΕΙΣ 7.4 556
7.5 Σημεία άρθρωσης και δίκτυα υπολογιστών 558
Η διατύπωση του προβλήματος 558
Η ιδέα πίσω από τον αλγόριθμο 559
Ο αλγόριθμος 561
ENOTHTA 7.5 Ανασκόπηση 563
ΑΣΚΗΣΕΙΣ 7.5 563
ΚΕΦΑΛΑΙΟ 7 Ανασκόπηση 564
ΣΤΟΝ ΥΠΟΛΟΓΙΣΤΗ 565
14 ΠΕΡΙΕΧΟΜΕΝΑ
ΚΕΦΑΛΑΙΟ 8 Άλγεβρα Boole και λογική υπολογιστών 587
8.1 Η δομή της άλγεβρας Boole 588
Υποδείγματα ή αφηρημένες μορφές 589
Ορισμός και ιδιότητες 570
Ισομορφικές άλγεβρες Boole 575
Τι είναι ο ισομορφισμός; 575
Εφαρμογή του ισομορφισμού στις άλγεβρες Boole 576
ENOTHTA 8.1 Ανασκόπηση 579
ΑΣΚΗΣΕΙΣ 8.1 579
8.2 Λογικά κυκλώματα 585
Συνδυαστικά κυκλώματα 585
Βασικά λογικά στοιχεία 585
Εκφράσεις Boole 586
Συναρτήσεις αληθείας 586
Κυκλώματα και εκφράσεις 587
Κανονική μορφή 588
Ελαχιστοποίηση 591
Προγραμματιζόμενες λογικές συσκευές 592
Ένα χρήσιμο κύκλωμα 594
Άλλα λογικά στοιχεία 595
Κατασκευάζοντας συναρτήσεις αληθείας 597
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
ΣΕΛΙΔΑ ΙΔΙΑΙΤΕΡΟΥ ΕΝΔΙΑΦΕΡΟΝΤΟΣ Κλάδεμα τσιπ και προγραμμάτων 598 ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
ENOTHTA 8.2 Ανασκόπηση 599
ΑΣΚΗΣΕΙΣ 8.2 599
8.3 Ελαχιστοποίηση 606
Διαδικασία ελαχιστοποίησης 606
Χάρτης Karnaugh 607
Χάρτες για τρεις και τέσσερις μεταβλητές 608
Χρησιμοποιώντας τον χάρτη Karnaugh 610
Η διαδικασία των Quine – McCluskey 614
ENOTHTA 8.3 Ανασκόπηση 618
ΑΣΚΗΣΕΙΣ 8.3 618
ΚΕΦΑΛΑΙΟ 8 Ανασκόπηση 623
ΣΤΟΝ ΥΠΟΛΟΓΙΣΤΗ 624
ΚΕΦΑΛΑΙΟ 9 Μοντελοποίηση αριθμητικής, υπολογισμός και γλώσσες 625
9.1 Αλγεβρικές δομές 626
Ορισμοί και παραδείγματα 626
Βασικά αποτελέσματα για τις ομάδες 634
Υποομάδες 637
Ισομορφικές ομάδες 640
ENOTHTA 9.1 Ανασκόπηση 645
ΑΣΚΗΣΕΙΣ 9.1 645
9.2 Θεωρία κωδικοποίησης 650
Εισαγωγή 650
Υπόβαθρο: Ομομορφισμοί και σύμπλοκα 651
Παράγοντας κώδικες ομάδας 653
Αποκωδικοποιώντας κώδικες ομάδας 658
ENOTHTA 9.2 Ανασκόπηση 662
ΑΣΚΗΣΕΙΣ 9.2 662
9.3 Μηχανές πεπερασμένων καταστάσεων 663
Ορισμός 664
ΠΕΡΙΕΧΟΜΕΝΑ 15
Παραδείγματα μηχανών πεπερασμένων καταστάσεων 665
Αναγνώριση 668
Κανονικά σύνολα και το Θεώρημα του Kleene 670
Ελαχιστοποίηση μηχανής 672
Μη προσπελάσιμες καταστάσεις 672
Διαδικασία ελαχιστοποίησης 673
Ακολουθιακά κυκλώματα και μηχανές πεπερασμένων καταστάσεων 678
–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
ΣΕΛΙΔΑ ΙΔΙΑΙΤΕΡΟΥ ΕΝΔΙΑΦΕΡΟΝΤΟΣ Οι μηχανές πεπερασμένων καταστάσεων στη σχεδίαση παιχνιδιών 682 –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
ENOTHTA 9.3 Ανασκόπηση 683
ΑΣΚΗΣΕΙΣ 9.3 684
9.4 Μηχανές Turing 695
Μηχανές Turing ως αναγνωριστές συνόλων 699
Οι μηχανές Turing ως υπολογιστές συναρτήσεων 702
Θέση των Church – Turing 704
Προβλήματα απόφασης και μη υπολογισιμότητα 705
Παραδείγματα προβλημάτων απόφασης 706
Το πρόβλημα τερματισμού 707
Υπολογιστική πολυπλοκότητα 710
ENOTHTA 9.4 Ανασκόπηση 712
ΑΣΚΗΣΕΙΣ 9.4 712
9.5 Τυπικές γλώσσες 715
Κατηγορίες γραμματικών 721
Τυπικές γλώσσες και υπολογιστικές συσκευές 724
Γραμματικές χωρίς συμφραζόμενα 725
ENOTHTA 9.5 Ανασκόπηση 727
ΑΣΚΗΣΕΙΣ 9.5 727
ΚΕΦΑΛΑΙΟ 9 Ανασκόπηση 730
ΣΤΟΝ ΥΠΟΛΟΓΙΣΤΗ 732
ΠΑΡΑΡΤΗΜΑ Α
Συμπερασματικοί κανόνες για την προτασιακή και κατηγορηματική λογική 735
ΠΑΡΑΡΤΗΜΑ Β
Συμβολισμός του αθροίσματος και του γινομένου 737
ΠΑΡΑΡΤΗΜΑ Γ
Η λογαριθμική συνάρτηση 740