- 締切済み
計算機科学 同値関係の問題です。
Anti-Giantsの回答
- Anti-Giants
- ベストアンサー率44% (198/443)
No1.です。 まず、訂正があります。 前の回答で初めの方で「対称律」といっているのは間違いで、正しくは「反射律」です。 >>ちなみに同条件で w≦w’ ⇔ l(w)≦l(w’) (このときl(w)は文字列wの長さ) が半順序集合であるか? という問題があり、僕は半順序集合だと思ったのですが、どうでしょうか? 反対称率を満たしません。 文字列の長さが等しくても、文字列が等しいとは言えませんから。 具体例で言うと w(1) = "a", w(2) = "b" は |w(1)| ≦ |w(2)|かつ |w(2)| ≦ |w(1)|ですが、w(1) ≠ w(2)です。 (|x|はxの長さ) >>反射律:w、w’∈X* に対して w≦w’ ⇔ l(w)≦l(w’)は成立。 これは、反射律を勘違いしています。反射律とは x ≦ x を満たすということです。「同じ元どうしに順序を定義できるか?」ということです。 ですからこの場合は、|x| ≦ |x| が真か偽か確かめることです。(|x|はxの長さ) >>このような答えでいってるのですが推移律対称律がわからないのです。 推移率や反対称率、(ここでは扱っていないが、対称率)は、「ある前提条件を満たした場合、あとに示される条件を見たさなければならない」という論理構造をもっています。 例えば、推移率 a ≦ b かつ b ≦ c ⇒ a ≦ c については、「a ≦ b かつ c ≦ d」を満たさないa,b,cに対しては、a ≦ c かどうかを検証しなくてもよいのです。
関連するQ&A
- 数学の同値関係の問題です
集合Zでm~nとは、m-nは3で割り切れるとするとき、~が同値関係であることを示せ、という問題に困っています……。 反射律まではわかるのですが、対象律、推移律の証明の仕方がわかりません。どなたか教えていただけないでしょうか。最近集合を勉強し始めたのですが、ネットの情報などを見てもどうしてもわからないので質問しました。どうぞよろしくお願いいたします……
- 締切済み
- 数学・算数
- 同値関係の問題です。
「反射律、対称律を満たすが、推移律は満たさない関係の例をあげよ」 という問題です。 同値関係については少しは理解しているのですがまだ勉強を始めたばかりでこういう問題はちょっと苦手です。 ヒントだけでも頂けないでしょうか?
- ベストアンサー
- 数学・算数
- 同値関係の問題です。
同値関係の問題です。 1)群Gと部分群Hで{(x,y)|xy∈H}がG上の同値関係でないものを与えよ。 2)群Gと部分群Hで{(x,y)|xyx^(-1)y^(-1)∈H}がG上の同値関係でないものを与えよ。 3)RをXの同値関係とする。与えられたx∈Xに対して、y∈Xを(x,y)∈Rとなるように選ぶ。対称律より(y,x)∈Rとなり、次に推移律より(x,x)∈Rが示される。それゆえ、同値関係の反射律は余計なように思える。この議論の何が問題なのだろうか? 1問でもいいので分かる方おねがいします。
- 締切済み
- 数学・算数
- 集合論の同値関係の基本的な問題
自然数の集合 N から N への写像全体の集合 F における二項関係 R を f R g ⇔ {n∈N: f(n)≠g(n)} は有限集合 によって定める.このとき,R は同値関係であることを示せ. という問題について. 反射律と対称律は自明ですが,推移律が自分にとって自明でありません. fRg ∧ gRh ⇒ fRh {n∈N: f(n)≠g(n)} は有限集合 かつ {n∈N: g(n)≠h(n)} は有限集合 ⇒ {n∈N: f(n)≠h(n)} は有限集合 なにかうまく理解できる方法などがありましたら教えてください.
- ベストアンサー
- 数学・算数
- 同値関係
R(x,y)はx=yを意味し、 1.∀xR(x,x)(反射律) 2.∀x∀y[R(x,y)→R(y,x)](対称律) 3.∀x∀y∀z[R(x,y)∧R(y,z)→R(x,z)](推移律) の三つがあります。 この三つを満たしたとき同値関係となることがわかりますが、 1.が成り立って2.3.が成り立たないとき 2.が成り立って1.3.が成り立たないとき 3.が成り立って1.2.が成り立たないとき 1.2.が成り立って3.が成り立たないとき 1.3.が成り立って2.が成り立たないとき 2.3.が成り立って1.が成り立たないとき の6つのパターン例を示すことはできるのでしょうか? 日常の例でかまいません><
- ベストアンサー
- 数学・算数