Did Socrates believe that animals possessed souls? I come to a logical contradiction when I apply his teachings to the question.

I would be curious to hear what contradiction you arrive at. It's hard to guess from what you say just which aspects of his teaching imply that animals do have souls and which aspects imply that they don't. But I can summarize some of the things he says in Plato's dialogues and suggest one path to a contradiction. By the way, I say "in Plato's dialogues" by way of making clear that I will talk about the Socrates we encounter in those works, not about a version of Socrates we get from other authors and not about the hypothetical, hard to pin down, "Socrates who really existed." The Socrates in Plato's dialogues says a lot more of a philosophical nature about souls than any other Socrates, so we should begin with him. Although there are many dialogues in which Socrates does not discuss the soul, at some points Plato has him argue at length that it survives a person's death. Plato's PHAEDO is devoted to this question, but we also find arguments for immortality of the soul in MENO, PHAEDRUS, and REPUBLIC....