✖️ ⛅️ 🏳️‍🌈 Karakteristik kuantitatif dari relasi 🏁 👩🏼‍✈️ 👂🏼

Teori relasi dalam matematika dan dalam sejumlah bidang studi (pengambilan keputusan, basis pengetahuan dan data, linguistik matematika, pemodelan proses, dll.) Memainkan peran yang sangat mencolok, tetapi masih jauh dari selesai. Seperti di cabang lain dari pengetahuan matematika, hasil terkenalnya berhubungan lebih luas dengan pertanyaan dan masalah keberadaan satu atau lain objeknya daripada masalah penghitungannya. Tampaknya setiap peneliti dalam cabang teori tertentu harus tertarik pada gambaran umum dan lengkap dari objek yang menarik dan ketergantungannya, untuk mengamati panorama penuh. Namun sayang, sangat bermasalah untuk melakukan ini, karena tidak ada yang membuat atau menawarkan panorama (gambar) seperti itu. Bahkan katalog hubungan yang diusulkan dalam pekerjaan tidak menutup masalah.

Contoh sederhana. Bertahun-tahun yang lalu dalam buku [1 hal. 207] saya menemukan paragraf seperti itu.

Teori himpunan berurutan sebagian masih mengandung banyak masalah yang belum terpecahkan. Bahkan pertanyaan tentang jumlah himpunan yang dapat dibangun dari sejumlah n elemen tertentu belum ada jika n≥6. Perhitungan langsung hanya berhasil menetapkan bahwa jika S (n) adalah banyaknya himpunan yang terurut sebagian, maka S (2) = 3, S (3) = 19, S (4) = 219, S (5) = 4231, dan bilangan S (n) untuk himpunan non-isomorfik ditemukan hanya untuk n = 4 dan n = 5 unsur: Sn (4) = 16 dan Sn (5) = 63.

Tentang ini, tulis kepala departemen Universitas Negeri Moskow Rybnikov K.A. Saya ingin mendalami ini lebih dalam dan tampaknya saya dapat mencoba mencari solusi, setidaknya entah bagaimana memperluas daftarnya, dan yang paling penting - membuat daftar pesanan parsial, melihat penyebarannya dalam kenyataan dengan propertinya. Hanya untuk menggantungkan hasilnya di dinding. Saya akui bahwa banyak usaha telah dikeluarkan, untuk mengembangkan program penelitian, membuat model urutan parsial yang dapat diterapkan, menulis program dan men-debugnya, komputer memutar algoritma yang diprogram selama puluhan jam. Pernyataan seseorang (dari yang hebat) muncul di benak saya bahwa dasar matematika seharusnya bukanlah angka, tetapi urutan, maka seharusnya banyak teorema akan menerima bukti yang lebih sederhana dan lebih transparan.

Kita telah belajar menghitung jumlah relasi pada pembawa himpunan besar dan menghitung relasinya, tetapi kita gagal mendapatkan rumus yang ketat bahkan untuk bilangan S (n). Saya ingat saat ini sebagai periode pertumbuhan kreatif intensif saya sendiri dan kolega saya, ketika setelah hampir setiap keluaran hasil komputer dan analisis mereka, ide muncul untuk memodifikasi, meningkatkan model, algoritme, koreksi dilakukan untuk menguji hipotesis baru, tetapi sesuatu yang signifikan ( ~~mungkin otak~~ ) tidak cukup.

Apa yang berhasil saya buka (dapatkan) saya berikan di bawah ini dalam teks. Ngomong-ngomong, hasil peneliti asing lainnya sama dengan milik kami, tetapi mereka hanya melaporkan angka S (n) dan tidak menyebutkan pencacahan sebagian pesanan.

Kami mulai dari yang kecil. Daftar lengkap relasi biner untuk himpunan n-carrier apa pun telah diketahui dan dapat diperoleh dengan mudah. Mereka mencari jawaban atas pertanyaan: berapa banyak, untuk n tertentu, ada relasi dengan satu properti tetap, dengan sepasang properti, dengan tiga, dll. Faktanya adalah bahwa dengan data ini, dimungkinkan untuk membangun bukan enumerasi, tetapi algoritma langsung untuk enumerasi relasi semacam itu yang dengan mengikuti Aturan Razor Occam, mereka tidak menghasilkan esensi tambahan.

Di sini selanjutnya kita akan berbicara tentang mendapatkan hasil seperti itu untuk hubungan biner (BO).

Jadi, ada n-set-carrier BO dan daftar lengkap semua BO, serta daftar properti BO:

- refleksivitas; antirefleksivitas; refleksivitas parsial;

- simetri; antisimetri; asimetri; asimetri;

- transitivitas; anti-transitivitas;

- pesanan lemah; pesanan ketat; pesanan parsial; sempurna (linier);

- toleransi;

- kesetaraan;

- siklus;

- kelengkapan.

Karakteristik kuantitatif dari jenis-jenis hubungan biner

Hubungan tidak hanya dapat memiliki satu properti tertentu, tetapi juga kumpulan pasangan, kembar tiga, dll. Properti. Penggunaan hubungan semacam itu dalam praktiknya adalah situasi yang umum. Jadi, misalnya, setiap sikap toleransi (indiferen) memiliki dua sifat: simetri dan refleksivitas. Kumpulan properti ini menentukan jenis hubungan toleransi.

Jenis hubungan lain muncul dari hubungan toleransi, jika kita memerlukan dari hubungan tersebut kelayakan daftar properti yang diperluas: simetri, refleksivitas dan transitivitas. Jelas bahwa mungkin tidak semua relasi toleransi berubah menjadi transitif, tetapi relasi yang memiliki himpunan tiga properti bernama akan membentuk jenis relasi baru yang disebut kesetaraan.

Himpunan relasi ekivalen ternyata bertumpuk dalam himpunan relasi toleransi. Misalnya, dalam katalog, jenis relasi ini disorot dengan mengisi (8 toleransi dan hanya 5 di antaranya yang ekuivalen). Muncul pertanyaan tentang jumlah BO dengan satu set properti atau salah satunya.

Refleksivitas

Relasi α = <, A> pada himpunan A = {

а_{1}, а_{2}, . . ., а_{n}

${_1,_2,...,_n}$ } bersifat refleksif (memiliki sifat refleksivitas) jika setiap pasangan (

а_{i}, а_{i}

$_ i, _ i$ ) memenuhi hubungan ini. Di sini M adalah grafik (bukan grafik) dari hubungan

а_{i} α а_{i}, а_{i} є A, i = 1 (1) | A |

$_ i α _ i , _i є A , i = 1(1)|A|$ ...

Dengan kata lain, diagonal utama matriks grafik, rasio, diisi dengan satu. Semua simpul pada grafik relasi refleksif memiliki loop. Sikap anti reflektif jika tidak

а_{i} є A, i = 1 (1) | A |

$_i є A , i = 1(1)|A|$ tidak dilakukan

а_{i} α а_{i}

$_ i α _ i$ ... Dalam hal ini, matriks relasi antirefleksif α pada diagonal utama tidak memiliki satu kesatuan yaitu ada nol, dan graf yang bersesuaian tidak memiliki simpul pada simpul manapun.

Akhirnya, relasi α adalah non-reflektif jika untuk beberapa orang

а_{i} є A, а_{i} α а_{i}

$_i є A ,_ i α _ i$ dijalankan, tetapi untuk orang lain tidak. Kami akan menganggap hubungan seperti itu sebagian refleksif. Matriks relasi non-reflektif pada diagonal utama berisi sebagian, sebagian - nol. Grafik dari relasi non-reflektif semacam itu tidak memiliki loop di semua simpul.

Contoh klasik dari relasi refleksif adalah diagonal utama representasi matriks, rasio unit (E = Δ), yaitu hubungan kesetaraan (dalam katalog no. 68). Grafik rasio ini dibentuk oleh titik-titik (pasangan) yang terletak di diagonal utama matriks dan pasangan yang sesuai

(i, i) А, i = 1 (1) | A |

$( i , i ) , i =1(1)|A|$ , grafik tidak berisi titik lain.

Representasi matriks dari rasio ini sesuai dengan matriks identitas (E). Grafik hubungan diagonal dibentuk oleh simpul-simpul yang sesuai dengan elemen-elemen dari himpunan A yang diberikan loop. Hubungan diagonal sering dilambangkan dengan

Δ_{А}

$Δ_$ ...

Dalam kasus relasi refleksif, graf yang bersangkutan juga refleksif, dalam kasus relasi antirefleksif, grafnya antirefleksif. Jika untuk beberapa hubungan α diketahui refleksif, maka komplemen ᾱ selalu antirefleksif, dan

α \cap ᾱ = \emptyset, α \cap Δ_{А} = Δ_{А}

$α ∩ ᾱ =∅ , α ∩ Δ_ = Δ_$ ...

Untuk relasi antirefleksif β, itu benar

β \cap Δ_{А} = \emptyset

$β ∩Δ_= ∅$ ...

Contoh 1 . Relasi ≤ (tidak lebih) pada himpunan N bersifat refleksif, dan relasi <(kurang) pada himpunan yang sama antireflexive.

Sikap “menjadi anak laki-laki” adalah anti-reflektif, karena tidak ada seorangpun yang adalah anaknya sendiri.

Untuk tujuan praktis, terkadang perlu menghitung jumlah relasi refleksif yang tersedia di himpunan lengkap relasi yang diberikan pada himpunan A dengan kardinalitas | A | = n.

Mari kita tunjukkan bagaimana perhitungan seperti itu dapat dilakukan. Kami akan mempertimbangkan matriks dari hubungan refleksif biner α pada bidang. Itu selalu berisi semua titik diagonal.

Sisa titik yang sesuai dengan pasangan (i, j), banyaknya n × n - n = n (n - 1) yang mana, dapat dimasukkan ke dalam komposisi dan bilangan yang berbeda k, k = 0 (1) (n × n - n)ke dalam hubungan yang mungkin, yang, tentu saja, akan menjadi reflektif. Dengan menjumlahkan kombinasi k dari n (n-1) di atas k , jumlah total relasi refleksif ditentukan di

mana K = n (n-1) / 2 adalah jumlah busur (sisi) dalam graf n- simpul tanpa loop.

Jumlah hubungan non-reflektif didefinisikan sebagai selisih antara jumlah total hubungan pada A dan jumlah yang refleksif.

Ini mengikuti dari ekspresi ini yang berisi himpunan relasi non-reflektif

(2^{n} - 1)

$(2^n -1)$ kali lebih banyak hubungan daripada hubungan refleksif. Kelebihan rasio ini dihasilkan oleh keragaman kombinasi titik diagonal pada grafik, sedangkan komposisi dan jumlah titik yang tersisa diulangi begitu saja.

Jumlah relasi antirefleksif dari himpunan non-refleksif sama persis dengan jumlah relasi refleksif yaitu

2^{n^{2} - n}

$2^{n^2-n}$ ... Ini mengikuti dari fakta bahwa korespondensi satu-ke-satu dapat dibangun antara hubungan refleksif dan antirefleksif: dari setiap hubungan refleksif, dengan menghilangkan semua titik diagonal, satu hubungan antirefleksif dapat diperoleh dan sebaliknya.

Simetri

Berdasarkan properti simetri, seluruh himpunan hubungan tidak dibagi menjadi empat kelas: simetris, asimetris. Yang terakhir, pada gilirannya, terbagi dalam tiga kelas: antisimetris, asimetris, dan asimetris lainnya.

Hubungan α = <Å, A> pada himpunan A adalah simetris (memiliki sifat simetri terhadap garis lurus yang bertepatan dengan diagonal utama grafik M) jika untuk beberapa pasangan

(i, j) є A \times A

$(i, j) є A×A$ dari

а_{i} α а_{j}

$_i α _j$ Sebaiknya

а_{j} α а_{i}

$_j α _i$ ... Dengan kata lain, untuk pasangan mana saja

((а_{i}, а_{j}) є Å)

$((_i, _j) є Å)$ dieksekusi di kedua arah, atau tidak sama sekali.

Pada grafik relasi simetris, jika sepasang simpul i dan j dihubungkan oleh sebuah busur (i, j), maka itu harus dihubungkan dengan sebuah busur (j, i). Grafik hubungan simetris adalah grafik biasa yang berorientasi simetris, atau hanya tidak berarah.

Rasio α antisimetrik jika dari

а_{i} α а_{j}

$_i α _j$ dan

а_{j} α а_{i}

$_j α _i$ maka i = j.

Matriks rasio antisimetris tidak harus berisi semua yang ada di diagonal utama dan berisi satu dari dua posisi yang simetris terhadap diagonal utama: di atas diagonal atau di bawah diagonal. Grafik relasi ini dibentuk oleh simpul-simpul yang memiliki simpul-simpul untuk semua atau sebagian simpul, dan jika sepasang simpul (i, j) pada graf tersebut dihubungkan, maka ia selalu berupa busur yang hanya satu arah. Perhatikan bahwa untuk hubungan simetris dan antisimetris, beberapa titik diagonal dapat dimasukkan atau tidak.

Jika suatu relasi antisimetrik tidak mengandung satu titik diagonal, maka relasi tersebut dikatakan asimetris , yaitu asimetris . itu selalu anti-reflektif.

Contoh 2... Relasi (≤) pada himpunan N antisimetris, dan relasi (<) pada himpunan yang sama asimetris. Memang, dalam kasus pertama dari

а_{i} \leq а_{j}

$_i ≤_j$ dan

а_{j} \leq а_{i}

$_j ≤_i$ hanya bisa mengikuti

i = j

$i = j$ ... Hubungan persamaan (=) pada N simetris, hubungan α = A × A juga simetris.

Untuk rasio simetris apa pun α, nilainya selalu benar

α = α^{- 1}

$α = α^{-1}$ dan

α^{- 1}

$α^{-1}$ juga simetris. Untuk hubungan antisimetris,

α \cap α^{- 1} \subseteq ∆_{A}

$α ∩ α^{-1}⊆∆_A$ ... Hubungan umum, grafik yang berisi titik-titik simetris dan titik-titik asimetris, tidak simetris. Hubungan ini asimetris, tetapi tidak antisimetris, dan tidak asimetris.

Sifat simetri juga dimanifestasikan dalam hubungan n-ary. Relasi R di set

Х = x_{1}, x_{2}, \dots, x_{n}

$= { x_1, x_2,…,x_n}$ adalah relasi n-ary simetris jika itu, bersama dengan elemennya

< x_{i 1}, x_{i 2}, \dots, x_{i n} > є R

$<x_{i1}, x_{i2}, …,x_{in}>є R$ berisi urutan apa pun

< x_{j 1}, x_{j 2}, \dots, x_{j n} >

$< x_{j1}, x_{j2},…, x_{jn}>$ dibentuk oleh permutasi anggota himpunan X.

Perhatikan juga bahwa hubungan asimetris selalu antirefleksif; Relasi biner non-reflektif dan transitif selalu asimetris. Untuk latihan dan untuk melakukan kalkulasi, jumlah relasi yang memiliki properti tertentu terkait dengan simetri grafik adalah yang menarik. Mari kita hitung rasio semacam itu untuk himpunan sembarang A dari kardinalitas | A | = n.

Dalam argumen kami, kami akan mengandalkan properti refleksivitas, yang, seperti banyak lainnya, belum dipelajari secara mendalam. Bahkan analisis dangkal dari himpunan semua hubungan memungkinkan kita untuk menyimpulkan bahwa itu selalu dapat dibagi

2^{n}

$2^n$ kelas-kelas yang berukuran sama, dan komposisi relasi yang membentuk kelas-kelas ini mengikuti pola tertentu.

Himpunan relasi pada semua kelas memiliki struktur yang sama, hanya berbeda pada jumlah dan komposisi titik diagonal, yang keseluruhan ragamnya ditentukan oleh bilangan tersebut.

2^{n}

$2^n$ ... Mari kita tentukan keadaan diagonal suatu relasi untuk n tetap dengan jumlah dan komposisi titik-titik di atasnya dan milik relasi tertentu. Jelas bahwa, untuk tetap, himpunan status pengisian sel diagonal ditentukan oleh Boolean

2^{∆}

$2^∆$ , di mana ∆ adalah himpunan lengkap titik-titik diagonal grafik bujur sangkar Kartesius dari kardinalitas | ∆ | = n.

Jadi, dalam teori relasi, hanya dua keadaan ekstrim yang secara tradisional telah dipertimbangkan dan dipelajari: apakah semua titik diagonal termasuk dalam relasi dan itu refleksif, atau relasinya tidak mengandung titik diagonal, dan kemudian bersifat anti-reflektif.

Kita akan menyebut semua keadaan antara dengan satu titik diagonal, dengan dua, dan seterusnya, refleksivitas parsial dari orde k k = 0 (1) n, dan relasi semacam ini refleksif sebagian. Jadi relasi refleksif sebagian dari orde nol adalah relasi antirefleksif dan sebagian relasi refleksif orde n hanyalah relasi refleksif.

Perhatikan bahwa semua status dapat diurutkan sebagai elemen Boolean dari himpunan ∆. Pendekatan yang diusulkan memungkinkan kami untuk menguraikan cara menganalisis berbagai properti dan menghitung jumlah hubungan dengan properti individu atau agregatnya.

Biarkan hubungan dianggap refleksif dan simetris. Simetrisinya rasio ditentukan oleh adanya pasangan titik-titik di dalamnya, yang terletak pada matriks rasio secara simetris terhadap diagonal relatif. Untuk sembarang n pasangan seperti itu, ada

C_{n}^{2}

$C_n^2$ ... Mari kita nyatakan himpunan pasangan ini dengan simbol S.

Kemudian seluruh variasi hubungan simetris dan refleksif akan ditentukan oleh Boolean

2^{S}

$2^S$ ... Banyak dari hubungan semacam itu akan dibahas lebih rinci nanti, tetapi di sini kita akan mengatakan bahwa itu membentuk ruang ketidakpedulian atau toleransi. Jelas bahwa jumlah rasio toleransi ditentukan oleh kekuatan boolean

2^{S}

$2^S$ , yaitu

2^{C_{n}^{2}}

$2^{C_n^2}$ ...

Di bawah dalam tabel. 1 menunjukkan nilai jumlah rasio toleransi untuk nilai awal n dari segmen bilangan asli.

Tabel 1 . Jumlah BO yang toleran

Sekarang mudah untuk menghitung kardinalitas dari semua hubungan simetris, karena ada atau tidaknya titik diagonal tidak mengubah sifat simetri. Himpunan hubungan simetris dilambangkan dengan simbol SM. Kemudian kardinalitas himpunan ini untuk n tetap ditentukan oleh rumus

| S M | = 2^{n} \cdot 2^{C_{n}^{2}} = 2^{C_{n + 1}^{2}},

$|SM| = 2^n·2^{C_n^2} = 2^{C_{n+1}^2},$

dimana n adalah jumlah titik diagonal dari rasio tersebut. Meja 2 menunjukkan nilai | SM | untuk beberapa n.

Tabel 2 . Jumlah BO yang simetris

Sekarang mari kita beralih ke perhitungan hubungan asimetris, yang himpunannya akan dilambangkan dengan AS. Hubungan ini dicirikan oleh fakta bahwa semua titik diagonal tidak ada di dalamnya dan tidak ada sel dari matriks dari hubungan yang berada di luar diagonal yang memiliki yang simetris. Dengan kata lain, ini adalah seperangkat hubungan anti-reflektif dan antisimetris.

Kardinalitas himpunan ini dapat ditentukan dari ekspresi

| A S | = Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k} = 3^{C_{n}^{2}},

$|AS| = Σ_{k=0}^K C_K^k·2^k = 3^{C_n^2},$

dimana K =

C_{n}^{2}

$C_n^2$ ...

Kami mendapatkan rumus tereduksi untuk menghitung kardinalitas himpunan AS - hubungan asimetris untuk kardinalitas pembawa tertentu | A | = n. Menurut definisi, semua relasi himpunan AS adalah antirefleksi; oleh karena itu, diagonal utama dalam matriks relasi kosong, dan elemen unit hanya dapat ditempatkan di setengah dari posisi matriks yang tersisa, yaitu. di

C_{n}^{2} = (n^{2} - n) : 2

${C_n^2} =(n^2-n):2$ sel.

Jadi, anggaplah sebuah relasi asimetris mengandung k-elemen (titik, pasangan berurutan) 0 ≤ k ≤

C_{n}^{2}

${C_n^2}$ ... Jumlah relasi dengan jumlah elemen seperti itu jelas akan sama dengan jumlah kombinasi dari

C_{n}^{2}

$C_n^2$ oleh k.

Dalam hal ini, dengan masing-masing elemen k kita mengasosiasikan sepasang posisi simetris: satu di atas diagonal utama matriks, yang lain di bawah diagonal. Karena dalam setiap pasangan sebuah elemen dapat berada di salah satu dari dua posisi, maka boolean muncul untuk mengakomodasi elemen k

2^{n}

$2^n$ peluang.

Lewat sini,

C_{n}^{2}

$C_n^2$ Adalah banyaknya pilihan k pasang posisi dari

C_{n}^{2} = K

$C_n^2 = K$ pasangan yang tersedia dalam representasi matriks relasi, dan

2^{n}

$2^n$ - jumlah peluang untuk mengatur elemen k di posisi di setiap pasangan. Jumlah relasi yang mengandung elemen k didefinisikan sebagai hasil kali dari jumlah pilihan pasangan posisi dengan jumlah opsi untuk mengatur elemen k ini, yaitu

2^{k} C_{K}^{k}

$2^kC_K^k$ ...

Jumlah total relasi dalam himpunan AS diperoleh dengan menjumlahkan produk yang diperoleh di atas semua nilai k dari nol hingga maksimum yang diizinkan K =

C_{n}^{2} = K

$C_n^2 = K$ , yaitu

| A S | = Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k} = 3^{C_{n}^{2}},

$|AS| = Σ_{k=0}^K C_K^k·2^k = 3^{C_n^2},$

dimana K =

C_{n}^{2}

$C_n^2$ ...

Contoh 3. Misalkan kardinalitas himpunan pendukung | A | = 5. Hitung jumlah hubungan asimetris menggunakan rumus yang ditemukan. Mari kita tentukan nilai batas atas K dalam penjumlahannya, K =

C_{n}^{2}

$C_n^2$ = 10. Data perhitungan untuk penjumlahan diberikan dalam tabel. 3.

Tabel 3 . Karakteristik BO

Ada cara lain untuk menghitung kardinalitas himpunan AS. Ini didasarkan pada penghitungan jumlah pemetaan dari satu set pasangan posisi simetris ke dalam satu set keadaan di mana setiap pasangan tersebut dapat berada. Dalam hubungan asimetris, ada

K = C_{n}^{2}

$K = C_n^2$ pasang posisi.

Setiap posisi dalam sepasang sel dapat ditempati oleh 0 atau 1, tetapi untuk pasangan posisi terdapat S = 3 status, yang kami nyatakan sebagai berikut:

- 1, jika elemen (1) ditempatkan di atas diagonal;

- 2, jika elemen (1) ditempatkan di bawah diagonal;

- 3 jika kedua posisi kosong (ditempati oleh nol).

Jadi, sepasang posisi simetris (dalam matriks hubungan) dapat berada di setiap

hubungan di salah satu dari tiga keadaan. Rumus untuk menghitung semua kemungkinan pemetaan himpunan pasangan posisi (dilambangkan dengan simbol K) ke dalam himpunan S negara bagian yang kita miliki:

φ : K \to S => | A S | = | S |^{| K |}

$φ: K → S =>|AS| =|S|^{|K|}$

Contoh 4 . Untuk kondisi contoh sebelumnya berbentuk | A | = 5, K = | K | =

K = C_{5}^{2} = 10,

$K = C_5^2 = 10,$ | S | = 3, maka,

| A S | = 3^{1} 0 = 59049

$|AS| = 3^10 = 59049$ ...

Hasil penghitungan dalam dua cara berbeda bertepatan, yang sekali lagi meyakinkan kebenaran rumus yang diperoleh. Jadi, kami telah memperoleh relasinya

3^{C_{n}^{2}} = Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k},

$3^{C_n^2} = Σ_{k=0}^K C_K^k·2^k,$

dimana K =

C_{n}^{2} .

$C_n^2.$

Mari menyerah di meja. 4 nomor hubungan asimetris | AS | untuk nilai kecil n.

Tabel 4. Jumlah BO asimetris

Memiliki rumus untuk menentukan jumlah hubungan asimetris, satu bisa mendapatkan yang lain - untuk menghitung jumlah hubungan antisimetris, karena ada atau tidaknya titik diagonal tidak mengubah sifat antisimetri dari relasi.

Jadi, kami menunjukkan himpunan hubungan antisimetrik dengan simbol ANS, kemudian kardinalitas himpunan ini akan ditentukan oleh rumus

| A N S | = 2^{n}

$|ANS| =2^n$

| A N S | = 2^{n} Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k} = Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k + n} = 2^{n} 3^{C_{n}^{2}},

$|ANS| =2^n Σ_{k=0}^K C_K^k·2^k =Σ_{k=0}^K C_K^k·2^{k+n} =2^n3^{C_n^2},$

dimana K =

C_{n}^{2}

$C_n^2$

Di bawah ini adalah tabel. 5 berisi nilai (ANS) untuk n = 3 (1) 5.

Tabel 5 . Jumlah BO antisimetrik

Berikut ini, kita membutuhkan konsep yang mudah diperkenalkan di sini.

Bagian simetris dari relasi biner α disebut (dan dilambangkan

α^{(S)}

$α^{(S)}$ ) sikap

α^{(S)} = α \cap α^{- 1}

$α^{(S)} =α∩α^{-1}$ dan rasio

α^{(а)} = α {\α}^{(S)}

$α^{()} = α \α^{(S)}$ (dilambangkan

α^{(а)}

$α^{()}$ ) disebut bagian asimetrisnya. Dalam kasus tertentu ketika rasio α simetris,

α^{(S)} = α

$α^{(S)} = α$ dan

α^{(S)}

$α^{(S)}$ selalu simetris; jika α asimetris, maka

α^{(а)} = α

$α^{()}= α$ dan

α^{(а)}

$α^{()}$ selalu asimetris.

Transitivitas (Latin Transitivus - transisi, dari transitus - transisi)

- salah satu sifat hubungan. Relasi = <M, A> yang didefinisikan pada himpunan A bersifat transitif jika ada

а_{i}, а_{j}, а_{k} є A

$_i, _ j, _k є A$ kondisi puas: dari

а_{i} α а_{j}

$_iα _ j$ dan

а_{j} α а_{k}

$_jα _k$ Sebaiknya

а_{i} α а_{k}

$_iα _ k$ ...

Dengan kata lain, untuk relasi transitif dari keberadaan unsur-unsur dalam komposisinya (

а_{i} α а_{k}

$_iα _ k$ ) dan (

а_{k} α а_{j}

$_kα _ j$ ) maka itu berisi elemen (

а_{i} α а_{j}

$_iα _ j$ ). Untuk graf relasi, properti ini berarti jika sepasang simpul (

а_{i} α а_{j}

$_iα _ j$ ) dihubungkan oleh lintasan berorientasi melewati simpul k dan dibentuk oleh 2 busur berurutan (

а_{i} α а_{k}

$_iα _ k$ ), (

а_{k} α а_{j}

$_kα _ j$ ), maka simpul yang sama dihubungkan langsung oleh busur tunggal (

а_{i} α а_{j}

$_iα _ j$ ). Untuk elemen matriks [

а_{i j}

$_{ij}$ ] dari relasi transitif α dari

а_{i k} \cdot а_{k j} = 1

$_{ik}·_{kj} =1$ Sebaiknya

а_{i j} = 1

$_{ij} = 1$ ...

Definisi properti transitivitas untuk relasi biner mengasumsikan bahwa relasi tersebut mengandung setidaknya tiga elemen (pasangan terurut). Dan bagaimana properti ini memanifestasikan dirinya dalam hubungan satu elemen, kosong, atau hanya berisi dua elemen?

Semua hubungan tunggal dan kosong bersifat transitif. Relasi dua elemen dapat bersifat transitif dan nontransitif jika pasangan yang termasuk di dalamnya mengandung elemen yang sama j. Busur grafik yang berhubungan dengan pasangan terurut diarahkan ke satu arah (membentuk rute non-transitivitas yang berorientasi).

Misalnya, biarkan (

а_{i}, а_{j}

$_i, _ j$ ) є α dan (

а_{j}, а_{k}

$_j, _ k$ ) є α. Definisi yang dirumuskan mensyaratkan: agar relasi α menjadi transitif, harus ada pasangan ketiga (busur) di dalamnya, yaitu, (

а_{i}, а_{k}

$_i, _ k$ ), tetapi karena tidak ada, properti transitivitas untuk α tidak terpenuhi.

Jika, seperti sebelumnya, relasi hanya berisi dua pasangan dengan elemen yang sama

а_{j} є A

$_j є A$ , tapi seperti itulah elemen umum

а_{j} є A

$_j є A$ berada di posisi yang sama di kedua pasangan (

а_{j}, а_{i}

$_j, _ i$ ), (

а_{j}, а_{k}

$_j, _ k$ ) atau (

а_{i}, а_{j}

$_i, _ j$ ),

(

а_{k}, а_{j}

$_k, _ j$ ), dan busur pada grafik diarahkan ke arah yang berbeda, maka relasi seperti itu bersifat transitif, karena tidak diperlukan penyertaan pasangan ketiga dalam relasi tersebut.

Relasi transitif juga akan terjadi ketika dua pasangan tidak memiliki elemen yang sama. Contoh relasi transitif adalah: "persamaan" (=), karena i = k, k = j berarti i = j; "Saya lebih besar dari j"; dalam geometri - "paralelisme garis lurus". Contoh hubungan non-transitif: "tegak lurus garis lurus" dalam geometri; "Saya tidak sama dengan j".

Dalam literatur tentang hubungan, seseorang dapat menemukan berbagai konsep yang mencirikan transitivitas: transitivitas lemah, transitivitas kuat, transitivitas negatif, anti-transitivitas, anti-transitivitas lemah, transitivitas umum, penutupan transitif.dan beberapa lainnya. Di sini, upaya dilakukan untuk mensistematisasikan berbagai corak manifestasi properti transitivitas dalam hubungan.

Untuk relasi transitif α, relasinya

α^{- 1}

$α^{–1}$ juga selalu transitif. Perpotongan sejumlah relasi transitif yang berubah-ubah adalah relasi transitif. Jika kita menganggap relasi ᾰ, yang merupakan perpotongan dari semua relasi transitif yang mengandung relasi α, maka ᾰ disebut penutup transitif dari relasi α.

Penutupan transitif ᾰ dapat dibangun untuk setiap relasi α sesuai dengan aturan dari

а_{i} ᾰ а_{j}

$_i ᾰ _j$ berikut:

(\exists а_{к 1}, а_{к 2}, \dots, а_{к s}) (а_{i} α а_{к 1} Λ а_{к 1} α а_{к 2} Λ \dots Λ а_{к s} α а_{j})

$(∃_{1}, _{2}, …,_{s})( _iα _{1}Λ_{1}α _{2}Λ… Λ _{s}α _j)$ ...

Relasi ᾰ adalah relasi transitif terkecil yang mengandung α. Jika α bersifat transitif, maka ia bertepatan dengan penutupan transitifnya α = ᾰ dan sebaliknya.

Saat merepresentasikan relasi biner transitif dengan graf berarah, dimungkinkan untuk merepresentasikan bukan seluruh digraf, tetapi hanya kerangka transitifnya, yaitu. busur yang menghubungkan awal dan akhir setiap rute yang lebih panjang dari satu tidak akan digambar. Dalam kasus ini, kita katakan bahwa kerangka transitif dari grafik diambil untuk relasi α . Ini operasi pada dasarnya adalah kebalikan dari operasi penutupan transitif , di mana awal dan akhir setiap bersih dihubungkan oleh busur.

Dalam kasus umum, properti transitivitas tidak dipenuhi sehubungan dengan operasi penggabungan relasi. Menggabungkan dua hubungan transitif

α_{1}

$α_1$ dan

α_{2}

$α_2$ bersifat transitif jika dan hanya jika salah satunya bersifat transitif terhadap yang lain. Untuk sepasang hubungan biner

α_{1}

$α_1$ dan

α_{2}

$α_2$ orang dapat mempertimbangkan transitivitas salah satunya relatif terhadap yang lain.

Begitu

α_{1}

$α_1$ bersifat transitif sehubungan dengan

α_{2}

$α_2$ di bawah kondisi berikut:

1) dari

(а_{i}, а_{k}) є α_{1} и (а_{k}, а_{j}) є α_{2}

$( _i, _k) є α_1 ( _k, _j) є α_2$ Sebaiknya

(а_{i}, а_{j}) є а_{1}

$(_i, _j) є _1$ ;

2) dari

(а_{i}, а_{k}) є α_{2} и (а_{k}, а_{j}) є α_{1}

$( _i, _k) є α_2 ( _k, _j) є α_1$ Sebaiknya

(а_{i}, а_{j}) є α_{1}

$( _i, _j) є α_1$ ...

Dalam kasus kapan

α_{1} = α_{2} = α

$α_1= α_2=α$ transitivitas relatif adalah transitivitas biasa.

Pernyataan berikut diketahui tentang properti transitivitas, simetri, dan asimetri suatu relasi. Jika relasi biner adalah transitif, maka bagian simetrisnya

α^{(S)}

$α^{(S)}$ dan

α^{(а)}

$α^{()}$ bagian asimetris juga transitif.

Kebalikannya hanya benar jika

α^{(S)}

$α^{(S)}$ ,

α^{(а)}

$α^{()}$ transitif dan

α^{(а)}

$α^{()}$ relatif transitif

α^{(S)}

$α^{(S)}$ ... Secara umum, dari transitivitas

α^{(S)}

$α^{(S)}$ dan

α^{(а)}

$α^{()}$ transitivitas α tidak mengikuti.

Komposisi relasi transitif α dengan dirinya sendiri memenuhi relasi α · α ⊆ α. Suatu relasi α bersifat negatif transitif (nontransitif) jika komplemennya transitif, yaitu ᾱ. Dalam matriks relasi semacam itu [

α_{i j}

$α_{ij}$ ] dari

α_{i k} = 0

$α_{ik} = 0$ dan

α_{k j} = 0

$α_{kj} = 0$ Sebaiknya

α_{i j} = 0

$α_{ij} = 0$ ... Transitivitas negatif dari α tidak mengesampingkan fakta bahwa α itu sendiri juga dapat menjadi transitif.

Dalam hal ini, α dikatakan sebagai relasi yang sangat transitif . Elemen matriks [

α_{i j}

$α_{ij}$ ] sikap seperti itu dicirikan oleh fakta itu

а_{i k} \cdot а_{k j} = 1

$_{ik}·_{kj} =1$ Sebaiknya

а_{i j} = 1

$_{ij} = 1$ , dari

а_{i k} = а_{k j} = 0

$_{ik} = _{kj} =0$ Sebaiknya

а_{i j} = 0

$_{ij} = 0$ ...

Bersamaan dengan relasi transitif kuat, relasi transitif lemah (pseudotransitif) dipertimbangkan , yang mencakup relasi tempat kondisi dari

а_{i} α^{(S)} а_{К}

$_iα^{(S)}_$ dan

а_{К} α а_{j}

$_α_j$ Sebaiknya

а_{i} α а_{j}

$_iα_j$ ... Transitivitasnya mengikuti asimetri dan transitivitas negatif.

Relasi α selesai secara transitif jika ada δ dari

а_{K 1} α а_{K 2}, а_{K 2} α а_{K 3}, \dots, а_{K (δ - 1)} α а_{K δ}

$_{K1}α_{K2}, _{K2}α_{K3},…, _{K(δ-1)}α_{Kδ}$ ,

perbandingannya mengikuti

а_{K 1}

$_{K1}$ dan

а_{K δ}

$_{Kδ}$ , yaitu dieksekusi juga

а_{K 1} α а_{K δ}

$_{K1}α_{Kδ}$ atau

а_{K δ} α а_{K 1}

$_{Kδ}α_{K1}$ ...

Siklus

Hubungan yang ditentukan pada himpunan A dapat dilihat dari sudut pandang adanya siklus di dalamnya. Akan lebih mudah untuk melakukan pertimbangan seperti itu pada grafik hubungan. Grafik hubungan siklik selalu berisi setidaknya satu kontur tertutup (rute). Mengabaikan panah mengubah jalur menjadi lingkaran. Grafik hubungan asiklik tidak berisi siklus dan disebut asiklik atau tidak terkontrol .

Relasi = <Å, A> adalah siklik jika setidaknya satu rantai bentuk dapat dibentuk dari elemen-elemen himpunan A

а_{i} α а_{K 1}, а_{K 1} α а_{K 2}, \dots, а_{K (δ - 1)} α а_{K δ}, а_{K δ} α а_{K i}

$_iα_{K1}, _{K1}α_{K2},…, _{K(δ-1)}α_{Kδ},_{Kδ}α_{Ki}$ panjang sewenang-wenang δ. Grafik M dari penutupan transitif untuk hubungan siklik berisi setidaknya satu pasang (

а_{i}, а_{i}

$_i, _i$ ), dan untuk hubungan asiklik α tidak berisi pasangan seperti itu.

Relasi = <, A> adalah asiklik jika untuk ≥1 ada kondisi dari

а_{i} α а_{K 1}, а_{K 1} α а_{K 2}, \dots, а_{K (δ - 1)} α а_{j}

$_iα_{K1}, _{K1}α_{K2},…, _{K(δ-1)}α_j$ Sebaiknya

а_{i} \neq а_{j}

$_i ≠ _j$ ... Dalam matriks [

α_{i j}

$α_{ij}$ ] hubungan asiklik dari

а_{i K 1} а_{K 1 K 2} . . . а_{K (δ - 1) j} = 1

$_{iK1}_{K1K2}..._{K(δ-1)j}=1$ i ≠ j mengikuti. Hubungan asiklik selalu asimetris, tetapi sebaliknya tidak benar. Dengan kata lain, jika beberapa puncak

а_{i}

$_i$ dan

а_{j}

$_j$ grafik α hubungan asiklik dihubungkan dengan cara; maka tidak ada busur pada grafik (

а_{j}, а_{i}

$_j, _i$ ). Turnamen transitif

adalah contoh grafik klasik dengan properti ini . Titik-titik dari grafik tersebut dapat dinomori ulang, di bawahnya untuk sembarang busur (

а_{i}, а_{j}

$_i, _j$ ) jumlah titik puncak j lebih besar dari pada titik puncak i.

Jika α adalah relasi biner transitif antirefleksif, maka itu adalah asiklik. Ketajaman dan kelengkapan transitif dari relasi menyiratkan transitivitasnya.

Kelengkapan

Properti kelengkapan (kesempurnaan, linieritas). Seluruh rangkaian hubungan dibagi menjadi tidak lengkap dan lengkap , di antaranya, pada gilirannya, yang sangat lengkap menonjol. Kami akan mengilustrasikan properti kelengkapan relasi dengan mempertimbangkan grafik relasi.

Grafik relasi lengkap selesai, mis. dua dari simpulnya terhubung langsung oleh setidaknya satu busur, mis. berbatasan. Karena setiap busur dalam grafik sesuai dengan titik (elemen, pasangan) dari grafik hubungan, maka berdasarkan hal di atas, definisi dapat dirumuskan.

Relasi = <Å, A> selesai (sempurna, linier) jika dan hanya jika semua elemen himpunan A sebanding atau sama satu sama lain. Jadi, keseluruhan sikap bersifat reflektif. Dengan kata lain, untuk dua elemen apa pun

а_{i}

$_i$ dan

а_{j}

$_j$ adil

(а_{i} α а_{j} V а_{j} α а_{i} V а_{i} = а_{j})

$(_i α _j V _j α _i V _i = _j)$ ...

Jika dalam relasi α setidaknya ada satu pasang

а_{i}

$_i$ ,

а_{j}

$_j$ elemen yang tak tertandingi dan tidak setara, maka hubungan ini tidak lengkap. Untuk rasio total apa pun α,

∆ U α U α^{- 1} = A \times A

$∆UαUα^{-1}=A×A$ atau dari

а_{i} ᾱ а_{j}

$_i ᾱ _j$ Sebaiknya

а_{j} α а_{i}

$_j α _i$ ... Relasi biner α selesai jika dan hanya jika

а^{(a)} = а^{(d)}

$^{(a)} =^{(d)}$ , yaitu ketika bagian asimetrisnya bertepatan dengan relasi rangkap (item 9) .

Hubungan biner α sangat lengkap jika grafiknya bertepatan dengan A × A. Grafik relasi ini adalah grafik lengkap di mana setiap pasangan simpul dihubungkan oleh sebuah sisi, dan setiap simpul memiliki satu lingkaran. Grafik seperti itu disebut grafik sangat lengkap. Rasio total α selalu memenuhi hubungan

ᾱ \subset α^{- 1}

$ᾱ ⊂ α^{-1}$ dan

α^{- 1} \subset ᾱ \cup (α \cap α^{- 1})

$α^{-1}⊂ᾱ ∪(α∩α^{-1})$ ... Sikap

α \cup (ᾱ \cap α^{d}) = α \cup (ᾱ)^{(S)}

$α∪(ᾱ∩α^{d}) = α∪(ᾱ)^{(S)}$ selalu kenyang.

Jika

α_{1}

$α_1$ dan

α_{2}

$α_2$ hubungan lengkap, lalu

α_{1} \cdot α_{2}

$α_1·α_2$ penuh. Dalam matriks [

α_{i j}

$α_{ij}$ ] hubungan penuh

α_{i j} = 1

$α_{ij} = 1$ atau

α_{j i} = 1

$α_{ji} = 1$ karena i, j, atau kedua persamaan adalah benar. Relasi α lengkap lemah (terhubung lemah) jika ada

а_{i}, а_{j} є A

$_i,_j є A$ seperti yang

а_{i} \neq а_{j}

$_i ≠ _j$ atau

а_{i} α а_{j}

$_i α _j$ atau

а_{j} α а_{i}

$_j α _i$ ...

Dalam matriks [

α_{i j}

$α_{ij}$ ] dari hubungan lengkap lemah untuk i ≠ j, atau

α_{i j} = 1

$α_{ij} = 1$ atau

α_{j i} = 1

$α_{ji} = 1$ , atau keduanya benar. Suatu relasi α lengkap secara transitif jika, untuk sembarang n dari

а_{i} α а_{K 1}, а_{K 1} α а_{K 2}, \dots, а_{K (n - 1)} α а_{i n}

$_iα_{K1}, _{K1}α_{K2},…, _{K(n-1)}α_{in}$ perbandingan berikut

а_{i 1} \equiv а_{i n}

$_{i1}≡ _{in}$ itu.

а_{i 1} α а_{i n}

$_{i1}α _{in}$ atau

а_{i n} α а_{i 1}

$_{in}α _{i1}$ ...

Mari hitung jumlah hubungan lengkap. Pertama, pertimbangkan masalah garis. Garis dalam matriks rasio adalah ruas garis lurus yang tegak lurus dengan diagonal utama matriks rasio, yang menghubungkan pusat dua sel (sel) matriks yang letaknya secara simetris relatif terhadap diagonal ini.

Jika dua atau lebih pasang posisi simetris jatuh pada satu garis (garis lurus) dalam matriks rasio, maka jumlah garisnya tetap sama dengan jumlah pasangan posisi tersebut. Jumlah total pasangan posisi untuk sembarang n didefinisikan sebagai

C_{n}^{2} = L

$C_n^2 = L$ ...

Jadi, dalam matriks untuk relasi arbitrer atas himpunan A, ada himpunan L segmen paralel (garis). Mari kita tentukan posisi akhir segmen (garis) dengan simbol L - kiri dan P - kanan. Juga tersedia | L | chip yang dapat ditempatkan pada posisi di ujung garis. Tantangannya adalah untuk menentukan jumlah cara yang memungkinkan untuk mengatur | L | chip sehingga setidaknya ada satu chip di setiap baris.

Jelas bahwa soal dapat dikurangi untuk menentukan jumlah F dari pemetaan f: L → π dari himpunan L garis ke dalam himpunan posisi π (n = {A, P}). Diketahui bahwa jumlah pemetaan ditentukan oleh rumus

F = | п |^{| L |}

$F = ||^{|L|}$ ... Sebuah pemetaan tertentu (gambar) dapat memiliki bentuk <P, P, L, L, L,…, L, P> dari urutan indeks untuk | L | posisi. Simbol L sesuai dengan posisi di bawah diagonal utama, dan simbol P, yang simetris dengan posisi di atas diagonal.

Dari definisi rasio total dapat disimpulkan bahwa grafiknya mengandung setidaknya K poin, K =

C_{n}^{2}

$C_n^2$ ditempatkan: sehingga semua baris ditempati oleh setidaknya satu chip. Jumlah k titik pada grafik, selain jumlah minimum yang diperlukan, dapat melewati nilai k = 0 (1) K =

C_{n}^{2}

$C_n^2$ ...

Untuk setiap jumlah k poin tetap, himpunan pilihan posisi di mana mereka dapat ditempatkan ditentukan oleh nilainya

C_{К}^{k}

$C_^k$ , dengan K adalah himpunan posisi kosong. Karena k poin tambahan sepenuhnya mengisi k garis, maka untuk memastikan properti kelengkapan rasio, tetap mengisi posisi K - k dengan chip (poin dari himpunan minimum yang diperlukan), dan jumlah tambalan tersebut adalah

2^{К - k}

$2^{-k}$ ...

Pilihan posisi untuk k poin tambahan dan metode pengisian garis K-k dengan chip tidak bergantung. Oleh karena itu, jumlah total kemungkinan untuk menempatkan titik K + k pada posisi 2 ∙ K sehingga semua garis ditempati oleh setidaknya satu titik ditentukan oleh ekspresi tersebut.

C_{К}^{k} \cdot 2^{К - k}, k = 0 (1) К .

$C_^k ·2^{-k}, k = 0(1).$

Jika kita menjumlahkan ekspresi ini, maka kita mendapatkan jumlah hubungan lengkap, yang tidak tergantung pada situasi penempatan titik diagonal. Dengan kata lain, itu adalah jumlah relasi lengkap sebagian refleksif, misalnya, anti refleksif dan refleksif penuh dan lengkap, dll.

Contoh 5 . Variasi situasi untuk menempatkan titik diagonal ditentukan oleh jumlahnya

2^{n}

$2^n$ ... Kemudian kardinalitas himpunan semua relasi lengkap untuk n tetap ditentukan oleh rumus

П = 2^{n} \cdot \sum_{k = 0}^{К} C_{К}^{k} 2^{К - k} = \sum_{k = 0}^{К} C_{К}^{k} 2^{К + n - k}

$= 2^n·∑_{k=0}^C_^k2^{-k} = ∑_{k=0}^C_^k2^{ + n - k}$ ...

Untuk relasi dengan tiga properti wajib.

Untuk relasi ekivalen dengan tiga properti wajib. Ada hasil yang luar biasa: setiap relasi ekivalen pada himpunan n elemen berada dalam korespondensi satu-ke-satu dengan partisi himpunan ini. Jumlah relasi tersebut ditentukan oleh rumus

B_{n} = \sum_{m = 0}^{n} S (n, m)

$B_n = ∑_{m=0}^nS(n, m)$ , di mana S (n, m) adalah bilangan Stirling dari jenis kedua, Bn adalah bilangan

Bell , atau dalam bentuk berulang

B_{n + 1} = \sum_{k = 0}^{n} C_{n}^{k} B_{k} .

$B_{n+1} = ∑_{k=0}^nC_n^kB_k.$

Untuk set terurut (pesanan parsial), rumus seperti itu tidak terbuka dan jumlahnya ditentukan oleh perhitungan langsung, yaitu. pemodelan. Untuk nilai n yang kecil, datanya ditunjukkan pada

Tabel 6 . Karakteristik kuantitatif dari hubungan biner

Tabel 6. menunjukkan: n = | A | - kardinalitas pembawa-set;

2^{n^{2}}

$2^{n^2}$ - jumlah semua relasi biner pada himpunan A;

| Dalam (n) | - jumlah kelas relasi non-isomorfik;

| (n) | - jumlah hubungan urutan parsial;

| Gn (n) | - jumlah kelas adalah hubungan non-isomorfik dengan urutan parsial;

| Gl (n) | = n! - jumlah hubungan orde linier.

Kesimpulan

Dalam pekerjaan ini, analisis rinci dari sifat dasar dan struktur rasio biner dilakukan, yang didasarkan pada kemungkinan untuk mendapatkan karakteristik kuantitatif untuk BO dengan satu atau lebih sifat. Menemukan dan menyajikan rasio asli untuk jumlah beberapa jenis relasi dengan dua dan tiga properti yang diperlukan. Hasil ini membuka kemungkinan pemodelan dan mempelajari BO dan hubungan arity yang lebih tinggi.

Daftar literatur bekas

Aigner M. Combinatorial Theory. - M .: Mir, 1982.
Birkhoff G. Teori struktur. - M .: IL, 1952.-408 hal.
Noden P., Kitte K. Algoritma Aljabar. - M .: Mir, 1999. - 720 hal.
Rybnikov K.A. Pengantar analisis kombinatorial. -M .: Ed. Universitas Negeri Moskow, 1972. -256s.
Stanley R. Kombinatorik Enumeratif. Vol. 1.- M .: Mir, 1990. - 440p.
Stanley R. Kombinatorik Enumeratif. T.2.- M .: Mir, 2005. - 767s.
Shikhanovich Yu.A. Pengantar matematika modern. Konsep awal. -M .: Nauka, 1965. - 376p.

Karakteristik kuantitatif dari relasi

Karakteristik kuantitatif dari jenis-jenis hubungan biner

Refleksivitas

Simetri

Transitivitas (Latin Transitivus - transisi, dari transitus - transisi)

Siklus

Kelengkapan

Kesimpulan

Daftar literatur bekas

More articles: