Are == and != mutually dependent?

You would not want the language to automatically rewrite a != b as !(a == b) when a == b returns something other than a bool. And there are a few reasons why you might make it do that.

You may have expression builder objects, where a == b doesn't and isn't intended to perform any comparison, but simply builds some expression node representing a == b.

You may have lazy evaluation, where a == b doesn't and isn't intended to perform any comparison directly, but instead returns some kind of lazy<bool> that can be converted to bool implicitly or explicitly at some later time to actually perform the comparison. Possibly combined with the expression builder objects to allow complete expression optimisation before evaluation.

You may have some custom optional<T> template class, where given optional variables t and u, you want to allow t == u, but make it return optional<bool>.

There's probably more that I didn't think of. And even though in these examples the operation a == b and a != b do both make sense, still a != b isn't the same thing as !(a == b), so separate definitions are needed.

If there is no such possibility, then why on Earth does C++ have these two operators being defined as two distinct functions?

Because you can overload them, and by overloading them you can give them a totally different meaning from their original one.

Take, for example, operator <<, originally the bitwise left shift operator, now commonly overloaded as an insertion operator, like in std::cout << something; totally different meaning from the original one.

So, if you accept that the meaning of an operator changes when you overload it, then there is no reason to prevent user from giving a meaning to operator == that is not exactly the negation of operator !=, though this might be confusing.

My concern is, though, why are there two separate definitions needed?

You don't have to define both.
If they are mutually exclusive, you can still be concise by only defining == and < alongside std::rel_ops

Fom cppreference:

#include <iostream>
#include <utility>

struct Foo {
    int n;
};

bool operator==(const Foo& lhs, const Foo& rhs)
{
    return lhs.n == rhs.n;
}

bool operator<(const Foo& lhs, const Foo& rhs)
{
    return lhs.n < rhs.n;
}

int main()
{
    Foo f1 = {1};
    Foo f2 = {2};
    using namespace std::rel_ops;

    //all work as you would expect
    std::cout << "not equal:     : " << (f1 != f2) << '\n';
    std::cout << "greater:       : " << (f1 > f2) << '\n';
    std::cout << "less equal:    : " << (f1 <= f2) << '\n';
    std::cout << "greater equal: : " << (f1 >= f2) << '\n';
}

Is there any situation possible in which asking questions about two objects being equal does make sense, but asking about them not being equal doesn't make sense?

We often associate these operators to equality. Although that is how they behave on fundamental types, there is no obligation that this be their behaviour on custom data types. You don't even have to return a bool if you don't want to.

I've seen people overload operators in bizarre ways, only to find that it makes sense for their domain specific application. Even if the interface appears to show that they are mutually exclusive, the author may want to add specific internal logic.

(either from the user's perspective, or the implementer's perspective)

I know you want a specific example,
so here is one from the Catch testing framework that I thought was practical:

template<typename RhsT>
ResultBuilder& operator == ( RhsT const& rhs ) {
    return captureExpression<Internal::IsEqualTo>( rhs );
}

template<typename RhsT>
ResultBuilder& operator != ( RhsT const& rhs ) {
    return captureExpression<Internal::IsNotEqualTo>( rhs );
}

These operators are doing different things, and it would not make sense to define one method as a !(not) of the other. The reason this is done, is so that the framework can print out the comparison made. In order to do that, it needs to capture the context of what overloaded operator was used.

There are some very well-established conventions in which (a == b) and (a != b) are both false not necessarily opposites. In particular, in SQL, any comparison to NULL yields NULL, not true or false.

It's probably not a good idea to create new examples of this if at all possible, because it's so unintuitive, but if you're trying to model an existing convention, it's nice to have the option to make your operators behave "correctly" for that context.

I will only answer the second part of your question, namely:

If there is no such possibility, then why on Earth does C++ have these two operators being defined as two distinct functions?

One reason why it makes sense to allow the developer to overload both is performance. You might allow optimizations by implementing both == and !=. Then x != y might be cheaper than !(x == y) is. Some compilers may be able to optimize it for you, but perhaps not, especially if you have complex objects with a lot of branching involved.

Even in Haskell, where developers take laws and mathematical concepts very seriously, one is still allowed to overload both == and /=, as you can see here (http://hackage.haskell.org/package/base-4.9.0.0/docs/Prelude.html#v:-61--61-):

$ ghci
GHCi, version 7.10.2: http://www.haskell.org/ghc/  :? for help
λ> :i Eq
class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool
        -- Defined in `GHC.Classes'

This would probably be considered micro-optimization, but it might be warranted for some cases.

Is there any situation possible in which asking questions about two objects being equal does make sense, but asking about them not being equal doesn't make sense? (either from the user's perspective, or the implementer's perspective)

That's an opinion. Maybe it doesn't. But the language designers, not being omniscient, decided not to restrict people who might come up with situations in which it might make sense (at least to them).

In response to the edit;

That is, if it is possible for some type to have the operator == but not the !=, or vice versa, and when does it make sense to do so.

In general, no, it doesn't make sense. Equality and relational operators generally come in sets. If there is the equality, then the inequality as well; less than, then greater than and so on with the <= etc. A similar approach is applied to the arithmetic operators as well, they also generally come in natural logical sets.

This is evidenced in the std::rel_ops namespace. If you implement the equality and less than operators, using that namespace gives you the others, implemented in terms of your original implemented operators.

That all said, are there conditions or situations where the one would not immediately mean the other, or could not be implemented in terms of the others? Yes there are, arguably few, but they are there; again, as evidenced in the rel_ops being a namespace of its own. For that reason, allowing them to be implemented independently allows you to leverage the language to get the semantics you require or need in a way that is still natural and intuitive for the user or client of the code.

The lazy evaluation already mentioned is an excellent example of this. Another good example is giving them semantics that don't mean equality or in-equality at all. A similar example to this is the bit shift operators << and >> being used for stream insertion and extraction. Although it may be frowned upon in general circles, in some domain specific areas it may make sense.

If the == and != operators don't actually imply equality, in the same way that the << and >> stream operators don't imply bit-shifting. If you treat the symbols as if they mean some other concept, they don't have to be mutually exclusive.

In terms of equality, it could make sense if your use-case warrants treating objects as non-comparable, so that every comparison should return false (or a non-comparable result type, if your operators return non-bool). I can't think of a specific situation where this would be warranted, but I could see it being reasonable enough.

With great power comes great responsibly, or at least really good style guides.

== and != can be overloaded to do whatever the heck you want. It's both a blessing and a curse. There's no guarantee that != means !(a==b).

enum BoolPlus {
    kFalse = 0,
    kTrue = 1,
    kFileNotFound = -1
}

BoolPlus operator==(File& other);
BoolPlus operator!=(File& other);

I can't justify this operator overloading, but in the example above it is impossible to define operator!= as the "opposite" of operator==.

In the end, what you are checking with those operators is that the expression a == b or a != b is returning a Boolean value (true or false). These expression returns a Boolean value after comparison rather than being mutually exclusive.

[..] why are there two separate definitions needed?

One thing to consider is that there might be the possibility of implementing one of these operators more efficiently than just using the negation of the other.

(My example here was rubbish, but the point still stands, think of bloom filters, for example: They allow fast testing if something is not in a set, but testing if it's in may take a lot more time.)

[..] by definition, a != b is !(a == b).

And it's your responsibility as programmer to make that hold. Probably a good thing to write a test for.

By customizing the behavior of the operators, you can make them do what you want.

You may wish to customize things. For instance, you may wish to customize a class. Objects of this class can be compared just by checking a specific property. Knowing that this is the case, you can write some specific code that only checks the minimum things, instead of checking every single bit of every single property in the whole object.

Imagine a case where you can figure out that something is different just as fast, if not faster, than you can find out something is the same. Granted, once you figure out whether something is the same or different, then you can know the opposite simply by flipping a bit. However, flipping that bit is an extra operation. In some cases, when code gets re-executed a lot, saving one operation (multiplied by many times) can have an overall speed increase. (For instance, if you save one operation per pixel of a megapixel screen, then you've just saved a million operations. Multiplied by 60 screens per second, and you save even more operations.)

hvd's answer provides some additional examples.

Yes, because one means "equivalent" and another means "non-equivalent" and this terms are mutually exclusive. Any other meaning for this operators is confusing and should be avoided by all means.

Maybe an uncomparable rule, where a != b was false and a == b was false like a stateless bit.

if( !(a == b || a != b) ){
    // Stateless
}