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

Απριλίου 16, 2009

Ικανοποίηση

Κατηγορίες: Άλυτα Προβλήματα — 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 να είναι αληθές.

4 σχόλια »

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


Κανάλι RSS για τα σχόλια του άρθρου. TrackBack URI

Γράψτε ένα σχόλιο

Για να σχολιάσετε πρέπει να συνδεθείτε.

Blog στο WordPress.com.