Άσκηση 3η
Πότε η ένωση δύο
σχημάτων είναι επίσης ένα σχήμα; Για παράδειγμα, η
είναι ένα σχήμα
, αλλά η
δεν είναι.
Πότε είναι η τομή δύο σχημάτων επίσης ένα σχήμα; Ποια η διαφορά των δύο σχημάτων;
Λύση:
Ας υποθέσουμε ότι έχουμε δύο σχήματα Σ1 και Σ2. Βρίσκουμε για κάθε ένα από αυτά το σύνολο των συμβολοσειρών που αυτό αντιπροσωπεύει, έστω S1 και S2. Ως ένωση των δύο σχημάτων Σ1 και Σ2 θεωρούμε το σχήμα το οποίο αντιπροσωπεύει όλα τα στοιχεία της ένωσης των συνόλων S1 και S2 και μόνο αυτά. Η ένωση δύο σχημάτων υπάρχει και είναι σχήμα όταν ισχύουν τα παρακάτω:
1. Τα αρχικά σχήματα είναι ίδια.
2.
Αν δεν ισχύει το 1 και σε κάποιες θέσεις το ένα
σχήμα έχει 0 ή 1 και το άλλο έχει στις ίδιες θέσεις το αδιάφορο σύμβολο (). Βεβαίως οι υπόλοιπες θέσεις πρέπει να είναι ίδιες.
3. Αν δεν ισχύει το 1 και το 2 και σε μία και μόνο θέση το ένα σχήμα έχει 0 (ή 1) και στην ίδια θέση το άλλο σχήμα έχει 1 (ή αντίστοιχα 0). Πάλι βέβαια οι υπόλοιπες θέσεις πρέπει να είναι ίδιες.
Η περίπτωση 1 είναι προφανής. Στην περίπτωση 3 το σχήμα που αποτελεί την ένωση των δύο αρχικών σχημάτων προκύπτει εάν θέσουμε στη θέση που διαφέρουν αυτά το αδιάφορο σύμβολο και κρατήσουμε τις υπόλοιπες θέσεις ίδιες. Στην περίπτωση 2 στις θέσεις που το ένα σχήμα έχει 0 ή 1 και το άλλο έχει το αδιάφορο σύμβολο τοποθετούμε το αδιάφορο σύμβολο για να πάρουμε την ένωση των αρχικών σχημάτων.
Σημειώνουμε εδώ ότι στην περίπτωση 2 πρέπει όλα τα 0 ή 1 να τα έχει το ένα σχήμα
και όλα τα αδιάφορα σύμβολα (στις αντίστοιχες θέσεις) το άλλο. Για να το δούμε
αυτό ας θεωρήσουμε ένα απλό παράδειγμα: Ας είναι Σ1 =
0 και Σ2 = 0
. Τότε S1={00, 10},
S2 = {00, 01} και
= {00, 01, 10}. Αν θεωρούσαμε σε αυτήν την περίπτωση
ότι
= (
) τότε θα είχαμε αντιπροσωπεύσει και τη συμβολοσειρά 11, η
οποία όμως δεν υπάρχει στο σύνολο
.
Αντίστοιχα θεωρούμε και την τομή των δύο σχημάτων. Ως τομή, δηλαδή, δύο σχημάτων Σ1 και Σ2 θεωρούμε το σχήμα το οποίο αντιπροσωπεύει όλα τα στοιχεία της τομής των συνόλων S1 και S2 και μόνον αυτά.
Η τομή δύο σχημάτων υπάρχει και είναι σχήμα όταν ισχύουν τα παρακάτω:
1. Τα αρχικά σχήματα είναι ίδια.
2.
Αν δεν ισχύει το 1 και σε κάποιες θέσεις το ένα
σχήμα έχει 0 ή 1 και το άλλο έχει στις ίδιες θέσεις το αδιάφορο σύμβολο
. Βεβαίως οι υπόλοιπες θέσεις πρέπει να είναι ίδιες.
Η περίπτωση 1 είναι προφανής. Στην περίπτωση 2 στις θέσεις που το ένα σχήμα έχει 0 ή 1 και το άλλο έχει το αδιάφορο σύμβολο τοποθετούμε το 0 (ή ανάλογα το 1) στην αντίστοιχη θέση για να πάρουμε την τομή των αρχικών σχημάτων.
Να σημειώσουμε ότι δεν απαιτείται στην περίπτωση 2 όλα τα 0 ή 1 να ανήκουν στο ένα σχήμα και όλα τα αδιάφορα σύμβολα στο άλλο, όπως ήταν απαραίτητο όταν βρίσκαμε την ένωση δύο σχημάτων.
Για να δούμε τη διαφορά της ένωσης από την τομή δύο σχημάτων θα πρέπει καταρχάς για τα αρχικά σχήματα να ορίζεται τόσο η ένωση όσο και η τομή τους. Αυτό συμβαίνει όταν:
1. Τα αρχικά σχήματα είναι ίδια (περίπτωση τετριμμένη που δεν μας ενδιαφέρει ιδιαίτερα).
2. Ισχύει η περίπτωση 2 για την ένωση δύο σχημάτων (που ταυτόχρονα είναι υποπερίπτωση της περίπτωσης 2 για την τομή δύο σχημάτων).
Σε αυτήν την περίπτωση τα δύο σχήματα που αντιστοιχούν στην ένωση και την τομή των δύο αρχικών σχημάτων διαφέρουν μόνο στα σημεία όπου το ένα από τα αρχικά σχήματα είχε 0 ή 1 και το άλλο το αδιάφορο σύμβολο. Η ένωση σε αυτές τις περιπτώσεις έχει το αδιάφορο σύμβολο ενώ η τομή έχει το 0 (ή αντίστοιχα το 1).