A note on the complexity of Boolean concepts

Abstract
What is the relationship between the degree of learning difficulty of a Boolean concept (i.e., a category defined by logical rules expressed in terms of Boolean operators) and the complexity of its logical description? Feldman [(2000). Minimization of Boolean complexity in human concept learning. Nature, 407(October), 630–633] investigated this question experimentally by defining the complexity of a Boolean formula (that logically describes a concept) as the length of the shortest formula logically equivalent to it. Using this measure as the independent variable in his experiment, he concludes that in general, the subjective difficulty of learning a Boolean concept is well predicted by Boolean complexity. Moreover, he claims that one of the landmark results and benchmarks in the human concept learning literature, the Shepard, Hovland, and Jenkins learning difficulty ordering, is precisely predicted by this hypothesis. However, in what follows, we introduce a heuristic procedure for reducing Boolean formulae, based in part on the well-established minimization technique from Boolean algebra known as the Quine–McCluskey (QM) method, which when applied to the SHJ Boolean concept types reveals that some of their complexity values are notably different from the approximate values obtained by Feldman. Furthermore, using the complexity values for these simpler expressions fails to predict the correct empirical difficulty ordering of the SHJ concept types. Motivated by these findings, this note includes a brief tutorial on the QM method and concludes with a brief discussion on some of the challenges facing the complexity hypothesis.
Keywords No keywords specified (fix it)
Categories No categories specified
(categorize this paper)
Options
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
 
Download options
PhilPapers Archive


Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 10,768
External links
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA

No references found.

Citations of this work BETA
Similar books and articles
Analytics

Monthly downloads

Added to index

2009-01-28

Total downloads

2 ( #345,621 of 1,099,004 )

Recent downloads (6 months)

1 ( #287,293 of 1,099,004 )

How can I increase my downloads?

My notes
Sign in to use this feature


Discussion
Start a new thread
Order:
There  are no threads in this forum
Nothing in this forum yet.