1.10 Προτασιακός Λογισμός

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

$$p,q,r,p_{1},\ldots$$

Παράδειγμα 1.27   Οι εκφράσεις,

$p:$ κάθε ακέραιος αριθμός διαιρεί τα πολλαπλασιά του,
$q:$ ο Ηλιος δύει στο βορρά

είναι προτάσεις, γιατί η $p$ είναι αληθής και η $q$ είναι ψευδής.

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

αληθής (α) ή ψευδής (ψ).

Παράδειγμα 1.28   Η έκφραση:

Που πηγαίνεις;

δεν είναι πρόταση, αφού δε χαρακτηρίζεται ούτε αληθής ούτε ψευδής.

Τιμή μιάς πρότασης $p$, λέγεται η αλήθεια ή το ψεύδος της. Γράφουμε:

$$v(p)=\alpha \eta' 1 \eta' T$$

αν είναι αληθής και

$$v(p)=\psi \eta' 0 \eta' F$$

αν είναι ψευδής. Καταχρηστικά (για ευκολία μας) γράφουμε επίσης καμιά φορά $p = \alpha$ ή $\psi$ αντί να γράψουμε $v(p) = \alpha$ ή $\psi$.

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

Παράδειγμα 1.29   Θεωρούμε τις προτάσεις,

$p:$ κάνει κρύο,
$q:$ βρέχει,
$r:$ ο ήλιος λάμπει.

1. Αν συνδέσουμε τις $p$ και $q$ με την λέξη «και», δημιουργούμε την σύνθετη πρόταση
   $p\wedge{q}:$ κάνει κρύο και βρέχει,
   η οποία λέγεται σύζευξη των $p$ και $q$, συμβολίζεται $p\wedge{q}$ (διαβάζεται $p$ και $q$) και η οποία είναι αληθής μόνο αν και οι δύο προτάσεις είναι αληθείς.
2. Με την λέξη «δεν» και την πρόταση $q$, δημιουργούμε μιά νέα πρόταση
   $\sim{q}:$ δεν βρέχει,
   η οποία λέγεται άρνηση της $q$, συμβολίζεται $\sim{q}$ (διαβάζεται όχι $q$) και είναι αληθής μόνο αν η $q$ είναι ψευδής.
3. Αν συνδέσουμε τις προτάσεις $p, r$ με την λέξη «ή» τότε έχουμε την σύνθετη πρόταση
   $p\vee{r}:$ κάνει κρύο ή ο ήλιος λάμπει,
   που λέγεται διάζευξη των $p, r$, συμβολίζεται $p\vee{r}$ (διαβάζεται $p$ ή $r$) και είναι αληθής μόνο όταν αληθεύει μία τουλάχιστον απο τις προτάσεις $p$ και $r$.
4. Πολλές προτάσεις, ειδικά στα μαθηματικά, είναι της μορφής «αν $p$ τότε $q$». Τέτοιες προτάσεις με υπόθεση (η πρόταση $p$) και συμπέρασμα (η πρόταση $q$) λέγονται συνεπαγωγές και συμβολίζονται με $p\Rightarrow{q}$.
   $p\Rightarrow{q}:$ αν κάνει κρύο τότε βρέχει.
   Μία συνεπαγωγή είναι ψευδής μόνο όταν το συμπέρασμα είναι ψευδές και η υπόθεση αληθής.

Γενικά μπορούμε να δημιουργήσουμε σύνθετες προτάσεις με όποιο τρόπο θέλουμε και να τις συμβολίζουμε όπως επιθυμούμε, αρκεί να καθορίσουμε πότε είναι αληθείς ή ψευδείς. Π.χ. ορίζουμε $p\Lsh{q}$ να είναι η σύνθετη πρόταση που αληθεύει μόνο όταν αληθεύει η $p$ και την διαβάζουμε: $p$ ανεξάρτητα $q$. Κάθε τρόπος δημιουργίας νέας πρότασης από δοθείσες άλλες προτάσεις, λέγεται τελεστής. Οι βασικοί τελεστές που έχουν ενδιαφέρον και βρίσκουν εφαρμογές, είναι οι τελεστές του παραδείγματος 1.29. Οι τιμές τους ορίζονται από τους παρακάτω πίνακες, που λέγονται πίνακες αλήθειας των αντίστοιχων τελεστών.

1.10.0.1 Σύζευξη

Δύο οποιεσδήποτε προτάσεις $p, q$ μπορούν να συνδεθούν με το «και» δημιουργώντας μία σύνθετη πρόταση, που λέγεται σύζευξη των $p, q$ και συμβολίζεται με $p\wedge{q}$ (διαβάζεται $p$ και $q$ ). Η τιμή της $p\wedge{q}$ εξαρτάται από τις τιμές των $p, q$ όπως δίνεται από τον παρακάτω πίνακα (πίνακας αλήθειας της σύζευξης):

$p$	$q$	$p \wedge q$
$\alpha$	$\alpha$	$\alpha$
$\alpha$	$\psi$	$\psi$
$\psi$	$\alpha$	$\psi$
$\psi$	$\psi$	$\psi$

1.10.0.2 Διάζευξη

Γιά κάθε δύο προτάσεις $p, q$ με το διαζευτικό «ή» ορίζουμε μια νέα πρόταση που λέγεται διάζευξη των $p$ και $q$ και συμβολίζεται με $p \vee q$ (διαβάζεται $p$ ή $q$). Ο πίνακας αλήθειας της διάζευξης είναι:

$p$	$q$	$p \vee q$
$\alpha$	$\alpha$	$\alpha$
$\alpha$	$\psi$	$\alpha$
$\psi$	$\alpha$	$\alpha$
$\psi$	$\psi$	$\psi$

1.10.0.3 Άρνηση

Γιά κάθε πρόταση $p$ μπορούμε να δημιουργήσουμε την πρόταση «δεν αληθεύει η $p$» ή «όχι $p$» που λέγεται άρνηση της $p$ και συμβολίζεται με $\sim p$ . Ο πίνακας αλήθειας της άρνησης είναι:

$p$	$\sim p$
$\alpha$	$\psi$
$\psi$	$\alpha$

1.10.0.4 Συνεπαγωγή

Η συνθετη πρόταση της μορφής «αν $p$ τότε $q$», όπου $p, q$ οποιεσδήποτε προτάσεις, λέγεται συνεπαγωγή και συμβολίζεται με $p\Rightarrow q$. Η πρόταση $p$ ονομάζεται υπόθεση της συνεπαγωγής και η πρόταση $p$ ονομάζεται συμπέρασμα. Ο πίνακας αλήθειας της συνεπαγωγής είναι:

$p$	$q$	$p\Rightarrow q$
$\alpha$	$\alpha$	$\alpha$
$\alpha$	$\psi$	$\psi$
$\psi$	$\alpha$	$\alpha$
$\psi$	$\psi$	$\alpha$

Με άλλα λόγια, για να είναι αληθής μια συνπαγωγή πρέπει όποτε ισχύει η υπόθεση αναγκαστικά να ισχύει και το συμπέρασμα. Αν σε κάποια περίπτωση η υπόθεση ισχύει αλλά όχι το συμπέρασμα τότε η συνεπαγωγή θεωρείται ψευδής πρόταση. Αυτή είναι και η μόνο περίπτωση να θεωρηθεί μια συνεπαγωγή ψευδής. Ειδικότερα, αν η υπόθεση είναι ψευδής πρόταση τότε δεν έχουμε κανένα έλεγχο να κάνουμε. Σε αυτή την περίπτωση το συμπέρασμα μπορεί να είναι αληθές ή ψευδές χωρίς αυτό να επηρεάζει την αλήθεια της συνπεγαγωγής.

Παράδειγμα 1.30   Θεωρούμε τις προτάσεις:

$p:$ η Αθήνα είναι πρωτεύουσα της Γαλλίας,
$q:2+2=4$.

Ποιες είναι οι τιμές των προτάσεων

$$p\vee q, (\sim p)\wedge q, q\Rightarrow p, p\Rightarrow q;$$

1. Έχουμε $v(p\vee q)=\alpha$ διότι $q$ είναι αληθής (τρίτη γραμμή του πίνακα αληθείας της σύζευξης.
2. Επίσης $v[(\sim p)\wedge q]=\alpha$ διότι οι προτάσεις $\sim p, q$ είναι αληθείς.
3. $v(q\Rightarrow p) = \psi$ διότι η $q$ είναι αληθής και η $p$ είναι ψευδής.
4. Τέλος $v(p\Rightarrow q)=\alpha$ (τρίτη γραμμή του πίνακα αληθείας της συνεπαγωγής).

Παράδειγμα 1.31   Πολλες σύνθετες προτάσεις, ειδικά στα Μαθηματικά, είναι της μορφής «$p$ αν και μόνο αν $q$» και ονομάζονται ισοδυναμίες. Γράφουμε:

$$p\Longleftrightarrow q.$$

Τη σύνθετη πρόταση της ισοδυναμίας $p\Longleftrightarrow q$, μπορούμε να την ορίσουμε ως εξής:

$$p\Longleftrightarrow q = (p\Rightarrow q)\wedge (q\Rightarrow p)$$

Ακολουθεί ο πίνακας αληθείας της $p\Longleftrightarrow q$.

$p$	$q$	$p\Rightarrow q$	$q \Rightarrow p$	$p\Longleftrightarrow q$
$\alpha$	$\alpha$	$\alpha$	$\alpha$	$\alpha$
$\alpha$	$\psi$	$\psi$	$\alpha$	$\psi$
$\psi$	$\alpha$	$\alpha$	$\psi$	$\psi$
$\psi$	$\psi$	$\alpha$	$\alpha$	$\alpha$

Παράδειγμα 1.32   Η αποκλειστική διάζευξη δύο προτάσεων $p, q$ που συμβολίζεται $p\veebar q$, ορίζεται ως εξής:

$p$	$q$	$p\veebar q$
$\alpha$	$\alpha$	$\psi$
$\alpha$	$\psi$	$\alpha$
$\psi$	$\alpha$	$\alpha$
$\psi$	$\psi$	$\psi$

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

Άσκηση 1.32   Έστω οι προτάσεις

$p:$ αγόρασα λαχείο, $q:$ κέρδισα το λαχείο.

Περιγράψτε στην κοινή γλώσσα κάθε μια από τις παρακάτω προτάσεις:

$$\sim p, p \vee q, p \wedge q, p \Rightarrow q, \sim p \Rightarrow \sim q,\ \sim p \vee (p \wedge q).$$

Άσκηση 1.33   Παρακάτω σας δίνονται κάποιες σύνθετες προτάσεις $P, Q, \ldots$, και κάποιες απλούστερες $p, q, \ldots$. Γράψτε κάθε μια από τις σύνθετες προτάσεις χρησιμοποιώντας τις απλούστερες και λογικούς τελεστές.

Σύνθετες προτάσεις

• $P:$ Το μάθημα είναι δύσκολο και ο καθηγητής είναι απαιτητικός
• $Q:$ Για να περάσει κανείς ένα δύσκολο μάθημα πρέπει να διαβάσει
• $R:$ Αν ένα μάθημα είναι εύκολο και ο καθηγητής είναι απαιτητικός τότε για να το περάσει κανείς πρέπει να διαβάσει
• $S:$ Αν ένα μάθημα είναι δύσκολο και ο καθηγητής απαιτητικός τότε είναι αδύνατο να το περάσει κανείς.

Απλούστερες προτάσεις

• $p:$ Το μάθημα είναι δύσκολο
• $q:$ Ο καθηγητής είναι απαιτητικός
• $r:$ Περνάω το μάθημα
• $s:$ Διαβάζω το μάθημα

1.10.0.5 Ταυτολογίες και αντιφάσεις

Ορισμός 1.26   (Γενικευμμένη πρόταση) Μια γενικευμένη πρόταση είναι μια πρόταση της οποία η τιμή αληθείας εξαρτάται από άλλες προτάσεις που υπεισέρχονται στην πρώτη ως μεταβλητές.

Παράδειγμα 1.33   Αν $p, q$ είναι ονόματα προτάσεων (οποιωνδήποτε προτάσεων, αυτές είναι οι μεταβλητές μας) τότε η έκφραση

$$p \wedge q$$ (1.22)

είναι μια γενικευμένη πρόταση.

Για να αποφανθούμε αν αυτή είναι αληθής ή ψευδής θα πρέπει να γνωρίζουμε τις τιμές των $p$ και $q$, αν δηλ. αυτές οι προτάσεις είναι αληθείς ή ψευδείς. Προσέξτε ότι δε μας ενδιαφέρει το ποιες είναι οι προτάσεις $p, q$ παρά μόνο το αν αυτές είναι αληθείς ή ψευδείς, για να αποφασίσουμε την τιμή αληθείας της γενικευμένης πρότασης (1.22).

Συχνά δίνουμε ονόματα στις γενικευμένες μας προτάσεις, περίπου όπως δίνουμε ονόματα στις συναρτήσεις αριθμών. Έτσι, π.χ., θα μπορούσαμε στην πρόταση (1.22) να δώσουμε το όνομα $C(p, q)$ γράφοντας

$$C(p, q) = p \wedge q.$$

Η πρόταση $C(p, q)$ παίρνει τιμή μόλις ξέρουμε τις τιμές των παραμέτρων της $p, q$. Αν κάποιος π.χ. μας πει ότι

$p =$ ο ήλιος είναι πιο μεγάλος από τη γη,
$q =$ η γη είναι πιο μεγάλη από το φεγγάρι,

τότε μπορούμε να αποφανθούμε ότι $C(p, q) = \alpha$.

Παράδειγμα 1.34   Οι επόμενες παραστάσεις είναι γενικευμένες προτάσεις με δύο μεταβλητές:

$$f(p,q) = \sim p \vee (p\Rightarrow q),$$

$$g(p,q) = (p\Leftrightarrow q)\wedge q,$$

$$h(p,q) = f(p,q)\wedge g(p,q)$$

Ας υποθέσουμε ότι κάποιος μας λεει ότι $p = \alpha$ και $q = \psi$. Τότε έπεται ότι $f(p, q) = \psi$, $g(p, q) = \psi$ και $h(p, q) = \psi$ (βεβαιωθείτε ότι καταλαβαίνετε πώς προκύπτουν αυτά).

Γενικά ένας σίγουρος (αλλά συνήθως αργός και βαρετός) τρόπος για να βρίσκουμε την τιμή μιάς γενικευμένης πρότασης, είναι να κάνουμε τον πίνακα αληθείας της. Ο πίνακας αληθείας της $f(p,q)$ του παραδείγματος 1.34 είναι ο εξής:

$p$	$q$	$\sim p$	$p\Rightarrow q$	$\sim p \vee(p\Rightarrow q)$
$\alpha$	$\alpha$	$\psi$	$\alpha$	$\alpha$
$\alpha$	$\psi$	$\psi$	$\psi$	$\psi$
$\psi$	$\alpha$	$\alpha$	$\alpha$	$\alpha$
$\psi$	$\psi$	$\alpha$	$\alpha$	$\alpha$

Ορισμός 1.27   (Ταυτολογία. Αντίφαση.) Μια γενικευμένη πρόταση $P(p,q,\ldots)$ λέγεται ταυτολογία, αν η $P(p,q,\ldots)$ είναι αληθής για κάθε τιμή των $p, q, \ldots$. Η $P(p,q,\ldots)$ λέγεται αντίφαση αν είναι ψευδής για κάθε τιμή των $p, q, \ldots$ (διαφορετικά: η $P(p,q,\ldots)$ είναι ταυτολογία αν και μόνο αν η $\sim P(p,q,\ldots)$ είναι αντίφαση).

Ορισμός 1.28   (Ισοδύναμες προτάσεις) Λέμε ότι δύο γενικευμένες προτάσεις $P(p,q,\ldots)$, $Q(p,q,\ldots)$ με ίδιο αριθμό μεταβλητών είναι ισοδύναμες και γράφουμε

$$P(p,q,\ldots) \equiv Q(p,q,\ldots),$$

αν η γενικευμένη πρόταση

$$P(p,q,\ldots)\Leftrightarrow Q(p,q,\ldots)$$

είναι ταυτολογία, αν δηλαδή οι πίνακες αληθείας τους ταυτίζονται.

Παράδειγμα 1.35 (Τύποι De Morgan)   Θέλουμε να δείξουμε ότι οι παρακάτω σύνθετες προτάσεις είναι ταυτολογίες.

1. $\sim(p\vee q)\equiv \sim p\wedge \sim q$.
2. $\sim(p\wedge q)\equiv \sim p\vee \sim q$.

Ελέγχουμε για την πρώτη τους πίνακες αληθείας των δύο μελών της ισοδυναμίας, των προτάσεων δηλ. $\sim(p\vee q)$ και $\sim p\wedge \sim q$:

$p$	$q$	$\sim p$	$\sim q$	$p \vee q$	$\sim(p\vee q)$	$\sim p\wedge \sim q$
$\alpha$	$\alpha$	$\psi$	$\psi$	$\alpha$	$\psi$	$\psi$
$\alpha$	$\psi$	$\psi$	$\alpha$	$\alpha$	$\psi$	$\psi$
$\psi$	$\alpha$	$\alpha$	$\psi$	$\alpha$	$\psi$	$\psi$
$\psi$	$\psi$	$\alpha$	$\alpha$	$\psi$	$\alpha$	$\alpha$

Βλέπουμε ότι οι πίνακες αληθείας των $\sim(p\vee q), \sim p\wedge \sim q$ ταυτίζονται. Συνεπώς η $\sim(p\vee q)\Longleftrightarrow (\sim p \wedge \sim q)$ είναι ταυτολογία. Παρόμοια εργαζόμαστε για τη δεύτερη ισοδυναμία.

Άσκηση 1.34   Ποιες από τις παρακάτω γενικευμένες προτάσεις είναι ταυτολογίες, ποιες είναι αντιφάσεις και ποιες ούτε ταυτολογίες ούτε αντιφάσεις;

1. $p \wedge {\sim} p$
2. $p \vee {\sim} p$
3. $p \wedge {\sim} p \Rightarrow q$
4. $p\Rightarrow q$
5. $p \Rightarrow p$
6. $(p \vee q) \Rightarrow (q \vee p)$
7. $\left( p \wedge (p \Rightarrow q) \right) \Rightarrow q$
8. $((p\Rightarrow q) \wedge (q\Rightarrow r)) \Rightarrow (p \Rightarrow r)$
9. $(p \Rightarrow q) \vee (p \Rightarrow {\sim} q)$
10. $(p \Rightarrow q) \vee (q \Rightarrow p)$

Άσκηση 1.35  

Στο πρόβλημα αυτό βλέπουμε πώς υλοποιούμε διάφορους λογικούς τελεστές στη γλώσσα python. Στην python υπάρχουν ήδη ορισμένοι οι λογικοί τελεστές and, or, not οι οποίοι δρουν μεταξύ εκφράσεων που έχουν λογικές τιμές True ή False. Στο παρακάτω πρόγραμμα (τρέξτε το και προσπαθήσετε να καταλάβετε πώς δουλεύει) χρησιμοποιούμε τους ήδη υπάρχοντες αυτούς τελεστές για να ορίσουμε τους τελεστές $\Rightarrow$ (συνεπαγωγή), $\Leftrightarrow$ (ισοδυναμία) και $\veebar$ (αποκλειστική διάζευξη (xor)).

def implies(p, q):
    return q or not p

def equivalent(p, q):
    return implies(p, q) and implies(q, p)

def xor(p, q):
    return (p and not q) or (q and not p)

a = True
b = False

print "a => b is", implies(a, b)
print "b => a is", implies(b, a)
print "a <=> b is", equivalent(a, b)
print "a xor b is", xor(a, b)