Παραδείγματα στον προτασιακό λογισμό

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

Πρώτο παράδειγμα

Θα προσπαθήσουμε να βρούμε πότε είναι αληθής αυτός ο τύπος: ϕ = (p ∧ q) ∨ ¬q. Γράφουμε στον πίνακα τις προτασιακές μεταβλητές p και q:

$$\begin{array}{cc}p& q\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Στη συνέχεια προσθέτουμε στον πίνακα το πρώτο μέρος του τύπου: (p ∧ q), την άρνηση ¬q και μετά ολόκληρο τον τύπο:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

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

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}$$

Τέλος υπολογίζουμε τις τιμές της τελευταίας στήλης. Αυτή είναι ολόκληρος ο τύπος. Με βάση τον πίνακά μας υπολογίζουμε λοιπόν τη διάζευξη «ανάμεσα στην τρίτη και στην τέταρτη στήλη». Αποτέλεσμα:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0& 1\\ 1& 0& 0& 1& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 1\end{array}$$

Δεύτερο παράδειγμα

Ίδια εκφώνηση, διαφορετικός τύπος: ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ q). Βλέπουμε ότι στον τύπο υπάρχουν οι προτασιακές μεταβλητές p και q και οι αρνήσεις τους. Πρώτα λοιπόν φτιάχνουμε έναν πίνακα με τα δύο σύμβολα και τις αρνήσεις τους:

$$\begin{array}{cccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q\\ 1& 1& 0& 0\\ 1& 0& 0& 1\\ 0& 1& 1& 0\\ 0& 0& 1& 1\end{array}$$

Στη συνέχεια προσθέτουμε τους τύπους p ∧ ¬q και ¬p ⇒ q, που πια μπορούμε να τους υπολογίσουμε εύκολα, επειδή έχουμε στον πίνακα και τις αποτιμήσεις των επιμέρους προτάσεων και των αρνήσεών τους. Ο πίνακας είναι ο εξής:

$$\begin{array}{cccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)\\ 1& 1& 0& 0& 0& 1\\ 1& 0& 0& 1& 1& 1\\ 0& 1& 1& 0& 0& 1\\ 0& 0& 1& 1& 0& 0\end{array}$$

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

$$\begin{array}{ccccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)& \varphi \\ 1& 1& 0& 0& 0& 1& 0\\ 1& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 0\\ 0& 0& 1& 1& 0& 0& 1\end{array}$$

Τρίτο παράδειγμα

Το τρίτο παράδειγμα θα είναι λίγο πιο σύνθετο, θα δοκιμάσουμε τρεις προτασιακές μεταβλητές, με τις οποίες ο υπολογισμός του πίνακα περιπλέκεται. Ο τύπος θα είναι ο εξής: ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q)).

Επειδή έχουμε τρεις προτασιακές μεταβλητές, το συνολικό πλήθος των δυνατών αποτιμήσεων θα είναι οκτώ:

$$\begin{array}{ccc}p& q& r\\ 1& 1& 1\\ 1& 1& 0\\ 1& 0& 1\\ 1& 0& 0\\ 0& 1& 1\\ 0& 1& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}$$

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

$$\begin{array}{ccccccccc}p& q& r& \mathrm{\neg }p& (p\Rightarrow q)& (\mathrm{\neg }p\vee q)& \mathrm{\neg }(p\Rightarrow q)& (r\iff (\mathrm{\neg }p\vee q))& \varphi \\ 1& 1& 1& 0& 1& 1& 0& 1& 0\\ 1& 1& 0& 0& 1& 1& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0& 0& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 0& 1& 0\\ 0& 1& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 1& 1& 1& 1& 0& 1& 0\\ 0& 0& 0& 1& 1& 1& 0& 0& 0\end{array}$$

Τέταρτο παράδειγμα

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

1. Αν πάει ο Μάρκος, τότε θα πάει και ο Ιάκωβος.
2. Στο πάρτι θα έρθει ο Πέτρος ή, αν έρθει εκεί ο Μάρκος, τότε δεν θα έρθει ο Ιάκωβος.
3. Ο Πέτρος θα έρθει αν και μόνο αν δεν έρθει ο Μάρκος ή δεν έρθει ο Ιάκωβος.

Το ερώτημα είναι αν μπορούν να έρθουν όλοι στο πάρτι. Αν όχι, ποιοι μπορούν να πάνε στο πάρτι χωρίς να παραβιαστεί κανένας κανόνας;

Πρώτα πρέπει να ξαναγράψουμε τις προηγούμενες προτάσεις με προτασιακές μεταβλητές και τύπους. Ας συμβολίσουμε λοιπόν τις προτασιακές μεταβλητές M, J και P (Μάρκος, Ιάκωβος, Πέτρος) και η καθεμία θα σημαίνει πάντα πρόταση του τύπου «ο Μάρκος θα πάει στο πάρτι». Τον πρώτο κανόνα θα μπορούσαμε να τον ξαναγράψουμε ως εξής: M ⇒ J – «αν M, τότε J», δηλαδή «αν ο Μάρκος πάει στο πάρτι, τότε ο Ιάκωβος πάει στο πάρτι».

Τον δεύτερο κανόνα θα τον ξαναγράψουμε ως εξής. Ο κανόνας αρχίζει με τη φράση «Στο πάρτι θα έρθει ο Πέτρος ή…», άρα προφανώς θα χρειαστούμε διάζευξη. Προς το παρόν γράφουμε αυτό: P ∨ … Το επόμενο μέρος της φράσης λέει: «αν έρθει εκεί ο Μάρκος, τότε δεν θα έρθει ο Ιάκωβος». Αυτό είναι συνεπαγωγή, όπου στη δεξιά πλευρά πρέπει ακόμη να χρησιμοποιήσουμε άρνηση. «δεν θα έρθει ο Ιάκωβος» = ¬J. Ολόκληρη η συνεπαγωγή θα είναι: M ⇒ ¬J. Αυτήν τη συνδέουμε με την προηγούμενη διάζευξη: P ∨ (M ⇒ ¬J).

Τον τρίτο κανόνα τον ξαναγράφουμε ως εξής: ξεκινάμε με το «Ο Πέτρος θα έρθει αν και μόνο αν». Αυτό σημαίνει ισοδυναμία: P ⇔ … Στη συνέχεια έχουμε «δεν θα έρθει ο Μάρκος ή δεν θα έρθει ο Ιάκωβος», που το ξαναγράφουμε ως εξής: ¬M ∨ ¬J. Τα συνθέτουμε: (P ⇔ (¬M ∨ ¬J)).

Τώρα βάζουμε όλους τους τύπους στον πίνακα και υπολογίζουμε τις τιμές:

$$\begin{array}{cccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))\\ 1& 1& 1& 1& 1& 0\\ 1& 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 1\\ 1& 0& 0& 0& 1& 0\\ 0& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0\end{array}$$

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

Ψάχνουμε λοιπόν τις γραμμές στις οποίες στις θέσεις που συμβολίζουν τους όρους (δηλαδή στις τρεις τελευταίες στήλες) υπάρχουν μόνο μονάδες. Μονάδα σημαίνει ότι ο όρος ικανοποιείται. Βλέπουμε ότι αυτό συμβαίνει σε δύο περιπτώσεις. Όταν πάνε ο Ιάκωβος και ο Πέτρος, αλλά όχι ο Μάρκος, και μετά όταν πάει μόνο ο Πέτρος.

Μπορείς επίσης να το υπολογίσεις προσθέτοντας στον πίνακα τον τύπο ϕ, που θα είναι η σύζευξη και των τριών όρων. Δηλαδή θα είναι: ϕ = ((M ⇒ J) ∧ (P ∨ (M ⇒ ¬J)) ∧ (P ⇔ (¬M ∨ ¬J))). Αυτό εκφράζει αυτό που θέλουμε – να ικανοποιούνται όλοι οι τύποι (όλοι οι όροι). Ο πίνακας θα είναι τότε ο εξής:

$$\begin{array}{ccccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))& \varphi \\ 1& 1& 1& 1& 1& 0& 0\\ 1& 1& 0& 1& 0& 1& 0\\ 1& 0& 1& 0& 1& 1& 0\\ 1& 0& 0& 0& 1& 0& 0\\ 0& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$

Μερικά παραδείγματα στη μέθοδο του πίνακα αλήθειας

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

Τύπος: ((a ∧ ¬b) ∨ (b ∧ (b ⇒ a))). Πίνακας:

$$\begin{array}{ccccc}a& b& (a\wedge \mathrm{\neg }b)& (b\wedge (b\Rightarrow a))& ((a\wedge \mathrm{\neg }b)\vee (b\wedge (b\Rightarrow a)))\\ 1& 1& 0& 1& 1\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}$$

Τύπος: (a ∨ ¬a) ⇔ (b ∧ ¬b). Πίνακας:

$$\begin{array}{ccccc}a& b& (a\vee \mathrm{\neg }a)& (b\wedge \mathrm{\neg }b)& ((a\vee \mathrm{\neg }a)\iff (b\wedge \mathrm{\neg }b))\\ 1& 1& 1& 0& 0\\ 1& 0& 1& 0& 0\\ 0& 1& 1& 0& 0\\ 0& 0& 1& 0& 0\end{array}$$

Τύπος: ¬(a ∨ b) ⇔ (¬b ∧ ¬a). Πίνακας:

$$\begin{array}{ccccc}a& b& \mathrm{\neg }(a\vee b)& (\mathrm{\neg }b\wedge \mathrm{\neg }a)& (\mathrm{\neg }(a\vee b)\iff (\mathrm{\neg }b\wedge \mathrm{\neg }a))\\ 1& 1& 0& 0& 1\\ 1& 0& 0& 0& 1\\ 0& 1& 0& 0& 1\\ 0& 0& 1& 1& 1\end{array}$$

Τύπος: ϕ = (¬p ⇔ (q ∧ r)) ⇒ (p ∨ ¬(p ∧ q)). Πίνακας:

$$\begin{array}{cccccccc}p& q& r& (q\wedge r)& \mathrm{\neg }(p\wedge q)& (\mathrm{\neg }p\iff (q\wedge r))& (p\vee \mathrm{\neg }(p\wedge q))& \varphi \\ 1& 1& 1& 1& 0& 0& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 0& 1& 0& 1& 1& 1& 1\\ 1& 0& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 0& 1& 0& 1& 1\\ 0& 0& 1& 0& 1& 0& 1& 1\\ 0& 0& 0& 0& 1& 0& 1& 1\end{array}$$

Τύπος: ϕ = ¬(p ⇔ ¬q) ∧ (r ⇒ ¬p) ∧ (p ∨ r). Πίνακας:

$$\begin{array}{ccccccc}p& q& r& \mathrm{\neg }(p\iff \mathrm{\neg }q)& (r\Rightarrow \mathrm{\neg }p)& (p\vee r)& \varphi \\ 1& 1& 1& 1& 0& 1& 0\\ 1& 1& 0& 1& 1& 1& 1\\ 1& 0& 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 1& 1& 0\\ 0& 1& 1& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$