Beställningsförhållande. Beställda set
Låt R vara en binär relation på mängden A.
DEFINITION. En binär relation R på en mängd A kallas en ordningsrelation på A eller en ordning på A om den är transitiv och antisymmetrisk.
DEFINITION. En relation av ordning R på en mängd A kallas icke-strikt om den är reflexiv på A, det vill säga för var och en av A.
En ordningsrelation R kallas strikt (på A) om den är antireflexiv på A, det vill säga för någon av A. Av antireflexiviteten hos den transitiva relationen R följer dock att den är antisymmetrisk. Därför kan följande ekvivalenta definition ges.
DEFINITION. En binär relation R på en mängd A kallas en strikt ordning på A om den är transitiv och antireflexiv på A.
Exempel. 1. Låt vara mängden av alla delmängder av mängden M. Inklusionsrelationen på en mängd är en relation av icke-strikt ordning.
2. Relationer på mängden reella tal är relationer av strikt respektive icke-strikt ordning.
3. Delbarhetsrelationen i mängden naturliga tal är en relation av icke-strikt ordning.
DEFINITION. En binär relation R på en mängd A kallas en förbeställningsrelation eller förbeställning på A om den är reflexiv på och transitiv.
Exempel. 1. Delbarhetsrelationen i mängden heltal är inte en ordning. Det är dock reflexivt och transitivt, vilket betyder att det är en förbeställning.
2. Relationen av logisk implikation är en förbeställning på uppsättningen av propositionella logiska formler.
Linjär ordning. Ett viktigt specialfall av ordning är linjär ordning.
DEFINITION. En ordningsrelation på en mängd kallas en linjär ordningsrelation eller en linjär ordning på om den är kopplad på , d.v.s. för valfritt x, y från A
En ordningsrelation som inte är linjär kallas vanligtvis en delordningsrelation eller partiell ordning.
Exempel. 1. Relationen "mindre än" på mängden reella tal är en relation av linjär ordning.
2. Ordningsrelationen som används i ryska ordböcker kallas lexikografisk. Den lexikografiska ordningen på uppsättningen av ord på det ryska språket är en linjär ordning.
2) en relation på mängden X kallas en relation strikt i ordning, om den är antisymmetrisk och transitiv. Relationen kallas antisymmetrisk, om av det faktum att a står i relation till c i det inte följer att b står i relation till a (a, i ∈ X, och R i → i Ra) R – att vara i relation. Relationen kallas transitiv, om för några element a, b, c från det faktum att a R in och i R c → att a R c, a, b, c ∈ X. Till exempel: relationen "mer, mindre". En uppsättning på vilken en strikt ordningsrelation definieras kallas beordrade många.
3) en relation på mängden X kallas en relation inte i strikt ordning, om den är reflexiv, asymmetrisk och transitiv. Till exempel: relation ≥ ≤. Om en ordningsrelation har egenskapen anknytning, så sägs den vara en relation linjär ordning. Relationen kallas relaterad på mängden X, om för några element x och y följande villkor är uppfyllt: av det faktum att x ≠ y följer att x R y eller y R x. Om en linjär ordningsrelation ges på en mängd, så ordnar den linjärt den givna mängden.
5. Uppsättningen av reella tal. Dess egenskaper. Utvidgningen av uppsättningen av rationella tal leddes av behovet av att mäta längden på segment, områden, etc. Grunden för varje mätning är samma princip: det uppmätta objektet jämförs med en standard (objekt eller fenomen), vars värde har ett numeriskt värde lika med 1, men enhetssegmentet är inte alltid inbäddat i det uppmätta objektet. När man mäter gör man därför två antaganden, som i matematik definieras som axiom: 1) En enda standard kan delas upp i valfritt antal lika delar eller delar. 2) Den valda standarden kan användas för att mäta vilket objekt som helst så stort som önskas. För segment formulerades dessa axiom av Arkimedes: Oavsett hur litet segmentet AB är och hur stort segmentet CD än är, finns det ett naturligt tal N så att N*AB>CD, om det uppmätta segmentet CD innehåller ett lika antal segment AB, så uttrycks längden på segmentet CD som ett naturligt tal. Om segmentet AB är placerat ett ojämnt antal gånger i det uppmätta segmentet CD, så delas AB in i 10 identiska segment, kallade tiondelar av standarder. Vid behov kan en tiondel delas upp i 10 lika delar osv. Om lika antal 10, 100, etc. passar in i segmentet CD. bråkdelar av segment AB, så uttrycks längden på segmentet CD med ett rationellt tal. Längden på ett segment kan dock inte alltid uttryckas som ett naturligt eller rationellt tal. Det finns inkommensurabla segment, d.v.s. segment vars längd inte uttrycks med ett rationellt tal. (satser se fråga 32)
Tal som kan representeras som oändliga decimala icke-periodiska bråk kallas irrationella. Unionen av mängden rationella tal och mängden irrationella tal är mängden reella tal ().
Egenskaper för uppsättningen av reella tal. 1). Uppsättningen av punkter på tallinjen är lika med uppsättningen av reella tal.
0 M 1 Ta valfri punkt M på segmentet från 0 till 1,
D rita en halvcirkel med mitten vid
Mittpunkten av detta segment och radien
K O S lika med hälften av det. Låt oss rita en vinkelrät från M tills den skär halvcirkeln. Vi får D. Denna punkt är unik, eftersom halvcirkeln och den räta linjen skär varandra endast i en punkt. Från mitten av detta segment, dra en rak linje genom D tills den skär talaxeln. Vi får K, som bestäms på ett unikt sätt, eftersom linjerna endast skär varandra i en punkt. Genom att välja en annan godtycklig punkt på ett givet segment och upprepa hela processen får vi att vilken punkt som helst på segmentet från 0 till 1 motsvarar en enda punkt på tallinjen. Om vi resonerar i omvänd ordning kan vi visa att vilken punkt som helst på tallinjen också motsvarar en enstaka punkt från 0 till 1. Om en godtycklig punkt E tillhör tallinjen, så kan genom punkterna M och E endast en linje dras som skär halvcirkeln. Från en halvcirkel kan du sänka en vinkelrät till ett givet segment. Således upprättas en ömsesidigt identisk mappning mellan punkterna i segmentet från 0 till 1 och punkterna på tallinjen, dvs. de är lika kraftfulla.
2) mängden reella tal är inte räknebar, dvs. det är inte lika med mängden naturliga tal.
3). Uppsättningen av reella tal är en kontinuerlig uppsättning. Kontinuiteten för mängden reella tal är att det mellan två reella tal finns en oändlig mängd av endast reella tal
6. Dela upp en uppsättning i klasser. Exempel på klassificering. Ekvivalensrelation, dess egenskaper. Förhållandet mellan ekvivalensrelationen och uppdelningen av en mängd i klasser. Låt oss titta på ett exempel. Låt en mängd M ges (en uppsättning konvexa polygoner), vi bildar alla delmängder av denna mängd: A 1 – en uppsättning trianglar; A2 – uppsättning fyrkanter; A3 – uppsättning femhörningar; Ak är en uppsättning k-goner. En uppsättning M anses vara indelad i klasser om följande villkor är uppfyllda:
- varje delmängd A är inte tom
- skärningspunkten mellan två delmängder är den tomma mängden
- föreningen av alla delmängder är den givna mängden M
Att partitionera en uppsättning i klasser kallas klassificering.
Attityd på uppsättningen kallas X likvärdig , om den är reflexiv, symmetrisk och transitiv. Relationen kallas reflekterande, om något element från mängden X är i en relation med sig själv a ∈ X, och Ra (R är i ett samband). Relationen kallas symmetrisk, om för några två element i mängden X (a och b) från det faktum att a är i ett samband med b, kommer det att följa att b är i ett samband med a (a, b ∈ X och R b → i R a). Relationen kallas transitiv, om för några element a, b, c från det faktum att a R in och i R c → att a R c, a, b, c ∈ X. På grafen för ekvivalensrelationer finns slingor, ömsesidigt inversa pilar och triangulära pilar. Ekvivalensrelationen, och endast den, är associerad med uppdelningen av en uppsättning i klasser. Detta uttalande kan formuleras som satser: Om en ekvivalensrelation specificeras på en mängd X, så delar denna relation upp mängden X i klasser, och vice versa, om mängden X är uppdelad i klasser, så är ekvivalensrelationen uppfylld på den givna mängden. Till exempel. Låt inställningen vara given – att bo i samma hus. Låt oss visa att uppsättningen av invånare i huset kommer att delas in i klasser. Och varje klass är en separat lägenhet. För denna uppdelning kommer alla nödvändiga villkor för att dela upp en uppsättning i klasser att uppfyllas: a) varje klass är inte tom, eftersom i varje lägenhet är minst 1 person registrerad, b) klasserna överlappar inte varandra (1 person är inte registrerad i två olika lägenheter), c) föreningen av alla klasser, d.v.s. invånare i varje lägenhet, och utgör uppsättningen av boende i huset.
18 . En mängdteoretisk metod för att konstruera teorin om icke-negativa heltal. Jämställdhetsrelationer, mer (mindre). Två uppsättningar A och B kallas ekvivalenta eller lika kraftfulla om en en-till-en-överensstämmelse kan upprättas mellan dem, det vill säga om varje element i uppsättning A är associerat med ett enda element av uppsättning B och vice versa. Potens eller kardinaltal är en egenskap som är inneboende i någon mängd B som är ekvivalent med mängd A och inte är inneboende i någon annan mängd som inte är lika med mängd A. A~B n (A) = a är potens. Relationen lika makt är en ekvivalensrelation, d.v.s. egenskaperna reflexivitet, symmetri och transitivitet är tillfredsställda för det. Ekvivalensrelationen delar upp mängden av alla mängder i ekvivalensklasser. För att definiera begreppet ett naturligt tal och noll, överväg partitionen av alla finita mängder.
Låt M vara mängden av alla ändliga mängder. M = K 0 Ka Kv, där Ko är klassen av tomma mängder, Ka är en mängd som innehåller lika mängder a 1, a 2, a 3, etc., Kv är en mängd. Innehåller uppsättningar av lika kardinalitet i 1, i 2, i 3, etc. Mängden M kan också innehålla andra delmängder K av olika karaktär, vilka består av mängder med lika stor styrka. Varje ekvivalensklass K har det gemensamt att de består av samma antal element, det finns inga andra gemensamma egenskaper. Ett icke-negativt heltal, ur en mängdteoretisk synvinkel, är en allmän egenskap hos klassen av ändliga uppsättningar av lika kraft. Ett naturligt tal är en allmän egenskap hos klassen av icke-tomma ändliga mängder av lika kardinalitet. Varje klass tilldelas ett kardinalnummer (kardinalitet). Klassens tomma uppsättning tilldelas koordinatnumret 0. Klassen som består av uppsättningar som har 1 element tilldelas numret 1. En klass bestående av mängder med 2 element tilldelas talet 2. (n(K 0)=0, n(K 1)=1, n(K 2)=2, n(Ka)=a).
Jämställdhetsrelation. Icke-negativa heltal a och b sägs vara lika om mängderna A och B, vars antal de uttrycker, är lika (A; n(A)=a, n(B)=b, A ~ B n( A)=n(B)a=c).
Sats: likhetsrelationen i mängden icke-negativa heltal är en ekvivalensrelation. Bevis. Låt oss bevisa att jämställdhetsrelationen har egenskaperna symmetri, transitivitet och reflexivitet.
Därför att egenskaperna för reflexivitet, symmetri och transitivitet är uppfyllda, då är likhetsrelationen en ekvivalensrelation.
Förhållandet är mindre. Icke-negativt heltal a<в, если множество А равномощно собственному подмножеству В 1 множества В. а<в; n(А)=а; n(В)=в; В 1 В n(В 1) Sats: relationen mindre än i mängden icke-negativa heltal är en relation av strikt ordning. Bevis: Låt oss bevisa att relationen mindre har egenskaperna antisymmetri och transitivitet. C 2 C 1 C 2 ~B 1 C 2 ~A n(A)=n(C 2) n(C 2) A B C 1 C B 1 C 2 19
. Addition och subtraktion i den kvantitativa teorin för icke-negativa heltal. Deras egenskaper. Belopp två icke-negativa heltal a och b kallas ett icke-negativt heltal c, vilket är kardinaliteten av föreningen av två disjunkta mängder A och B, vars kardinaliteter är lika med a respektive b. a+b=c, n(C)=n(AUB), n(AUB)=n(A)+n(B). Egenskaper för tillägg. 1. Addition i en uppsättning icke-negativa heltal finns alltid och definieras på ett unikt sätt. Låt oss bevisa att summan alltid existerar. Betrakta A och B, så att deras skärningspunkt är den tomma mängden och antalet element i A är a, och kardinaliteten för B är b. låt oss hitta föreningen av A och B. Eftersom föreningen av två disjunkta mängder alltid existerar betyder det att summan också existerar, och av definitionen av summan följer att addition alltid existerar. Låt oss bevisa att summan bestäms på ett unikt sätt. Det finns C 1 och C 2 – icke-negativa heltal. Ci = a + b och C2 = a + b. Summan av talen a och b beror inte på vilka mängder A och B vi valt från klassen av lika potensmängder, och därför beror inte föreningen av A och B från klassen av lika potensmängder av valet av uppsättningarna A och B, eftersom effekten i varje klass är densamma, då är C 1 = C 2. 2. Kommutativ addition. För alla icke-negativa heltal a och b gäller egenskapen a+b=b+a. Från mängdteorin vet vi att för АУВ = ВУА. Om mängderna är lika är deras numeriska värden lika. n(AУВ)=n(ВУА). Från mängdteorin vet vi att kraften i en förening är lika med summan av makterna. N(A)+n(B)=n(B)+n(A). 3. Egenskapen för associativitet. För alla tal a, b, c gäller följande egenskap: a+(b+c)=(a+b)+c. Från mängdteorin är det känt att för att förena mängder är associativitetsegenskapen uppfylld: АU(ВУС)=(АУВ)UC, om mängderna är lika, då är deras numeriska värden lika, n(АU(ВУС))=n( (АУВ)UC). Från mängdteorin är det känt att en unions potens är lika med summan av potenserna av dessa mängder, n(A)+n(BUC)=n(AUB)+n(C) n(A)+(n) (B)+n(C))= (n(A)+n(B))+n(C) a+(b+c)=(a+b)+c. Genom skillnad icke-negativa heltal a och b kallas ett icke-negativt heltal c, vilket är styrkan av komplementet av mängden B till mängden A, så att B tillhör A, n(A)=a, n(B) =b. Skillnadsegenskaper. 1. För att skillnaden mellan icke-negativa heltal ska existera är det nödvändigt och tillräckligt att a är större än eller lika med b. Låt oss bevisa: 1) ett tillräckligt villkor för förekomsten av en skillnad. Givet: a - b = c, bevisa: a c. Genom definitionen av skillnad följer att det finns ett komplement av mängd B till mängd A, och detta komplement har makt, vilket kan hittas från den likhet som är känd från mängdteorin. n() = n(A)-n(B). Av det faktum att B är en delmängd av A följer att antalet element i B är mindre än antalet element i A. n (B) 2). Nödvändigt skick. Givet ett c. bevisa förekomsten av skillnad (a-c). Om a>b, enligt definitionen av "mindre än"-relationen, finns det en mängd A 1 så att A 1 ingår i A och A 1 ~B. Låt oss göra skillnaden mellan A och A 1. Denna skillnad finns alltid (A - A 1 = C), och därför finns det C, vilket är denna skillnad. Av dessa villkor följer att C är komplementet av A 1 till A. C = 1A Potensen för C är potensen av komplementet av A 1 till A. n (C)=n( 1A)=n(A)- n(A 1), eftersom A 1 ~ B, då n(A 1)=n(B), därför n(C)=n(A)-n(B), därför c=a-b. 2. Skillnaden mellan icke-negativa heltal hittas på ett unikt sätt, eftersom skillnaden är styrkan av komplementet av delmängder till en mängd, och komplementet bestäms på ett unikt sätt, då är skillnaden mellan icke-negativa heltal bestäms på ett unikt sätt. 3. Egenskaperna för kommutativitet och associativitet är inte uppfyllda för subtraktion. 4. Subtrahera ett belopp från ett tal. a-(b+c)=(a-c)-c. Från mängdteorin är det känt A\(BUC)=(A\B)\C, och B Ì A; S Ì A; BUSCA. n (A\(BUC))=n((A\B)\C) n(A)-n(BUC)=n(A\B)-n(C) n(A)-(n(B)+n(C))=(n(A)-n(B))-n(C) a-(b+c)=(a-c)-c. 5. Subtrahera ett tal från skillnaden (a-c)-c=(a-c)-c. Beviset är baserat på egenskapen för skillnaden mellan mängder (A\B)\C=(A\C)\B. 6. Subtrahera ett tal från summan (a+b)-c=(a-c)+c. Beviset är baserat på egenskaperna hos mängderna (АУВ)\С=(А\С) УВ. Inte ens ens I praktiken stöter vi ofta på funktioner som varken är jämna eller jämna. 4. Funktioner kan vara periodiska. En funktion kallas periodisk om det finns ett tal T så att villkoret f(x+T)=f(x) är uppfyllt. Alla trigonometriska funktioner (sinus, cosinus, tangens) är periodiska. 5. funktioner kan ha singulära punkter. Dessa är skärningspunkterna med koordinataxlarna och punkterna för extrema, d.v.s. lägsta och högsta poäng. Punkten x0 kallas minimipunkten för funktionen om för alla X från närheten av x0 villkoren f (x) > f (x0) är uppfyllda. En punkt x0 kallas en maxpunkt för en funktion om för alla x i närheten av x0 f(x)< f (x0). 6. funktioner kan ha intervall av tecken på konstanthet, d.v.s. dessa är de delmängder, definitionsdomäner, vars element gör funktionen antingen bara positiv eller endast negativ. 7. en funktion kan ha brytpunkter, dvs. de värden av variabeln x där y inte finns (funktioner av omvänd proportionalitet). y = , om x = 0 Sök på sajten: Inaktivera adBlock! Egenskaper för relationer: 1) reflexivitet; 2) symmetri; 3)transitivitet. 4) anknytning. Attityd R på ett set X kallad reflekterande, om varje element i uppsättningen X vi kan säga att han är i ett förhållande R Med mig själv: XRx. Om relationen är reflexiv, så finns det en slinga vid varje hörn av grafen. Omvänt är en graf vars varje hörn innehåller en loop en reflexiv relationsgraf. Exempel på reflexiva relationer är relationen "multipel" på mängden naturliga tal (varje tal är en multipel av sig själv), och likhetsrelationen mellan trianglar (varje triangel liknar sig själv), och relationen "likhet" ( varje tal är lika med sig själv), etc. Det finns relationer som inte har egenskapen reflexivitet, till exempel förhållandet mellan segmentens vinkelräta: ab, ba(det finns inte ett enda segment som kan sägas vara vinkelrätt mot sig självt) .
Därför finns det inte en enda slinga i grafen för detta förhållande. Relationen "längre" för segment, "mer med 2" för naturliga tal, etc. har inte egenskapen reflexivitet. Attityd R på ett set X kallad antireflekterande, om för något element från uppsättningen X alltid falskt XRx: .
Det finns relationer som varken är reflexiva eller antireflexiva. Ett exempel på ett sådant förhållande är förhållandet ”punkt X symmetrisk i sak på relativt rak l", definierad på en uppsättning punkter i planet. Ja, alla punkter på en rak linje lär symmetriska till sig själva och punkter som inte ligger på en rak linje jag, själva är inte symmetriska. Attityd R på ett set X kallad symmetrisk,
om villkoret är uppfyllt: från det faktum att elementet X står i relation till elementet y, det följer att elementet yär i relation R med element X:xRyyRx. Den symmetriska relationsgrafen har följande funktion: tillsammans med varje pil som kommer från X Till y, innehåller grafen en pil som går från y Till X(Fig. 35). Exempel på symmetriska relationer kan vara följande: förhållandet mellan "parallellism" av segment, förhållandet mellan "vinkelrätt" av segment, förhållandet mellan "likhet" av segment, förhållandet mellan likhet mellan trianglar, förhållandet mellan "likhet" av bråk etc. Det finns relationer som inte har egenskapen symmetri. Ja, om segmentet X längre än segmentet på, sedan segmentet på kan inte vara längre än segmentet X. Grafen för detta förhållande har en egenhet: pilen som förbinder hörnen är endast riktad i en riktning. Attityd R kallad antisymmetrisk, om för några element X Och y från sanningen
xRy ska vara falskt
yRx: : xRyyRx. Förutom den "längre" relationen finns det andra antisymmetriska relationer på många segment. Till exempel, relationen "större än" för tal (if X Mer på, Den där på det kan inte bli mer X), "mer om"-attityden osv. Det finns relationer som varken har egenskapen symmetri eller egenskapen antisymmetri. Relation R på en uppsättning X kallad transitiv, om från det elementet Xär i relation R med element y, och element yär i relation R med element z, det följer att elementet Xär i relation R med element z: xRy Och yRzxRz. Transitiv relationsgraf med varje par av pilar som kommer från X Till y och från y Till z, innehåller en pil som går från X Till z.
Relationen "längre" på en uppsättning segment har också transitivitetsegenskapen: om segmentet A längre än segmentet b, linjesegmentet b längre än segmentet Med, sedan segmentet A längre än segmentet Med. Relationen "jämlikhet" på en uppsättning segment har också egenskapen transitivitet: (a=b, b=c)(a=c). Det finns relationer som inte har egenskapen transitivitet. En sådan relation är till exempel relationen vinkelräthet: om ett segment A vinkelrätt mot segmentet b och segmentet b vinkelrätt mot segmentet Med, sedan segmenten A Och Med inte vinkelrät! Det finns en annan egenskap av relationer, som kallas egenskapen för anknytning, och en relation som har den kallas sammankopplad. Attityd R på ett set X kallad ansluten, om för några element X Och y från denna uppsättning är följande villkor uppfyllt: if X Och yär olika då heller Xär i relation R med element y, eller element yär i relation R med element X. Med hjälp av symboler kan detta skrivas så här:
xyxRy eller yRx. Till exempel, relationen "större än" för naturliga tal har egenskapen att vara ansluten: för alla distinkta tal x och y kan man ange antingen x>y, eller y>x. I en sammankopplad relationsgraf är två valfria hörn sammankopplade med en pil. Det motsatta påståendet är också sant. Det finns relationer som inte har egenskapen anknytning. En sådan relation, till exempel, är relationen mellan delbarhet på mängden naturliga tal: vi kan namnge sådana tal x och y oavsett antal Xär inte en divisor av ett tal y, inget nummer yär inte en divisor av ett tal X(tal 17
Och 11
, 3
Och 10
etc.) .
Låt oss titta på några exempel. På set X=(1, 2, 4, 8, 12) relationen "antal" ges X multipel av talet y" Låt oss konstruera en graf över detta förhållande och formulera dess egenskaper. Relationen mellan bråklikhet sägs vara en ekvivalensrelation. Attityd R på ett set X kallad ekvivalensförhållande, om den samtidigt har egenskaperna reflexivitet, symmetri och transitivitet. Exempel på ekvivalensrelationer inkluderar: likhetsrelationer för geometriska figurer, relationer av parallellitet mellan linjer (förutsatt att sammanfallande linjer anses vara parallella). I förhållandet "jämlikhet av bråk" som diskuterats ovan, uppsättningen X delas upp i tre delmängder: ( ; ;
}, {;
} ,
(). Dessa delmängder skär inte varandra, och deras förening sammanfaller med mängden X, dvs. vi har en uppdelning av uppsättningen i klasser. Så, om en ekvivalensrelation ges på en mängd X, genererar den en partition av denna mängd i parvis disjunkta delmängder - ekvivalensklasser. Således har vi fastställt att jämställdhetsrelationen på uppsättningen Principen att dela upp en uppsättning i klasser med hjälp av någon ekvivalensrelation är en viktig princip inom matematiken. Varför? För det första betyder likvärdig likvärdig, utbytbar. Därför är element av samma ekvivalensklass utbytbara. Således, fraktioner som är i samma ekvivalensklass (; ; ),
är omöjliga att särskilja ur synvinkeln av förhållandet mellan jämlikhet och bråkdelen
kan till exempel ersättas av en annan .
Och denna ersättning kommer inte att ändra resultatet av beräkningarna. För det andra, eftersom ekvivalensklassen innehåller element som inte går att särskilja ur någon relations synvinkel, tror man att ekvivalensklassen bestäms av någon av dess representanter, dvs. ett godtyckligt element i klassen. Således kan vilken klass som helst av lika fraktioner specificeras genom att specificera vilken fraktion som helst som tillhör denna klass. ekvivalensklass av en representant låter dig studera en uppsättning representanter från ekvivalensklasser istället för alla delar av uppsättningen. Till exempel genererar ekvivalensrelationen "att ha samma antal hörn", definierad på en uppsättning polygoner, en partition av denna uppsättning i klasser av trianglar, fyrhörningar, femhörningar, etc. fastigheter som ingår i en viss klass anses på en av dess representanter. För det tredje, partitionering av en uppsättning i klasser med hjälp av en ekvivalensrelation används för att introducera nya begrepp. Till exempel kan begreppet "bunt av linjer" definieras som vad parallella linjer har gemensamt med varandra. En annan viktig typ av relation är ordningsförhållandet. Låt oss överväga problemet, på uppsättningen X={3, 4, 5, 6, 7, 8, 9, 10
) relationen ”har samma rest när de divideras med 3
" Denna relation genererar en partition av uppsättningen X in i klasser: alla tal kommer att falla i en, när de divideras med 3
det visar sig vara resten 0
(detta är siffror 3, 6,
9
). I den andra - siffror, när de divideras med 3
resten är 1
(detta är siffror 4, 7, 10
). Den tredje kommer att innehålla alla siffror som, när de divideras med 3
resten är 2
(detta är siffror 5, 8
). Faktum är att de resulterande uppsättningarna inte skär varandra och deras förening sammanfaller med mängden X. Därför har relationen "samma återstod när den divideras med 3
", definieras på setet X, är en ekvivalensrelation. För att ta ett annat exempel kan de många eleverna i en klass sorteras efter längd eller ålder. Observera att denna relation har egenskaperna antisymmetri och transitivitet. Eller så vet alla ordningen på bokstäverna i alfabetet. Det tillhandahålls av "bör"-attityden. Attityd R på ett set X kallad förhållande av en strikt ordning, om den samtidigt har egenskaperna antisymmetri och transitivitet. Till exempel relationen " X<
y». Om relationen har egenskaperna reflexivitet, antisymmetri och transitivitet, så kommer den att vara sådan icke-strikt förhållande. Till exempel relationen " Xy». Exempel på ordningsrelationer inkluderar: "mindre än"-relationen på en uppsättning naturliga tal, den "kortare" relationen på en uppsättning segment. Om en ordningsrelation också har egenskapen anknytning, så sägs den vara det linjär ordningsrelation. Till exempel relationen "mindre än" på mängden naturliga tal. Ett gäng X kallad ordnad, om en orderrelation anges på den. Till exempel många X={2, 8, 12, 32
) kan beställas med hjälp av "mindre än"-relationen (fig. 41), eller så kan detta göras med "multipel"-relationen (fig. 42). Men eftersom de är ordningsrelationer, ordnar relationerna "mindre än" och "multipel" mängden naturliga tal på olika sätt. Relationen "mindre än" låter dig jämföra två valfria tal från en uppsättning X, men relationen "multipel" har inte denna egenskap. Okej, ett par siffror. 8
Och 12
är inte relaterat till relationen "multipel": det kan inte sägas så 8
flera olika 12
eller 12
flera olika 8.
Man ska inte tro att alla relationer är uppdelade i ekvivalensförhållanden och ordningsförhållanden. Det finns ett stort antal relationer som varken är ekvivalensrelationer eller ordningsrelationer. Ordet "ordning" används ofta i en mängd olika frågor. Officeren ger kommandot: "Räkna i numerisk ordning", aritmetiska operationer utförs i en viss ordning, idrottare rangordnas efter höjd, alla ledande schackspelare är ordnade i en viss ordning enligt de så kallade Elo-koefficienterna (amerikansk professor vem utvecklade systemkoefficienterna, så att du kan ta hänsyn till spelarnas alla framgångar och misslyckanden), efter mästerskapet är alla fotbollslag placerade i en viss ordning, etc. Det finns en operationsordning när man tillverkar en del, ordföljd i en mening (försök att förstå vad meningen "på den gamle mannen" betyder att jag inte planterade åsnan!" Genom att arrangera elementen i en viss uppsättning efter varandra, ordnar vi dem eller upprättar någon relation mellan dem i ordning. Det enklaste exemplet är den naturliga ordningen för de naturliga talen. Dess naturlighet ligger i det faktum att vi för två naturliga tal vet vilket som följer efter det andra eller vilket som är större än det andra, så vi kan ordna de naturliga talen i en sekvens så att det större talet är placerat, till exempel till höger om den mindre: 1, 2, 3, ... . Naturligtvis kan sekvensen av element skrivas i vilken riktning som helst, inte bara från vänster till höger. Själva begreppet naturliga tal innehåller redan idén om ordning. Genom att etablera ett relativt arrangemang av elementen i vilken mängd som helst, definierar vi därigenom en binär ordningsrelation på den, som i varje specifikt fall kan ha sitt eget namn, till exempel "att vara mindre", "att vara äldre", "att vara äldre", ingå i ", "följa" etc. Symboliska ordningsbeteckningar kan också varieras, till exempel Í osv. Det främsta utmärkande kännetecknet för en ordningsrelation är att den har egenskapen transitivitet. Så, om vi har att göra med en sekvens av några objekt x 1, x 2, ..., x n,..., ordnat till exempel efter relation, sedan från det som utförs x 1x 2... x n..., det bör följa det för vilket par som helst x i, x j delar av denna sekvens är också uppfyllda x ix j: För ett par element x ij i relationsgrafen ritar vi en pil från vertexet x i till toppen x j, dvs från det mindre elementet till det större. Ordningsrelationsgrafen kan förenklas genom att använda den så kallade metoden Hasse diagram. Hasse-diagrammet är konstruerat enligt följande. Mindre element placeras lägre och större placeras högre. Eftersom en sådan regel inte ensam räcker för avbildning, ritas linjer som visar vilket av de två elementen som är större och vilket som är mindre än det andra. I det här fallet räcker det att bara rita linjer för elementen omedelbart efter varandra. Exempel på Hasse-diagram visas i figuren: Du behöver inte inkludera pilar i ett Hasse-diagram. Hasse-diagrammet kan roteras i ett plan, men inte godtyckligt. Vid svängning är det nödvändigt att bibehålla den relativa positionen (ovanför - nedan) för diagrammets hörn: Attityd R i överflöd X kallad attityd av strikt ordning, om den är transitiv och asymmetrisk. En uppsättning där en strikt ordningsrelation definieras kallas beordrade. Till exempel är mängden naturliga tal ordnad efter relationen "mindre än". Men samma uppsättning är också ordnad efter en annan relation - "delad i" och "mer". Grafen för relationen "mindre än" i uppsättningen naturliga tal kan avbildas som en stråle: Attityd R V X kallas relation icke-strikt (partiell) ordning, om den är transitiv och antisymmetrisk. Varje förhållande av icke-strikt ordning är reflexivt. Epitetet "partiell" uttrycker det faktum att kanske inte alla delar av en uppsättning är jämförbara i ett givet avseende. Typiska exempel på partiella ordningsrelationer är relationerna "inte större än", "inte mindre än" och "inte större än". Partikeln "inte" i relationernas namn tjänar till att uttrycka deras reflexivitet. Relationen "inte mer än" sammanfaller med relationen "mindre än eller lika", och relationen "inte mindre" är detsamma som "större än eller lika". I detta avseende kallas också partiell ordning inte strikt i ordning. Ofta betecknas en partiell (icke-strikt) ordningsrelation med symbolen "". Inklusionsrelationen Í mellan delmängder av en viss mängd är också en partiell ordning. Uppenbarligen är inte varannan delmängd jämförbar i detta avseende. Figuren nedan visar den partiella inkluderingsordningen på uppsättningen av alla delmängder av uppsättningen (1,2,3). Pilarna på grafen som ska peka uppåt visas inte. Uppsättningar på vilka delordning ges anropas delvis beställd, eller bara beordrade set. Element X Och på delvis beställt set kallas jämför med oss Om Xpå eller påX. Annars är de inte jämförbara. En ordnad uppsättning där två valfria element är jämförbara kallas linjärt ordnade, och ordningen är linjär. Linjär ordning kallas också perfekt ordning. Till exempel är mängden av alla reella tal med naturlig ordning, såväl som alla dess delmängder, linjärt ordnade. Föremål av mest varierande karaktär kan beställas hierarkiskt. Här är några exempel. Exempel 1: Delarna i en bok är ordnade så att en bok innehåller kapitel, kapitel innehåller avsnitt och avsnitt innehåller underavsnitt. Exempel 2. Mappar i datorns filsystem är kapslade inuti varandra och bildar en grenstruktur. Exempel 3. Relationen mellan föräldrar och barn kan skildras som den sk släktträd, som visar vem som är vems förfader (eller avkomma). Släpp på uppsättningen A delorder ges. Element X kallad maximum (minimum) element i mängd A, om från det faktum att Xpå(påX), jämställdhet följer X= u. Med andra ord, elementet Xär max (minimum) om för något element på eller är det inte sant det Xpå(påX), eller exekveras X=u. Således är det maximala (minsta) elementet större (mindre) än alla element som skiljer sig från det som det är i relation till. Element X kallad störst (minst), om för någon påÎ A genomförde på< х (х< у).
En delbeställd uppsättning kan ha flera minimi- och/eller maximumelement, men det kan inte finnas mer än ett minimum- och maximumelement. Det minsta (största) elementet är också minimum (maximum), men det omvända är inte sant. Bilden till vänster visar en delordning med två minsta och två maximala element, och till höger en delordning med de minsta och största elementen: I en ändlig, delvis ordnad uppsättning finns det alltid minimum- och maximumelement. En beställd uppsättning som har de största och minsta elementen kallas begränsad. Figuren visar ett exempel på en oändlig avgränsad mängd. Naturligtvis är det omöjligt att avbilda en oändlig uppsättning på en ändlig sida, men du kan visa principen för dess konstruktion. Här visas inte slingorna nära hörnen för att förenkla ritningen. Av samma anledning visas inte bågarna som ger visningen av transitivitetsegenskapen. Figuren visar med andra ord Hasse-diagrammet för ordningsrelationen. Oändliga uppsättningar kanske inte har max- eller minimumelement, eller båda. Till exempel har uppsättningen naturliga tal (1,2, 3, ...) ett minsta element på 1, men inget maximum. Mängden av alla reella tal med naturlig ordning har varken ett minsta eller största element. Men dess delmängd består av alla siffror X<
5, har det största elementet (talet 5), men har inte det minsta. Föreläsningsplan nr 14 Klassificering av binära relationer 1. Klassificering av antisymmetriska relationer Klassificering av antisymmetriska relationer Struktur av acykliska sambandsgrafer Struktur av kvalitativa ordningsrelationsgrafer Struktur av svaga ordningsrelationsgrafer Strikta relationer En strikt ordning (strikt preferens, stark ordning, strikt linjär ordning) är en antireflexiv, transitiv, svagt sammankopplad binär relation (12). Strikt ordning är ett specialfall av svag ordning (strikt partiell preferens) med tilläggsvillkoret svag koppling. Exempel: Relationen "strikt mindre än" på en uppsättning heltal. Klassificering av reflexiva relationer Kvasiordningsrelationer Dessa binära relationer gör det möjligt att jämföra element i en viss mängd, men inte genom likhet, utan genom att arrangera elementen i grupper i en viss ordning, d.v.s. genom delbeställning. En kvasiordning (slapp partiell preferens) är en reflexiv och transitiv binär relation (3). Exempel: "att vara en bror" (Ivan-Peter, Andrey-Anna) Egenskaper för kvasiorder 1. Skärningen av kvasiorder förblir en kvasiordning. Icke strikta partiella ordningsrelationer En icke-strikt partiell ordningsrelation (4) är en relation som har egenskaperna reflexivitet, antisymmetri och transitivitet. En svag partiell ordning är en antisymmetrisk kvasiordning Exempel: "vara del"-relationen definierad för mängder (och deras delmängder) Egenskaper för icke strikta delordrar 1. Skärningen av icke-strikt delorder förblir en icke-strikt delorder. Lösa beställningsrelationer En lös ordning är en reflexiv relation som har den svagt sammankopplade egenskapen (5). En lös beställning kan också definieras som en helt sammankopplad relation. En lös ordningsrelation kan representeras som ett resultat av att kombinera några relationer av tolerans och dominans. Egenskaper för relationer av icke-strikt partiell ordning 1. Skärningen och föreningen av helt sammankopplade relationer förblir en helt sammankopplad relation. Relationer av icke-strikt kvalitativ ordning En binär relation R kallas en icke-strikt kvalitativ ordning om den är negativ-transitiv och helt sammankopplad (6). En icke-strikt kvalitativ ordning är en negativ icke-strikt ordning. Relationen mellan en icke-strikt kvalitativ ordning kan representeras som ett resultat av att kombinera några relationer av tolerans och kvalitativ ordning. Egenskaper för relationer av icke-strikt kvalitativ ordning 1. Den symmetriska delen av den icke-strikta kvalitativa ordningen är tolerans. NT? Icke-strikta svaga ordningsrelationer En icke-strikt svag ordning är en helt sammankopplad transitiv och negativ transitiv relation (7). En helt sammankopplad transitiv relation kallas en icke-strikt svag ordning. En icke-strikt svag ordning är en transitiv icke-strikt ordning. Egenskaper för relationer av icke-strikt svag ordning 1. Den symmetriska delen av en icke-strikt svag ordning är en ekvivalens. Relationer av icke-strikt (linjär) ordning En icke-strikt ordning (en icke-strikt linjär ordning) är en antisymmetrisk, transitiv, helt sammankopplad binär relation (8). En icke-strikt ordning är en antisymmetrisk icke-strikt svag ordning. En icke-strikt ordning är en antisymmetrisk icke-strikt ordning. Egenskaper för relationer av icke-strikt linjär ordning 1. Den symmetriska delen av en icke-strikt ordning är en diagonal. Dualitet av relationer av strikt och icke-strikt ordning Översikt över egenskaper hos olika typer av relationer
7. Konceptet med en tuppel av ett beställt par. Kartesisk produkt av uppsättningar och dess egenskaper. Antalet element i en dekret produkt av mängder. För att introducera konceptet med en kartesisk produkt av uppsättningar, överväg konceptet kortege. Detta koncept, liksom begreppet mängd, är ett grundläggande obestämt begrepp. För en tupel är ordningen på elementen viktig. Element i en tupel kan upprepas. Antalet element i en given tuppel kallas dess längd. En tuppel av längd 2 kallas ett ordnat par. Kortet är betecknat med () eller< >. × är en beteckning för den kartesiska produkten av uppsättningar. (a,b,a); (a,b,c) ≠ (b,a,c); (a,e,c)=(a,e,c). Kartesisk produkt av uppsättningar A och B är en uppsättning som består av alla ordnade par där den första komponenten är ett element i den första uppsättningen och den andra komponenten är ett element i den andra uppsättningen. A=(a,b,c) B=(1,2) A×B=((a,1),(a,2), (c,1),(c,2),(c,1) ,(c,2)) Egenskapen för den kartesiska produkten av uppsättningar (CPM). DPM har inte egenskapen kommutativitet och associativitet: A×B≠B×A. De fördelande egenskaperna för DPM är uppfyllda: 1) med avseende på föreningen av mängder A×(B⋃C)=(A×B)⋃(A×C); 2) angående skärningspunkten mellan mängderna A×(B∩C)=(A×B)∩(A×C). För att hitta antalet element i en DP i två eller flera uppsättningar behöver du veta antalet element i varje uppsättning. Om antalet element är n. Om n(A)=n, och n(B)=m, då n(A×B)=n*m. Låt A=(a1,a2,a3,...an) B=(b1,b2,b3,...bm). Låt oss komponera DPM A och B: (a1,b1) (a1,b2) (a1,b3) ...(a1, bm) (a2,b1) (a2,b2) (a2,b3) ...( a2, bm) (a3 ,в1) (а3,в2) (а3,в3) …(а3,вm) ___________________________ (аn, в1) (аn, в2) (аn, в3) …(аn, вm) I varje rad det finns em-par, sådana linjer sv, det betyder att det totala antalet listade objekt är em on en pairs, därför är antalet element i DPM A och B lika med produkten av antalet element i set A och antalet element i uppsättning B. 8. Begreppet överensstämmelse mellan uppsättningar. Metoder för att specificera efterlevnad. Typer av korrespondenser. Överensstämmelsen ef mellan elementen i mängderna X och Y kallas en trippel av mängder (X;U; G f (ji från ef), ji från ef är en delmängd av DP (kartesisk produkt). Mängden X kallas avgångsregionen, mängden Y kallas ankomstregionen ji från ef - kallas grafen för denna överensstämmelse. Domänen för bestämning av överensstämmelse ef är mängden av de element i den första uppsättningen (d.v.s. avgångsområdet) till vilken elementen i den andra uppsättningen (dvs ankomstområdet) överensstämmer. Uppsättningen av korrespondensvärdet ef är uppsättningen av element i ankomstområdet som i enlighet med vissa delar av avgångsområdet. Metoder för att specificera överensstämmelse: listar dess element, använder en graf, använder en graf, använder en tabell, verbalt, algebraiskt, d.v.s. ekvation, ojämlikhet. Typer av korrespondenser. Korrespondenserna kallas överallt definierat, om sändningsområdet sammanfaller med definitionsområdet. I grafen för en sådan korrespondens avviker åtminstone en pil från varje element i den första uppsättningen. Efterlevnad kallas surjektiv, om dess uppsättning värden sammanfaller med ankomstregionen. I en graf av sådan korrespondens matchar minst 1 pil varje element i den andra uppsättningen. Efterlevnad kallas injektiv, om inga olika element i den 1:a uppsättningen motsvarar samma element i den andra uppsättningen. I en graf av sådan korrespondens matchas inget element i den andra uppsättningen av mer än en pil. Efterlevnad kallas funktionell, om varje element i den 1:a uppsättningen inte motsvarar mer än 1 element i den andra uppsättningen. På en graf av en sådan överensstämmelse, om det bara finns en pil som avviker från varje element i den första uppsättningen. Funktionell korrespondens kallas fungera. Bland alla funktionella korrespondenser finns det universellt definierande korrespondenser, som kallas visa. Efterlevnad kallas en till en, om följande villkor är uppfyllda: 1) alla två olika element i mängden X motsvarar olika element i mängden Y, 2) vilket som helst element i mängden Y motsvarar minst ett element i mängden X. Två överensstämmelser mellan uppsättningarna X och Y kallas motsatt, om deras grafer ömsesidigt kompletterar den kartesiska produkten av X och Y. Korrespondensen kallas omvänd till en given korrespondens om en given korrespondens håller om och endast om det omvända gäller. Om en given överensstämmelse är en delmängd av den kartesiska produkten av mängderna X och Y, så är den omvända överensstämmelsen en delmängd av den kartesiska produkten av mängderna X och Y. För att erhålla den omvända överensstämmelsen med den givna. På dess graf är det nödvändigt att ändra pilarnas riktning.
9.Funktionell efterlevnad. Egenskaper för numeriska funktioner. Efterlevnad kallas funktionell, om varje element i den 1:a uppsättningen inte motsvarar mer än 1 element i den andra uppsättningen. På en graf av en sådan överensstämmelse, om det bara finns en pil som avviker från varje element i den första uppsättningen. En funktionell överensstämmelse definierad på en numerisk uppsättning kallas numerisk kallas fungera. Egenskaper för numeriska funktioner. 1. Varje funktion har en definitionsdomän och en uppsättning värden. 2. Funktionen kan vara ökande eller minskande. En funktion sägs öka på intervallet a b om den för någon x1 och x2 x1 > x2 följer efter f (x1) > f (x2). En funktion kallas att minska på intervallet a b om för någon x1 och x2 från detta intervall, från det faktum att x1 > x2 följer f (x1)< f (x2).
3. функции могут быть четными или не четными. Функция называется четной, если она задана на симметричной области определения и выполняется условие f(-x)=f(x). Функция называется не четной, если на симметричной области определения выполняется условие f(-x)=-f(x). График четной функции симметричен относительно оси ОУ, не четной – симметричен относительно начала координат.
у = х 2 у = х 3
2015-2020 hemsida - Kontakter - Senaste tillskottet
mycket nödvändigt
X=( ;; ; ; ; ) motsvarar uppdelningen av denna mängd i ekvivalensklasser, som var och en består av bråkdelar lika med varandra.
2. Klassificering av reflexiva relationer
2.1. Kvasiordningsrelationer
2.2. Icke strikta partiella ordningsrelationer
2.3. Icke-strängt ordnade relationer
2.4. Lax kvalitetsorder
2.5. Lax svag ordning
2.6. Lös ordning
3. Dualitet av relationer av strikt och icke-strikt ordning
4. Genomgång av egenskaperna hos olika typer av relationer
2. Den symmetriska delen av kvasiordningen har egenskaperna reflexivitet, symmetri och transitivitet och är därför en ekvivalensrelation. Rc = R/R inv
3. Med hjälp av denna skärningspunkt är det möjligt att identifiera grupper av alternativ som är ekvivalenta med varandra, sedan kan en icke-strikt partiell ordningsrelation genererad av den ursprungliga relationen upprättas mellan de valda grupperna.
4. Den asymmetriska delen av kvasiordningen är en transitiv och antireflexiv relation = kvalitativ ordning.
2. Den symmetriska delen av en icke-strikt partiell ordning är en diagonal.
3. Den asymmetriska delen av en icke-strikt partiell ordning är en (strikt) kvalitativ ordning.
4. I teorin om intelligenta system spelas en viktig roll av delvis ordnade uppsättningar - domäner, tillsammans med relationerna av icke-strikt partiell ordning som definieras på dem.
5. Delvis ordnade uppsättningar med den ytterligare egenskapen att det finns övre och nedre gränser för varje par av element kallas gitter. Ett specialfall av gitter är booleska algebror.
2. Den symmetriska delen av den icke-strikta delordningen är tolerans.
3. Den asymmetriska delen av den icke-strikta partiella ordningen är dominans.
4. För helt sammankopplade relationer är en nödvändig förutsättning för transitivitet relationens negativitet.
5. För helt sammankopplade relationer är transitivitetens egenskap ett tillräckligt villkor för relationens negativitet.
2. Den asymmetriska delen av en icke-strikt kvalitativ ordning är transitiv, därför är den en relation av en kvalitativ ordning.
3. Således kan en relation av en icke-strikt kvalitativ ordning representeras som ett resultat av att kombinera toleransrelationerna och kvalitativ ordning som genereras av den ursprungliga relationen.
4. Den dubbla relationen har egenskaperna asymmetri och transitivitet och är därför en relation av kvalitativ ordning.
2. Den asymmetriska delen R ac av en icke-strikt svag ordning är transitiv, därför är den en relation av kvalitativ ordning.
3. Således kan en icke-strikt svag ordningsrelation representeras som ett resultat av att kombinera ekvivalensen och svagordningens relationer som genereras av den ursprungliga relationen.
4. En icke-strikt svag ordning kan representeras som en uppsättning partiellt ordnade lager, som vart och ett är en ekvivalensklass.
2. Den asymmetriska delen R ac av icke-strikt ordning är transitiv och svagt sammankopplad, därför är den en relation av strikt ordning.
3. Den dubbla relationen har egenskaperna asymmetri, negatransitivitet och svag koppling, därför är det en relation av strikt ordning. Dessutom sammanfaller den med R ac.
4. Således kan en icke-strikt ordningsrelation representeras som ett resultat av att kombinera den diagonala och strikta ordningen som genereras av den ursprungliga relationen.
