プロが教えるわが家の防犯対策術!

 要素数nの集合Aにおいて

(1)A上の関係で反射的なものはいくつあるか?
これは空集合以外の(n-1)個でしょうか?

(2)A上の関係で反射的かつ対称的なものはいくつあるか?
これは{a}や{a,b,c}などは反射・対称を満たしているのでしょうか?

離散数学の問題の考え方が分からずに困ってます。説明よろしくお願いします。

A 回答 (2件)

>補足


R={(a,a)(a,b)(b,a)(b,b)} なら、反射律を満たしますね。
これ以外にも、
R={(a,a)(b,b)}
R={(a,a)(a,b)(b,b)}
R={(a,a)(b,a)(b,b)}
なら、反射律を満たしているわけです。
    • good
    • 0
この回答へのお礼

 そうなるとn=3のときは64個ありますから、
1,4,64,・・・から 2^(n^2 -n)個 となるんですね。
ありがとうございます。

お礼日時:2009/05/11 22:45

(1) だけ。


>これは空集合以外の(n-1)個でしょうか?
まず、「関係」というのを何だか理解していますか?
http://ja.wikipedia.org/wiki/%E4%BA%8C%E9%A0%85% …
ここにwikipediaでの定義が書いてありますが、授業では「関係」をどう定義してましたか?

とりあえず、wikipediaの定義だと思えば、
集合Aと集合Aの直積A×Aは、n^2個の要素を持っていますが、この直積集合の部分集合Rのことを「A上の関係」と言います。
で、反射律を満たすってことですから、
任意のα∈Aについて、{α,α}∈R …☆
は満たしてないといけないので、これを満たすような、A×Aの部分集合Rの取り方を数えればいいです。
ここからは、まあ、高校の場合の数の問題なわけですが、つまり、A×Aは全部でn^2個要素がある集合で、そのうち、☆から、n個は常にRに入っていないといけませんから、残りの n^2-n 個の要素をRに入れるか入れないかを考えれば、題意を満たす関係は、全部で
2^(n^2-n)
個あることがわかります。

この回答への補足

 Rの取り方についてですが、要素数2のA={a,b}とします。
R={(a,a)(a,b)(b,a)(b,b)}ですね。このとき、(a,b)に関して a∊A b∊A なので (a,a)(b,b)∊R なので反射律が成り立つといえるのでしょうか?

補足日時:2009/05/10 21:16
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!