A catalog of Boolean concepts. (English) Zbl 1040.91093

Feldman, Jacob

J. Math. Psychol. 47, No. 1, 75-89 (2003).

Summary: Boolean concepts are concepts whose membership is determined by a Boolean function, such as that expressed by a formula of propositional logic. Certain Boolean concepts have been much studied in the psychological literature, in particular with regard to their ease of learning. But research attention has been somewhat uneven, with a great deal of attention paid to certain concepts and little to others, in part because of the unavailability of a comprehensive catalog. This paper gives a complete classification of Boolean concepts up to congruence (isomorphism of logical form). Tables give complete details of all concepts determined by up to four Boolean variables. For each concept type, the tables give a canonic logical expression, an approximately minimal logical expression, the Boolean complexity (length of the minimal expression), the number of distinct Boolean concepts of that type, and a pictorial depiction of the concept as a set of vertices in Boolean \(D\)-space. Some psychological properties of Boolean concepts are also discussed.

MSC:

91E40

Memory and learning in psychology

References:

[1]	Aiken, H. H., & the Staff of the Computation Laboratory at Harvard University. (1951). Synthesis of electronic computing and control circuits. Cambridge: Harvard University Press.
[2]	Armstrong, S.; Gleitman, L.; Gleitman, H., What some concepts might not be, Cognition, 13, 263-308, (1983)
[3]	Boole, G., An investigation of the laws of thought on which are founded the mathematical theories of logic and probabilities, (1854), Dover New York
[4]	Bourne, L.E., Knowing and using concepts, Psychological review, 77, 6, 546-556, (1970)
[5]	Bourne, L.E.; Ekstrand, B.R.; Montgomery, B., Concept learning as a function of the conceptual rule and the availability of positive and negative instances, Journal of experimental psychology, 82, 3, 538-544, (1969)
[6]	Bruner, J.S.; Goodnow, J.J.; Austin, G.A., A study of thinking, (1956), Wiley New York
[7]	Chaitin, G.J., On the length of programs for computing finite binary sequences, Journal of the association for computing machinery, 13, 547-569, (1966) · Zbl 0158.25301
[8]	Ciborowski, T.; Cole, M., A cross-cultural study of conjunctive and disjunctive concept learning, Child development, 43, 774-789, (1972)
[9]	Feldman, J., Minimization of Boolean complexity in human concept learning, Nature, 407, 630-633, (2000)
[10]	Fodor, J., Conceptsa potboiler, Cognition, 50, 95-113, (1994)
[11]	Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman New York · Zbl 0411.68039
[12]	Givone, D.D., Introduction to switching circuit theory, (1970), McGraw Hill New York · Zbl 0213.17905
[13]	Harrison, M.A., Introduction to switching and automata theory, (1965), McGraw-Hill New York · Zbl 0196.51702
[14]	Haygood, R. C. (1963). Rule and attribute learning as aspects of conceptual behavior. Doctoral dissertation, University of Utah, unpublished.
[15]	Haygood, R.C.; Bourne, L.E., Attribute- and rule-learning aspects of conceptual behavior, Psychological review, 72, 3, 175-195, (1965)
[16]	Johnson-Laird, P.N., Mental models: towards a cognitive science of language, inference, and consciousness, (1983), Harvard University Press Cambridge
[17]	Kolmogorov, A.N., Three approaches to the quantitative definition of information, Problems of information transmission, 1, 1, 1-7, (1965) · Zbl 0271.94018
[18]	Kruschke, J., Alcovean exemplar-based connectionist model of category learning, Psychological review, 99, 1, 22-44, (1992)
[19]	Li, M.; Vitányi, P., An introduction to Kolmogorov complexity and its applications, (1997), Springer New York · Zbl 0866.68051
[20]	McCulloch, W.S.; Pitts, W.H., A logical calculus of the ideas immanent in nervous activity, Bulletin of mathematical biophysics, 5, 89-93, (1943), (Reprinted in W. S. McCulloch, Embodiments of mind, Cambridge, MIT Press, 1965.) · Zbl 0063.03860
[21]	Medin, D.L.; Altom, M.W.; Edelson, S.M.; Freko, D., Correlated symptoms and simulated medical classification, Journal of experimental psychology: learning, memory, and cognition, 8, 37-50, (1982)
[22]	Medin, D.L.; Schaffer, M.M., Context model of classification learning, Psychological review, 85, 207-238, (1978)
[23]	Neisser, U.; Weene, P., Hierarchies in concept attainment, Journal of experimental psychology, 64, 6, 640-645, (1962)
[24]	Nosofsky, R.M.; Gluck, M.A.; Palmeri, T.J.; McKinley, S.C.; Glauthier, P., Comparing models of rule-based classification learninga replication and extension of Shepard, hovland, and Jenkins (1961), Memory cognition, 22, 3, 352-369, (1994)
[25]	Nosofsky, R.M.; Palmeri, T.J.; McKinley, S.C., Rule-plus-exception model of classification learning, Psychological review, 101, 1, 53-79, (1994)
[26]	Paterson, M. S. (Ed.). (1992). Boolean function complexity. Cambridge: Cambridge University Press. · Zbl 0754.00019
[27]	Posner, M.I.; Keele, S.W., On the genesis of abstract ideas, Journal of experimental psychology, 77, 3, 353-363, (1968)
[28]	Rosch, E.H., Natural categories, Cognitive psychology, 4, 328-350, (1973)
[29]	Schöning, U.; Pruim, R., Gems of theoretical computer science, (1998), Springer Berlin · Zbl 0911.68002
[30]	Shepard, R.; Hovland, C.L.; Jenkins, H.M., Learning and memorization of classifications, Psychological monographs: general and applied, 75, 13, 1-42, (1961)
[31]	Smith, J.D.; Minda, J.P., Thirty categorization results in search of a model, Journal of experimental psychology: learning memory and cognition, 26, 1, 3-27, (2000)
[32]	Solomonoff, R.J., A formal theory of inductive inferencepart I, Information and control, 7, 1-22, (1964) · Zbl 0258.68045
[33]	Wegener, I., The complexity of Boolean functions, (1987), Wiley Chichester · Zbl 0623.94018
[34]	Wells, H., & Deffenbacher, K. A. (1967). Comparative study of conjuntive and disjunctive concept learning. In: Proceedings of the 75th annual convention of the American Psychological Association (pp. 46-48). Washington, DC.