From our daily experience we know that most of the time cats and dogs are involved in fights rather than in expressions of affection. Is there an evolutionary basis(justification) for this?
Why would two species of animals fight each other (apparently for no reason) wasting their precious energy?
You Should not Expect a Just-So Story
To my eyes, the question reeks of adaptationism: the attempt to explain what we see (cats and dogs, or otherwise) exclusively in terms of evolutionary adaptation, as if all creatures were evolutionary "perfect."
Humoring that, an adaptationist response would read as follows: Domestic pet warfare was emphatically not the problem cat and dog brains evolved to solve. They evolved in the wild: all dogs used to be wolves, and cats had every reason to fear them, and no reason to evolve a method of distinguishing good and bad dogs.
But even that involves some speculation.
Darwin was the first to highlight the difficulty of understanding why a specific trait did or did not evolve (Origin, ch. VII):
Why, in other quarters of the world, various animals belonging to this same order have not acquired either an elongated neck or a proboscis, cannot be distinctly answered; but it is as unreasonable to expect a distinct answer to such a question, as why some event in the history of mankind did not occur in one country, whilst it did in another.
The over-eager application of adaptationism -- making up evolutionary "just so" stories -- has been out of favor among evolutionary biologists since Stephen J. Gould famously criticized it in "The Spandrels of San Marco and the Panglossian Paradigm: A Critique of the Adaptationist Programme", Proc. of the Royal Society of London, Series B, Biological Sciences, 205, 1979.
Evolutionary psychology (which the question involves) has a bad reputation among biologists for being (in many cases) too adaptationist in its assumptions.
Evolution is not guaranteed to produce optimal or general solutions to problems -- i.e. a cat that knows what it should and should not trust. It cobbles together half-assed solutions to very specific problems -- a heuristic like "be afraid of anything snake-like," perhaps -- and it can only use existing material.
As a result, organisms easily get stuck in myriad sub-optimal solutions along the way. What might appear to us as an obvious way around a problem ("Don't waste resources fighting friendly animals") may not at all be obvious to mutation and natural selection! Ergo the famous caricature of evolution as a limited "tinker" rather than a brilliant "engineer" by François Jacob (Cf. "Evolution and Tinkering," Science, vol. 196, 1977)
EDIT: I should not that how often local optimums inhibit ideal adaptation is a very controversial topic in biology. Adaptationism has a strong following today, due in part to the success of evolutionary game theory at using adaptationist assumptions to model animal behavior.
Stanley Coren (in How to Speak Dog) notes that the body language of cats and dogs often mean opposite things (for example, a dog on his back is being submissive (or friendly) while a cat on its back is in a fighting posture) and speculates that this may be part of the historic problem between dogs and cats (he explains it better in this google book snippit)
One interesting take on this is the following research article: "The Escape Drive in Domestic Cats and the Dog and Cat Relationship" (Source: Behaviour, Volume 5, Number 1, 1953 , pp. 81-84(4))
Abstract:
Domestic cats reared without access to the street develop a pathological timidity, attributable to the escape drive being released by stimuli which would otherwise be subliminal. I suggest that in European and American cities dogs and cats form a commensality in which the cats provide the stimuli releasing the chasing instinct of dogs, and dogs the stimuli releasing the flight instinct of cats, thus mutually satisfying otherwise starved drives.
