How to prove completeness I am learning about completeness of the sentential logic natural deduction system. In the lecture notes, there are some examples:


*

*If the rule VI (Disjunction Introduction) is removed, is the system still complete? -> No

*If the rule &I (Conjunction Introduction) is removed, is the system still complete? -> No

*If the rule ~I (Negation Introduction) is removed, is the system still complete? -> Yes
I would like to know in general, what is the approach to proving a system is "complete"?
 A: In order to show that a system is complete, you need to show that it proves everything it needs to. If you've already got a system you know is complete, this isn't too bad: just show that your first system can do all the things your second system can. E.g. in your example, if you can show that your system without ~I can still introduce negations, then you've proved it is complete since you know the original system was complete.
What if you need to prove completeness from scratch? Well, this is harder. One way of attacking this looks hard: you would need to show how, given a collection of sentences $\Sigma$ which entail some sentence $\varphi$, we can prove $\varphi$ from $\Sigma$ in the system. 
Instead, we make the problem easier by taking the contrapositive. Supposing $\Sigma$ did not prove $\varphi$, we show that $\varphi$ is not entailed by $\Sigma$. And this we know how to do! In order to show that $\Sigma$ doesn't entail $\varphi$, you just have to build a truth assignment in which $\Sigma$ is true, but $\varphi$ is false. 
We can switch things up a bit to make it even easier: it's enough to show that if $\Gamma$ is consistent from the perspective of the system, then $\Gamma$ is satisfiable. Why? Well, just replace $\Gamma$ with $\Sigma\cup\{\neg\varphi\}$, and you've got the version in the previous paragraph! So to sum up:

To show that a system is complete, we just need to show that, given a set of sentences $\Gamma$, if our system doesn't prove a contradiction from $\Gamma$ then $\Gamma$ is satisfiable.

To do this, we construct a truth assignment $T_\Gamma$ associated to $\Gamma$, and show that if $\Gamma$ is consistent in the sense of our system then $T_\Gamma$ satisfies $\Gamma$. Actually this isn't quite right - we first expand $\Gamma$ to get a bigger $\Gamma'$ with some nicer properties - but this is the big picture idea.

What about the other side of things?
Perhaps surprisingly, the hard version is usually showing that a system is not complete. Here, you have to build a set of sentences $\Gamma$ which is not satisfiable, but such that your system doesn't prove a contradiction from $\Gamma$. Now, this last bit is important: even after coming up with a good choice of $\Gamma$, we have to prove that our system can't find a contradiction in $\Gamma$! And this involves proving something about all possible proofs in a given system. 
There isn't really a royal road to such arguments, but one good trick is to try to pin down some specific thing that your system can never do, and then verify that by induction (e.g. can your system easily interchange the order of two sentences in a conjunction? can you prove that it can't?). At the end of the day, though, this will almost always come down to a hard induction argument. (For this reason, sometimes proofs of incompleteness of systems are only sketched in introductory courses, since the basic limitation is often convincing and easy to see while verifying its insurmountability can be quite hard.)

It looks like you're specifically looking at propositional (or sentential) logic. It should be noted that what I've said above applies equally well to first-order (predicate) logic (and many other logics).
