Set nəzəriyyəsi. Əsas anlayışlar
Çoxluqlar nəzəriyyəsi müasir riyaziyyatın əsas tərifidir. 1860-cı illərdə Georg Cantor tərəfindən yaradılmışdır. O yazırdı: “Çoxluluq çoxludur, tək bir bütöv olaraq düşünülür”. Çoxluq anlayışı riyaziyyatın əsas, müəyyən edilməmiş anlayışlarından biridir. Onu başqa, daha sadə anlayışlara endirmək olmaz. Buna görə də onu müəyyən etmək olmaz, ancaq izah etmək olar. Beləliklə, çoxluq intuisiyamız və ya düşüncəmizlə aydın şəkildə fərqlənən bir bütöv cisimdə birləşmədir; ümumi xarakteristikası ilə müəyyən edilmiş müəyyən obyektlərin toplusu.
Misal üçün,
1. Voronej sakinlərinin çoxu
2. Təyyarə nöqtələrinin dəsti
3. Natural ədədlər çoxluğu ℕ və s.
Dəstlər adətən böyük Latın hərfləri ilə işarələnir ( A, B, C və s.). Verilmiş çoxluğu təşkil edən obyektlərə onun elementləri deyilir. Çoxluğun elementləri kiçik Latın hərfləri ilə işarələnir( a, b, c və s.). Əgər X– təyin edin, sonra qeyd edin x∈X bunun mənası Xçoxluğun elementidir X ya da nə X dəstinə aiddir X, və giriş x∉X həmin element X dəstinə aid deyil X. Məsələn, ℕ natural ədədlər çoxluğu olsun. Sonra 5 ℕ , A 0,5∉ℕ .
Əgər set Yçoxluğun elementlərindən ibarətdir X, sonra belə deyirlər Yçoxluğun alt çoxluğudur X və işarə edir Y⊂Х(və ya Y⊆Х). Məsələn, tam ədədlər toplusu ℤ rasional ədədlərin alt çoxluğudur ℚ .
Əgər iki dəst üçün X Və Y iki daxilolma eyni vaxtda baş verir X Y Və Y X, yəni. Xçoxluğun alt çoxluğudur Y Və Yçoxluğun alt çoxluğudur X, sonra dəstlər X Və Y eyni elementlərdən ibarətdir. Belə dəstlər X Və Y bərabər adlanır və yazın: X=Y.
Boş dəst termini tez-tez istifadə olunur - Ø - tək elementi olmayan çoxluq. Hər hansı bir çoxluğun alt çoxluğudur.
Çoxluqları təsvir etmək üçün aşağıdakı üsullardan istifadə edilə bilər.
Dəstlərin təyin edilməsi üsulları
1. Obyektlərin sadalanması. Yalnız sonlu çoxluqlar üçün istifadə olunur.
Misal üçün, X=(x1, x2, x3… x n). Qeyd Y ={1, 4, 7, 5} çoxluğun dörd rəqəmdən ibarət olduğunu bildirir 1, 4, 7, 5 .
2. Çoxluğun elementlərinin xarakterik xassəsinin göstərilməsi.
Bu məqsədlə müəyyən bir əmlak təyin olunur R, elementin çoxluğa aid olub-olmadığını müəyyən etməyə imkan verir. Bu üsul daha universaldır.
X=(x: P(x))
(bir dəstə X kimi elementlərdən ibarətdir X, əmlakın sahib olduğu P(x)).
Boş dəst xassələrini təyin etməklə müəyyən edilə bilər: Ø=(x: x≠x)
Siz çoxluqlar üzərində əməliyyatlardan istifadə edərək artıq müəyyən edilmişlərdən istifadə edərək yeni çoxluqlar qura bilərsiniz.
Əməliyyatları təyin edin
1. Birlik (cəm) hər biri çoxluqlardan ən azı birinə aid olan bütün elementlərdən ibarət çoxluqdur. A və ya IN.
A∪B=(x: x A və ya x B).
2. Kəsişmə (məhsul) hər biri eyni vaxtda çoxluğa aid olan bütün elementlərdən ibarət çoxluqdur. A, və bir çoxları IN.
A∩B=(x: x A və x B).
3. Fərqi təyin edin A Və INçoxluğa aid olan bütün elementlərdən ibarət çoxluqdur A və çoxluğa aid deyil IN.
A\B=(x: x A və x B)
4. Əgər A– çoxluğun alt çoxluğu IN. O çoxdur B\Açoxluğun tamamlayıcısı adlanır AÇoxlu IN və işarə edir A'.
5. İki çoxluğun simmetrik fərqi çoxluqdur A∆B=(A\B) (B\A)
N- bütün natural ədədlərin çoxluğu;
Z- bütün tam ədədlər çoxluğu;
Q- bütün rasional ədədlərin çoxluğu;
R- bütün həqiqi ədədlərin çoxluğu;
C- bütün kompleks ədədlərin çoxluğu;
Z 0- bütün qeyri-mənfi tam ədədlər çoxluğu.
Çoxluqlar üzərində əməliyyatların xüsusiyyətləri:
1. A B=B A (kommutativ birlik)
2. A B=B A (kəsişmənin kommutativliyi)
3. A(B C)=(A IN) C (birlik assosiativliyi)
4. A (IN C)=(A IN) C (kəsişmə assosiativliyi)
5. A (IN C)=(A IN) (A C) (paylanmanın 1-ci qanunu)
6. A (IN C)=(A IN) (A C) (2-ci paylanma qanunu)
7. A Ø=A
8. A U=U
9. A Ø= Ø
10. Ə U=A
11. (Ə B)'=A' B' (de Morqan qanunu)
12. (Ə B)'=A' B' (de Morqan qanunu)
13. Ə (A B)=A (udma qanunu)
14. Ə (A B)=A (udma qanunu)
11 saylı mülkü sübut edək. (A B)'=A' IN'
Bərabər dəstlərin tərifinə əsasən, iki daxilliyi sübut etməliyik 1) (A B)' ⊂A' IN';
2) A' B'⊂(A IN)'.
Birinci daxil olmağı sübut etmək üçün ixtiyari elementi nəzərdən keçirin x∈(A B)’=X\(A∪B). Bu o deməkdir ki x∈X, x∉ A∪B. Bundan belə çıxır x∉A Və x∉B, Buna görə də x∈X\A Və x∈X\B, yəni x∈A’∩B’. Beləliklə, (A B)'⊂A' IN'
Geri olsa x∈A’ IN', Bu X eyni zamanda çoxluqlara aiddir A', B', yəni x∉A Və x∉B. Bundan belə çıxır x∉ A IN, Buna görə də x∈(A IN)'. Beləliklə, A' B'⊂(A IN)'.
Belə ki, (A B)'=A' IN'
Elementlərin sırasının təyin olunduğu iki elementdən ibarət çoxluğa sıralı cüt deyilir. Onu yazmaq üçün mötərizələrdən istifadə edin. (x 1, x 2)– iki elementli çoxluq, burada x 1 birinci element, x 2 isə ikinci element hesab olunur. Cütlüklər (x 1, x 2) Və (x 2, x 1), Harada x 1 ≠ x 2, fərqli hesab olunur.
Elementlərin sırasının təyin olunduğu n elementdən ibarət çoxluğa n elementdən ibarət sıralı çoxluq deyilir.
Kartezyen məhsul ixtiyari çoxluqdur X 1, X 2,…,X n n elementdən ibarət sifarişli çoxluqlar, burada x 1 X 1 , x 2 X 2 ,…, x n X n
X 1 Xn
Əgər dəstlər X 1, X 2,…,X n uyğun (X 1 = X 2 =…=X n), onda onların məhsulu işarələnir Xn.
Misal üçün, ℝ 2 – sıralı cüt həqiqi ədədlər toplusu.
Ekvivalentlik münasibətləri. Faktor dəstləri
Verilmiş çoxluğa əsaslanaraq, bəzi alt çoxluqların çoxluğunu nəzərə alaraq yeni çoxluqlar qurmaq olar. Bu halda, biz adətən alt çoxluqlar toplusu haqqında deyil, bir ailə və ya alt qruplar sinfi haqqında danışırıq.
Bir sıra suallarda verilmiş çoxluğun belə alt çoxluqlarının sinfi nəzərdən keçirilir A kəsişməyən və birliyi üst-üstə düşən A. Bu set A onun qoşa bölünmüş alt çoxluqlarının birliyi kimi təmsil oluna bilər, onda demək adətdir ki, A siniflərə bölünür. Siniflərə bölünmə hansısa xarakteristikaya görə həyata keçirilir.
Qoy X boş çoxluq deyil, hər hansı alt çoxluqdur R işdən X Xçoxluqda ikili əlaqə adlanır X. Əgər cütlük (x,y) daxil R, x elementinin münasibətdə olduğunu deyirlər R ilə saat.
Məsələn, münasibətlər x=y, x≥yçoxluqdakı ikili əlaqələrdir ℝ.
İkili əlaqə R dəstdə X ekvivalentlik əlaqəsi adlanır, əgər:
1. (x,x) R; X X (reflektorluq xüsusiyyəti)
2. (x,y) R => (y,x) R (simmetriya xüsusiyyəti)
3. (x,y) R, (y,z) R, sonra (x, z) R (keçid xüsusiyyəti)
Əgər cütlük (x,y) ekvivalent münasibətlərə girdikdə, x və y ekvivalent adlanır (x~y).
1. Qoy ℤ - tam ədədlər toplusu, m≥1- tam ədəd. Ekvivalentlik əlaqəsini təyin edək R haqqında ℤ belə ki n~k, Əgər n-k bölünür m. Bu əlaqə üzrə xassələrin qane olub-olmadığını yoxlayaq.
1. Refleksivlik.
Hər kəs üçün n∈ℤ ℤ belə (p,p)∈R
р-р=0. Çünki 0∈ ℤ , Bu (p,p)∈ℤ.
2. Simmetriya.
From (n,k) ∈R belə bir şeyin olduğu ortaya çıxır р∈ℤ, Nə n-k=mp;
k-n =m(-p), -p∈ ℤ, deməli (k,n) ∈R.
3. Keçidlilik.
Nədən (n,k) ∈R, (k,q) ∈R belələri var ki, belə çıxır səh 1 Və р 2 ∈ ℤ, Nə n-k=mp 1 Və k-q=mp 2. Bu ifadələri əlavə edərək, əldə edirik n-q=m(p 1 + p 2), p 1 + p 2 =p, p∈ ℤ. Buna görə də (n,q) ∈ ℤ.
2. Dəsti nəzərdən keçirin X kosmosun və ya təyyarənin bütün istiqamətlənmiş seqmentləri . =(A, B). Ekvivalentlik əlaqəsini təqdim edək R haqqında X.
Amili təyin edin
Çoxluq.
x çoxluğunda qismən nizam əlaqəsi antisimmetrik, refleksiv və keçidli olan ikili əlaqədir və aşağıdakılarla işarələnir.
bir cüt olaraq:
İkili əlaqə refleksiv və simmetrikdirsə, tolerantlıq adlanır.
İkili əlaqə irrefleks, antisimmetrik və keçidli (əvvəlcədən sifariş) olarsa, kvazi düzən adlanır.
İkili münasibət refleksiv və keçidli olarsa, o, ciddi nizam adlanır.
M çoxluğu üzərində enar cəbri əməliyyat funksiyadır
– vahid əməliyyat;
– ikili əməliyyat;
- triary əməliyyat.
İkili cəbr əməliyyatı -
– M çoxluğundan hər bir sıralanmış cütə M çoxluğunun bəzi elementlərini təyin edən əməliyyat.
Xüsusiyyətlər:
1) Kommutativlik:
2) Assosiativlik:
Neytral element
Binar cəbri əməliyyatlar üçün M təyin edir
Element deyilir:
X çoxluğunda R ikili münasibət olsun. R münasibəti adlanır əks etdirən , əgər (x, x) O R bütün x О X üçün; simmetrik – (x, y) О R-dən (y, x) О R gəlirsə; (x, y) О R və (y, z) О R (x, z) О R nəzərdə tutursa, 23 keçid nömrəsi 24-cü varianta uyğundur.
Misal 1
Deyəcəyik ki, x О X ortaq cəhətləri var
y О X elementi ilə, əgər çoxluq
x Ç y boş deyil. Ortaq əlaqə refleksiv və simmetrik olacaq, lakin keçid deyil.
Ekvivalentlik əlaqəsi X üzərində refleksiv, keçidli və simmetrik əlaqədir. R Í X ´ X-nin ekvivalentlik əlaqəsi olacağını görmək asandır, o zaman və yalnız daxiletmələr baş verərsə:
Id X Í R (refleksivlik),
R -1 Í R (simmetriya),
R ° R Í R (keçidlilik).
Əslində bu üç şərt aşağıdakılara bərabərdir:
Id X Í R, R -1 = R, R ° R = R.
Parçalayaraq X dəstinin A çoxluğu qoşa bölünmüş a Í X alt çoxluqlarıdır, belə ki, UA = X. Hər bir A bölməsi ilə biz ekvivalentlik münasibətini ~ ilə X üzərində əlaqələndirə bilərik, əgər x və y bəzi a Î A elementləridirsə, x ~ y qoya bilərik. .
X-də hər bir ekvivalentlik münasibəti A bölməsinə uyğundur, elementləri alt çoxluqlardır, hər biri ~ münasibətindəkilərdən ibarətdir. Bu alt çoxluqlar adlanır ekvivalentlik sinifləri . Bu A bölməsi ~-ə münasibətdə X çoxluğunun faktorlar çoxluğu adlanır və işarələnir: X/~.
w natural ədədlər çoxluğunda x və y-nin 3-ə bölünməsindən qalanlar bərabər olarsa, x ~ y qoyaraq ~ münasibətini təyin edək. Sonra w/~ 0, 1 və 2 qalıqlarına uyğun gələn üç ekvivalentlik sinfindən ibarətdir.
Sifariş əlaqəsi
X çoxluğunda ikili R əlaqəsi adlanır antisimmetrik , əgər x R y və y R x-dən belə çıxır: x = y. X çoxluğunda ikili R əlaqəsi adlanır sifariş əlaqəsi , refleksiv, antisimmetrik və keçidli olarsa. Bunun aşağıdakı şərtlərə bərabər olduğunu görmək asandır:
1) Id X Í R (refleksivlik),
2) R Ç R -1 (antimmetriya),
3) R ° R Í R (keçidlilik).
X dəstindən və X üzərində R nizamlı münasibətdən ibarət sifarişli cütə (X, R) deyilir qismən sifarişli dəst .
Misal 1
X = (0, 1, 2, 3), R = ((0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2) olsun ), (1, 3), (2, 2), (3, 3)).
R 1 – 3 şərtlərini ödədiyi üçün (X, R) qismən sıralanmış çoxluqdur. x = 2, y = 3 elementləri üçün nə x R y, nə də y R x doğru deyil. Belə elementlər adlanır müqayisə olunmaz . Adətən sifariş əlaqəsi £ ilə işarələnir. Verilən misalda 0 £ 1 və 2 £ 2, lakin 2 £ 3 olduğu doğru deyil.
Misal 2
Qoy< – бинарное отношение строгого неравенства на множестве w натуральных чисел, рассмотренное в разд. 1.2. Тогда объединение отношений = и < является отношением порядка £ на w и превращает w в частично упорядоченное множество.
Qismən sıralanmış çoxluğun (X, £) x, y О X elementləri çağırılır müqayisəli , əgər x £ y və ya y £ x olarsa.
Qismən sıralanmış çoxluq (X, £) adlanır xətti qaydada və ya zəncir , əgər onun elementlərindən hər hansı ikisi müqayisə edilə biləndirsə. Nümunə 2-dəki çoxluq xətti qaydada sıralanacaq, lakin 1-ci misaldakı çoxluq olmayacaq.
Qismən sıralanmış çoxluğun (X, £) A Í X alt çoxluğu adlanır yuxarıda məhdudlaşdırılır , əgər x О X elementi varsa ki, bütün a О A üçün £ x olsun. x О X elementi adlanır. ən böyüyü X-də əgər y £ x hamısı üçün y О X. x £ y olan x-dən fərqli y О X elementləri yoxdursa, x О X elementi maksimal adlanır. 1-ci misalda 2 və 3-cü elementlər maksimum olacaq, lakin ən böyük deyil. Eynilə müəyyən edilmişdir aşağı hədd alt çoxluqlar, ən kiçik və minimum elementlər. 1-ci misalda 0 elementi həm ən kiçik, həm də minimum olacaqdır. Nümunə 2-də 0 da bu xüsusiyyətlərə malikdir, lakin (w, £) nə ən böyük, nə də maksimum elementə malikdir.
Qoy (X, £) qismən sıralanmış çoxluq, A Í X alt çoxluq olsun. a £ b olan a, b О A elementlərinin cütlərindən ibarət olan A-ya münasibət A-da nizamlı münasibət olacaq. Bu əlaqə eyni işarə ilə işarələnir: £. Beləliklə, (A, £) qismən sıralanmış çoxluqdur. Əgər xətti düzülübsə, onda A olduğunu söyləyəcəyik zəncir (X, £) ilə.
Maksimum prinsip
Bəzi riyazi ifadələr seçim aksiomu olmadan sübuta yetirilə bilməz. Bu ifadələrin olduğu deyilir seçim aksiomundan asılıdır və ya ZFC nəzəriyyəsində etibarlıdır , praktikada adətən isbat üçün seçim aksiomunun əvəzinə ya Zermelo aksiomundan, ya da Kuratowski-Zorn lemmasından və ya seçim aksiomuna ekvivalent olan hər hansı digər ifadədən istifadə olunur.
Kuratovski-Zorn Lemma. Hər bir zəncir qismən sifarişli dəstdə olarsa(X, £) yuxarıdan məhdudlaşdırılır, sonra içəri X ən azı bir maksimum element var.
Bu lemma seçim aksiomuna bərabərdir və buna görə də onu aksiom kimi qəbul etmək olar.
Teorem.İstənilən qismən sifariş edilmiş dəst üçün(X, £) münasibəti ehtiva edən münasibət vardır£ və çevrilir X xətti düzülmüş çoxluğa çevrilir.
Sübut. £ münasibətini ehtiva edən bütün nizam münasibətlərinin çoxluğu U daxilolma münasibəti ilə sıralanır. Nizam münasibətləri zəncirinin birliyi nizam əlaqəsi olacağına görə, Kuratovski-Zorn lemması ilə maksimum R əlaqəsi mövcuddur ki, x £ y x R y deməkdir. Sübut edək ki, R X xətti düzülən əlaqədir. Bunun əksini fərz edək: a, b О X olsun ki, nə (a, b), nə də (b, a) R-ə aid olmasın. Münasibətə nəzər salın:
R¢ = R È ((x, y): x R a və b R y).
(a, b) cütünü R-ə və R¢-nin sıra əlaqəsi olması şərtindən R¢-yə əlavə edilməli olan (x, y) cütlərini əlavə etməklə əldə edilir. R¢-nin refleksiv, antisimmetrik və keçid olduğunu görmək asandır. R-nin maksimallığına zidd olan R Ì R¢ alırıq, buna görə də R arzu olunan xətti nizam əlaqəsidir.
Xətti düzülən X çoxluğu yaxşı sıralanmış adlanırsa, onun hər bir boş olmayan alt çoxluğu A Í X ən kiçik elementi a Î A-dan ibarətdir. Kuratovski-Zorn lemması və seçim aksiomu da aşağıdakı ifadəyə ekvivalentdir:
Zermelo aksioması. Hər dəst üçün onu tamamilə nizamlanmış çoxluğa çevirən bir sıra əlaqəsi var.
Məsələn, natural ədədlərin w çoxluğu tam sıralanır. İnduktivlik prinsipi aşağıdakı kimi ümumiləşdirilir:
Transfinit induksiya. Əgər(X, £) tam nizamlanmış çoxluqdur və F(x) onun elementlərinin xassəsidir,ən kiçik element üçün doğrudur x 0 О X və F(y) həqiqətindən bütün y üçün < z следует истинность F(z), то F(x) hamı üçün doğrudur x О X .
Burada y< z означает, что у £ z, но y ¹ z. Действительно, в противном случае среди x Î X, не обладающих свойством F(x), можно выбрать наименьший элемент x 1 , и выполнение F(y) для всех y < x 1 приводит к выполнению F(x 1), противоречащему предположению.
Güc konsepsiyası
Qoy f: X à Y və g: Y à Z çoxluqların xəritəsi olsun. f və g əlaqələri olduğundan onların tərkibi g ° f(x) = g(f(x)) müəyyən edilir. Əgər h: Z à T çoxluqların xəritəsidirsə, h ° (g ° f) = (h ° g) ° f. İd X və İd Y münasibətləri funksiyalardır, buna görə də Id Y ° f = f ° Id x = f kompozisiyaları müəyyən edilir. X = Y üçün f 2 = f ° f, f 3 = f 2 ° f, ..., f n+1 = f n ° f müəyyən edirik.
Xəritəçəkmə f: X àY adlanır inyeksiya yolu ilə , əgər X dəstinin hər hansı x 1 ¹ x 2 elementi üçün f(x 1) ¹ f(x 2) yerinə yetirilir. Xəritəçəkmə f adlanır suryeksiya , əgər hər bir y ОY üçün x О X mövcuddur ki, f(x) = y olsun. Əgər f həm suryeksiya, həm də inyeksiyadırsa, o zaman f deyilir bijeksiya . F -1 Í Y ´ X tərs əlaqəsi funksiya olduqda və yalnız və yalnız o halda f-nin bijeksiya olduğunu görmək asandır.
Deyəcəyik ki, |X| bərabərliyi = |Y|, əgər X və Y arasında bijection varsa. Qoy |X| £ |Y|, inyeksiya varsa f: X à Y.
Kantor-Şröder-Bernşteyn teoremi. Əgər|X| £ |Y| Və|Y| £ |X| , Bu|X| = |Y|.
Sübut. Şərtə görə, f: X à Y və g: Y à X inyeksiyaları var. A = g¢¢Y = Img, Y çoxluğunun g xəritəçəkmə ilə bağlı təsviri olsun. Sonra
(X \ A) Ç (gf)¢¢(X \ A) = Æ,
(gf)¢¢(X \ A) Ç (gf) 2 ¢¢(X \ A) = Æ, …,
(gf) n ¢¢(X \ A) Ç (gf) n+1 ¢¢(X \ A) = Æ, …
j(x) = gf(x) ilə verilmiş j: X à A xəritələşdirməsini nəzərdən keçirək
x Î (X \ A) È (gf)¢¢(X \ A) È (gf) 2 ¢¢(X \ A) È …, digər hallarda isə j(x) = x. j-nin bijection olduğunu görmək asandır. X və Y arasında tələb olunan bijection g -1 ° j-ə bərabər olacaqdır.
Kantorun antinomiyası
Qoy |X|< |Y|, если |X| £ |Y| и не существует биекции между X и Y.
Kantor teoremi. İstənilən X, |X| dəsti üçün< |P(X)|, где P(X) – множество всех подмножеств множества X.
Aşağıdakı teoremləri sübut etmək olar.
Teorem 1.4. f funksiyası f -1 tərs funksiyasına malikdir, o halda ki, f bijectivdir.
Teorem 1.5. Bijektiv funksiyaların tərkibi bijektiv funksiyadır.
düyü. 1.12 müxtəlif əlaqələri göstərir, birincisi istisna olmaqla, hamısı funksiyalardır.
münasibət, lakin |
inyeksiya, lakin |
suryeksiya, lakin |
||||||||||||||
funksiya deyil |
suryeksiya deyil |
iynə deyil |
||||||||||||||
f : A→B funksiyası, A və B çoxluqları isə sonlu çoxluqlar olsun, A = n, B = m qoyaq. Dirixlet prinsipi bildirir ki, əgər n > m olarsa, f-nin ən azı bir qiyməti bir neçə dəfə baş verir. Başqa sözlə, f(a i )= f(a j ) olan a i ≠ a j , a i , a j A cüt elementi var.
Dirixletin prinsipini sübut etmək asandır, ona görə də biz bunu əhəmiyyətsiz bir məşq kimi oxucunun öhdəsinə buraxırıq. Bir nümunəyə baxaq. Qrupda 12-dən çox tələbə olsun. Onda aydın olur ki, ən azı ikisinin eyni ayda ad günü var.
A çoxluğundakı R ikili əlaqəsi, əgər R refleksiv, simmetrik və keçidli olarsa, ekvivalentlik münasibəti adlanır.
Ədədlər toplusunda bərabərlik münasibəti göstərilən xüsusiyyətlərə malikdir və buna görə də ekvivalentlik münasibətidir.
Üçbucaq oxşarlıq əlaqəsi açıq-aydın ekvivalentlik əlaqəsidir.
Həqiqi ədədlər çoxluğunda qeyri-ciddi bərabərsizlik münasibəti (≤ ) ekvivalentlik münasibəti olmayacaq, çünki o, simmetrik deyil: 3≤ 5-dən 5≤ 3-ə uyğun gəlmir.
Verilmiş ekvivalentlik münasibəti R üçün a elementi tərəfindən yaradılan ekvivalentlik sinfi (koset) R ilə a münasibətində olan x A-nın alt çoxluğudur. Göstərilən ekvivalentlik sinfi [a]R ilə işarələnir, buna görə də bizdə:
[a] R = (x A: a, x R).
Bir nümunəyə baxaq. Üçbucaqlar çoxluğunda oxşarlıq əlaqəsi təqdim olunur. Aydındır ki, bütün bərabərtərəfli üçbucaqlar bir kosetə düşür, çünki onların hər biri, məsələn, bütün tərəflərinin vahid uzunluğu olan üçbucağa bənzəyir.
Teorem 1.6. R A çoxluğunda ekvivalentlik münasibəti və [a] R a koset olsun, yəni. [a] R = (x A: a, x R), onda:
1) hər hansı bir A üçün: [a] R ≠, xüsusilə, a [a] R;
2) müxtəlif kosetlər kəsişmir;
3) bütün kosetlərin birliyi bütün A çoxluğu ilə üst-üstə düşür;
4) müxtəlif kosetlər dəsti A çoxluğunun bir hissəsini təşkil edir.
Sübut. 1) R-nin refleksivliyinə görə biz əldə edirik ki, hər hansı a, a A üçün bizdə a,a R var, ona görə də a [ a] R və [ a] R ≠ ;
2) tutaq ki, [ a] R ∩ [b] R ≠ , yəni. A və c [a]R ∩ [b]R elementinin c elementi var. Sonra (cRa)&(cRb)-dən R-nin simmetriyasına görə (aR c)&(cRb) ki, R-nin keçiciliyindən aRb əldə edirik.
İstənilən x [a] R üçün bizdə: (xRa)&(aRb), onda R-nin keçid qabiliyyətinə görə xRb əldə edirik, yəni. x [b] R, buna görə də [a] R [b] R. Eynilə, hər hansı y, y [b] R üçün bizdə: (yRb)&(aRb) və R-nin simmetriyasına görə (yRb)&(bR a), onda R-nin keçid qabiliyyətinə görə əldə edirik. , biz əldə edirik ki, yR a , yəni. y [a] R və
buna görə də [b] R [a] R . [ a ] R [ b ] R və [ b ] R [ a ] R-dən [ a ] R = [ b ] R əldə edirik, yəni kosetlər kəsişirsə, o zaman üst-üstə düşür;
3) hər hansı a, A üçün, sübut olunduğu kimi, bizdə [a] R var, onda aydındır ki, bütün kosetlərin birliyi A çoxluğu ilə üst-üstə düşür.
1.6 teoreminin 4) müddəası 1)-3)-dən irəli gəlir. Teorem sübut edilmişdir. Aşağıdakı teorem isbat edilə bilər.
Teorem 1.7. A çoxluğundakı müxtəlif ekvivalentlik əlaqələri A-nın müxtəlif bölmələrini yaradır.
Teorem 1.8. A çoxluğunun hər bir bölməsi A çoxluğunda ekvivalentlik əlaqəsi yaradır və müxtəlif bölmələr fərqli ekvivalentlik münasibətləri yaradır.
Sübut. A çoxluğunun B = (B i ) bölməsi verilsin. R : a,b R münasibətini o halda müəyyən edək ki, a və b hər ikisi bu B i-yə aid olan B i mövcud olsun. Aydındır ki, təqdim edilən əlaqə refleksiv, simmetrik və keçidlidir, ona görə də R ekvivalent münasibətdir. Göstərmək olar ki, arakəsmələr müxtəlifdirsə, onların yaratdığı ekvivalentlik münasibətləri də fərqlidir.
Verilmiş ekvivalentlik münasibəti R ilə bağlı A çoxluğunun bütün kosetlərinin çoxluğuna faktorlar çoxluğu deyilir və A/R ilə işarələnir. Amil dəstinin elementləri kosetlərdir. Koset sinfi [a] R, məlum olduğu kimi, bir-birinə R nisbətində olan A elementlərindən ibarətdir.
Z = (..., -3, -2, -1, 0, 1, 2, 3, ...) tam ədədlər çoxluğunda ekvivalentlik münasibətinin nümunəsini nəzərdən keçirək.
Əgər m a-b ədədinin bölənidirsə, yəni bizdə olduqda, a və b iki tam ədədi müqayisə edilə bilən (uyğun) modul m adlanır:
a=b+km , k=…, -3, -2, -1, 0, 1, 2, 3, ….
Bu halda a≡ b(mod m) yazın.
Teorem 1.9. İstənilən a, b, c və m>0 ədədləri üçün bizdə:
1) a ≡ a(mod m);
2) əgər a ≡ b(mod m), onda b ≡ a(mod m);
3) əgər a ≡ b(mod m) və b ≡ c(mod m), onda a ≡ c(mod m).
Sübut. 1) və 2) ifadələri aydındır. 3-ü sübut edək). Qoy a=b+k 1 m, b=c+k 2 m, onda a=c+(k 1 +k 2)m, yəni. a ≡ c (mod m) . Teorem sübut edilmişdir.
Beləliklə, müqayisəlilik əlaqəsi modulu m ekvivalentlik əlaqəsidir və tam ədədlər çoxluğunu ədədlərin ayrı-ayrı siniflərinə bölür.
Şəkildə göstərilən sonsuz açılan bir spiral quraq. 1.13 bütöv bir xətt kimi, sonsuz burulma spiral isə kəsik xətt kimi göstərilmişdir. Mənfi olmayan m tam ədədi verilsin. Biz bütün tam ədədləri (Z dəstinin elementlərini) şəkildə göstərildiyi kimi bu spirallərin m şüalarla kəsişmə nöqtələrinə yerləşdirəcəyik. 1.13.
Müqayisəlilik əlaqəsi modulu m üçün (xüsusən, m =8 üçün) ekvivalentlik sinfi şüa üzərində uzanan ədədlərdir. Aydındır ki, hər bir nömrə bir və yalnız bir sinifə düşür. Əldə etmək olar ki, m= 8 üçün bizdə:
[ 0] ={…, -8, 0, 8, 16, …}; |
|||||
[ 1] ={…, -7, 1, 9, 17, …}; |
|||||
[ 2] ={…, -6, 2, 10, 18, …}; |
|||||
[ 7] ={…, -9, -1, 7, 15, …}. |
|||||
Müqayisə modulu m ilə bağlı Z çoxluğunun faktorlar çoxluğu Z/m və ya Z m kimi işarələnir. Baxılan iş üçün m =8
alırıq ki, Z/8 = Z8 = ( , , , …, ) .
Teorem 1.10. İstənilən a, b, a*, b*, k və m tam ədədləri üçün:
1) əgər a ≡ b(mod m), onda ka ≡ kb(mod m);
2) əgər a ≡ b(mod m) və a* ≡ b* (mod m), onda:
a) a+a * ≡ b+b* (mod m); b) aa * ≡ bb* (mod m).
2b halı üçün sübut təqdim edirik). Bəzi s və t tam ədədləri üçün a ≡ b(mod m) və a * ≡ b * (mod m), sonra a=b+sm və a * =b * +tm olsun. Çoxalma
alırıq: aa* =bb* + btm+ b* sm+ stm2 =bb* +(bt+ b* s+ stm)m. Beləliklə,
aa* ≡ bb* (mod m).
Beləliklə, modul müqayisələri terminə görə əlavə edilə və çoxaldıla bilər, yəni. bərabərliklərlə eyni şəkildə fəaliyyət göstərir. Misal üçün,
Əgər münasibət R aşağıdakı xüsusiyyətlərə malikdir: refleksiv simmetrik keçid, yəni. çoxluqdakı ekvivalentlik münasibətidir (~ və ya ≡ və ya E). M , onda ekvivalentlik sinifləri çoxluğu çoxluğun faktorlar çoxluğu adlanır M ekvivalentliklə bağlı R və təyin edilir CƏNAB
Dəstin elementlərinin alt çoxluğu var M ekvivalent x , çağırdı ekvivalentlik sinfi.
Faktor dəstinin tərifindən belə nəticə çıxır ki, o, Booleanın alt çoxluğudur: .
Funksiya çağırılır identifikasiya və aşağıdakı kimi müəyyən edilir:
Teorem. Faktor cəbri F n /~ Boolean funksiyalarının cəbri üçün izomorfdur B n
Sübut.
Tələb olunan izomorfizm ξ : F n / ~ → B n aşağıdakı qayda ilə müəyyən edilir: ekvivalentlik sinfi ~(φ) funksiyası uyğun gəlir f φ , çoxluqdan ixtiyari düstur üçün həqiqət cədvəlinə malik olmaq ~(φ) . Fərqli ekvivalentlik sinifləri fərqli həqiqət cədvəllərinə uyğun olduğundan, xəritələşdirmə ξ injective və hər hansı Boolean funksiyası üçün f -dan Səh funksiyanı ifadə edən düstur var f, sonra xəritəçəkmə ξ surjective. Saxlama əməliyyatları, göstərildikdə 0, 1 ξ birbaşa yoxlanılır. CTD.
Sabit olmayan hər bir funksiyanın funksional tamlığı haqqında teoremlə 0 , bəzi SDNF-lərə uyğun gəlir ψ , sinfinə aiddir ~(φ) = ξ -1 (f) funksiyanı təmsil edən düsturlar f . Sinifdə olmaq problemi yaranır ~(φ) ən sadə quruluşa malik olan disjunktiv normal forma.
İşin sonu -
Bu mövzu bölməyə aiddir:
Moskva Dövlət İnşaat Mühəndisliyi Universiteti.. Tikintidə İdarəetmə İqtisadiyyatı və İnformasiya Sistemləri İnstitutu.. IEEE..
Bu mövzuda əlavə materiala ehtiyacınız varsa və ya axtardığınızı tapmadınızsa, işlərimiz bazamızda axtarışdan istifadə etməyi məsləhət görürük:
Bu material sizin üçün faydalı olsaydı, onu sosial şəbəkələrdə səhifənizdə saxlaya bilərsiniz:
| Tweet |
Diskret riyaziyyatın mövzusu
Diskret (sonlu, sonlu) riyaziyyatın predmeti riyaziyyatın diskret strukturların xassələrini, klassik (davamlı) riyaziyyat isə obyektlərin xassələrini öyrənən bölməsidir.
İzomorfizm
Cəbri əməliyyatları öyrənən elmə cəbr deyilir. Kursu öyrəndikcə bu konsepsiya daha konkretləşəcək və dərinləşəcək. Cəbri yalnız NECƏ hərəkət etmə sualı maraqlandırır
Məşqlər
1. İzomorf xəritələşdirmənin həmişə izotonik olduğunu və bunun əksinin doğru olmadığını sübut edin. 2. Qrupunuzu dəstlərin dilində yazın. 3. Çoxluqların dilində olan obyektləri yazın
Çoxluq və çoxluğun elementləri
Hazırda mövcud çoxluq nəzəriyyələri konseptual əsas və məntiqi vasitələrin paradiqmatikası (baxışlar sistemi) ilə fərqlənir. Beləliklə, nümunə olaraq iki əksini göstərə bilərik
Sonlu və sonsuz çoxluqlar
Dəstənin ibarət olduğu şey, yəni. Çoxluğu təşkil edən obyektlərə onun elementləri deyilir. Çoxluğun elementləri bir-birindən fərqli və fərqlidir. Verilən nümunələrdən göründüyü kimi
Setin gücü
Sonlu çoxluq üçün kardinallıq onun elementlərinin sayına bərabərdir. Məsələn, n kardinallığın A çoxluğunun B(A) kainatının kardinallığı
A1A2A3| + … + |A1A2A3| + … + |A1A2An| + … + |Аn-2An-1An| + (-1)n-1 |А1A2A3...An|
Sonlu A çoxluğu 1 seqmentinə bərabərdirsə k kardinallığına malikdir.. k;:
Alt çoxluq, öz alt çoxluğu
Çoxluq anlayışı təqdim edildikdən sonra mövcud olanlardan yeni çoxluqlar qurmaq, yəni çoxluqlar üzərində əməliyyatları müəyyən etmək vəzifəsi yaranır. "Çoxlu M"
Mənalı çoxluq nəzəriyyələrinin simvolik dili
Kursu öyrənmək prosesində biz çoxluqlar nəzəriyyəsinin obyekt dili ilə obyekt dilinin öyrənildiyi metadil arasında fərq qoyacağıq. Çoxluq nəzəriyyəsinin dili dedikdə, əlaqəni nəzərdə tuturuq
Sübut
B çoxluğu sonsuzdur, yəni
Elementlərin əlavə edilməsi və çıxarılması
Əgər A çoxluqdursa və x elementdirsə, sonra elementdir
Sərhədli dəstlər. Sərhədləri təyin edin
Bəzi X çoxluğunda f(x) ədədi funksiyası verilsin. f(x) funksiyasının yuxarı sərhədi (sərhədi) belə bir ədəddir
Dəqiq yuxarı (aşağı) limit
Bütün yuxarı sərhədlərin E çoxluğu Es, bütün aşağı sərhədləri isə Ei ilə işarələnir. halda
Dəstin yuxarı (aşağı) dəqiq sərhədi
z elementi E çoxluğu ilə onun bütün yuxarı sərhədlərinin Es çoxluğunun kəsişməsinə aiddirsə (müvafiq olaraq aşağı r)
Yuxarı və aşağı sərhədlərin əsas xassələri
X qismən sıralanmış çoxluq olsun. 1. Əgər, onda
Atributiv baxımdan təyin edin
Məcmu nöqteyi-nəzər, atributiv nöqteyi-nəzərdən fərqli olaraq, Russell və Cantor tipli paradokslara gətirib çıxarması mənasında məntiqi cəhətdən əsassızdır (aşağıya bax). Atributiv t çərçivəsində
Struktur
Qismən sıralanmış X çoxluğunda hər hansı iki elementli çoxluq varsa struktur adlanır
Örtmə və arakəsmə dəstləri
A dəstinin bölməsi Ai ailəsidir
İkili əlaqələr
Uzunluğu n olan, şərtləri a1, .... an olan ardıcıllıq (a1, .... a) ilə işarələnəcək.
Binar əlaqələrin xassələri
Ho çoxluğundakı R ikili əlaqəsi aşağıdakı xüsusiyyətlərə malikdir: (a) xRx olduqda refleksiv
Üçlü münasibətlər
Kartezian məhsulu XY
N-ar münasibətləri
İki X,Y dəstinin Kartezyen hasilinə bənzətməklə, X, Dekart məhsulunu qura bilərik
Göstərir
Xəritəçəkmələr dəstlərin elementləri arasında bəzi əlaqələrdir. Münasibətlərin ən sadə nümunələri x üzvlüyünün münasibətləridir
Yazışmalar
Dekart hasilinin S alt çoxluğuna Mi çoxluqlarının elementlərinin n-ar uyğunluğu deyilir. Formal olaraq
Funksiya
Diskret riyaziyyatın bütün sahələri funksiya anlayışına əsaslanır. Qoy X -
Münasibətlər baxımından funksiyanı təmsil edən
İkili f əlaqəsi və-dən olduqda funksiya adlanır
Enjeksiyon, suryeksiya, bijeksiya
“Xəritələmə” terminindən istifadə edərkən XbY xəritələşdirilməsi və X-nin Y-yə uyğunlaşdırılması arasında fərq qoyulur.
Tərs funksiya
İxtiyari olanlar üçün biz müəyyən edirik
Qismən sifarişli dəstlər
S çoxluğuna refleksiv, keçidli və antisimmetrik ikili qismən sıra əlaqəsi verilirsə, ona qismən sifarişli (PUM) deyilir.
Təqdimatın minimuma endirilməsini təyin edin
Bu qanunlardan istifadə edərək, əməliyyatlardan istifadə edərək M çoxluğunun təsvirinin minimuma endirilməsi məsələsini nəzərdən keçiririk
Yenidən tənzimləmələr
A çoxluğu verilmişdir. Qoy A n elementdən ibarət sonlu çoxluq olsun A = (a1, a2, …, a
Təkrarlarla dəyişdirmələr
Qoy A çoxluğu eyni (təkrarlanan) elementlərə malik olsun. Kompozisiyanın təkrarları ilə permutasiya (n1, n2, … , nk
Yerləşdirmələr
n elementli A çoxluğunun müxtəlif elementlərindən ibarət olan k (1≤k≤n) uzunluqlu kortejlər (tuples
Təkrarlarla yerləşdirmələr
Qoy A çoxluğu eyni (təkrarlanan) elementlərə malik olsun. k adın n elementinin təkrarı ilə yerləşdirmələr
Nizamlı yerləşdirmə
Gəlin n obyekti m qutuya elə yerləşdirək ki, hər qutuda əvvəlki kimi bir sıra obyektlər deyil, ardıcıllıq olsun. iki
Kombinasiyalar
m elementli A çoxluğundan elementləri eyni mövzulu aranjimanlar olan n uzunluğunda sıralı çoxluq qururuq.
Təkrarlarla birləşmələr
Alınan düsturlar yalnız A çoxluğunda eyni elementlər olmadıqda etibarlıdır. N tipli elementlər və onlardan bir dəst olsun
Funksiya yaratma üsulu
Bu üsul kombinator ədədləri sadalamaq və kombinator eyniliklərini yaratmaq üçün istifadə olunur. Başlanğıc nöqtəsi ardıcıllıq (ai) kombinatorudur
Cəbr sistemi
A cəbri sistemi ‹M,O,R› toplusudur, onun birinci komponenti M boş olmayan çoxluqdur, ikinci komponent O çoxluqdur
Bağlanma və subalgebralar
φ if əməliyyatı altında alt çoxluğun qapalı olduğu deyilir
Bir ikili əməliyyatı olan cəbrlər
M çoxluğu üzərində bir ikili əməliyyat verilsin. Onun yaratdığı cəbrləri nəzərdən keçirək, lakin əvvəlcə ikili əməliyyatların bəzi xassələrini nəzərdən keçirək. Binar o
Qrupoid
Formanın cəbri<М, f2>qrupoid adlanır. Əgər f2 vurma kimi əməliyyatdırsa (
Tam ədədlər modulu m
Tam ədədlər halqası verilmişdir
Uyğunluqlar
Cəbr üzrə uyğunluq A =
Qrafik nəzəriyyəsinin elementləri
Qrafiklər riyazi obyektlərdir. Qrafik nəzəriyyəsi fizika, kimya, rabitə nəzəriyyəsi, kompüter dizaynı, elektrik mühəndisliyi, maşınqayırma, memarlıq, tədqiqatlar kimi sahələrdə istifadə olunur.
Qrafik, təpə, kənar
İstiqamətsiz qrafik (və ya qısaca desək, qrafik) dedikdə biz belə ixtiyari G = cütünü nəzərdə tuturuq.
Yazışmalar
G istiqamətləndirilmiş qrafikin daha tez-tez istifadə olunan başqa bir təsviri X təpələri dəstini və G uyğunluğunu təyin etməkdən ibarətdir.
İstiqamətsiz qrafik
Əgər kənarların orientasiyası yoxdursa, o zaman qrafik istiqamətsiz adlanır (istiqamətsiz dublikat və ya istiqamətsiz
İnsident, qarışıq qrafik
Əgər e kənarı (u, v) və ya formasına malikdirsə<и, v>, onda deyəcəyik ki, e kənarı hadisə verdir
Əks uyğunluq
Çünki o, belə təpələr toplusunu təmsil edir
Qrafik izomorfizmi
İki qrafik G1 =
Yol yönümlü marşrut
İstiqamətləndirilmiş qrafikin yolu (və ya yönəldilmiş marşrutu) qövslər ardıcıllığıdır
Qonşu qövslər, bitişik təpələr, təpə dərəcəsi
Qövslər a = (xi, xj), xi ≠ xj, ümumi son təpələri, n
Bağlantı
Qrafikdə iki təpə, əgər onları birləşdirən sadə yol varsa, ona bağlı deyilir. Qrafik bütün təpələri bir-birinə bağlıdırsa, ona bağlı deyilir. Teorem.
Çəkili qövs qrafiki
Hansısa l funksiyası: A → R A qövsləri çoxluğunda elə təyin olunarsa, G = (N, A) qrafiki çəkili adlanır.
Güclü əlaqə matrisi
Güclü əlaqə matrisi: diaqonal boyunca 1 qoyun; X1 sətrini doldurun - əgər təpəyə X1 və X1-dən çatmaq olarsa d
Ağaclar
Ağaclar təkcə biliklərin müxtəlif sahələrində tətbiq tapdıqları üçün deyil, həm də qrafik nəzəriyyəsinin özündə xüsusi mövqe tutduqları üçün vacibdir. Sonuncu, ağacın quruluşunun həddindən artıq sadəliyindən qaynaqlanır
Hər hansı qeyri-trivial ağacın ən azı iki asma təpəsi var
Sübut G(V, E) ağacını nəzərdən keçirək. Buna görə ağac əlaqəli bir qrafikdir
Teorem
Sərbəst ağacın mərkəzi bir təpədən və ya iki bitişik təpədən ibarətdir: Z(G) = 0&k(G) = 1 → C(G) = K1
İstiqamətləndirilmiş, sifarişli və ikili ağaclar
İstiqamətləndirilmiş (sifarişli) ağaclar həm praktik həyatda, həm də riyaziyyat və proqramlaşdırmada çox tez-tez rast gəlinən iyerarxik əlaqələrin abstraksiyasıdır. Ağac (oriyentasiya)
Sübut
1. Hər bir qövs bəzi node daxil olur. 9.2.1-ci tərifin 2-ci bəndindən biz: v
Sifarişli ağaclar
Orderev-in ekvivalent tərifində T1,..., Tk çoxluqları alt ağaclardır. Əgər alt ağacların nisbi sırası T1,...,
İkili ağaclar
İkili (və ya ikili) ağac ya boş və ya bir kökdən və iki ayrı ikili ağacdan - sol və sağdan ibarət olan sonlu qovşaqlar dəstidir. Binar ağac java deyil
Pulsuz ağac təmsil
Ağacları təmsil etmək üçün ümumi qrafikləri təmsil etmək üçün eyni üsullardan istifadə edə bilərsiniz - bitişiklik və insident matrisləri, bitişiklik siyahıları və s. Lakin xüsusi xassələrindən istifadə edərək
üçün bitir
Əsaslandırma Prüfer kodu həqiqətən pulsuz ağac təsviridir. Bunu görmək üçün göstərək ki, əgər T" ağacdırsa
İkili ağacların təmsili
İstənilən sərbəst ağac qovşaqlarından birini kök kimi təyin etməklə istiqamətləndirilə bilər. İstənilən sifariş özbaşına sifariş edilə bilər. Sifarişli nizamın bir düyününün (qardaşlarının) nəsilləri üçün nisbi təyin olunur
Əsas məntiq funksiyaları
İki ədəddən ibarət çoxluğu E2 = (0, 1) ilə işarə edək. 0 və 1 rəqəmləri diskret matda əsasdır
Boolean funksiyası
n arqumentin x1, x2, … ,xn məntiqi funksiyası çoxluğun n-ci gücündən f funksiyasıdır.
İki elementli Boole cəbri
Mənbələrin cədvəlinə uyğun olaraq Во = (0,1) çoxluğunu nəzərdən keçirək və üzərində əməliyyatları təyin edək.
Boolean Funksiya Cədvəlləri
n dəyişənin Boolean funksiyası iki sütun və 2n sətirdən ibarət cədvəllə təyin edilə bilər. Birinci sütun B-dən bütün dəstləri sadalayır
F5 – y ilə təkrarlayın
f6 – cəmi modulu 2 f7
Əməliyyatların sırası
Mürəkkəb ifadədə mötərizə yoxdursa, onda əməllər aşağıdakı ardıcıllıqla yerinə yetirilməlidir: birləşmə, disjunksiya, implikasiya, ekvivalentlik, inkar. Şennonun birinci teoreminin təşkili ilə bağlı konvensiyalar
İlkin φ düsturuna ekvivalent SDNF və SCNF-nin tapılması məsələsini həll etmək üçün əvvəlcə f(x1, x2) Boole funksiyasının genişlənmələrini nəzərdən keçiririk.
Şennonun ikinci teoremi
İkilik prinsipinə görə, 6.4.3 teoremi (Şennonun ikinci teoremi) Boole cəbrləri üçün uyğundur. İstənilən Boolean funksiyası f(x1, x2,...
Funksional tamlıq
Teorem (funksional tamlıq haqqında). Hər hansı bir məntiqi f funksiyası üçün f funksiyasını təmsil edən φ düsturu var
Sdnf tapmaq üçün alqoritm
SDNF-ni tapmaq üçün bu düstur əvvəlcə DNF-ə endirilməlidir, sonra isə aşağıdakı hərəkətlərdən istifadə etməklə onun konyunksiyalarını vahidin tərkib hissələrinə çevirmək lazımdır: a) əgər konyunktura bəziləri daxildirsə.
Quine üsulu
Verilmiş Boolean funksiyasını təmsil edən MDNF tapmaq üçün Quine metodunu nəzərdən keçirin. Aşağıdakı üç əməliyyatı müəyyən edək: - tam yapışdırma əməliyyatı -
Məntiqi funksiyaların kanonik təsviri
Məntiqi (düsturlar) funksiyaların kanonik formaları məntiqi funksiyanı unikal şəkildə təmsil edən məntiqi düsturun standart formasına malik ifadələrdir. Cəbrdə
Boolean funksiya sistemləri
Məntiq funksiyaları f(g1, g2, …, gm) və g1(x1, x2, …, xn), g2(x1) olsun.
Zhegalkin əsasında
Gəlin sistemə baxaq. Standart əsasdan istənilən funksiya terminlərlə ifadə edildiyi üçün tamdır
Post teoremi
Post teoremi Boolean funksiyalar sisteminin tamlığı üçün zəruri və kifayət qədər şərtləri müəyyən edir. (Post E.L. Riyazi məntiqin iki dəyərli interaktiv sistemləri. – Annals of Math. Stu.
Sübut
Zərurət. Əks tərəfdən. Qoy olsun
Zhegalkin cəbri Təklif məntiqi Predikatın tərifi Cəbrdə predikatların tətbiqi Boolean predikat cəbri F↔G=(F→G)(G→F), F→G=FG deyil Predikativ hesablama İzləmə və ekvivalentlik Qəbul edilmiş qeydlər Meta təyinatlar
Cəm modulu 2, birləşmə və sabitlər 0 və 1 funksional olaraq tam bir sistem təşkil edir, yəni. bir cəbr əmələ gətirir - Zhegalkin cəbri. A=
Riyazi məntiq təbii dilin sintaksisi (forma) və semantikası (məzmun) haqqında əsas anlayışları öyrənir. Riyazi məntiqin üç əsas tədqiqat sahəsini - məntiqi nəzərdən keçirək
X1, X2, ..., Xn ixtiyari dəyişənlər olsun. Bu dəyişənləri mövzu dəyişənləri adlandıracağıq. Dəyişən sizi təyin etsin
Yalnız bir dəyişənin sərbəst olduğu, x ilə işarə etdiyimiz predikatları nəzərdən keçirək və cəbrdə predikatlardan istifadəni müzakirə edək. Tipik bir nümunə
Məntiqi əməliyyatları predikatlara tətbiq etmək mümkün olduğundan, onlar üçün Boole cəbrinin əsas qanunları etibarlıdır. Teorem. (Predikatlar üçün məntiqi əməliyyatların xassələri). Mn
2. Qanunu F=F deyil, de Morqanın qanunlarından istifadə edin: yox (F
Predikat hesablamalarına birinci dərəcəli nəzəriyyə də deyilir. Predikat hesablamasında, eləcə də təklif hesablamasında birinci ən vacib yer həlledicilik problemidir.
Q1→Q2 təlqini doğru olarsa, Q2 təklif forması Q1 təklif formasından əmələ gəlir.
"Sifariş yoxdur" simvolları. İki f(n) və g(n) funksiyasının artım sürətini (mənfi olmayan qiymətlərlə) müqayisə edərkən aşağıdakılar çox əlverişlidir.
Simvollar İçindəkilər Nümunə OR
