We study the weak truth table degree spectra of first-order relational structures. We prove a dichotomy among the possible wtt degree spectra along the lines of Knight’s upward-closure theorem for Turing degree spectra. We prove new results contrasting the wtt degree spectra of finite- and infinite-signature structures. We show that, as a method of defining classes of reals, the wtt degree spectrum is, except for some trivial cases, strictly more expressive than the Turing degree spectrum.

Developing a suggestion of Wittgenstein, I provide an account of truth tables as formulas of a formal language. I define the syntax and semantics of TPL (the language of Tabular Propositional Logic), and develop its proof theory. Single formulas of TPL, and finite groups of formulas with the same top row and TF matrix (depiction of possible valuations), are able to serve as their own proofs with respect to metalogical properties of interest. The situation is different, however, for (...) groups of formulas whose top rows differ. For them I provide (i) a tree-style system of ‘row tree proofs’, which is shown to be sound and complete, and (ii) an alternative, re-writing strategy. (shrink)

Schnorr randomness and computable randomness are natural concepts of random sequences. However van Lambalgen’s Theorem fails for both randomnesses. In this paper we define truth-table Schnorr randomness and truth-table reducible randomness, for which we prove that van Lambalgen's Theorem holds. We also show that the classes of truth-table Schnorr random reals relative to a high set contain reals Turing equivalent to the high set. It follows that each high Schnorr random real is half of a real for (...) which van Lambalgen's Theorem fails. Moreover we establish the coincidence between triviality and lowness notions for truth-table Schnorr randomness. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim. (shrink)

Two types of truth table tasks are used investigating mental representations of conditionals: a possibilities-based and a truth-based one. In possibilities tasks, participants indicate whether a situation is possible or impossible according to the conditional rule. In truth tasks participants evaluate whether a situation makes the rule true or false, or is irrelevant with respect to the truth of the rule. Comparing the two-option version of the possibilities task with the truth task in Experiment 1, (...) the possibilities task yields logical answer patterns whereas the truth task yields defective patterns. Adding the irrelevant option to the possibilities task in Experiment 2 leads to a considerable amount of defective patterns in the possibilities task, but still to more logical patterns in the possibilities task than in the truth task. Experiment 3 shows that directionality matters since rule-to-situation tasks yield more logical answer patterns than do situation-to-rule tasks. We conclude that both task types are not comparable as such since wording, number of options and directionality influence the results. (shrink)

In our former works, for a given concept of reduction, we study the following hypothesis: “For a random oracle A, with probability one, the degree of the one-query tautologies with respect to A is strictly higher than the degree of A.” In our former works (Suzuki in Kobe J. Math. 15, 91–102, 1998; in Inf. Comput. 176, 66–87, 2002; in Arch. Math. Logic 44, 751–762), the following three results are shown: The hypothesis for p-T (polynomial-time Turing) reduction is equivalent to (...) the assertion that the probabilistic complexity class R is not equal to NP; The hypothesis for p-tt (polynomial-time truth-table) reduction implies that P is not NP; The hypothesis holds for each of the following: disjunctive reduction, conjunctive reduction, and p-btt (polynomial-time bounded-truth-table) reduction. In this paper, we show the following three results: (1) Let c be a positive real number. We consider a concept of truth-table reduction whose norm is at most c times size of input, where for a relativized propositional formula F, the size of F denotes the total number of occurrences of propositional variables, constants and propositional connectives. Then, our main result is that the hypothesis holds for such tt-reduction, provided that c is small enough. How small c can we take so that the above holds? It depends on our syntactic convention on one-query tautologies. In our setting, the statement holds for all c < 1. (2) The hypothesis holds for monotone truth-table reduction (also called positive reduction). (3) Dowd (in Inf. Comput. 96, 65–76, 1992) shows a polynomial upper bound for the minimum sizes of forcing conditions associated with a random oracle. We apply the above result (1), and get a linear lower bound for the sizes. (shrink)

Two types of truth table task are used to examine people's mental representation of conditionals. In two within-participants experiments, participants either receive the same task-type twice (Experiment 1) or are presented successively with both a possibilities task and a truth task (Experiment 2). Experiment 3 examines how people interpret the three-option possibilities task and whether they have a clear understanding of it. The present study aims to examine, for both task-types, how participants' cognitive ability relates to the classification (...) of the truth table cases as irrelevant, and their consistency in doing so. Looking at the answer patterns, participants' cognitive ability influences their classification of the truth table cases: A positive correlation exists between cognitive ability and the number of false-antecedent cases classified as ?irrelevant?, both in the possibilities task and the truth task. This favours a suppositional representation of conditionals. (shrink)

The relativized propositional calculus is a system of Boolean formulas with query symbols. A formula in this system is called a one-query formula if the number of occurrences of query symbols is just one. If a one-query formula is a tautology with respect to a given oracle A then it is called a one-query tautology with respect to A. By extending works of Ambos-Spies (1986) and us (2002), we investigate the measure of the class of all oracles A such that (...) the set of all one-query tautologies with respect to A does not p-btt-reduce to A, where p-btt denotes polynomial-time bounded-truth-table. We show that certain Dowd-type generic oracles all belong to the class, and hence measure of the class is one. (shrink)

Using a latent variable modelling strategy we study individual differences in patterns of answers to the selection task and to the truth table task. Specifically we investigate the prediction of mental model theory according to which the individual tendency to select the false consequent card (in the selection task) is negatively correlated with the tendency to judge the false antecedent cases as irrelevant (in the truth table task). We fit a psychometric model to two large samples ( N (...) = 486, twice), and find no evidence for this negative correlation. We examine which of the assumptions of the model theory must be amended to accommodate our findings. (shrink)

ABSTRACTDo truth tables—the ordinary sort that we use in teaching and explaining basic propositional logic—require an assumption of consistency for their construction? In this essay we show that truth tables can be built in a consistency-independent paraconsistent setting, without any appeal to classical logic. This is evidence for a more general claim—that when we write down the orthodox semantic clauses for a logic, whatever logic we presuppose in the background will be the logic that appears in (...) the foreground. Rather than any one logic being privileged, then, on this count partisans across the logical spectrum are in relatively similar dialectical positions. (shrink)

It has been suggested that Russell and or Wittgenstein arrived at a truth-table device in or around 1912 [Shosky 1997], and that, since the history of its development is so complex, the best one can claim is that theirs may be the first identifiably ascribable example. However, Charles Peirce had, unbeknownst to most logicians of the time, already developed a truth table for binary connectives of his algebra of logic in 1902.

Let $D_{tt} $ denote the set of truth-table degrees. A bijection π: $D_{tt} \to \,D_{tt} $ is an automorphism if for all truth-table degrees x and y we have $ \leqslant _{tt} \,y\, \Leftrightarrow \,\pi (x)\, \leqslant _{tt} \,\pi (y)$ . We say an automorphism π is fixed on a cone if there is a degree b such that for all $x \geqslant _{tt} b$ we have π(x) = x. We first prove that for every 2-generic real X (...) we have X' $X' \le _{tt} \,X\, \oplus \,0'$ . We next prove that for every real $X \ge _{tt} \,0'$ there is a real Y such that $Y \oplus 0{\text{'}}\, \equiv _{tt} \,Y{\text{'}} \equiv _{tt} \,X$ . Finally, we use this to demonstrate that every automorphism of the truth-table degrees is fixed on a cone. (shrink)

Kalrnaric. We set out a system T, consisting of normal proofs constructed by means of elegantly symmetrical introduction and elimination rules. In the system T there are two requirements, called ( ) and ()), on applications of discharge rules. T is sound and complete for Kalmaric arguments. ( ) requires nonvacuous discharge of assumptions; ()) requires that the assumption discharged be the sole one available of highest degree. We then consider a 'Duhemian' extension T*, obtained simply by dropping the requirement (...) ()). T* is a proper subsystem of intuitionistic relevant logic. Our main result is that T* is a double negation consistency companion to classical logic. Thus all one needs to add to T* to obtain classical logic is the (intuitionistic) absurdity rule, and the (classical) rule of double nega-. (shrink)

There are certain uses of and and or that cannot be explained by their normal meanings as truth-functional connectives, even with sophisticated pragmatic resources. These include examples such as The cops show up, and a fight will break out (‘If the cops show up, a fight will break out’), and I have no friends, or I would throw a party (‘I have no friends. If I did have friends, I would throw a party.’). We argue that these uses are (...) indeed distinct from the more ordinary uses of and and or, but that they are nonetheless related in a principled way. To explain them we give an analysis of what we call the dynamic effects of connectives, which arise in all their uses. The special uses at issue are then argued to be instances where the connectives exhibit their dynamic effects without their truth-conditional meaning. (shrink)

Psychological research on people’s understanding of natural language connectives has traditionally used truth table tasks, in which participants evaluate the truth or falsity of a compound sentence given the truth or falsity of its components in the framework of propositional logic. One perplexing result concerned the indicative conditional if A then C which was often evaluated as true when A and C are true, false when A is true and C is false but irrelevant“ (devoid of value) (...) when A is false (whatever the value of C). This was called the “psychological defective table of the conditional.” Here we show that far from being anomalous the “defective” table pattern reveals a coherent semantics for the basic connectives of natural language in a trivalent framework. This was done by establishing participants’ truth tables for negation, conjunction, disjunction, conditional, and biconditional, when they were presented with statements that could be certainly true, certainly false, or neither. We review systems of three-valued tables from logic, linguistics, foundations of quantum mechanics, philosophical logic, and artificial intelligence, to see whether one of these systems adequately describes people’s interpretations of natural language connectives. We find that de Finetti’s (1936/1995) three-valued system is the best approximation to participants’ truth tables. (shrink)

We give several characterizations of Schnorr trivial sets, including a new lowness notion for Schnorr triviality based on truth-table reducibility. These characterizations allow us to see not only that some natural classes of sets, including maximal sets, are composed entirely of Schnorr trivials, but also that the Schnorr trivial sets form an ideal in the truth-table degrees but not the weak truth-table degrees. This answers a question of Downey, Griffiths and LaForte.

In this paper, a novel experimental task is developed for testing the highly influential, but experimentally underexplored, possible worlds account of conditionals (Stalnaker, 1968; Lewis, 1973). In Experiment 1, this new task is used to test both indicative and subjunctive conditionals. For indicative conditionals, five competing truth tables are compared, including the previously untested, multi-dimensional possible worlds semantics of Bradley (2012). In Experiment 2, these results are replicated and it is shown that they cannot be accounted for by (...) an alternative hypothesis proposed by our reviewers. In Experiment 3, individual variation in truth assignments of indicative conditionals is investigated via Bayesian mixture models that classify participants as following one of several competing models. As a novelty of this study, it is found that a possible worlds semantics of Lewis and Stalnaker is capable of accounting for participants’ aggregate truth value assignments in this task. Applied to indicative conditionals, we show across three experiments, that the theory both captures participants’ truth values at the aggregate level (Experiments 1 and 2) and that it makes up the largest subgroup in the analysis of individual variation in our experimental paradigm (Experiment 3). (shrink)

We explore the technical details and historical evolution of Charles Peirce's articulation of a truth table in 1893, against the background of his investigation into the truth-functional analysis of propositions involving implication. In 1997, John Shosky discovered, on the verso of a page of the typed transcript of Bertrand Russell's 1912 lecture on ?The Philosophy of Logical Atomism? truth table matrices. The matrix for negation is Russell's, alongside of which is the matrix for material implication in the (...) hand of Ludwig Wittgenstein. It is shown that an unpublished manuscript identified as composed by Peirce in 1893 includes a truth table matrix that is equivalent to the matrix for material implication discovered by John Shosky. An unpublished manuscript by Peirce identified as having been composed in 1883?1884 in connection with the composition of Peirce's ?On the Algebra of Logic: A Contribution to the Philosophy of Notation? that appeared in the American Journal of Mathematics in 1885 includes an example of an indirect truth table for the conditional. (shrink)

We show that Smullyan's analytic tableaux cannot p-simulate the truth-tables. We identify the cause of this computational breakdown and relate it to an underlying semantic difficulty which is common to the whole tradition originating in Gentzen's sequent calculus, namely the dissonance between cut-free proofs and the Principle of Bivalence. Finally we discuss some ways in which this principle can be built into a tableau-like method without affecting its analytic nature.

We study the classes of hypersimple and semicomputable sets as well as their intersection in the weak truth table degrees. We construct degrees that are not bounded by hypersimple degrees outside any non-trivial upper cone of Turing degrees and show that the hypersimple-free c.e. wtt degrees are downwards dense in the c.e. wtt degrees. We also show that there is no maximal (w.r.t. ≤wtt) hypersimple wtt degree. Moreover, we consider the sets that are both hypersimple and semicomputable, characterize them (...) as the (bi-infinite) c.e. cuts of computable orderings of ℕ of order type ω+ω* and study their wtt degrees. We show that there are hypersimple degrees that are not bounded by any hypersimple semicomputable degree, investigate relationships with the join and look for maximal and minimal elements of related classes. (shrink)

We give a decision procedure for the ∀∃-theory of the weak truth-table (wtt) degrees of the recursively enumerable sets. The key to this decision procedure is a characterization of the finite lattices which can be embedded into the r.e. wtt-degrees by a map which preserves the least and greatest elements: a finite lattice has such an embedding if and only if it is distributive and the ideal generated by its cappable elements and the filter generated by its cuppable elements (...) are disjoint. We formulate general criteria that allow one to conclude that a distributive upper semi-lattice has a decidable two-quantifier theory. These criteria are applied not only to the weak truth-table degrees of the recursively enumerable sets but also to various substructures of the polynomial many-one (pm) degrees of the recursive sets. These applications to the pm degrees require no new complexity-theoretic results. The fact that the pm-degrees of the recursive sets have a decidable two-quantifier theory answers a question raised by Shore and Slaman in [21]. (shrink)

If r is a reducibility between sets of numbers, a natural question to ask about the structure ? r of the r-degrees containing computably enumerable sets is whether every element not equal to the greatest one is branching (i.e., the meet of two elements strictly above it). For the commonly studied reducibilities, the answer to this question is known except for the case of truth-table (tt) reducibility. In this paper, we answer the question in the tt case by showing (...) that every tt-incomplete computably enumerable truth-table degree a is branching in ? tt . The fact that every Turing-incomplete computably enumerable truth-table degree is branching has been known for some time. This fact can be shown using a technique of Ambos-Spies and, as noticed by Nies, also follows from a relativization of a result of Degtev. We give a proof here using the Ambos-Spies technique because it has not yet appeared in the literature. The proof uses an infinite injury argument. Our main result is the proof when a is Turing-complete but tt-incomplete. Here we are able to exploit the Turing-completeness of a in a novel way to give a finite injury proof. (shrink)

This essay provides an intuitive technique that illustrates why a conditional must be true when the antecedent is false and the consequent is either true or false. Other techniques for explaining the conditional’s truth table are unsatisfactory.

There is ample evidence that in classical truth table task experiments false antecedents are judged as ?irrelevant?. Instead of interpreting this in support of a suppositional representation of conditionals, Schroyens (2010a, 2010b) attributes it to the induction problem: the impossibility of establishing the truth of a universal claim on the basis of a single case. In the first experiment a truth table task with four options is administered and the correlation with intelligence is inspected. It is observed (...) that ?undetermined? is chosen in one third of the judgements and ?irrelevant? in another third. A positive correlation is revealed between intelligence and the number of ?irrelevant? and ?undetermined? judgements. The data do not exclude that a part of the ?irrelevant? judgements in classical truth table task experiments might be caused by the induction problem. In the second experiment participants are presented with a simplified four-option truth table task and asked for a justification of their judgements. These justifications show the induction problem is not the reason for choosing the ?irrelevant? or ?undetermined? option, which is supportive for a suppositional representation of conditionals. (shrink)

The following theorems on the structure inside nonrecursive truth-table degrees are established: Dëgtev's result that the number of bounded truth-table degrees inside a truth-table degree is at least two is improved by showing that this number is infinite. There are even infinite chains and antichains of bounded truth-table degrees inside every truth-table degree. The latter implies an affirmative answer to the following question of Jockusch: does every truth-table degree contain an infinite antichain of many-one (...) degrees? Some but not all truth-table degrees have a least bounded truth-table degree. The technique to construct such a degree is used to solve an open problem of Beigel, Gasarch and Owings: there are Turing degrees (constructed as hyperimmune-free truth-table degrees) which consist only of 2-subjective sets and therefore do not contain any objective set. Furthermore, a truth-table degree consisting of three positive degrees is constructed where one positive degree consists of enumerable semirecursive sets, one of coenumerable semirecursive sets and one of sets, which are neither enumerable nor coenumerable nor semirecursive. So Jockusch's result that there are at least three positive degrees inside a truth-table degree is optimal. The number of positive degrees inside a truth-table degree can also be some other odd integer as for example nineteen, but it is never an even finite number. (shrink)

Prior’s Tonk is a famously horrible connective. It is defined by its inference rules. My aim in this article is to compare Tonk with some hitherto unnoticed nasty connectives, which are defined in semantic terms. I first use many-valued truth-tables for classical sentential logic to define a nasty connective, Knot. I then argue that we should refuse to add Knot to our language. And I show that this reverses the standard dialectic surrounding Tonk, and yields a novel solution (...) to the problem of many-valued truth-tables for classical sentential logic. I close by outlining the technicalities surrounding nasty connectives on many-valued truth-tables. (shrink)

While there is now considerable experimental evidence that, on the one hand, participants assign to the indicative conditional as probability the conditional probability of consequent given antecedent and, on the other, they assign to the indicative conditional the “defective truth-table” in which a conditional with false antecedent is deemed neither true nor false, these findings do not in themselves establish which multi-premise inferences involving conditionals participants endorse. A natural extension of the truth-table semantics pronounces as valid numerous inference (...) patterns that do seem to be part of ordinary usage. However, coupled with something the probability account gives us—namely that when conditional-free ϕ entails conditional-free ψ, “if ϕ then ψ” is a trivial, uninformative truth—we have enough logic to derive the paradoxes of material implication. It thus becomes a matter of some urgency to determine which inference patterns involving indicative conditionals participants do endorse. Only thus will we be able to arrive at a realistic, systematic semantics for the indicative conditional. (shrink)

Informal construction -- Formal construction -- Limiting results.

We show that the partial order of Σ0 3-sets under inclusion is elementarily definable with parameters in the semilattice of r.e. wtt-degrees. Using a result of E. Herrmann, we can deduce that this semilattice has an undecidable theory, thereby solving an open problem of P. Odifreddi.

ABSTRACTThe probabilistic truth table task involves assessing the probability of "If A then C" conditional sentences. Previous studies have shown that a majority of participants assess this probability as the conditional probability P while a substantial minority responds with the probability of the conjunction A and C. In an experiment involving 96 participants, we investigated the impact on the rate of conjunctive responses of the context in which the task is framed. We show that a context intended to lead (...) participants to consider all the possible cases elicited more conjunctive responses than a context assumed not to have this effect. These results suggest that the step of inferring the probability can distort our assessment of participants' interpretation of conditional sentences. This might compromise the validity of the probabilistic task in studying conditional reasoning. (shrink)