Misalkan R adalah relasi biner pada himpunan X. Relasi R disebut reflektif , jika (x, x) О R untuk semua x О X; simetris – jika dari (x, y) О R mengikuti (y, x) О R; bilangan transitif 23 sesuai dengan opsi 24 jika (x, y) О R dan (y, z) О R menyiratkan (x, z) О R.

Contoh 1

Kita akan mengatakan bahwa x О X memiliki kesamaan dengan unsur y О X, jika himpunan
x Ç y tidak kosong. Relasi yang dimiliki bersama akan bersifat refleksif dan simetris, namun tidak transitif.

Hubungan kesetaraan pada X merupakan relasi refleksif, transitif dan simetris. Sangat mudah untuk melihat bahwa R Í X ´ X akan menjadi relasi ekuivalen jika dan hanya jika inklusinya memenuhi:

Id X Í R (refleksivitas),

R -1 Í R (simetri),

R ° R Í R (transitivitas).

Pada kenyataannya, ketiga kondisi ini setara dengan berikut ini:

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

Dengan membelah dari himpunan X adalah himpunan A yang terdiri dari himpunan bagian lepas berpasangan a Í X sehingga UA = X. Dengan setiap partisi A kita dapat mengasosiasikan relasi ekivalen ~ pada X, dengan menempatkan x ~ y jika x dan y adalah elemen dari beberapa a Î A .

Setiap relasi ekivalen ~ pada X berhubungan dengan partisi A, yang elemen-elemennya merupakan himpunan bagian, yang masing-masing terdiri dari elemen-elemen dalam relasi ~. Subset ini disebut kelas kesetaraan . Partisi A ini disebut himpunan faktor dari himpunan X terhadap ~ dan dinotasikan: X/~.

Mari kita definisikan relasi ~ pada himpunan w bilangan asli, dengan menempatkan x ~ y jika sisa pembagian x dan y dengan 3 adalah sama. Kemudian w/~ terdiri dari tiga kelas ekuivalen yang bersesuaian dengan sisa 0, 1 dan 2.

Hubungan pesanan

Relasi biner R pada himpunan X disebut antisimetris , jika dari x R y dan y R x sebagai berikut: x = y. Relasi biner R pada himpunan X disebut hubungan pesanan , jika bersifat refleksif, antisimetris, dan transitif. Sangat mudah untuk melihat bahwa ini setara dengan kondisi berikut:

1) Id X Í R (refleksivitas),

2) R Ç R -1 (antisimetri),

3) R ° R Í R (transitivitas).

Pasangan terurut (X, R) yang terdiri dari himpunan X dan relasi keteraturan R pada X disebut set yang dipesan sebagian .

Contoh 1

Misalkan X = (0, 1, 2, 3), R = ((0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2 ), (1, 3), (2, 2), (3, 3)).

Karena R memenuhi syarat 1 – 3, maka (X, R) adalah himpunan terurut sebagian. Untuk elemen x = 2, y = 3, baik x R y maupun y R x tidak benar. Unsur-unsur seperti ini disebut tak tertandingi . Biasanya relasi keteraturan dilambangkan dengan £. Dalam contoh yang diberikan, 0 £ 1 dan 2 £ 2, tetapi tidak benar bahwa 2 £ 3.

Contoh 2

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

Elemen x, y О X dari himpunan terurut sebagian (X, £) disebut sebanding , jika x £ y atau y £ x.

Himpunan terurut sebagian (X, £) disebut dipesan secara linear atau rantai , jika ada dua elemennya yang sebanding. Himpunan dari contoh 2 akan terurut secara linier, tetapi himpunan dari contoh 1 tidak.

Subset A Í X dari himpunan terurut sebagian (X, £) disebut dibatasi di atas , jika terdapat suatu elemen x О X sehingga a £ x untuk semua a О A. Elemen x О X disebut terbesar dalam X jika y £ x untuk semua y О X. Suatu elemen x О X disebut maksimal jika tidak ada elemen y О X yang berbeda dengan x yang x £ y. Pada contoh 1, elemen 2 dan 3 akan menjadi maksimum, namun bukan yang terbesar. Didefinisikan serupa batasan yang lebih rendah himpunan bagian, elemen terkecil dan minimum. Dalam contoh 1, elemen 0 akan menjadi yang terkecil dan minimum. Pada Contoh 2, 0 juga mempunyai sifat-sifat ini, tetapi (w, £) tidak mempunyai elemen terbesar dan maksimum.

Misalkan (X, £) adalah himpunan terurut sebagian, A Í X adalah himpunan bagian. Suatu relasi di A, terdiri dari pasangan (a, b) elemen a, b О A, yang mana a £ b, akan menjadi relasi orde di A. Relasi ini dilambangkan dengan simbol yang sama: £. Jadi, (A, £) adalah himpunan terurut sebagian. Jika diurutkan secara linier, maka dikatakan A adalah rantai dalam (X, £).

Prinsip maksimal

Beberapa pernyataan matematis tidak dapat dibuktikan tanpa aksioma pilihan. Pernyataan-pernyataan ini dikatakan demikian bergantung pada aksioma pilihan atau valid dalam teori ZFC , dalam praktiknya, alih-alih aksioma pilihan, aksioma Zermelo, atau lemma Kuratowski-Zorn, atau pernyataan lain yang setara dengan aksioma pilihan biasanya digunakan sebagai pembuktian.

Kuratowski-Zorn Lemma. Jika setiap rantai dalam himpunan terurut sebagian(X, £) dibatasi dari atas, lalu ke dalam X setidaknya ada satu elemen maksimum.

Lemma ini setara dengan aksioma pilihan, sehingga dapat diterima sebagai aksioma.

Dalil.Untuk set yang dipesan sebagian(X, £) ada relasi yang berisi relasi tersebut£ dan bertransformasi X menjadi himpunan yang terurut secara linier.

Bukti. Himpunan semua relasi keteraturan yang mengandung relasi £ diurutkan berdasarkan relasi inklusi U. Karena penyatuan rantai relasi keteraturan akan menjadi relasi keteraturan, maka menurut lemma Kuratowski-Zorn terdapat relasi maksimal R sehingga x £ y menyiratkan x R y. Mari kita buktikan bahwa R adalah suatu relasi yang berurut linier X. Mari kita asumsikan kebalikannya: misalkan ada a, b О X sehingga baik (a, b) maupun (b, a) tidak termasuk dalam R. Perhatikan relasinya:

R¢ = R È ((x, y): x R a dan b R y).

Diperoleh dengan menjumlahkan pasangan (a, b) pada R dan pasangan (x, y) yang harus dijumlahkan pada R¢ dengan syarat R¢ merupakan relasi keteraturan. Sangat mudah untuk melihat bahwa R¢ bersifat refleksif, antisimetris dan transitif. Kita memperoleh R Ì R¢, yang bertentangan dengan maksimalitas R, oleh karena itu, R adalah relasi tatanan linier yang diinginkan.

Himpunan X yang terurut linier disebut terurut baik jika setiap himpunan bagian tak kosong A Í X di dalamnya mengandung elemen terkecil a Î A. Lemma Kuratowski-Zorn dan aksioma pilihan juga ekuivalen dengan pernyataan berikut:

Aksioma Zermelo. Untuk setiap himpunan terdapat relasi keteraturan yang mengubahnya menjadi himpunan terurut sempurna.

Misalnya, himpunan w bilangan asli terurut sempurna. Prinsip induktansi diringkas sebagai berikut:

Induksi transfinit. Jika(X, £) adalah himpunan terurut lengkap dan F(x) adalah properti dari elemen-elemennya, benar untuk elemen terkecil x 0 О X dan sedemikian sehingga dari kebenaran F(y) untuk semua y < z следует истинность F(z), то F(x) benar untuk semua orang x О X .

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

Konsep kekuatan

Misalkan f: X à Y dan g: Y à Z adalah peta himpunan. Karena f dan g merupakan relasi, komposisinya didefinisikan g ° f(x) = g(f(x)). Jika h: Z à T merupakan peta himpunan, maka h°(g°f) = (h°g)°f. Relasi Id X dan Id Y merupakan fungsi, oleh karena itu komposisi Id Y ° f = f ° Id x = f terdefinisi. Untuk X = Y, kita definisikan f 2 = f ° f, f 3 = f 2 ° f, ..., f n+1 = f n ° f.

Pemetaan f: X àY disebut dengan suntikan , jika untuk setiap elemen x 1 ¹ x 2 dari himpunan X, f(x 1) ¹ f(x 2) benar. Pemetaan f disebut dugaan , jika untuk setiap y ОY terdapat x О X sehingga f(x) = y. Jika f merupakan surjeksi dan injeksi, maka f disebut keberatan . Mudah untuk melihat bahwa f adalah suatu bijeksi jika dan hanya jika relasi invers f -1 Í Y ´ X adalah suatu fungsi.

Kita akan mengatakan bahwa persamaan |X| = |Y|, jika terdapat bijeksi antara X dan Y. Misalkan |X| £ |Y|, jika ada suntikan f : X à Y.

Teorema Cantor-Schroeder-Bernstein. Jika|X| £ |kamu| Dan|kamu| £ |X| , Itu|X| = |kamu|.

Bukti. Dengan syarat, terdapat injeksi f: X à Y dan g: Y à X. Misalkan A = g¢¢Y = Img adalah bayangan himpunan Y terhadap pemetaan g. Kemudian

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

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

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

Perhatikan pemetaan j: X à A, diberikan sebagai j(x) = gf(x), dengan

x Î (X \ A) È (gf)¢¢(X \ A) È (gf) 2 ¢¢(X \ A) È …, dan j(x) = x dalam kasus lain. Sangat mudah untuk melihat bahwa j adalah sebuah bijection. Bijeksi yang diperlukan antara X dan Y akan sama dengan g -1 ° j.

Antinomi Penyanyi

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

Teorema Penyanyi. Untuk himpunan apa pun X, |X|< |P(X)|, где P(X) – множество всех подмножеств множества X.

(yaitu, yang mempunyai sifat-sifat berikut: setiap elemen himpunan ekuivalen dengan dirinya sendiri; jika X setara kamu, Itu kamu setara X; Jika X setara kamu, A kamu setara z, Itu X setara z ).

Kemudian himpunan semua kelas ekivalensi dipanggil kumpulan faktor dan ditunjuk. Mempartisi suatu himpunan ke dalam kelas-kelas elemen yang ekuivalen disebut nya faktorisasi.

Tampilan dari X ke dalam himpunan kelas ekuivalen disebut pemetaan faktor.

Contoh

Masuk akal untuk menggunakan faktorisasi himpunan untuk mendapatkan ruang bernorma dari ruang semi-bernorma, ruang dengan hasil kali dalam dari ruang dengan hasil kali dalam, dan sebagainya. Untuk melakukan ini, kami memperkenalkan, masing-masing, norma suatu kelas, yang sama dengan norma dari elemen sembarang, dan hasil kali dalam kelas sebagai hasil kali dalam dari elemen kelas yang berubah-ubah. Pada gilirannya, relasi ekivalensi diperkenalkan sebagai berikut (misalnya, untuk membentuk ruang hasil bagi yang dinormalisasi): subset dari ruang seminorm asli diperkenalkan, terdiri dari elemen-elemen dengan seminorm nol (omong-omong, ini linier, yaitu, itu adalah subruang) dan dua elemen dianggap setara jika perbedaannya termasuk dalam subruang ini.

Jika, untuk memfaktorkan suatu ruang linier, dimasukkan subruang tertentu dan diasumsikan bahwa jika selisih dua elemen ruang asal termasuk dalam subruang tersebut, maka elemen-elemen tersebut ekuivalen, maka himpunan faktornya adalah ruang linier dan disebut ruang faktor.

Contoh

Lihat juga

Yayasan Wikimedia. 2010.

Lihat apa itu "Kumpulan faktor" di kamus lain:

Prinsip logis yang mendasari definisi melalui abstraksi (Lihat Definisi melalui abstraksi): setiap Relasi jenis kesetaraan, yang ditentukan pada beberapa kumpulan elemen awal, membagi (membagi, mengklasifikasikan) yang asli... ...

Suatu bentuk pemikiran yang mencerminkan sifat-sifat esensial, hubungan dan hubungan objek-objek dan fenomena-fenomena dalam kontradiksi dan perkembangannya; suatu pemikiran atau sistem pemikiran yang menggeneralisasi, membedakan objek-objek suatu golongan tertentu menurut umum tertentu dan secara agregat... ... Ensiklopedia Besar Soviet

Kohomologi kelompok Galois. Jika M adalah grup Abelian dan grup Galois dari ekstensi yang bekerja pada M, maka grup kohomologi Galois adalah grup kohomologi yang didefinisikan oleh kompleks yang terdiri dari semua peta, dan d adalah operator kobatas (lihat Kohomologi grup)... . .. Ensiklopedia Matematika

Konstruksinya, menuju surga, pertama kali muncul dalam teori himpunan, dan kemudian digunakan secara luas dalam aljabar, topologi, dan bidang matematika lainnya. Kasus khusus yang penting dari I. p. adalah I. p. dari keluarga struktur matematika bertipe sama yang terarah. Biarlah… Ensiklopedia Matematika

Poin meskipun relatif terhadap grup G yang bekerja pada himpunan X (di sebelah kiri), himpunan Set adalah subgrup dari G dan disebut. stabilizer, atau subgrup stasioner suatu titik terhadap G. Pemetaan tersebut menginduksi bijeksi antara G/Gx dan orbit G(x). TENTANG.… … Ensiklopedia Matematika

Artikel ini memiliki pendahuluan yang terlalu singkat. Silakan tambahkan bagian pengantar yang memperkenalkan secara singkat topik artikel dan merangkum isinya... Wikipedia

Artikel ini membahas tentang sistem aljabar. Untuk cabang logika matematika yang mempelajari pernyataan dan operasinya, lihat Aljabar Logika. Aljabar Boolean adalah himpunan A tak kosong dengan dua operasi biner (analog dengan konjungsi), ... ... Wikipedia

Misalkan suatu relasi ekivalen diberikan pada suatu himpunan. Kemudian himpunan semua kelas ekivalensi disebut himpunan faktor dan dilambangkan. Mempartisi suatu himpunan ke dalam kelas-kelas elemen yang ekuivalen disebut faktorisasi. Memetakan dari ke... ... Wikipedia

Dalam geometri, ruas berarah dipahami sebagai sepasang titik terurut, yang pertama, titik A, disebut permulaannya, dan yang kedua, B, disebut ujungnya. Isi 1 Definisi ... Wikipedia

Dalam berbagai cabang matematika, inti pemetaan adalah himpunan garitan tertentu, yang dalam arti tertentu mencirikan perbedaan antara f dan pemetaan injeksi. Definisi spesifiknya mungkin berbeda-beda, tetapi untuk pemetaan injektif f... ... Wikipedia

Sumber pekerjaan: Tugas 10_20. Ilmu Sosial Ujian Negara Bersatu 2018. Larutan

Tugas 20. Bacalah teks di bawah ini yang ada beberapa kata (frasa) yang hilang. Pilih dari daftar kata (frasa) yang perlu disisipkan sebagai pengganti spasi.

“Kualitas hidup bergantung pada banyak faktor, mulai dari tempat tinggal seseorang hingga situasi sosial ekonomi dan (A) secara umum, serta keadaan politik di negara tersebut. Kualitas hidup, pada tingkat tertentu, dapat dipengaruhi oleh situasi demografis, kondisi perumahan dan produksi, volume dan kualitas _____(B), dll. Tergantung pada tingkat kepuasan kebutuhan dalam perekonomian, itu adalah merupakan kebiasaan untuk membedakan berbagai tingkat kehidupan penduduk: kekayaan - penggunaan (B) memastikan pembangunan manusia secara menyeluruh; tingkat normal _____(G) menurut standar berbasis ilmiah, memberikan seseorang pemulihan kekuatan fisik dan intelektualnya; kemiskinan - konsumsi barang pada tingkat pemeliharaan kapasitas kerja sebagai batas terendah reproduksi _____(D); Kemiskinan adalah konsumsi sejumlah barang dan jasa minimum yang dapat diterima menurut kriteria biologis, yang hanya memungkinkan kelangsungan hidup manusia.

Penduduk, beradaptasi dengan kondisi pasar, menggunakan berbagai sumber pendapatan tambahan, termasuk pendapatan dari lahan pribadi, keuntungan dari _____(E).”

Kata-kata (frasa) dalam daftar diberikan dalam kasus nominatif. Setiap kata (frasa) hanya dapat digunakan satu kali.

Pilih satu kata (frasa) demi satu, secara mental mengisi setiap celah. Harap dicatat bahwa ada lebih banyak kata (frasa) dalam daftar daripada yang Anda perlukan untuk mengisi bagian yang kosong.

Daftar istilah:

1) modal

2) lingkungan

3) konsumsi rasional

4) barang konsumsi

5) alat produksi

7) tenaga kerja

8) kegiatan wirausaha

9) mobilitas sosial

Larutan.

Mari masukkan istilah ke dalam teks.

“Kualitas hidup bergantung pada banyak faktor, mulai dari tempat tinggal seseorang hingga situasi sosial-ekonomi dan lingkungan (2) (A) secara umum, serta keadaan politik di negara tersebut. Kualitas hidup sampai tingkat tertentu dapat dipengaruhi oleh situasi demografis, kondisi perumahan dan produksi, volume dan kualitas barang konsumsi (4) (B), dll. Tergantung pada tingkat kepuasan kebutuhan dalam perekonomian, merupakan kebiasaan untuk membedakan standar hidup penduduk yang berbeda : kekayaan - penggunaan manfaat (6) (B) yang menjamin perkembangan menyeluruh seseorang; tingkat konsumsi rasional yang normal (3) (D) menurut standar berbasis ilmiah, memberikan pemulihan kekuatan fisik dan intelektual bagi seseorang; kemiskinan - konsumsi barang pada tingkat pemeliharaan kapasitas kerja sebagai batas terendah reproduksi angkatan kerja (7) (D); Kemiskinan adalah konsumsi sejumlah barang dan jasa minimum yang dapat diterima menurut kriteria biologis, yang hanya memungkinkan kelangsungan hidup manusia.

Jika sikap R mempunyai sifat sebagai berikut: transitif simetris refleksif, yaitu merupakan relasi ekivalen (~ atau ≡ atau E) pada himpunan M , maka himpunan kelas ekivalensi disebut himpunan faktor dari himpunan tersebut M mengenai kesetaraan R dan ditunjuk TN

Ada subset dari elemen himpunan M setara X , ditelepon kelas kesetaraan.

Dari definisi himpunan faktor dapat disimpulkan bahwa himpunan tersebut adalah bagian dari Boolean: .

Fungsinya disebut identifikasi dan didefinisikan sebagai berikut:

Dalil. Aljabar faktor F n /~ isomorfik terhadap aljabar fungsi Boolean B N

Bukti.

Isomorfisme yang diperlukan ξ : F N / ~ → B n ditentukan oleh aturan berikut: kelas kesetaraan ~(φ) fungsinya cocok f φ , memiliki tabel kebenaran untuk rumus arbitrer dari himpunan ~(φ) . Karena kelas kesetaraan yang berbeda berhubungan dengan tabel kebenaran yang berbeda, pemetaannya ξ injektif, dan sejak untuk fungsi Boolean apa pun F dari Di hal ada rumus yang mewakili fungsi tersebut F, lalu pemetaannya ξ dugaan. Operasi penyimpanan, 0, 1 saat ditampilkan ξ diperiksa secara langsung. CTD.

Dengan teorema kelengkapan fungsional setiap fungsi yang tidak konstan 0 , sesuai dengan beberapa SDNF ψ , milik kelas ~(φ) = ξ -1 (f) rumus yang mewakili suatu fungsi F . Masalah berada di dalam kelas muncul ~(φ) bentuk normal disjungtif, yang mempunyai struktur paling sederhana.

Akhir pekerjaan -

Topik ini termasuk dalam bagian:

Mata kuliah perkuliahan pada disiplin ilmu matematika diskrit

Universitas Teknik Sipil Negeri Moskow.. Institut Ekonomi Manajemen dan Sistem Informasi dalam Konstruksi.. IEEE..

Jika Anda memerlukan materi tambahan tentang topik ini, atau Anda tidak menemukan apa yang Anda cari, kami sarankan untuk menggunakan pencarian di database karya kami:

Apa yang akan kami lakukan dengan materi yang diterima:

Jika materi ini bermanfaat bagi Anda, Anda dapat menyimpannya ke halaman Anda di jejaring sosial:

Menciak

Semua topik di bagian ini:

Mata pelajaran matematika diskrit
Mata pelajaran matematika diskrit (berhingga, berhingga) merupakan salah satu cabang matematika yang mempelajari sifat-sifat struktur diskrit, sedangkan matematika klasik (kontinu) mempelajari sifat-sifat benda.

Isomorfisme
Ilmu yang mempelajari operasi aljabar disebut aljabar. Konsep ini akan menjadi lebih spesifik dan mendalam seiring Anda mempelajari kursus ini. Aljabar hanya tertarik pada pertanyaan BAGAIMANA bertindak

Latihan
1. Buktikan bahwa pemetaan isomorfik selalu isoton, dan kebalikannya tidak benar. 2. Tuliskan grup Anda dalam bahasa himpunan. 3. Tuliskan dalam bahasa himpunan benda-benda itu

Himpunan dan unsur-unsur himpunan
Saat ini, teori himpunan yang ada berbeda dalam paradigma (sistem pandangan) landasan konseptual dan sarana logis. Jadi, sebagai contoh, kita dapat mengutip dua hal yang berlawanan

Himpunan terbatas dan tak terbatas
Terdiri dari apa himpunan itu, mis. Benda-benda yang menyusun suatu himpunan disebut elemen-elemennya. Unsur-unsur suatu himpunan berbeda dan berbeda satu sama lain. Seperti yang dapat dilihat dari contoh yang diberikan

Kekuatan set
Kardinalitas himpunan berhingga sama dengan jumlah elemennya. Misalnya, kardinalitas alam semesta B(A) dari himpunan A dengan kardinalitas n

A1A2A3| + … + |A1A2A3| + … + |A1A2An| + … + |Аn-2An-1An| + (-1)n-1 |А1A2A3…Sebuah|
Himpunan berhingga A mempunyai kardinalitas k jika sama dengan ruas 1.. k;:

Subset, subset sendiri
Setelah konsep himpunan diperkenalkan, muncul tugas untuk membangun himpunan baru dari himpunan yang sudah ada, yaitu mendefinisikan operasi pada himpunan. Himpunan M",

Bahasa simbolis dari teori himpunan yang bermakna
Dalam proses mempelajari mata kuliah ini, kita akan membedakan antara bahasa objek teori himpunan dan bahasa meta, yang melaluinya bahasa objek dipelajari. Yang kami maksud dengan bahasa teori himpunan adalah relasional

Bukti
Himpunan B tidak terhingga, artinya

Menambah dan menghapus item
Jika A adalah himpunan, dan x adalah suatu elemen, maka elemen tersebut adalah

Himpunan berbatas. Tetapkan batasan
Misalkan fungsi numerik f(x) diberikan pada himpunan X. Batas atas (batas) dari fungsi f(x) adalah bilangan tersebut

Batas atas (bawah) yang tepat
Himpunan semua batas atas E dilambangkan dengan Es, dan semua batas bawah dilambangkan dengan Ei. Dalam hal

Batas atas (bawah) himpunan yang tepat
Jika suatu elemen z termasuk dalam perpotongan himpunan E dan himpunan semua batas atasnya Es (masing-masing r bawah

Sifat dasar batas atas dan batas bawah
Misalkan X adalah himpunan terurut sebagian. 1. Jika, maka

Ditetapkan dari sudut pandang atributif
Sudut pandang agregat, berbeda dengan sudut pandang atributif, secara logis tidak dapat dipertahankan dalam arti mengarah pada paradoks seperti Russell dan Cantor (lihat di bawah). Dalam kerangka atributif t

Struktur
Himpunan X yang terurut sebagian disebut struktur jika himpunan tersebut memuat himpunan dua elemen

Set penutup dan partisi
Partisi dari himpunan A merupakan famili Ai

Hubungan biner
Suatu barisan yang panjangnya n yang suku-sukunya adalah a1, .... an, dilambangkan dengan (a1, .... a

Properti hubungan biner
Relasi biner R pada himpunan Ho mempunyai sifat sebagai berikut: (a) refleksif jika xRx

Hubungan terner
Produk kartesius XY

Hubungan N-ary
Dengan analogi dengan perkalian kartesius dua himpunan X,Y, kita dapat membuat perkalian kartesius X

Menampilkan
Pemetaan adalah beberapa hubungan antar elemen himpunan. Contoh relasi yang paling sederhana adalah relasi keanggotaan x

Korespondensi
Subset S dari perkalian Cartesian disebut korespondensi n-ary dari elemen-elemen himpunan Mi. Secara formal

Fungsi
Semua cabang matematika diskrit didasarkan pada konsep fungsi. Biarkan X -

Mewakili suatu fungsi dalam kaitannya dengan relasi
Relasi biner f disebut fungsi jika dari dan

Injeksi, dugaan, bijeksi
Saat menggunakan istilah “pemetaan”, dibuat perbedaan antara pemetaan XbY dan pemetaan X ke Y

Fungsi terbalik
Untuk yang sewenang-wenang, kami mendefinisikannya

Set yang dipesan sebagian
Suatu himpunan S disebut terurut sebagian (PUM) jika diberikan relasi tatanan parsial biner refleksif, transitif, dan antisimetris

Tetapkan minimalisasi representasi
Dengan menggunakan hukum-hukum ini, kami mempertimbangkan masalah meminimalkan representasi himpunan M menggunakan operasi

Penataan ulang
Diberikan himpunan A. Misalkan A adalah himpunan berhingga yang terdiri dari n elemen A = (a1, a2, …, a

Permutasi dengan pengulangan
Misalkan himpunan A mempunyai elemen-elemen yang identik (berulang). Permutasi dengan pengulangan komposisi (n1, n2, … ,nk

Penempatan
Tupel dengan panjang k (1≤k≤n), terdiri dari elemen berbeda dari himpunan n-elemen A (tupel berbeda dalam

Penempatan dengan pengulangan
Misalkan himpunan A mempunyai elemen-elemen yang identik (berulang). Penempatan dengan pengulangan n elemen k nama

Penempatannya teratur
Mari kita tempatkan n objek ke dalam m kotak sehingga setiap kotak berisi urutan, dan bukan, seperti sebelumnya, sekumpulan objek yang ditempatkan di dalamnya. Dua

Kombinasi
Dari himpunan m-elemen A kita membuat himpunan terurut dengan panjang n, yang elemen-elemennya merupakan susunan dengan tema yang sama

Kombinasi dengan pengulangan
Rumus yang dihasilkan hanya valid jika tidak ada elemen yang identik dalam himpunan A. Misalkan ada elemen dengan n tipe dan darinya menjadi tupel

Metode pembangkitan fungsi
Metode ini digunakan untuk menghitung bilangan kombinatorial dan menetapkan identitas kombinatorial. Titik awalnya adalah kombinator barisan (ai).

Sistem aljabar
Sistem aljabar A adalah himpunan M,O,R› yang komponen pertamanya M adalah himpunan tak kosong, komponen kedua O adalah himpunan

Penutupan dan subaljabar
Subset dikatakan tertutup pada operasi φ jika

Aljabar dengan satu operasi biner
Misalkan satu operasi biner diberikan pada himpunan M. Mari kita pertimbangkan aljabar yang dihasilkannya, tapi pertama-tama kita akan mempertimbangkan beberapa properti operasi biner. Biner o

Grupoid
Aljabar bentuk<М, f2>disebut grupoid. Jika f2 adalah operasi seperti perkalian (

Modul bilangan bulat m
Diberikan sebuah cincin bilangan bulat . Izinkan kami mengingatkan Anda. Aljabar<М,

Kesesuaian
Kesesuaian pada aljabar A = (Σ – tanda tangan aljabar hanya terdiri dari simbol-simbol fungsi) relasi ekivalensi seperti itu disebut

Elemen teori grafik
Grafik adalah objek matematika. Teori graf digunakan di berbagai bidang seperti fisika, kimia, teori komunikasi, desain komputer, teknik elektro, teknik mesin, arsitektur, penelitian tentang

Grafik, titik, tepi
Yang kami maksud dengan graf tak berarah (atau, singkatnya, graf) adalah pasangan sembarang G = , Apa

Korespondensi
Deskripsi lain yang lebih sering digunakan dari graf berarah G terdiri dari penentuan himpunan simpul X dan korespondensi Г, untuk

Grafik tidak berarah
Jika sisi-sisinya tidak mempunyai orientasi, maka graf tersebut disebut tidak berarah (undirected duplikasi atau tidak berorientasi

Insiden, grafik campuran
Jika rusuk e berbentuk (u, v) atau<и, v>, maka kita akan mengatakan bahwa tepi e adalah kejadian ver

Pertandingan Terbalik
Karena ini mewakili sekumpulan simpul tersebut

Grafik isomorfisme
Dua grafik G1 = dan G2 = bersifat isomorfik (G

Rute berorientasi jalur
Jalur (atau rute berarah) dari graf berarah adalah barisan busur yang didalamnya

Busur yang berdekatan, simpul yang berdekatan, derajat simpul
Busur a = (xi, xj), xi ≠ xj, mempunyai simpul ujung yang sama, n

Konektivitas
Dua simpul dalam suatu graf disebut terhubung jika terdapat jalur sederhana yang menghubungkan keduanya. Suatu graf disebut terhubung jika semua simpulnya terhubung. Dalil.

Grafik busur berbobot
Suatu graf G = (N, A) disebut berbobot jika beberapa fungsi l: A → R didefinisikan pada himpunan busur A sedemikian rupa sehingga

Matriks konektivitas yang kuat
Matriks konektivitas yang kuat: letakkan 1 di sepanjang diagonal; isi baris X1 - jika titik puncak dapat dijangkau dari X1 dan X1 d

Pohon
Pohon penting bukan hanya karena dapat diterapkan dalam berbagai bidang ilmu pengetahuan, tetapi juga karena mempunyai posisi khusus dalam teori graf itu sendiri. Yang terakhir ini disebabkan oleh kesederhanaan ekstrim dari struktur pohon

Setiap pohon non-sepele memiliki setidaknya dua simpul gantung
Bukti Perhatikan pohon G(V, E). Oleh karena itu, pohon adalah graf terhubung

Dalil
Pusat pohon bebas terdiri dari satu simpul atau dua simpul yang berdekatan: Z(G) = 0&k(G) = 1 → C(G) = K1

Pohon terarah, teratur, dan biner
Pohon terarah (terurut) merupakan abstraksi hubungan hierarki yang sangat sering dijumpai baik dalam kehidupan praktis maupun dalam matematika dan pemrograman. Pohon (orientasi)

Bukti
1. Setiap busur memasuki suatu simpul. Dari ayat 2 definisi 9.2.1 kita mempunyai: v

Pohon yang dipesan
Himpunan T1,..., Tk dalam definisi ekuivalen orderev adalah subpohon. Jika urutan relatif dari subpohon T1,...,

Pohon biner
Pohon biner (atau biner) adalah himpunan simpul berhingga yang kosong atau terdiri dari satu akar dan dua pohon biner yang terpisah - kiri dan kanan. Pohon biner tidak ada di java

Representasi Pohon Gratis
Untuk merepresentasikan pohon, Anda dapat menggunakan teknik yang sama seperti untuk merepresentasikan grafik umum - matriks ketetanggaan dan kejadian, daftar ketetanggaan, dan lain-lain. Tetapi menggunakan sifat khusus dari

Akhir untuk
Dasar Pemikiran Kode Prüfer memang merupakan representasi pohon bebas. Untuk memahaminya, mari kita tunjukkan bahwa jika T" adalah sebuah pohon

Representasi pohon biner
Setiap pohon bebas dapat diorientasikan dengan menunjuk salah satu simpulnya sebagai akar. Pesanan apa pun dapat dipesan secara sewenang-wenang. Untuk keturunan dari satu simpul (saudara) dari suatu tatanan terurut, itu didefinisikan relatif

Fungsi logika dasar
Mari kita nyatakan dengan E2 = (0, 1) himpunan yang terdiri dari dua bilangan. Angka 0 dan 1 merupakan angka dasar pada matras diskrit

fungsi Boolean
Fungsi Boolean dari n argumen x1, x2, …,xn adalah fungsi f dari pangkat ke-n dari himpunan tersebut

Aljabar Boolean dua elemen
Mari kita perhatikan himpunan Во = (0,1) dan tentukan operasinya, berdasarkan tabel sumber

Tabel Fungsi Boolean
Fungsi Boolean dari n variabel dapat ditentukan dengan tabel yang terdiri dari dua kolom dan 2n baris. Kolom pertama mencantumkan semua himpunan dari B

F5 – ulangi di y
f6 – jumlah modulo 2 f7

Urutan operasi
Jika tidak ada tanda kurung dalam ekspresi kompleks, maka operasi harus dilakukan dengan urutan sebagai berikut: konjungsi, disjungsi, implikasi, kesetaraan, negasi. Konvensi mengenai susunan teorema pertama Shannon
Untuk menyelesaikan masalah mencari ekuivalen SDNF dan SCNF dengan rumus asli φ, pertama-tama kita perhatikan perluasan fungsi Boolean f(x1, x2

Teorema kedua Shannon
Berdasarkan prinsip dualitas, Teorema 6.4.3 (teorema kedua Shannon) berlaku untuk aljabar Boolean. Fungsi Boolean apa pun f(x1, x2,...

Kelengkapan fungsional
Teorema (tentang kelengkapan fungsional). Untuk setiap fungsi Boolean f terdapat rumus φ yang mewakili fungsi f

Algoritma untuk menemukan sdnf
Untuk mencari SDNF, rumus ini harus direduksi terlebih dahulu menjadi DNF, lalu diubah konjungsinya menjadi konstituen unit dengan menggunakan tindakan berikut: a) jika konjungsinya mencakup beberapa

metode Quine
Pertimbangkan metode Quine untuk menemukan MDNF yang mewakili fungsi Boolean tertentu. Mari kita definisikan tiga operasi berikut: - operasi pengeleman lengkap -

Representasi kanonik dari fungsi logis
Bentuk kanonik fungsi logika (rumus) adalah ekspresi yang memiliki bentuk standar rumus Boolean sedemikian rupa sehingga merepresentasikan fungsi logika secara unik. Dalam aljabar

sistem fungsi Boolean
Misalkan fungsi Boolean f(g1, g2, …, gm) dan g1(x1, x2, …, xn), g2(x1

Dasar Zhegalkin
Mari kita coba, mari kita lihat sistemnya. Itu lengkap, karena fungsi apa pun dari basis standar dinyatakan dalam istilah

Teorema Post
Teorema Post menetapkan kondisi perlu dan cukup untuk kelengkapan sistem fungsi Boolean. (Posting E.L. Sistem logika matematika interaktif dua nilai. – Annals of Math. Stu

Bukti
Kebutuhan. Dari sebaliknya. Biarlah

Aljabar Zhegalkin
Jumlah modulo 2, konjungsi dan konstanta 0 dan 1 membentuk sistem yang lengkap secara fungsional, yaitu. membentuk aljabar - aljabar Zhegalkin. SEBUAH=

Logika proposisional
Logika matematika mempelajari konsep dasar sintaksis (bentuk) dan semantik (isi) bahasa alami. Mari kita pertimbangkan tiga bidang utama penelitian dalam logika matematika - logika

Pengertian predikat
Misalkan X1, X2, ..., Xn adalah variabel sembarang. Kami akan menyebut variabel-variabel ini sebagai variabel subjek. Biarkan variabel menentukan Anda

Penerapan predikat dalam aljabar
Mari kita perhatikan predikat yang hanya memiliki satu variabel bebas, yang dilambangkan dengan x, dan diskusikan penggunaan predikat dalam aljabar. Sebuah contoh yang khas

Aljabar predikat Boolean
Karena operasi logika dapat diterapkan pada predikat, hukum dasar aljabar Boolean juga berlaku untuk predikat tersebut. Dalil. (Properti operasi logika untuk predikat). M N

F↔G=(F→G)(G→F), F→G=bukan FG
2. Gunakan hukum bukan bukan F=F, hukum de Morgan: bukan (F

Kalkulus predikat
Kalkulus predikat disebut juga teori orde pertama. Dalam kalkulus predikat, maupun dalam kalkulus proposisional, tempat terpenting pertama adalah masalah solvabilitas.

Mengikuti dan kesetaraan
Bentuk proposisi Q2 mengikuti bentuk proposisi Q1 jika implikasi Q1→Q2 menjadi benar

Notasi yang diterima
Simbol "jangan pesan lagi". Saat membandingkan tingkat pertumbuhan dua fungsi f(n) dan g(n) (dengan nilai non-negatif), berikut ini sangat mudah:

Penunjukan meta
Simbol Isi Contoh OR

Teorema berikut dapat dibuktikan.

Teorema 1.4. Suatu fungsi f mempunyai invers fungsi f -1 jika dan hanya jika f bersifat bijektif.

Teorema 1.5. Susunan fungsi bijektif merupakan fungsi bijektif.

Beras. 1.12 menunjukkan berbagai hubungan, semuanya kecuali yang pertama adalah fungsi.

sikap, tapi

injeksi, tapi

dugaan, tapi

bukan suatu fungsi

bukan sebuah dugaan

bukan suntikan

Misalkan f : A→B suatu fungsi, dan himpunan A dan B merupakan himpunan berhingga, misalkan A = n, B = m. Prinsip Dirichlet menyatakan bahwa jika n > m, maka paling sedikit satu nilai f muncul lebih dari satu kali. Dengan kata lain, terdapat sepasang elemen a i ≠ a j , a i , a j A yang f(ai )= f(a j ).

Prinsip Dirichlet mudah dibuktikan, jadi kami serahkan kepada pembaca sebagai latihan yang sepele. Mari kita lihat sebuah contoh. Misalkan ada lebih dari 12 siswa dalam satu kelompok. Maka jelaslah bahwa setidaknya dua orang di antara mereka berulang tahun di bulan yang sama.

§ 7. Hubungan kesetaraan. Faktor - himpunan

Relasi biner R pada himpunan A disebut relasi ekivalen jika R refleksif, simetris, dan transitif.

Suatu relasi kesetaraan pada himpunan bilangan mempunyai sifat-sifat yang ditunjukkan, dan oleh karena itu merupakan relasi ekivalen.

Relasi kemiripan segitiga jelas merupakan relasi ekuivalen.

Relasi pertidaksamaan tak tegas (≤ ) pada himpunan bilangan real bukanlah relasi ekivalen, karena tidak simetris: dari 3≤ 5 tidak berarti 5≤ 3.

Kelas ekivalen (koset) yang dihasilkan oleh elemen a untuk relasi ekuivalen tertentu R adalah himpunan bagian dari x A yang berada dalam relasi R dengan a. Kelas kesetaraan yang ditunjukkan dilambangkan dengan [a]R, oleh karena itu, kita memiliki:

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

Mari kita lihat sebuah contoh. Relasi keserupaan diperkenalkan pada himpunan segitiga. Jelas bahwa semua segitiga sama sisi termasuk dalam satu koset, karena masing-masing segitiga sebangun, misalnya, dengan segitiga yang semua sisinya mempunyai panjang satuan.

Teorema 1.6. Misalkan R adalah relasi ekivalen pada himpunan A dan [a] R sebuah koset, yaitu [a] R = (x A: a, x R), maka:

1) untuk setiap a A: [a] R ≠, khususnya, a [a] R;

2) koset yang berbeda tidak berpotongan;

3) gabungan semua koset berimpit dengan seluruh himpunan A;

4) himpunan koset yang berbeda membentuk partisi himpunan A.

Bukti. 1) Karena refleksivitas R, kita peroleh bahwa untuk sembarang a, a A, kita mempunyai a,a R, oleh karena itu a [ a] R dan [ a] R ≠ ;

2) mari kita asumsikan bahwa [ a] R ∩ [b] R ≠ , yaitu. ada elemen c dari A dan c [a]R ∩ [b]R. Kemudian dari (cRa)&(cRb) karena kesimetrisan R kita peroleh bahwa (aR c)&(cRb), dan dari transitivitas R kita peroleh aRb.

Untuk setiap x [a] R kita mempunyai: (xRa)&(aRb), maka karena transitivitas R kita memperoleh xRb, yaitu x [b] R, oleh karena itu [a] R [b] R. Demikian pula, untuk setiap y, y [b] R, kita mempunyai: (yRb)&(aRb), dan karena kesimetrian R kita peroleh bahwa (yRb)&(bR a), maka, karena transitivitas R , kita mendapatkan bahwa yR a , yaitu. kamu [a]R dan

oleh karena itu [b] R [a] R . Dari [ a ] ​​​​R [ b ] R dan [ b ] R [ a ] ​​​​R kita memperoleh [ a ] ​​​​R = [ b ] R , yaitu jika koset-koset berpotongan, maka koset-koset tersebut berhimpitan;

3) untuk sembarang a, a A, terbukti kita mempunyai a [a] R, maka jelas gabungan semua koset berimpit dengan himpunan A.

Pernyataan 4) Teorema 1.6 mengikuti dari 1)-3). Teorema tersebut telah terbukti. Teorema berikut dapat dibuktikan.

Teorema 1.7. Relasi ekivalen yang berbeda pada himpunan A menghasilkan partisi A yang berbeda.

Teorema 1.8. Setiap partisi pada himpunan A menghasilkan relasi ekivalen pada himpunan A, dan partisi yang berbeda menghasilkan relasi ekivalen yang berbeda.

Bukti. Misalkan diberikan partisi B = (B i ) dari himpunan A. Mari kita definisikan relasi R : a,b R jika dan hanya jika terdapat a B i sehingga a dan b keduanya termasuk dalam B i ini. Jelas bahwa relasi yang diperkenalkan bersifat refleksif, simetris, dan transitif, oleh karena itu R merupakan relasi ekivalen. Dapat ditunjukkan bahwa jika partisinya berbeda, maka relasi ekivalensi yang dihasilkannya juga berbeda.

Himpunan semua koset dari suatu himpunan A terhadap suatu relasi ekivalen tertentu R disebut himpunan faktor dan dilambangkan dengan A/R. Elemen-elemen himpunan faktor adalah koset. Kelas koset [a]R, seperti diketahui, terdiri dari elemen A yang berhubungan satu sama lain R.

Perhatikan contoh relasi ekivalen pada himpunan bilangan bulat Z = (..., -3, -2, -1, 0, 1, 2, 3, ...).

Dua bilangan bulat a dan b disebut modulo m yang sebanding (kongruen) jika m adalah pembagi bilangan a-b, yaitu jika kita mempunyai:

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

Dalam hal ini, tulis a≡ b(mod m) .

Teorema 1.9. Untuk sembarang bilangan a, b, c dan m>0 kita mempunyai:

1) a ≡ a(mod m) ;

2) jika a ≡ b(mod m), maka b ≡ a(mod m);

3) jika a ≡ b(mod m) dan b ≡ c(mod m), maka a ≡ c(mod m).

Bukti. Pernyataan 1) dan 2) sudah jelas. Mari kita buktikan 3). Misalkan a=b+k 1 m, b=c+k 2 m, maka a=c+(k 1 +k 2)m, mis. a ≡ c(mod m) . Teorema tersebut telah terbukti.

Jadi, relasi komparabilitas modulo m merupakan relasi ekivalensi dan membagi himpunan bilangan bulat menjadi kelas-kelas bilangan yang terpisah-pisah.

Mari kita membangun spiral yang tidak berliku tanpa henti, seperti yang ditunjukkan pada Gambar. 1.13 ditampilkan sebagai garis padat, dan spiral yang berputar tanpa henti ditampilkan sebagai garis putus-putus. Misalkan bilangan bulat non-negatif m diberikan. Kami akan menempatkan semua bilangan bulat (elemen dari himpunan Z) pada titik potong spiral ini dengan sinar m, seperti yang ditunjukkan pada Gambar. 1.13.

Untuk modulo relasi komparabilitas m (khususnya, untuk m =8), kelas ekuivalennya adalah bilangan-bilangan yang terletak pada sinar. Jelasnya, setiap nomor termasuk dalam satu dan hanya satu kelas. Dapat diperoleh bahwa untuk m= 8 kita mempunyai:

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

Himpunan faktor dari himpunan Z terhadap hubungan perbandingan modulo m dilambangkan sebagai Z/m atau sebagai Z m. Untuk kasus yang sedang dipertimbangkan m =8

kita peroleh bahwa Z/8 = Z8 = ( , , , …, ) .

Teorema 1.10. Untuk sembarang bilangan bulat a, b, a*, b*, k dan m:

1) jika a ≡ b(mod m), maka ka ≡ kb(mod m);

2) jika a ≡ b(mod m) dan a* ≡ b* (mod m), maka:

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

Kami menyajikan bukti untuk kasus 2b). Misalkan a ≡ b(mod m) dan a * ≡ b * (mod m), maka a=b+sm dan a * =b * +tm untuk beberapa bilangan bulat s dan t. Mengalikan

kita peroleh: aa* =bb* + btm+ b* sm+ stm2 =bb* +(bt+ b* s+ stm)m. Karena itu,

aa* ≡ bb* (modm).

Dengan demikian, perbandingan modulo dapat dijumlahkan dan dikalikan suku demi suku, yaitu beroperasi dengan cara yang persis sama dengan kesetaraan. Misalnya,