Ορισμός :  Έστω Τ Τ( Γ ). Θα λέμε ότι :

i)	η αποτίμηση ικανοποιεί την πρόταση αν και μόνον αν ( ) = Α και η αποτίμηση ικανοποιεί το Τ αν και μόνον αν η ικανοποιεί κάθε στοιχείο του Τ.
ii)	το Τ είναι ικανοποιήσιμο αν και μόνον αν υπάρχει αποτίμηση που το ικανοποιεί.
iii)	η είναι ταυτολογία αν και μόνον αν κάθε αποτίμηση ικανοποιεί την .
iv)	η είναι αντίφαση αν η    είναι ταυτολογία.
v)	το Τ ταυτολογικά συνεπάγεται την πρόταση και γράφουμε   Τ    αν κάθε αποτίμηση που ικανοποιεί το Τ ικανοποιεί και την .

Παρατηρούμε ότι αν  Τ=  τότε     ή     αν η είναι ταυτολογία. Αν το Τ δεν είναι ικανοποιήσιμο τότε   Τ    για κάθε . Στην περίπτωση που Τ = { }, γράφουμε     αντί { }  .  Tέλος αν     και      τότε γράφουμε     και λέμε ότι οι προτάσεις και είναι ταυτολογικά ισοδύναμες.

Παραδείγματα :
1) Η πρόταση    : ( ( ) ) (( )( )) είναι ταυτολογία γιατί όπως βλέπουμε από τον παρακάτω πίνακα, κάθε αποτίμηση την ικανοποιεί.


Για να είναι μια πρόταση ταυτολογία πρέπει η τελευταία στήλη του αληθοπίνακά της να αποτελείται αποκλειστικά από Α.

2) Δείξτε ότι { ₁ , ₂ } _{1 2}
( )
Έστω ότι { ₁ , ₂ } και μια τυχαία αποτίμηση.
Αν ( ₁ ) = Α και ( ₂ ) = Α τότε και ( ) = Α και άρα ( _{1 2} ) = A.
Αν είτε ( ₁ ) = Ψ ή ( ₂ ) = Ψ τότε ( _{1 2} ) = Ψ και άρα ( _{1 2} ) = Α.
Επομένως αν { ₁ , ₂ } έχουμε ( _{1 2} ) = Α για κάθε αποτίμηση , δηλαδή _{1 2} .
( )
Έστω ότι _{1 2} , και μια τυχαία αποτίμηση που ικανοποιεί το { ₁ , ₂ } δηλαδή
( ₁ ) = ( ₂ ) = Α. Τότε όμως ( ) = Α γιατί ( _{1 2} ) = Α.
Άρα { ₁ , ₂ } , γιατί κάθε αποτίμηση που ικανοποιεί το { ₁ , ₂ } ικανοποιεί και τη .

Aσκήσεις
1) Είναι η πρόταση ( ) ( ( ) ) ταυτολογία ;
Απάντηση

2)Τρείς ύποπτοι συλλαμβάνονται για κάποιο έγκλημα.

O Α λέει : " Ο Β το έκανε. Ο C είναι αθώος. "

O B λέει : " Aν ο Α είναι ένοχος τότε και ο C είναι ένοχος. "

O C λέει : " Δεν το έκανα εγώ. Κάποιος από τους άλλους το έκανε. "

Είναι οι παραπάνω καταθέσεις στοιχεία ικανοποιησίμου συνόλου ; Υποθέτοντας ότι όλοι είναι αθώοι ποιός λέει ψέμματα ; Υποθέτοντας ότι η κατάθεση που είπε ο καθένας είναι αληθής, ποιός είναι αθώος και ποιός ένοχος ;
Απάντηση
Πρώτα πρέπει να τυποποιήσουμε τις καταθέσεις των τριών υπόπτων.
Θέτουμε

p : o Α είναι αθώος

q : o Β είναι αθώος και

r : o C είναι αθώος

O Α λοιπόν κατέθεσε	:   q r
O B κατέθεσε	:   p r
O C κατέθεσε	:   r (p q )

Θα πρέπει να μελετήσουμε το σύνολο { q r , p r , r (p q ) }.
Κατασκευάζουμε τον πίνακα αλήθειας για το σύνολο αυτό.


Βλέπουμε λοιπόν στην τρίτη γραμμή του παραπάνω αληθοπίνακα, υπάρχει αποτίμηση ( συγκεκριμένα ( p ) = A , ( q ) = Ψ και ( r ) = Α ) που κάνει όλες τις καταθέσεις αληθείς.
Άρα το σύνολο { q r , p r , r (p q ) } είναι ικανοποιήσιμο.
Αν υποθέσουμε ότι όλοι είναι αθώοι βρισκόμαστε στην πρώτη γραμμή του αληθοπίνακα, όπου ( p ) = ( q ) = ( r ) = Α και άρα ψέμματα λένε ο Α και ο C. Υποθέτοντας ότι όλες οι καταθέσεις είναι αληθείς, από την τρίτη γραμμή πάλι του αληθοπίνακα, βλέπουμε ότι ο Β είναι ένοχος.

3) Αν

p   :     Η ομάδα Α θα κερδίσει τουλάχιστον έναν τίτλο q   :     Η ομάδα B θα κερδίσει τουλάχιστον έναν τίτλο r   :     Η ομάδα C θα κερδίσει τουλάχιστον έναν τίτλο s   :     Η Α έχει πολλούς τραυματισμένους παίκτες t   :     Ο καλύτερος παίκτης της Β έχει αποβληθεί u   :     Βρέχει κατά την διάρκεια των αγώνων

γράψτε συμβολικά στη γλώσσα Γ τις παρακάτω προτάσεις :

i)	Ακριβώς μια ομάδα θα κερδίσει έναν τίτλο.
ii)	Το πολύ δύο από τις ομάδες θα κερδίσουν τίτλους.
iii)	Εφ' όσον δεν βρέξει κατά την διάρκεια των αγώνων, και ο καλύτερος παίκτης της Β δεν έχει αποβληθεί, η Β θα κερδίσει έναν τίτλο αν κάποια από τις Α ή C κερδίσει έναν τίτλο.
iv)	Αν η Α έχει πολλούς τραυματισμένους παίκτες, θα κερδίσει έναν τίτλο μόνο αν καμμιά από τις άλλες ομάδες δεν κερδίσει και δεν βρέχει κατά την διάρκεια των αγώνων.

Απάντηση

4) Δείξτε ότι _{1 2 1} ( ₂ )
Απάντηση

5) Είναι { p q , q r } p r ;
Απάντηση

6) Ποιά από τις δύο προτάσεις  p₁ ( p₂ p₃ )  και ( p₁ p₂ p₃ ) ( p₁ p₂ p₃ )ταυτολογικά συνεπάγεται την άλλη ;
Απάντηση

7) Είναι οι προτάσεις ( ) και ταυτολογικά ισοδύναμες ;
Απάντηση :
Κατασκευάζουμε έναν πίνακα αλήθειας με τις δύο προτάσεις. Είναι πράγματι ταυτολογικά ισοδύναμες γιατί σε κάθε αποτίμηση έχουν την ίδια αληθοτιμή, δηλαδή έχουν τον ίδιο πίνακα αλήθειας.

8) Είναι το σύνολο { p q , q r , r ( q p ) , p r q } ικανοποιήσιμο ;
Απάντηση

Οι πιό γνωστές ταυτολογίες είναι :

( ) ( )
( ) [ ( ) ( ) ]
( ) ( ) ( ) ( ) ( ) ( )	} Κανόνες De Morgan
( )	διπλή άρνηση
( σ ) ( ) σ ( σ ) ( ) σ	} προσεταιριστικότητα των ,
	αντιμεταθετικότητα των ,
( σ ) ( ) ( σ ) ( σ ) ( ) ( σ )	} επιμεριστικότητα των , επί των , αντίστοιχα
	νόμος απόκλεισης του τρίτου
( ) ( )	νόμος της αντιθετοαντιστροφής

Προηγούμενο

Ευρετήριο

Επόμενο