Προτασιακός λογισμός

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

Το ακόλουθο είναι ένα παράδειγμα ενός πολύ απλού συμπερασμού που εμπίπτει στο πεδίο εφαρμογής της προτασιακής λογικής:

Προκείμενη 1: Αν βρέχει, τότε έχει συννεφιά

Προκείμενη 2: Βρέχει.

Συμπέρασμα: Έχει συννεφιά.

Και οι δύο προκείμενες, όπως και το συμπέρασμα είναι λογικές προτάσεις. Οι προκείμενες θεωρούνται δεδομένες και, στη συνέχεια, με την εφαρμογή του modus ponens (ένας κανόνας συμπερασμού) συνάγεται το συμπέρασμα.

Καθώς όμως η προτασιακή λογική δεν ασχολείται με τη δομή των προτάσεων πέρα από όσο μπορούν να αναλυθούν μέσω των λογικών συνδέσμων, ο παραπάνω συμπερασμός μπορεί να επαναδιατυπωθεί αντικαθιστώντας τις προηγούμενες ατομικές προτάσεις με συγκεκριμένα σύμβολα («προτασιακές μεταβλητές») που τις αντιπροσωπεύουν:

Προκείμενη 1: $P\to Q$

Προκείμενη 2: $P$

Συμπέρασμα: $Q$

Το ίδιο μπορεί να παρασταθεί συμβολικά με τον ακόλουθο τρόπο:

$P\to Q,P\vdash Q$

Όταν το Ρ ερμηνεύεται ως «Βρέχει» και το Q ως «έχει συννεφιά» οι παραπάνω συμβολικές εκφράσεις μπορεί να θεωρηθούν ότι αντιστοιχούν ακριβώς στην αρχική έκφραση σε φυσική γλώσσα. Όχι μόνο αυτό, αλλά θα αντιστοιχούν επίσης και σε οποιοδήποτε άλλο συμπερασμό αυτής της μορφής, ο οποίος θα είναι έγκυρος κατά τον ίδιο τρόπο.

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

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

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

Ιστορική αναδρομή[Επεξεργασία | επεξεργασία κώδικα]

Παρ'όλο που η προτασιακή λογική (που συχνά συγχέεται με τον προτασιακό λογισμό) έχει υπαινιχθεί από πρώιμους φιλόσοφους, αναπτύχθηκε σε επίσημη λογική από τον Χρύσιππο τον 3 αιώνα [1] και επεκτάθηκε από τους Στωικούς. Η λογική ήταν εστιασμένη στις προτάσεις. Η ανέλιξη αυτή ήταν διαφορετική από την παραδοσιακή συλλογιστική λογική που εστίαζε στους όρους. Δυστυχώς όμως στην αρχαιότητα τ,η προτασιακή λογική που είχε αναπτυχθεί από τους Στωικούς έπαψε να είναι κατανοητή. Συνεπώς αυτό το σύστημα ιδεών ουσιαστικά ανακαλύφτηκε εκ νέου από τον Πέτρο Αβελάρδο τον 12ο αιώνα.^[1]

Η προτασιακή Λογική βελτιώθηκε σταδιακά με την χρήση συμβόλων . Ο φιλόσοφος Γκότφριντ Λάιμπνιτς του 17ου-18ου αιώνα έχει αποτιμηθεί ως ο ιδρυτής της Συμβολικής Λογικής για την δουλειά του. Παρόλο που ήταν ο πρώτος που ασχολήθηκε με αυτό το είδος, δεν ήταν γνωστός στην τότε διαδεδομένη κοινότητα που ασχολούνταν με την λογική. Για αυτόν τον λόγο πολλές από τις ανακαλύψεις του, επαναδιατυπώθηκαν από άλλους λογικούς όπως ο Τζορτζ Μπουλ και ο Αύγουστος ντε Μόργκαν. Όπως ήταν απόλυτα λογικό όμως, όλες οι επαναδιατυπώσεις ήταν απολύτως εξαρτημένες από τις διατυπώσεις και τις ανακαλύψεις του Leibniz.

Όπως η προτασιακή λογική θεωρείται σαν μια εξέλιξη της πρώιμης συλλογιστικής λογικής έτσι και η Κατηγορηματική Λογική του Γκότλομπ Φρέγκε ήταν μια εξέλιξη από την πρώιμη προτασιακή λογική. Ένας συγγραφέας περιγράφει την κατηγορηματική Λογική σαν αντικείμενο που συνδυάζει : «τα διακριτά χαρακτηριστικά της συλλογιστικής και της προτασιακής λογικής». Όπως ήταν φυσικό η Κατηγορηματική Λογικά ανήγγειλε μια νέα περιοχή στην ιστορία της Λογικής. Τα επόμενα χρόνια καινούριες ανακαλύψεις προστέθηκαν μετά τον Γκότλομπ Φρέγκε, μερικές από τις οποίες είναι και η Φυσική απαγωγή, τα συντακτικά δέντρα και οι πίνακες αληθείας. Η φυσική απαγωγή ανακαλύφθηκε από τον Gerhard Gentzen και Jan Łukasiewicz. Τα δέντρα αληθείας ανακαλύφτηκαν από τον Evert Willem Beth.[5] Η ανακάλυψη των πινάκων αληθείας, όμως παραμένει ως αντικείμενο αντιπαράθεσης ως προς το πρόσωπο που την πρωτοανακάλυψε.

Ορολογία[Επεξεργασία | επεξεργασία κώδικα]

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

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

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

Η γλώσσα του προτασιακού λογισμού αποτελείται από

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

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

Οι μαθηματικοί μερικές φορές διακρίνουν προτασιακές σταθερές, προτασιακές μεταβλητές και σχήματα.Οι προτασιακές σταθερές αντιπροσωπεύουν κάποια συγκεκριμένη πρόταση, ενώ οι προτασιακές μεταβλητές κυμαίνονται πάνω από το σύνολο όλων των ατομικών προτάσεων. Τα σχήματα, ωστόσο, κυμαίνονται πάνω από όλες τις προτάσεις. Είναι κοινό να εκπροσωπούνται οι προτασιακές σταθερές από τα Α, Β, και Γ, οι προτασιακές μεταβλητές από τα P, Q, και R, και τα σχηματικά γράμματα είναι συχνά ελληνικά γράμματα, τις περισσότερες φορές φ, ψ και χ.

Βασικές έννοιες[Επεξεργασία | επεξεργασία κώδικα]

Στη συνέχεια παρουσιάζεται συνοπτικά ένα πρότυπο προτασιακού λογισμού. Πολλά διαφορετικά σκευάσματα υπάρχουν τα οποία είναι όλα περισσότερο ή λιγότερο ισοδύναμα, αλλά διαφέρουν στις λεπτομέρειες τους:

1. η γλώσσα τους, που είναι, η συγκεκριμένη συλλογή των πρωτόγονων συμβόλων και των συμβόλων φορέα,

2. το σύνολο των αξιωμάτων, ή διακεκριμένων τύπων, και

3. το σύνολο των κανόνων συμπερασμάτων.

Οποιαδήποτε δεδομένη πρόταση μπορεί να εκπροσωπείται με ένα γράμμα που ονομάζεται «προτασιακή σταθερά», αναλόγως ώστε να αντιπροσωπεύει μια σειρά από γράμματα στα μαθηματικά, για παράδειγμα, a = 5. Όλες οι προτάσεις που απαιτούν ακριβώς μία από τις δύο τιμές αλήθειας: αληθής ή ψευδής. Για παράδειγμα, έστω ότι P είναι η πρόταση που βρέχει έξω. Τότε θα ισχύει (P) αν βρέχει έξω και ψευδείς διαφορετικά (-P).

Στην συνέχεια ορίζουμε την αληθή-λειτουργική φράση, ξεκινώντας με την άρνηση. (-P αντιπροσωπεύει την άρνηση της Ρ, η οποία μπορεί να θεωρηθεί ως άρνηση της P. Στο παραπάνω παράδειγμα, (-P εκφράζει ότι δεν βρέχει έξω, ή από μια πιο τυπική ανάγνωση: «Δεν είναι αλήθεια ότι βρέχει έξω ."Όταν το P είναι αληθές, η -P είναι ψευδής, και όταν P είναι ψευδές, -P είναι αληθές . --P έχει πάντα την ίδια αξία αλήθειας όπως το P.
Σύζευξη είναι ένα αλήθες-λειτουργικό συνδετικό που σχηματίζει μια πρόταση από δύο απλούστερες προτάσεις, για παράδειγμα, Ρ και Q. Ο συνδυασμός των Ρ και Q είναι γραμμένο P ∧ Q, και εκφράζει ότι το καθένα είναι αλήθεια. Διαβάζουμε P ∧ Q για "P και Q". Για οποιεσδήποτε δύο προτάσεις, υπάρχουν τέσσερις πιθανές αναθέσεις τιμών αλήθειας:

1. P είναι αληθής και η Q είναι αληθής

2. P είναι αληθής και η Q είναι ψευδής

3. P είναι ψευδής και η Q είναι αληθής

4. P είναι ψευδής και Q είναι ψευδής

Η σύζευξη των Ρ και Q είναι αληθές στην περίπτωση 1 και είναι ψευδής διαφορετικά. Όπου P είναι η πρόταση που βρέχει έξω και Q είναι η πρόταση ότι υπάρχει ένα κρύο-μέτωπο πάνω από το Κάνσας, P ∧ Q είναι αληθής όταν βρέχει έξω και υπάρχει ένα κρύο-μέτωπο πάνω από το Κάνσας. Αν δεν βρέχει έξω, τότε P ∧ Q είναι ψευδές και αν δεν υπάρχει κρύο-μέτωπο πάνω από το Κάνσας, τότε P ∧ Q είναι ψευδές.

Η Διάζευξη σαν έννοια μοιάζει με τον συνδυασμό από το γεγονός ότι αποτελεί μια πρόταση από δύο απλούστερες προτάσεις. Γράφουμε P ∨Q, και διαβάζεται "P ή Q". Εκφράζει ότι είτε Ρ ή Q είναι αληθής. Έτσι,στις περιπτώσεις που αναφέρονται παραπάνω, η αποσύνδεση των P και Q είναι αληθής σε όλες τις περιπτώσεις εκτός από την 4. Χρησιμοποιώντας το παραπάνω παράδειγμα, ο διαχωρισμός εκφράζει ότι είτε βρέχει έξω ή υπάρχει ένα ψυχρό μέτωπο πάνω από το Κάνσας. (Σημείωση, αυτή η χρήση της διάζευξης υποτίθεται ότι μοιάζει με τη χρήση της αγγλικής λέξης "ή".Ωστόσο, μοιάζει περισσότερο σαν το αγγλικό «περιλαμβάνων»"ή", το οποίο μπορεί να χρησιμοποιηθεί για να εκφράσει την αλήθεια τουλάχιστον για μία από τις δύο προτάσεις. Δεν είναι σαν το αγγλικό «αποκλειστικό» "ή",που εκφράζει την αλήθεια για ακριβώς μία από τις δύο προτάσεις. Δηλαδή, το «αποκλειστικό»"ή" είναι ψευδές όταν και οι δύο P και Q είναι αληθείς (περίπτωση 1).Ένα παράδειγμα του «αποκλειστικού» ή είναι: Μπορεί να έχετε ένα κουλούρι ή ένα γλυκό, αλλά όχι τα δύο. Συνήθως σε φυσική γλώσσα, δεδομένου του κατάλληλου πλαισίου, η φράση "αλλά όχι και τα δύο" παραλείπεται, αλλά υπονοείται.Στα μαθηματικά, ωστόσο,το διαζευκτικό "ή" ισχύει πάντα χωρίς αποκλεισμούς.. ή και αν είναι «αποκλειστικό» ή,εννοείται ότι θα πρέπει να καθορίζεται, ενδεχομένως με "XOR")
Η Εξάρτηση υλικού ενώνει επίσης δύο απλούστερες προτάσεις, και γράφουμε P → Q, το οποίο διαβάζεται «αν P τότε Q". Η πρόταση αριστερά του βέλους ονομάζεται προηγηθείσα και η πρόταση προς τα δεξιά ονομάζεται επακόλουθη. (Δεν υπάρχει τέτοια ονομασία συνδυασμού ή διάζευξης,δεδομένου ότι είναι αντιμεταθετικές πράξεις.) Εκφράζει ότι το Q είναι αληθής όταν το p είναι αληθές. Έτσι, είναι αλήθεια σε κάθε περίπτωση παραπάνω, εκτός από την περίπτωση 2, διότι αυτή είναι η μόνη περίπτωση όπου το P είναι αλήθεια,αλλά το Q δεν είναι. Χρησιμοποιώντας το παράδειγμα, εάν ισχύει το Ρ τότε ισχύει και το Q εκφράζει ότι αν βρέχει έξω τότε υπάρχει ένα κρύο-μέτωπο πάνω Κάνσας.Η εξάρτηση υλικού συχνά συγχέεται με τη φυσική αιτία. Το υλικό υπό όρους, όμως, αφορά μόνο δύο προτάσεις από την αξία της αλήθειας τους και δεν είναι η σχέση αιτίου και αποτελέσματος. Είναι αμφιλεγόμενο στη βιβλιογραφία αν το υλικό της επίπτωσης αντιπροσωπεύει τη λογική της αιτιώδους συνάφειας.
Η διπλή εξάρτηση ενώνει δύο απλούστερες προτάσεις, και γράφουμε P ↔ Q, που διαβάζεται "P αν και μόνο αν Q". Εκφράζει ότι P και Q έχουν την ίδια αξία αλήθειας, έτσι το P ισχύει αν και μόνο αν το Q είναι αληθές στις περιπτώσεις 1 και 4, και ψευδείς διαφορετικά.

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

Το κλείσιμο στο πλαίσιο των πράξεων[Επεξεργασία | επεξεργασία κώδικα]

Η προτασιακή λογική είναι κλειστή ως προς τους συνδέσμους της συνάρτησης αληθείας. Δηλαδή, για κάθε πρόταση φ, η ¬φ έιναι επίσης μια πρόταση. Ομοίως, για τυχόν προτάσεις φ και ψ,η φ ∧ ψ είναι μια πρόταση, και ομοίως για διάζευξη, για υπόθεση και για ισοδυναμία. Αυτό σημαίνει , για παράδειγμα, ότι η φ ∧ ψ όντας μια πρόταση, μπορεί να είναι συνδεθεί με μια άλλη πρόταση. Για να το παραστήσουμε αυτό, πρέπει να χρησιμοποιήσουμε παρενθέσεις για να δείξουμε ποια πρόταση είναι συνδεδεμένη με ποια. Για παράδειγμα,η πρόταση P ∧ Q ∧ R δεν είναι μια καλά σχηματισμένη φόρμουλα, γιατί δεν ξέρουμε αν είναι συνένωση της P ∧ Q με την R ή αν είναι συνένωση της P με την Q ∧ R. Έτσι πρέπει να γράψουμε είτε (P ∧ Q ) ∧ R, για να εκπροσωπεί την πρώτη, ή P ∧ (Q ∧ R) για να εκπροσωπεί την τελευταία αντίστοιχα. Με την αξιολόγηση των συνθηκών αλήθειας, βλέπουμε ότι και οι δύο εκφράσεις έχουν τις ίδιες προϋποθέσεις αλήθειας (θα ισχύουν στις ίδιες περιπτώσεις), και, επιπλέον, ότι οποιαδήποτε πρόταση που σχηματίζεται από αυθαίρετους συνδέσμους θα έχουν τις ίδιες προϋποθέσεις αλήθειας, ανεξάρτητα από τη θέση των παρενθέσεων. Αυτό σημαίνει ότι η σχέση είναι προσεταιριστική, ωστόσο, δεν θα πρέπει να υποθέσουμε ότι παρενθέσεις δεν εξυπηρετούν ποτέ ένα σκοπό. Για παράδειγμα, η πρόταση P ∧ (Q ∨ R) δεν έχει τις ίδιες προϋποθέσεις αλήθειας με την πρόταση (P ∧ Q) ∨ R, έτσι είναι διαφορετικές προτάσεις που διακρίνονται μόνο από τις παρενθέσεις.Αυτό μπορεί να ελεγθεί με τη μέθοδο του πίνακα αλήθειας που αναφέρεται παραπάνω.

Σημείωση: Για κάθε αυθαίρετο αριθμό προτασιακών σταθερών, μπορούμε να σχηματίσουμε ένα πεπερασμένο αριθμό περιπτώσεων στις οποίες παρατίθενται οι πιθανές τιμές αλήθειας τους. Ένας απλός τρόπος για να το δημιουργήσουμε αυτό, είναι οι πίνακες αλήθειας, στους οποίους πρώτα γράφουμε τα P, Q, ..., Z, για οποιαδήποτε λίστα k προτασιακών σταθερών-δηλαδή, οποιαδήποτε λίστα προτασιακών σταθερών με καταχωρήσεις k και έπειτα γράφουμε 2k σειρές, και κάτω από το P συμπληρώνουμε το πρώτο μισό των σειρών με αληθές (ή Τ) και το δεύτερο μισό με ψευδή (ή F). Κάτω από το Q συμπληρώνουμε το ένα τέταρτο των σειρών με Τ, το επόμενο τέταρτο με F, το επόμενο τέταρτο με το Τ και το τελευταίο τέταρτο με F. Η επόμενη στήλη εναλάσσεται μεταξύ αληθούς και ψευδούς σε κάθε όγδοη σειρά, στη συνέχεια στην δέκατη έκτη, και ούτω καθεξής, μέχρι την τελευταία προτασιακή σταθερά μεταβάλλεται μεταξύ Τ και F σε κάθε γραμμή. Αυτό θα δώσει μια πλήρη λίστα των περιπτώσεων ή αλλιώς τις πιθανές αναθέσεις τιμών αλήθειας για αυτές τις προτασιακές σταθερές.

Επιχείρημα[Επεξεργασία | επεξεργασία κώδικα]

Ο προτασιακός λογισμός ορίζει στη συνέχεια ένα επιχείρημα ως ενα ένα σύνολο προτάσεων. Ένα έγκυρο επιχείρημα είναι ένα σύνολο προτάσεων, η τελευταία εκ των οποίων προκύπτει -ή υπονοείται- από τα υπόλοιπα. Όλα τα άλλα επιχειρήματα δεν ειναι έγκυρα. Το απλούστερο έγκυρο επιχείρημα είναι τα modus ponens, ένα παράδειγμα των οποίων είναι το ακόλουθο σύνολο προτάσεων:

{\begin{array}{rl}1.&P\to Q\\2.&P\\\hline \therefore &Q\end{array}}

Αυτό είναι ένα σύνολο τριών προτάσεων, όπου κάθε γραμμή είναι μια πρόταση, και η τελευταία πρόταση προκύπτει από τις υπόλοιπες. Οι δύο πρώτες γραμμές ονομάζονται προκείμενες προτάσεις, και η τελευταία: συμπέρασμα. Λέμε ότι μια πρόταση $C$ προκύπτει από οποιοδήποτε σύνολο των προτάσεων $(P_{1},...,P_{n})$ ,αν το $C$ είναι αλήθεια όποτε είναι αλήθεια και το κάθε μέλος από το σύνολο $(P_{1},...,P_{n})$ .Στο παραπάνω επιχείρημα, για κάθε $P$ και $Q$ , όποτε $P \to Q$ και $P$ είναι αλήθεια, αναγκαστικά ειναι και το $Q$ αλήθεια. Παρατηρήστε ότι, όταν το $P$ είναι αλήθεια, δεν μπορούμε να θεωρήσουμε τις περιπτώσεις 3 και 4 (από τον πίνακα αλήθειας). Όταν $P \to Q$ είναι αλήθεια, δεν μπορούμε να θεωρήσουμε την περίπτωση 2. Αυτό αφήνει μόνο την περίπτωση 1, στην οποία $Q$ είναι επίσης αλήθεια. Έτσι το $Q$ υπονοείται από τις προκείμενες προτάσεις.

Αυτό μπορεί να γενικευτεί με την βοήθεια ενός σχήματος. Έτσι, όπου $φ$ και $ψ$ μπορεί να είναι οποιεσδήποτε προτάσεις,

{\begin{array}{rl}1.&\varphi \to \psi \\2.&\varphi \\\hline \therefore &\psi \end{array}}

Υπάρχουν και άλλες μορφές επιχείρηματος που είναι κατάλληλες, αλλά δεν είναι απαραίτητες. Λαμβάνοντας υπόψη ένα πλήρες σύνολο αξιωμάτων (βλέπε παρακάτω για ένα τέτοιο σύνολο),το modus ponens αρκεί για να αποδείξει όλες τις άλλες μορφές επιχείρηματος στην προτασιακή λογική,και έτσι αυτές να θεωρούνται ως παράγωγα. Αξίζει να σημειωθεί, οτι αυτό δεν μπορεί να εφαρμόζεται γενικά ως επέκταση της προτασιακής λογικής και σε άλλες λογικές, όπως για παράδειγμα στην [λογική [πρώτης τάξης]]. Η λογική πρώτης τάξης απαιτεί τουλάχιστον ένα επιπλέον κανόνα εξαγωγής συμπερασμάτων για να επιτευχθεί η πληρότητα.

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

. μπορύμε να ορίσουμε ένα σύστημα διεξαγωγής $Γ$ το οποίο είναι το σύνολο όλων των προτάσεων που απορρέουν από το $A$ .

Επανάληψη πάντα υποτίθεται, έτσι $P\lor Q,\neg Q\land R,(P\lor Q)\to R\in \Gamma$ . Επίσης, από το πρώτο στοιχείο του $A$ , το τελευταίο στοιχείο, καθώς και το modus ponens, το $R$ είναι μια συνέπεια, και έτσι το $R\in \Gamma$ . Επειδή δεν έχουμε διατυπώσει αρκετά και πλήρη αξιώματα,δεν μπορεί δεν μπορεί να συναχθεί κάτι αλλο. Έτσι, παρόλο που τα περισσότερα συστήματα απαγωγής που συναντάμε στην προτασιακή λογική συναγάγουν συνήθως ( $(P\lor Q)\leftrightarrow (\neg P\to Q)$ ,, το συγκεκριμένο είναι πάρα πολύ αδύναμο για να αποδείξει μια τέτοια πρόταση.

Γενική περιγραφή του Προτασιακού Λογισμού[Επεξεργασία | επεξεργασία κώδικα]

Ο Προτασιακός λογισμός είναι ένα σύστημα $L$ = $L$ ( $\mathrm {A}$ , $\mathrm {Z}$ , $\Omega$ , $\mathrm {I}$ ) όπου :

Το σύνολο Α είναι ένα πεπερασμένο σύνολο στοιχείων που ονομάζονται σύμβολα πρόταση ή προτασιακές μεταβλητές . Συντακτικά μιλώντας , αυτά είναι τα πιο βασικά στοιχεία της επίσημης γλώσσας { L } , αλλιώς αναφέρεται ως ατομικός τύπος ή ακραία στοιχεία. Στα παραδείγματα που ακολουθούν, τα στοιχεία του Α είναι συνήθως τα γράμματα p , q , r, και ούτω καθεξής.
Το σύνολο ωμέγα Ω είναι ένα πεπερασμένο σύνολο στοιχείων που ονομάζονται σύμβολα φορέα ή λογικοί σύνδεσμοι . Το σύνολο Ω είναι χωρισμένο σε ξένα μεταξύ τους υποσύνολα ως εξής :

           $\Omega$  =  $\Omega$ ₀ $\cup$  $\Omega$ ₁..... $\cup$  $\Omega$ _j $\cup$ ... $\cup$  $\Omega$ _m

Το όρισμα $\Omega$ _j είναι το σύνολο των στοιχείων της κλάσης j.

Στον πιο γνωστό προτασιακό λογισμό το σύνολο Ω κατανέμεται ως εξής :

          $\Omega$ ₁ = { $\lnot$ }

          $\Omega$ ₂   $\subseteq$  { $\land$ , $\vee$ , $\to$ , $\leftrightarrow$ }

Eίναι σύνηθες να αντιμετωπίζουμε τις συνεχείς λογικές τιμές ως φορείς της μηδενικής κλάσης έτσι:

          $\Omega$ ₀ = { 0 ,1 }

Ορισμένοι συγγραφείς χρησιμοποιούν την περισπωμένη (~), ή Ν, αντί για το σύμβολο ¬ και μερικοί χρησιμοποιούν το σύμβολο (&), το πρόθεμα Κ, ή . αντί $\vee$ . Οι Συμβολισμοί ποικίλλουν ακόμη περισσότερο για το σύνολο των λογικές τιμών, με σύμβολα, όπως {ψευδές, αληθές}, {F, T}, ή όλα μπορούν να χρησιμοποιηθούν σε διάφορα περιβάλλοντα αντί για {0, 1}.

Το σύνολο $\mathrm {Z}$ είναι ένα πεπερασμένο σύνολο κανόνων μετασχηματισμού που ονομάζονται κανόνες συμπεράσματος όταν σχετίζονται με λογικές εφαρμογές.
Το σύνολο $\mathrm {I}$ είναι το πεπερασμένο σύνολο των αρχικών σημείων που ονομάζονται αξιώματα όταν λαμβάνουν λογικές ερμηνείες

Η γλώσσα του $L$ , επίσης γνωστή ως σύνολο καλά ορισμένων τύπων, που επαγωγικά ορίζεται από τους ακόλουθους κανόνες:

Βάση: Οποιοδήποτε στοιχείο του άλφα που $\mathrm {A}$ είναι ένας τύπος της $L$ .
Αν $p$ ₁, $p$ ₂.... $p$ _j τύποι και είναι στο $\Omega$ ₀ , τότε είναι ένας τύπος $L$ .
Τέλος: Τίποτα άλλο δεν είναι ένας τύπος της .

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

Από τον κανόνα 1, το p είναι ένας τύπος.
Από τον κανόνα 2, -p είναι ένας τύπος.
Από τον κανόνα 1, το q είναι ένας τύπος.
Από τον κανόνα 2 (-p V q) είναι ένας τύπος.

Παράδειγμα 1. Απλό σύστημα αξιωμάτων[Επεξεργασία | επεξεργασία κώδικα]

Έστω ${\mathcal {L}}_{1}={\mathcal {L}}(\mathrm {A} ,\Omega ,\mathrm {Z} ,\mathrm {I} )$ που ορίζεται ως εξής:

Το σύνολο Α , είναι ένα πεπερασμένο σύνολο συμβόλων το οποίο είναι αρκετά μεγάλο ώστε να μας καλύψει για τις ανάγκες μιας δοθείσας συζήτησης, για παράδειγμα:

          ::: $\mathrm {A} =\{p,q,r,s,t,u\}.$

Από τους τρεις συνδέσμους για την σύζευξη,διάζευξη και συμπέρασμα ( $\wedge ,\lor$ , and $\to$ ),ένα απο αυτά μπορεί να θεωρηθεί ως αρχική και οι άλλες δύο μπορούν να οριστούν με τους όρους αυτής ακόμη και ως άρνηση( $\neg$ ).[8] Ισχύει ότι όλοι οι λογικοί σύνδεσμοι μπορούν να οριστούν και μόνο απο έναν επαρκή τελεστή. Η συνεπαγωγή μπορεί φυσικά να οριστεί σε σχέση με την σύζευξη και το συμπέρασμα,με την βοήθεια ενός $a\leftrightarrow b$ defined as $(a\to b)\land (b\to a)$ .

Το να καθιερώσουμε την άρνηση και το συμπέρασμα ως τους αρχικούς τελεστές του προτασιακού λογισμού είναι ισοδύναμο με το να έχουμε ένα σύνολο $\Omega =\Omega _{1}\cup \Omega _{2}$ που χωρίζεται ως εξής:

           :::  $\Omega _{1}=\{\lnot \},$ 
           :::  $\Omega _{2}=\{\to \}.$

Ένα αξιωματικό σύστημα που ανακαλύφτηκε απο τον Jan Łukasiewicz σχηματίζει τον προτασιακό λογισμό με την βοήθεια αυτής της γλώσσας ως εξής.Τα αξιώματα είναι όλα παραδείγματα αντικατάστασης των:

           :*  $(p\to (q\to p))$

$((p\to (q\to r))\to ((p\to q)\to (p\to r)))$

$((\neg p\to \neg q)\to (q\to p))$

Ο κανόνας του συμπεράσματος είναι το modus ponens (i.e., από το p και το(p \to q), συμπεραίνουμε το q). Τότε το \lor b ορίζεται ως \neg a \to b, και το \land b ορίζεται ως \neg(a \to \neg b).Αυτό το σύστημα χρησιμοποιείται στο Metamath set.mm formal proof database.

Παράδειγμα 2. Σύστημα φυσικής απαγωγής[Επεξεργασία | επεξεργασία κώδικα]

Έστω ${\mathcal {L}}_{2}={\mathcal {L}}(\mathrm {A} ,\Omega ,\mathrm {Z} ,\mathrm {I} )$ , όπου $\mathrm {A}$ , $\Omega$ , $\mathrm {Z}$ , $\mathrm {I}$ ορίζονται ως ακολούθως:

Το σύνολο Α $\mathrm {A}$ , είναι ένα πεπερασμένο σύνολο συμβόλων το οποίο είναι αρκετά μεγάλο όσο χρειαζόμαστε για να κάνουμε έναν διάλογο, για παράδειγμα:

$\mathrm {A} =\{p,q,r,s,t,u\}.$
Το σύνολο Ω $\Omega =\Omega _{1}\cup \Omega _{2}$ χωρίζεται ως εξής:
$\Omega _{1}=\{\lnot \},$

$\Omega _{2}=\{\land ,\lor ,\to ,\leftrightarrow \}.$

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

Το σύνολο των αρχικών σημείων είναι άδειο,δηλαδή $\mathrm {I} =\varnothing$ .

 Το σύνολο των κανόνων μετασχηματισμού, \Zeta, περιγράφεται ως εξής:

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

Για να περιγράψουμε τους κανόνες μετασχηματισμού,χρειαζόμαστε να εισάγουμε ένα σύμβολο μιας "μεταγλώσσας" $\vdash$ . Βασικά είναι ένας εύκολος τρόπος να πούμε: "συμπεραίνουμε αυτό". Ο συμβολισμός του είναι $\Gamma \vdash \psi$ , στο οποίο το Γ είναι ένα (πιθανώς άδειο) σύνολο τύπων που αποκαλείται προκείμενο, και ψ είναι ένας τύπος που ονομάζεται συμπέρασμα. Ο κανόνας μετασχηματισμού: $\Gamma \vdash \psi$ σημαίνει ότι αν κάθε πρόταση είναι και ένα θεώρημα (ή τουλάχιστον έχει την ίδια αξία αλήθειας όπως αυτή των αξιωμάτων), τότε το ψ είναι εξίσου ένα θεώρημα. Αξίζει να σημειωθεί ότι θεωρώντας τον ακόλουθο κανόνα της εισαγωγής της Σύζευξης θα μπορούμε να γνωρίζουμε αν κάποια στιγμή το Γ έχει περισσότερους από έναν τύπους, εμείς να μπορούμε να τους απλοποιήσουμε ώστε να καταλήξουμε μοναχά σε έναν χρησιμοποιώντας φυσικά την σύζευξη. Έτσι, για συντομία, από εδώ και στο εξής μπορούμε να αντικαταστήσουμε το Γ σαν εναν τύπο ανί για ένα σύνολο. Μία άλλη παράλειψη που μπορούμε να κάνουμε για να διευκολυνθούμε είναι όταν το Γ θα είναι ένα άδειο σύνολο, τότε να μην εμφανίζεται καθόλου.

Παρουσίαση της άρνησης: Από $(p\to q)$ και $(p\to \neg q)$ , συμπεραίνουμε ότι $\neg p$ .; Δηλαδή, $\{(p\to q),(p\to \neg q)\}\vdash \neg p$ .
Απαλοιφή της άρνησης: Από $\neg p$ , συμπεραίνουμε ότι $(p\to r)$ .; That is, $\{\neg p\}\vdash (p\to r)$ .
Διπλή Απαλοιφή της άρνησης: Από $\neg \neg p$ , συμπεραίνουμε ότι $p$ .; That is, $\neg \neg p\vdash p$ .
Παρουσίαση της σύζευξης: Από $p$ and $q$ , συμπεραίνουμε ότι $(p\land q)$ .; That is, $\{p,q\}\vdash (p\land q)$ .
Απαλοιφή της σύζευξης: Από $(p\land q)$ , συμπεραίνουμε ότι $p$ .; Από $(p\land q)$ , συμπεραίνουμε ότι $q$ .; That is, $(p\land q)\vdash p$ and $(p\land q)\vdash q$ .
Παρουσίαση της διάζευξης: Από $p$ , συμπεραίνουμε ότι $(p\lor q)$ .; Από $q$ , συμπεραίνουμε ότι $(p\lor q)$ .; That is, $p\vdash (p\lor q)$ and $q\vdash (p\lor q)$ .
Απαλοιφή της διάζευξης: Από $(p\lor q)$ and $(p\to r)$ and $(q\to r)$ , συμπεραίνουμε ότι $r$ .; That is, $\{p\lor q,p\to r,q\to r\}\vdash r$ .
Παρουσίαση της συνεπαγωγής: Από $(p\to q)$ and $(q\to p)$ , συμπεραίνουμε ότι $(p\leftrightarrow q)$ .; That is, $\{p\to q,q\to p\}\vdash (p\leftrightarrow q)$ .
Απαλοιφή της συνεπαγωγής: Από $(p\leftrightarrow q)$ , συμπεραίνουμε ότι $(p\to q)$ .; Από $(p\leftrightarrow q)$ , συμπεραίνουμε ότι $(q\to p)$ .; That is, $(p\leftrightarrow q)\vdash (p\to q)$ and $(p\leftrightarrow q)\vdash (q\to p)$ .
Modus ponens (Απαλοιφή με χρηση της υπόθεσης): Από $p$ and $(p\to q)$ , συμπεραίνουμε ότι $q$ .; That is, $\{p,p\to q\}\vdash q$ .
Απόδειξη με την χρήση υπόθεσης (Παρουσίαση υπόθεσης): Από [accepting $p$ allows a proof of $q$ ], συμπεραίνουμε ότι $(p\to q)$ .; That is, $(p\vdash q)\vdash (p\to q)$ .

Βασικές και Παράγωγες μορφές Επιχειρήματος[Επεξεργασία | επεξεργασία κώδικα]

Όνομα	Ακολουθία	Περιγραφή
Modus ponens	(( p → q ) Λ p ) \|– q	Αν p τότε q p Ως εκ τούτου, q
Modus tollens	(( p → q ) Λ -q ) \|– -q	Αν p τότε q οχι q Ως εκ τούτου όχι p
Υποθετικός συλλογισμός	(( p → q ) Λ ( q → r ) ) \|– ( p → r )	Αν p τότε q q αν και στη συνέχεια r Ως εκ τούτου, αν p τότε r
Διαζευκτικός συλλογισμός	(( p V q ) Λ -p ) \|– q	Είτε p ή q, ή και τα δύο Όχι p Ως εκ τούτου, q
Εποικοδομητικό δίλημμα	(( p → q ) Λ ( r → s ) Λ ( p V r )) \|– ( q V s )	Αν p τότε q και εάν r και στη συνέχεια s αλλά p ή r Ως εκ τούτου, q ή s
Καταστροφικό δίλημμα	(( p → q ) Λ ( r → s ) Λ ( -q V -s) \|– ( -p V -r)	Αν p τότε q και εάν r και στη συνέχεια s αλλά όχι q ή όχι s Ως εκ τούτου, όχι p ή όχι r
Δίλημμα διπλής κατεύθυνσης	(( p → q ) Λ ( r → s ) Λ ( p V -s ) \|– ( q V -r )	Αν p τότε q και εάν r και στη συνέχεια s αλλά p ή όχι s Ως εκ τούτου, q ή όχι r
Απλοποίηση	( p V q ) \|– p	p και q είναι αλήθεια Ως εκ τούτου, το p είναι αληθές
Σύνδεση	p,q \|– ( p Λ q )	p και q είναι αληθείς χωριστά Ως εκ τούτου, είναι αλήθεια συνδυαστικά
Πρόσθεση	p \|– ( p V q )	p είναι η αλήθεια Ως εκ τούτου, η διάζευξη (p ή q) είναι αληθής
Σύνθεση	(( p → q ) Λ ( p → r ) ) \|– ( p → ( q Λ r ))	Αν p τότε q και αν p τότε r Ως εκ τούτου, εάν το ρ είναι αλήθεια τότε q και r είναι αλήθεια
Θεώρημα De Morgan's (1)	- ( p Λ q ) → ( -p V -q )	Η άρνηση της (p και q) είναι ισοδύναμα (όχι p ή όχι q)
Θεώρημα De Morgan's (2)	- ( p V q ) → ( -p Λ -q )	Η άρνηση του (p ή q) είναι ισοδύναμα (όχι p και όχι q)
Μετατροπή (1)	( p V q ) \|– ( q V p )	(p ή q) είναι ισοδύναμα ως (q ή p)
Μετατροπή (2)	( p Λ q ) \|– ( q Λ p )	(p και q) είναι ισοδύναμα ως (q και p)
Μετατροπή (3)	( p ↔ q ) \|– ( q ↔ p )	(το ρ είναι ισοδύναμo με q) είναι ισοδύναμo με (q είναι ισοδύναμo με q)
Σύνδεσμος (1)	( p V ( q V r ) \|– (( p V q ) V r )	p ή (q ή r) είναι ισοδύναμα με (p ή q) ή r
Σύνδεσμος (2)	( p Λ ( q Λ r ) \|– (( p Λ q ) Λ r )	p και (q και r) είναι ισοδύναμα με (p και q) και r
Διανομή (1)	( p Λ ( q V r )) \|– (( p Λ q ) V ( p Λ r ))	p και (q ή r) είναι ισοδύναμα με (p και q) ή (p και r)
Διανομή (2)	( p V ( q Λ r )) \|– (( p V q ) Λ ( p V r ))	p ή (q και r) είναι ισοδύναμα με (p ή q) και (p ή r)
Διπλή άρνηση	p \|– - -p	p είναι ισοδύναμη με την άρνηση όχι p
Μεταφορά	( p → q ) \|– ( -q → -p )	Αν p τότε q είναι ισοδύναμα αν όχι τότε το q όχι p
Συνέπεια υλικού	( p → q ) \|– ( -p V q )	Αν p τότε q είναι ισοδύναμα όχι p ή q
Ισοδυναμία υλικού (1)	( p ↔ q ) \|– (( p → q ) Λ ( q → p )	(p ανν q) είναι ισοδύναμα (εάν p είναι αληθής τότε η q είναι αληθής) και (αν το q είναι αληθής τότε η p είναι αληθής)
Ισοδυναμία υλικού (2)	( p ↔ q ) \|– (( p Λ q ) V ( -p Λ -q )	(p ανν q) είναι ισοδύναμα είτε (p και q είναι αληθής) ή (αμφότερα τα p και q είναι ψευδής)
Ισοδυναμία υλικού (3)	( p ↔ q ) \|– (( p V q ) Λ ( -p V -q)	(p ανν q) είναι ισοδύναμο με, (p ή όχι q είναι αληθής) και (όχι p ή q είναι αληθής)
Εξαγωγή	( ( p Λ q ) → r ) \|– ( p → ( q → r ) )	από (εάν τα p και q είναι αληθής τότε r είναι αλήθεια) μπορούμε να αποδείξουμε (εάν q είναι αληθής τότε το r είναι αλήθεια, αν το p είναι αλήθεια)
Εισαγωγή	( p → ( q → r ) ) \|– ( ( p Λ q) → r )	Αν p τότε (εάν q τότε r) είναι ισοδύναμο με αν p και q τότε r
Ταυτολογία (1)	p \|– ( p V p)	p είναι αληθής είναι ισοδύναμo. με το p είναι αληθές ή το p είναι αληθές
Ταυτολογία (2)	p \|– ( p Λ p )	p είναι αληθής είναι ισοδύναμo με p είναι αληθές και η p είναι αληθές
Νόμος της μέσης απόκλισης	\|– ( p V -p )	p ή όχι p είναι αληθής
Νόμος της μη-αντίφασης	\|– - ( p Λ -p )	p και όχι p είναι ψευδής, είναι μια αληθινή δήλωση

Αποδείξεις στον προτασιακό λογισμό[Επεξεργασία | επεξεργασία κώδικα]

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

Στη συζήτηση που θα ακολουθήσει, μια απόδειξη παρουσιάζεται ως μια σειρά αριθμημένων γραμμών, με κάθε γραμμή να αποτελείται από ένα μόνο τύπο που ακολουθείται από ένα λόγο ή δικαιολογία εισαγωγής του τύπου αυτού. Κάθε υπόθεση του επιχειρήματος, δηλαδή, μια υπόθεση που εισάγεται ως μια υπόθεση του επιχειρήματος, αναφέρεται στην αρχή της σειράς και χαρακτηρίζεται ως "προϋπόθεση" αντί άλλων. Το συμπέρασμα είναι τοποθετημένο στην τελευταία γραμμή. Μια απόδειξη είναι πλήρης αν κάθε γραμμή προκύπτει από τα προηγούμενα με την ορθή εφαρμογή του κανόνα μετασχηματισμού. (Για μια αντίθεση προσέγγιση, βλέπε απόδειξη δέντρα).

Παράδειγμα απόδειξης[Επεξεργασία | επεξεργασία κώδικα]

Για να δείξει ότι η A → A.

Μια πιθανή απόδειξη αυτού (το οποίο, αν και έγκυρο, συμβαίνει να περιέχει περισσότερα βήματα από οτι είναι απαραίτητο) μπορεί να είναι διατεταγμένο ως εξής:

Αριθμός	Τύπος	Επιχείρημα
1	Α	υπόθεση
2	Α V Α	Από την (1) με εισαγωγή διάζευξης
3	(Α V A) Λ Α	Από την (1) και (2) με την εισαγωγή συνδυασμού
4	A	Από (3), με την απλοποίηση συνδυασμού
5	A \|- A	Περίληψη της (1) έως (4)
6	A \|- A --> A	Από την (5) με υποθετική απόδειξη

Να ερμηνεύσει μια |- Α ως «Υποθέτοντας Α, να συναγάγει Α". Διαβάστε |- A --> Α όπως «Αν υποθέσουμε τίποτα, σημαίνει ότι Α συνεπάγεται Α" ή "Είναι μια ταυτολογία ότι ο Α συνεπάγεται Α" ή "Είναι πάντα αλήθεια ότι Α συνεπάγεται Α".

Γραφικός λογισμός[Επεξεργασία | επεξεργασία κώδικα]

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

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

Εναλλακτικοί Λογισμοί[Επεξεργασία | επεξεργασία κώδικα]

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

Αξιώματα[Επεξεργασία | επεξεργασία κώδικα]

Ας είναι {{mvar|φ}},{{mvar|χ}} και {{mvar|ψ}} καλά ορισμένες συναρτήσεις. (Σημειώνεται ότι οι καλά ορισμένες συναρτήσεις αυτές καθ' αυτές ορίζονται από λατινικούς και όχι ελληνικούς χαρακτήρες). Τότε τα αξιώματα ορίζονται ως εξής:

Αξιώματα
Όνομα	Σχήμα	Περιγραφή
Then-1	$\phi \to (\chi \to \phi )$	Εισαγωγή της {{mvar\|χ}} στη {{mvar\|φ}}
Then-2	$(\phi \to (\chi \to \psi ))\to ((\phi \to \chi )\to (\phi \to \psi ))$	Διαμοιρασμός της {{mvar\|φ}} στην υπόθεση
And-1	$\phi \land \chi \to \phi$	Εξάληψη σύζευξης
And-2	$\phi \land \chi \to \chi$
And-3	$\phi \to (\chi \to (\phi \land \chi ))$	Εισαγωγή σύζευξης
Or-1	$\phi \to \phi \lor \chi$	Εισαγωγή διάζευξης
Or-2	$\chi \to \phi \lor \chi$
Or-3	$(\phi \to \psi )\to ((\chi \to \psi )\to (\phi \lor \chi \to \psi ))$	Εξάληψη διάζευξης
Not-1	$(\phi \to \chi )\to ((\phi \to \neg \chi )\to \neg \phi )$	Εισαγωγή άρνησης
Not-2	$\phi \to (\neg \phi \to \chi )$	Εξάληψη άρνησης
Not-3	$\phi \lor \neg \phi$	Εξαίρεση του μεσσαίου, (κλασσική λογική)
Iff-1	$(\phi \leftrightarrow \chi )\to (\phi \to \chi )$	Εξάληψη ισότητας
Iff-2	$(\phi \leftrightarrow \chi )\to (\chi \to \phi )$
Iff-3	$(\phi \to \chi )\to ((\chi \to \phi )\to (\phi \leftrightarrow \chi ))$	Εισαγωγή ισότητας

Το αξίωμα Then-2 είναι η επιμεριστική ιδιότητα της συνάρτησης που εισάγουμε ως προς την ίδια.
Τα αξιώματα And-1,2 αντιστοιχούν στην εξάληψη της σύζευξης και υπογραμμίζουν την ιδιότητα του συντελεστή σύζευξης.
Το αξίωμα And-3 είναι η εισαγωγή της άρνησης.
Τo αξιώμα Not-1 είναι γνωστό ως "reductio ad absurdum".
Το αξίωμα Not-2 επιτρέπει την αφαίρεση οποιασδήποτε σχέσης από κάποια άλλη.
To αξίωμα Not-3 καλείται αλλιώς "tertium non datur" ("a third is not given") και υποδυκνύει ότι μία συνάρτηση στον προτασιακό λογισμό μπορεί να έχει μια αληθής τιμή που προκύπτει από αληθή ή ψευδή τιμή. Στην κλασσική λογική δεν υπάρχει "τρίτη" τιμή.

Άλλοι λογισμοί[Επεξεργασία | επεξεργασία κώδικα]

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

Λογική πρώτης τάξης ( γνωστή και ως πρώτης τάξης λογική κατηγορήματος ) προκύπτει όταν οι «ατομικές προτάσεις" της προτασιακής λογικής χωρίζονται σε όρους , μεταβλητές , κατηγορήματα , και ποσοδείκτες , τηρώντας τους κανόνες της προτασιακής λογικής μαζί με κάποιους καινούριους. (Για παράδειγμα , από το " Όλα τα σκυλιά είναι θηλαστικά " μπορούμε να συμπεράνουμε « Αν ο Rover είναι ένα σκυλί τότε ο Rover είναι ένα θηλαστικό ».) Με τα εργαλεία της λογικής πρώτης τάξης είναι δυνατόν να διατυπωθεί μια σειρά από θεωρίες , είτε με ρητά αξιώματα, είτε από τους κανόνες του συμπεράσματος ,που μπορούν να αντιμετωπίζονται ως λογική λιθίασης . Η Αριθμητική είναι η πιο γνωστή από αυτές, άλλες περιλαμβάνουν τη θεωρία των συνόλων και mereology. Λογικές δεύτερης τάξης και άλλες λογικές ανώτερης τάξης είναι τυπικές επεκτάσεις της λογικής πρώτης τάξης. Έτσι, σε σύγκριση με αυτές της λογικές αναφερόμαστε στην προτασιακή λογική ως " λογική μηδενικής τάξεως".

Η Τροπική λογική προσφέρει επίσης μια ποικιλία των συμπερασμάτων που δεν μπορούν να σταματούν σε προτασιακού λογισμού. Για παράδειγμα, "κατ 'ανάγκη Χ" μπορούμε να συμπεράνουμε ότι θα ισχύει το Χ. Από Χ μπορούμε να συμπεράνουμε «Είναι πιθανό ότι Χ". Η μετάφραση μεταξύ των τρόπων μεταφοράς λογικής και αλγεβρικής λογικής δημιουργεί την κλασική και ενορατική λογική, αλλά με την εισαγωγή ενός μοναδιαίου τελεστή σε Boolean ή Heyting άλγεβρες, διαφορετικο από ενας Boolean τελεστή, ερμηνεύοντας την τροπικότητα δυνατότητα, και στην περίπτωση της Heyting άλγεβρα ένα δεύτερο φορέα για την ερμηνεία της αναγκαιότητας (στην Boolean άλγεβρα αυτή είναι περιττή αφού η αναγκαιότητα είναι η De Morgan διπλή της δυνατότητας). Ο πρώτος φορέας διατηρεί το μηδέν και τη διάζευξη, ενώ ο δεύτερος διατηρεί το 1 και τον συνδυασμό

Λογικές πολλαπλής αποτίμησης είναι αυτές που επιτρέπουν οι προτάσεις να έχουν άλλες τιμές εκτός από αλήθεια και ψέμα. (Για παράδειγμα, καμιά από τις δύο είναι "έξτρα τιμές"-η "Λογική συνέχεια" επιτρέπει σε κάθε πρόταση να έχει οποιοδήποτε από έναν άπειρο αριθμό «βαθμών αλήθειας» μεταξύ αληθινού και το ψεύτικου.) Αυτές οι λογικές συχνά απαιτούν υπολογιστικές συσκευές, αρκετά διαφορετικές από του προτασιακού λογισμού. Όταν οι τιμές σχηματίζουν μια Boolean άλγεβρα (η οποία μπορεί να έχει περισσότερες από δύο ή ακόμα και απείρως πολλές τιμές), η λογική πολλαπλής αποτίμησης γίνεται κλασική λογική. Η λογική πολλαπλής αποτίμησης είναι επομένως ανεξάρτητου ενδιαφέροντος, όταν οι τιμές δημιουργούν μια άλγεβρα που δεν είναι Boolean.

Λύτες[Επεξεργασία | επεξεργασία κώδικα]

Η εξεύρεση λύσεων σε τύπους προτασιακής λογική είναι ένα NP - πλήρες πρόβλημα . Ωστόσο, υπάρχουν πρακτικές μέθοδοι ( π.χ. , ο αλγόριθμος DPLL , 1962 – αλγόριθμος «άχυρο», 2001), που είναι πολύ γρήγορες για πολλές χρήσιμες περιπτώσεις . Πρόσφατες εργασίες έχουν επεκτείνει τους αλγόριθμους SAT να δουλεύουν με προτάσεις που περιέχουν αριθμητικές εκφράσεις - αυτές είναι οι λύτες SMT .

Αναφορές[Επεξεργασία | επεξεργασία κώδικα]

↑ Marenbon, John (2007). Medieval philosophy: an historical and philosophical introduction. Routledge. σελ. 137.

Για περισσότερες πληροφορίες[Επεξεργασία | επεξεργασία κώδικα]

Brown, Frank Markham (2003), Boolean Reasoning: The Logic of Boolean Equations, 1st edition, Kluwer Academic Publishers, Norwell, MA. 2nd edition, Dover Publications, Mineola, NY.
Chang, C.C. and Keisler, H.J. (1973), Model Theory, North-Holland, Amsterdam, Netherlands.
Kohavi, Zvi (1978), Switching and Finite Automata Theory, 1st edition, McGraw–Hill, 1970. 2nd edition, McGraw–Hill, 1978.
Korfhage, Robert R. (1974), Discrete Computational Structures, Academic Press, New York, NY.
Lambek, J. and Scott, P.J. (1986), Introduction to Higher Order Categorical Logic, Cambridge University Press, Cambridge, UK.
Mendelson, Elliot (1964), Introduction to Mathematical Logic, D. Van Nostrand Company.