We conducted a computer-based psychological experiment in which a random mix of 40 tautologies and 40 non-tautologies were presented to the participants, who were asked to determine which ones of the formulas were tautologies. The participants were eight university students in computer science who had received tuition in propositional logic. The formulas appeared one by one, a time-limit of 45 s applied to each formula and no aids were allowed. For each formula we recorded the proportion of the participants who (...) classified the formula correctly before timeout and the mean response time among those participants. We propose a new proof formalism for modeling propositional reasoning with bounded cognitive resources. It models declarative memory, visual memory, working memory, and procedural memory according to the memory model of Atkinson and Shiffrin and reasoning processes according to the model of Newell and Simon. We also define two particular proof systems, T and NT, for showing propositional formulas to be tautologies and non-tautologies, respectively. The accuracy was found to be higher for non-tautologies than for tautologies ( p T was.89 and for non-tautologies the correlation between latency and minimum proof length in NT was.87. (shrink)

We investigate the modal logic of interpretability over Peano arithmetic. Our main result is a compactness theorem that extends the arithmetical completeness theorem for the interpretability logic ILM ω . This extension concerns recursively enumerable sets of formulas of interpretability logic (rather than single formulas). As corollaries we obtain a uniform arithmetical completeness theorem for the interpretability logic ILM and a partial answer to a question of Orey from 1961. After some simplifications, we also obtain Shavrukov's embedding theorem for Magari (...) algebras (a.k.a. diagonalizable algebras). (shrink)

First, we describe a psychological experiment in which the participants were asked to determine whether sentences of first-order logic were true or false in finite graphs. Second, we define two proof systems for reasoning about truth and falsity in first-order logic. These proof systems feature explicit models of cognitive resources such as declarative memory, procedural memory, working memory, and sensory memory. Third, we describe a computer program that is used to find the smallest proofs in the aforementioned proof systems when (...) capacity limits are put on the cognitive resources. Finally, we investigate the correlation between a number of mathematical complexity measures defined on graphs and sentences and some psychological complexity measures that were recorded in the experiment. (shrink)