Προτασιακή Λογική

Εισαγωγή στην Προτασιακή Λογική

Η προτασιακή λογική (ή προτασιακός λογισμός) είναι ο κλάδος της μαθηματικής λογικής που ασχολείται με προτάσεις και τις συνδέσεις τους. Αποτελεί τη βάση της μαθηματικής απόδειξης και της λογικής σκέψης.

Προτάσεις

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

Παραδείγματα προτάσεων:

• "Το 5 είναι πρώτος αριθμός" (Αληθής)
• "Η Αθήνα είναι πρωτεύουσα της Γαλλίας" (Ψευδής)
• "$2 + 3 = 5$" (Αληθής)

Δεν είναι προτάσεις:

• "Τι ώρα είναι;" (ερώτηση)
• "Κλείσε την πόρτα!" (προστακτική)
• "$x + 2 = 5$" (εξαρτάται από το $x$, είναι προτασιακή συνάρτηση)

Τιμές Αληθείας

Κάθε πρόταση έχει μία τιμή αληθείας:

• Α (Αληθής) ή 1 ή T (True)
• Ψ (Ψευδής) ή 0 ή F (False)

Απλές και Σύνθετες Προτάσεις

• Απλή πρόταση: δεν περιέχει λογικούς συνδέσμους
• Σύνθετη πρόταση: δημιουργείται συνδυάζοντας απλές προτάσεις με λογικούς συνδέσμους

Οι απλές προτάσεις συμβολίζονται συνήθως με πεζά γράμματα: $p$, $q$, $r$, ...

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

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

Για $n$ απλές προτάσεις, υπάρχουν $2^n$ δυνατοί συνδυασμοί τιμών αληθείας.

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

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

Παράδειγμα: $p \lor \neg p$ ("ο αριθμός είναι άρτιος ή δεν είναι άρτιος")

Αντίφαση είναι μια σύνθετη πρόταση που είναι πάντα ψευδής.

Παράδειγμα: $p \land \neg p$ ("ο αριθμός είναι άρτιος και δεν είναι άρτιος")

Ενδεχόμενη πρόταση είναι αυτή που δεν είναι ούτε ταυτολογία ούτε αντίφαση.

Λογική Ισοδυναμία

Δύο προτάσεις $p$ και $q$ είναι λογικά ισοδύναμες (συμβολίζεται $p \equiv q$ ή $p \Leftrightarrow q$) αν έχουν τις ίδιες τιμές αληθείας για όλους τους δυνατούς συνδυασμούς.

Βασικές Λογικές Ισοδυναμίες:

• Διπλή άρνηση: $\neg(\neg p) \equiv p$
• Νόμοι De Morgan:
  • $\neg(p \land q) \equiv \neg p \lor \neg q$
  • $\neg(p \lor q) \equiv \neg p \land \neg q$
• Αντιθετοαντίστροφη: $(p \Rightarrow q) \equiv (\neg q \Rightarrow \neg p)$

Συλλογιστική και Συμπερασμός

Ένα επιχείρημα αποτελείται από προκείμενες (υποθέσεις) και ένα συμπέρασμα. Το επιχείρημα είναι έγκυρο αν, όταν όλες οι προκείμενες είναι αληθείς, το συμπέρασμα είναι επίσης αληθές.

Modus Ponens:

Αν $p \Rightarrow q$ και $p$, τότε $q$.

Modus Tollens:

Αν $p \Rightarrow q$ και $\neg q$, τότε $\neg p$.