In the context of formal logic, completeness has more than one meaning, and from your example I'm not sure which is closest to what you mean. These are the main ones:
Functional completeness. In the context of classical propositional logic, a set of connectives is said to be functionally complete, or expressively adequate, if all truth-functional connectives can be defined in terms of them. A logic that contains only disjunction and identity, like your example, would be incomplete by this definition, since it would not be able to express all the boolean functions. Emil Post proved which sets of connectives are functionally complete for propositional logic. The expressive power of more powerful logics is not so easily described and measured. First order logic seems to be adequate for expressing most theories in physics.
Semantic completeness and strong completeness. Semantic completeness is a relation between a deductive system and some semantics: usually a formal semantics such as model theory. Completeness in this sense is the converse of soundness. A deductive system is sound if every formula it proves is a validity of the semantic system. It is complete if every validity of the semantic system is provable. This is sometimes written as follows:
If ⊢ φ then ⊨ φ (Soundness)
If ⊨ φ then ⊢ φ (Completeness)
Where ⊢ indicates syntactic derivability, and ⊨ indicates semantic consequence. Strong soundness and completeness is an extension of these relations to derivations from a set of premises. Gödel proved that first order classical logic is sound and complete when he did his PhD thesis. The soundness part is easy to prove; the completeness part is hard.
Syntactic completeness or deductive completeness. This is a property of a theory T, such that the addition of any unprovable sentence to it makes it inconsistent. This is roughly equivalent to saying that for any sentence φ in the language of T, T ⊢ φ or T ⊢ ¬φ. Gödel's first incompleteness theorem shows that any system of arithmetic that is consistent, axiomatisable, and at least as strong as Robinson arithmetic, is incomplete in this sense. The proof is ingenious and not too difficult to understand. There is an account of it in a freely downloadable book by Peter Smith.