Ορισμός :
Μία συνάρτηση  f  : { Α , Ψ }^k { Α , Ψ } λέγεται συνάρτηση Boole με k μεταβλητές.
Σε κάθε συνάρτηση Boole  f με k μεταβλητές αντιστοιχεί μιά πρόταση με k προτασιακές μεταβλητές που έχει τον ίδιο πίνακα αλήθειας με την  f.
Ας δούμε πως βρίσκεται η πρόταση που αντιστοιχεί σε μια συνάρτηση Boole  f.
Έστω  f  : { Α , Ψ }³ { Α , Ψ } μια συνάρτηση Boole με μεταβλητές που ορίζεται από τον "πίνακα αλήθειας".


Για να βρούμε την που αντιστοιχεί στην f και έχει τον ίδιο πίνακα αλήθειας με την f, πρώτα προσδιορίζουμε τα στοιχεία του { Α , Ψ }³ στα οποία η f παίρνει την τιμή Α. Αυτά είναι (Α , Ψ , Ψ) , (Ψ , Α , Ψ) και (Ψ , Ψ , Α). Σε κάθε μια από αυτές τις τριάδες αντιστοιχούμε μια πρόταση στην οποία εμφανίζονται μόνο οι p₁ , p₂ , p₃ ως εξής : Αν το πρώτο στοιχείο της τριάδας είναι Α τότε παίρνουμε την p₁ , ενώ αν είναι Ψ παίρνουμε p₁. Όμοια για τα άλλα δύο στοιχεία της τριάδας και τελικά παίρνουμε την σύζευξη των τριών στοιχειωδών προτάσεων. Έτσι στην (Α , Ψ , Ψ) αντιστοιχεί η πρόταση p₁ p₂ p₃. Η διάζευξη των προτάσεων που αντιστοιχούν στις τρείς τριάδες είναι η πρόταση :( p₁p₂p₃ )( p₁p₂p₃ )( p₁p₂p₃ ) της οποίας ο πίνακας αλήθειας ταυτίζεται με της  f.
Παράδειγμα :
1) Δίνεται η συνάρτηση Boole g με τρείς μεταβλητές, που ορίζεται από τον πίνακα:


Να βρεθεί η πρόταση που έχει τον ίδιο πίνακα αλήθειας με την g.
Όπως προηγούμενα παίρνουμε τις τριάδες (Α , Α , Ψ) , (Α , Ψ , Ψ) , (Ψ , Α , Α) , (Ψ , Ψ , Ψ) και κατασκευάζουμε τις προτάσεις : p₁p₂p₃ , p₁p₂p₃ , p₁p₂p₃ , p₁p₂p₃ Η ζητούμενη πρόταση είναι ( p₁p₂p₃ )( p₁p₂p₃ )( p₁p₂p₃ )( p₁p₂p₃ )
Παρατηρούμε ότι οι προτάσεις που αντιστοιχούν σε συναρτήσεις Boole, περιέχουν μόνο τους συνδέσμους

, ,

Ορισμός :
Μια πρόταση είναι σε κανονική διαζευκτική μορφή αν είναι διάζευξη συζεύξεων προτασιακών μεταβλητών ή αρνήσεων προτασιακών μεταβλητών.
Άμεσα φαίνεται ότι κάθε πρόταση είναι ταυτολογικά ισοδύναμη με μια άλλη σε κανονική διαζευκτική μορφή. Και αυτό γιατί κάθε πρόταση μπορεί να θεωρηθεί σαν συνάρτηση Boole.
Για παράδειγμα έστω η πρόταση p₁( ( p₂p₁)p₃ ), της οποίας ο πίνακας αλήθειας είναι :

Ο πίνακας αυτός ορίζει και μια συνάρτηση Boole με τρεις μεταβλητές, Αυτή η συνάρτηση παίρνει την τιμή Α για τις τριάδες
(A , A , A) , ( A , Ψ , A) , (Ψ , A , A) , ( Ψ, A , Ψ) , (Ψ , Ψ , A) , (Ψ , Ψ , Ψ)
Άρα η πρόταση που έχει τον ίδιο πίνακα αλήθειας με αυτήν τη συνάρτηση (και επομένως και με την αρχική πρόταση ) είναι η ( p₁p₂p₃ )( p₁p₂p₃ )(p₁p₂p₃ )(p₁p₂p₃ )(p₁p₂p₃ )(p₁p₂p₃ )
Δηλαδή p₁( ( p₂p₁)p₃ ) ( p₁p₂p₃ )( p₁p₂p₃ )(p₁p₂p₃ )(p₁p₂p₃ )(p₁p₂p₃ )(p₁p₂p₃ )
Στην πρόταση p₁( ( p₂p₁)p₃ ) αντιστοιχεί και άλλη πρόταση σε κανονική διαζευκτική μορφή που είναι ταυτολογικά ισοδύναμη με αυτήν. Αυτό φαίνεται παρακάτω.
Από την γνωστή ταυτολογία ( ) ( ) έχουμε και άρα
p₁( ( p₂p₁)p₃ ) p₁ ( p₂p₁)p₃ αλλά η πρόταση p₁ ( p₂p₁)p₃ είναι σε κανονική διαζευκτική μορφή.

Ασκήσεις
1) Βρείτε μια πρόταση σε κανονική διαζευκτική μορφή που είναι ταυτολογικά ισοδύναμη με την ( p₁ ( p₂ p₃) ) Απάντηση

2) Βρείτε μια πρόταση σε κανονική διαζευκτική μορφή που είναι ταυτολογικά ισοδύναμη με την ( p₁ p₂)( p₁p₂ ) Απάντηση

Ορισμός :
Έστω Α { , , , , }. Το Α είναι ένα επαρκές σύνολο συνδέσμων αν κάθε πρόταση είναι ταυτολογικά ισοδύναμη με μια πρόταση που περιέχει μόνο συνδέσμους από το Α.
Το σύνολο { , , } είναι προφανώς επαρκές γιατί για κάθε πρόταση μπορούμε να βρούμε μια άλλη * σε κανονική διαζευκτική μορφή με *.
Επίσης το { , }είναι επαρκές. Αυτό , γιατί όπως προηγούμενα για κάθε έχουμε *.
Αν η * δεν περιέχει διαζεύξεις τότε δεν χρειάζεται να δείξουμε τίποτα. Αν περιέχει διαζεύξεις τότε για κάθε διάζευξη της * εφαρμόζουμε την ( ) και τελικά βρίσκουμε μια πρόταση που περιέχει μόνο τους συνδέσμους και .
Παράδειγμα :    Έστω η πρόταση   p₂ ( p₁p₃ ).
Έχουμε
p₂(p₁p₃ ) p₂(p₁p₃ ) (p₂( p₁p₃ ) )
( p₂ ( p₁ p₃ ) ) ( p₂p₁p₃ )
Μπορούμε επίσης να δείξουμε ότι και τα σύνολα { , } και { , } είναι επαρκή.
Για το { , } χρειάζεται να χρησιμοποιήσουμε την ισοδυναμία ( )
και για το { , } την .
Ασκήσεις
1) Βρείτε πρόταση που να περιέχει μόνο τους συνδέσμους , και να είναι ταυτολογικά ισοδύναμη με την p₁ ( p₃p₂ ) Απάντηση

2) Όμοια με την προηγούμενη άσκηση για την πρόταση p₁ ( p₂p₃ )
Απάντηση

3) Βρείτε πρόταση που να περιέχει μόνο τους συνδέσμους , και να είναι ταυτολογικά ισοδύναμη με την p₁ ( p₂p₃ ) Απάντηση

4) Όμοια με την προηγούμενη άσκηση για την πρόταση ( p₂ p₁ ) ( p₁ p₃ )
Απάντηση


Ορίζουμε δύο καινούργιους συνδέσμους , με τους παρακάτω πίνακες αλήθειας :
Ας δείξουμε ότι το σύνολο { } είναι επαρκές σύνολο συνδέσμων. Επειδή το { , } είναι επαρκές αρκεί να δείξουμε πως να μετασχηματίζουμε την άρνηση και την διάζευξη για να βρούμε μια πρόταση που να περιέχει μόνο τον σύνδεσμο .
Παρατηρούμε ότι

και

( ) ( ) ( )

Άρα το { } είναι επαρκές.
Παράδειγμα :
Ας βρούμε πρόταση που να περιέχει μόνο τον σύνδεσμο και να είναι ταυτολογικά ισοδύναμη με την p₁ p₂
Έχουμε
p₁ p₂ p₁p₂ (p₁ p₂ ) (p₁ p₂ ) ( (p₁ p₁ ) p₂ ) ( (p₁ p₁ ) p₂ )
Μπορούμε εύκολα να δούμε επίσης ότι

|   και ( | ) | ( | )

και επειδή το σύνολο { , } είναι επαρκές και το σύνολο { | } είναι επίσης επαρκές.

Άσκηση :
Έστω ότι θέλουμε να βρούμε πρόταση που να περιέχει μόνο τον σύνδεσμο | και να είναι ταυτολογικά ισοδύναμη με την ( p₁ p₂ ) p₃. Απάντηση

Προηγούμενο

Ευρετήριο