Reasoning about partial functions with the aid of a computer

Partial functions are ubiquitous in both mathematics and computer science. Therefore, it is imperative that the underlying logical formalism for a general-purpose mechanized mathematics system provide strong support for reasoning about partial functions. Unfortunately, the common logical formalisms — first-order logic, type theory, and set theory — are usually only adequate for reasoning about partial functionsin theory. However, the approach to partial functions traditionally employed by mathematicians is quite adequatein practice. This paper shows how the traditional approach to partial functions can be formalized in a range of formalisms that includes first-order logic, simple type theory, and Von-Neumann—Bernays—Gödel set theory. It argues that these new formalisms allow one to directly reason about partial functions; are based on natural, well-understood, familiar principles; and can be effectively implemented in mechanized mathematics systems.Supported by the MITRE-Sponsored Research program. This paper is a written version (with references) of an address given at the Partial Functions and Programming: Foundational Questions conference held 17 February 1995 at the University ol California at Irvine.     

A transitive-chain theory of syllogistic reasoning

A new theory of syllogistic reasoning, called the transitive-chain theory, is presented. The transitive-chain theory proposes that information about set relations is represented in memory by pairs of informational components. The theory further proposes that information about set relations is integrated by applying a small set of rules to transitive chains of these set relations. The rules that are applied to these chains are specified in detail. The theory is cast in terms of information-processing models for variants of the syllogistic reasoning task, and then mathematical models that quantify each of these information-processing models are presented. In a series of five experiments, the transitive-chain theory provides a good account of the response-choice data for syllogisms with various types of content, quantifiers, and logical relations (categorical and conditional). The results of these experiments offer tentative answers to four issues in the theory of syllogistic reasoning: (a) representation of premise information; (b) combination of premise information; (c) sources of difficulty in syllogistic reasoning; and (d) generality of the processes used in syllogistic reasoning.     

Theories of the syllogism: A meta-analysis

Syllogisms are arguments about the properties of entities. They consist of 2 premises and a conclusion, which can each be in 1 of 4 "moods": All A are B, Some A are B, No A are B, and Some A are not B. Their logical analysis began with Aristotle, and their psychological investigation began over 100 years ago. This article outlines the logic of inferences about syllogisms, which includes the evaluation of the consistency of sets of assertions. It also describes the main phenomena of reasoning about properties. There are 12 extant theories of such inferences, and the article outlines each of them and describes their strengths and weaknesses. The theories are of 3 main sorts: heuristic theories that capture principles that could underlie intuitive responses, theories of deliberative reasoning based on formal rules of inference akin to those of logic, and theories of deliberative reasoning based on set-theoretic diagrams or models. The article presents a meta-analysis of these extant theories of syllogisms using data from 6 studies. None of the 12 theories provides an adequate account, and so the article concludes with a guide-based on its qualitative and quantitative analyses-of how best to make progress toward a satisfactory theory.     

Unification of Two Approaches to Quantum Logic: Every Birkhoff – von Neumann Quantum Logic is a Partial Infinite-Valued Łukasiewicz Logic

In the paper it is shown that every physically sound Birkhoff – von Neumann quantum logic, i.e., an orthomodular partially ordered set with an ordering set of probability measures can be treated as partial infinite-valued ?ukasiewicz logic, which unifies two competing approaches: the many-valued, and the two-valued but non-distributive, which have co-existed in the quantum logic theory since its very beginning.     

Braine心理逻辑理论述评

该文对Braine提出的在推理心理学研究领域占居重要地位的“心理逻辑理论”做了综合述评。“心理逻辑理论”主要包括三方面内容:构成“心理逻辑理论”基础的一组推理规则图式、将推理规则图式应用于推理过程的推理方案、实际应用意义。Braine认为他和他的同事于1984年设计并实施的以“自然推理系统”所含各推理规则为实验材料的实验结果支持该理论的基本观点。     

Social Cognition and the So-Called Conjunction Fallacy

The so-called ‘conjunction effect’, in which participants incorrectly assert that an instance from the conjunction of two sets is more probable than an instance from one of the two conjoining sets alone, has been a source of debate as to whether it is a genuine fallacy of individual thinking or not. We argue that reasoning about individuals follows a different process than reasoning about sets. 35 participants took part in 3 tasks: a) one involving blocks of different sizes and colours designed to evoke set-based reasoning, b) one where a particular block was ‘individuated’ by stating that it represented a particular person, and c) the original Tversky and Kahneman (Psychological Review 90(4):293–315, 1983) ‘Linda’ problem. As predicted, set-based reasoning was significantly more prevalent for the blocks task than for the other two tasks. Participants’ reasons for their choices suggest that some individuals correctly use set-based logic in one task and a social reasoning process for the other tasks.     

Measuring inaccuracy of uncertain doxastic states in many-valued logical systems

I will propose an alternative philosophical approach to the representation of uncertain doxastic states. I will argue that the current account of measuring inaccuracy of uncertain doxastic states is inadequate for Belnap's four-valued logic. Specifically, a situation can be found in which either an inaccuracy measure returns a completely wrong result or an agent's inaccuracy score is inadequate relative to the mistake in her doxastic attitude. This will motivate an alternative representation of uncertain doxastic states based on ordered pairs. I will describe a possible inaccuracy measure that is suitable for ordered pairs, and I will show that it has all the qualities that are required for an inaccuracy measure to be legitimate. Finally, I will introduce conditions of rationality for uncertain doxastic states represented by ordered pairs.     

Reasoning Continuously: A Formal Construction of Continuous Proofs

We begin with the idea that lines of reasoning are continuous mental processes and develop a notion of continuity in proof. This requires abstracting the notion of a proof as a set of sentences ordered by provability. We can then distinguish between discrete steps of a proof and possibly continuous stages, defining indexing functions to pick these out. Proof stages can be associated with the application of continuously variable rules, connecting continuity in lines of reasoning with continuously variable reasons. Some examples of continuous proofs are provided. We conclude by presenting some fundamental facts about continuous proofs, analogous to continuous structural rules and composition. We take this to be a development on its own, as well as lending support to non-finitistic constructionism.

     

Synthesizing partial orders given comparability information: Partitive sets and slack in critical path networks

A problem which arises in the analysis of reaction times is considered. Suppose a task requires the completion of a set of mental activities which can be represented as a partially ordered set of arcs in a critical path network, but the network is unknown. If one knows for every pair of activities whether the pair is comparable (i.e., sequential) or incomparable (i.e., concurrent), then a partial order for the activities can be constructed with a procedure known as the transitive orientation algorithm. It is known that only two partial orders are possible, one the converse of the other, unless some proper nonsingleton partitive subset of the activities is not stable. Two main results are presented: First, a set of arcs generating a weakly connected subnetwork is partitive if and only if the subnetwork has a unique source, a unique sink, and no vertex of attachment other than these. Second, a simple relationship between partitive sets of activities and the slack between comparable activities is presented. These issues are important for the uniqueness problem in the synthesis of critical path networks representing cognitive tasks.     

Partial Monotonic Protothetics

This paper has four parts. In the first part, I present Leniewski's protothetics and the complete system provided for that logic by Henkin. The second part presents a generalized notion of partial functions in propositional type theory. In the third part, these partial functions are used to define partial interpretations for protothetics. Finally, I present in the fourth part a complete system for partial protothetics. Completeness is proved by Henkin's method [4] using saturated sets instead of maximally saturated sets. This technique provides a canonical representation of a partial semantic space and it is suggested that this space can be interpreted as an epistemic state of a non-omniscient agent.     

Probabilities on Sentences in an Expressive Logic

Automated reasoning about uncertain knowledge has many applications. One difficulty when developing such systems is the lack of a completely satisfactory integration of logic and probability. We address this problem directly. Expressive languages like higher-order logic are ideally suited for representing and reasoning about structured knowledge. Uncertain knowledge can be modeled by using graded probabilities rather than binary truth values. The main technical problem studied in this paper is the following: Given a set of sentences, each having some probability of being true, what probability should be ascribed to other (query) sentences? A natural wish-list, among others, is that the probability distribution (i) is consistent with the knowledge base, (ii) allows for a consistent inference procedure and in particular (iii) reduces to deductive logic in the limit of probabilities being 0 and 1, (iv) allows (Bayesian) inductive reasoning and (v) learning in the limit and in particular (vi) allows confirmation of universally quantified hypotheses/sentences. We translate this wish-list into technical requirements for a prior probability and show that probabilities satisfying all our criteria exist. We also give explicit constructions and several general characterizations of probabilities that satisfy some or all of the criteria and various (counter)examples. We also derive necessary and sufficient conditions for extending beliefs about finitely many sentences to suitable probabilities over all sentences, and in particular least dogmatic or least biased ones. We conclude with a brief outlook on how the developed theory might be used and approximated in autonomous reasoning agents. Our theory is a step towards a globally consistent and empirically satisfactory unification of probability and logic.     

中外两种推理理论的实验比较研究

通过两个实验对中国学者提出的“推理题与推理者的推理知识双重结构模型”和Evans提出的“双重加工理论”进行了实验比较研究。实验一通过两种评定方法对相应性质命题进行评定后所得实验结果表明Evans等(1983)有关“信念效应”研究中的“结论可信性”变量可以视为与胡竹菁等(1996)实验中的“内容正确性”变量是同一性质的变量; 实验二根据“形式正确性”和“内容正确性”两个自变量设计的推理实验结果与Evans等(1983)的研究结果基本一致; 但增加“内容熟悉性”这一自变量设计的推理实验结果表明“推理题与推理者的推理知识双重结构模型”比Evans提出的“双重加工理论”能更好地解释推理者对性质三段论的推理结果。     

Coherent choice functions under uncertainty

We discuss several features of coherent choice functions—where the admissible options in a decision problem are exactly those that maximize expected utility for some probability/utility pair in fixed set S of probability/utility pairs. In this paper we consider, primarily, normal form decision problems under uncertainty—where only the probability component of S is indeterminate and utility for two privileged outcomes is determinate. Coherent choice distinguishes between each pair of sets of probabilities regardless the “shape” or “connectedness” of the sets of probabilities. We axiomatize the theory of choice functions and show these axioms are necessary for coherence. The axioms are sufficient for coherence using a set of probability/almost-state-independent utility pairs. We give sufficient conditions when a choice function satisfying our axioms is represented by a set of probability/state-independent utility pairs with a common utility.     

Conditionals,Context, and the Suppression Effect

Modus ponens is the argument from premises of the form If A, then B and A to the conclusion B (e.g., from If it rained, Alicia got wet and It rained to Alicia got wet). Nearly all participants agree that the modus ponens conclusion logically follows when the argument appears in this Basic form. However, adding a further premise (e.g., If she forgot her umbrella, Alicia got wet) can lower participants’ rate of agreement—an effect called suppression. We propose a theory of suppression that draws on contemporary ideas about conditional sentences in linguistics and philosophy. Semantically, the theory assumes that people interpret an indicative conditional as a context‐sensitive strict conditional: true if and only if its consequent is true in each of a contextually determined set of situations in which its antecedent is true. Pragmatically, the theory claims that context changes in response to new assertions, including new conditional premises. Thus, the conclusion of a modus ponens argument may no longer be accepted in the changed context. Psychologically, the theory describes people as capable of reasoning about broad classes of possible situations, ordered by typicality, without having to reason about individual possible worlds. The theory accounts for the main suppression phenomena, and it generates some novel predictions that new experiments confirm.     

Definedness

Questions of definedness are ubiquitous in mathematics. Informally, these involve reasoning about expressions which may or may not have a value. This paper surveys work on logics in which such reasoning can be carried out directly, especially in computational contexts. It begins with a general logic of partial terms, continues with partial combinatory and lambda calculi, and concludes with an expressively rich theory of partial functions and polymorphic types, where termination of functional programs can be established in a natural way.Lecture for mini-conference on Partial Functions and Programming: Foundational Questions, U.C. Irvine, 17 February 1995. I wish to thank Professor Karel Lambert for his work in organizing this conference. (Research supported by grants from the N.S.F.)     

Conditionals: a theory of meaning,pragmatics, and inference

The authors outline a theory of conditionals of the form If A then C and If A then possibly C. The 2 sorts of conditional have separate core meanings that refer to sets of possibilities. Knowledge, pragmatics, and semantics can modulate these meanings. Modulation can add information about temporal and other relations between antecedent and consequent. It can also prevent the construction of possibilities to yield 10 distinct sets of possibilities to which conditionals can refer. The mental representation of a conditional normally makes explicit only the possibilities in which its antecedent is true, yielding other possibilities implicitly. Reasoners tend to focus on the explicit possibilities. The theory predicts the major phenomena of understanding and reasoning with conditionals.     

Reasoning About Social Choice Functions

We introduce a logic specifically designed to support reasoning about social choice functions. The logic includes operators to capture strategic ability, and operators to capture agent preferences. We establish a correspondence between formulae in the logic and properties of social choice functions, and show that the logic is expressively complete with respect to social choice functions, i.e., that every social choice function can be characterised as a formula of the logic. We prove that the logic is decidable, and give a complete axiomatization. To demonstrate the value of the logic, we show in particular how it can be applied to the problem of determining whether a social choice function is strategy-proof.     

Simultaneous Rigid Sorted Unification for Tableaux

In this paper we integrate a sorted unification calculus into free variable tableau methods for logics with term declarations. The calculus we define is used to close a tableau at once, unifying a set of equations derived from pairs of potentially complementary literals occurring in its branches. Apart from making the deduction system sound and complete, the calculus is terminating and so, it can be used as a decision procedure. In this sense we have separated the complexity of sorts from the undecidability of first order logic.     

Uncertainty, credal sets and second order probability

The last 20 years or so has seen an intense search carried out within Dempster–Shafer theory, with the aim of finding a generalization of the Shannon entropy for belief functions. In that time, there has also been much progress made in credal set theory—another generalization of the traditional Bayesian epistemic representation—albeit not in this particular area. In credal set theory, sets of probability functions are utilized to represent the epistemic state of rational agents instead of the single probability function of traditional Bayesian theory. The Shannon entropy has been shown to uniquely capture certain highly intuitive properties of uncertainty, and can thus be considered a measure of that quantity. This article presents two measures developed with the purpose of generalizing the Shannon entropy for (1) unordered convex credal sets and (2) possibly non-convex credal sets ordered by second order probability, thereby providing uncertainty measures for such epistemic representations. There is also a comparison with the results of the measure AU developed within Dempster–Shafer theory in a few instances where unordered convex credal set theory and Dempster–Shafer theory overlap.     

A Purely Recombinatorial Puzzle

A new puzzle of modal recombination is presented which relies purely on resources of first‐order modal logic. It shows that naive recombinatorial reasoning, which has previously been shown to be inconsistent with various assumptions concerning propositions, sets and classes, leads to inconsistency by itself. The context sensitivity of modal expressions is suggested as the source of the puzzle, and it is argued that it gives us reason to reconsider the assumption that the notion of metaphysical necessity is in good standing.