Relații de echivalență. Setați factorul. Relația de echivalență și setul de factori Seturi de factori inclusiv
(adică care are următoarele proprietăți: fiecare element al multimii este echivalent cu sine; Dacă X echivalentă cu y, Acea y echivalentă cu X; Dacă X echivalentă cu y, A y echivalentă cu z, Acea X echivalentă cu z ).
Apoi se numește mulțimea tuturor claselor de echivalență set de factori si se noteaza. Împărțirea unei mulțimi în clase de elemente echivalente se numește ei factorizarea.
Afișare de la Xîn mulţimea claselor de echivalenţă se numeşte cartografierea factorilor.
Exemple
Este rezonabil să se folosească factorizarea multime pentru a obține spații normate din spații semi-normate, spații cu produs interior din spații cu produs aproape interior etc. Pentru aceasta se introduce norma unei clase, respectiv, egală cu norma de un element arbitrar al acestuia și produsul scalar al claselor ca produs scalar al elementelor arbitrare ale claselor. La rândul său, se introduce relația de echivalență în felul următor(de exemplu, pentru a forma un spațiu coeficient normat): se introduce o submulțime a spațiului semi-normat original, constând din elemente cu seminormă zero (apropo, este liniar, adică este un subspațiu) si se considera ca doua elemente sunt echivalente daca diferenta lor apartine chiar acestui subspatiu.
Dacă un anumit subspațiu al unui spațiu liniar este introdus pentru a factoriza un spațiu liniar și se presupune că dacă diferența a două elemente din spațiul original aparține acestui subspațiu, atunci aceste elemente sunt echivalente, atunci mulțimea factorilor este spațiu liniarși se numește spațiu coeficient.
Exemple
Vezi si
Fundația Wikimedia. 2010 .
Vedeți ce este „Factorset” în alte dicționare:
Principiul logic care stă la baza definițiilor prin abstracție (vezi Definiția prin abstracție): orice relație de tip de egalitate, definită pe un set inițial de elemente, desparte (împarte, clasifică) originalul... ...
O formă de gândire care reflectă proprietățile esențiale, conexiunile și relațiile obiectelor și fenomenelor în contradicția și dezvoltarea lor; un gând sau un sistem de gânduri care generalizează, evidențiază obiectele unei anumite clase în funcție de un anumit general și în agregat ... ... Marea Enciclopedie Sovietică
Coomologia grupului Galois. Dacă M este un grup Abelian și un grup Galois al unei extensii care acționează pe M, atunci coomologia Galois este grupul de coomologie definit de complexul constă din toate mapările, iar d este un operator de co-limită (vezi Coomologia grupului). Enciclopedie matematică
Construcția rai a apărut pentru prima dată în teoria mulțimilor și apoi a devenit utilizată pe scară largă în algebră, topologie și alte domenii ale matematicii. Important caz special Un I.P. este un I.P. dintr-o familie dirijată de structuri matematice de același tip. Lasa … Enciclopedie matematică
Puncte față de un grup G care acționează asupra unei mulțimi X (stânga), mulțimea A mulțime este un subgrup al lui G și se numește. stabilizator, sau un subgrup staționar al unui punct în raport cu G. Maparea induce o bijecție între G/Gx și orbita G(x). DESPRE.… … Enciclopedie matematică
Acest articol are o introducere foarte scurtă. Vă rugăm să completați o secțiune introductivă care descrie pe scurt subiectul articolului și rezumă conținutul acestuia... Wikipedia
Acest articol este despre sistemul algebric. Pentru ramura logicii matematice care studiază propozițiile și operațiile asupra lor, vezi Algebra logicii. Algebra booleană este o mulțime A nevidă cu două operații binare (analoage unei conjuncții), ... ... Wikipedia
Fie dată o relație de echivalență pe mulțime. Apoi, mulțimea tuturor claselor de echivalență se numește mulțime de factori și se notează. Împărțirea unei mulțimi în clase de elemente echivalente se numește factorizare. Afișare de la la ... ... Wikipedia
Un segment direcționat în geometrie este înțeles ca o pereche ordonată de puncte, primul punct A fiind numit începutul său, iar al doilea B este numit sfârșitul său. Cuprins 1 Definiție ... Wikipedia
În diverse ramuri ale matematicii, nucleul unei mapări este un kerf set, care într-un anumit sens caracterizează diferența dintre f și o mapare injectivă. Definiția specifică poate varia, totuși, pentru o mapare injectivă f ...... Wikipedia
factor setat
Seturi.
O relație de ordin parțial pe o mulțime x este o relație binară care este antisimetrică, reflexivă și tranzitivă și se notează cu
ca pereche:
O relație binară se numește toleranță dacă este reflexivă și simetrică.
O relație binară se numește cvasiordine dacă este ireflexivă, antisimetrică și tranzitivă (preordine).
O relație binară se numește ordine strictă dacă este reflexivă și tranzitivă.
O operație algebrică enary pe o mulțime M este o funcție
este o operațiune unară;
este o operație binară;
- operațiune triary.
Operație algebrică binară −
este o operație care atribuie fiecărei perechi ordonate din mulțimea M un element al mulțimii M.
Proprietăți:
1) Comutativitate:
2) Asociativitate:
element neutru
Setează M pentru o operație algebrică binară
Elementul se numește:
-
Factor seturi este mulţimea claselor de echivalenţă ale acesteia seturi. Relația de ordine parțială pe multitudine x se numește relație binară... -
Urmatoarea intrebare." Factor seturi. Factor seturi- agregat. Forme multiplicative și aditive. -
Factor seturi- agregat.
O multime de- un ansamblu de obiecte anumite și diferite, concepute ca un singur întreg. -
O funcție multiplicativă este o... mai multe detalii ». Factor seturi. Factor seturi este mulţimea claselor de echivalenţă ale acesteia seturi. -
În realitate, procesul de producție este mai complicat, iar produsul său este rezultatul utilizării. seturi factori. -
De calitatea deciziilor manageriale depinde seturi factori, dintre care cel mai semnificativ poate fi n. -
Optimizarea deciziilor de strângere de capital este un proces de cercetare seturi factori care afectează rezultatele așteptate...
Dacă raportul R are următoarele proprietăți: reflexiv simetric tranzitiv, i.e. este o relație de echivalență (~ sau ≡ sau E) pe mulțime M , atunci mulțimea claselor de echivalență se numește mulțime de factori a mulțimii M în ceea ce priveşte echivalenţa R și notat DOMNUL
Iată un subset al elementelor setului M echivalent X numit clasa de echivalență.
Din definiția unui set de factori rezultă că acesta este o submulțime a booleanului: .
Funcția este numită Identificareși se definește după cum urmează:
Teorema. Algebra factorială F n /~ este izomorf la algebra funcțiilor booleene B n
Dovada.
Izomorfism necesar ξ : F n / ~ → B n se determină după următoarea regulă: clasa de echivalenţă ~(φ) funcția mapată f φ , având un tabel de adevăr al unei formule arbitrare din mulţime ~(φ) . Deoarece diferite clase de echivalență corespund diferitelor tabele de adevăr, maparea ξ injectiv, și deoarece pentru orice funcție booleană f din În p există o formulă care reprezintă funcția f, apoi cartografierea ξ în mod surjectiv. Salvarea operațiunilor , 0, 1 când sunt afișate ξ verificat direct. CHTD.
Conform teoremei privind completitatea funcțională a fiecărei funcții care nu este o constantă 0 , corespunde unor SDNF ψ , aparținând clasei ~(φ) = ξ -1 (f) formule care reprezintă o funcție f . Există o problemă de a fi în clasă ~(φ) forma normală disjunctivă, care are cea mai simplă structură.
Sfârșitul lucrării -
Acest subiect aparține:
Curs de prelegeri pe disciplina matematică discretă
Universitatea de Stat de Inginerie Civilă din Moscova, Institutul de Economie a Managementului și sisteme de informare in constructii.. ieuis..
Dacă aveți nevoie de material suplimentar pe această temă, sau nu ați găsit ceea ce căutați, vă recomandăm să utilizați căutarea în baza noastră de date de lucrări:
Ce vom face cu materialul primit:
Dacă acest material s-a dovedit a fi util pentru dvs., îl puteți salva pe pagina dvs. de pe rețelele sociale:
| tweet |
Toate subiectele din această secțiune:
Subiectul de matematică discretă
Subiectul matematicii discrete (finite, finite) este o ramură a matematicii care studiază proprietățile structurilor discrete, în timp ce matematica clasică (continuă) studiază proprietățile obiectelor.
izomorfism
Știința care studiază operațiile algebrice se numește algebră. Acest concept va fi concretizat și aprofundat pe măsură ce cursul este studiat. Algebra este interesată doar de întrebarea CUM
Exerciții
1. Demonstrați că o mapare izomorfă este întotdeauna izotonă și inversul nu este adevărat. 2. Notează-ți grupul în limba seturi. 3. Notează în limbajul seturilor obiectele care
Multimea si elementele multimii
În prezent, teoriile multimilor existente diferă în paradigmatica (sistemul de vederi) a bazei conceptuale și a mijloacelor logice. Deci, ca exemplu, putem da două opuse
Mulțimi finite și infinite
În ce constă setul, adică Obiectele care alcătuiesc o mulțime se numesc elementele sale. Elementele unui set sunt distincte și distincte unele de altele. După cum se vede din exemple
Setați puterea
Puterea pentru o mulțime finită este egală cu numărul elementelor sale. De exemplu, cardinalitatea universului B(A) al mulțimii A cu cardinalitatea n
A1A2A3| + … + |А1A2A3| + … + |А1A2An| + … + |An-2An-1An| + (-1)n-1 |А1A2A3…An|
O mulțime finită A are cardinalitatea k dacă este echivalentă cu segmentul 1..k;:
Subset, subset propriu
După ce a fost introdus conceptul de mulțime, se pune problema construcției de mulțimi noi din cele existente, adică de a determina operații pe mulțimi. set de M",
Limbajul simbolic al teoriilor multimilor semnificative
În procesul de studiere a cursului, vom face distincția între limbajul obiect al teoriei mulțimilor și metalimbajul, prin intermediul căruia se studiază limbajul obiect. Prin limbajul teoriei mulțimilor înțelegem relația
Dovada
Mulțimea B este infinită, deci
Adăugarea și eliminarea articolelor
Dacă A este o mulțime și x este un element, în plus, atunci elementul
Seturi limitate. Stabiliți limite
Fie dată o funcție numerică f(x) pe o mulțime X. Limita superioară (limita) a funcției f (x) se numește un astfel de număr
Limită superioară (inferioară) precisă
Setul tuturor limitelor superioare ale lui E este notat cu Es, al tuturor limitelor inferioare - cu Ei. În cazul în care
Limita superioară (inferioară) exactă a setului
Dacă un element z aparține intersecției mulțimii E și mulțimii tuturor limitelor sale superioare Es (respectiv, z inferior
Proprietățile de bază ale marginilor superioare și inferioare
Fie X o mulțime parțial ordonată. 1. Dacă, atunci
Un set din punct de vedere atributiv
Punctul de vedere agregat, spre deosebire de cel atributiv, este logic insuportabil în sensul că duce la paradoxuri precum Russell și Cantor (vezi mai jos). În cadrul t atributivului
Structura
O mulțime X parțial ordonată se numește structură dacă conține orice mulțime de două elemente
Seturi de acoperire și despicare
O partiție a unei mulțimi A este o familie Ai
relații binare
O secvență de lungime n ai cărei membri sunt a1, .... an va fi notat cu (a1, .... a
Proprietățile relațiilor binare
Relația binară R pe mulțimea Ho are următoarele proprietăți: (a) în mod reflex dacă xRx
Relații ternare
Produsul cartezian XY
Relații N-are
Prin analogie cu produsul cartezian a doi setează X,Y se poate construi produsul cartezian X
Afișări
Mapările sunt niște conexiuni între elementele mulțimilor. Cele mai simple exemple de relații sunt relațiile de membru x
Corespondenţă
Submulțimea S a produsului cartezian se numește corespondența n-ară a elementelor mulțimilor Mi. Oficial
Funcţie
În centrul tuturor secțiunilor matematicii discrete se află conceptul de funcție. Fie x-
Reprezentarea unei funcții în termeni de relații
O funcție este o relație binară f dacă de la și
Injecție, surjecție, bijecție
Când se utilizează termenul „mapping”, se face o distincție între o mapare X la Y și o mapare X la Y
Funcție inversă
Pentru arbitrar, definim
Seturi parțial comandate
O mulțime S se numește parțial ordonată (POS) dacă i se oferă o relație de ordin parțial binar reflexiv, tranzitiv și antisimetric.
Setați minimizări de reprezentare
Folosind aceste legi, luăm în considerare problema minimizării reprezentării mulțimii M cu ajutorul operațiilor
Permutări
Dată o mulțime A. Fie A o mulțime finită formată din n elemente A = (a1, a2, …, a
Permutări cu repetări
Fie ca multimea A sa contina elemente identice (repetate). Permutarea cu repetări ale compoziției (n1, n2, … ,nk
Cazare
Tupluri de lungime k (1≤k≤n) constând din diferite elemente ale mulțimii de n elemente A (tuplurile diferă într-unul
Plasări cu repetări
Fie ca multimea A sa contina elemente identice (repetate). Plasări cu repetări de n elemente prin k nume
Plasare comandată
Am plasat n obiecte în m cutii astfel încât fiecare cutie să conțină o succesiune, și nu un set, ca înainte, a obiectelor plasate în ea. Două
Combinații
Dintr-o mulțime de m elemente A construim o mulțime ordonată de lungime n ale cărei elemente sunt aranjamente cu aceleași subiecte
Combinații cu repetări
Formulele rezultate sunt valabile numai atunci când nu există elemente identice în mulțimea A. Să fie elemente de n tipuri și din ele un tuplu de
Funcții generatoare de metode
Această metodă este folosită pentru a enumera numere combinatorii și pentru a stabili identități combinatorii. Punctul de plecare este combinatorul secvenței (ai).
Sistem algebric
Sistem algebric A este colecția ‹M,O,R›, prima componentă a cărei M este o mulțime nevidă, a doua componentă O este mulțimea
Închidere și subalgebre
O submulțime se numește închisă sub operația φ dacă
Algebre cu o operație binară
Să fie dată o operație binară pe mulțimea M. Luați în considerare algebrele generate de acesta, dar mai întâi luați în considerare unele proprietăți ale operațiilor binare. Binar despre
grupoid
Vedeți algebra<М, f2>numit un grupoid. Dacă f2 este o operație ca înmulțirea (
Numerele întregi modulo m
Dat un inel de numere întregi
Congruente
Congruență pe algebră A =
Elemente de teoria grafurilor
Graficele sunt obiecte matematice. Teoria graficelor este aplicată în domenii precum fizica, chimia, teoria comunicării, proiectarea computerelor, inginerie electrică, inginerie mecanică, arhitectură, cercetare
grafic, vârf, muchie
Prin un graf nedirecționat (sau, pe scurt, un graf) înțelegem o astfel de pereche arbitrară G =
Corespondenţă
O altă descriere mai frecvent utilizată a unui graf direcționat G este de a specifica un set de vârfuri X și o corespondență Γ, care
Grafic nedirecționat
Dacă marginile nu au nicio orientare, atunci graficul se numește nedirecționat (duplicat nedirecționat sau nedirecționat).
Incident, grafic mixt
Dacă muchia e are forma (u, v) sau<и, v>, atunci vom spune că muchia e este incidentă cu ver
Potrivire inversă
Deoarece este un set de astfel de vârfuri
Izomorfismul grafic
Două grafice G1 =
Traseu orientat spre cale
O cale (sau traseu direcționat) a unui grafic direcționat este o succesiune de arce în care
Arce adiacente, vârfuri adiacente, grad de vârf
Arce а = (хi, хj), хi ≠ хj, având vârfuri comune, n
Conectivitate
Două vârfuri dintr-un graf se numesc conectate dacă există o cale simplă care le conectează. Un graf se numește conexat dacă toate vârfurile sale sunt conectate. Teorema.
Grafic cu arce ponderate
Un grafic G = (N, A) se numește ponderat dacă pe mulțimea arcelor A este definită o funcție l: A → R, care pe
Matrice de conectivitate puternică
Matrice de conectivitate puternică: setați în diagonală 1; completați linia X1 - dacă vârful este accesibil de la X1 și X1 d
Copaci
Arborii sunt importanți nu numai pentru că își găsesc aplicații în diverse domenii ale cunoașterii, ci și datorită poziției lor speciale în teoria grafurilor în sine. Acesta din urmă se datorează simplității extreme a structurii arborelui.
Fiecare copac non-trivial are cel puțin două vârfuri suspendate
Dovada Se consideră un arbore G(V, E). Un arbore este un graf conectat, deci
Teorema
Centrul unui arbore liber este format dintr-un vârf sau două vârfuri adiacente: Z(G) = 0&k(G) = 1 → C(G) = K1
Arbori direcționați, ordonați și binari
Arborii orientați (ordonați) sunt o abstractizare a relațiilor ierarhice care sunt foarte comune atât în viața practică, cât și în matematică și programare. Copac (orient
Dovada
1. Fiecare arc intră într-un nod. Din punctul 2 din definiția 9.2.1 avem: v
Arbori ordonați
Mulțimile T1,..., Tk din definiția echivalentă a unui arbore de ordine sunt subarbori. Dacă ordinea relativă a subarborilor T1,...,
arbori binari
Un arbore binar (sau binar) este un set finit de noduri care este fie gol, fie constă dintr-o rădăcină și doi arbori binari care nu se intersectează - stânga și dreapta. arbore binar nu java
Reprezentarea arborilor liberi
Pentru a reprezenta arbori, puteți folosi aceleași tehnici ca și pentru reprezentarea graficelor generale - matrice de adiacență și incidență, liste de adiacență și altele. Dar folosind proprietățile speciale ale lui d
Sfârșit pentru
Motivație Codul Prufer este într-adevăr o reprezentare a unui arbore liber. Pentru a verifica acest lucru, arătăm că dacă T" este un arbore
Reprezentarea arborilor binari
Orice arbore liber poate fi orientat prin desemnarea unuia dintre noduri ca rădăcină. Orice comandă poate fi ordonată în mod arbitrar. Pentru descendenții unui nod (frați) ai unui arbore de ordine ordonată, ruda
Funcții logice de bază
Notăm cu E2 = (0, 1) mulțimea formată din două numere. Numerele 0 și 1 sunt de bază în mat discret
funcţie booleană
O funcție booleană de n argumente x1, x2, …, xn, este o funcție f din puterea a n-a a mulțimii
Algebră booleană cu două elemente
Luați în considerare mulțimea Bo = (0,1) și definiți operații pe ea, conform tabelelor
Tabelele cu funcții booleene
O funcție booleană de n variabile poate fi dată ca un tabel cu două coloane și 2n rânduri. Prima coloană listează toate seturile din B
F5 - se repetă în y
f6 – suma modulo 2 f7
Ordinea operațiunilor
Dacă într-o expresie complexă nu există paranteze, atunci operațiile trebuie efectuate în următoarea ordine: conjuncție, disjuncție, implicație, echivalență, negație. Convenții de aranjare Prima teoremă a lui Shannon
Pentru a rezolva problema găsirii SDNF și SKNF echivalente cu formula originală φ, luăm în considerare mai întâi expansiunile funcției booleene f(x1, x2
A doua teoremă a lui Shannon
În virtutea principiului dualității pentru algebrele booleene, Teorema 6.4.3 (a doua teoremă a lui Shannon) este valabilă. Orice funcție booleană f(x1, x2,...
Completitudine funcțională
Teorema (despre completitudinea funcțională). Pentru orice funcție booleană f, există o formulă φ care reprezintă funcția f
Algoritm pentru găsirea sdnf
Pentru a găsi SDNF, această formulă trebuie mai întâi redusă la DNF, iar apoi conjunctele sale trebuie convertite în constituenți unitari folosind următoarele acțiuni: a) dacă conjuncția conține unele
Metoda Quine
Luați în considerare metoda lui Quine pentru găsirea unui MDNF reprezentând o funcție booleană dată. Definim urmatoarele tri-operatii: - operatia de lipire completa -
Reprezentarea canonică a funcțiilor booleene
Formele canonice ale funcțiilor logice (formule) sunt expresii care au o formă standard a unei formule booleene, una care reprezintă în mod unic o funcție logică. În algebră
Sisteme cu funcții booleene
Fie funcțiile booleene f(g1, g2, …, gm) și g1(x1, x2, …, xn), g2(x1
Baza Zhegalkin
Exemplu Luați în considerare sistemul. Este completă, deoarece orice funcție din baza standard este exprimată în termeni de
teorema lui Post
Teorema lui Post stabilește condițiile necesare și suficiente pentru completitudinea unui sistem de funcții booleene. (Post E.L. Sistemele interactive cu două valori ale logicii matematice. – Annals of Math. Stu
Dovada
Necesitate. Din contra. Lasă și
Algebră Zhegalkin Logica propozițională Definiția predicatului Aplicarea predicatelor în algebră Algebră a predicatelor booleene F↔G=(F→G)(G→F), F→G=nu FG Calcul predicat Urmărirea și Echivalența Denumiri acceptate Meta desemnări Fie R o relație binară pe o mulțime X. Relația R se numește reflectorizant
, dacă (x, x) О R pentru toate x О X; simetric
– dacă (x, y) О R implică (y, x) О R; numărul tranzitiv 23 corespunde variantei 24 dacă (x, y) Î R și (y, z) Î R implică (x, z) Î R. Exemplul 1 Vom spune că x − X are în comun
cu elementul y н X dacă mulţimea Relația de echivalență pe X se numește relație reflexivă, tranzitivă și simetrică. Este ușor de observat că R Н X ´ X va fi o relație de echivalență dacă și numai dacă includerile au loc: Id X Í R (reflexivitate), R -1 Í R (simetrie), R ° R Í R (tranzitivitate). De fapt, aceste trei condiții sunt echivalente cu următoarele: Id X Í R, R -1 = R, R ° R = R. despicare mulţimea X este mulţimea A de submulţimi disjunse în perechi a н X astfel încât UA = X. Cu fiecare partiţie a lui A, putem asocia o relaţie de echivalenţă ~ pe X stabilind x ~ y dacă x şi y sunt elemente ale unor a н A . Fiecărei relaţii de echivalenţă ~ pe X îi corespunde o partiţie A, ale cărei elemente sunt submulţimi, fiecare fiind formată din cele din relaţia ~. Aceste subseturi sunt numite clase de echivalenţă
. Această partiție A se numește mulțime de factori a mulțimii X față de ~ și se notează: X/~. Să definim relația ~ pe mulțimea w de numere naturale stabilind x ~ y dacă resturile după împărțirea x și y la 3 sunt egale. Atunci w/~ constă din trei clase de echivalență corespunzătoare resturilor 0, 1 și 2. Relația de comandă O relație binară R pe o mulțime X se numește antisimetric
, dacă din x R y și y R x rezultă: x = y. O relație binară R pe o mulțime X se numește relație de ordine
, dacă este reflexiv, antisimetric și tranzitiv. Este ușor de observat că acest lucru este echivalent cu următoarele condiții: 1) Id X Í R (reflexivitate), 2) R Ç R -1 (antisimetrie), 3) R ° R Í R (tranzitivitate). Se numește o pereche ordonată (X, R) formată dintr-o mulțime X și o relație de ordine R pe X set parțial comandat
. Exemplul 1 Fie X = (0, 1, 2, 3), R = ((0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2) ), (1, 3), (2, 2), (3, 3)). Deoarece R satisface condițiile 1–3, atunci (X, R) este o mulțime parțial ordonată. Pentru elementele x = 2, y = 3, nici x R y nici y R x nu sunt adevărate. Astfel de elemente sunt numite incomparabil
. De obicei, relația de ordine este notată cu £. În exemplul de mai sus, 0 £ 1 și 2 £ 2, dar nu este adevărat că 2 £ 3. Exemplul 2 Lăsa< – бинарное отношение строгого неравенства на множестве w натуральных чисел, рассмотренное в разд. 1.2. Тогда объединение отношений = и < является отношением порядка £ на w и превращает w в частично упорядоченное множество. Elementele x, y О X ale unei mulțimi parțial ordonate (X, £) sunt numite comparabil
, dacă x £ y sau y £ x. Se numește mulțimea parțial ordonată (X, £). ordonat liniar
sau lanţ
dacă oricare două dintre elementele sale sunt comparabile. Mulțimea din Exemplul 2 va fi ordonată liniar, dar mulțimea din Exemplul 1 nu. Se numește o submulțime A Í X dintr-o mulțime parțial ordonată (X, £). mărginit de sus
, dacă există un element x н X astfel încât un £ x pentru tot un н A. Un element x н X se numește cel mai mare
în X dacă y £ x pentru tot y О X. Un element x О X se numeşte maxim dacă nu există elemente y О X diferite de x pentru care x £ y. În exemplul 1, elementele 2 și 3 vor fi maxime, dar nu cele mai mari. The constrângere de jos
submulțimi, elemente minime și minime. În exemplul 1, elementul 0 ar fi atât cel mai mic, cât și cel mai mic. În exemplul 2, 0 are și aceste proprietăți, dar (w, t) nu are nici cel mai mare, nici elementul maxim. Fie G=(p 0 =e, p 1 , …, p r ) un grup de permutare definit pe mulțimea X = (1, 2, …, n) cu identitate e=p 0 prin permutarea identică. Definim relația x~y prin stabilirea x~y, ceea ce este echivalent cu a spune că există un p aparținând lui G(p(x)=y). Relația introdusă este o relație de echivalență, adică satisface trei axiome: 1) x~x; Fie A o mulțime arbitrară. notat cu a ~ b, σ(a,b), (a,b) ∈ σ, a σ b Definiție: O partiție a unei mulțimi A este o familie de submulțimi disjunse în perechi din A, în unire (în sumă) dând tot A. Subseturile A i sunt numite clase ale partiției. Teorema: fiecare relație de echivalență definită pe A corespunde unei partiții a mulțimii A. Fiecare partiție a mulțimii A corespunde unei relații de echivalență pe mulțimea A. Pe scurt, există o corespondență unu-la-unu între clasele tuturor relațiilor de echivalență definite pe mulțimea A și clasa tuturor partițiilor mulțimii A. Dovada: fie σ o relație de echivalență pe o mulțime A. Fie a ∈ A. Să construim o mulțime: К a =(x ∈ A,: x~a ) – toate elementele echivalente cu a. Mulțimea (notația) se numește clasa de echivalență în raport cu echivalența σ. Rețineți că dacă b aparține lui K a , atunci b~a. Să arătăm că a~b⇔K a =K b . Într-adevăr, să fie a~b. Luați un element arbitrar c aparține lui K a . Atunci c~a, a~b, c~b, c aparţine lui K b şi deci K b aparţine lui K a . Faptul că K a aparține lui K b este arătat în mod similar. Prin urmare, K b =K a . Dacă 2 clase Ka și K b au un element comun c, atunci Ka = K b . Într-adevăr, dacă c aparține lui Ka și K b , atunci b~c, c~a, b~a => Ka = K b . Prin urmare, diferite clase de echivalență fie nu se intersectează, fie se intersectează și apoi coincid. Fiecare element c al lui A aparține unei singure clase de echivalență K c. Prin urmare, sistemul de clase de echivalență care nu se suprapun la intersecție dă întreaga mulțime A. Și, prin urmare, acest sistem este o partiție a mulțimii A în clase de echivalență. Revers: Fie A = suma peste sau A i o partiție a lui A. Să introducem relația a~b pe A, deoarece a~b ⇔ a,b aparțin aceleiași clase de partiții. Această relație satisface următoarele axiome: 1) a ~ a (sunt în aceeași clasă); cometariu: 2) Împărțirea lui A în submulțimi de un element corespunde relației de echivalență, care este egalitate. 3) Partiția A, constând dintr-o clasă A, corespunde unei relații de echivalență care conține A x A. 4) a σ b → [a] σ = [b] σ — orice relație de echivalență definită pe o mulțime împarte această mulțime în clase disjunse pe perechi numite clase de echivalență. Definiție: Mulțimea claselor de echivalență ale mulțimii A se numește mulțime de factori A/σ a mulțimii A prin echivalența σ. Definiție: O mapare p:A→A/σ astfel încât p(A)=[a] σ se numește o mapare canonică (naturală). Orice relație de echivalență definită pe o mulțime împarte această mulțime în clase disjunse, numite clase de echivalență.
Suma modulo 2, conjuncția și constantele 0 și 1 formează un sistem complet funcțional, adică. formează o algebră - algebra Zhegalkin. A=
Logica matematică studiază conceptele de bază de sintaxă (formă) și semantică (conținut) ale unui limbaj natural. Luați în considerare trei domenii majore de cercetare în logica matematică - logica
Fie X1, X2, ..., Xn variabile arbitrare. Aceste variabile vor fi numite variabile obiect. Fie seturile de variabile
Luați în considerare predicate în care o singură variabilă este liberă, pe care le notăm cu x, și discutăm despre aplicarea predicatelor în algebră. Un exemplu tipic
Deoarece operațiile logice pot fi aplicate predicatelor, legile de bază ale algebrei booleene sunt valabile pentru acestea. Teorema. (Proprietăți ale operațiilor logice pentru predicate). Mn
2. Folosiți legea nu nu F=F, legile lui de Morgan: nu (F
Calculul predicaților se mai numește și teorii de ordinul întâi. În calculul predicatului, precum și în calculul propozițional, pe primul loc ca importanță se află problema decidabilitatii.
Forma propozițională Q2 decurge din forma propozițională Q1 dacă implicația Q1→Q2 se transformă într-un mare adevărat.
Simboluri de „nu mai comanda”. Când se compară rata de creștere a două funcții f(n) și g(n) (cu valori nenegative), următoarele sunt foarte convenabile.
Simboluri Cuprins Exemplu SAU
x З y nu este gol. Relația de a avea în comun va fi reflexivă și simetrică, dar nu tranzitivă.
2) x~y→y~x;
3) x~y&y~z→x~z;
Definiție: O relație binară δ=A*A este o relație de echivalență (notată a ~ b) dacă îndeplinesc următoarele axiome:
∀ a, b, c ∈ A
1) a ~ a - reflexivitate;
2) a ~ b ⇒ b ~ a - comutativitate;
3) a ~ b & b ~ c → a ~ c - tranzitivitatea
А= ∪А i , А i ∩А j = ∅, ∀i ≠ j.
Fie acum K b =K a . Atunci a aparține lui K a = K b , a aparține lui K b , a~b. Ceea ce trebuia arătat.
2) a ~ b → b ~ a;
3) a ~ b & b ~ c → a ~ c, i.e. relaţia introdusă ~ este o relaţie de echivalenţă.
1) împărțirea mulțimii A în submulțimi cu un singur element și partiția lui A, constând numai din mulțimea A, se numește partiție trivială (improprie).
Se încarcă...
