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

Απρίλιος 16, 2009

Ικανοποίηση

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 10:50 μμ

Έστω k ένας φυσικός αριθμός και μια λογική έκφραση

C_1 \wedge \cdots \wedge C_n

όπου κάθε ένα από τα C_i, i=1,\ldots,n, είναι της μορφής

y_1 \vee \cdots \vee y_k

όπου κάθε y_j είναι είτε x_\nu είτε \overline{x_\nu}. Τα x_\nu, \nu=1,2,\ldots, είναι λογικές μεταβλητές, είναι δηλ. είτε αληθείς είτε ψευδείς.

Παράδειγμα μιας τέτοιας έκφρασης με k=3 είναι η

(x_1 \vee \overline{x_2} \vee x_3) \wedge (\overline{x_1} \vee x_3 \vee x_4).

Αν n<2^k δείξτε ότι η λογική έκφραση είναι ικανοποιήσιμη, μπορούμε δηλ. να αναθέσουμε τιμές (αληθής ή ψευδής) σε κάθε μια από τις λογικές μεταβλητές x_\nu ώστε κάθε ένα από τα C_j να είναι αληθές.

Advertisements

6 Σχόλια »

  1. Αρκετά σημαντική η μέθοδος επίλυσης αυτού του προβλήματος. Αν δεν μπορείτε να βρείτε τι τιμές να βάλετε στις μεταβλητές x_i, ρίξτε ένα νόμισμα…

    Μου αρέσει!

    Σχόλιο από Δημήτρης — Απρίλιος 24, 2009 @ 5:43 μμ

  2. Θα μπορούσε κάποιος να λύσει αυτό το πρόβλημα και αυτό το παλιότερο με τον ίδιο ουσιαστικά τρόπο.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Απρίλιος 24, 2009 @ 6:05 μμ

  3. Υπόδειξη:

    Επιλέξτε τις τιμές των μεταβλητών σας στην τύχη, ανεξάρτητα. Πόσα, κατά μέσο όρο, από τα C_j είναι αληθή;

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουνίου 1, 2009 @ 11:55 μμ

  4. Υπόδειξη:

    Αν είναι X το πλήθος των C_j που είναι αληθή (αφού αναθέσουμε τυχαίες τιμές στα x_\nu) τότε {\mathbb E}X = \sum_{j=1}^n {\mathbb P}(C_j = {\rm true}). Η τελευταία πιθανότητα υπολογίζεται εύκολα. Μην ξεχνάτε επίσης ότι η τυχαία μεταβλητή X παίρνει ακέραιες τιμές.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουλίου 9, 2009 @ 11:10 μμ

  5. Έστω Y = n - X το πλήθος των ψευδών C_j . Τότε
    \mathbb{P}[C_j = false] = \frac{1}{2^n} που σημαίνει
    {\mathbb E}[Y] = \frac{n}{2^k} < 1.
    Άρα υπάρχει ανάθεση τιμών στις x_{\nu} για τις οποίες Y=0 .

    Μου αρέσει!

    Σχόλιο από henk&christos — Μαρτίου 8, 2012 @ 7:47 μμ

  6. Σωστά.

    Πολλές φορές το να διαλέξουμε στην τύχη μας λύνει το πρόβλημά μας. Η δυσκολία με αυτή τη μέθοδο μετατοπίζεται (α) στο να επιλέξουμε το με ποιο τρόπο διαλέγουμε στην τύχη (η ομοιόμορφη κατανομή όπως εδώ δε λύνει πάντα το πρόβλημα) και, το σημαντικότερο, (β) στο να αποδείξουμε ότι η τυχαία μας επιλογή έχει θετική πιθανότητα να δουλέψει.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Μαρτίου 8, 2012 @ 7:58 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Blog στο WordPress.com.

Αρέσει σε %d bloggers: