Minimal true-implies-false and true-implies-true sets of propositions in noncontextual hidden-variable theories

An essential ingredient in many examples of the conflict between quantum theory and noncontextual hidden variables (e.g., the proof of the Kochen-Specker theorem and Hardy's proof of Bell's theorem) is a set of atomic propositions about the outcomes of ideal measurements such that, when outcome noncontextuality is assumed, if proposition A is true, then, due to exclusiveness and completeness, a nonexclusive proposition B (C) must be false (true). We call such a set a true-implies-false set (TIFS) [true-implies-true set (TITS)]. Here we identify all the minimal TIFSs and TITSs in every dimension d >= 3, i.e., the sets of each type having the smallest number of propositions. These sets are important because each of them leads to a proof of impossibility of noncontextual hidden variables and corresponds to a simple situation with quantum vs classical advantage. Moreover, the methods developed to identify them may be helpful to solve some open problems regarding minimal Kochen-Specker sets.