Pieņemsim, ka R ir kopas X bināra relācija. Tiek izsaukta relācija R atstarojošs , ja (x, x) О R visiem x О X; simetrisks – ja no (x, y) О R seko (y, x) О R; pārejas skaitlis 23 atbilst 24. opcijai, ja (x, y) О R un (y, z) О R nozīmē (x, z) О R.

1. piemērs

Mēs teiksim, ka x О X ir kopīgs ar elementu y О X, ja kopa
x Ç y nav tukšs. Kopīgā saistība būs refleksīva un simetriska, bet ne pārejoša.

Ekvivalences attiecība uz X ir refleksīva, pārejoša un simetriska attiecība. Ir viegli saprast, ka R Í X ´ X būs ekvivalences relācija tad un tikai tad, ja ieslēgumi atbilst:

Id X Í R (refleksivitāte),

R -1 Í R (simetrija),

R ° R Í R (transitivitāte).

Patiesībā šie trīs nosacījumi ir līdzvērtīgi šādiem:

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

Ar sadalīšanu kopas X ir pa pāriem disjunktu apakškopu kopa A Í X tā, ka UA = X. Ar katru nodalījumu A mēs varam saistīt ekvivalences relāciju ~ ar X, liekot x ~ y, ja x un y ir kādas a Î A elementi. .

Katra ekvivalences relācija ~ uz X atbilst nodalījumam A, kura elementi ir apakškopas, no kurām katra sastāv no relācijā ~ esošajiem. Šīs apakškopas sauc ekvivalences klases . Šo nodalījumu A sauc par kopas X faktoru kopu attiecībā pret ~ un apzīmē: X/~.

Definēsim attiecību ~ uz naturālu skaitļu kopas w, liekot x ~ y, ja atlikumi no x un y dalīšanas ar 3 ir vienādi. Tad w/~ sastāv no trim ekvivalences klasēm, kas atbilst atlikumiem 0, 1 un 2.

Pasūtījuma attiecības

Tiek izsaukta binārā relācija R uz kopas X antisimetrisks , ja no x R y un y R x izriet: x = y. Tiek izsaukta binārā relācija R uz kopas X pasūtījuma attiecības , ja tas ir refleksīvs, antisimetrisks un pārejošs. Ir viegli saprast, ka tas ir līdzvērtīgs šādiem nosacījumiem:

1) Id X Í R (refleksivitāte),

2) R Ç R -1 (antisimetrija),

3) R ° R Í R (transitivitāte).

Tiek izsaukts sakārtots pāris (X, R), kas sastāv no kopas X un secības attiecības R uz X daļēji pasūtīts komplekts .

1. piemērs

Pieņemsim, ka X = (0, 1, 2, 3), R = ((0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2) ), (1, 3), (2, 2), (3, 3)).

Tā kā R atbilst nosacījumiem 1 – 3, tad (X, R) ir daļēji sakārtota kopa. Elementiem x = 2, y = 3 ne x R y, ne y R x nav patiess. Tādus elementus sauc nesalīdzināms . Parasti pasūtījuma attiecību apzīmē ar £. Norādītajā piemērā 0 £ 1 un 2 £ 2, taču tā nav taisnība, ka 2 £ 3.

2. piemērs

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

Tiek izsaukti daļēji sakārtotas kopas (X, £) elementi x, y О X salīdzināmi , ja x £ y vai y £ x.

Tiek izsaukta daļēji sakārtota kopa (X, £). lineāri sakārtots vai ķēde , ja kādi divi tā elementi ir salīdzināmi. Kopa no 2. piemēra tiks sakārtota lineāri, bet kopa no 1. piemēra netiks sakārtota.

Tiek izsaukta daļēji sakārtotas kopas (X, £) apakškopa A Í X robežojas augstāk , ja ir tāds elements x О X, ka £ x visiem a О A. Elementu x О X sauc lielākais X, ja y £ x visiem y О X. Elementu x О X sauc par maksimālo, ja nav elementu y О X, kas atšķiras no x, kuram x £ y. 1. piemērā elementi 2 un 3 būs maksimālie, bet ne lielākie. Līdzīgi definēts apakšējā robeža apakškopas, mazākie un minimālie elementi. 1. piemērā elements 0 būs gan mazākais, gan minimālais. 2. piemērā 0 arī ir šīs īpašības, bet (w, £) nav ne lielākā, ne maksimālā elementa.

Lai (X, £) ir daļēji sakārtota kopa, A Í X ir apakškopa. Relācija uz A, kas sastāv no elementu a, b О A pāriem (a, b), kuriem a £ b, būs secības relācija uz A. Šo attiecību apzīmē ar to pašu simbolu: £. Tādējādi (A, £) ir daļēji sakārtota kopa. Ja tas ir lineāri sakārtots, tad teiksim, ka A ir ķēde (X, £).

Maksimālais princips

Dažus matemātiskos apgalvojumus nevar pierādīt bez izvēles aksiomas. Tiek teikts, ka šie paziņojumi ir atkarīgs no izvēles aksiomas vai derīga ZFC teorijā , praksē izvēles aksiomas vietā pierādīšanai parasti izmanto vai nu Zermelo aksiomu, vai Kuratovska-Zorna lemmu, vai jebkuru citu apgalvojumu, kas līdzvērtīgs izvēles aksiomai.

Kuratovskis-Zorns Lemma. Ja katra ķēde daļēji pasūtītā komplektā(X, £) ir ierobežots no augšas, tad iekšā X ir vismaz viens maksimālais elements.

Šī lemma ir līdzvērtīga izvēles aksiomai, un tāpēc to var pieņemt kā aksiomu.

Teorēma.Jebkuram daļēji pasūtītam komplektam(X, £) ir relācija, kas satur attiecību£ un pārveidojot X lineāri sakārtotā komplektā.

Pierādījums. Visu secības attiecību kopa, kas satur relāciju £, tiek sakārtota pēc iekļaušanas relācijas U. Tā kā secības attiecību ķēdes savienība būs secības relācija, tad pēc Kuratovska-Zorna lemmas pastāv tāda maksimālā attiecība R, ka x £ y nozīmē x R y. Pierādīsim, ka R ir relācija, kas lineāri sakārtota X. Pieņemsim pretējo: eksistē a, b О X tā, ka ne (a, b), ne (b, a) nepieder R. Aplūkosim sakarību:

R¢ = R È ((x, y): x Ra un b R y).

To iegūst, pievienojot pāri (a, b) R un pārus (x, y), kas jāpievieno R¢ no nosacījuma, ka R¢ ir kārtas relācija. Ir viegli redzēt, ka R¢ ir refleksīvs, antisimetrisks un pārejošs. Iegūstam R Ì R¢, kas ir pretrunā ar R maksimumu, tāpēc R ir vēlamā lineārās kārtas sakarība.

Lineāri sakārtotu kopu X sauc par labi sakārtotu, ja katra tās netukšā apakškopa A Í X satur mazāko elementu a Î A. Kuratovska-Zorna lemma un izvēles aksioma ir līdzvērtīgas arī šādam apgalvojumam:

Cermelo aksioma. Katram komplektam ir pasūtījuma attiecība, kas to pārvērš par pilnībā sakārtotu komplektu.

Piemēram, naturālo skaitļu kopa w ir pilnībā sakārtota. Induktivitātes princips ir apkopots šādi:

Transfinita indukcija. Ja(X, £) ir pilnībā sakārtota kopa, un F(x) ir tās elementu īpašība, patiess mazākajam elementam x 0 О X un tāds, ka no F(y) patiesības visiem y < z следует истинность F(z), то F(x) taisnība visiem x О X .

Šeit y< z означает, что у £ z, но y ¹ z. Действительно, в противном случае среди x Î X, не обладающих свойством F(x), можно выбрать наименьший элемент x 1 , и выполнение F(y) для всех y < x 1 приводит к выполнению F(x 1), противоречащему предположению.

Jaudas jēdziens

Lai f: X à Y un g: Y à Z ir kopu kartes. Tā kā f un g ir attiecības, to sastāvs ir definēts g ° f(x) = g(f(x)). Ja h: Z à T ir kopu karte, tad h ° (g ° f) = (h ° g) ° f. Sakarības Id X un Id Y ir funkcijas, tāpēc ir definētas kompozīcijas Id Y ° f = f ° Id x = f. Ja X = Y, mēs definējam f 2 = f ° f, f 3 = f 2 ° f, ..., f n+1 = f n ° f.

Tiek izsaukta kartēšana f: X àY ar injekciju palīdzību , ja kādiem kopas X elementiem x 1 ¹ x 2, f(x 1) ¹ f(x 2) ir patiess. Tiek izsaukta kartēšana f surjekcija , ja katram y ОY ir tāds x О X, ka f(x) = y. Ja f ir gan surjekcija, gan injekcija, tad f sauc bijekcija . Ir viegli redzēt, ka f ir bijekcija tad un tikai tad, ja apgrieztā attiecība f -1 Í Y ´ X ir funkcija.

Teiksim, ka vienādība |X| = |Y|, ja starp X un Y ir bijekcija. Pieņemsim, ka |X| £ |Y|, ja ir injekcija f: X à Y.

Kantora-Šrēdera-Bernšteina teorēma. Ja|X| £ |Y| Un|Y| £ |X| , Tas|X| = |Y|.

Pierādījums. Pēc nosacījuma ir injekcijas f: X à Y un g: Y à X. Lai A = g¢¢Y = Img ir kopas Y attēls attiecībā pret kartējumu g. Tad

(X \ A) Ç (gf)¢¢ (X \ A) = Æ,

(gf)¢¢(X \ A) Ç (gf) 2 ¢¢ (X \ A) = Æ, …,

(gf) n ¢¢(X \ A) Ç (gf) n+1 ¢¢(X \ A) = Æ, …

Apsveriet kartējumu j: X à A, kas dots kā j(x) = gf(x), ar

x Î (X \ A) È (gf)¢¢(X \ A) È (gf) 2 ¢¢(X \ A) È … un j(x) = x citos gadījumos. Ir viegli redzēt, ka j ir bijekcija. Nepieciešamā bijekcija starp X un Y būs vienāda ar g -1 ° j.

Kantora antinomija

Let |X|< |Y|, если |X| £ |Y| и не существует биекции между X и Y.

Kantora teorēma. Jebkurai kopai X, |X|< |P(X)|, где P(X) – множество всех подмножеств множества X.

(tas ir, kam ir šādas īpašības: katrs kopas elements ir līdzvērtīgs pats sev; ja x ekvivalents y, Tas y ekvivalents x; Ja x ekvivalents y, A y ekvivalents z, Tas x ekvivalents z ).

Tad tiek izsaukta visu ekvivalences klašu kopa faktoru kopa un ir apzīmēts. Kopas sadalīšanu līdzvērtīgu elementu klasēs sauc par kopu faktorizēšana.

Displejs no X tiek izsaukts ekvivalences klašu komplektā faktoru kartēšana.

Piemēri

Ir saprātīgi izmantot kopu faktorizāciju, lai iegūtu normētas telpas no pusnormatīvām, telpas ar iekšējo reizinājumu no telpām ar gandrīz iekšējo reizinājumu utt. Lai to izdarītu, mēs attiecīgi ieviešam klases normu, kas vienāda ar patvaļīga elementa norma un klašu iekšējais reizinājums kā patvaļīgu klašu elementu iekšējais reizinājums. Savukārt ekvivalences sakarība tiek ieviesta šādi (piemēram, lai izveidotu normalizētu koeficientu telpu): tiek ieviesta sākotnējās seminormētās telpas apakškopa, kas sastāv no elementiem ar nulles pusnormu (starp citu, tā ir lineāra, t.i. tā ir apakštelpa), un tiek uzskatīts, ka divi elementi ir līdzvērtīgi, ja to atšķirība pieder tieši šai apakštelpai.

Ja, lai faktorizētu lineāro telpu, tiek ieviesta noteikta apakštelpa un pieņemts, ka, ja divu sākotnējās telpas elementu atšķirība pieder šai apakštelpai, tad šie elementi ir ekvivalenti, tad faktoru kopa ir lineāra telpa un tiek saukta faktoru telpa.

Piemēri

Skatīt arī

Wikimedia fonds. 2010. gads.

Skatiet, kas ir “Factorset” citās vārdnīcās:

Loģiskais princips, kas ir definīciju pamatā, izmantojot abstrakciju (sk. Definīcija caur abstrakciju): jebkura vienlīdzības veida saistība, kas definēta uz kādu sākotnējo elementu kopu, sadala (dala, klasificē) sākotnējo... ...

Domāšanas forma, kas atspoguļo priekšmetu un parādību būtiskās īpašības, sakarības un attiecības to pretrunā un attīstībā; doma vai domu sistēma, kas vispārina, atšķir noteiktas klases objektus pēc noteikta vispārīga un kopumā... ... Lielā padomju enciklopēdija

Galois grupas kohomoloģija. Ja M ir Ābela grupa un Galois grupa paplašinājumam, kas iedarbojas uz M, tad Galuā kohomoloģijas grupas ir kohomoloģijas grupas, kuras definē komplekss, kas sastāv no visām kartēm, un d ir līdzrobežu operators (sk. Grupu kohomoloģija). .. Matemātiskā enciklopēdija

Paradīzes konstrukcija vispirms parādījās kopu teorijā un pēc tam tika plaši izmantota algebrā, topoloģijā un citās matemātikas jomās. Svarīgs īpašs I.p. gadījums ir tāda paša veida matemātisko struktūru virzītas ģimenes I.p. Lai ir… Matemātiskā enciklopēdija

Punkti, lai gan attiecībā pret grupu G, kas darbojas kopā X (kreisajā pusē), kopa ir G apakšgrupa un tiek izsaukta. stabilizators jeb stacionāra punkta apakšgrupa attiecībā pret G. Kartēšana inducē bijekciju starp G/Gx un orbītu G(x). PAR…… Matemātiskā enciklopēdija

Šajā rakstā ir pārāk īss ievads. Lūdzu, pievienojiet ievada sadaļu, kas īsi ievada raksta tēmu un apkopo tā saturu... Wikipedia

Šis raksts ir par algebrisko sistēmu. Matemātiskās loģikas nozari, kas pēta apgalvojumus un darbības ar tiem, skatiet sadaļā Loģikas algebra. Būla algebra ir netukša kopa A ar divām binārām operācijām (analogi savienojumam), ... ... Wikipedia

Ļaujiet kopai dot ekvivalences attiecību. Tad visu ekvivalences klašu kopu sauc par faktoru kopu un apzīmē. Kopas sadalīšanu līdzvērtīgu elementu klasēs sauc par tās faktorizāciju. Kartēšana no līdz... ... Wikipedia

Ģeometrijā ar virzītu segmentu saprot sakārtotu punktu pāri, no kuriem pirmo, punktu A, sauc par tā sākumu, bet otro, B, par tā beigām. Saturs 1 Definīcija ... Wikipedia

Dažādās matemātikas nozarēs kartējuma kodols ir noteikta kopa, kas savā ziņā raksturo atšķirību starp f un injektīvo kartēšanu. Konkrētā definīcija var atšķirties, bet injektīvajai kartēšanai f... ... Wikipedia

Darba avots: 10_20. uzdevums. Vienotais valsts eksāmens 2018 Sociālās zinības. Risinājums

20. uzdevums. Izlasiet zemāk esošo tekstu, kurā trūkst vairāku vārdu (frāžu). Atlasiet vārdu (frāžu) sarakstā, kas jāievieto atstarpju vietā.

“Dzīves kvalitāte ir atkarīga no daudziem faktoriem, sākot no personas dzīvesvietas līdz vispārējai sociāli ekonomiskajai un (A) situācijai, kā arī politisko lietu stāvoklim valstī. Dzīves kvalitāti vienā vai otrā pakāpē var ietekmēt demogrāfiskā situācija, mājokļu un ražošanas apstākļi, _____(B) apjoms un kvalitāte utt. Atkarībā no vajadzību apmierināšanas pakāpes ekonomikā ir ierasts izdalīt dažādus iedzīvotāju dzīves līmeņus: bagātība - izmantošana (B) nodrošinot visaptverošu cilvēka attīstību; normāls _____(G) līmenis pēc zinātniski pamatotiem standartiem, nodrošinot cilvēkam viņa fizisko un intelektuālo spēku atjaunošanu; nabadzība - preču patēriņš darbaspēju saglabāšanas līmenī kā reprodukcijas zemākā robeža _____(D); Nabadzība ir minimālā pieņemamā preču un pakalpojumu kopuma patēriņš pēc bioloģiskiem kritērijiem, kas tikai ļauj saglabāt cilvēka dzīvotspēju.

Iedzīvotāji, pielāgojoties tirgus apstākļiem, izmanto dažādus papildu ienākumu avotus, tajā skaitā ienākumus no personīgajiem zemes gabaliem, peļņu no _____(E).”

Vārdi (frāzes) sarakstā norādīti nominatīvā gadījumā. Katru vārdu (frāzi) var lietot tikai vienu reizi.

Izvēlieties vienu vārdu (frāzi) pēc otra, garīgi aizpildot katru tukšumu. Lūdzu, ņemiet vērā, ka sarakstā ir vairāk vārdu (frāžu), nekā jums būs nepieciešams, lai aizpildītu nepilnības.

Terminu saraksts:

1) kapitāls

2) vides

3) racionāls patēriņš

4) patēriņa preces

5) ražošanas līdzekļi

7) darbaspēks

8) uzņēmējdarbība

9) sociālā mobilitāte

Risinājums.

Ievietosim terminus tekstā.

“Dzīves kvalitāte ir atkarīga no daudziem faktoriem, sākot no personas dzīvesvietas līdz vispārējai sociāli ekonomiskajai un vides (2) (A) situācijai, kā arī no politisko lietu stāvokļa valstī. Dzīves kvalitāti vienā vai otrā pakāpē var ietekmēt demogrāfiskā situācija, mājokļu un ražošanas apstākļi, patēriņa preču apjoms un kvalitāte (4) (B) utt. Atkarībā no vajadzību apmierināšanas pakāpes valstī. ekonomiku, ir pieņemts izdalīt dažādus iedzīvotāju dzīves līmeņus : bagātība - pabalstu izmantošana (6) (B), kas nodrošina cilvēka vispusīgu attīstību; normāls racionāla patēriņa līmenis (3) (D) pēc zinātniski pamatotiem standartiem, nodrošinot personai viņa fizisko un intelektuālo spēku atjaunošanu; nabadzība - preču patēriņš darbaspēju saglabāšanas līmenī kā darbaspēka atražošanas zemākā robeža (7) (D); Nabadzība ir minimālā pieņemamā preču un pakalpojumu kopuma patēriņš pēc bioloģiskiem kritērijiem, kas tikai ļauj saglabāt cilvēka dzīvotspēju.

Ja attieksme R ir šādas īpašības: refleksīvs simetrisks pārejošs, t.i. ir ekvivalences attiecība (~ vai ≡ vai E) kopā M , tad ekvivalences klašu kopu sauc par kopas faktoru kopu M attiecībā uz līdzvērtību R un ir norādīts M/R

Ir kopas elementu apakškopa M ekvivalents x , zvanīja ekvivalences klase.

No faktoru kopas definīcijas izriet, ka tā ir Būla apakškopa: .

Funkcija tiek izsaukta identifikācija un ir definēts šādi:

Teorēma. Faktoru algebra F n /~ ir izomorfs Būla funkciju algebrai B n

Pierādījums.

Nepieciešamais izomorfisms ξ : F n / ~ → B n nosaka ar šādu noteikumu: ekvivalences klase ~(φ) funkcija ir saskaņota f φ , kam ir patiesības tabula patvaļīgai formulai no kopas ~(φ) . Tā kā dažādas ekvivalences klases atbilst dažādām patiesības tabulām, kartēšana ξ injektīvs un tā kā jebkurai Būla funkcijai f no lpp ir formula, kas attēlo funkciju f, tad kartēšana ξ surjektīvs. Saglabāšanas darbības, 0, 1, kad tiek parādīts ξ tiek pārbaudīts tieši. CTD.

Ar teorēmu par katras funkcijas, kas nav konstante, funkcionālo pilnīgumu 0 , atbilst kādam SDNF ψ , kas pieder klasei ~(φ) = ξ -1 (f) formulas, kas attēlo funkciju f . Rodas problēma atrasties klasē ~(φ) disjunktīvā normālā forma, kurai ir visvienkāršākā struktūra.

Darba beigas -

Šī tēma pieder:

Lekciju kurss disciplīnā diskrētā matemātika

Maskavas Valsts Būvniecības universitāte.. Vadības ekonomikas un informācijas sistēmu institūts būvniecībā.. IEEE..

Ja jums ir nepieciešams papildu materiāls par šo tēmu vai jūs neatradāt to, ko meklējāt, mēs iesakām izmantot meklēšanu mūsu darbu datubāzē:

Ko darīsim ar saņemto materiālu:

Ja šis materiāls jums bija noderīgs, varat to saglabāt savā lapā sociālajos tīklos:

Čivināt

Visas tēmas šajā sadaļā:

Diskrētās matemātikas priekšmets
Diskrētās (galīgās, galīgās) matemātikas priekšmets ir matemātikas nozare, kas pēta diskrētu struktūru īpašības, savukārt klasiskā (nepārtrauktā) matemātika pēta objektu īpašības.

Izomorfisms
Zinātni, kas pēta algebriskās darbības, sauc par algebru. Šī koncepcija kļūs specifiskāka un padziļinās, apgūstot kursu. Algebru interesē tikai jautājums, KĀ rīkoties

Vingrinājumi
1. Pierādiet, ka izomorfā kartēšana vienmēr ir izotona un otrādi nav taisnība. 2. Uzrakstiet savu grupu kopu valodā. 3. Kopu valodā pierakstiet objektus, kas

Kopa un komplekta elementi
Šobrīd pastāvošās kopu teorijas atšķiras pēc konceptuālās bāzes un loģisko līdzekļu paradigmātikas (uzskatu sistēmas). Tātad, kā piemēru varam minēt divus pretējus

Ierobežotas un bezgalīgas kopas
Tas, no kā sastāv komplekts, t.i. Objektus, kas veido kopu, sauc par tās elementiem. Komplekta elementi ir atšķirīgi un atšķiras viens no otra. Kā redzams no dotā piemēra

Komplekta jauda
Galīgas kopas kardinalitāte ir vienāda ar tās elementu skaitu. Piemēram, visuma B(A) kardinalitāte kopai A ar kardinalitāti n

A1A2A3| + … + |A1A2A3| + … + |A1A2An| + … + |Аn-2An-1An| + (-1)n-1 |А1A2A3…An|
Galīgai kopai A ir kardinalitāte k, ja tā ir vienāda ar segmentu 1.. k;:

Apakškopa, pareiza apakškopa
Pēc kopas jēdziena ieviešanas rodas problēma konstruēt jaunas kopas no esošajām, tas ir, noteikt darbības ar kopām. M komplekts",

Nozīmīgo kopu teoriju simboliskā valoda
Kursa apguves procesā nošķirsim kopu teorijas objektu valodu no metavalodas, ar kuras palīdzību tiek pētīta objektu valoda. Ar kopu teorijas valodu mēs saprotam relāciju

Pierādījums
Kopa B ir bezgalīga, kas nozīmē

Vienumu pievienošana un noņemšana
Ja A ir kopa un x ir elements, tad elements

Ierobežoti komplekti. Nosakiet robežas
Lai kādai kopai X ir dota skaitliska funkcija f(x). Funkcijas f(x) augšējā robeža (robeža) ir šāds skaitlis

Precīza augšējā (apakšējā) robeža
Visu E augšējo robežu kopa tiek apzīmēta ar Es, visas apakšējās robežas - ar Ei. Gadījumā

Precīza komplekta augšējā (apakšējā) robeža
Ja elements z pieder kopas E un visu tās augšējo robežu kopas Es krustpunktam (attiecīgi apakšējā z

Augšējo un apakšējo robežu pamatīpašības
Lai X ir daļēji sakārtota kopa. 1. Ja, tad

Iestatījums no atributīva viedokļa
Apkopotais skatījums, atšķirībā no atributīvā viedokļa, ir loģiski nepieņemams tādā nozīmē, ka tas noved pie tādiem paradoksiem kā Rasels un Kantors (skat. tālāk). Atribūtīvās t ietvaros

Struktūra
Daļēji sakārtotu kopu X sauc par struktūru, ja tā satur jebkuru divu elementu kopu

Pārklājumu un starpsienu komplekti
Kopas A nodalījums ir saime Ai

Binārās attiecības
Secība ar garumu n, kuras locekļi ir a1, .... an tiks apzīmēta ar (a1, .... a

Bināro attiecību īpašības
Binārajai relācijai R uz Ho kopas ir šādas īpašības: (a) refleksīvi, ja xRx

Trīskāršas attiecības
Dekarta produkts XY

N-āras attiecības
Pēc analoģijas ar divu kopu X,Y Dekarta reizinājumu var izveidot Dekarta reizinājumu X

Displeji
Kartējumi ir daži savienojumi starp kopu elementiem. Vienkāršākie attiecību piemēri ir piederības x attiecības

Sarakste
Dekarta reizinājuma apakškopu S sauc par kopu Mi elementu n-āro atbilstību. Formāli

Funkcija
Visas diskrētās matemātikas nozares balstās uz funkcijas jēdzienu. Ļaujiet X -

Funkcijas attēlošana attiecību izteiksmē
Bināro attiecību f sauc par funkciju, ja no un

Injekcija, izsūkšana, bijekcija
Lietojot terminu "kartēšana", tiek nošķirta kartēšana X uz Y un kartēšana X uz Y

Apgrieztā funkcija
Patvaļīgiem mēs definējam

Daļēji pasūtīti komplekti
Kopu S sauc par daļēji sakārtotu (POS), ja tai ir dota refleksīva, pārejoša un antisimetriska bināra daļēja secība.

Iestatiet reprezentācijas minimizēšanu
Izmantojot šos likumus, mēs aplūkojam kopas M attēlojuma minimizēšanas problēmu ar operāciju palīdzību

Pārkārtojumi
Dota kopa A. Lai A ir galīga kopa, kas sastāv no n elementiem A = (a1, a2, …, a

Permutācijas ar atkārtojumiem
Ļaujiet kopai A būt identiskiem (atkārtotiem) elementiem. Permutācija ar kompozīcijas atkārtojumiem (n1, n2, … ,nk

Izvietojumi
Koreži ar garumu k (1≤k≤n), kas sastāv no dažādiem n-elementu kopas A elementiem (koreži atšķiras ar

Izvietojumi ar atkārtojumiem
Ļaujiet kopai A būt identiskiem (atkārtotiem) elementiem. Izvietojumi ar k nosaukumu n elementu atkārtojumiem

Sakārtota izvietošana
Ievietosim n objektus m kastēs tā, lai katrā lodziņā būtu secība, nevis, kā iepriekš, tajā ievietotu objektu kopa. Divas

Kombinācijas
No m elementu kopas A veidojam sakārtotu kopu ar garumu n, kuras elementi ir izkārtojumi ar vienādām tēmām

Kombinācijas ar atkārtojumiem
Rezultātā iegūtās formulas ir derīgas tikai tad, ja kopā A nav identisku elementu. Lai ir elementi n veidu un no tiem kortežs

Funkciju ģenerēšanas metode
Šo metodi izmanto, lai uzskaitītu kombinatoriskos skaitļus un noteiktu kombinatoriskās identitātes. Sākumpunkts ir secības (ai) kombinators

Algebriskā sistēma
Algebriskā sistēma A ir kopa ‹M,O,R›, kuras pirmā sastāvdaļa M ir netukša kopa, otrā komponente O ir kopa.

Slēgšana un subalgebras
Tiek uzskatīts, ka apakškopa ir slēgta saskaņā ar operāciju φ if

Algebras ar vienu bināro darbību
Dota viena bināra darbība uz kopas M. Apskatīsim tā ģenerētās algebras, bet vispirms apskatīsim dažas bināro darbību īpašības. Binārais o

Groupoid
Formas algebra<М, f2>sauc par grupoīdu. Ja f2 ir tāda darbība kā reizināšana (

Veseli skaitļi modulo m
Dots veselu skaitļu gredzens . Atgādināsim. Algebra<М,

Saskaņas
Atbilstība algebrai A = (Σ – algebras paraksts sastāv tikai no funkciju simboliem) šādu ekvivalences sakarību sauc

Grafu teorijas elementi
Grafiki ir matemātiski objekti. Grafu teorija tiek izmantota tādās jomās kā fizika, ķīmija, komunikācijas teorija, datordizains, elektrotehnika, mašīnbūve, arhitektūra, pētniecība

Grafs, virsotne, mala
Ar nevirzītu grafiku (vai, īsi sakot, grafiku) mēs saprotam šādu patvaļīgu pāri G = , Kas

Sarakste
Vēl viens biežāk izmantots virzīta grafa G apraksts ir norādīt virsotņu kopu X un atbilstību Γ, kas

Nevirzīts grafiks
Ja malām nav orientācijas, tad grafiku sauc par nevirzītu (nevirzīts dublikāts vai nevirzīts).

Biežums, jaukts grafiks
Ja malai e ir forma (u, v) vai<и, v>, tad teiksim, ka mala e ir incidenta ver

Apgrieztā atbilstība
Tā kā tas attēlo šādu virsotņu kopu

Grafu izomorfisms
Divi grafiki G1 = un G2 = ir izomorfi (G

Maršruts, kas orientēts uz taku
Virzīta grafika ceļš (vai virzīts maršruts) ir loku secība, kurā

Blakus esošie loki, blakus virsotnes, virsotņu pakāpe
Loki a = (xi, xj), xi ≠ xj, ar kopīgām gala virsotnēm, n

Savienojamība
Divas grafa virsotnes sauc par savienotām, ja tās savieno vienkāršs ceļš. Grafu sauc par savienotu, ja visas tā virsotnes ir savienotas. Teorēma.

Svērtais loka grafiks
Grafu G = (N, A) sauc par svērtu, ja kāda funkcija l: A → R ir definēta loku kopā A tā, ka

Spēcīga savienojamības matrica
Spēcīga savienojamības matrica: novietojiet 1 pa diagonāli; aizpildiet rindu X1 - ja virsotne ir sasniedzama no X1 un X1 d

Koki
Koki ir svarīgi ne tikai tāpēc, ka tiem atrod pielietojumu dažādās zināšanu jomās, bet arī tāpēc, ka tiem ir īpaša pozīcija pašā grafu teorijā. Pēdējo izraisa koka struktūras ārkārtējā vienkāršība

Jebkuram netriviālam kokam ir vismaz divas piekārtas virsotnes
Pierādījums Aplūkosim koku G(V, E). Tāpēc koks ir savienots grafiks

Teorēma
Brīvā koka centrs sastāv no vienas virsotnes vai divām blakus virsotnēm: Z(G) = 0&k(G) = 1 → C(G) = K1

Virzītie, sakārtotie un binārie koki
Virzītie (sakārtotie) koki ir hierarhisku attiecību abstrakcija, kas ļoti bieži sastopama gan praktiskajā dzīvē, gan matemātikā un programmēšanā. Koks (orientācija)

Pierādījums
1. Katrs loks ieiet kādā mezglā. No 9.2.1. definīcijas 2. punkta mums ir: v

Pasūtīti koki
Kopas T1,..., Tk orderev ekvivalentajā definīcijā ir apakškoki. Ja apakškoku relatīvā secība T1,...,

Binārie koki
Binārais (vai binārais) koks ir ierobežota mezglu kopa, kas ir vai nu tukša, vai sastāv no saknes un diviem nesaistītiem binārajiem kokiem — pa kreisi un pa labi. Binārais koks nav java

Bezmaksas koku attēlošana
Lai attēlotu kokus, varat izmantot tos pašus paņēmienus kā vispārīgu grafiku attēlošanai - blakusesības un sastopamības matricas, blakus esošo sarakstu un citus. Bet izmantojot īpašās īpašības

Beigas priekš
Pamatojums Prüfer kods patiešām ir bezmaksas koka attēlojums. Lai to redzētu, parādīsim, ja T" ir koks

Bināro koku attēlojums
Jebkuru brīvu koku var orientēt, norādot vienu no tā mezgliem kā sakni. Jebkuru pasūtījumu var pasūtīt patvaļīgi. Viena sakārtotas kārtas mezgla (brāļu) pēcnācējiem tas tiek definēts kā relatīvs

Pamata loģikas funkcijas
Apzīmēsim ar E2 = (0, 1) kopu, kas sastāv no diviem skaitļiem. Cipari 0 un 1 ir pamata diskrētā paklājā

Būla funkcija
Būla funkcija no n argumentiem x1, x2, … ,xn ir funkcija f no kopas n-tās pakāpes

Divu elementu Būla algebra
Apskatīsim kopu Во = (0,1) un definēsim ar to darbības saskaņā ar avotu tabulām

Būla funkciju tabulas
Būla funkciju, kurā ir n mainīgie, var norādīt ar tabulu, kas sastāv no divām kolonnām un 2n rindām. Pirmajā kolonnā ir uzskaitītas visas kopas no B

F5 — atkārtojiet y
f6 – summa modulo 2 f7

Operāciju secība
Ja kompleksā izteiksmē nav iekavas, tad darbības jāveic šādā secībā: konjunkcija, disjunkcija, implikācija, ekvivalence, noliegums. Konvencijas par Šenona pirmās teorēmas izkārtojumu
Lai atrisinātu problēmu atrast SDNF un SCNF, kas ir ekvivalenti sākotnējai formulai φ, vispirms apsveram Būla funkcijas f(x1, x2) paplašinājumus.

Šenona otrā teorēma
Saskaņā ar dualitātes principu 6.4.3. teorēma (Šenona otrā teorēma) attiecas uz Būla algebrām. Jebkura Būla funkcija f(x1, x2,...

Funkcionālā pilnība
Teorēma (par funkcionālo pilnīgumu). Jebkurai Būla funkcijai f ir formula φ, kas attēlo funkciju f

Algoritms sdnf atrašanai
Lai atrastu SDNF, šī formula vispirms ir jāsamazina līdz DNF un pēc tam jāpārveido tās konjunkti par vienības sastāvdaļām, izmantojot šādas darbības: a) ja konjunkts ietver dažus

Kvina metode
Apsveriet Kvina metodi, lai atrastu MDNF, kas pārstāv noteiktu Būla funkciju. Definēsim šādas trīs darbības: - pilnīga līmēšanas darbība -

Loģisko funkciju kanoniskais attēlojums
Loģisko funkciju (formulu) kanoniskās formas ir izteiksmes, kurām ir Būla formulas standarta forma tā, ka tā unikāli attēlo loģisko funkciju. Algebrā

Būla funkciju sistēmas
Ļaujiet Būla funkcijām f(g1, g2, …, gm) un g1(x1, x2, …, xn), g2(x1

Zhegalkin pamats
Izmēģināsim. Apskatīsim sistēmu. Tas ir pabeigts, jo jebkura funkcija no standarta bāzes ir izteikta terminos

Pasta teorēma
Pasta teorēma nosaka nepieciešamos un pietiekamos nosacījumus Būla funkciju sistēmas pilnīgumam. (Post E.L. The Two-valued interactive systems of mathematical logic. – Annals of Math. Stu

Pierādījums
Nepieciešamība. No pretējās puses. Lai notiek

Žegalkina algebra
Summa modulo 2, savienojums un konstantes 0 un 1 veido funkcionāli pilnīgu sistēmu, t.i. veido algebru - Žegalkina algebru. A=

Propozīcijas loģika
Matemātiskā loģika pēta dabiskās valodas sintakses (formas) un semantikas (satura) pamatjēdzienus. Apsveriet trīs galvenās matemātiskās loģikas pētījumu jomas - loģiku

Predikāta definīcija
Lai X1, X2, ..., Xn ir patvaļīgi mainīgie. Mēs šos mainīgos sauksim par subjekta mainīgajiem. Ļaujiet mainīgajam iestatīt jūs

Predikātu pielietojums algebrā
Apsveriet predikātus, kuros ir brīvs tikai viens mainīgais, ko apzīmējam ar x, un apspriediet predikātu pielietojumu algebrā. Tipisks piemērs

Būla predikātu algebra
Tā kā predikātiem var pielietot loģiskās darbības, tiem ir spēkā Būla algebras pamatlikumi. Teorēma. (Predikātu loģisko operāciju īpašības). Mn

F↔G=(F→G)(G→F), F→G=nav FG
2. Izmantojiet likumu nevis F=F, de Morgana likumus: nē (F

Predikātu aprēķins
Predikātu aprēķinus sauc arī par pirmās kārtas teoriju. Predikātu aprēķinos, kā arī propozīcijas aprēķināšanā atrisināmības problēma ieņem pirmo vietu pēc nozīmes.

Sekošana un līdzvērtība
Propozīcijas forma Q2 izriet no priekšlikuma formas Q1, ja implikācija Q1→Q2 pārvēršas par patiesu augstu

Pieņemtie apzīmējumi
Simboli "vairs nepasūti". Salīdzinot divu funkciju f(n) un g(n) (ar nenegatīvām vērtībām) pieauguma ātrumu, ļoti ērti ir sekojošais.

Meta apzīmējumi
Simboli Saturs Piemērs VAI

Var pierādīt šādas teorēmas.

Teorēma 1.4. Funkcijai f ir apgrieztā funkcija f -1 tad un tikai tad, ja f ir bijektīva.

Teorēma 1.5. Bijektīvo funkciju sastāvs ir bijektīva funkcija.

Rīsi. 1.12 parāda dažādas attiecības, visas, izņemot pirmo, ir funkcijas.

attieksme, bet

injekcija, bet

surjekcija, bet

nav funkcija

nav izteikums

nevis injekcija

Lai f : A→ B ir funkcija, un kopas A un B ir galīgas kopas, lai A = n , B = m . Dirihlē princips nosaka, ja n > m, tad vismaz viena f vērtība notiek vairāk nekā vienu reizi. Citiem vārdiem sakot, ir elementu pāris a i ≠ a j , a i , a j A, kuriem f(a i )= f(a j ).

Dirihlē principu ir viegli pierādīt, tāpēc mēs to atstājam lasītāja ziņā kā triviālu vingrinājumu. Apskatīsim piemēru. Lai grupā būtu vairāk par 12 skolēniem. Tad ir acīmredzams, ka vismaz diviem no viņiem ir dzimšanas diena vienā mēnesī.

§ 7. Ekvivalences attiecība. Faktors - komplekts

Bināro sakarību R kopā A sauc par ekvivalences relāciju, ja R ir refleksīva, simetriska un pārejoša.

Vienlīdzības attiecībai uz skaitļu kopas ir norādītās īpašības, un tāpēc tā ir ekvivalences attiecība.

Trijstūra līdzības attiecība acīmredzami ir ekvivalences attiecība.

Nestingrā nevienādības attiecība (≤ ) uz reālo skaitļu kopas nebūs ekvivalences attiecība, jo tā nav simetriska: no 3≤ 5 neizriet, ka 5≤ 3.

Ekvivalences klase (coset), ko ģenerē elements a noteiktai ekvivalences relācijai R ir to x A apakškopa, kas atrodas attiecībā R ar a. Norādītā ekvivalences klase ir apzīmēta ar [a]R, tāpēc mums ir:

[a] R = (x A: a, x R).

Apskatīsim piemēru. Trīsstūru kopai tiek ieviesta līdzības attiecība. Ir skaidrs, ka visi vienādmalu trijstūri ietilpst vienā kopumā, jo katrs no tiem ir līdzīgs, piemēram, trijstūrim, kura visām malām ir garuma vienība.

Teorēma 1.6. Pieņemsim, ka R ir ekvivalences sakarība uz kopas A un [a] R a coset, t.i. [a] R = (x A: a, x R), tad:

1) jebkuram a A: [a] R ≠, jo īpaši, a [a] R;

2) dažādas cosets nekrustojas;

3) visu kosetu savienība sakrīt ar visu kopu A;

4) dažādu komplektu kopa veido kopas A nodalījumu.

Pierādījums. 1) Sakarā ar R refleksivitāti iegūstam, ka jebkuram a, a A mums ir a,a R, tāpēc a [ a] R un [ a] R ≠ ;

2) pieņemsim, ka [ a] R ∩ [b] R ≠ , t.i. ir A elements c un c [a]R ∩ [b]R. Tad no (cRa)&(cRb) R simetrijas dēļ iegūstam, ka (aR c)&(cRb), un no R tranzitivitātes iegūstam aRb.

Jebkuram x [a] R mums ir: (xRa)&(aRb), tad R tranzitivitātes dēļ iegūstam xRb, t.i. x [b] R, tāpēc [a] R [b] R. Līdzīgi jebkuram y, y [b] R mums ir: (yRb)&(aRb), un R simetrijas dēļ mēs iegūstam, ka (yRb)&(bR a), tad R tranzitivitātes dēļ. , iegūstam, ka yR a , t.i. y [a]R un

tāpēc [b] R [a] R . No [ a ] ​​R [ b ] R un [ b ] R [ a ] ​​R mēs iegūstam [ a ] ​​R = [ b ] R , tas ir, ja kosetes krustojas, tad tās sakrīt;

3) jebkuram a, a A, kā pierādīts, mums ir [a] R, tad acīmredzot visu kosetu savienība sakrīt ar kopu A.

1.6. teorēmas 4) apgalvojums izriet no 1)-3). Teorēma ir pierādīta. Var pierādīt šādu teorēmu.

Teorēma 1.7. Dažādas ekvivalences attiecības kopā A ģenerē dažādas A sadaļas.

Teorēma 1.8. Katrs kopas A nodalījums kopā A ģenerē ekvivalences relāciju, un dažādas sadaļas ģenerē dažādas ekvivalences attiecības.

Pierādījums. Ir dots kopas A nodalījums B = (B i ). Definēsim sakarību R : a,b R tad un tikai tad, ja eksistē tāda B i, ka a un b abi pieder šim B i . Ir acīmredzams, ka ieviestā attiecība ir refleksīva, simetriska un pārejoša, tāpēc R ir ekvivalences relācija. Var parādīt, ka, ja nodalījumi ir atšķirīgi, tad arī to ģenerētās ekvivalences attiecības ir atšķirīgas.

Kopas A visu kosetu kopu attiecībā pret doto ekvivalences attiecību R sauc par faktoru kopu un apzīmē ar A/R. Faktoru kopas elementi ir kosetes. Coset klase [a]R, kā zināms, sastāv no elementiem A, kas ir viens pret otru R.

Apskatīsim ekvivalences attiecības piemēru veselu skaitļu kopai Z = (..., -3, -2, -1, 0, 1, 2, 3, ...).

Divus veselus skaitļus a un b sauc par salīdzināmu (kongruentu) moduli m, ja m ir skaitļa a-b dalītājs, t.i., ja mums ir:

a=b+km , k=…, -3, -2, -1, 0, 1, 2, 3, ….

Šajā gadījumā ierakstiet a≡ b(mod m) .

Teorēma 1.9. Jebkuriem skaitļiem a, b, c un m>0 mums ir:

1) a ≡ a(mod m) ;

2) ja a ≡ b(mod m), tad b ≡ a(mod m);

3) ja a ≡ b(mod m) un b ≡ c(mod m), tad a ≡ c(mod m).

Pierādījums. 1) un 2) apgalvojumi ir acīmredzami. Pierādīsim 3). Pieņemsim, ka a=b+k 1 m, b=c+k 2 m, tad a=c+(k 1 +k 2)m, t.i. a ≡ c(mod m) . Teorēma ir pierādīta.

Tādējādi salīdzināmības relācija modulo m ir ekvivalences relācija un sadala veselo skaitļu kopu nesaistītās skaitļu klasēs.

Izveidosim bezgalīgi atritināmu spirāli, kas parādīta attēlā. 1.13 ir parādīta kā nepārtraukta līnija, un bezgalīgi vītā spirāle ir parādīta kā pārtraukta līnija. Dots nenegatīvs vesels skaitlis m. Mēs novietosim visus veselus skaitļus (elementus no kopas Z) šo spirāļu krustpunktos ar m stariem, kā parādīts attēlā. 1.13.

Salīdzināmības relācijai modulo m (īpaši m = 8) ekvivalences klase ir skaitļi, kas atrodas uz stara. Acīmredzot katrs numurs ietilpst vienā un tikai vienā klasē. Var iegūt, ka m= 8 mums ir:

[ 0] ={…, -8, 0, 8, 16, …};
[ 1] ={…, -7, 1, 9, 17, …};
[ 2] ={…, -6, 2, 10, 18, …};
[ 7] ={…, -9, -1, 7, 15, …}.

Kopas Z faktoru kopa attiecībā pret salīdzināšanas sakarību modulo m tiek apzīmēta kā Z/m vai kā Z m. Izskatāmajam gadījumam m =8

iegūstam, ka Z/8 = Z8 = ( , , , …, ) .

Teorēma 1.10. Jebkuriem veseliem skaitļiem a, b, a*, b*, k un m:

1) ja a ≡ b(mod m), tad ka ≡ kb(mod m);

2) ja a ≡ b(mod m) un a* ≡ b* (mod m), tad:

a) a+a * ≡ b+b* (mod m); b) aa * ≡ bb* (mod m).

Mēs piedāvājam pierādījumus gadījumam 2b). Pieņemsim, ka a ≡ b(mod m) un a * ≡ b * (mod m), tad a=b+sm un a * =b * +tm dažiem veseliem skaitļiem s un t. Pavairošana

iegūstam: aa* =bb* + btm+ b* sm+ stm2 =bb* +(bt+ b* s+ stm)m. Tāpēc

aa* ≡ bb* (mod m).

Tādējādi moduļu salīdzinājumus var saskaitīt un reizināt ar terminu, t.i. darbojas tieši tāpat kā ar vienlīdzību. Piemēram,