Θεωρία Γραφημάτων 7

#1

Ο Ανδρέας έχει $n \geqslant 2$ προτάσεις $P_1,\ldots,P_n$ για τις οποίες θέλει να αποδείξει πως είναι όλες ισοδύναμες μεταξύ τους. Αυτό θα το κάνει αποδεικνύοντας προτάσεις του τύπου $P_i \Rightarrow P_j$ .

Εννοείται πως αν αποδείξει πως $P_i \Rightarrow P_j$ και $P_j \Rightarrow P_k$ τότε δεν χρειάζεται να δουλέψει περισσότερο για να αποδείξει ότι $P_i \Rightarrow P_k$ αφού έπεται άμεσα από τους κανόνες της λογικής.

Ποιος είναι ο μικρότερος αριθμός αποδείξεων που πρέπει να κάνει; (Κάθε $P_i \Rightarrow P_j$ μετράει σαν μία απόδειξη.)

asxetos · #2

Demetres έγραψε:Ο Ανδρέας έχει $n \geqslant 2$ προτάσεις $P_1,\ldots,P_n$ για τις οποίες θέλει να αποδείξει πως είναι όλες ισοδύναμες μεταξύ τους. Αυτό θα το κάνει αποδεικνύοντας προτάσεις του τύπου $P_i \Rightarrow P_j$ .

Εννοείται πως αν αποδείξει πως $P_i \Rightarrow P_j$ και $P_j \Rightarrow P_k$ τότε δεν χρειάζεται να δουλέψει περισσότερο για να αποδείξει ότι $P_i \Rightarrow P_k$ αφού έπεται άμεσα από τους κανόνες της λογικής.

Ποιος είναι ο μικρότερος αριθμός αποδείξεων που πρέπει να κάνει; (Κάθε $P_i \Rightarrow P_j$ μετράει σαν μία απόδειξη.)

Νομίζω πως έχω απάντηση σε αυτή εδώ την άσκηση αλλά δεν είμαι σίγουρος.Ας την κοιτάξει κάποιος.

Θα δουλέψουμε με επαγωγή.

Προτού αυτό όμως,θα θεωρήσουμε τις προτάσεις P_i

ως σημεία στο επίπεδο,και συγκεκριμένα σημεία ενός κανονικού

γώνου ώστε να έχουμε καλύτερη εποπτεία.(Γράφημα)
Θα ενώνουμε δύο σημεία P_i,P_j

αν και μόνο αν έχουμε αποδείξει $P_i \Rightarrow P_j$ ή $P_j \Rightarrow P_i$ .
Όμως για να αποδείξουμε ότι όλες οι προτάσεις είναι ισοδύναμες πρέπει, λόγω των κανόνων λογικής, να αποδείξουμε ότι υπάρχει δρομίσκος που να διέρχεται από όλες τις κορυφές(σημεία). Επομένως αρκεί να αποδείξουμε πως το γράφημά μας είναι γράφημα Euler.Είναι γνωστό όμως ότι ικανή και αναγκαία συνθήκη για να είναι ένα γράφημα, γράφημα Euler, είναι κάθε κορυφή της να έχει άρτιο βαθμό.Ο ελάχιστος θετικός άρτιος είναι ο 2.
Συνεπώς ζητάμε τον ελάχιστο αριθμό με το οποίο μπορούμε να ενώσουμε τις κορυφές $P_i,P_{i+1}$ .Αυτό προφανώς μπορεί να γίνει με n-1

τρόπους αλλά όχι n-2

.
Πράγματι,έστω ότι έχουμε φέρει n-2

ευθύγραμμα τμήματα.Τότε $\displaystyle{\sum_{i=1}^{n} {u(P_i)}=2n-2}$ . Ωστόσο $\displaystyle{\min \sum_{i=1}^{n} {u(P_i)}=2n}$ , άτοπο.
Έτσι η απόδειξη ολοκληρώθηκε.

Ελπίζω να είναι σωστή.

#3

Υπάρχουν διάφορα προβλήματα με την απόδειξη:

- Αυτό που θες δεν είναι το γράφημα να είναι γράφημα Euler αλλά να είναι συνεκτικό. (Δηλαδή από κάθε κορυφή να μπορείς να πας σε κάθε άλλη.)

- Και έτσι όμως υπάρχει πρόβλημα με τον τρόπο που όρισες το γράφημα. Βλεποντας την ακμή μεταξύ των P_i

και

δεν ξέρουμε αν έχουμε αποδείξει το $P_i \Rightarrow P_j$ ή το $P_j \Rightarrow P_i$ . Χρειάζεται να βάλουμε κατευθύνσεις στις ακμές.

Ο τρόπος που όρισες το γράφημα είναι πιο κοντά στην άσκηση εδώ.

#4

Demetres έγραψε:Ο Ανδρέας έχει $n \geqslant 2$ προτάσεις $P_1,\ldots,P_n$ για τις οποίες θέλει να αποδείξει πως είναι όλες ισοδύναμες μεταξύ τους. Αυτό θα το κάνει αποδεικνύοντας προτάσεις του τύπου $P_i \Rightarrow P_j$ .

Εννοείται πως αν αποδείξει πως $P_i \Rightarrow P_j$ και $P_j \Rightarrow P_k$ τότε δεν χρειάζεται να δουλέψει περισσότερο για να αποδείξει ότι $P_i \Rightarrow P_k$ αφού έπεται άμεσα από τους κανόνες της λογικής.

Ποιος είναι ο μικρότερος αριθμός αποδείξεων που πρέπει να κάνει; (Κάθε $P_i \Rightarrow P_j$ μετράει σαν μία απόδειξη.)

Απάντηση:

.

Για να αποδείξουμε την P_k

, όπου $k\in \{1, \, 2, \, ... , \, n\}$ δοθείς, χρειαζόμαστε μία απόδειξη της μορφής $\displaystyle{P_{m(k)} \Rightarrow P_k}$ . Άρα χρειαζόμαστε τουλάχιστον

αποδείξεις. Όμως ο κύκλος $\displaystyle{P_1 \Rightarrow P_2 \Rightarrow \, ... \, \Rightarrow P_n \Rightarrow P_1}$ έχει ακριβώς

αποδείξεις που δείχνουν την ισοδυναμία όλων. Τελειώσαμε.

Φιλικά,

Μιχάλης.

Θεωρία Γραφημάτων 7

Θεωρία Γραφημάτων 7

Re: Θεωρία Γραφημάτων 7

Re: Θεωρία Γραφημάτων 7

Re: Θεωρία Γραφημάτων 7

Μέλη σε σύνδεση