Matematické Fórum

Aquabellla · 30. 12. 2011 18:03

Zdravím, mám úlohu z diskrétní matematiky:
Najděte všechny relace na množině {0; 1} a určete, které jsou reflexivní, symetrické, antisymetrické, tranzitivní a zobrazení.
P({0; 1} x {0; 1}) - množina všech podmnožin

Řešení:
$\o$ STA
${(0; 0)}$ STA, ${(1; 1)}$ STA, ${(0; 1)}$ TA, ${(1; 0)}$ TA
${(0; 0), (0; 1)}$ TA, ${(1; 0), (0; 1)}$ SZ, ${(0; 0), (1; 1)}$ RSTAZ, ${(0; 0), (1; 0)}$ TAZ, ${(1; 0), (1; 1)}$ A, ${(0; 1), (1; 1)}$ TAZ
${(0; 0), (0; 1), (1; 0)}$ S, ${(0; 0), (0; 1), (1; 1)}$ RTA, ${(0; 0), (1; 0), (1; 1)}$ RTA, ${(0; 1), (1; 0), (1; 1)}$ S
${(0; 0), (0; 1), (1; 0), (1; 1)}$ RST

Jak se na to přijde:
Zobrazení: ${(x; y), (u; v)}$ - pokud $(x = u)$ , potom $(y = v)$
Reflexivita: musí obsahovat (0; 0) i (1; 1)
Symetrie: když obsahuje (0; 1), musí obsahovat i (1; 0) apod.

Nemohu přijít, jak se u těchto relací přijde na antisymetrii a tranzitivitu?
Předem díky :-)

jarrro · 30. 12. 2011 18:23

tranzitívna je keď $\left(\forall a,b,c\right)\left(\left(\left(a;b\right)\in R\wedge \left(b;c\right)\in R\right)\Rightarrow \left(\left(a;c\right)\in R\right)\right)$
a antisymetrická $\left(\forall a,b\right)\left(\left(\left(a;b\right)\in R\wedge \left(b;a\right)\in R\right)\Rightarrow \left(a=b\right)\right)$

Aquabellla · 30. 12. 2011 18:29

↑ jarrro:

Ano, definice znám, ale neumím je aplikovat na tyto relace.
Například proč relace ${(0; 0), (1; 0)}$ je tranzitivní i antisymetrická?

jarrro · 30. 12. 2011 18:37

↑ Aquabellla:tak tranzitívna je,lebo predpoklad v tej implikácii nie je splnený teda je tá implikácia pravdivá. antisymetrická je,lebo tiež v definičnej implikácii predpoklad splňujú len dve nuly a pre ne to je splnené

Aquabellla · 30. 12. 2011 18:47

↑ jarrro:

Antisymetrii snad chápu, jen mi přijde, že i poslední relace by měla být antisymetrická ${(0; 0), (0; 1), (1; 0), (1; 1)}$ , mám pravdu?

K té tranzitivitě, proč není splněna? Když si vezmu (a; b) = (1; 0) a (b; c) = (0; 0), tak pak (a; c) = (1; 0), což je prvkem relace.

jarrro · 30. 12. 2011 18:55

${(0; 0), (0; 1), (1; 0), (1; 1)}$ nie je antisymetrická,lebo (0;1) je v relácii aj (1;0) je v relácii a 0 sa predsa nerovná jednej
čo sa týka relácie ${(0; 0), (1; 0)}$ tak máš pravdu pomýlil som sa,ale ako si povedala (1;0) je prvkom relácie takže podmienka v definícii je splnená teda je relácia tranzitívna

Aquabellla · 30. 12. 2011 19:07

↑ jarrro:

Super, už to chápu, díky :-)

A když jsem si procházela ty zbývající relace, asi mám u jedné chybu... ${(1; 0), (1; 1)}$ by měla být tranzitivní, protože když si zvolím (1; 1) = (a; b) a (1; 0) = (b;c), tak pak (a; c) = (1; 0), což je prvek relace. Říkám to správně?

vanok · 30. 12. 2011 19:08 — Editoval vanok (30. 12. 2011 19:11)

Ahoj ↑ jarrro:,
Transitivita je tu efektivna v tychto
pripadoch
$(0;0) \wedge (0;0)$
a
$(1;0) \wedge (0;0)$

Poznamka: da sa na to pozerat ako na wagony so maju rovnake konce...

Antisymetria plati, lebo nemas ine symetricke prvky ... az na $((0;0)$
*************
Ahoj ↑ Aquabellla:,
${(0; 0), (0; 1), (1; 0), (1; 1)}$ sa je tranzitivna ( lebo mas vsetki prvky z {0; 1} x {0; 1})
a ako aj symetricka
ale nie anitisymetricka
lebo mas
$(0;1) \wedge (1;0)$ ale $0 \ne 1$

jarrro · 30. 12. 2011 19:09 — Editoval jarrro (23. 03. 2022 09:38)

↑ Aquabellla:áno [mathjax]\left\{\left(1; 0\right), \left(1; 1\right)\right\}[/mathjax] je tranzitívna

Aquabellla · 30. 12. 2011 19:11

↑ jarrro: ↑ vanok:

Díky moc oběma!

Wotton · 02. 01. 2012 12:06 — Editoval Wotton (02. 01. 2012 12:08)

↑ jarrro:

jen si dovolím malou poznákmu. Máš samozřejmě pravdu, ale aby to nebylo tak jednoduchý, tak v literatuře se vyskytují 2 rozdílné definice antisymetrické relace.

Ta druhá (mně bližší, protože tak jsem se to učil) je $\forall a,b\left(\left(a;b\right)\in R\rightarrow\left(b;a\right)\not\in R\right)$ ... pro tebou uváděno se pak používá termín Slabá antisymetrie.

jarrro · 02. 01. 2012 13:42

↑ Wotton:neviem čo sme my v Banskej Bystrici mali v prvom ročníku úvodný kurz tak tam bola antisymetrická $\left(\forall a,b\right)\left(\left(\left(a;b\right)\in R\wedge \left(b;a\right)\in R\right)\Rightarrow \left(a=b\right)\right)$ a čo si ty uviedol tak to bola tuším asymetrická(hádam nie naopak,ale všetko je možné)

Wotton · 02. 01. 2012 19:28

↑ jarrro:

jojo, teď si vzpomínám, že jak říkáš tak se ji říká (v té druhé konvenci) asymetrická.

A jak koukám, tak to co píšu může vyznít nejednoznačně, takže raději ještě přehledně:

$\forall a,b\left(\left(\left(a;b\right)\in R\wedge \left(b;a\right)\in R\right)\rightarrow \left(a=b\right)\right)$ je podle I. konvence antisymetrická a podle II. slabě antisymetrická
$\forall a,b\left(\left(a;b\right)\in R\rightarrow\left(b;a\right)\not\in R\right)$ je podle I. konvence asymetrická, podle II. konvence antisymetrická

tím nechci říct že je jedna konvence špatně (obě se používají - v češtině určitě a předpokládám že ve slovenštině taky), jen je potřeba si na to dávat pozor.

Matematické Fórum

#1 30. 12. 2011 18:03

Relace na množině {0, 1}

#2 30. 12. 2011 18:23

Re: Relace na množině {0, 1}

#3 30. 12. 2011 18:29

Re: Relace na množině {0, 1}

#4 30. 12. 2011 18:37

Re: Relace na množině {0, 1}

#5 30. 12. 2011 18:47

Re: Relace na množině {0, 1}

#6 30. 12. 2011 18:55

Re: Relace na množině {0, 1}

#7 30. 12. 2011 19:07

Re: Relace na množině {0, 1}

#8 30. 12. 2011 19:08 — Editoval vanok (30. 12. 2011 19:11)

Re: Relace na množině {0, 1}

#9 30. 12. 2011 19:09 — Editoval jarrro (23. 03. 2022 09:38)

Re: Relace na množině {0, 1}

#10 30. 12. 2011 19:11

Re: Relace na množině {0, 1}

#11 02. 01. 2012 12:06 — Editoval Wotton (02. 01. 2012 12:08)

Re: Relace na množině {0, 1}

#12 02. 01. 2012 13:42

Re: Relace na množině {0, 1}

#13 02. 01. 2012 19:28

Re: Relace na množině {0, 1}

Zápatí