Minimization of Boolean complexity in human concept learning

Top Cited Papers
Publisher Website
Google Scholar
Abstract
One of the unsolved problems in the field of human concept learning concerns the factors that determine the subjective difficulty of concepts: why are some concepts psychologically simple and easy to learn, while others seem difficult, complex or incoherent? This question was much studied in the 1960s1 but was never answered, and more recent characterizations of concepts as prototypes rather than logical rules2,3 leave it unsolved4,5,6. Here I investigate this question in the domain of Boolean concepts (categories defined by logical rules). A series of experiments measured the subjective difficulty of a wide range of logical varieties of concepts (41 mathematically distinct types in six families—a far wider range than has been tested previously). The data reveal a surprisingly simple empirical ‘law’: the subjective difficulty of a concept is directly proportional to its Boolean complexity (the length of the shortest logically equivalent propositional formula)—that is, to its logical incompressibility.