• ベストアンサー

離散数学　2項関係についての問題

某国立大の情報系の学科に通っているものです。情報系では離散数学を習うのですが、あまり理解が進まず困っています。 今回は下記の問題に関して質問があります。 Ｓ＝｛１，２，３，４，５，６，７，８，９，１０｝とする （１）Ｓ上の2項関係で対照的なものはいくつあるか （２）　　　〃　　　反射的なものはいくつあるか （３）　　　〃　　　反射的かつ対照的なものはいくつあるか という問題です。 Ｓ上の2項関係の総数は　２の１００乗　個あるというところまでは分かります。 Ｓ上の二項関係をＲとして 反射的・・・すべてのＳの要素Ｘに対して（Ｘ，Ｘ）∈Ｒ 対象的・・・（Ｘ，Ｙ）∈Ｒ　ならば　（Ｙ，Ｘ）∈Ｒ こんな感じだとは思うのですが、ここからどう回答していけばよいのか見当がつきません。 もし、解法をご存知の方がいましたらご助力願います。

質問者が選んだベストアンサー

  • ベストアンサー
  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.3

うん, S×S が 100個の要素からなっていて, R はその部分集合だから 2^100通り. ちょいと #1 へのコメントを見たんだけど, 「反射的」と「対称的」が逆だよ.... 反射的な関係であれば全ての x ∈ S に対して (x, x) ∈ R だから, 「R に入れるかどうか」の選択ができる組み合わせは x ≠ y であるような (x, y) に限定されます. これは何組ありますか? 対称的な関係も同様で, (x, y) ∈ R if and only if (y, x) ∈ R だということは, 「x > y であるような (x, y) については ((y, x) ∈ R かどうかを決めれば) 自動的に決まってしまうので考えなくてもよい」ということになります.

zinrong
質問者

お礼

ちょいと #1 へのコメントを見たんだけど, 「反射的」と「対称的」が逆だよ.... >>>逆に書いてしまいました；（１）と（２）の答えは逆です。 考え方はあんな感じで合っているのでしょうか？お手数かけます・・・

全文を見る
すると、全ての回答が全文表示されます。

その他の回答 (2)

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.2

S 上の 2項関係がなぜ 2^100個あるのかは理解できてますか?

zinrong
質問者

お礼

まず直積Ｓ×Ｓ＝１０×１０＝１００ 二項関係＝直積の部分集合なので、１００個の要素がある直積Ｓ×Ｓの部分集合の数を出せばよいので→２^１００個 自分ではこういう風に覚えているのですが・・・

全文を見る
すると、全ての回答が全文表示されます。
  • koko_u_
  • ベストアンサー率18% (459/2509)
回答No.1

まあ、S = {1, 2, 3} くらいでまずは考えるべ。

zinrong
質問者

お礼

S = {1, 2, 3}とすると・・・ Ｓ×Ｓ＝９より二項関係の総数は２^９個 （１）（１,１）（２,２）（３,３）の３つが必ず含まれる直積の部分集合の数を出せばよい（？ （１,１）（２,２）（３,３）の３つは必ず含まれるので、直積の総数から３を引いて９－３＝６ 直積の総数を6個と考えればよいので２^６個 （２）Ｘ、ＹをＳに含まれる数・Ｓ上の二項関係をＲとしてとして （Ｘ，Ｙ）∈Ｒ　ならば　（Ｙ，Ｘ）∈Ｒ　 （Ｘ,Ｙ）（Ｙ,Ｘ）のどちらかがＲに含まれるかどうか調べればよい（？ （１,１）（２,２）（３,３）の３つと それ以外の要素の半分６/３＝２を足して　５　したがって２^５個 （３）（１,１）（２,２）（３,３）の３つは必ず含まれるので ５－３＝２から　２^２個 一応やってみました。ぜんぜん自信ありませんけど・・・； （１,１）や（２,２）とかは対照的と見ていいんでしょうか・・・？

全文を見る
すると、全ての回答が全文表示されます。
  1. カテゴリ
  2. [技術者向] コンピューター
  3. その他([技術者向] コンピューター)

関連するQ&A

  • ２項関係についてです

    次のように定義される自然数Ｎ（０含）上の２項関係Ｒは、反射的か、対称的か、 反対称的か、推移的か、それぞれ決定し、各性質が成り立たない場合には、その反例を 挙げよという問題があって、 ・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

  • 離散数学の問題が解けずに困っています。

    離散数学の問題が解けずに困っています。 どなたか教えていただけないでしょうか？ 【問題文】 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の元を示せ。

  • 離散数学

    大至急です．大学の学部の離散数学の授業で、 (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に関する極小元を持つことを示せばいいんですが，どうやって示せばいいかわかりません 分かる方，教えてください。.お願いします。

  • 離散数学

    Z*を非負整数全体の集合とする。 Z*上の関係R={(x,y)|x+y=0}に対し、反射性、反反射性、対称性、反対称性、推移性のそれぞれが成り立つかどうか述べよ という問題で、 答えは「対称性、反対称性、推移性が成り立つ」なのですが、 理由がわかりません。 どなたか、どうか教えてくださいm(__)m

  • 【離散数理・2項関係】

    【2項関係】 次の問いの答えを教えてください。 次の2項関係は反射性、対称性、反対称性、推移性、半順序性、全順序性のどれを満たすか。 １）ｘとｙが英単語のとき、ｘRｙはｘはｙよりも辞書の配列順で前にある。 ２）有向グラフG＝（V,E）において点aから点bに有向路があるとき、aRbとする。 ３）無向グラフG＝（V,E）において点aから点bに路があるとき、aRbとする。 よろしくお願いします。

  • 離散数学の２項関係について

    「Ｓ＝｛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」個らしいです。 　２項関係自体の理解も曖昧なのですが、よろしければ説明をお願いします。

  • ２項関係に対する問題

    以下の問題の解答がわかりません。解答とできれば考え方を教えてください。 S={1,2,...,n}において、S上の２項関係で反射的かつ対称的なものは全部で何個存在するか。

  • 二項関係の問題で

    ブール代数の問題で 2つの異なる集合A={a,b} と B{1,2}を考える. ただし,aとbは実数であり,a≠bである。 このとき A とBの二項関係としてR={(x,y)|x >y}を考える. xRy={(a,1),(a ,2)}のとき,a とbが満たすべき条件 を 述べよ. 何か少しでも知っているものがあれば教えて頂きたく、よろしくお願いします。

  • 離散数学課題

    学校の離散数学の時間に課題が出ました。しかし全然分かりません。教えてください。 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項関係で反射的かつ反対称なものは全部で何個存在するか。理由とと もに述べよ。 よろしくお願いします。

  • 離散数学の問題

    離散数学の勉強を始めました。以下の問題を解きたいのですが、分かりません。お分かりの方、教えて頂けないでしょうか。quantifiersを使わずに、命題で表せという問題です。 Suppose we are considering the domain of just two numbers D = {0, 1}. Convert the following propositions containing quantifiers to propositions that do not use any quantifiers. For example, ∀x P(x) can be restated as P(0) ∧ P(1). １. ∀x ∃y P(x, y) ２. ∃x P(x) ∨ (∀y Q(x, y)) ３. ￢ (∀x ∃y [P(x) → Q(y)])

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する