- ベストアンサー
離散数学(関係の問題)
関係の問題で困っているので教えてください。 答えがないので全く分からなくなってます。 Aを空でない有限集合としてa=|A|とする。以下をaを使って表せ。 1,|A*A| 2,|{R|RはA上の関係}| 3,|{R|RはA上の反射的な関係}| 4,|{R|RはA上の対称的な関係}| 5,|{R|RはA上の反射的かつ対称的な関係}| 以上です。 自分で考えた結果 1についてはAの基数がaであることからa*a 2については1のべき集合なので2^(a*a)でたぶん合っていると思います。 しかし3以降が全く分からず、困っています。 3についてはa={a1,a2,a3,a4,…}とした時にRに(a1,a1)(a2,a2)(a3,a3)…が含まれればOKだと思うのですがどうやって表せばよいか見当がつきません。 よろしくお願いします。
- みんなの回答 （2）
- 専門家の回答
関連するQ&A
- 離散数学 2項関係についての問題
某国立大の情報系の学科に通っているものです。情報系では離散数学を習うのですが、あまり理解が進まず困っています。 今回は下記の問題に関して質問があります。 Ｓ＝｛１，２，３，４，５，６，７，８，９，１０｝とする （１）Ｓ上の2項関係で対照的なものはいくつあるか （２） 〃 反射的なものはいくつあるか （３） 〃 反射的かつ対照的なものはいくつあるか という問題です。 Ｓ上の2項関係の総数は ２の１００乗 個あるというところまでは分かります。 Ｓ上の二項関係をＲとして 反射的・・・すべてのＳの要素Ｘに対して（Ｘ，Ｘ）∈Ｒ 対象的・・・（Ｘ，Ｙ）∈Ｒ ならば （Ｙ，Ｘ）∈Ｒ こんな感じだとは思うのですが、ここからどう回答していけばよいのか見当がつきません。 もし、解法をご存知の方がいましたらご助力願います。
- ベストアンサー
- その他([技術者向] コンピューター)
- 集合の基数について
集合について勉強しています。以下質問です。 1． 「集合の基数」というのは「集合の要素の個数」という意味でよろしいのでしょうか？ 2． 問題を解いていてわからなかったことです。問題の解答によると (a){φ}の基数は1であり、 (b)べき集合P({{φ,{φ}},φ})の基数は4であり、 (c){{2},4,6,{6,8},9,12}∩{1,3,{6,8},{9},12}の基数は2である ということです。 (a)について、空集合が要素であるから1なのだろうなと思うのですが、 (b)について、どうして4になるかわかりません。空集合はすでに要素として書いてあるから(b)のべき集合は {{φ,{φ}},φ,{{φ,{φ}},φ}}となって答えは3になるのではないのでしょうか？ (c)について、{{6,8},12}の2つが要素となるので2という答えなのでしょうが、 どうしてこのときは空集合を要素としてカウントして答えが3にならないのでしょうか？ 集合、要素、空集合についての理解が頭の中で整理できません。 どなたかわかりやすく説明してください。よろしくお願いします。
- ベストアンサー
- 数学・算数
- 離散数学
大至急です．大学の学部の離散数学の授業で、 (1)RとSが集合X上の順序のときR∘SはX上の順序になるか？理由とともに結論を述べよ．という問題で， 反対称的のとき (x,y)∈R∘S ∩ (y,x)∈R∘S ⇒∃a,b∈X, {((x,a)∈R かつ (a,y)∈S) ∩ ((y,b)∈R かつ (b,x)∈S)} ⇒ここからどういうふうにすればわかりません． 推移的のとき <x,y>∈R∘S ∩ <y,z>∈R∘S ⇒∃a,b∈X, {((x,a)∈R かつ (a,y)∈S) ∩ ((y, b)∈R かつ(b, z)∈S)} ⇒ ここからどういうふうにすればわかりません． (2)<A,≦_A>と<B,≦_B>が整礎な順序集合ならば，A×B上の辞書式順序≦_lは整礎な順序であることを示せ． A×Bの空でない任意の部分集合Sが辞書式順序≦_lに関する極小元を持つことを示せばいいんですが，どうやって示せばいいかわかりません 分かる方，教えてください。.お願いします。
- 締切済み
- 数学・算数
- 離散数学課題
学校の離散数学の時間に課題が出ました。しかし全然分かりません。教えてください。 1≦nなる自然数nに対し、1からnまでの自然数の集合をS={1,2,...,n}で表す。以 下の問いに答えよ。 (1)SからSのべき集合2のs乗への全域関数は全部で何個存在するか。理由ととも に述べよ。 (2)Sのべき集合2のs乗から集合{0,1}への部分関数は全部で何個存在するか。理 由とともに述べよ。 (3)S上の2項関係で反対称的なものは全部で何個存在するか。理由とともに述べ よ。 (4)S上の2項関係で反射的かつ反対称なものは全部で何個存在するか。理由とと もに述べよ。 よろしくお願いします。
- 締切済み
- 数学・算数
- 集合論の同値関係の基本的な問題
自然数の集合 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)} は有限集合 なにかうまく理解できる方法などがありましたら教えてください．
- ベストアンサー
- 数学・算数
- 要素数nの集合Aにおける反射律・対称律
要素数ｎの集合Aにおいて (1)A上の関係で反射的なものはいくつあるか？ これは空集合以外の(n-1)個でしょうか？ (2)A上の関係で反射的かつ対称的なものはいくつあるか？ これは{a}や{a,b,c}などは反射・対称を満たしているのでしょうか？ 離散数学の問題の考え方が分からずに困ってます。説明よろしくお願いします。
- 締切済み
- 数学・算数
- 関係の問題
関係Rを次のように定義する。 (a, b) ∈ R ←→ 1<=|a|+|b|<=2. （※←→はbioconditional/if and only if） （※Rは実数） 解いてみたのですが、正しいかどうかわかりません。 おかしなところがあれば指摘して欲しいです。 1. 関係Rが反射律でも推移律でもないことを示せ。 関係Rを座標に書くとすると、a,b = (2,0), (0,-2), (-2,0), (0.2)の4点を隅にした正方形からa,b = (1,0), (0,-1), (-1,0), (0,1)を隅にした正方形を引いたような図になると（恐らく）思われます。 この場合、例えばa,b=(2,0)は成り立つがa,aの(2,2)は成り立たないので反射律は成り立たない。推移律に関しては、a,b=(2,0), b,c=(0,2)のとき、a,c=(2,2)は範囲外となってしまうので成り立たない。 2. 関係Rは対称律か？反対称律か？ この範囲内の点であれば、aとbを取り替えても(0,0)を軸にして１８０度回転させるのと同じことで、まだ範囲内にあることになるので対称律は成り立つ。反対称律については、a,b=(2,0)かつb,c=(0,-2)の場合にa≠cの為成り立たない。
- ベストアンサー
- 数学・算数
- 離散数学の問題が解けずに困っています。
離散数学の問題が解けずに困っています。 どなたか教えていただけないでしょうか？ 【問題文】 A=B=C={r,y,g}とする。 ここで、 A,B,Cはそれぞれが信号機SA,SB,SCが表示できる色の集合、 r,y,gはそれぞれが赤、黄、青に対応する元を表す。 RABがAからBへの二項関係、RACがAからCへの二項関係であるとき、次式が成り立つ。 ・ RAB(r)={r,y,g}、 RAB(y)={r}、 RAB(g)={r} ・ RAC(r)={r}、 RAC(y)={y}、 RAC(g)={g} ここで、a∈A、b∈B、c∈Cのとき、RAB(a)={b|aRABb}、RAC(a)={c|aRACc}である。 このとき、以下の問いに答えよ。 (1)、RABとRACの元をそれぞれ示せ。 (2)、RABの逆関数RAB^-1を示せ。 (3)、BからCへの二項関係RBCをRAB^-1を用いて表し、RBCの元を示せ。
- ベストアンサー
- 数学・算数
お礼
考えてみました。 3,Rの要素は｛(1,1)(2,2)(3,3)(4,4)とα｝になるのでαだけ別に考える。 今の場合α＝(1,2)(1,3)(1,4)、(2,1)(2,3)…となるので|α|＝2^(3*4) なので、RをR1＝｛(1,1)(2,2)(3,3)(4,4)｝とR2＝｛α｝で分割して考えて後から組み合わせるとすると、|R|＝|R2|＝2^(3*4)という考え方になったのですがどうでしょうか？ そうすると、一般的には|R|＝2^{a*(a-1)}で良いのでしょうか？