Νόμος de Morgan (i)
[~(p∧q)] ⇔[(~p)∨(~q)]
Η άρνηση της σύζευξης δύο λογικών προτάσεων ισούται (ισοδυναμεί) με τη διάζευξη των αρνήσεών τους.
Για παράδειγμα:
- Αν είναι p : «Ο Νίκος είναι ξανθός» και q : «Ο Λεωνίδας είναι ψηλός» τότε η πρόταση ~(p∧q) : «Δεν είναι (ο Νίκος ξανθός και ο Λεωνίδας ψηλός)» είναι ίση (ισοδύναμη) με την (~p)∨(~q) : «Ο Νίκος δεν είναι ξανθός ή ο Λεωνίδας δεν είναι ψηλός»
- Αν είναι p : «Έχω χρήματα» και q : «Έχω χρόνο» τότε η ~(p∧q) : «Δεν έχω (χρήματα και χρόνο)» ισοδυναμεί με την (~p)∨(~q) : «Δεν έχω χρήματα ή δεν έχω χρόνο»
Απόδειξη
Κατασκευάζουμε τον πίνακα αλήθειας για τους διάφορους συνδυασμούς των p και q. Συμπληρώνουμε διαδοχικά τις στήλες (3), (4), (5), (6) και (7).
| (1) | (2) | (3) | (4) | (5) | (6) | (7) | (8) |
| p | q | p∧q | ~(p∧q) | ~p | ~q | (~p)∨(~q) | [~ (p∧q)] ⇔[(~p)∨(~q)] |
| α | α | α | ψ | ψ | ψ | ψ | α |
| α | ψ | ψ | α | ψ | α | α | α |
| ψ | α | ψ | α | α | ψ | α | α |
| ψ | ψ | ψ | α | α | α | α | α |
Παρατηρούμε ότι οι προτάσεις των στηλών (6) και (7) είναι ισοδύναμες άρα η πρόταση της στήλης (8) είναι ταυτολογία.
Νόμος de Morgan (ii)
[~ (p∨q)] ⇔[(~p) ∧ (~q)]
Η άρνηση της διάζευξης δύο λογικών προτάσεων ισούται (ισοδυναμεί) με τη σύζευξη των αρνήσεών τους.
Για παράδειγμα:
- Αν είναι p : «Ο Νίκος είναι ξανθός» και q : «Ο Λεωνίδας είναι ψηλός» τότε η πρόταση ~(p∨q) : «Δεν είναι (ο Νίκος ξανθός ή ο Λεωνίδας ψηλός)» είναι ίση (ισοδύναμη) με την (~p)∧(~q) : «Ο Νίκος δεν είναι ξανθός και ο Λεωνίδας δεν είναι ψηλός»
- Αν είναι p : «Έχω χρήματα» και q : «Έχω χρόνο» τότε η ~(p∨q) : «Δεν έχω (χρήματα ή χρόνο)» ισοδυναμεί με την (~p)∧(~q) : «Δεν έχω χρήματα και δεν έχω χρόνο»
Απόδειξη
Κατασκευάζουμε τον πίνακα αλήθειας για τους διάφορους συνδυασμούς των p και q. Συμπληρώνουμε διαδοχικά τις στήλες (3), (4), (5), (6) και (7).
| (1) | (2) | (3) | (4) | (5) | (6) | (7) | (8) |
| p | q | p∨q | ~(p∨q) | ~p | ~q | (~p)∧(~q) | [~ (p∨q)] ⇔[(~p)∧(~q)] |
| α | α | α | ψ | ψ | ψ | ψ | α |
| α | ψ | α | ψ | ψ | α | ψ | α |
| ψ | α | α | ψ | α | ψ | ψ | α |
| ψ | ψ | ψ | α | α | α | α | α |
Παρατηρούμε ότι οι προτάσεις των στηλών (6) και (7) είναι ισοδύναμες άρα η πρόταση της στήλης (8) είναι ταυτολογία.
Προσεταιριστικός Νόμος (Ι)
(p∧q)∧r⇔p∧(q∧r)
Απόδειξη
Κατασκευάζουμε τον πίνακα αλήθειας για τους διάφορους συνδυασμούς των p,q και r. Συμπληρώνουμε διαδοχικά τις στήλες (3), (4), (5), (6), (7) και (8)
| (1) | (2) | (3) | (4) | (5) | (6) | (7) | (8) |
| p | q | r | p∧q | (p∧q)∧r | (q∧r) | p∧(q∧r) | [(p∧q)∧r]
⇔ [p∧(q∧r)] |
| α | α | α | α | α | α | α | α |
| α | α | ψ | α | ψ | ψ | ψ | α |
| α | ψ | α | ψ | ψ | ψ | ψ | α |
| α | ψ | ψ | ψ | ψ | ψ | ψ | α |
| ψ | α | α | ψ | ψ | α | ψ | α |
| ψ | α | ψ | ψ | ψ | ψ | ψ | α |
| ψ | ψ | α | ψ | ψ | ψ | ψ | α |
| ψ | ψ | ψ | ψ | ψ | ψ | ψ | α |
Άρα ταυτολογία.
Προσεταιριστικός Νόμος (ΙΙ)
(p∨q)∨r⇔p∨(q∨r)
Απόδειξη
Κατασκευάζουμε τον πίνακα αλήθειας για τους διάφορους συνδυασμούς των p,q και r. Συμπληρώνουμε διαδοχικά τις στήλες (3), (4), (5), (6), (7) και (8)
| (1) | (2) | (3) | (4) | (5) | (6) | (7) | (8) |
| p | q | r | p∨q | (p∨q)∨r | (q∨r) | p∨(q∨r) | [(p∨q)∨r]
⇔ [p∨(q∨r)] |
| α | α | α | α | α | α | α | α |
| α | α | ψ | α | α | α | α | α |
| α | ψ | α | α | α | α | α | α |
| α | ψ | ψ | α | α | ψ | α | α |
| ψ | α | α | α | α | α | α | α |
| ψ | α | ψ | α | α | α | α | α |
| ψ | ψ | α | ψ | α | α | α | α |
| ψ | ψ | ψ | ψ | ψ | ψ | ψ | α |
Άρα ταυτολογία.
Επιμεριστικός Νόμος (Ι)
[(p∧q)∨r]⇔[(p∨r)∧(q∨r)]
Για παράδειγμα:
- Αν είναι p : «Το βράδυ θα πάμε στο θέατρο», q : «Το βράδυ θα φάμε σουβλάκια» και r : «Το βράδυ θα πάμε για χορό» τότε η πρόταση (p∧q)∨r : «(Το βράδυ θα πάμε στο θέατρο και θα φάμε σουβλάκια) ή θα πάμε για χορό» είναι ίση (ισοδύναμη) με την (p∨r)∧(q∨r) : «Το βράδυ θα πάμε στο θέατρο ή για χορό) και (θα φάμε σουβλάκια ή θα πάμε για χορό)».
- Αν είναι p : «Έχω χρήματα», q : «Έχω κέφια» και r : «Έχω χρόνο» τότε η (p∧q)∨r : «Έχω (χρήματα και κέφια) ή χρόνο» ισοδυναμεί με την (p∨r)∧(q∨r) : «Έχω (χρήματα ή χρόνο) και (κέφια ή χρόνο)»
Απόδειξη
Κατασκευάζουμε τον πίνακα αλήθειας για τους διάφορους συνδυασμούς των p,q και r. Συμπληρώνουμε διαδοχικά τις στήλες (3), (4), (5), (6), (7) και (8)
| (1) | (2) | (3) | (4) | (5) | (6) | (7) | (8) |
| p | q | r | p∧q | (p∧q)∨r | (p∨r) | (q∨r) | (p∨r)∧(q∨r) |
| α | α | α | α | α | α | α | α |
| α | α | ψ | α | α | α | α | α |
| α | ψ | α | ψ | α | α | α | α |
| α | ψ | ψ | ψ | ψ | α | ψ | ψ |
| ψ | α | α | ψ | α | α | α | α |
| ψ | α | ψ | ψ | ψ | ψ | α | ψ |
| ψ | ψ | α | ψ | α | α | α | α |
| ψ | ψ | ψ | ψ | ψ | ψ | ψ | ψ |
Παρατηρούμε στις στήλες (5) και (8) πως οι προτάσεις είναι ισοδύναμες, άρα η δοθείσα είναι ταυτολογία.
Επιμεριστικός Νόμος (ΙΙ)
[(p∨q)∧r]⇔[(p∧r)∨(q∧r)]
Για παράδειγμα:
- Αν είναι p : «Το βράδυ θα πάμε στο θέατρο», q : «Το βράδυ θα φάμε σουβλάκια» και r : «Το βράδυ θα πάμε για χορό» τότε η πρόταση (p∨q)∧r : «(Το βράδυ θα πάμε στο θέατρο ή θα φάμε σουβλάκια) και θα πάμε για χορό» είναι ίση (ισοδύναμη) με την (p∧r)∨(q∧r) : «Το βράδυ θα πάμε στο θέατρο και για χορό) ή (θα φάμε σουβλάκια και θα πάμε για χορό)».
- Αν είναι p : «Έχω χρήματα», q : «Έχω κέφια» και r : «Έχω χρόνο» τότε η (p∨q)∧r : «Έχω (χρήματα ή κέφια) και χρόνο» ισοδυναμεί με την (p∧r)∨(q∧r) : «Έχω (χρήματα και χρόνο) ή (κέφια και χρόνο)»
Απόδειξη
Κατασκευάζουμε τον πίνακα αλήθειας για τους διάφορους συνδυασμούς των p,q και r. Συμπληρώνουμε διαδοχικά τις στήλες (3), (4), (5), (6), (7) και (8)
| (1) | (2) | (3) | (4) | (5) | (6) | (7) | (8) |
| p | q | r | p∨q | (p∨q)∧r | (p∧r) | (q∧r) | (p∨r)∨(q∨r) |
| α | α | α | α | α | α | α | α |
| α | α | ψ | α | ψ | ψ | ψ | ψ |
| α | ψ | α | α | α | α | ψ | α |
| α | ψ | ψ | α | ψ | ψ | ψ | ψ |
| ψ | α | α | α | α | ψ | α | α |
| ψ | α | ψ | α | ψ | ψ | ψ | ψ |
| ψ | ψ | α | ψ | ψ | ψ | ψ | ψ |
| ψ | ψ | ψ | ψ | ψ | ψ | ψ | ψ |
Παρατηρούμε στις στήλες (5) και (8) πως οι προτάσεις είναι ισοδύναμες, άρα η δοθείσα είναι ταυτολογία.
[(p⇒q)∧(q⇒s)]⇒(p⇒s)
Αν ισχύουν οι συνεπαγωγές p⇒q και q⇒s τότε θα ισχύει και η p⇒s.
Για παράδειγμα:
Αν είναι p : «Το βιβλίο είναι ιστορικό» q : «Το βιβλίο έχει πολλές σελίδες» και s : «Το βιβλίο είναι κουραστικό» τότε αν ισχύουν πως :
- «Αν το βιβλίο είναι ιστορικό τότε έχει πολλές σελίδες.» (p⇒q) και
- «Αν το βιβλίο που έχει πολλές σελίδες είναι κουραστικό.» (q⇒s) τότε
- «Το ιστορικό βιβλίο είναι κουραστικό.» (p⇒s)
Απόδειξη
Κατασκευάζουμε τον πίνακα αλήθειας για τους διάφορους συνδυασμούς των τιμών αλήθειας των p, q και s. Συμπληρώνουμε διαδοχικά τις στήλες (4), (5) και (6). Παρατηρούμε τη στήλη (6).
| (1) | (2) | (3) | (4) | (5) | (6) | (7) | (8) |
| p | q | s | p⇒q | q⇒s | (p⇒q)∧(q⇒s) | p⇒s | [(p⇒q)∧(q⇒s)]⇒(p⇒s) |
| α | α | α | α | α | α | α | α |
| α | α | ψ | α | ψ | ψ | ⇢αδύνατο | από υπόθεση |
| α | ψ | α | ψ | α | ψ | ⇢αδύνατο | από υπόθεση |
| α | ψ | ψ | ψ | α | ψ | ⇢αδύνατο | από υπόθεση |
| ψ | α | α | α | α | α | (α) | α |
| ψ | α | ψ | α | ψ | ψ | ⇢αδύνατο | από υπόθεση |
| ψ | ψ | α | α | α | α | (α) | α |
| ψ | ψ | ψ | α | α | α | (α) | α |
Όπου η πρόταση της (6) γίνεται ψευδής, η γραμμή διαγράφεται, διότι είναι αντίθετη προς την υπόθεση. Παρατηρούμε τότε ότι στο υπόλοιπο της στήλης (7) η αντίστοιχη πρόταση είναι πάντα αληθής.
Νόμος Αναδιάταξης.
[p ⇒(q ⇒r)]⇔[q ⇒ (p ⇒r)]
Για παράδειγμα:
Αν είναι p : «Το ΑΒΓΔ είναι ρόμβος» q : «Το ΑΒΓΔ είναι ορθογώνιο» και s : «Το ΑΒΓΔ είναι τετράγωνο» τότε αν ισχύει: η p, προφανώς η συνεπαγωγή q⇒r είναι αληθής. Αν το ΑΒΓΔ είναι ρόμβος, τότε αν είναι και ορθογώνιο θα είναι τετράγωνο.
Απ’ την άλλη αν : Το ΑΒΓΔ είναι ορθογώνιο τότε αν είναι και ρόμβος θα είναι τετράγωνο.
Απόδειξη
Κατασκευάζουμε τον πίνακα αλήθειας για τους διάφορους συνδυασμούς των p,q και r. Συμπληρώνουμε διαδοχικά τις στήλες (3), (4), (5), (6), (7) και (8)
| (1) | (2) | (3) | (4) | (5) | (6) | (7) | (8) | (9) | (10) |
| p | q | r | q⇒r | p⇒(q⇒r) | p⇒r | q⇒(p⇒r) | [(p∨q)∨r] ⇔ [p∨(q∨r)] |
p∧q | (p∧q)⇒r |
| α | α | α | α | α | α | α | α | α | α |
| α | α | ψ | ψ | ψ | ψ | ψ | α | α | ψ |
| α | ψ | α | α | α | α | α | α | ψ | α |
| α | ψ | ψ | α | α | ψ | α | α | ψ | α |
| ψ | α | α | α | α | α | α | α | ψ | α |
| ψ | α | ψ | ψ | α | α | α | α | ψ | α |
| ψ | ψ | α | α | α | α | α | α | ψ | α |
| ψ | ψ | ψ | α | α | α | α | α | ψ | α |
Άρα ταυτολογία.
Αν προσθέσουμε και τις στήλες (9) και (10) και συγκρίνουμε τις στήλες (10) και (7) αντιλαμβανόμαστε και νέα επέκταση του θεωρήματος. (βλ. Νόμο εξαγωγής).
Νόμος Εξαγωγής.
[(p ∧ q) ⇒r] ⇔[p⇒(q⇒r)]
Απόδειξη
Κατασκευάζουμε τον πίνακα αλήθειας για τους διάφορους συνδυασμούς των p,q και r. Συμπληρώνουμε διαδοχικά τις στήλες (3), (4), (5), (6), (7) και (8)
| (1) | (2) | (3) | (4) | (5) | (6) | (7) | (8) |
| p | q | r | p∧q | (p∧q)⇒r | q⇒r | p⇒(q⇒r) | [(p∧q)⇒r]
⇔ [p⇒(q⇒r)] |
| α | α | α | α | α | α | α | α |
| α | α | ψ | α | ψ | ψ | ψ | α |
| α | ψ | α | ψ | α | α | α | α |
| α | ψ | ψ | ψ | α | α | α | α |
| ψ | α | α | ψ | α | α | α | α |
| ψ | α | ψ | ψ | α | ψ | α | α |
| ψ | ψ | α | ψ | α | α | α | α |
| ψ | ψ | ψ | ψ | α | α | α | α |
Άρα ταυτολογία.
Λογικές Ισοδυναμίες
Nόμος Περιγραφή
Tαυτότητας p ⇔ p
Διπλής άρνησης p⇔~(~p)
Aποκλείσεως τρίτου p∨(~ p)⇔(α)
Aντιφατικότητας ~(p∧~p)⇔(α)
De Morgan ~(p∧q)⇔~p∨~q
~(p∨q)⇔~p∧~q
Aντιμεταθετικότητας p∧q⇔q∧p
p∨q⇔q∨p
Προσεταιριστικότητας (p∧q)∧r⇔p∧(q∧r)
(p∨q)∨r⇔p∨(q∨r)
Aντιθετικός (p⇒q)⇔(~q ⇒~p)
Eπιμεριστικός p∧(q∨r)⇔(p∧q)∨(p∧r)
p∨(q∧r)⇔(p∨q)∧(p∨r)
Aναδιάταξης [p ⇒(q →r)]⇔[q ⇒(p ⇒r)]
Eξαγωγής [(p∧q)⇒r]⇔[p⇒(q⇒r)]