Προβλήματα και Γρίφοι Μαθηματικών

Ενα blog για τα Μαθηματικά

Posts Tagged ‘Ασκήσεις Μαθηματικής Λογικής

Γραφήματα και χρώματα

leave a comment »

Έστω G ένα άπειρο γράφημα και n \in \mathbb{N}^{*}, αποδείξτε ότι αν κάθε πεπερασμένο υπογράφημα του G βάφεται με n χρώματα τότε και το G βάφεται με n χρώματα.

Advertisements

Written by Κιουβρέκης Γιάννης / Kiouvrekis Yiannis

Οκτώβριος 5, 2011 at 11:14 μμ

Ένας Γκεντελιανός Γρίφος.

with one comment

Υποθέτουμε ότι υπάρχει μια μηχανή η οποία τυπωνει καποιες εκφρασεις οι οποιες αποτελουνται απο τα παρακατω συμβολα

\sim, \ T, \ N \ (, \ )

Με τον ορο εκφραση εννοουμε καθε πεπερασμενη και μη κενη ακολουθια απο τα 5 συμβολα αυτα. Μια εκφραση ονομαζεται τυπώσιμη αν μπορει η μηχανη μας να την τυπωσει. Επισης υποθετουμε οτι αν μια εκφραση ειναι τυπώσιμητοτε η μηχανη θα την τυπωσει στο μελλον καποια στιγμη.Με τον όρο νόρμα μιας έκφρασης X εννοούμε την έκφραση X(X) και την συμβολίζουμε με N(X), με τον όρο πρόταση εννοούμε μια έκφραση της μορφής:

  1. T(X)
  2. TN(X)
  3. \sim T(X)
  4. \sim TN(X)

To νόημα που δίνουμε στις προτάσεις είναι το προφανές, το T σημαίνει τυπώσιμη, το N η νόρμα της και το \sim για το όχι. Ορίζουμε:

  • Η πρόταση T(X) είναι αληθής αν και μόνο αν η έκφραση X είναι τυπώσιμη
  • Η πρόταση TN(X) είναι αληθής αν και μόνο αν η έκφραση X(X) είναι τυπώσιμη
  • Η πρόταση \sim T(X) είναι αληθής αν και μόνο αν η έκφραση X δεν είναι τυπώσιμη
  • Η πρόταση \sim TN(X) είναι αληθής αν και μόνο αν η έκφραση X(X) δεν είναι τυπώσιμη

Επίσης υποθέτουμε ότι η μηχανή δεν μας κοροϊδεύει. Δεν τυπώνει ψευδείς προτάσεις αλλά μόνο αληθείς, δηλαδή αν η μηχανή τυπώσει την πρόταση T(X) τότε η έκφραση X κάποια στιγμή θα τυπωθεί από την μηχανή. Ορίσαμε καλά το πότε μια πρόταση είναι αληθής και πότε ψευδής. Το παράδοξο είναι ότι η μηχανή μας είναι μια αυτοαναφορική μηχανή, μπορεί να μιλάει για τον εαυτό της π.χ. οι εκφράσεις T(X) , \ \sim TN(X).

Ερώτηση: Μπορείτε να βρείτε μια πρόταση η οποία είναι αληθής άλλα δεν μπορεί να τυπωθεί;

Written by Κιουβρέκης Γιάννης / Kiouvrekis Yiannis

Απρίλιος 15, 2011 at 12:32 πμ