URGENT! I need help with proof, can someone provide some explanations or guide on how to tackle the problem?

2016-09-02 11:10 pm
更新1:

Here's the prompt: For each of the following assertions, prove using the defintions of the notations or disprove by providing a specific counterexample.

回答 (1)

2016-09-02 11:26 pm
Since there's an intersection symbol, I guess these are each sets.

First of all, to prove set equality, you need to prove that each side is a subset of the other side.
Second, being in the intersection means that x is a member of both sets.

So the structure of your proof is this:
a. Let x be an element of theta(g(n)). Then x is an element of O(g(n)), and also x is an element of Omega(g(n)). (You have to argue that from whatever it means to be members of those sets). Therefore x is an element of the intersection.

This shows that Theta is a subset of O intersect Omega.

b. Let x be an element of O intersect Omega, so it has whatever properties make it a member of those sets. Show that it has the property that makes it an element of Theta.

This shows that O intersect Omega is a subset of Theta.

c. Both sides are subsets of each other. Therefore they are equal.


收錄日期: 2021-04-21 23:25:32
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20160902151046AAt8ijg

檢視 Wayback Machine 備份