Multilabel image classification: is it necessary to have traning data for each combination of labels?
Both cases will work. The point that you have to consider is that you shouldn't use Softmax activation in the last layer because your classes have intersection and they are not mutually exclusive. You should employ Sigmoid activation function and there should be two of them which each of them can be one or zero as the output vector. Consider that in this case you should not compare each activation to the other. Each one shows the probability of existence of the corresponding object, cat or dog.

For your case I suggest you to provide images which don't have either and in some cases have both. The former is more important. Because if you don't provide negative labels, not existing, the net always try to make something out of nothing. Means the net always try to flag similar patters as cats or dogs.