Course content
Lecture 1: Logic & Cognition. Introduction and Some Examples
In the first lecture we will discuss philosophical issues surrounding the project of applying modern logic and computability theory in cognitive science. We will start with the brief historical overview of the divide between logic and psychology. Then, we will present a modern information processing approach to cognitive task that links nicely with logic and computability theory.
In the second part we will present some examples of how logic can be used to analyze the structure and difficulty of cognitive tasks. The general strategy here is to assign a logical representation to a relevant domain of reasoning, and to associate a logical proof with each strategic reasoning leading to a solution. By comparing the `complexity’ of the proofs we can estimate and test the cognitive difficulty of various tasks. We will focus on 2 examples: syllogistic reasoning and playing Master Mind game.
References:
- Bart Geurts. Reasoning with quantifiers. Cognition, 2003.
- Nina Gierasimczuk, Han van der Maas, and Maartje Raijmakers. Logical and psychological analysis of Deductive Mastermind. Proceedings of the Logic & Cognition Workshop at ESSLLI 2012.
- Michiel van Lambalgen and Keith Stenning. Human reasoning and cognitive science. MIT 2008.
Lecture 2: Cognition & Computability
This lecture will review the ties between cognition and computability theory via the psychological version of Church-Turing Thesis and P-Cognition Thesis. On the one hand, we will focus on some cognitive processes of complexity reaching beyond Turing boundary, like language acquisition, learning or belief revision. On the other hand, we explore how computational complexity theory may help to delimit cognitively tractable functions within computable range. Time permitting, we will show some experiments suggesting that people avoid intractability.
References:
- Nina Gierasimczuk and Jakub Szymanik. Branching quantification vs. two-way quantification, Journal of Semantics, 2009.
- Juha Kontinen and Jakub Szymanik. A remark on collective quantification. Journal of Logic, Language, and Information, 2008.
- Peter Kugel. Thinking may be more than computing. Cognition, 1986.
- Iris Van Rooij. The tractable cognition thesis. Cognitive Science, 2008.
- Jakub Szymanik. Computational complexity of polyadic lifts of generalized quantifiers in natural language. Linguistics & Philosophy 2010.
Lecture 3: Semantics & Cognition
In this lecture we will show how automata theory can be used to link formal semantics of natural language with human processing. In particular, formal results on complexity allow us to predict cognitive load of subjects involved in sentence comprehension
References:
- Jakub Szymanik and Marcin Zajenkowski. Comprehension of simple quantifiers. Empirical Evaluation of a Computational Model, Cognitive Science, 2010.
- Jakub Szymanik and Marcin Zajenkowski. Quantifiers and working memory, Proceedings of Amsterdam Colloquium 2009, Lecture Notes in Artificial Intelligence 6042, 2010.
- Marcin Zajenkowski, Rafał Styła, and Jakub Szymanik. A computational approach to quantifiers as an explanation for some language impairments in schizophrenia, Journal of Communication Disorder, 2011.
- Jakub Szymanik, Shane Steinert-Threlkeld, Marcin Zajenkowski, and Thomas F. Icard III. Automata and complexity in multiple-quantifier sentence verification, Proceedings of the 12th International Conference on Cognitive Modeling, 2013.
Lecture 4: Logic & Social Cognition
In this lecture we will focus on logical approaches to social cognition. In particular, we will analyze cognitive tasks demanding higher-order reasoning of the form ‘I believe that Ann knows that Peter thinks…’ . In the psychological research on the Theory of Mind there are two dominating experimental paradigms: turn-based games and false-belief task. We show how to formalize those tasks and use some structural properties to predict participants’ behaviors when solving the experimental trials.
References:
- Torben Brauner. Hybrid-logical reasoning in false-belief tasks. Proceedings of the 14th Conference on Theoretical Aspects of Rationality and Knowledge, 2013.
- Nina Gierasimczuk and Jakub Szymanik. A note on a generalization of the Muddy Children. Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge, 2011.
- Jakub Szymanik, Ben Meijering, and Rineke Verbrugge. Using intrinsic complexity of turn-taking games to predict participants’ reaction times. Proceedings of the 35th Annual Conference of Cognitive Science Society, 2013.
- Michiel van Lambalgen and Keith Stenning. Human reasoning and cognitive science. MIT 2008.
- Rineke Verbrugge. Logic and social cognition: The facts matter, and so do computational models. Journal of Philosophical Logic, 2009.