ΜΑΘ101/Προτάσεις

Αρχή

Περιεχόμενα

Επόμενη Ενότητα

Λογικές Προτάσεις

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

Π.χ.

• Όλοι οι γάϊδαροι είναι γκρι.
• Τρία και τρία είναι ίσο με έξι.
• Το 4 είναι μεγαλύτερο από το 2.

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

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

Συμβολίζουμε μια πρόταση με μικρά γράμματα του λατινικού αλφαβήτου p, q, r, κλπ. ή με κεφαλαία γράμματα του αλφαβήτου Α, Β, κλπ.

Πίνακας Αληθείας

Ο πρώτος μας στόχος είναι να χρησιμοποιήσουμε μια πρόταση για να σχηματίσουμε νέες προτάσεις και στη συνέχεια να αποφασίσουμε αν αυτές είναι αληθείς ή ψευδείς.

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

• Αν η πρόταση είναι αληθής έχει την τιμή 1. Χρησιμοποιούμε το γράμμα Α για να δείξουμε ότι η p είναι αληθής.
• Αν η πρόταση είναι ψευδής έχει την τιμή 0. Χρησιμοποιούμε το γράμμα Ψ για να δείξουμε ότι η p είναι ψευδής.

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

Λογικοί Σύνδεσμοι

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

Άρνηση

Έστω μια πρόταση p, η άρνηση της p είναι μια νέα πρόταση η οποία είναι αληθής όταν η p είναι ψευδής και ψευδής όταν η p είναι αληθής. Η άρνηση συμβολίζεται με ¬p (διαβάζεται "not-p", "όχι-p").

Ο ορισμός της άρνησης κωδικοποιείται στον ακόλουθο πίνακα αληθείας:

$p$	$\lnot p$
Α	Ψ
Ψ	Α

Παράδειγμα

Έστω p η πρόταση:

"Το 7 είναι μεγαλύτερο του 2."

Η άρνηση της p τότε είναι η πρόταση:

"Το 7 δεν είναι μεγαλύτερο από το 2" (δηλαδή είτε 7 = 2 είτε 7 < 2).

Η νέα αυτή πρόταση συμβολίζεται με ¬p.

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

Εκτός από την άρνηση μπορούμε να έχουμε νέες προτάσεις με την ένωση δύο ή περισσοτέρων προτάσεων με τους παρακάτω λογικούς συνδέσμους.

Όνομα	Σύνδεσμος	Συμβολίζεται
σύζευξη	p και q	$p\land q$
διάζευξη	p ή q	$p\lor q$
συνεπαγωγή	Αν p τότε q	$p\Rightarrow q$
	p συνεπάγεται q
	p άρα q
	p ικανή συνθήκη της q
	q αναγκαία συνθήκη της p
ισοδυναμία	p αν και μόνο αν q	$p\Leftrightarrow q$
	p είναι ισοδύναμο με q
	p ανν q

Ορισμένες φορές στη βιβλιογραφία χρησιμοποιούνται επίσης τα σύμβολα $\rightarrow$ και $\leftrightarrow$, αντί των $\Rightarrow$ και $\Leftrightarrow$ αντίστοιχα. Το σύμβολο $\rightarrow$ χρησιμοποιείται και στις συναρτήσεις και για να μη δημιουργηθεί σύγχυση σε αυτό το μάθημα σε μια συνεπαγωγή θα χρησιμοποιούμε μόνο το $\Rightarrow$.

Σύζευξη

Μία λογική πρόταση $p\land q$ είναι αληθής αν και μόνο αν και οι δύο προτάσεις p και q είναι αληθείς.

Ο πίνακας αληθείας της σύζευξης είναι ο ακόλουθος:

$p$	$q$	$p\land q$
Α	Α	Α
Α	Ψ	Ψ
Ψ	Α	Ψ
Ψ	Ψ	Ψ

Παραδείγματα

Η πρόταση $(5>3)\land (2<8)$ είναι αληθής επειδή και η πρόταση $5>3$ και η πρόταση $2<8$ είναι αληθής.

(Διαβάζουμε "το 5 είναι μεγαλύτερο του 3 και το 2 ειναι μικρότερο του 8")

Η πρόταση $(5>4)\land (3>6)$ είναι ψευδής επειδή η πρόταση $5>4$ είναι αληθής, αλλά η πρόταση $3>6$ είναι ψευδής.

(Διαβάζουμε "το 5 είναι μεγαλύτερο του 4 και το 3 είναι μεγαλύτερο του 6")

Διάζευξη

Μία λογική πρόταση $p\lor q$ είναι αληθής αν και μόνο αν τουλάχιστον μία από τις προτάσεις p, q είναι αληθής.

Ο πίνακας αληθείας της διάζευξης είναι ο ακόλουθος:

$p$!style="width:25%"|$q$	$p\lor q$
Α	Α	Α
Α	Ψ	Α
Ψ	Α	Α
Ψ	Ψ	Ψ

Συνεπαγωγή

Μία λογική πρόταση $p\Rightarrow q$ είναι ψευδής αν και μόνο αν η πρόταση p είναι αληθής και η πρόταση q είναι ψευδής.

Ο πίνακας αληθείας της συνεπαγωγής είναι ο ακόλουθος:

$p$	$q$	$p\Rightarrow q$
Α	Α	Α
Α	Ψ	Ψ
Ψ	Α	A
Ψ	Ψ	A

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

Σε μια συνεπαγωγή $p\Rightarrow q$, η p ονομάζεται ικανή συνθήκη και η q αναγκαία συνθήκη.

Παραδείγματα

Η πρόταση "Αν η γη είναι τετράγωνη, τότε ο Φεντερίκο Γκαρθία Λόρκα ήταν Ισπανός ποιητής" είναι αληθής.

Αναλυτικά, οι επιμέρους προτάσεις που την αποτελούν είναι οι:

• p = η γη είναι τετράγωνη (ψευδής)
• q = ο Φεντερίκο Γκαρθία Λόρκα ήταν Ισπανός ποιητής (αληθής)

Η σύνθετη πρόταση επομένως είναι η

$p\Rightarrow q$ = Αν η γη είναι τετράγωνη, τότε ο Φεντερίκο Γκαρθία Λόρκα ήταν Ισπανός ποιητής

Είναι σημαντικό να κατανοήσετε ότι από μια ψευδή πρόταση, όπως η p, μπορούμε να εξάγουμε οποιοδήποτε συμπέρασμα, όπως την αληθή πρόταση q. Για αυτόν το λόγο ολόκληρη η πρόταση $p\Rightarrow q$ είναι αληθής.

Ισοδυναμία

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

Ο πίνακας αληθείας της ισοδυναμίας είναι ο ακόλουθος:

$p$	$q$	$p\Leftrightarrow q$
Α	Α	Α
Α	Ψ	Ψ
Ψ	Α	Ψ
Ψ	Ψ	A

Νόμοι De Morgan

Οι παρακάτω νόμοι εφαρμόζονται στην άρνηση μιας σύζευξης ή μιας διάζευξης. Ονομάζονται νόμοι De Morgan ή θεώρημα De Morgan προς τιμήν του μαθηματικού Augustus De Morgan (1806–1871) ο οποίος τους εισήγαγε την τυπική τους εκδοχή στην Προτασιακή Λογική.

Νόμοι

• $[\lnot (p\land q)]\Leftrightarrow [(\lnot p)\lor (\lnot q)]$
• $[\lnot (p\lor q)]\Leftrightarrow [(\lnot p)\land (\lnot q)]$

Απόδειξη

• $[\lnot (p\land q)]\Leftrightarrow [(\lnot p)\lor (\lnot q)]$

Χρησιμοποιούμε πίνακα αληθείας για την απόδειξη:

$p$	$q$	$p\land q$	$\lnot (p\land q)$	$\lnot p$	$\lnot q$	$(\lnot p)\lor (\lnot q)$	$[\lnot (p\land q)]\Leftrightarrow [(\lnot p)\lor (\lnot q)]$
Α	Α	Α	Ψ	Ψ	Ψ	Ψ	Α
Α	Ψ	Ψ	Α	Ψ	Α	Α	Α
Ψ	Α	Ψ	Α	Α	Ψ	Α	Α
Ψ	Ψ	Ψ	Α	Α	Α	Α	Α

• $[\lnot (p\lor q)]\Leftrightarrow [(\lnot p)\land (\lnot q)]$

Ομοίως αποδεικνύεται με πίνακα αληθείας:

$p$	$q$	$p\lor q$	$\lnot (p\lor q)$	$\lnot p$	$\lnot q$	$(\lnot p)\land (\lnot q)$	$[\lnot (p\lor q)]\Leftrightarrow [(\lnot p)\land (\lnot q)]$
Α	Α	Α	Ψ	Ψ	Ψ	Ψ	Α
Α	Ψ	Α	Ψ	Ψ	Α	Ψ	Α
Ψ	Α	Α	Ψ	Α	Ψ	Ψ	Α
Ψ	Ψ	Ψ	Α	Α	Α	Α	Α

Ταυτολογία

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

Παράδειγμα

Η πρόταση $p\lor (\lnot p)$ είναι ταυτολογία. Από τον πίνακα αληθείας αποδεικνύεται:

$p$	$\lnot p$	$p\lor (\lnot p)$
Α	Ψ	Α
Ψ	Α	A

ότι είναι πάντα αληθής, ανεξαρτήτως των τιμών που έχουν οι προτάσεις $p$ και $\lnot p$.

Αρχή

Περιεχόμενα

Επόμενη Ενότητα