Contextuality and nonlocality are non-classical properties exhibited by quantum statistics whose implications profoundly impact both foundations and applications of quantum theory. In this paper we provide some insights into logical contextuality and inequality-free proofs. The former can be understood as the possibility version of contextuality, while the latter refers to proofs of quantum contextuality/nonlocality that are not based on violations of some noncontextuality (or Bell) inequality. The present work aims to build a bridge between these two concepts from what we call possibilistic paradoxes, which are sets of possibilistic conditions whose occurrence implies contextuality/nonlocality. As main result, we demonstrate the existence of possibilistic paradoxes whose occurrence is a necessary and sufficient condition for logical contextuality in a very important class of scenarios. Finally, we discuss some interesting consequences arising from the completeness of these possibilistic paradoxes.

To appear in Phys. Rev. A. Comments still welcome!