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

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

Archive for the ‘Ασκήσεις Μαθηματικής Λογικής’ Category

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

leave a comment »

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

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 πμ

Ένα λογικό κύκλωμα.

4 Σχόλια

Ένας ηλεκρολόγος βρέθηκε σε μια πολύ περίεργη κατάσταση. Του ζητήσανε να κατασκευάσει ένα ηλεκτρονικό κύκλωμα με τρείς διακόπτες τέτοιο ώστε να έχει ρεύμα αν και μόνο αν δύο τουλάχιστον από τους διακόπτες είναι κλειστοί. Υπάρχει τέτοιο κύκλωμα;

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

Απρίλιος 28, 2010 at 9:49 μμ