Expressive Power and Incompleteness of Propositional Logics

Natural deduction systems were motivated by the desire to define the meaning of each connective by specifying how it is introduced and eliminated from inference. In one sense, this attempt fails, for it is well known that propositional logic rules (however formulated) underdetermine the classical truth tables. Natural deduction rules are too weak to enforce the intended readings of the connectives; they allow non-standard models. Two reactions to this phenomenon appear in the literature. One is to try to restore the standard readings, for example by adopting sequent rules with multiple conclusions. Another is to explore what readings the natural deduction rules do enforce. When the notion of a model of a rule is generalized, it is found that natural deduction rules express “intuitionistic” readings of their connectives. A third approach is presented here. The intuitionistic readings emerge when models of rules are defined globally, but the notion of a local model of a rule is also natural. Using this benchmark, natural deduction rules enforce exactly the classical readings of the connectives, while this is not true of axiomatic systems. This vindicates the historical motivation for natural deduction rules. One odd consequence of using the local model benchmark is that some systems of propositional logic are not complete for the semantics that their rules express. Parallels are drawn with incompleteness results in modal logic to help make sense of this.     

A Dynamic-Logical Perspective on Quantum Behavior

In this paper we show how recent concepts from Dynamic Logic, and in particular from Dynamic Epistemic logic, can be used to model and interpret quantum behavior. Our main thesis is that all the non-classical properties of quantum systems are explainable in terms of the non-classical flow of quantum information. We give a logical analysis of quantum measurements (formalized using modal operators) as triggers for quantum information flow, and we compare them with other logical operators previously used to model various forms of classical information flow: the “test” operator from Dynamic Logic, the “announcement” operator from Dynamic Epistemic Logic and the “revision” operator from Belief Revision theory. The main points stressed in our investigation are the following: (1) The perspective and the techniques of “logical dynamics” are useful for understanding quantum information flow. (2) Quantum mechanics does not require any modification of the classical laws of “static” propositional logic, but only a non-classical dynamics of information. (3) The main such non-classical feature is that, in a quantum world, all information-gathering actions have some ontic side-effects. (4) This ontic impact can affect in its turn the flow of information, leading to non-classical epistemic side-effects (e.g. a type of non-monotonicity) and to states of “objectively imperfect information”. (5) Moreover, the ontic impact is non-local: an information-gathering action on one part of a quantum system can have ontic side-effects on other, far-away parts of the system.     

Proof-Theoretic Functional Completeness for the Hybrid Logics of Everywhere and Elsewhere

A hybrid logic is obtained by adding to an ordinary modal logic further expressive power in the form of a second sort of propositional symbols called nominals and by adding so-called satisfaction operators. In this paper we consider hybridized versions of S5 (“the logic of everywhere”) and the modal logic of inequality (“the logic of elsewhere”). We give natural deduction systems for the logics and we prove functional completeness results.     

Toward a More Natural Expression of Quantum Logic with Boolean Fractions

This paper uses a non-distributive system of Boolean fractions (a|b), where a and b are 2-valued propositions or events, to express uncertain conditional propositions and conditional events. These Boolean fractions, ‘a if b’ or ‘a given b’, ordered pairs of events, which did not exist for the founders of quantum logic, can better represent uncertain conditional information just as integer fractions can better represent partial distances on a number line. Since the indeterminacy of some pairs of quantum events is due to the mutual inconsistency of their experimental conditions, this algebra of conditionals can express indeterminacy. In fact, this system is able to express the crucial quantum concepts of orthogonality, simultaneous verifiability, compatibility, and the superposition of quantum events, all without resorting to Hilbert space. A conditional (a|b) is said to be “inapplicable” (or “undefined”) in those instances or models for which b is false. Otherwise the conditional takes the truth-value of proposition a. Thus the system is technically 3-valued, but the 3rd value has nothing to do with a state of ignorance, nor to some half-truth. People already routinely put statements into three categories: true, false, or inapplicable. As such, this system applies to macroscopic as well as microscopic events. Two conditional propositions turn out to be simultaneously verifiable just in case the truth of one implies the applicability of the other. Furthermore, two conditional propositions (a|b) and (c|d) reside in a common Boolean sub-algebra of the non-distributive system of conditional propositions just in case b=d, their conditions are equivalent. Since all aspects of quantum mechanics can be represented with this near classical logic, there is no need to adopt Hilbert space logic as ordinary logic, just a need perhaps to adopt propositional fractions to do logic, just as we long ago adopted integer fractions to do arithmetic. The algebra of Boolean fractions is a natural, near-Boolean extension of Boolean algebra adequate to express quantum logic. While this paper explains one group of quantum anomalies, it nevertheless leaves no less mysterious the ‘influence-at-a-distance’, quantum entanglement phenomena. A quantum realist must still embrace non-local influences to hold that “hidden variables” are the measured properties of particles. But that seems easier than imaging wave-particle duality and instant collapse, as offered by proponents of the standard interpretation of quantum mechanics. Partial support for this work is gratefully acknowledged from the In-House Independent Research Program and from Code 2737 at the Space & Naval Warfare Systems Center (SSC-SD), San Diego, CA 92152-5001. Presently this work is supported by Data Synthesis, 2919 Luna Avenue, San Diego, CA 92117.     

Quantum logic as a dynamic logic

We address the old question whether a logical understanding of Quantum Mechanics requires abandoning some of the principles of classical logic. Against Putnam and others (Among whom we may count or not E. W. Beth, depending on how we interpret some of his statements), our answer is a clear “no”. Philosophically, our argument is based on combining a formal semantic approach, in the spirit of E. W. Beth’s proposal of applying Tarski’s semantical methods to the analysis of physical theories, with an empirical–experimental approach to Logic, as advocated by both Beth and Putnam, but understood by us in the view of the operational- realistic tradition of Jauch and Piron, i.e. as an investigation of “the logic of yes–no experiments” (or “questions”). Technically, we use the recently-developed setting of Quantum Dynamic Logic (Baltag and Smets 2005, 2008) to make explicit the operational meaning of quantum-mechanical concepts in our formal semantics. Based on our recent results (Baltag and Smets 2005), we show that the correct interpretation of quantum-logical connectives is dynamical, rather than purely propositional. We conclude that there is no contradiction between classical logic and (our dynamic reinterpretation of) quantum logic. Moreover, we argue that the Dynamic-Logical perspective leads to a better and deeper understanding of the “non-classicality” of quantum behavior than any perspective based on static Propositional Logic.     

Goodman’s “New Riddle”

First, a brief historical trace of the developments in confirmation theory leading up to Goodman’s infamous “grue” paradox is presented. Then, Goodman’s argument is analyzed from both Hempelian and Bayesian perspectives. A guiding analogy is drawn between certain arguments against classical deductive logic, and Goodman’s “grue” argument against classical inductive logic. The upshot of this analogy is that the “New Riddle” is not as vexing as many commentators have claimed (especially, from a Bayesian inductive-logical point of view). Specifically, the analogy reveals an intimate connection between Goodman’s problem, and the “problem of old evidence”. Several other novel aspects of Goodman’s argument are also discussed (mainly, from a Bayesian perspective).     

A Non-deterministic View on Non-classical Negations

We investigate two large families of logics, differing from each other by the treatment of negation. The logics in one of them are obtained from the positive fragment of classical logic (with or without a propositional constant ff for “the false”) by adding various standard Gentzen-type rules for negation. The logics in the other family are similarly obtained from LJ⁺, the positive fragment of intuitionistic logic (again, with or without ff). For all the systems, we provide simple semantics which is based on non-deterministic four-valued or three-valued structures, and prove soundness and completeness for all of them. We show that the role of each rule is to reduce the degree of non-determinism in the corresponding systems. We also show that all the systems considered are decidable, and our semantics can be used for the corresponding decision procedures. Most of the extensions of LJ⁺ (with or without ff) are shown to be conservative over the underlying logic, and it is determined which of them are not.     

Anderson and Belnap’s Invitation to Sin

Quine has argued that modal logic began with the sin of confusing use and mention. Anderson and Belnap, on the other hand, have offered us a way out through a strategy of nominalization. This paper reviews the history of Lewis’s early work in modal logic, and then proves some results about the system in which “A is necessary” is intepreted as “A is a classical tautology.”     

How our brains reason logically

The aim of this article is to strengthen links between cognitive brain research and formal logic. The work covers three fundamental sorts of logical inferences: reasoning in the propositional calculus, i.e. inferences with the conditional “if...then”, reasoning in the predicate calculus, i.e. inferences based on quantifiers such as “all”, “some”, “none”, and reasoning with n-place relations. Studies with brain-damaged patients and neuroimaging experiments indicate that such logical inferences are implemented in overlapping but different bilateral cortical networks, including parts of the fronto-temporal cortex, the posterior parietal cortex, and the visual cortices. I argue that these findings show that we do not use a single deterministic strategy for solving logical reasoning problems. This account resolves many disputes about how humans reason logically and why we sometimes deviate from the norms of formal logic.

‘Now’ and ‘Then’ in Tense Logic

According to Hans Kamp and Frank Vlach, the two-dimensional tense operators “now” and “then” are ineliminable in quantified tense logic. This is often adduced as an argument against tense logic, and in favor of an extensional account that makes use of explicit quantification over times. The aim of this paper is to defend tense logic against this attack. It shows that “now” and “then” are eliminable in quantified tense logic, provided we endow it with enough quantificational structure. The operators might not be redundant in some other systems of tense logic, but this merely indicates a lack of quantificational resources and does not show any deep-seated inability of tense logic to express claims about time. The paper closes with a brief discussion of the modal analogue of this issue, which concerns the role of the actuality operator in quantified modal logic.     

Counting distinctions: on the conceptual foundations of Shannon’s information theory

Categorical logic has shown that modern logic is essentially the logic of subsets (or “subobjects”). In “subset logic,” predicates are modeled as subsets of a universe and a predicate applies to an individual if the individual is in the subset. Partitions are dual to subsets so there is a dual logic of partitions where a “distinction” [an ordered pair of distinct elements (u, u′) from the universe U] is dual to an “element”. A predicate modeled by a partition π on U would apply to a distinction if the pair of elements was distinguished by the partition π, i.e., if u and u′ were in different blocks of π. Subset logic leads to finite probability theory by taking the (Laplacian) probability as the normalized size of each subset-event of a finite universe. The analogous step in the logic of partitions is to assign to a partition the number of distinctions made by a partition normalized by the total number of ordered |U|² pairs from the finite universe. That yields a notion of “logical entropy” for partitions and a “logical information theory.” The logical theory directly counts the (normalized) number of distinctions in a partition while Shannon’s theory gives the average number of binary partitions needed to make those same distinctions. Thus the logical theory is seen as providing a conceptual underpinning for Shannon’s theory based on the logical notion of “distinctions.” This paper is dedicated to the memory of Gian-Carlo Rota—mathematician, philosopher, mentor, and friend.     

Dissuasion as a Rhetorical Technique of Creating a General Disposition to Inaction

In this paper, it is argued that the classical rhetorical framework undergoes a transformation because of an important change in Western thought. Following this hypothesis, I analyze a rhetorical notion of “dissuasion” as a rhetorical technique of creating a “general disposition to inaction” in addition to a classical rhetorical notion of “dissuasion” that aims at “refraining from an action”.     

What is Classical Mereology?

Classical mereology is a formal theory of the part-whole relation, essentially involving a notion of mereological fusion, or sum. There are various different definitions of fusion in the literature, and various axiomatizations for classical mereology. Though the equivalence of the definitions of fusion is provable from axiom sets, the definitions are not logically equivalent, and, hence, are not inter-changeable when laying down the axioms. We examine the relations between the main definitions of fusion and correct some technical errors in prominent discussions of the axiomatization of mereology. We show the equivalence of four different ways to axiomatize classical mereology, using three different notions of fusion. We also clarify the connection between classical mereology and complete Boolean algebra by giving two “neutral” axiom sets which can be supplemented by one or the other of two simple axioms to yield the full theories; one of these uses a notion of “strong complement” that helps explicate the connections between the theories.     

Truth Values,Neither-true-nor-false,and Supervaluations

The first section (§1) of this essay defends reliance on truth values against those who, on nominalistic grounds, would uniformly substitute a truth predicate. I rehearse some practical, Carnapian advantages of working with truth values in logic. In the second section (§2), after introducing the key idea of auxiliary parameters (§2.1), I look at several cases in which logics involve, as part of their semantics, an extra auxiliary parameter to which truth is relativized, a parameter that caters to special kinds of sentences. In many cases, this facility is said to produce truth values for sentences that on the face of it seem neither true nor false. Often enough, in this situation appeal is made to the method of supervaluations, which operate by “quantifying out” auxiliary parameters, and thereby produce something like a truth value. Logics of this kind exhibit striking differences. I first consider the role that Tarski gives to supervaluation in first order logic (§2.2), and then, after an interlude that asks whether neither-true-nor-false is itself a truth value (§2.3), I consider sentences with non-denoting terms (§2.4), vague sentences (§2.5), ambiguous sentences (§2.6), paradoxical sentences (§2.7), and future-tensed sentences in indeterministic tense logic (§2.8). I conclude my survey with a look at alethic modal logic considered as a cousin (§2.9), and finish with a few sentences of “advice to supervaluationists” (2.10), advice that is largely negative. The case for supervaluations as a road to truth is strong only when the auxiliary parameter that is “quantified out” is in fact irrelevant to the sentences of interest—as in Tarski’s definition of truth for classical logic. In all other cases, the best policy when reporting the results of supervaluation is to use only explicit phrases such as “settled true” or “determinately true,” never dropping the qualification.     

Understanding risk: A guide for the perplexed

Over the course of the past decade, neurobiologists have become increasingly interested in concepts and models imported from economics. Terms such as “risk,” “risk aversion,” and “utility” have become commonplace in the neuroscientific literature as single-unit physiologists and human cognitive neuroscientists search for the biological correlates of economic theories of value and choice. Among neuroscientists, an incomplete understanding of these concepts has, however, led to a growing confusion that threatens to check the rapid advances in this area. Adding to the confusion, notions of risk have more recently been imported from finance, which employs quite different, although formally related, mathematical tools. Of course, the mixing of economic, financial, and neuroscientific traditions can only be beneficial in the long run, but truly understanding the conceptual machinery of each area is a prerequisite for obtaining that benefit. With that in mind, I present here an overview of economic and financial notions of risk and decision. The article begins with an overview of the classical economic approach to risk, as developed by Bernoulli. It then explains the important differences between the classical tradition and modern neoclassical economic approaches to these same concepts. Finally, I present a very brief overview of the financial tradition and its relation to the economic tradition. For novices, this should provide a reasonable introduction to concepts ranging from “risk aversion” to “risk premiums.”     

Monadic Bounded Algebras

We introduce the equational notion of a monadic bounded algebra (MBA), intended to capture algebraic properties of bounded quantification. The variety of all MBA’s is shown to be generated by certain algebras of two-valued propositional functions that correspond to models of monadic free logic with an existence predicate. Every MBA is a subdirect product of such functional algebras, a fact that can be seen as an algebraic counterpart to semantic completeness for monadic free logic. The analysis involves the representation of MBA’s as powerset algebras of certain directed graphs with a set of “marked” points.     

Logic with numbers

Many people regard utility theory as the only rigorous foundation for subjective probability, and even de Finetti thought the betting approach supplemented by Dutch Book arguments only good as an approximation to a utility-theoretic account. I think that there are good reasons to doubt this judgment, and I propose an alternative, in which the probability axioms are consistency constraints on distributions of fair betting quotients. The idea itself is hardly new: it is in de Finetti and also Ramsey. What is new is that it is shown that probabilistic consistency and consequence can be defined in a way formally analogous to the way these notions are defined in deductive (propositional) logic. The result is a free-standing logic which does not pretend to be a theory of rationality and is therefore immune to, among other charges, that of “logical omniscience”.     

Rough Sets and 3-Valued Logics

In the paper we explore the idea of describing Pawlak’s rough sets using three-valued logic, whereby the value t corresponds to the positive region of a set, the value f — to the negative region, and the undefined value u — to the border of the set. Due to the properties of the above regions in rough set theory, the semantics of the logic is described using a non-deterministic matrix (Nmatrix). With the strong semantics, where only the value t is treated as designated, the above logic is a “common denominator” for Kleene and Łukasiewicz 3-valued logics, which represent its two different “determinizations”. In turn, the weak semantics—where both t and u are treated as designated—represents such a “common denominator” for two major 3-valued paraconsistent logics. We give sound and complete, cut-free sequent calculi for both versions of the logic generated by the rough set Nmatrix. Then we derive from these calculi sequent calculi with the same properties for the various “determinizations” of those two versions of the logic (including Łukasiewicz 3-valued logic). Finally, we show how to embed the four above-mentioned determinizations in extensions of the basic rough set logics obtained by adding to those logics a special two-valued “definedness” or “crispness” operator.     

Dynamic Deontic Logic and its Paradoxes

In Meyer’s promising account [7] deontic logic is reduced to a dynamic logic. Meyer claims that with his account “we get rid of most (if not all) of the nasty paradoxes that have plagued traditional deontic logic.” But as was shown by van der Meyden in [4], Meyer’s logic also contains a paradoxical formula. In this paper we will show that another paradox can be proven, one which also effects Meyer’s “solution” to contrary to duty obligations and his logic in general. Presented by Hannes Leitgeb