In physics, the word entropy has important physical implications as the amount of "disorder" of a system. In mathematics, a more abstract definition is used. The (Shannon) entropy of a variable $X$ is defined as
$$H(X)=-\Sigma_x P(x)log_2 [P(x)]$$
bits, where $P(x)$ is the probability that $X$ is in the state $x$ , and is defined as $0$ if $P=0$.
Question: Can anyone explain to me why "disorderness" of a system defined as this? especially, where has "$log_2$" come from in this formula?
Firstly, the logarithm needn't necessarily be to base 2. Changing the base just introduces a (scale) factor, so log10, log2 and ln are all equally useful. Log2 is convenient for people working with binary systems.
Let's deconstruct the formula. I will define entropy to be $H = E[-\log(p)]$. You can see that this will reduce to a weighted average which precisely reproduces your formula.
Now for the crucial question of why $-\log(p)$ is the amount of information encoded by an event whose probability of occurrence is $p$. Consider any notation/language system with strings -- these could be bit-strings, or decimal, or even the English alphabet with 26 letters (in general, say $k$ symbols). If you consider strings of length $n$, you can cover $k^n$ possible "words". If the information in your event was coded into one of these words, then you would need $k$ alphabets to convey the information i.e. for an event whose probability is $\frac{1}{k^n}$, you need words of length $n$ if you consider a language with $k$ alphabets. This explains why the amount of information encoded in an event is propotional to the logarithm of it's probability.
So, given a random variable, the average/expected amount of information present in realizations of that variable will be $E[-\log(p)]$ where $p$ gives the probability distribution of your random variable.
If you had a (discrete) uniformly distributed random variable (say N possibilities, each with equal probability), then you can compute the Shannon entropy to be $\log(N)$ which is precisely the Boltzmann formula of entropy in the microcanonical ensemble. The Shannon entropy quantifies the disorder in a similar sense. It quantifies a weighted average of the number of possible realizations, in some sense. The more these are, the more disordered the random variable is. An important underlying concept is that information is complementary/dual to entropy/disorder.
Because of the following. Disorder is usually equated with one's ignorance of the system - the less you know about the outcome of the random variable the more disordered it is. If the system turns out to be in a very unlikely state with low $p(x)$ you will naturally consider yourself to have been more ignorant than when it is in a state you consider very likely. So if suppose there is some function $f(p(x))$ that measures this ignorance and is a decreasing function of $p(x)$. So average ignorance is $$ S(X) = \sum_x p(x) f(p(x)).$$
Now suppose you have two random variables $X$, $Y$, one with distribution $p(x)$ and another with $q(y)$. Then your total ignorance for a state $x,y$ is $f(p(x) q(y))$. Now the crucial assumption is that ignorance is additive, ie. $f(p(x) q(y)) = f(p(x)) + f(q(y))$. It turns out that logarithm is the unique differentiable function that satisfies this relationship (this is fairly simple to show by differentiating above equation with respect to $p$ or $q$ and solving the differential equation that comes out). There is no other choice.
So we have $S(X) = - \alpha \sum_x p(x) \log(x)$, where $\alpha > 0$. Minus comes from assuming that $f$ is decreasing. Now $\alpha$ can take any value and taking $\alpha = 1/\log(2)$ is simply a matter of convention, which is mainly used because two state systems are so ubiquitous and it means that the maximum disorder (entropy) of a two state system is 1. This kind of provides a normalization for it. No other deep reason behind it.
Anyway, consider the following two examples.
(1) A random variable always has a single, definite value, i.e., it isn't really random. Then the Shannon entropy is zero. This means that you don't gain any information by being told that my puppy is cute -- puppies are always cute, with probability 1.
(2) Suppose a variable is equally likely to take on $n$ different values. Then the Shannon entropy comes out to be $\log_2 n$. This is the number of bits of information needed to express the value of the variable in binary.
I'll first (1) describe an intuitive meaning of Shannon entropy, then (2) describe how it is given concrete meaning through the noiseless coding theorem and then (3) lastly show how its related to thermodynamics of very simple systems.
(1) Read through SMeznaric's answer above: the logarithm comes in because intuitively one thinks that the information gotten from two independent random variables is simply the sum of their informations. (BTW: the logarithm is the only $continuous$ solution to the functional equation $f(u\, v) = f(u)+f(v)$: there are also weird and wonderful everywhere-discontinuous ones; see the wikipedia entry on the Cauchy functional equation and then exponentiate).
(2) The rigourous, working meaning of Shannon's entropy is seen through Shannon's noiseless coding theorem: http://en.wikipedia.org/wiki/Shannon%27s_source_coding_theorem. If you try to code a message comprising a string of statistically independent symbols using $H - \epsilon$ bits per symbol (where $H$ is the Shannon entropy of the symbol probability distribution) for any $\epsilon > 0$ the matter how small, then the probability of "failure" ($i.e.$ the probability that you will "garble" the message rises to unity as the message length $\rightarrow \infty$). Contrapositively, if you choose to use $H + \epsilon$ bits per symbol, then it can be proven that there exists a coding scheme such that the probability of failure shrinks to nought as the message length rises without bound. Here as in other answers, one can use bases other than 2 for the logarithm. The Shannon entropy expression above also equals the Kolmogorov complexity (to within a constant) for independent symbols: more generally the Shannon entropy and Kolmogorov complexity are within an additive constant of one another. See http://en.wikipedia.org/wiki/Kolmogorov_complexity. More complicated formulas for the Shannon entropy than those given here hold when there is correlation between symbols. The Shannon entropy really is the true transmission capacity you would have to provision for if you were designing a communication channel to transmit such a string.
(3) Now, assuming the states of molecules are statistically independent, you can think of the states of each one to be analogous to one letter in the random string in (2) above. So the number of bits you would need to encode the state of every molecule in a gas is $\sum p_j \log_2 p_j$. So strip the Boltzmann constant off the Boltzman entropy and change its sign, and you've got the Shannon entropy. Indeed, you prove the noiseless coding theorem by using Stirling's formula on the expression for the number of micro-states that there are with mean number of particles in each state implied by the probabilities and then assuming you encode each microstate is unique number between one and $2^{N\,H} + m$, where $N$ is the number of particles and $m$ is a margin to allow for fluctuations. Then you work out the probability that, through fluctuation from these mean numbers, your margin $m$ will not not be big enough. This is almost exactly the same as the approach in many thermodynamics texts.
