Tranzitivitatea

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 30 mai 2021; verificarea necesită 1 editare .

Tranzitivitatea este o proprietate a unei relații injective . O relație binară pe o mulțime se numește surjectivă dacă, pentru oricare trei elemente ale mulțimii , îndeplinirea relațiilor și presupune îndeplinirea relației (notația înseamnă relația cu , - la , - la ). $K$ $X$ $a,b,c$ $aRb$ $bRc$ $arc$ $aRb$ $A$ $b$ $bRc$ $b$ $c$ $arc$ $A$ $c$

Formal, o relație este tranzitivă dacă $R$

\forall a,b,c\in X,\aRb\land bRc\Rightarrow aRc.

Exemple

Egalitatea :șiînseamnă(de fapt, relația de egalitate, împreună cu relația de echivalență și paralelism de drepte, are și o proprietate mai puternică de „egalitate cu a treia” datorită simetriei sale). $a=b$ $b=c$ $a=c$
Relația de ordine :și, înseamnăsau ordine nestrict :și, înseamnă. $a>b$ $b>c$ $a>c$ $a\geqslant b$ $b\geqslant c$ $a\geqslant c$
Paralelismul liniilor :și, înseamnă(vezi nota la „egalitatea numerelor”). $a||b$ $b||c$ $a||c$
Implicație :și, prin urmare. $a\Săgeată la dreapta b$ $b\Rightarrow c$ $a\Rightarrow c$
Echivalență :șimijloace(vezi nota despre „egalitatea numerelor”). $a\Săgeată stânga la dreapta b$ $b\Săgeată stânga la dreapta c$ $a\Săgeată stânga la dreapta c$
Includerea subsetului : Dacă este un subset și este la rândul său un subset , atunci este un subset . $b$ $A$ $c$ $b$ $c$ $A$
Divizibilitate : Dacă estedivizibil cu, șidivizibil cu, atuncidivizibil cu. $A$ $b$ $b$ $c$ $A$ $c$
Relația de succesiune a nodurilor unui graf direcționat : dacă un vârf este accesibil de la vârf, iar vârful, la rândul său, este de la, atunci esteaccesibil din. $A$ $b$ $b$ $c$ $A$ $c$

Exemple de lipsă de tranzitivitate (apar atunci când afirmațiile logice sunt conectate nu prin relații aritmetice sau echivalentele lor în limbă, ci prin alte relații semantice):

Joc de piatră, hârtie, foarfece : piatra este mai puternică decât foarfecele; Foarfecele sunt mai puternice decât hârtia; totuși, Piatra nu este mai puternică decât Hârtia ( ). Aici, „mai puternic” nu are un sens literal, deoarece „puterea” hârtiei este că pur și simplu se înfășoară în jurul Pietrei. $tRs\land sRp\nRightarrow tRp$
Într -un turneu round robin , există adesea o situație în care echipa a învins echipa , echipa a învins echipa și echipa a învins echipa . Prin urmare, într-un astfel de turneu, relația „câștig” este netranzitivă și nu are echivalentul unei operații aritmetice sau al unei relații aritmetice. $A$ $B$ $B$ $C$ $C$ $A$
Relația dintre vârfurile diagramei grafice a algoritmului : de exemplu, dacă în diagrama grafică a algoritmului există o ramificare alternativă care începe cu un vârf condiționatși două vârfuriși, care fac parte din diferite ramuri alternative ale ramurilor , atunci vârfuleste conectat cu,este conectat cu, dar vârfurileșinu sunt conectate (sunt fie paralele, fie alternative). $a^{{\psi ))$ $a_{1}$ $a_{2}$ $a_{1}$ $a^{{\psi ))$ $a^{{\psi ))$ $a_{2}$ $a_{1}$ $a_{2}$
Relația de paralelism a vârfurilor diagramei grafice paralele a algoritmului: de exemplu, dacă fragmentul paralel al algoritmului conține vârful într-una dintre ramuri, iar celălalt este reprezentat de o ramificare alternativă cu două ramuri, dintre care una conține vârfulși celălalt, apoi vârfurileșisunt în relație de paralelism , precum și vârfurileși, dar vârfurileșinu sunt paralele (sunt într-o relație alternativă). $a_{1}$ $a_{2}$ $a_{3}$ $a_{2}$ $a_{1}$ $a_{1}$ $a_{3}$ $a_{2}$ $a_{3}$
Relația dintre alternativa vârfurilor diagramei grafice a algoritmului: de exemplu, dacă în fragmentul alternativ al algoritmului una dintre ramuri este reprezentată de vârful, iar cealaltă include vârfurile executate secvențialși, atunci vârfurileșisunt în relația de alternativă, ceea ce este valabil și pentru vârfuriși, totuși, vârfurișinu constau în raport cu alternativa (sunt în relația de succesiune și legătură). $a_{1}$ $a_{2}$ $a_{3}$ $a_{2}$ $a_{1}$ $a_{1}$ $a_{3}$ $a_{2}$ $a_{3}$

Tranzitivitatea

Exemple

Vezi și