Συμπερασματικός κανόνας

Στην μαθηματική λογική, συμπερασματικός κανόνας ή επαγωγικός κανόνας (inference rule) είναι μια συνάρτηση από σύνολα προτάσεων σε προτάσεις. Το όρισμα της συνάρτησης λέγεται σύνολο προϋποθέσεων ή απλούστερα προϋποθέσεις ή υποθέσεις, και η τιμή της συνάρτησης λέγεται συμπέρασμα. Οι συναρτήσεις αυτές μπορούν επίσης να θεωρηθούν ως σχέσεις μεταξύ των υποθέσεων και του συμπεράσματος, όπου λέμε ότι το συμπέρασμα είναι παραγόμενο ή συνεπαγόμενο ή επαγόμενο από τις υποθέσεις. Αν το σύνολο των υποθέσεων είναι κενό, τότε το συμπέρασμα λέγεται και αξίωμα στη λογική που το περιέχει.

Μια επιθυμητή ιδιότητα ενός συμπερασματικού κανόνα είναι να είναι αποτελεσματικός. Αυτό σημαίνει ότι υπάρχει μια αποτελεσματική διαδικασία (ουσιαστικά ένας αλγόριθμος) που αποφασίζει αν μια δεδομένη πρόταση μπορεί να προκύψει από οποιοδήποτε σύνολο προτάσεων με χρήση αυτού του κανόνα. Παράδειγμα αναποτελεσματικού κανόνα είναι ο κανόνας ωμέγα άπειρης τάξης.

Ένας συμπερασματικός κανόνας δεν χρειάζεται να διατηρεί κάποια σημασιολογική ιδιότητα, όπως είναι π.χ. η αλήθεια ή η εγκυρότητα του συμπεράσματος. Πράγματι, δεν χρειάζεται μια λογική που ορίζεται συντακτικά να έχει οποιαδήποτε σημασιολογία ή ερμηνεία. Ένας κανόνας μπορεί π.χ. να διατηρεί την ιδιότητα ότι το συμπέρασμα είναι συνδυασμός των υπο-προτάσεων της μεγαλύτερης πρότασης από τις υποθέσεις. Παρ' όλα αυτά, σε πολλά συστήματα οι συμπερασματικοί κανόνες χρησιμοποιούνται από κοινού με μία σημασιολογία αλήθειας / ψεύδους για να παράγουν θεωρήματα, δηλαδή κατά την κατασκευή αποδείξεων.

Εξέχοντα παραδείγματα συμπερασματικών κανόνων στην προτασιακή λογική, είναι οι κανόνες του modus ponens και modus tollens. Για τη λογική πρώτης τάξης, οι συμπερασματικοί κανόνες χρειάζονται για τους λογικούς ποσοδείκτες. Τα σχήματα αξιωμάτων μπορούν επίσης να θεωρηθούν ως συμπερασματικοί κανόνες χωρίς προϋποθέσεις.

Υπάρχουν πολλά διαφορετικά συστήματα τυπικής λογικής, κάθε ένα από τα οποία έχει το δικό του σύνολο από καλά ορισμένες προτάσεις, συμπερασματικούς κανόνες και, ενίοτε, σημασιολογία. Για παράδειγμα, βλ. χρονική λογική, τροπική λογική, ή διαισθητική λογική. Η κβαντική λογική είναι επίσης μια μορφή λογικής διαφορετική από τις παραπάνω. Για χρήσεις συμπερασματικών κανόνων, βλ. ακόμα θεωρία αποδείξεων. Στον κατηγορηματικό λογισμό, χρειάζεται ένας επιπλέον συμπερασματικός κανόνας, η γενίκευση.

Γενικά

Στην τυπική λογική (και πολλές σχετικές περιοχές στα μαθηματικά και στην επιστήμη υπολογιστών), οι συμπερασματικοί κανόνες έχουν συνήθως την παρακάτω καθιερωμένη μορφή:   Υπόθεση #1
  Υπόθεση #2
        ...
  Υπόθεση #n   
  Συμπέρασμα

Η έκφραση αυτή δηλώνει ότι, οποτεδήποτε στην πορεία μιας λογικής επαγωγικής διαδικασίας, δίνονται ή παράγονται οι συγκεκριμένες υποθέσεις, τότε το συγκεκριμένο συμπέρασμα μπορεί επίσης να ληφθεί ως δεδομένο. Η συγκεκριμένη τυπική γλώσσα που χρησιμοποιείται για να εκφράσει τόσο τις υποθέσεις όσο και το συμπέρασμα εξαρτάται από το γενικό πλαίσιο όπου γίνεται η επαγωγική διαδικασία. Για παράδειγμα, στην απλή περίπτωση που χρησιμοποιούμε λογικές προτάσεις:

  A→B
  A        
  ∴B

το οποίο είναι απλά ο κανόνας modus ponens της προτασιακής λογικής. Οι συμπερασματικοί κανόνες διατυπώνονται συνήθως ως σχήματα κανόνων με χρήση καθολικών μεταβλητών. Στον παραπάνω κανόνα (σχήμα), τα A και B μπορούν να σημαίνουν οποιοδήποτε μαθηματικό αντικείμενο ή στοιχείο συνόλου ή του Σύμπαντος (συνήθως, συμβατικά, κάποιου υποσυνόλου όπως οι μαθηματικές προτάσεις), ώστε να παράγουν ένα πιθανώς άπειρο σύνολο «συγκεκριμένων» συμπερασματικών κανόνων.

Ένα σύστημα αποδείξεων σχηματίζεται από ένα σύνολο κανόνων εφαρμοζόμενων στη σειρά ώστε να σχηματίσουν αποδείξεις, ή παραγωγές (derivations). Οποιαδήποτε παραγωγή έχει ένα μόνο τελικό συμπέρασμα, που είναι και η πρόταση που αποδεικνύεται ή παράγεται. Αν κάποιες υποθέσεις μένουν ανικανοποίητες στην παραγωγή, τότε αυτή αποτελεί απόδειξη μιας υποθετικής θέσης: «αν οι υποθέσεις ισχύουν, τότε το συμπέρασμα ισχύει».

Αποδεκτοί κανόνες και κανόνες που παράγονται

Σε ένα σύνολο κανόνων, ένας συμπερασματικός κανόνας μπορεί να είναι πλεοναστικός, με την έννοια ότι είναι αποδεκτός ή δυνάμενος να παραχθεί. Κανόνας που μπορεί να παραχθεί είναι αυτός του οποίου το συμπέρασμα μπορεί να παραχθεί από τις υποθέσεις, χρησιμοποιώντας άλλους κανόνες. Αποδεκτός κανόνας είναι αυτός του οποίου το συμπέρασμα ισχύει πάντα όταν ισχύουν οι υποθέσεις του. Όλοι οι κανόνες που μπορούν να παραχθούν είναι και αποδεκτοί. Για να φανεί η διαφορά, έστω οι παρακάτω κανόνες που ορίζουν τους φυσικούς αριθμούς (η κρίση $n\,\,{\mathsf {nat}}$ βεβαιώνει ότι το $n$ είναι φυσικός αριθμός):

${\begin{matrix}{\frac {}{\mathbf {0} \,\,{\mathsf {nat}}}}&{\frac {n\,\,{\mathsf {nat}}}{\mathbf {s(} n\mathbf {)} \,\,{\mathsf {nat}}}}\\\end{matrix}}$

Ο πρώτος κανόνας δηλώνει ότι το 0 είναι φυσικός αριθμός, και ο δεύτερος δηλώνει ότι τοs(n) είναι φυσικός αριθμός αν το n είναι. Σε αυτό το σύστημα αποδείξεων, ο ακόλουθος κανόνας, που δείχνει ότι ο μεθ-επόμενος αριθμός ενός φυσικού αριθμού είναι επίσης φυσικός αριθμός, είναι δυνάμενος να παραχθεί:

${\frac {n\,\,{\mathsf {nat}}}{\mathbf {s(s(} n\mathbf {))} \,\,{\mathsf {nat}}}}$

Η παραγωγή του είναι απλά η σύνθεση δυο χρήσεων του κανόνα για τον επόμενο αριθμό, από πριν. Ο ακόλουθος κανόνας που βεβαιώνει την ύπαρξη ενός προηγούμενου για κάθε μη μηδενικό αριθμό, είναι απλά αποδεκτός:

${\frac {\mathbf {s(} n\mathbf {)} \,\,{\mathsf {nat}}}{n\,\,{\mathsf {nat}}}}$

Αυτό ισχύει για τους φυσικούς αριθμούς, και μπορεί να αποδειχθεί με επαγωγή. (Για να αποδείξουμε ότι ο κανόνας αυτός είναι αποδεκτός, πρέπει να υποθέσουμε μια παραγωγή της υπόθεσης, και με επαγωγή να κατασκευάσουμε μια παραγωγή του $n\,\,{\mathsf {nat}}$.) Όμως, αυτό δεν είναι δυνατό να παραχθεί, αφού εξαρτάται από τη δομή της παραγωγής της υπόθεσης. Εξ' αιτίας αυτού, η ιδιότητα ενός κανόνα να δύναται να παραχθεί είναι σταθερή κάτω από προσθήκες στο σύστημα αποδείξεων, ενώ η ιδιότητα να είναι αποδεκτός όχι. Για να δείξουμε τη διαφορά, έστω ότι προσθέτουμε στο σύστημα αποδείξεων τον ακόλουθο ανόητο κανόνα:

${\frac {}{\mathbf {s(-3)} \,\,{\mathsf {nat}}}}$

Στο νέο σύστημα, ο κανόνας για το δεύτερο διάδοχο (μεθεπόμενο) είναι ακόμα δυνατό να παραχθεί. Όμως, ο κανόνας εύρεσης του προηγούμενου δεν είναι πλέον αποδεκτός, αφού δεν υπάρχει τρόπος να παραχθεί το $\mathbf {-3} \,\,{\mathsf {nat}}$. Η αποδεκτικότητα είναι τόσο εύθραυστη λόγω του τρόπου που αποδεικνύεται: αφού η απόδειξη κάνει αναγωγή στη δομή της παραγωγής της υπόθεσης, οι επεκτάσεις του συστήματος προσθέτουν νέες περιπτώσεις στην απόδειξη αυτή, επομένως αυτή μπορεί να μην ισχύει πλέον.

Οι αποδεκτοί κανόνες μπορούν να θεωρηθούν θεωρήματα του συστήματος αποδείξεων. Για παράδειγμα, σε ένα λογισμό ακολουθητών όπου ισχύει η απαλοιφή τομής, ο κανόνας τομής είναι αποδεκτός.

Διάφορες παρατηρήσεις

Οι συμπερασματικοί κανόνες μπορούν επίσης να αναφερθούν στην παρακάτω μορφή:

1. κάποιες (ίσως μηδέν) υποθέσεις
2. το σύμβολο turnstile $\vdash$ που σημαίνει παράγει, αποδεικνύει ή συμπεραίνει, και
3. ένα συμπέρασμα

Αυτό συνήθως ενσωματώνει την σχεσιακή (σε αντιδιαστολή με τη συναρτησιακή) αντίληψη ενός συμπερασματικού κανόνα, όπου το σύμβολο turnstile συμβολίζει τη συμπερασματική σχέση μεταξύ υποθέσεων και συμπεράσματος.

Οι συμπερασματικοί κανόνες πρέπει να διαχωριστούν από τα αξιώματα μιας θεωρίας. Σημασιολογικά, τα αξιώματα είναι έγκυροι ισχυρισμοί. Τα αξιώματα συνήθως θεωρούνται αρχικά σημεία για την εφαρμογή συμπερασματικών κανόνων και την παραγωγή ενός συνόλου από συμπεράσματα. Ή, με λιγότερο τεχνικούς όρους:

Οι κανόνες είναι δηλώσεις για το σύστημα, τα αξιώματα είναι δηλώσεις μέσα στο σύστημα. Για παράδειγμα:

• Ο κανόνας ότι από το $\vdash p$ μπορεί να παραχθεί το $\vdash Provable(p)$ είναι μια δήλωση που λέει αν αποδείξεις το p, τότε αποδεικνύεται το ότι το p αποδεικνύεται. Αυτό ισχύει στην αριθμητική Πεάνο, για παράδειγμα.
• Το αξίωμα $p\to Provable(p)$ θα σήμαινε ότι κάθε πρόταση που ισχύει είναι αποδείξιμη. Αυτό όμως δεν ισχύει στην αριθμητική Πεάνο.

Οι συμπερασματικοί κανόνες παίζουν σημαντικό ρόλο στη διατύπωση των διάφορων λογισμών στη λογική, όπως ο λογισμός ακολουθητών και η φυσική παραγωγή, αφού εξετάζονται στη θεωρία αποδείξεων.