Δυαδικές σχέσεις. Σχέση ισοδυναμίας, σύνολο πηλίκου

Θεωρία συνόλων. ΒΑΣΙΚΕΣ ΕΝΝΟΙΕΣ

Η θεωρία συνόλων είναι ο θεμελιώδης ορισμός των σύγχρονων μαθηματικών. Δημιουργήθηκε από τον Georg Cantor τη δεκαετία του 1860. Έγραψε: «Το πολλαπλάσιο είναι πολλά, το οποίο συλλαμβάνεται ως ένα ενιαίο σύνολο». Η έννοια του συνόλου είναι μια από τις βασικές, απροσδιόριστες έννοιες των μαθηματικών. Δεν μπορεί να περιοριστεί σε άλλες, πιο απλές έννοιες. Επομένως, δεν μπορεί να οριστεί, αλλά μπορεί μόνο να εξηγηθεί. Έτσι, ένα σύνολο είναι μια ενοποίηση σε ένα σύνολο αντικειμένων που διακρίνονται σαφώς από τη διαίσθησή μας ή τη σκέψη μας. μια συλλογή ορισμένων αντικειμένων που ορίζονται από ένα κοινό χαρακτηριστικό.

Για παράδειγμα,

1. Πολλοί κάτοικοι του Voronezh

2. Σύνολο σημείων στο επίπεδο

3. Σύνολο φυσικών αριθμών ℕ κ.λπ.

Τα σύνολα συνήθως συμβολίζονται με κεφαλαία λατινικά γράμματα ( Α, Β, Γκαι τα λοιπά.). Τα αντικείμενα που αποτελούν ένα δεδομένο σύνολο ονομάζονται στοιχεία του. Τα στοιχεία ενός συνόλου συμβολίζονται με μικρά λατινικά γράμματα ( α, β, γκαι τα λοιπά.). Αν Χ– ρυθμίστε και στη συνέχεια καταγράψτε x∈Xσημαίνει ότι Χείναι στοιχείο του συνόλου Χή τι Χανήκει σε πολλούς Χ, και την καταχώρηση x∉Xαυτό το στοιχείο Χδεν ανήκει στο σύνολο Χ. Για παράδειγμα, έστω ℕ το σύνολο των φυσικών αριθμών. Επειτα 5 ℕ , ΕΝΑ 0,5∉ℕ .

Αν το σετ Υαποτελείται από στοιχεία του συνόλου Χ, μετά το λένε αυτό Υείναι υποσύνολο του συνόλου Χκαι δηλώνουν Y⊂Х(ή Y⊆Х). Για παράδειγμα, ένα σύνολο ακεραίων ℤ είναι ένα υποσύνολο ρητών αριθμών ℚ .

Αν για δύο σετ ΧΚαι Υδύο εγκλείσματα συμβαίνουν ταυτόχρονα Χ ΥΚαι Υ Χ, δηλ. Χείναι υποσύνολο του συνόλου ΥΚαι Υείναι υποσύνολο του συνόλου Χ, μετά τα σετ ΧΚαι Υαποτελούνται από τα ίδια στοιχεία. Τέτοια σετ ΧΚαι Υονομάζονται ίσοι και γράφουν: X=Y.

Ο όρος κενό σύνολο χρησιμοποιείται συχνά - Ø - ένα σύνολο που δεν περιέχει ούτε ένα στοιχείο. Είναι υποσύνολο οποιουδήποτε συνόλου.

Οι ακόλουθες μέθοδοι μπορούν να χρησιμοποιηθούν για την περιγραφή συνόλων.

Μέθοδοι καθορισμού συνόλων

1. Αριθμός αντικειμένων. Χρησιμοποιείται μόνο για πεπερασμένα σύνολα.

Για παράδειγμα, X=(x1, x2, x3… x n). Εγγραφή Υ ={1, 4, 7, 5} σημαίνει ότι το σύνολο αποτελείται από τέσσερις αριθμούς 1, 4, 7, 5 .

2. Ένδειξη της χαρακτηριστικής ιδιότητας των στοιχείων του συνόλου.

Για το σκοπό αυτό, ορίζεται μια ορισμένη ιδιότητα R, το οποίο σας επιτρέπει να προσδιορίσετε εάν ένα στοιχείο ανήκει σε ένα σύνολο. Αυτή η μέθοδος είναι πιο καθολική.

X=(x: P(x))

(ένα μάτσο Χαποτελείται από τέτοια στοιχεία Χ, για το οποίο κατέχει το ακίνητο P(x)).

Ένα κενό σύνολο μπορεί να καθοριστεί προσδιορίζοντας τις ιδιότητές του: Ø=(x: x≠x)

Μπορείτε να δημιουργήσετε νέα σύνολα χρησιμοποιώντας ήδη καθορισμένα χρησιμοποιώντας πράξεις σε σύνολα.

Ορισμός Λειτουργιών

1. Ένωση (άθροισμα) είναι ένα σύνολο που αποτελείται από όλα εκείνα τα στοιχεία, καθένα από τα οποία ανήκει σε τουλάχιστον ένα από τα σύνολα ΕΝΑή ΣΕ.

A∪B=(x: x A ή x B).

2. Τομή (προϊόν) είναι ένα σύνολο που αποτελείται από όλα τα στοιχεία, καθένα από τα οποία ανήκει ταυτόχρονα στο σύνολο ΕΝΑ, και πολλά ΣΕ.

A∩B=(x: x A και x B).

3. Ορίστε τη διαφορά ΕΝΑΚαι ΣΕείναι ένα σύνολο που αποτελείται από όλα εκείνα τα στοιχεία που ανήκουν στο σύνολο ΕΝΑκαι δεν ανήκουν στο πλήθος ΣΕ.

A\B=(x: x A και x B)

4. Αν ΕΝΑ– ένα υποσύνολο ενός συνόλου ΣΕ. Είναι πολύ B\Aονομάζεται συμπλήρωμα ενός συνόλου ΕΝΑσε πολλές ΣΕκαι δηλώνουν ΕΝΑ'.

5. Η συμμετρική διαφορά δύο συνόλων είναι το σύνολο A∆B=(A\B) (B\A)

Ν- το σύνολο όλων των φυσικών αριθμών.
Ζ- το σύνολο όλων των ακεραίων αριθμών.
Q- το σύνολο όλων των ρητών αριθμών.
R- το σύνολο όλων των πραγματικών αριθμών.
ντο- το σύνολο όλων των μιγαδικών αριθμών.
Ζ 0- το σύνολο όλων των μη αρνητικών ακεραίων.

Ιδιότητες πράξεων σε σύνολα:

1. Α Β=Β A (αντιθετική ένωση)

2. Α Β=Β A (ανταλλαγή τομής)

3. Α(Β Γ)=(Α ΣΕ) Γ (συνδικαλιστική οργάνωση)

4. Α (ΣΕ Γ)=(Α ΣΕ) Γ (συνειρμότητα τομής)

5. Α (ΣΕ Γ)=(Α ΣΕ) (ΕΝΑ Γ) (1ος νόμος της κατανομής)

6. Α (ΣΕ Γ)=(Α ΣΕ) (ΕΝΑ Γ) (2ος νόμος της κατανομής)

7. Α Ø=Α

8. Α U= U

9. Α Ø= Ø

10. Α U=A

11. (Α Β)'=Α' Β' (νόμος του de Morgan)

12. (Α Β)'=Α' Β' (νόμος του de Morgan)

13. Α (ΕΝΑ Β)=Α (νόμος απορρόφησης)

14. Α (ΕΝΑ Β)=Α (νόμος απορρόφησης)

Ας αποδείξουμε την ιδιοκτησία Νο 11. (ΕΝΑ Β)'=Α' ΣΕ'

Εξ ορισμού των ίσων συνόλων, πρέπει να αποδείξουμε δύο εγκλείσματα 1) (ΕΝΑ Β) "⊂A" ΣΕ';

2) ΕΝΑ' B’⊂(A ΣΕ)'.

Για να αποδείξετε την πρώτη συμπερίληψη, εξετάστε ένα αυθαίρετο στοιχείο x∈(Α B)’=X\(A∪B).Αυτό σημαίνει ότι x∈X, x∉ A∪B. Από αυτό προκύπτει ότι x∉AΚαι x∉B, Να γιατί x∈X\AΚαι x∈X\B, που σημαίνει x∈A'∩B'. Ετσι, (ΕΝΑ Β)"⊂A" ΣΕ'

Επιστροφή αν x∈A' ΣΕ', Οτι Χανήκει ταυτόχρονα σε σύνολα Α', Β', που σημαίνει x∉AΚαι x∉B. Από αυτό προκύπτει ότι x∉ Α ΣΕ, Να γιατί x∈(Α ΣΕ)'. Ως εκ τούτου, ΕΝΑ' B’⊂(A ΣΕ)'.

Ετσι, (ΕΝΑ Β)'=Α' ΣΕ'

Ένα σύνολο που αποτελείται από δύο στοιχεία, στα οποία ορίζεται η σειρά των στοιχείων, ονομάζεται διατεταγμένο ζεύγος. Για να το γράψετε, χρησιμοποιήστε παρενθέσεις. (x 1, x 2)– ένα σύνολο δύο στοιχείων στο οποίο το x 1 θεωρείται το πρώτο στοιχείο και το x 2 είναι το δεύτερο. Ζευγάρια (x 1, x 2)Και (x 2, x 1),Οπου x 1 ≠ x 2, θεωρούνται διαφορετικά.

Ένα σύνολο που αποτελείται από n στοιχεία, στο οποίο ορίζεται η σειρά των στοιχείων, ονομάζεται διατεταγμένο σύνολο n στοιχείων.

Ένα καρτεσιανό προϊόν είναι ένα αυθαίρετο σύνολο X 1, X 2,…,X nδιατεταγμένα σύνολα n στοιχείων, όπου x 1 X 1, x 2 X 2 ,…, x n X n

Χ 1 Xn

Αν τα σετ X 1, X 2,…,X nαγώνας (X 1 = X 2 =…=X n), τότε συμβολίζεται το γινόμενο τους Xn.

Για παράδειγμα, ℝ 2 – ένα σύνολο διατεταγμένων ζευγών πραγματικών αριθμών.

Σχέσεις ισοδυναμίας. Σύνολα παραγόντων

Με βάση ένα δεδομένο σύνολο, νέα σύνολα μπορούν να κατασκευαστούν λαμβάνοντας υπόψη το σύνολο ορισμένων υποσυνόλων. Σε αυτήν την περίπτωση, συνήθως δεν μιλάμε για ένα σύνολο υποσυνόλων, αλλά για μια οικογένεια ή κατηγορία υποσυνόλων.

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

Αφήνω Χδεν είναι ένα κενό σύνολο, τότε οποιοδήποτε υποσύνολο Rαπό το έργο Χ Χονομάζεται δυαδική σχέση στο σύνολο Χ. Αν ένα ζευγάρι (x,y)συμπεριλαμβανεται σε R,λένε ότι το στοιχείο x βρίσκεται στη σχέση RΜε στο.

Για παράδειγμα, οι σχέσεις x=y, x≥yείναι δυαδικές σχέσεις στο σετ ℝ.

Δυαδική σχέση Rσε ένα σετ Χονομάζεται σχέση ισοδυναμίας αν:

1. (x,x) R; Χ X (ιδιότητα ανακλαστικότητας)

2. (x,y) R => (y,x) R (ιδιότητα συμμετρίας)

3. (x,y) R, (y,z) R, μετά (x,z) R (ιδιότητα μεταβατικότητας)

Αν ένα ζευγάρι (x,y)μπαίνουν σε σχέσεις ισοδυναμίας, τότε τα x και y ονομάζονται ισοδύναμα (x~y).

1.Αφήστε ℤ - ένα σύνολο ακεραίων αριθμών, m≥1– ένας ακέραιος αριθμός. Ας ορίσουμε τη σχέση ισοδυναμίας Rεπί ℤ έτσι ώστε n~k, Αν ν-κδιαιρείται με Μ. Ας ελέγξουμε αν οι ιδιότητες ικανοποιούνται σε αυτή τη σχέση.

1. Αντανακλαστικότητα.

Για οποιονδηποτε n∈ℤ ℤ τέτοια που (p,p)∈R

р-ρ=0. Επειδή 0∈ ℤ , Οτι (p,p)∈ℤ.

2. Συμμετρία.

Από (n,k) ∈Rπροκύπτει ότι υπάρχει κάτι τέτοιο р∈ℤ, Τι n-k=mp;

k-n =m(-p), -p∈ ℤ, ως εκ τούτου (k,n) ∈R.

3. Μεταβατικότητα.

Από τι (n,k) ∈R, (k,q) ∈Rέπεται ότι υπάρχουν τέτοια σελ 1Και р 2 ∈ ℤ, Τι n-k=mp 1Και k-q=mp 2. Προσθέτοντας αυτές τις εκφράσεις, καταλαβαίνουμε ότι n-q=m(p 1 + p 2), p 1 + p 2 =p, p∈ ℤ. Να γιατί (n,q) ∈ ℤ.

2. Σκεφτείτε το σετ Χόλα τα κατευθυνόμενα τμήματα του χώρου ή του επιπέδου . =(Α, Β). Ας εισάγουμε τη σχέση ισοδυναμίας Rεπί Χ.

(δηλαδή, το οποίο έχει τις ακόλουθες ιδιότητες: κάθε στοιχείο του συνόλου είναι ισοδύναμο με τον εαυτό του, αν Χισοδύναμος y, Οτι yισοδύναμος Χ; Αν Χισοδύναμος y, ΕΝΑ yισοδύναμος z, Οτι Χισοδύναμος z ).

Τότε καλείται το σύνολο όλων των κλάσεων ισοδυναμίας σύνολο συντελεστώνκαι ορίζεται . Η διαίρεση ενός συνόλου σε κλάσεις ισοδύναμων στοιχείων ονομάζεται του παραγοντοποίηση.

Εμφάνιση από Χστο σύνολο των κλάσεων ισοδυναμίας καλείται χαρτογράφηση παραγόντων.

Παραδείγματα

Είναι λογικό να χρησιμοποιηθεί παραγοντοποίηση συνόλου για να ληφθούν κανονικοί χώροι από ημι-κανονισμένους, χώρους με εσωτερικό γινόμενο από χώρους με σχεδόν εσωτερικό γινόμενο κ.λπ. Για να γίνει αυτό, εισάγουμε, αντίστοιχα, τον κανόνα μιας κλάσης, ίσο με το κανόνας ενός αυθαίρετου στοιχείου και το εσωτερικό γινόμενο των κλάσεων ως εσωτερικό γινόμενο αυθαίρετων στοιχείων κλάσεων. Με τη σειρά του, η σχέση ισοδυναμίας εισάγεται ως εξής (για παράδειγμα, για να σχηματιστεί ένας κανονικοποιημένος χώρος πηλίκου): εισάγεται ένα υποσύνολο του αρχικού ημιοργανωμένου χώρου, που αποτελείται από στοιχεία με μηδενικό ημιοργανισμό (παρεμπιπτόντως, είναι γραμμικό, δηλαδή, είναι ένας υποχώρος) και θεωρείται ότι δύο στοιχεία είναι ισοδύναμα αν η διαφορά τους ανήκει σε αυτόν ακριβώς τον υποχώρο.

Εάν, για την παραγοντοποίηση ενός γραμμικού χώρου, εισάγεται ένας συγκεκριμένος υποχώρος και υποτεθεί ότι αν η διαφορά δύο στοιχείων του αρχικού χώρου ανήκει σε αυτόν τον υποχώρο, τότε αυτά τα στοιχεία είναι ισοδύναμα, τότε το σύνολο παραγόντων είναι ένας γραμμικός χώρος και ονομάζεται ένας χώρος παράγοντας.

Παραδείγματα

δείτε επίσης

Ίδρυμα Wikimedia. 2010.

Δείτε τι είναι το "Σετ συντελεστών" σε άλλα λεξικά:

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

Μια μορφή σκέψης που αντανακλά τις ουσιαστικές ιδιότητες, τις συνδέσεις και τις σχέσεις των αντικειμένων και των φαινομένων στην αντίφαση και την ανάπτυξή τους. μια σκέψη ή σύστημα σκέψεων που γενικεύει, διακρίνει αντικείμενα μιας ορισμένης τάξης σύμφωνα με ορισμένες γενικές και στο σύνολο... ... Μεγάλη Σοβιετική Εγκυκλοπαίδεια

Κοομολογία ομάδας Galois. Εάν το M είναι μια ομάδα Abelian και μια ομάδα Galois μιας επέκτασης που ενεργεί στο M, τότε οι ομάδες συνομολογίας Galois είναι ομάδες συνομολογίας που ορίζονται από ένα σύμπλεγμα που αποτελείται από όλους τους χάρτες και το d είναι ένας συνοριακός τελεστής (βλ. Κοομολογία ομάδων).... . .. Μαθηματική Εγκυκλοπαίδεια

Η κατασκευή, στον παράδεισο, εμφανίστηκε αρχικά στη θεωρία συνόλων και στη συνέχεια χρησιμοποιήθηκε ευρέως στην άλγεβρα, την τοπολογία και άλλους τομείς των μαθηματικών. Μια σημαντική ειδική περίπτωση ενός I. p είναι μια κατευθυνόμενη οικογένεια μαθηματικών δομών του ίδιου τύπου. Ας είναι … Μαθηματική Εγκυκλοπαίδεια

Σημεία αν και σε σχέση με την ομάδα G που ενεργεί στο σύνολο X (στα αριστερά), το σύνολο είναι μια υποομάδα του G και καλείται. σταθεροποιητής, ή ακίνητη υποομάδα ενός σημείου ως προς το G. Η χαρτογράφηση προκαλεί μια διχοτόμηση μεταξύ G/Gx και της τροχιάς G(x). ΣΧΕΤΙΚΑ ΜΕ.… … Μαθηματική Εγκυκλοπαίδεια

Αυτό το άρθρο έχει πολύ σύντομη εισαγωγή. Προσθέστε μια εισαγωγική ενότητα που εισάγει εν συντομία το θέμα του άρθρου και συνοψίζει το περιεχόμενό του... Wikipedia

Αυτό το άρθρο αφορά το αλγεβρικό σύστημα. Για τον κλάδο της μαθηματικής λογικής που μελετά δηλώσεις και πράξεις σε αυτές, δείτε την Άλγεβρα της Λογικής. Η άλγεβρα Boole είναι ένα μη κενό σύνολο Α με δύο δυαδικές πράξεις (ανάλογες με έναν σύνδεσμο), ... ... Wikipedia

Ας δοθεί μια σχέση ισοδυναμίας σε ένα σύνολο. Τότε το σύνολο όλων των κλάσεων ισοδυναμίας ονομάζεται σύνολο παραγόντων και συμβολίζεται. Η διαίρεση ενός συνόλου σε κλάσεις ισοδύναμων στοιχείων ονομάζεται παραγοντοποίησή του. Χαρτογράφηση από έως... ... Wikipedia

Στη γεωμετρία, ένα κατευθυνόμενο τμήμα νοείται ως ένα διατεταγμένο ζεύγος σημείων, το πρώτο από τα οποία, το σημείο Α, ονομάζεται αρχή του και το δεύτερο, Β, το τέλος του. Περιεχόμενα 1 Ορισμός ... Wikipedia

Σε διάφορους κλάδους των μαθηματικών, ο πυρήνας μιας αντιστοίχισης είναι ένα ορισμένο σύνολο kerf, το οποίο κατά μία έννοια χαρακτηρίζει τη διαφορά μεταξύ f και μιας εγχυτικής χαρτογράφησης. Ο συγκεκριμένος ορισμός μπορεί να διαφέρει, αλλά για την ενστικτώδη χαρτογράφηση f... ... Wikipedia

Συντελεστής ορισμού

Πλήθη.

Μια σχέση μερικής τάξης σε ένα σύνολο x είναι μια δυαδική σχέση που είναι αντισυμμετρική, αντανακλαστική και μεταβατική και συμβολίζεται με
ως ζευγάρι:

Μια δυαδική σχέση ονομάζεται ανοχή εάν είναι αντανακλαστική και συμμετρική.

Μια δυαδική σχέση ονομάζεται οιονεί τάξη εάν είναι ααντανακλαστική, αντισυμμετρική και μεταβατική (προ-τάξη).

Μια δυαδική σχέση ονομάζεται αυστηρή τάξη εάν είναι αντανακλαστική και μεταβατική.

Μια εναρική αλγεβρική πράξη στο σύνολο M είναι η συνάρτηση

– ενιαία λειτουργία·

– δυαδική λειτουργία.

– δοκιμαστική λειτουργία.

Δυαδική αλγεβρική πράξη –

– μια πράξη που εκχωρεί σε κάθε διατεταγμένο ζεύγος από το σύνολο M κάποιο στοιχείο του συνόλου M.

Ιδιότητες:

1) Ανταλλαγή:

2) Συνεταιρισμός:

Ουδέτερο στοιχείο

Ορίζει το M για δυαδικές αλγεβρικές πράξεις

Το στοιχείο ονομάζεται:

• 
  Παράγοντας σκηνικά– ένα σύνολο τάξεων ισοδυναμίας αυτού σκηνικά. Μερική σχέση παραγγελίας στις ΠολλάΤο x ονομάζεται δυαδική σχέση...


• 
  Επόμενη ερώτηση." Παράγοντας σκηνικά. Παράγοντας σκηνικά– ολότητα Πολλαπλασιαστικές και προσθετικές μορφές.


• 
  Παράγοντας σκηνικά– ολότητα
  Ενα μάτσο- ένα σύνολο καθορισμένων και διακριτών αντικειμένων που είναι νοητά ως ενιαίο σύνολο.


• 
  Μια πολλαπλασιαστική συνάρτηση είναι μια... περισσότερα ». Παράγοντας σκηνικά. Παράγοντας σκηνικά– ένα σύνολο τάξεων ισοδυναμίας αυτού σκηνικά.


• 
  Στην πραγματικότητα, η διαδικασία παραγωγής είναι πιο περίπλοκη και το προϊόν της είναι αποτέλεσμα χρήσης σκηνικά παράγοντες.


• 
  Η ποιότητα των αποφάσεων της διοίκησης εξαρτάται από σκηνικά παράγοντες, το πιο σημαντικό από τα οποία μπορεί να είναι το n.


• 
  Η βελτιστοποίηση των αποφάσεων άντλησης κεφαλαίων είναι μια ερευνητική διαδικασία σκηνικά παράγοντεςεπηρεάζει τα αναμενόμενα αποτελέσματα...

Έστω R μια δυαδική σχέση στο σύνολο X. Η σχέση R ονομάζεται ανακλαστικός , εάν (x, x) О R για όλα τα x О X; συμμετρικός – αν από (x, y) О R ακολουθεί (y, x) О R; ο μεταβατικός αριθμός 23 αντιστοιχεί στην επιλογή 24 εάν (x, y) О R και (y, z) О R υποδηλώνουν (x, z) О R.

Παράδειγμα 1

Θα πούμε ότι x О X έχει κοινά με στοιχείο y О X, αν το σύνολο
x Ç y δεν είναι κενό. Η σχέση που έχουμε από κοινού θα είναι αντανακλαστική και συμμετρική, αλλά όχι μεταβατική.

Σχέση ισοδυναμίαςστο X είναι μια ανακλαστική, μεταβατική και συμμετρική σχέση. Είναι εύκολο να δούμε ότι το R Í X ´ X θα είναι μια σχέση ισοδυναμίας αν και μόνο αν ισχύουν τα εγκλείσματα:

Id X Í R (ανακλαστικότητα),

R -1 Í R (συμμετρία),

R ° R Í R (μεταβατικότητα).

Στην πραγματικότητα, αυτές οι τρεις συνθήκες είναι ισοδύναμες με τις ακόλουθες:

Id X Í R, R -1 = R, R ° R = R.

Με τη διάσπασηενός συνόλου X είναι το σύνολο A ζευγαρωμένων ασύνδετων υποσυνόλων a Í X έτσι ώστε UA = X. Με κάθε διαμέρισμα A μπορούμε να συσχετίσουμε μια σχέση ισοδυναμίας ~ στο X, βάζοντας x ~ y αν x και y είναι στοιχεία κάποιου a Î A .

Κάθε σχέση ισοδυναμίας ~ στο Χ αντιστοιχεί σε ένα διαμέρισμα Α, τα στοιχεία του οποίου είναι υποσύνολα, καθένα από τα οποία αποτελείται από αυτά στη σχέση ~. Αυτά τα υποσύνολα ονομάζονται τάξεις ισοδυναμίας . Αυτό το διαμέρισμα Α ονομάζεται συντελεστή συνόλου του συνόλου Χ ως προς το ~ και συμβολίζεται: Χ/~.

Ας ορίσουμε τη σχέση ~ στο σύνολο w των φυσικών αριθμών, βάζοντας x ~ y αν τα υπόλοιπα από τη διαίρεση των x και y με το 3 είναι ίσα. Τότε το w/~ αποτελείται από τρεις κλάσεις ισοδυναμίας που αντιστοιχούν στα υπόλοιπα 0, 1 και 2.

Σχέση παραγγελίας

Μια δυαδική σχέση R σε ένα σύνολο Χ ονομάζεται αντισυμμετρική , αν από x R y και y R x προκύπτει: x = y. Μια δυαδική σχέση R σε ένα σύνολο Χ ονομάζεται σχέση παραγγελίας , αν είναι αντανακλαστικό, αντισυμμετρικό και μεταβατικό. Είναι εύκολο να διαπιστωθεί ότι αυτό είναι ισοδύναμο με τις ακόλουθες συνθήκες:

1) Id X Í R (ανακλαστικότητα),

2) R Ç R -1 (αντισυμμετρία),

3) R ° R Í R (μεταβατικότητα).

Καλείται ένα διατεταγμένο ζεύγος (X, R) που αποτελείται από ένα σύνολο X και μια σχέση τάξης R στο X σετ μερικής παραγγελίας .

Παράδειγμα 1

Έστω X = (0, 1, 2, 3), R = ((0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2 ), (1, 3), (2, 2), (3, 3)).

Εφόσον το R ικανοποιεί τις συνθήκες 1 – 3, τότε το (X, R) είναι ένα μερικώς διατεταγμένο σύνολο. Για στοιχεία x = 2, y = 3, ούτε x R y ούτε y R x είναι αληθές. Τέτοια στοιχεία ονομάζονται ασύγκριτος . Συνήθως η σχέση παραγγελίας συμβολίζεται με £. Στο παράδειγμα που δίνεται, 0 £ 1 και 2 £ 2, αλλά δεν είναι αλήθεια ότι 2 £ 3.

Παράδειγμα 2

Αφήνω< – бинарное отношение строгого неравенства на множестве w натуральных чисел, рассмотренное в разд. 1.2. Тогда объединение отношений = и < является отношением порядка £ на w и превращает w в частично упорядоченное множество.

Τα στοιχεία x, y О X ενός μερικώς διατεταγμένου συνόλου (X, £) ονομάζονται συγκρίσιμος , εάν x £ y ή y £ x.

Καλείται ένα μερικώς διατεταγμένο σετ (X, £). γραμμικά διατεταγμένα ή αλυσίδα , εάν δύο από τα στοιχεία του είναι συγκρίσιμα. Το σύνολο από το παράδειγμα 2 θα ταξινομηθεί γραμμικά, αλλά το σύνολο από το παράδειγμα 1 όχι.

Καλείται ένα υποσύνολο A Í X ενός μερικώς διατεταγμένου συνόλου (X, £). οριοθετείται παραπάνω , αν υπάρχει ένα στοιχείο x О X τέτοιο ώστε ένα £ x για όλα τα a О A. Το στοιχείο x О X ονομάζεται το μεγαλύτερο στο X αν y £ x για όλα τα y О X. Ένα στοιχείο x О X ονομάζεται μέγιστο αν δεν υπάρχουν στοιχεία y О X διαφορετικά από το x για το οποίο x £ y. Στο παράδειγμα 1, τα στοιχεία 2 και 3 θα είναι το μέγιστο, αλλά όχι το μεγαλύτερο. Ομοίως ορίζεται κατώτερο όριο υποσύνολα, μικρότερα και ελάχιστα στοιχεία. Στο παράδειγμα 1, το στοιχείο 0 θα είναι τόσο το μικρότερο όσο και το ελάχιστο. Στο Παράδειγμα 2, το 0 έχει επίσης αυτές τις ιδιότητες, αλλά το (w, £) δεν έχει ούτε το μεγαλύτερο ούτε το μέγιστο στοιχείο.

Αν η στάση R έχει τις εξής ιδιότητες: αντανακλαστικό συμμετρικό μεταβατικό, δηλ. είναι μια σχέση ισοδυναμίας (~ ή ≡ ή E) στο σύνολο Μ , τότε το σύνολο των κλάσεων ισοδυναμίας ονομάζεται σύνολο παραγόντων του συνόλου Μ σχετικά με την ισοδυναμία R και ορίζεται ΚΥΡΙΟΣ

Υπάρχει ένα υποσύνολο στοιχείων του συνόλου Μ ισοδύναμος Χ , που ονομάζεται τάξη ισοδυναμίας.

Από τον ορισμό ενός συνόλου παραγόντων προκύπτει ότι είναι υποσύνολο ενός Boolean: .

Η συνάρτηση καλείται ταυτοποίησηκαι ορίζεται ως εξής:

Θεώρημα.Άλγεβρα παραγόντων φάΤο n /~ είναι ισόμορφο με την άλγεβρα των συναρτήσεων Boole σι n

Απόδειξη.

Ο απαιτούμενος ισομορφισμός ξ : φά n / ~ → σι Το n καθορίζεται από τον ακόλουθο κανόνα: κλάση ισοδυναμίας ~(φ) αντιστοιχίζεται η λειτουργία f φ , έχοντας έναν πίνακα αλήθειας για έναν αυθαίρετο τύπο από το σύνολο ~(φ) . Δεδομένου ότι διαφορετικές κλάσεις ισοδυναμίας αντιστοιχούν σε διαφορετικούς πίνακες αλήθειας, η αντιστοίχιση ξ injective, και αφού για οποιαδήποτε Boolean συνάρτηση φά από Στη σελ υπάρχει ένας τύπος που αντιπροσωπεύει τη συνάρτηση φά, μετά η χαρτογράφηση ξ υποκειμενικό. Λειτουργίες αποθήκευσης, 0, 1 όταν εμφανίζεται ξ ελέγχεται απευθείας. CTD.

Με το θεώρημα της συναρτησιακής πληρότητας κάθε συνάρτησης που δεν είναι σταθερά 0 , αντιστοιχεί σε κάποιο SDNF ψ , που ανήκουν στην τάξη ~(φ) = ξ -1 (f) τύπους που αντιπροσωπεύουν μια συνάρτηση φά . Προκύπτει το πρόβλημα του να είσαι στην τάξη ~(φ) διαζευκτική κανονική μορφή, η οποία έχει την απλούστερη δομή.

Τέλος εργασίας -

Αυτό το θέμα ανήκει στην ενότητα:

Μάθημα διαλέξεων για τον κλάδο των διακριτών μαθηματικών

Κρατικό Πανεπιστήμιο Πολιτικών Μηχανικών της Μόσχας.. Ινστιτούτο Διοίκησης Οικονομίας και Πληροφοριακών Συστημάτων στις Κατασκευές.. IEEE..

Εάν χρειάζεστε επιπλέον υλικό για αυτό το θέμα ή δεν βρήκατε αυτό που αναζητούσατε, συνιστούμε να χρησιμοποιήσετε την αναζήτηση στη βάση δεδομένων των έργων μας:

Τι θα κάνουμε με το υλικό που λάβαμε:

Εάν αυτό το υλικό σας ήταν χρήσιμο, μπορείτε να το αποθηκεύσετε στη σελίδα σας στα κοινωνικά δίκτυα:

Τιτίβισμα

Όλα τα θέματα σε αυτήν την ενότητα:

Θέμα διακριτών μαθηματικών
Το θέμα των διακριτών (πεπερασμένων, πεπερασμένων) μαθηματικών είναι κλάδος των μαθηματικών που μελετά τις ιδιότητες διακριτών δομών, ενώ τα κλασικά (συνεχή) μαθηματικά μελετούν τις ιδιότητες των αντικειμένων

Ισομορφισμός
Η επιστήμη που μελετά τις αλγεβρικές πράξεις ονομάζεται άλγεβρα. Αυτή η έννοια θα γίνει πιο συγκεκριμένη και θα εμβαθύνει καθώς μελετάτε το μάθημα. Η Άλγεβρα ενδιαφέρεται μόνο για το ΠΩΣ να ενεργήσει

Γυμνάσια
1. Να αποδείξετε ότι μια ισομορφική χαρτογράφηση είναι πάντα ισότονη και το αντίστροφο δεν ισχύει. 2. Γράψτε την ομάδα σας στη γλώσσα των συνόλων. 3. Γράψτε στη γλώσσα των συνόλων τα αντικείμενα που

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

Πεπερασμένα και άπειρα σύνολα
Αυτό από το οποίο αποτελείται το σύνολο, δηλ. Τα αντικείμενα που συνθέτουν ένα σύνολο ονομάζονται στοιχεία του. Τα στοιχεία ενός συνόλου είναι διακριτά και διακριτά μεταξύ τους. Όπως φαίνεται από τα παραδείγματα που δίνονται

Ισχύς του σετ
Η καρδινάτητα για ένα πεπερασμένο σύνολο είναι ίση με τον αριθμό των στοιχείων του. Για παράδειγμα, η καρδινικότητα του σύμπαντος Β(Α) ενός συνόλου Α καρδιναικότητας n

A1A2A3| + … + |A1A2A3| + … + |A1A2An| + … + |Аn-2An-1An| + (-1)n-1 |А1A2A3…An|
Ένα πεπερασμένο σύνολο Α έχει καρδινάλιο k αν είναι ίσο με το τμήμα 1.. k;:

Υποσύνολο, δικό του υποσύνολο
Αφού εισαχθεί η έννοια του συνόλου, προκύπτει το καθήκον της κατασκευής νέων συνόλων από τα υπάρχοντα, δηλαδή ο καθορισμός πράξεων σε σύνολα. "Πολλαπλά Μ"

Συμβολική γλώσσα των θεωριών συνόλων με νόημα
Στη διαδικασία της μελέτης του μαθήματος, θα γίνει διάκριση μεταξύ της αντικειμενικής γλώσσας της θεωρίας συνόλων και της μεταγλώσσας, μέσω της οποίας μελετάται η γλώσσα αντικειμένου. Με τη γλώσσα της θεωρίας συνόλων εννοούμε τη σχεσιακή

Απόδειξη
Το σύνολο Β είναι άπειρο, που σημαίνει

Προσθήκη και αφαίρεση στοιχείων
Αν το A είναι ένα σύνολο, και το x είναι ένα στοιχείο, και τότε το στοιχείο

Οριοθετημένα σύνολα. Θέστε όρια
Έστω μια αριθμητική συνάρτηση f(x) σε κάποιο σύνολο X. Το άνω όριο (όριο) της συνάρτησης f(x) είναι ένας τέτοιος αριθμός

Ακριβώς ανώτερο (κάτω) όριο
Το σύνολο όλων των άνω ορίων E συμβολίζεται με Es και όλα τα κάτω όρια με Ei. Σε περίπτωση

Το ακριβές άνω (κάτω) όριο του σετ
Αν ένα στοιχείο z ανήκει στην τομή του συνόλου E και του συνόλου όλων των άνω ορίων του Es (αντίστοιχα κάτω r

Βασικές ιδιότητες των άνω και κάτω ορίων
Έστω X ένα μερικώς διατεταγμένο σύνολο. 1. Αν, τότε

Σετ από μια αποδοτική σκοπιά
Η συνολική άποψη, σε αντίθεση με την αποδοτική άποψη, είναι λογικά αβάσιμη με την έννοια ότι οδηγεί σε παράδοξα του τύπου του Russell και του Cantor (βλ. παρακάτω). Στα πλαίσια του αποδοτικού τ

Δομή
Ένα μερικώς διατεταγμένο σύνολο Χ ονομάζεται δομή εάν περιέχει οποιοδήποτε σύνολο δύο στοιχείων

Σετ κάλυψης και διαχωρισμού
Ένα διαμέρισμα ενός συνόλου Α είναι μια οικογένεια Ai

Δυαδικές σχέσεις
Μια ακολουθία μήκους n, οι όροι της οποίας είναι a1, .... an, θα συμβολίζεται με (a1, .... a

Ιδιότητες δυαδικών σχέσεων
Μια δυαδική σχέση R στο σύνολο Ho έχει τις ακόλουθες ιδιότητες: (α) ανακλαστική αν xRx

Τριμερείς σχέσεις
Καρτεσιανό προϊόν XY

Ν-αριακές σχέσεις
Κατ' αναλογία με το καρτεσιανό γινόμενο δύο συνόλων X,Y, μπορούμε να κατασκευάσουμε το καρτεσιανό γινόμενο X

Οθόνες
Οι αντιστοιχίσεις είναι μερικές συνδέσεις μεταξύ στοιχείων συνόλων. Τα πιο απλά παραδείγματα σχέσεων είναι οι σχέσεις μέλους x

Αλληλογραφία
Ένα υποσύνολο S ενός καρτεσιανού γινομένου ονομάζεται ν-αριακή αντιστοιχία στοιχείων των συνόλων Mi. Τυπικά

Λειτουργία
Όλοι οι κλάδοι των διακριτών μαθηματικών βασίζονται στην έννοια της συνάρτησης. Έστω X -

Αναπαράσταση μιας συνάρτησης από την άποψη των σχέσεων
Μια δυαδική σχέση f ονομάζεται συνάρτηση αν από και

Ένεση, εγχείρηση, διχασμός
Όταν χρησιμοποιείται ο όρος "χαρτογράφηση", γίνεται διάκριση μεταξύ της αντιστοίχισης XbY και της αντιστοίχισης X σε Y

Αντίστροφη συνάρτηση
Για τα αυθαίρετα ορίζουμε

Μερικώς παραγγελθέντα σετ
Ένα σύνολο S ονομάζεται μερικώς διατεταγμένο (PUM) εάν του δοθεί μια ανακλαστική, μεταβατική και αντισυμμετρική σχέση δυαδικής μερικής τάξης

Ορισμός ελαχιστοποίησης αναπαράστασης
Χρησιμοποιώντας αυτούς τους νόμους, εξετάζουμε το πρόβλημα της ελαχιστοποίησης της αναπαράστασης του συνόλου M χρησιμοποιώντας τις πράξεις

Ανακατατάξεις
Δίνεται ένα σύνολο A. Έστω A ένα πεπερασμένο σύνολο που αποτελείται από n στοιχεία A = (a1, a2, …, a

Μεταθέσεις με επαναλήψεις
Έστω ότι το σύνολο Α έχει πανομοιότυπα (επαναλαμβανόμενα) στοιχεία. Μετάθεση με επαναλήψεις σύνθεσης (n1, n2, … ,nk

Τοποθετήσεις
Πλειάδες μήκους k (1≤k≤n), που αποτελούνται από διαφορετικά στοιχεία του συνόλου n στοιχείων Α (οι πλειάδες διαφέρουν σε

Τοποθετήσεις με επαναλήψεις
Έστω ότι το σύνολο Α έχει πανομοιότυπα (επαναλαμβανόμενα) στοιχεία. Τοποθετήσεις με επαναλήψεις n στοιχείων κ ονομάτων

Τακτική τοποθέτηση
Ας τοποθετήσουμε n αντικείμενα σε m κουτιά έτσι ώστε κάθε πλαίσιο να περιέχει μια ακολουθία και όχι, όπως πριν, ένα σύνολο αντικειμένων που τοποθετούνται σε αυτό. Δύο

Συνδυασμοί
Από ένα σύνολο m-στοιχείων Α κατασκευάζουμε ένα διατεταγμένο σύνολο μήκους n, τα στοιχεία του οποίου είναι διατάξεις με τα ίδια θέματα

Συνδυασμοί με επαναλήψεις
Οι τύποι που προκύπτουν είναι έγκυροι μόνο όταν δεν υπάρχουν πανομοιότυπα στοιχεία στο σύνολο Α. Έστω στοιχεία n τύπων και από αυτά πλειάδα

Μέθοδος δημιουργίας συναρτήσεων
Αυτή η μέθοδος χρησιμοποιείται για την απαρίθμηση συνδυαστικών αριθμών και τη δημιουργία συνδυαστικών ταυτοτήτων. Το σημείο εκκίνησης είναι ο συνδυασμός ακολουθίας (ai).

Αλγεβρικό σύστημα
Ένα αλγεβρικό σύστημα A είναι μια συλλογή ‹M,O,R›, το πρώτο συστατικό του οποίου το M είναι ένα μη κενό σύνολο, το δεύτερο συστατικό O είναι ένα σύνολο

Κλείσιμο και υποάλγεβρες
Ένα υποσύνολο λέγεται ότι είναι κλειστό στην πράξη φ if

Άλγεβρες με μία δυαδική πράξη
Ας δοθεί μία δυαδική πράξη στο σύνολο M. Ας εξετάσουμε τις άλγεβρες που δημιουργεί, αλλά πρώτα θα εξετάσουμε ορισμένες ιδιότητες των δυαδικών πράξεων. Δυαδικό ο

Ομαδικό
Άλγεβρα της μορφής<М, f2>που ονομάζεται γκρουποειδής. Αν η f2 είναι μια πράξη όπως ο πολλαπλασιασμός (

Ακέραιοι modulo m
Δίνεται ένας δακτύλιος ακεραίων . Να σας το θυμίσουμε. Αλγεβρα<М,

Συμφωνίες
Συμφωνία στην άλγεβρα A = (Σ – η υπογραφή της άλγεβρας αποτελείται μόνο από σύμβολα συνάρτησης) μια τέτοια σχέση ισοδυναμίας ονομάζεται

Στοιχεία θεωρίας γραφημάτων
Οι γραφικές παραστάσεις είναι μαθηματικά αντικείμενα. Η θεωρία γραφημάτων χρησιμοποιείται σε τομείς όπως η φυσική, η χημεία, η θεωρία της επικοινωνίας, ο σχεδιασμός υπολογιστών, η ηλεκτρική μηχανική, η μηχανολογία, η αρχιτεκτονική, η έρευνα σε

Γράφημα, κορυφή, άκρη
Με τον όρο μη κατευθυνόμενο γράφημα (ή, εν συντομία, γράφημα) εννοούμε ένα τέτοιο αυθαίρετο ζεύγος G = , Τι

Αλληλογραφία
Μια άλλη, πιο συχνά χρησιμοποιούμενη περιγραφή ενός κατευθυνόμενου γραφήματος G αποτελείται από τον καθορισμό ενός συνόλου κορυφών X και μιας αντιστοιχίας Г,

Μη κατευθυνόμενο γράφημα
Εάν οι ακμές δεν έχουν προσανατολισμό, τότε το γράφημα ονομάζεται μη κατευθυνόμενο (μη κατευθυνόμενο διπλότυπο ή μη προσανατολισμένο

Επίπτωση, μικτό γράφημα
Αν η ακμή e έχει τη μορφή (u, v) ή<и, v>, τότε θα πούμε ότι η ακμή e είναι πρόσπτωση ver

Αντίστροφη αντιστοίχιση
Δεδομένου ότι αντιπροσωπεύει ένα σύνολο τέτοιων κορυφών

Ισομορφισμός γραφήματος
Δύο γραφήματα G1 = και G2 = είναι ισόμορφα (Γ

Διαδρομή προσανατολισμένη στο μονοπάτι
Μια διαδρομή (ή κατευθυνόμενη διαδρομή) ενός κατευθυνόμενου γραφήματος είναι μια ακολουθία τόξων στην οποία

Παρακείμενα τόξα, διπλανές κορυφές, βαθμός κορυφής
Τόξα a = (xi, xj), xi ≠ xj, που έχουν κοινές ακραίες κορυφές, n

Συνδεσιμότητα
Δύο κορυφές σε ένα γράφημα ονομάζονται συνδεδεμένες εάν υπάρχει μια απλή διαδρομή που τις συνδέει. Ένα γράφημα ονομάζεται συνδεδεμένο εάν όλες οι κορυφές του είναι συνδεδεμένες. Θεώρημα.

Γράφημα σταθμισμένου τόξου
Ένα γράφημα G = (N, A) ονομάζεται σταθμισμένο εάν κάποια συνάρτηση l: A → R ορίζεται στο σύνολο τόξων A έτσι ώστε

Ισχυρή μήτρα συνδεσιμότητας
Ισχυρή μήτρα συνδεσιμότητας: βάλτε 1 κατά μήκος της διαγώνιας. συμπληρώστε τη γραμμή X1 - εάν η κορυφή είναι προσβάσιμη από X1 και X1 d

Δέντρα
Τα δέντρα είναι σημαντικά όχι μόνο επειδή βρίσκουν εφαρμογές σε διάφορα γνωστικά πεδία, αλλά και επειδή κατέχουν ιδιαίτερη θέση στην ίδια τη θεωρία γραφημάτων. Το τελευταίο προκαλείται από την εξαιρετική απλότητα της δομής του δέντρου

Οποιοδήποτε μη τετριμμένο δέντρο έχει τουλάχιστον δύο κρεμαστές κορυφές
Απόδειξη Θεωρήστε το δέντρο G(V, E). Επομένως, ένα δέντρο είναι ένα συνδεδεμένο γράφημα

Θεώρημα
Το κέντρο ενός ελεύθερου δέντρου αποτελείται από μία κορυφή ή δύο γειτονικές κορυφές: Z(G) = 0&k(G) = 1 → C(G) = K1

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

Απόδειξη
1. Κάθε τόξο εισέρχεται σε κάποιον κόμβο. Από την παράγραφο 2 του ορισμού 9.2.1 έχουμε: v

Παραγγελμένα δέντρα
Τα σύνολα T1,..., Tk στον ισοδύναμο ορισμό του orderev είναι υποδέντρα. Αν η σχετική σειρά των υποδέντρων T1,...,

Δυαδικά δέντρα
Ένα δυαδικό (ή δυαδικό) δέντρο είναι ένα πεπερασμένο σύνολο κόμβων που είτε είναι κενό είτε αποτελείται από μια ρίζα και δύο δυαδικά δέντρα - αριστερά και δεξιά. Δυαδικό δέντρο όχι σε java

Δωρεάν αναπαράσταση δέντρων
Για να αναπαραστήσετε δέντρα, μπορείτε να χρησιμοποιήσετε τις ίδιες τεχνικές όπως για την αναπαράσταση γενικών γραφημάτων - πίνακες γειτνίασης και πρόσπτωσης, λίστες γειτνίασης και άλλα. Χρησιμοποιώντας όμως τις ειδικές ιδιότητες του

Τέλος για
Αιτιολογία Ο κώδικας Prüfer είναι πράγματι μια δωρεάν αναπαράσταση δέντρου. Για να το δούμε αυτό, ας δείξουμε ότι αν το T" είναι δέντρο

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

Βασικές λογικές συναρτήσεις
Ας συμβολίσουμε με Ε2 = (0, 1) ένα σύνολο που αποτελείται από δύο αριθμούς. Οι αριθμοί 0 και 1 είναι βασικοί σε ένα διακριτό χαλί

Boolean συνάρτηση
Μια Boolean συνάρτηση από n ορίσματα x1, x2, ... ,xn είναι μια συνάρτηση f από την nη δύναμη του συνόλου

Άλγεβρα Μπουλ δύο στοιχείων
Ας εξετάσουμε το σύνολο Во = (0,1) και ας ορίσουμε τις πράξεις σε αυτό, σύμφωνα με τους πίνακες των πηγών

Πίνακες συναρτήσεων Boolean
Μια Boolean συνάρτηση n μεταβλητών μπορεί να καθοριστεί από έναν πίνακα που αποτελείται από δύο στήλες και 2n σειρές. Η πρώτη στήλη παραθέτει όλα τα σύνολα από το B

F5 – επανάληψη σε y
f6 – sum modulo 2 f7

Σειρά εργασιών
Εάν δεν υπάρχουν παρενθέσεις σε μια σύνθετη έκφραση, τότε οι πράξεις πρέπει να εκτελούνται με την ακόλουθη σειρά: σύνδεσμος, διαχωρισμός, συνεπαγωγή, ισοδυναμία, άρνηση. Συμβάσεις σχετικά με τη διάταξη του πρώτου θεωρήματος του Shannon
Για να λύσουμε το πρόβλημα της εύρεσης του SDNF και του SCNF που είναι ισοδύναμο με τον αρχικό τύπο φ, εξετάζουμε πρώτα τις επεκτάσεις της Boolean συνάρτησης f(x1, x2

Το δεύτερο θεώρημα του Shannon
Δυνάμει της αρχής της δυαδικότητας, το Θεώρημα 6.4.3 (το δεύτερο θεώρημα του Shannon) ισχύει για τις άλγεβρες Boole. Οποιαδήποτε συνάρτηση Boole f(x1, x2,...

Λειτουργική πληρότητα
Θεώρημα (περί συναρτησιακής πληρότητας). Για κάθε Boolean συνάρτηση f υπάρχει ένας τύπος φ που αντιπροσωπεύει τη συνάρτηση f

Αλγόριθμος για την εύρεση sdnf
Για να βρείτε το SDNF, αυτός ο τύπος πρέπει πρώτα να αναχθεί στο DNF και στη συνέχεια να μετατρέψει τους συνδέσμους του σε συστατικά στοιχεία της μονάδας χρησιμοποιώντας τις ακόλουθες ενέργειες: α) εάν ο σύνδεσμος περιλαμβάνει κάποια

Η μέθοδος του Κουάιν
Εξετάστε τη μέθοδο του Quine για την εύρεση του MDNF που αντιπροσωπεύει μια δεδομένη συνάρτηση Boole. Ας ορίσουμε τις ακόλουθες τρεις λειτουργίες: - πλήρης διαδικασία κόλλησης -

Κανονική αναπαράσταση λογικών συναρτήσεων
Οι κανονικές μορφές λογικών (τύποι) συναρτήσεων είναι εκφράσεις που έχουν την τυπική μορφή ενός τύπου Boole, έτσι ώστε να αντιπροσωπεύει μοναδικά μια λογική συνάρτηση. Στην άλγεβρα

Boolean λειτουργικά συστήματα
Έστω Boolean συναρτήσεις f(g1, g2, …, gm) και g1(x1, x2, …, xn), g2(x1

βάση Zhegalkin
Ας το δοκιμάσουμε Ας δούμε το σύστημα. Είναι πλήρης, αφού οποιαδήποτε συνάρτηση από την τυπική βάση εκφράζεται με όρους

Το θεώρημα του Post
Το θεώρημα του Post θεσπίζει αναγκαίες και επαρκείς προϋποθέσεις για την πληρότητα ενός συστήματος συναρτήσεων Boole. (Post E.L. The two-valued interactive systems of mathematical logic. – Annals of Math. Stu

Απόδειξη
Ανάγκη. Από το αντίθετο. Ας είναι

Άλγεβρα Zhegalkin
Το άθροισμα συντελεστή 2, ο σύνδεσμος και οι σταθερές 0 και 1 σχηματίζουν ένα λειτουργικά πλήρες σύστημα, δηλ. σχηματίζουν μια άλγεβρα - άλγεβρα Zhegalkin. Α=

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

Ορισμός κατηγορήματος
Έστω X1, X2, ..., Xn αυθαίρετες μεταβλητές. Θα ονομάσουμε αυτές τις μεταβλητές υποκείμενες μεταβλητές. Αφήστε τη μεταβλητή να σας καθορίζει

Εφαρμογή κατηγορημάτων στην άλγεβρα
Ας εξετάσουμε κατηγορήματα στα οποία μόνο μία μεταβλητή είναι ελεύθερη, την οποία συμβολίζουμε με x, και ας συζητήσουμε τη χρήση κατηγορημάτων στην άλγεβρα. Χαρακτηριστικό παράδειγμα

Άλγεβρα κατηγορήματος Boole
Εφόσον οι λογικές πράξεις μπορούν να εφαρμοστούν σε κατηγορήματα, οι βασικοί νόμοι της άλγεβρας Boole ισχύουν για αυτούς. Θεώρημα. (Ιδιότητες λογικών πράξεων για κατηγορήματα). Mn

F↔G=(F→G)(G→F), F→G=όχι FG
2. Χρησιμοποιήστε το νόμο όχι F=F, τους νόμους του de Morgan: όχι (F

Κατηγορηματικός λογισμός
Ο λογισμός κατηγορήματος ονομάζεται επίσης θεωρία πρώτης τάξης. Στον λογισμό κατηγορήματος, καθώς και στον προτασιακό λογισμό, η πρώτη πιο σημαντική θέση είναι το πρόβλημα της επιλυτότητας.

Ακολούθηση και ισοδυναμία
Ο προτασιακός τύπος Q2 προκύπτει από τον προτασιακό τύπο Q1 εάν η συνεπαγωγή Q1→Q2 γίνει αληθής

Αποδεκτές σημειώσεις
Σύμβολα του «παραγγελία πια». Κατά τη σύγκριση του ρυθμού ανάπτυξης δύο συναρτήσεων f(n) και g(n) (με μη αρνητικές τιμές), τα ακόλουθα είναι πολύ βολικά

Μετα-προσδιορισμοί
Σύμβολα Περιεχόμενα Παράδειγμα Ή