Αντιθετοαντίστροφη Απόδειξη

Εισαγωγή στην Αντιθετοαντίστροφη Απόδειξη

Η αντιθετοαντίστροφη απόδειξη είναι μια μέθοδος που βασίζεται στη λογική ισοδυναμία μεταξύ μιας πρότασης και της αντιθετοαντίστροφής της. Αντί να αποδείξουμε απευθείας ότι "αν $P$ τότε $Q$", αποδεικνύουμε την ισοδύναμη πρόταση "αν όχι $Q$ τότε όχι $P$".

Λογική Βάση

Η αντιθετοαντίστροφη της πρότασης $P \Rightarrow Q$ είναι η πρόταση $\neg Q \Rightarrow \neg P$.

Θεμελιώδης Ισοδυναμία:

$$(P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P)$$

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

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

Οι στήλες $P \Rightarrow Q$ και $\neg Q \Rightarrow \neg P$ είναι ίδιες!

Δομή της Αντιθετοαντίστροφης Απόδειξης

Για να αποδείξουμε: "Αν $P$ τότε $Q$"

1. Διατυπώνουμε την αντιθετοαντίστροφη: "Αν όχι $Q$ τότε όχι $P$"
2. Υποθέτουμε ότι η $Q$ είναι ψευδής (δηλαδή ισχύει η $\neg Q$)
3. Αποδεικνύουμε ότι η $P$ είναι ψευδής (δηλαδή ισχύει η $\neg P$)
4. Συμπεραίνουμε ότι η αρχική πρόταση ισχύει

Διαφορά από Άλλες Μεθόδους

Πότε Χρησιμοποιούμε Αντιθετοαντίστροφη

Η μέθοδος είναι ιδιαίτερα χρήσιμη όταν:

• Η πρόταση $Q$ περιέχει άρνηση ή είναι πιο "θετική" στην αρνητική μορφή της
• Είναι πιο εύκολο να δουλέψουμε με την $\neg Q$ παρά με την $P$
• Η πρόταση $P$ είναι σύνθετη αλλά η $\neg P$ είναι απλούστερη
• Υπάρχουν πολλές περιπτώσεις για την $P$ αλλά λίγες για την $\neg Q$

Σημαντικές Διευκρινίσεις

Αντιθετοαντίστροφη vs Αντίστροφη

• Αρχική: $P \Rightarrow Q$
• Αντίστροφη: $Q \Rightarrow P$ (ΔΕΝ είναι ισοδύναμη με την αρχική!)
• Αντιθετοαντίστροφη: $\neg Q \Rightarrow \neg P$ (ΕΙΝΑΙ ισοδύναμη με την αρχική)

Κανόνες Άρνησης

• $\neg(\neg P) = P$ (διπλή άρνηση)
• $\neg(P \land Q) = (\neg P) \lor (\neg Q)$ (νόμος De Morgan)
• $\neg(P \lor Q) = (\neg P) \land (\neg Q)$ (νόμος De Morgan)
• $\neg(\forall x: P(x)) = \exists x: \neg P(x)$
• $\neg(\exists x: P(x)) = \forall x: \neg P(x)$