Επόμενη: Το Θεώρημα του Herbrand Πάνω Επίπεδο: Λογική Πρώτης Τάξης Προηγούμενη: Ερμηνείες και Μοντέλα

3.3 Κανονικές Μορφές

Υπάρχουν τύποι οι οποίοι, αν και φαινομενικά διαφορετικοί, είναι στην ουσία λογικά ισοδύναμοι. Για παράδειγμα, οι τύποι και είναι ισοδύναμοι, παρά την διαφορετική τους ``μορφή''. Είναι προφανές ότι θα ήταν βολική η δυνατότητα αναγωγής ενός τύπου σε μια περιορισμένη, ``κανονική μορφή'', ώστε να γίνονται ευκολότερα τυχόν συγκρίσεις. Μια τέτοια μορφή είναι η προσημασμένη συζευκτική κανονική μορφή (prenex conjunctive normal form), στην οποία οποιοσδήποτε τύπος μπορεί ν' αναχθεί. Τα βασικά δομικά στοιχεία της μορφής αυτής είναι τα λεκτικά στοιχεία (literals), τα οποία με τη σειρά τους συγκροτούν τις προτάσεις (clauses). 'Ενα λεκτικό στοιχείο είναι ένα άτομο ή η άρνηση ενός ατόμου. Μια πρόταση είναι μια πεπερασμένη διάζευξη (disjunction) κανενός ή περισσοτέρων λεκτικών στοιχείων. Για παράδειγμα, είναι μια πρόταση, αφού είναι διάζευξη τριών λεκτικών στοιχείων. Η διάζευξη μηδέν στο πλήθος λεκτικών στοιχείων ονομάζεται κενή πρόταση (empty clause) και συμβολίζεται .

Η γενική μορφή ενός τύπου σε προσημασμένη συζευκτική κανονική μορφή είναι:

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

είναι σε προσημασμένη συζευκτική κανονική μορφή.

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

'Ενας τύπος σε προσημασμένη διαζευκτική κανονική μορφή μπορεί να γραφεί ως μια διάζευξη καθολικά ποσοτικοποιημένων (universally quantified) προτάσεων, αφού πρώτα απαλείψουμε τους υπαρξιακούς ποσοδείκτες μέσω μιας διαδικασίας που ονομάζεται skolemization. Λέμε τότε, ότι ο τύπος μας είναι σε τυπική μορφή skolem (skolem standard form) ή, απλά, σε τυπική μορφή.

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

• Καθολικά ποσοτικοποιημένη διάζευξη λεκτικών στοιχείων:
  
  
  
• Διάζευξη λεκτικών στοιχείων χωρίς την αναγραφή των καθολικών ποσοδεικτών, για λόγους απλότητας:
  
  
  
• Σύνολο λεκτικών στοιχείων:
  
  
• Συνεπαγωγή. 'Εστω μια πρόταση με
  
  δηλαδή τα πρώτα ι λεκτικά στοιχεία της είναι αρνητικά (negative) και τα υπόλοιπα θετικά (positive). Η πρόταση αυτή είναι ισοδύναμη με τον τύπο
  
  Αν η πρόταση περιέχει μόνο θετικά λεκτικά στοιχεία, το σύμβολο συνήθως παραλείπεται. Αν υπάρχουν μόνο αρνητικά λεκτικά στοιχεία, γράφουμε
  
  Μια πρόταση σε μορφή συνεπαγωγής (implication notation) μπορεί να γραφεί και στις επόμενες μορφές:
  • 
  • , όπου τα κόμματα στ' αριστερά αντικαθιστούν το `', ενώ στα δεξιά αντικαθιστούν το `'
  •