I believe "decidable" doesn't typically mean the algorithm assigns a *truth value* to every sentence - in fact, true/false don't even really apply when we're talking about sentences in a theory. Instead, the algorithm takes a sentence as input, and returns an output saying that either yes this sentence is a theorem, or no it is not. It is totally possible for both P and ~P to not be theorems.

For example, if you are working from the group axioms, neither "∀x,y: xy=yx" nor its negation "∃x,y: xy≠yx" is a theorem that can be proved from the axioms. If you know a little bit of group theory, it should be easy to see why!