WikiDer > Тәуелділік қатынасы

Бұл мақала үшін қосымша дәйексөздер қажет тексеру. Өтінемін көмектесіңіз осы мақаланы жақсарту арқылы дәйексөздерді сенімді дерек көздеріне қосу. Ресурссыз материалға шағым жасалуы және алынып тасталуы мүмкін. Дереккөздерді табу: «Тәуелділік қатынасы» – жаңалықтар · газеттер · кітаптар · ғалым · JSTOR (Наурыз 2008 ж) (Бұл шаблон хабарламасын қалай және қашан жою керектігін біліп алыңыз)

Жылы Информатика, атап айтқанда параллельдік теория, а тәуелділік қатынасы Бұл екілік қатынас бұл шектеулі,^[1]:4 симметриялы, және рефлексивті;^[1]:6 яғни ақырлы төзімділік қатынасы. Яғни, бұл шекті жиынтығы жұптарға тапсырыс берді ${displaystyle D}$, осылай

• Егер ${displaystyle (a, b) in D}$ содан кейін ${displaystyle (b, a) in D}$ (симметриялы)
• Егер ${displaystyle a}$ - бұл қатынас анықталатын жиынның элементі, содан кейін ${displaystyle (a, a) in D}$ (рефлексивті)

Жалпы, тәуелділік қатынастары болмайды өтпелі; осылайша олар ан ұғымын жалпылайды эквиваленттік қатынас транзитивтілікті жою арқылы.

Егер ${displaystyle Sigma}$ (деп те аталады алфавит) жиынтығын білдіреді ${displaystyle D}$ анықталады, содан кейін тәуелсіздік туындаған ${displaystyle D}$ екілік қатынас болып табылады ${displaystyle I}$

${displaystyle I = (Sigma imes Sigma) setminus D}$

Яғни, тәуелсіздік дегеніміз барлық реттелген жұптардың жиынтығы ${displaystyle D}$. Тәуелсіздік қатынасы симметриялы және рефлексті емес. Керісінше, кез-келген симметриялы және иррефлекторлы байланыс берілген ${displaystyle I}$ ақырлы алфавит бойынша, қатынас

${displaystyle D = (Sigma imes Sigma) setminus I}$

тәуелділік қатынасы болып табылады.

Жұптар ${displaystyle (Sigma, D)}$ және ${displaystyle (Sigma, I)}$,^{[дәйексөз қажет]} немесе үштік ${displaystyle (Sigma, D, I)}$ (бірге ${displaystyle I}$ туындаған ${displaystyle D}$) кейде деп аталады қатарлас алфавит^{[дәйексөз қажет]} немесе сенім алфавиті. Бұл жағдайда элементтер ${displaystyle x, yin Sigma}$ деп аталады тәуелді егер ${displaystyle xDy}$ және ұстайды тәуелсіз, басқасы (яғни, егер ${displaystyle xIy}$ ұстайды).^[1]:6

Сенім алфавиті берілген ${displaystyle (Sigma, D, I)}$, симметриялы және рефлексивті қатынас ${displaystyle doteq}$ бойынша анықтауға болады ақысыз моноид ${displaystyle Sigma ^ {*}}$ ақырлы ұзындықтың барлық мүмкін жолдарының: ${displaystyle xabydoteq xbay}$ барлық жолдар үшін ${displaystyle x, yin Sigma ^ {*}}$ және барлық тәуелсіз рәміздер ${displaystyle a, бин I}$. The эквиваленттілікті жабу туралы ${displaystyle doteq}$ деп белгіленеді ${displaystyle equiv}$, немесе ${displaystyle equiv _ {(Sigma, D, I)}}$, және шақырды ${displaystyle (Sigma, D, I)}$-эквиваленттілік. Ресми емес, ${displaystyle pequiv q}$ егер жіп болса ${displaystyle p}$ түрлендірілуі мүмкін ${displaystyle q}$ шектес тәуелсіз шартты белгілерді ауыстырудың ақырлы тізбегі бойынша. The эквиваленттік сыныптар туралы ${displaystyle equiv}$ деп аталады іздер,^[1]:7–8 және оқылады із теориясы.

Мысалдар

Алфавит берілген ${displaystyle Sigma = {a, b, c}}$, мүмкін тәуелділік қатынасы ${displaystyle D = {(a, b) ,, (b, a) ,, (a, c) ,, (c, a) ,, (a, a) ,, (b, b) ,, (c, в)}}$, суретті қараңыз.

Тиісті тәуелсіздік ${displaystyle I = {(b, c) ,, (c, b)}}$. Содан кейін, мысалы. таңбалар ${displaystyle b, c}$ бір-біріне тәуелді емес және т.б. ${displaystyle a, b}$ тәуелді. Жіп ${displaystyle acbba}$ дегенге тең ${displaystyle abcba}$ және дейін ${displaystyle abbca}$, бірақ басқа жолға.

Әдебиеттер тізімі

Бұл абстрактілі алгебра- қатысты мақала а бұта. Сіз Уикипедияға көмектесе аласыз оны кеңейту. v т e

Бұл Информатика мақала бұта. Сіз Уикипедияға көмектесе аласыз оны кеңейту. v т e