3. gyakorlat

Fontos fogalmak

\(R \subseteq A \times B\)

Reflexív és irreflexív

Reflexív: \(\forall a \in A:\quad(a,a) \in R\)

Irreflexív: \(\forall a \in A:\quad(a,a) \notin R\)

(Kizárják egymást, de nem egymás ellentétei!)

Szimmetrikus és antiszimmetrikus

Szimmetrikus: \(\forall (a,b) \in R \quad \Rightarrow \quad (b,a) \in R\)

Antiszimmetrikus: \((a,b) \in R \wedge (b,a) \in R \quad \Rightarrow \quad a = b\)

(A szimmetria és az antiszimmetria nem zárják ki egymást!)

Tranzitív

Tranzitív: \((a,b) \in R \wedge (b,c) \in R \quad \Rightarrow \quad (a,c) \in R\)

További tulajdonságok

További tulajdonságok 1

\(R \subseteq A \times B; \quad R \ne \varnothing\)

Állítás: Ha \(R\) irreflexív és szimmetrikus, akkor nem tranzitív.

\(R \subseteq A \times B\)

Ha \(\; \forall a \in A: (a,a) \notin R \quad \land \quad \forall (a,b) \in R \Rightarrow (b,a) \in R\), akkor $$\(a,b) \in R \quad \land \quad (b,c) \in R \nRightarrow (a,c) \in R\)

Ekvivalenciareláció

Reflexív, tranzitív és szimetrikus

Gráffal leírható

Ekvivalencia osztályok

• Ezek mindig teljes gráfok
• Diszjunktak
• Egy elem is alkothatja (önmagával biztos, hogy kapcsolatban van)