Ekvivalensrelation och kvotmängd. Ekvivalensrelationer. Faktoruppsättningar Ekvivalensrelationer. Faktoruppsättningar
(det vill säga som har följande egenskaper: varje element i mängden är ekvivalent med sig själv; if x likvärdig y, Den där y likvärdig x; Om x likvärdig y, A y likvärdig z, Den där x likvärdig z ).
Sedan anropas mängden av alla ekvivalensklasser faktoruppsättning och är betecknad. Att dela upp en uppsättning i klasser av ekvivalenta element kallas dess faktorisering.
Visa från X in i uppsättningen av ekvivalensklasser kallas faktorkartläggning.
Exempel
Det är rimligt att använda mängdfaktorisering för att erhålla normerade utrymmen från semi-normerade, utrymmen med en inre produkt från utrymmen med en nästan inre produkt, etc. För att göra detta introducerar vi, respektive, normen för en klass, lika med norm av ett godtyckligt element, och den inre produkten av klasser som en inre produkt av godtyckliga element av klasser. I sin tur introduceras ekvivalensrelationen enligt följande (till exempel för att bilda ett normaliserat kvotutrymme): en delmängd av det ursprungliga seminormerade utrymmet introduceras, bestående av element med noll seminorm (förresten, det är linjärt, det vill säga, det är ett delrum) och det anses att två element är likvärdiga om deras skillnad tillhör just detta delrum.
Om, för att faktorisera ett linjärt rum, ett visst delrum introduceras och det antas att om skillnaden mellan två element i det ursprungliga rummet tillhör detta delrum, då dessa element är ekvivalenta, så är faktormängden ett linjärt rymd och kallas ett faktorutrymme.
Exempel
se även
Wikimedia Foundation. 2010.
Se vad "Factorset" är i andra ordböcker:
Den logiska principen som ligger till grund för definitioner genom abstraktion (Se definition genom abstraktion): alla relationer av typen av likhet, definierade på någon initial uppsättning element, delar (delar, klassificerar) originalet... ...
En form av tänkande som speglar de väsentliga egenskaperna, sambanden och förhållandena hos objekt och fenomen i deras motsägelse och utveckling; en tanke eller system av tankar som generaliserar, särskiljer objekt av en viss klass enligt vissa generella och sammanlagda... ... Stora sovjetiska encyklopedien
Galois gruppkohomologi. Om M är en Abelisk grupp och en Galois-grupp av en förlängning som verkar på M, så är Galois-kohomologigrupperna kohomologigrupper definierade av ett komplex som består av alla kartor, och d är en samgränsoperator (se Kohomologi av grupper).... . .. Matematisk uppslagsverk
Konstruktionen, till paradiset, dök först upp i mängdteorin och blev sedan allmänt använd inom algebra, topologi och andra områden av matematiken. Ett viktigt specialfall av en I. p. är en I. p. av en riktad familj av matematiska strukturer av samma typ. Låt vara … Matematisk uppslagsverk
Poäng även om den är relativt gruppen G som verkar på mängden X (till vänster), är mängden Mängden en undergrupp till G och kallas. stabilisator, eller stationär undergrupp av en punkt med avseende på G. Kartläggningen inducerar en bijektion mellan G/Gx och omloppsbanan G(x). HANDLA OM.… … Matematisk uppslagsverk
Den här artikeln har en för kort introduktion. Lägg till ett inledande avsnitt som kort introducerar artikelns ämne och sammanfattar dess innehåll... Wikipedia
Den här artikeln handlar om det algebraiska systemet. För grenen av matematisk logik som studerar påståenden och operationer på dem, se Algebra of Logic. Boolesk algebra är en icke-tom mängd A med två binära operationer (analogt med en konjunktion), ... ... Wikipedia
Låt ett ekvivalensförhållande ges på en mängd. Då kallas mängden av alla ekvivalensklasser faktormängden och betecknas. Att dela upp en mängd i klasser av ekvivalenta element kallas dess faktorisering. Kartläggning från till... ... Wikipedia
Inom geometri förstås ett riktat segment som ett ordnat par av punkter, varav den första punkten A kallas dess början och den andra B, dess slut. Innehåll 1 Definition ... Wikipedia
Inom olika grenar av matematiken är kärnan i en mappning en viss mängd kerf, vilket på sätt och vis kännetecknar skillnaden mellan f och en injektiv mappning. Den specifika definitionen kan variera, men för den injektiva kartläggningen av... ... Wikipedia
Mängdlära. Grundläggande koncept
Mängdlära är den grundläggande definitionen av modern matematik. Den skapades av Georg Cantor på 1860-talet. Han skrev: "Mångfald är många, tänkt som en enda helhet." Begreppet mängd är ett av de grundläggande, odefinierade begreppen inom matematik. Det går inte att reducera till andra enklare begrepp. Därför kan det inte definieras, utan bara förklaras. Således är en uppsättning en förening till en helhet av objekt som är tydligt urskiljbara av vår intuition eller vår tanke; en samling av vissa föremål som definieras av en gemensam egenskap.
Till exempel,
1. Många invånare i Voronezh
2. Uppsättning planpunkter
3. Uppsättning naturliga tal ℕetc.
Uppsättningar betecknas vanligtvis med stora latinska bokstäver( A, B, C etc.). De objekt som utgör en given mängd kallas dess element. Element i en mängd betecknas med små latinska bokstäver( a, b, c etc.). Om X– ställ in och spela in x∈X betyder att Xär en del av uppsättningen X eller vad X tillhör uppsättningen X, och posten x∉X det elementet X hör inte till uppsättningen X. Låt till exempel ℕ vara mängden naturliga tal. Sedan 5 ℕ , A 0,5∉ℕ .
Om uppsättningen Y består av delar av uppsättningen X, då säger de det Yär en delmängd av uppsättningen X och beteckna Y⊂Х(eller Y⊆Х). Till exempel en uppsättning heltal ℤ är en delmängd av rationella tal ℚ .
Om för två set X Och Y två inneslutningar inträffar samtidigt X Y Och Y X, dvs. Xär en delmängd av uppsättningen Y Och Yär en delmängd av uppsättningen X, sedan uppsättningarna X Och Y består av samma element. Sådana uppsättningar X Och Y kallas lika och skriver: X=Y.
Termen tom uppsättning används ofta - Ø - en uppsättning som inte innehåller ett enda element. Det är en delmängd av vilken uppsättning som helst.
Följande metoder kan användas för att beskriva uppsättningar.
Metoder för att specificera uppsättningar
1. Uppräkning av objekt. Används endast för ändliga uppsättningar.
Till exempel, X=(x1, x2, x3… x n). Y inträde ={1, 4, 7, 5} betyder att uppsättningen består av fyra nummer 1, 4, 7, 5 .
2. Indikation av den karakteristiska egenskapen hos elementen i uppsättningen.
För att göra detta ställs en viss egenskap in R, som låter dig avgöra om ett element tillhör en uppsättning. Denna metod är mer universell.
X=(x: P(x))
(ett gäng X består av sådana element X, som fastigheten innehar P(x)).
En tom uppsättning kan specificeras genom att ange dess egenskaper: Ø=(x: x≠x)
Du kan konstruera nya uppsättningar med hjälp av redan definierade med hjälp av operationer på uppsättningar.
Ställ in operationer
1. En union (summa) är en mängd som består av alla dessa element, som var och en tillhör minst en av mängderna A eller I.
A∪B=(x: x A eller x B).
2. En korsning (produkt) är en mängd som består av alla element, som var och en samtidigt tillhör mängden A, och många I.
A∩B=(x: x A och x B).
3. Ställ in skillnaden A Och Iär en mängd som består av alla de element som hör till mängden A och tillhör inte mängden I.
A\B=(x: x A och x B)
4. Om A– en delmängd av en uppsättning I. Det är mycket B\A kallas komplementet till en uppsättning A för många I och beteckna A'.
5. Den symmetriska skillnaden mellan två uppsättningar är uppsättningen A∆B=(A\B) (B\A)
N- mängden av alla naturliga tal;
Z- mängden av alla heltal;
F- mängden av alla rationella tal;
R- mängden av alla reella tal;
C- mängden av alla komplexa tal;
Z 0- mängden av alla icke-negativa heltal.
Egenskaper för operationer på set:
1. A B=B A (fackets kommutativitet)
2. A B=B A (kommutativitet av skärningspunkt)
3. A(B C)=(A I) C (facklig associativitet)
4. A (I C)=(A I) C (korsningsassociativitet)
5. A (I C)=(A I) (A C) (första fördelningslagen)
6. A (I C)=(A I) (A C) (andra distributionslagen)
7. A Ø=A
8. A U= U
9. A Ø= Ø
10. A U=A
11. (A B)'=A' B' (de Morgans lag)
12. (A B)'=A' B' (de Morgans lag)
13. A (A B)=A (absorptionslag)
14. A (A B)=A (absorptionslag)
Låt oss bevisa egendom nr 11. (A B)'=A' I'
Per definition av lika mängder måste vi bevisa två inneslutningar 1) (A B)’ ⊂A’ I';
2) A' B’⊂(A I)'.
För att bevisa den första inkluderingen, överväg ett godtyckligt element x∈(A B)'=X\(A∪B). Det betyder att x∈X, x∉ A∪B. Det följer att x∉A Och x∉B, Det är därför x∈X\A Och x∈X\B, som betyder x∈A'∩B'. Således, (A B)'⊂A' I'
Tillbaka om x∈A' I', Den där X hör samtidigt till uppsättningar A', B', som betyder x∉A Och x∉B. Det följer att x∉ A I, Det är därför x∈(A I)'. Därav, A' B’⊂(A I)'.
Så, (A B)'=A' I'
En uppsättning som består av två element, där ordningen på elementen är definierad, kallas ett ordnat par. För att skriva det, använd parenteser. (x 1, x 2)– en uppsättning av två element där x 1 anses vara det första elementet och x 2 är det andra. Par (x 1, x 2) Och (x 2, x 1), Var x 1 ≠ x 2, anses olika.
En uppsättning bestående av n element, där ordningen på elementen är definierad, kallas en ordnad uppsättning av n element.
En kartesisk produkt är en godtycklig uppsättning X 1, X 2,..., X n ordnade uppsättningar av n element, där x 1 X 1, x 2 X2,...,xn Xn
X 1 Xn
Om uppsättningarna X 1, X 2,..., X n match (X 1 = X 2 =...=X n), då betecknas deras produkt Xn.
Till exempel, ℝ 2 – en uppsättning ordnade par av reella tal.
Ekvivalensrelationer. Faktoruppsättningar
Baserat på en given uppsättning kan nya uppsättningar konstrueras genom att beakta uppsättningen av vissa delmängder. I det här fallet talar vi vanligtvis inte om en uppsättning delmängder, utan om en familj eller klass av delmängder.
I ett antal frågor beaktas klassen av sådana delmängder av en given uppsättning A, som inte korsar varandra och vars förening sammanfaller med A. Om detta set A kan representeras som en union av dess parvisa disjunkta delmängder, då är det vanligt att säga att A indelade i klasser. Indelningen i klasser utförs på basis av någon egenskap.
Låta Xär inte en tom uppsättning, sedan någon delmängd R från arbetet X X kallas en binär relation på mängden X. Om ett par (x,y) ingår i R, de säger att elementet x är i relationen R Med på.
Till exempel relationer x=y, x≥yär binära relationer på uppsättningen ℝ.
Binär relation R på ett set X kallas en ekvivalensrelation om:
1. (x,x) R; X X (reflexivitetsegenskap)
2. (x,y) R => (y,x) R (symmetriegenskap)
3. (x,y) R, (y, z) R, sedan (x,z) R (transitivitetsegenskap)
Om ett par (x,y) ingått ekvivalensrelationer, då kallas x och y ekvivalenta (x~y).
1. Låt ℤ – en uppsättning heltal, m≥1– ett heltal. Låt oss definiera ekvivalensrelationen R på ℤ så att n~k, Om n-k delat med m. Låt oss kontrollera om egenskaperna är nöjda med denna relation.
1. Reflexivitet.
För vem som helst n∈ℤ ℤ Så att (p,p)∈R
р-р=0. Därför att 0∈ ℤ , Den där (p,p)∈ℤ.
2. Symmetri.
Från (n,k) ∈R det följer att det finns något sådant р∈ℤ, Vad n-k=smp;
k-n =m(-p), -p∈ ℤ, därav (k,n) ∈R.
3. Transitivitet.
Från vad (n,k) ∈R, (k,q) ∈R det följer att det finns sådana p 1 Och р 2 ∈ ℤ, Vad n-k=smp 1 Och k-q=mp 2. Lägger vi till dessa uttryck får vi det n-q=m(p 1 + p 2), p 1 + p 2 = p, p∈ ℤ. Det är därför (n,q) ∈ ℤ.
2. Överväg uppsättningen X alla riktade segment av rymden eller planet . =(A, B). Låt oss introducera ekvivalensrelationen R på X.
Låt G=(p 0 =e, p 1, …, p r) vara en viss grupp av permutationer definierade på mängden X = (1, 2, …, n) med enheten e=p 0 identisk permutation. Låt oss definiera relationen x~y genom att sätta x~y ekvivalent med det faktum att det finns p som hör till G(p(x)=y). Den introducerade relationen är en ekvivalensrelation, det vill säga den uppfyller tre axiom:
1) x~x;
2) x~y→y~x;
3) x~y&y~z→x~z;
Låt A vara en godtycklig mängd.
Definition: En binär relation δ=A*A är en ekvivalensrelation (betecknad med a ~ b) om den uppfyller följande axiom:
∀ a, b, c ∈ A
1) a ~ a – reflexivitet;
2) a ~ b ⇒ b ~ a – kommutativitet;
3) a ~ b & b ~ c → a ~ c - transitivitet
betecknas med a ~ b, σ(a,b), (a,b) ∈ σ, a σ b
Definition: En partition av en mängd A är en familj av parvis disjunkta delmängder av A, som i föreningen (totalt) ger alla A.
А= ∪А i, А i ∩А j = ∅, ∀i ≠ j.
Delmängder A i kallas cosets för partitionen.
Sats: varje ekvivalensrelation som definieras på A motsvarar någon partition av mängden A. Varje partition av mängden A motsvarar någon ekvivalensrelation på mängden A.
Kortfattat: det finns en en-till-en-överensstämmelse mellan klasserna för alla ekvivalensrelationer definierade på mängd A och klassen för alla partitioner i mängd A.
Bevis: låt σ vara en ekvivalensrelation på mängden A. Låt a ∈ A.
Låt oss konstruera en mängd: K a =(x ∈ A,: x~a) – alla element ekvivalenta med a. Mängden (notationen) kallas ekvivalensklassen med avseende på ekvivalensen σ. Observera att om b tillhör K a , då b~a. Låt oss visa att a~b⇔K a =K b . Låt verkligen a~b. Ta ett godtyckligt element c som tillhör Ka . Då hör c~a, a~b, c~b, c till K b och därför hör K b till Ka . Att Ka tillhör K b visas på liknande sätt. Därför är K b =K a.
Låt nu K b =K a . Då hör a till K a = K b , a tillhör K b , a~b. Det var det som behövde visas.
Om 2 klasser Ka och Kb har ett gemensamt element c, så är Ka = Kb. Faktum är att om c tillhör Ka och Kb, då är b~c, c~a, b~a => Ka = Kb.
Därför skärs inte olika ekvivalensklasser eller korsar varandra och sammanfaller sedan. Varje element c i A tillhör endast en ekvivalensklass K c. Därför ger ett system med disjunkta ekvivalensklasser vid skärningspunkten hela mängden A. Och därför är detta system en uppdelning av mängden A i ekvivalensklasser.
Omvänt: Låt A = summa över eller A i är en partition av A. Låt oss introducera relationen a~b på A, eftersom a~b ⇔ a,b tillhör samma partitionsklass. Denna relation uppfyller följande axiom:
1) a ~ a (är i samma klass);
2) a ~ b → b ~ a;
3) a ~ b & b ~ c → a ~ c, dvs. den införda relationen ~ är en ekvivalensrelation.
Kommentar:
1) en partition av en uppsättning A i en-elements delmängder och en partition av A som endast består av mängden A kallas triviala (olämpliga) partitioner.
2) Att dela upp A i enelementsdelmängder motsvarar en ekvivalensrelation som är likhet.
3) Partitioner A, som består av en klass A, motsvarar en ekvivalensrelation som innehåller A x A.
4) a σ b → [a] σ = [b] σ - vilken ekvivalensrelation som helst som definieras på en viss mängd delar upp denna mängd i parvis disjunkta klasser som kallas ekvivalensklasser.
Definition: Mängden ekvivalensklasser för en mängd A kallas kvotmängden A/σ för mängden A genom ekvivalensen σ.
Definition: Mappningen p:A→A/σ, för vilken p(A)=[a] σ, kallas den kanoniska (naturliga) mappningen.
Varje ekvivalensrelation som definieras på en viss uppsättning delar upp denna uppsättning i parvis disjunkta klasser som kallas ekvivalensklasser.
Om attityden R har följande egenskaper: reflexive symmetrical transitive, d.v.s. är en ekvivalensrelation (~ eller ≡ eller E) på uppsättningen M , då kallas uppsättningen av ekvivalensklasser för uppsättningens faktoruppsättning M om likvärdighet R och är utsedd HERR
Det finns en delmängd av element i uppsättningen M likvärdig x , ringde ekvivalensklass.
Av definitionen av en faktormängd följer att det är en delmängd av en boolesk: .
Funktionen kallas Identifiering och definieras enligt följande:
Sats. Faktor algebra F n /~ är isomorft till algebra för booleska funktioner B n
Bevis.
Den erforderliga isomorfismen ξ : F n / ~ → B n bestäms av följande regel: ekvivalensklass ~(φ) funktionen matchas f φ , att ha en sanningstabell för en godtycklig formel från uppsättningen ~(φ) . Eftersom olika ekvivalensklasser motsvarar olika sanningstabeller är kartläggningen ξ injektiv, och sedan för valfri boolesk funktion f från I P det finns en formel som representerar funktionen f, sedan kartläggningen ξ surjektiv. Lagra operationer, 0, 1 när den visas ξ kontrolleras direkt. CTD.
Genom satsen om den funktionella fullständigheten av varje funktion som inte är en konstant 0 , motsvarar viss SDNF ψ , tillhörande klassen ~(φ) = ξ -1 (f) formler som representerar en funktion f . Problemet med att vara i klassrummet uppstår ~(φ) disjunktiv normalform, som har den enklaste strukturen.
Slut på arbetet -
Detta ämne hör till avsnittet:
Kurs med föreläsningar inom disciplinen diskret matematik
Moscow State University of Civil Engineering.. Institute of Management Economics and Information Systems in Construction.. IEEE..
Om du behöver ytterligare material om detta ämne, eller om du inte hittade det du letade efter, rekommenderar vi att du använder sökningen i vår databas med verk:
Vad ska vi göra med det mottagna materialet:
Om detta material var användbart för dig kan du spara det på din sida på sociala nätverk:
| Tweet |
Alla ämnen i detta avsnitt:
Ämne av diskret matematik
Ämnet diskret (ändlig, finit) matematik är en gren av matematiken som studerar egenskaperna hos diskreta strukturer, medan klassisk (kontinuerlig) matematik studerar objektens egenskaper
Isomorfi
Vetenskapen som studerar algebraiska operationer kallas algebra. Detta koncept kommer att bli mer specifikt och fördjupas när du studerar kursen. Algebra är bara intresserad av frågan om HUR man ska agera
Övningar
1. Bevisa att en isomorf kartläggning alltid är isoton, och det omvända är inte sant. 2. Skriv din grupp på uppsättningarnas språk. 3. Skriv ner på språket för uppsättningar objekten som
Set och delar av set
För närvarande skiljer sig befintliga mängdteorier i paradigmatiken (system av åsikter) av den konceptuella grunden och logiska medel. Så som ett exempel kan vi nämna två motsatta
Finita och oändliga mängder
Det som uppsättningen består av, d.v.s. Objekten som utgör en mängd kallas dess element. Elementen i en uppsättning är distinkta och distinkta från varandra. Som framgår av det givna exemplet
Setets kraft
Kardinaliteten för en ändlig mängd är lika med antalet element. Till exempel kardinaliteten för universum B(A) av en uppsättning A av kardinalitet n
A1A2A3| + … + |A1A2A3| + … + |A1A2An| + … + |Аn-2An-1An| + (-1)n-1 |А1A2A3…An|
En finit mängd A har kardinalitet k om den är lika med segmentet 1.. k;:
Delmängd, riktig delmängd
Efter att begreppet en uppsättning introducerats, uppstår uppgiften att konstruera nya uppsättningar från befintliga, det vill säga att definiera operationer på uppsättningar. Set med M",
Symbolspråk för meningsfulla mängdteorier
I arbetet med att studera kursen kommer vi att skilja mellan mängdlärans objektspråk och metaspråket, med hjälp av vilket objektspråket studeras. Med mängdlärans språk menar vi relationell
Bevis
Mängden B är oändlig, vilket betyder
Lägga till och ta bort objekt
Om A är en mängd, och x är ett element, och sedan elementet
Avgränsade uppsättningar. Sätt gränser
Låt en numerisk funktion f(x) ges på någon mängd X. Den övre gränsen (gränsen) för funktionen f(x) är ett sådant tal
Exakt övre (nedre) gräns
Mängden av alla övre gränser E betecknas med Es, och alla nedre gränser med Ei. Om
Uppsättningens exakta övre (nedre) gräns
Om ett element z tillhör skärningspunkten mellan mängden E och mängden av alla dess övre gränser Es (respektive nedre r
Grundläggande egenskaper hos övre och nedre gränser
Låt X vara en delvis ordnad uppsättning. 1. Om, då
Set ur en attributiv synvinkel
Den aggregerade synvinkeln, till skillnad från den attributiva synvinkeln, är logiskt sett ohållbar i den meningen att den leder till paradoxer av typen Russell och Cantor (se nedan). Inom ramen för attributivt t
Strukturera
En partiellt ordnad mängd X kallas en struktur om den innehåller någon uppsättning med två element
Täcknings- och skiljeuppsättningar
En partition av en mängd A är en familj Ai
Binära relationer
En sekvens med längden n, vars termer är a1, .... an, kommer att betecknas med (a1, .... a
Egenskaper för binära relationer
En binär relation R på mängden Ho har följande egenskaper: (a) reflexiv om xRx
Ternära relationer
Kartesisk produkt XY
N-ära relationer
I analogi med den kartesiska produkten av två mängder X,Y kan vi konstruera den kartesiska produkten X
Displayer
Mappningar är några kopplingar mellan element i uppsättningar. De enklaste exemplen på relationer är relationerna för medlemskap x
Korrespondens
En delmängd S av en kartesisk produkt kallas en n-är överensstämmelse mellan element i mängder Mi. Formellt
Fungera
Alla grenar av diskret matematik bygger på funktionsbegreppet. Låt X -
Representerar en funktion när det gäller relationer
En binär relation f kallas en funktion om från och
Injektion, injektion, bijektion
När man använder termen "mappning" skiljer man mellan mappningen XbY och mappningen X på Y
Omvänd funktion
För godtyckliga sådana definierar vi
Delvis beställda set
En mängd S kallas partiellt ordnad (PUM) om den ges en reflexiv, transitiv och antisymmetrisk binär partiell ordningsrelation
Ställ in representationsminimering
Genom att använda dessa lagar överväger vi problemet med att minimera representationen av mängden M med hjälp av operationerna
Omarrangemang
Givet en mängd A. Låt A vara en finit mängd bestående av n element A = (a1, a2, …, a
Permutationer med upprepningar
Låt mängd A ha identiska (repeterande) element. Permutation med upprepningar av komposition (n1, n2, … ,nk
Placeringar
Tuplar med längden k (1≤k≤n), bestående av olika element i n-elementuppsättningen A (tuplarna skiljer sig i
Placeringar med upprepningar
Låt mängd A ha identiska (repeterande) element. Placeringar med upprepningar av n element av k namn
Ordnad placering
Låt oss placera n objekt i m rutor så att varje ruta innehåller en sekvens, och inte, som tidigare, en uppsättning objekt placerade i den. Två
Kombinationer
Från en m-elementuppsättning A konstruerar vi en ordnad uppsättning av längden n, vars element är arrangemang med samma teman
Kombinationer med repetitioner
De resulterande formlerna är endast giltiga när det inte finns några identiska element i mängden A. Låt det finnas element av n typer och från dem en tupel av
Funktionsgenererande metod
Denna metod används för att räkna upp kombinatoriska siffror och fastställa kombinatoriska identiteter. Utgångspunkten är sekvensen (ai) kombinatorn
Algebraiskt system
Ett algebraiskt system A är en samling ‹M,O,R›, vars första komponent M är en icke-tom mängd, den andra komponenten O är en mängd
Stängning och subalgebra
En delmängd sägs vara sluten under operationen φ if
Algebror med en binär operation
Låt en binär operation ges på uppsättningen M. Låt oss överväga de algebror som den genererar, men först kommer vi att överväga några egenskaper hos binära operationer. Binär o
Groupoid
Formens algebra<М, f2>kallas en groupoid. Om f2 är en operation som multiplikation (
Heltal modulo m
Givet en ring av heltal
Kongruenser
Kongruens på algebra A =
Element i grafteori
Grafer är matematiska objekt. Grafteori används inom områden som fysik, kemi, kommunikationsteori, datordesign, elektroteknik, maskinteknik, arkitektur, forskning om
Graf, vertex, kant
Med en oriktad graf (eller kort sagt en graf) menar vi ett sådant godtyckligt par G =
Korrespondens
En annan, oftare använd beskrivning av en riktad graf G består av att specificera en uppsättning av hörn X och en motsvarighet Г, till
Oriktad graf
Om kanterna inte har någon orientering kallas grafen oriktad (oriktad dubblett eller oorienterad
Incidens, blandad graf
Om kanten e har formen (u, v) eller<и, v>, då kommer vi att säga att kanten e är infallande ver
Omvänd matchning
Eftersom det representerar en uppsättning sådana hörn
Grafisomorfism
Två grafer G1 =
Stigorienterad rutt
En väg (eller riktad rutt) för en riktad graf är en sekvens av bågar där
Intilliggande bågar, angränsande hörn, vertexgrad
Bågarna a = (xi, xj), xi ≠ xj, med gemensamma ändhörn, n
Anslutningsmöjligheter
Två hörn i en graf kallas sammankopplade om det finns en enkel väg som förbinder dem. En graf kallas sammankopplad om alla dess hörn är sammankopplade. Sats.
Viktad båggraf
En graf G = (N, A) kallas viktad om någon funktion l: A → R definieras på uppsättningen av bågar A så att
Stark anslutningsmatris
Stark anslutningsmatris: lägg 1 längs diagonalen; fyll i raden X1 - om spetsen kan nås från X1 och X1 d
Träd
Träd är viktiga inte bara för att de hittar tillämpningar inom olika kunskapsområden, utan också för att de har en särställning inom själva grafteorin. Det senare orsakas av den extrema enkelheten i trädets struktur
Alla icke-triviala träd har minst två hängande hörn
Bevis Betrakta trädet G(V, E). Ett träd är därför en sammankopplad graf
Sats
Mitten av ett fritt träd består av en vertex eller två angränsande hörn: Z(G) = 0&k(G) = 1 → C(G) = K1
Regisserade, ordnade och binära träd
Riktade (ordnade) träd är en abstraktion av hierarkiska relationer som mycket ofta påträffas både i det praktiska livet och i matematik och programmering. Träd (orientering)
Bevis
1. Varje båge går in i någon nod. Från paragraf 2 i definition 9.2.1 har vi: v
Beställde träd
Mängderna T1,..., Tk i den ekvivalenta definitionen av orderev är underträd. Om den relativa ordningen för underträden T1,...,
Binära träd
Ett binärt (eller binärt) träd är en ändlig uppsättning noder som antingen är tomma eller består av en rot och två disjunkta binära träd - vänster och höger. Binärt träd inte i java
Gratis trädrepresentation
För att representera träd kan du använda samma tekniker som för att representera allmänna grafer - närliggande och incidensmatriser, närliggande listor och andra. Men med hjälp av de speciella egenskaperna hos
Slut för
Bakgrund Prüfer-koden är verkligen en fri trädrepresentation. För att se detta, låt oss visa att om T" är ett träd
Representation av binära träd
Vilket fritt träd som helst kan orienteras genom att ange en av dess noder som roten. Vilken beställning som helst kan beställas godtyckligt. För ättlingar till en nod (bröder) av en ordnad ordning definieras den relativt
Grundläggande logiska funktioner
Låt oss beteckna med E2 = (0, 1) en mängd som består av två tal. Siffrorna 0 och 1 är grundläggande i en diskret matta
boolesk funktion
En boolesk funktion av n argument x1, x2, … ,xn är en funktion f från n:te potensen av mängden
Boolesk algebra med två element
Låt oss betrakta mängden Во = (0,1) och definiera operationer på den, enligt källtabellerna
Booleska funktionstabeller
En boolesk funktion med n variabler kan specificeras av en tabell som består av två kolumner och 2n rader. Den första kolumnen listar alla uppsättningar från B
F5 – upprepa i y
f6 – summa modulo 2 f7
Ordning för operationer
Om det inte finns några parenteser i ett komplext uttryck, måste operationerna utföras i följande ordning: konjunktion, disjunktion, implikation, ekvivalens, negation. Konventioner angående arrangemanget av Shannons första teorem
För att lösa problemet med att hitta SDNF och SCNF ekvivalenta med den ursprungliga formeln φ, överväger vi först expansionerna av den booleska funktionen f(x1, x2
Shannons andra teorem
I kraft av dualitetsprincipen gäller sats 6.4.3 (Shannons andra sats) för booleska algebror. Vilken boolesk funktion som helst f(x1, x2,...
Funktionell fullständighet
Sats (om funktionell fullständighet). För alla booleska funktioner f finns det en formel φ som representerar funktionen f
Algoritm för att hitta sdnf
För att hitta SDNF måste denna formel först reduceras till DNF och sedan omvandla dess konjunkter till beståndsdelar i enheten med hjälp av följande åtgärder: a) om konjunkten innehåller några
Quines metod
Betrakta Quines metod för att hitta MDNF som representerar en given boolesk funktion. Låt oss definiera följande tre operationer: - komplett limningsoperation -
Kanonisk representation av logiska funktioner
Kanoniska former av logiska (formler) funktioner är uttryck som har standardformen för en boolesk formel så att den unikt representerar en logisk funktion. I algebra
booleska funktionssystem
Låt booleska funktionerna f(g1, g2, …, gm) och g1(x1, x2, …, xn), g2(x1)
Zhegalkin grund
Låt oss prova det. Låt oss titta på systemet. Det är komplett, eftersom alla funktioner från standardbasen uttrycks i termer
Postens sats
Posts sats fastställer nödvändiga och tillräckliga villkor för fullständigheten av ett system av booleska funktioner. (Post E.L. The two-valued interaktiv system of matematic logic. – Annals of Math. Stu
Bevis
Nödvändighet. Från motsatsen. Låt det vara
Zhegalkin algebra Propositionell logik Definition av ett predikat Tillämpning av predikat i algebra Booleskt predikat algebra F↔G=(F→G)(G→F), F→G=inte FG Predikatkalkyl Följd och likvärdighet Godkända noteringar Metabeteckningar Låt R vara en binär relation på mängden X. Relationen R kallas reflekterande
, om (x, x) О R för alla x О X; symmetrisk
– om från (x, y) О R följer det (y, x) О R; det transitiva talet 23 motsvarar alternativ 24 om (x, y) О R och (y, z) О R innebär (x, z) О R. Exempel 1 Vi kommer att säga att x О X har gemensamt
med element y О X, om mängden Ekvivalensförhållande på X är en reflexiv, transitiv och symmetrisk relation. Det är lätt att se att R Í X ´ X kommer att vara en ekvivalensrelation om och endast om inneslutningarna gäller: Id X Í R (reflexivitet), R -1 Í R (symmetri), R ° R Í R (transitivitet). I verkligheten är dessa tre villkor likvärdiga med följande: Id X Í R, R-1 = R, R ° R = R. Genom att splittra av en mängd X är mängden A av parvis disjunkta delmängder a Í X så att UA = X. Med varje partition A kan vi associera en ekvivalensrelation ~ på X, sätta x ~ y om x och y är element i någon a Î A . Varje ekvivalensrelation ~ på X motsvarar en partition A, vars element är delmängder, som var och en består av de i relationen ~. Dessa delmängder kallas ekvivalensklasser
. Denna partition A kallas faktormängden för mängden X med avseende på ~ och betecknas: X/~. Låt oss definiera relationen ~ på mängden w av naturliga tal, och sätta x ~ y om resten av att dividera x och y med 3 är lika. Sedan består w/~ av tre ekvivalensklasser som motsvarar resten 0, 1 och 2. Beställningsförhållande En binär relation R på en mängd X kallas antisymmetrisk
, om från x R y och y R x följer: x = y. En binär relation R på en mängd X kallas beställningsförhållande
, om den är reflexiv, antisymmetrisk och transitiv. Det är lätt att se att detta motsvarar följande villkor: 1) Id X Í R (reflexivitet), 2) R Ç R -1 (antisymmetri), 3) R ° R Í R (transitivitet). Ett ordnat par (X, R) som består av en mängd X och en ordningsrelation R på X kallas delvis beställt set
. Exempel 1 Låt X = (0, 1, 2, 3), R = ((0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2) (1, 3), (2, 2), (3, 3)). Eftersom R uppfyller villkoren 1 – 3, är (X, R) en delvis ordnad uppsättning. För element x = 2, y = 3, är varken x R y eller y R x sanna. Sådana element kallas makalös
. Vanligtvis betecknas orderrelationen med £. I det givna exemplet, 0 £ 1 och 2 £ 2, men det är inte sant att 2 £ 3. Exempel 2 Låta< – бинарное отношение строгого неравенства на множестве w натуральных чисел, рассмотренное в разд. 1.2. Тогда объединение отношений = и < является отношением порядка £ на w и превращает w в частично упорядоченное множество. Elementen x, y О X i en delvis ordnad mängd (X, £) anropas jämförbar
, om x £ y eller y £ x. En delvis ordnad uppsättning (X, £) anropas linjärt ordnade
eller kedja
, om två av dess element är jämförbara. Uppsättningen från exempel 2 kommer att ordnas linjärt, men uppsättningen från exempel 1 kommer inte att göra det. En delmängd A Í X av en delvis ordnad mängd (X, £) anropas avgränsat ovan
, om det finns ett element x О X så att en £ x för alla a О A. Elementet x О X kallas den största
i X om y £ x för alla y О X. Ett element x О X kallas maximalt om det inte finns några element y О X som skiljer sig från x för vilka x £ y. I exempel 1 kommer element 2 och 3 att vara det högsta, men inte det största. Liknande definierad lägre gräns
delmängder, minsta och minimala element. I exempel 1 kommer element 0 att vara både det minsta och det minsta. I exempel 2 har 0 också dessa egenskaper, men (w, £) har varken det största eller maximala elementet.
Summan modulo 2, konjunktionen och konstanterna 0 och 1 bildar ett funktionellt komplett system, d.v.s. bilda en algebra - Zhegalkin algebra. A=
Matematisk logik studerar de grundläggande begreppen syntax (form) och semantik (innehåll) av naturligt språk. Låt oss överväga tre stora forskningsområden inom matematisk logik - logik
Låt X1, X2, ..., Xn vara godtyckliga variabler. Vi kommer att kalla dessa variabler för subjektvariabler. Låt variabeln ställa in dig
Låt oss överväga predikat där endast en variabel är fri, som vi betecknar med x, och diskutera användningen av predikat i algebra. Ett typiskt exempel
Eftersom logiska operationer kan tillämpas på predikat är de grundläggande lagarna för boolesk algebra giltiga för dem. Sats. (Egenskaper för logiska operationer för predikat). Mn
2. Använd lagen inte inte F=F, de Morgans lagar: inte (F
Predikatkalkyl kallas också första ordningens teori. I predikatkalkylen, liksom i satskalkylen, är den första viktigaste platsen problemet med lösbarheten.
Propositionsformen Q2 följer av propositionsformen Q1 om implikationen Q1→Q2 blir sann
Symboler för "beställ inte mer". När man jämför tillväxthastigheten för två funktioner f(n) och g(n) (med icke-negativa värden) är följande mycket praktiskt
Symboler Innehåll Exempel ELLER
x Ç y är inte tom. Relationen att ha gemensamt kommer att vara reflexiv och symmetrisk, men inte transitiv.
