- 締切済み
離散数学課題
学校の離散数学の時間に課題が出ました。しかし全然分かりません。教えてください。 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項関係で反射的かつ反対称なものは全部で何個存在するか。理由とと もに述べよ。 よろしくお願いします。
- nanacollet
- お礼率0% (0/2)
- 数学・算数
- 回答数2
- ありがとう数1
- みんなの回答 （2）
- 専門家の回答
みんなの回答
- ran-neko
- ベストアンサー率56% (13/23)
A,Bを有限集合としA,Bの要素の数をそれぞれa,bとする。 ｆ：A→B を全域関数とするとき ｆは全部でb^a個存在する。 （定義域のAの要素それぞれについてｂ個の異なるｆを作れる） （１） 上より明らか （２） 値域に対応する要素がない事をしめす集合を一つ付け加えて考えれば全域関数の場合に帰着できる。 （３） AがS上の二項関係であるとはA⊂S^2 であった。 ここでAの条件は（a,b）∈S^2 ⇒ b = a ∨ ￢(b,a) ∈ S^2 である。 つまりS^2の上三角形については自由に値をとることが出来るので、そのようなとり方が何通りあるか数えればよい。 （４） 上と同様にして条件を満たす点の取り方について考えればよい。
(1)sって何ですか？また、「全域関数」の定義は何ですか？ (2)「部分関数」の定義は何ですか？ (3)「2項関係」、「反対称的」の定義は何ですか？ (4)「反射的」、「反対称」の定義は何ですか？
関連するQ&A
- ２項関係に対する問題
以下の問題の解答がわかりません。解答とできれば考え方を教えてください。 S={1,2,...,n}において、S上の２項関係で反射的かつ対称的なものは全部で何個存在するか。
- 締切済み
- 数学・算数
- 離散数学 2項関係についての問題
某国立大の情報系の学科に通っているものです。情報系では離散数学を習うのですが、あまり理解が進まず困っています。 今回は下記の問題に関して質問があります。 Ｓ＝｛１，２，３，４，５，６，７，８，９，１０｝とする （１）Ｓ上の2項関係で対照的なものはいくつあるか （２） 〃 反射的なものはいくつあるか （３） 〃 反射的かつ対照的なものはいくつあるか という問題です。 Ｓ上の2項関係の総数は ２の１００乗 個あるというところまでは分かります。 Ｓ上の二項関係をＲとして 反射的・・・すべてのＳの要素Ｘに対して（Ｘ，Ｘ）∈Ｒ 対象的・・・（Ｘ，Ｙ）∈Ｒ ならば （Ｙ，Ｘ）∈Ｒ こんな感じだとは思うのですが、ここからどう回答していけばよいのか見当がつきません。 もし、解法をご存知の方がいましたらご助力願います。
- ベストアンサー
- その他([技術者向] コンピューター)
- 要素数nの集合Aにおける反射律・対称律
要素数ｎの集合Aにおいて (1)A上の関係で反射的なものはいくつあるか？ これは空集合以外の(n-1)個でしょうか？ (2)A上の関係で反射的かつ対称的なものはいくつあるか？ これは{a}や{a,b,c}などは反射・対称を満たしているのでしょうか？ 離散数学の問題の考え方が分からずに困ってます。説明よろしくお願いします。
- 締切済み
- 数学・算数
- 離散数学の２項関係について
「Ｓ＝｛1,2,3,…,n｝とする。 Ｓ上の２項関係は全部で何個？」 という問題なのですが、答えが良く分かりません。 自分で考えたのは (1,1),(1,2),…,(1,n) (2,1),(2,2),…,(2,n) ： (n,1),(n,2),…,(n,n) で、答えは n * n = 「n~2」 だと思うのですが、実際は「2~n~2」個らしいです。 ２項関係自体の理解も曖昧なのですが、よろしければ説明をお願いします。
- ベストアンサー
- 数学・算数
- 離散数学
大至急です．大学の学部の離散数学の授業で、 (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に関する極小元を持つことを示せばいいんですが，どうやって示せばいいかわかりません 分かる方，教えてください。.お願いします。
- 締切済み
- 数学・算数
- 離散数学(関係の問題)
関係の問題で困っているので教えてください。 答えがないので全く分からなくなってます。 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だと思うのですがどうやって表せばよいか見当がつきません。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 離散数学の問題が解けずに困っています。
離散数学の問題が解けずに困っています。 どなたか教えていただけないでしょうか？ 【問題文】 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の元を示せ。
- ベストアンサー
- 数学・算数
- ２項関係についてです
次のように定義される自然数Ｎ（０含）上の２項関係Ｒは、反射的か、対称的か、 反対称的か、推移的か、それぞれ決定し、各性質が成り立たない場合には、その反例を 挙げよという問題があって、 ・xRy⇔x-y<3 ・xRy⇔∃n∈Ｎ s.t.xy=n^2 ・xRy⇔∃n∈Ｎ s.t.xy=2n ・xRy⇔∃n∈Ｎ s.t.y=x+2n この４つの２項関係Ｒそれぞれについて反射的であるか、また対称的であるか 反対称的であるか、また推移的であるかをそれぞれ考えなければいけません。さらに性質に当てはまらない場合の反例というのは、例えば、 反対称的に対する反例の場合は、『1R2かつ2R1であるが、1≠2』というような感じです。 厚かましいですが、解説してくださると助かりますm(_ _;)m
- 締切済み
- 数学・算数
