Tranzitivita

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 30. května 2021; ověření vyžaduje 1 úpravu .

Tranzitivita je vlastnost injektivního vztahu . Binární relace na množině se nazývá surjektivní, jestliže pro kterékoli tři prvky množiny je splnění relací a znamená splnění relace (zápis znamená vztah k , - k , - k ). $K$ $X$ $a,b,c$ $aRb$ $bRc$ $oblouk$ $aRb$ $A$ $b$ $bRc$ $b$ $C$ $oblouk$ $A$ $C$

Formálně je relace tranzitivní, jestliže $R$

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

Příklady

Rovnost :aznamená(ve skutečnosti má vztah rovnosti spolu se vztahem ekvivalence a rovnoběžnosti úseček díky své symetrii také silnější vlastnost „rovnosti do třetice“). $a=b$ $b=c$ $a=c$
Řádový vztah :a, znamenánebo nestriktní pořadí :a, znamená. $a>b$ $b>c$ $a>c$ $a\geqslant b$ $b\geqslant c$ $a\geqslant c$
Rovnoběžnost čar :a, znamená(viz poznámka k "rovnosti čísel"). $a||b$ $b||c$ $a||c$
Implikace :aproto. $a\Šipka doprava b$ $b\Šipka doprava c$ $a\Šipka doprava c$
Ekvivalence :aznamená(viz poznámka o „rovnosti čísel“). $a\Šipka doleva b$ $b\Šipka doleva c$ $a\Šipka doleva c$
Zahrnutí podmnožiny : Jestliže je podmnožinou a je zase podmnožinou , pak je podmnožinou . $b$ $A$ $C$ $b$ $C$ $A$
Dělitelnost : Je-lidělitelná, adělitelná, pakdělitelná. $A$ $b$ $b$ $C$ $A$ $C$
Relace posloupnosti vrcholů orientovaného grafu : pokud je vrchol dosažitelný z vrcholua vrcholje naopak z, pak jedosažitelný z. $A$ $b$ $b$ $C$ $A$ $C$

Příklady nedostatečné tranzitivity (vyskytují se, když logické příkazy nejsou spojeny aritmetickými vztahy nebo jejich ekvivalenty v jazyce, ale jinými sémantickými vztahy):

Hra kámen, papír, nůžky : Kámen je silnější než nůžky; Nůžky jsou silnější než papír; kámen však není silnější než papír ( ). Zde „silnější“ nemá doslovný význam, protože „síla“ papíru spočívá v tom, že se jednoduše obalí kolem kamene. $tRs\land sRp\nŠipka doprava tRp$
V turnaji s cyklisty často dochází k situaci, kdy tým porazil tým , tým porazil tým a tým porazil tým . Proto je v takovém turnaji relace „výhra“ netranzitivní a nemá ekvivalent aritmetické operace nebo aritmetického vztahu. $A$ $B$ $B$ $C$ $C$ $A$
Vztah mezi vrcholy grafu diagramu algoritmu : například pokud v grafu diagramu algoritmu existuje alternativní větvení, které začíná podmíněným vrcholema dvěma vrcholya, které jsou součástí různých alternativních větví větve , pak je vrcholspojen s,je spojen s, ale vrcholyanejsou spojeny (jsou buď paralelní, nebo alternativní). $a^{{\psi ))$ $a_{1}$ $a_{2}$ $a_{1}$ $a^{{\psi ))$ $a^{{\psi ))$ $a_{2}$ $a_{1}$ $a_{2}$
Paralelní vztah vrcholů diagramu paralelního grafu algoritmu: například pokud paralelní fragment algoritmu obsahuje vrchol v jedné z větvía druhý je reprezentován alternativním větvením se dvěma větvemi, z nichž jedna obsahuje vrchola druhý, pak vrcholyajsou ve vztahu rovnoběžnosti , stejně jako vrcholya, ale vrcholyanejsou rovnoběžné (jsou v alternativním vztahu). $a_{1}$ $a_{2}$ $a_{3}$ $a_{2}$ $a_{1}$ $a_{1}$ $a_{3}$ $a_{2}$ $a_{3}$
Vztah alternativy vrcholů grafu diagramu algoritmu: pokud je například v alternativním fragmentu algoritmu jedna z větví reprezentována vrcholema druhá zahrnuje postupně prováděné vrcholya, pak vrcholyajsou ve vztahu alternativy, což platí i pro vrcholyavrcholyaneskládají se ve vztahu k alternativě (jsou ve vztahu posloupnosti a spojení). $a_{1}$ $a_{2}$ $a_{3}$ $a_{2}$ $a_{1}$ $a_{1}$ $a_{3}$ $a_{2}$ $a_{3}$

Tranzitivita

Příklady

Viz také