Αποστολέας Θέμα: Ισχύει ή δεν ισχύει  (Αναγνώστηκε 871 φορές)

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 551
  • There can be only one...may it be AEPP.
Ισχύει ή δεν ισχύει
« στις: 12 Μάρ 2015, 12:23:03 μμ »
Επειδή δεν το ξέρω καθόλου το θέμα ρωτάω μήπως και κατανοήσω κάτι.

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

Παράδειγμα: Να γίνει αλγόριθμος ο οποίος να υπολογίζει και να εμφανίζει ένα μήνυμα σχετικά με το αν ισχύει ο ισχυρισμός πως οποιαδήποτε τριάδα αριθμών (α,β,γ) μετά από συνεχόμενες αφαιρέσεις μεταξύ των { α = α - β , γ = α - γ , β = β - γ} , προκύπτει η τριάδα (0,0,0). πχ. για την τριάδα αριθμών (α,β,γ,) = (2,3,4) θα έχουμε:

α = Α_Τ(α-β) = 1    με την τριάδα να γίνεται (1,3,4)
β = Α_Τ(β-γ) = 1    με την τριάδα να γίνεται (1,1,4)
γ = Α_Τ(α-γ) = 3    με την τριάδα να γίνεται (1,1,3)
----------------------------------------------------------------
α = Α_Τ(α-β) = 0    με την τριάδα να γίνεται (0,1,3)
β = Α_Τ(β-γ) = 2    με την τριάδα να γίνεται (0,2,3)
γ = Α_Τ(α-γ) = 3    με την τριάδα να γίνεται (0,2,3)
---------------------------------------------------------------
α = Α_Τ(α-β) = 2    με την τριάδα να γίνεται (2,2,3)
β = Α_Τ(β-γ) = 1    με την τριάδα να γίνεται (2,1,3)
γ = Α_Τ(α-γ) = 1    με την τριάδα να γίνεται (2,1,1)
---------------------------------------------------------------
α = Α_Τ(α-β) = 1    με την τριάδα να γίνεται (1,1,1)
β = Α_Τ(β-γ) = 1    με την τριάδα να γίνεται (1,0,1)
γ = Α_Τ(α-γ) = 0    με την τριάδα να γίνεται (1,0,0)
---------------------------------------------------------------
α = Α_Τ(α-β) = 1    με την τριάδα να γίνεται (1,0,0)
β = Α_Τ(β-γ) = 0    με την τριάδα να γίνεται  (1,0,0)
γ = Α_Τ(α-γ) = 0    με την τριάδα να γίνεται (1,0,1)
---------------------------------------------------------------
α = Α_Τ(α-β) = 1    με την τριάδα να γίνεται (1,0,1)
β = Α_Τ(β-γ) = 0    με την τριάδα να γίνεται (1,1,1)
γ = Α_Τ(α-γ) = 0    με την τριάδα να γίνεται (1,1,0)
---------------------------------------------------------------
 :D
και συνεχίζεται, γιατί μάλλον παραπάνω για την τριάδα αυτή έχω κάνει κάποιο λάθος.
 :P
Κανονικά έπρεπε να έχει βγεί μέχρι τώρα!!
Απ' τα τσακάλια δεν γλυτώνεις μ'ευχές ή παρακάλια
(Κ. Βάρναλης)

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2457
  • I 'm not young enough to know everything
Απ: Ισχύει ή δεν ισχύει
« Απάντηση #1 στις: 12 Μάρ 2015, 02:23:59 μμ »
Επειδή δεν το ξέρω καθόλου το θέμα ρωτάω μήπως και κατανοήσω κάτι.

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

Όχι. Αν βρεις αντιπαράδειγμα τότε αποδεικνύεις ότι η πρόταση δεν ισχύει. Αν δε βρεις αντιπαράδειγμα, τότε δεν έχεις αποδείξει τίποτα... ούτε ότι ισχύει ούτε ότι δεν ισχύει. Μπορεί να υπάρχει λύση μετά από 1 τρισεκατομύριο επαναλήψεις. Μπορεί να θέλει χιλιάδες χρόνια εκτέλεσης του αλγορίθμου μέχρι να φτάσεις στη λύση. Ποτέ δεν ξέρεις γι αυτό δεν έχεις αποδείξει τίποτα.
Ένας συνηθισμένος τρόπος για να δείχνεις ότι μια πρόταση ισχύει για όλους τους θετικούς ακεραίους είναι η επαγωγή. Η λογική της είναι η εξής: Δείχνεις ότι ισχύει για το 1 και μετά δείχνεις ότι αν ισχύει για κάποιον συγκεκριμένο ακέραιο τότε ισχύει και για τον επόμενό του. Έτσι το έχεις δείξει για όλους.