Investigating Reasoning with Constraint Diagrams

Constraint diagrams are a visual notation designed to express logical constraints. Augmenting the diagrams with a reading tree (effectively a partial ordering of quantifiers) ensures that each diagram has a unique semantic interpretation.In this paper, we discuss examples of reasoning rules for augmented constraint diagrams which exhibit interesting properties or difficulties that can arise when developing rules for such a diagrammatic system. We do not present a complete set of rules, but investigate the generic problems arising, providing solutions. One problem corresponds to the nesting of quantifiers and another relates to the domain of universal quantification. These issues may be an important consideration in the definition of other logical reasoning systems which explicitly represent quantification diagrammatically.     

On the expressiveness of second-order spider diagrams

Existing diagrammatic notations based on Euler diagrams are mostly limited in expressiveness to monadic first-order logic with an order predicate. The most expressive monadic diagrammatic notation is known as spider diagrams of order. A primary contribution of this paper is to develop and formalise a second-order diagrammatic logic, called second-order spider diagrams, extending spider diagrams of order. A motivation for this lies in the limited expressiveness of first-order logics. They are incapable of defining a variety of common properties, like ‘is even’, which are second-order definable. We show that second-order spider diagrams are at least as expressive as monadic second-order logic. This result is proved by giving a method for constructing a second-order spider diagram for any regular expression. Since monadic second-order logic sentences and regular expressions are equivalent in expressive power, this shows second-order spider diagrams can express any sentence of monadic second-order logic.     

Strategy Analysis of Non-consequence Inference with Euler Diagrams

How can Euler diagrams support non-consequence inferences? Although an inference to non-consequence, in which people are asked to judge whether no valid conclusion can be drawn from the given premises (e.g., All B are A; No C are B), is one of the two sides of logical inference, it has received remarkably little attention in research on human diagrammatic reasoning; how diagrams are really manipulated for such inferences remains unclear. We hypothesized that people naturally make these inferences by enumerating possible diagrams, based on the logical notion of self-consistency, in which every (simple) Euler diagram is true (satisfiable) in a set-theoretical interpretation. The work is divided into three parts, each exploring a particular condition or scenario. In condition 1, we asked participants to directly manipulate diagrams with size-fixed circles as they solved syllogistic tasks, with the result that more reasoners used the enumeration strategy. In condition 2, another type of size-fixed diagram was used. The diagram layout change interfered with accurate task performances and with the use of the enumeration strategy; however, the enumeration strategy was still dominant for those who could correctly perform the tasks. In condition 3, we used size-scalable diagrams (with the default size as in condition 2), which reduced the interfering effect of diagram layout and enhanced participants’ selection of the enumeration strategy. These results provide evidence that non-consequence inferences can be achieved by diagram enumeration, exploiting the self-consistency of Euler diagrams. An alternate strategy based on counter-example construction with Euler diagrams, as well as effects of diagram layout in inferential processes, are also discussed.     

Nautilus, a Concurrent Diagrammatic Specification and Programming Language

Nautilus is a high-level specification and programming language having abstraction mechanisms not commonly found in other programming languages inspired by its semantic domain (a categorial model named Nonsequential Automata). It constitutes an elegant solution for concurrency and non-determinism as well as for synchronization of concurrent systems. The role as specification language highlights the diagrammatic syntax (it was originally text based).The diagrammatic syntax for Nautilus allows complete programs to be written using symbols and graphical diagrams. The graphical notation was elaborated in order to be able to express all the structures in the language, yet trying to improve the visualization of written programs. A brief comparison with UML is included. To support Nautilus as a programming language, a mapping to Java is constructed, setting the basis for an execution environment of Nautilus specifications.     

A Diagrammatic Inference System with Euler Circles

Proof-theory has traditionally been developed based on linguistic (symbolic) representations of logical proofs. Recently, however, logical reasoning based on diagrammatic or graphical representations has been investigated by logicians. Euler diagrams were introduced in the eighteenth century. But it is quite recent (more precisely, in the 1990s) that logicians started to study them from a formal logical viewpoint. We propose a novel approach to the formalization of Euler diagrammatic reasoning, in which diagrams are defined not in terms of regions as in the standard approach, but in terms of topological relations between diagrammatic objects. We formalize the unification rule, which plays a central role in Euler diagrammatic reasoning, in a style of natural deduction. We prove the soundness and completeness theorems with respect to a formal set-theoretical semantics. We also investigate structure of diagrammatic proofs and prove a normal form theorem.     

Towards explaining the cognitive efficacy of Euler diagrams in syllogistic reasoning: A relational perspective

Although diagrams have been widely used as methods for introducing students to elementary logical reasoning, it is still open to debate in cognitive psychology whether logic diagrams can aid untrained people to successfully conduct deductive reasoning. In our previous work, some empirical evidence was provided for the effectiveness of Euler diagrams in the process of solving categorical syllogisms. In this paper, we discuss the question of why Euler diagrams have such inferential efficacy in the light of a logical and proof-theoretical analysis of categorical syllogisms and diagrammatic reasoning. As a step towards an explanatory theory of reasoning with Euler diagrams, we argue that the effectiveness of Euler diagrams in supporting syllogistic reasoning derives from the fact that they are effective ways of representing and reasoning about relational structures that are implicit in categorical sentences. A special attention is paid to how Euler diagrams can facilitate the task of checking the invalidity of an inference, a task that is known to be particularly difficult for untrained reasoners. The distinctive features of our conception of diagrammatic reasoning are made clear by comparing it with the model-theoretic conception of ordinary reasoning developed in the mental model theory.     

Nesting in Euler Diagrams

This paper outlines the notion of nesting in Euler diagrams, and how nesting affects the interpretation and construction of such diagrams. After setting up the necessary definitions for Euler diagrams at concrete syntax and abstract levels, the notion of nestedness is introduced at the concrete level, then an equivalent notion is given at the abstract level. The natural progression to the diagram semantics is explored. In the final sections, we describe how this work supports tool-building for diagrams, and how effective we might expect this support to be in terms of the proportion of nested diagrams.     

Propositional Logic Constraint Patterns and Their Use in UML-Based Conceptual Modeling and Analysis

An important conceptual modeling activity in the development of database, object-oriented and agent-oriented systems is the capture and expression of domain constraints governing underlying data and object states. UML is increasingly used for capturing conceptual models, as it supports conceptual modeling of arbitrary domains, and has extensible notation allowing capture of invariant constraints both in the class diagram notation and in the separately denoted OCL syntax. However, a need exists for increased formalism in constraint capture that does not sacrifice ease of use for the analyst. In this paper, we codify a set of invariant patterns formalized for capturing a rich category of propositional constraints on class diagrams. We use tools of Boolean logic to set out the distinction between these patterns, applying them in modeling by way of example. We use graph notation to systematically uncover constraints hidden in the diagrams. We present data collected from applications across different domains, supporting the importance of "pattern-finding" for n-variable propositional constraints using general graph theoretic methods. This approach enriches UML-based conceptual modeling for greater completeness, consistency, and correctness by formalizing the syntax and semantics of these constraint patterns, which has not been done in a comprehensive manner before now     

Graphical notations for syllogisms: How alternative representations impact the accessibility of concepts

Five notations for standard and multi-premise syllogisms are examined. Four are existing notations (verbal propositions, Euler diagrams, Venn diagrams and Englebretsen's Linear diagrams) and one a novel diagrammatic system – Category Pattern Diagrams (CPDs). CPDs integrate spatial location, linear ordering and properties of graphical objects in a comprehensive representational format to encode information about syllogisms, which provides a contrast to the use of degrees of spatial containment in the existing diagrammatic systems. The comparison of the five notations reveals how their underlying representational schemes can substantially impact the effectiveness of the encoding of the core concepts of the knowledge domain; in particular whether the core domain concepts are readily accessible as perceptual inferences and thus the notations are semantically transparent. The relative merits of CPDs provide some support for claims about the utility of the Representational Epistemic design principles that were used to create CPDs.     

Prolegomena to a Cognitive Investigation of Euclidean Diagrammatic Reasoning

Euclidean diagrammatic reasoning refers to the diagrammatic inferential practice that originated in the geometrical proofs of Euclid’s Elements. A seminal philosophical analysis of this practice by Manders (‘The Euclidean diagram’, 2008) has revealed that a systematic method of reasoning underlies the use of diagrams in Euclid’s proofs, leading in turn to a logical analysis aiming to capture this method formally via proof systems. The central premise of this paper is that our understanding of Euclidean diagrammatic reasoning can be fruitfully advanced by confronting these logical and philosophical analyses with the field of cognitive science. Surprisingly, central aspects of the philosophical and logical analyses resonate in very natural ways with research topics in mathematical cognition, spatial cognition and the psychology of reasoning. The paper develops these connections, concentrating on four issues: (1) the cognitive origins of Euclidean diagrammatic reasoning, (2) the cognitive representations of spatial relations in Euclidean diagrams, (3) the nature of the cognitive processes and cognitive representations involved in Euclidean diagrammatic reasoning seen as a form of visuospatial relational reasoning and (4) the complexity of Euclidean diagrammatic reasoning for the human cognitive system. For each of these issues, our analysis generates concrete experiment proposals, opening thereby the way for further empirical investigations. The paper is thus a prolegomenon to a research program on Euclidean diagrammatic reasoning at the crossroads of logic, philosophy and cognitive science.     

一种面向图形化建模语言表示法的元模型

对于图形化的建模语言,为定义其表示法一般需要解决3个问题:如何定义每个建模元素的图形符号,如何定义图形符号之间的位置关系以及如何将表示法映射到抽象语法.为了方便进行模型转换和代码生成,还需要使用模型化的方式描述建模语言的表示法.通过对UML及其语言家族中的表示法进行总结、分析和归纳,提出了一种表示法定义元模型(notation definition metamodel,简称NDM).针对定义表示法所面临的3个问题,NDM被分成基本图元及其布局、基本位置关系和抽象语法桥三部分.使用NDM定义好的表示法模型还可以通过代码生成技术生成可使用的源代码.将NDM与其他几种定义表示法的方法进行了比较,结果表明,NDM与其他方法相比具有优势.NDM已经在元建模工具PKU MetaModeler中实现.介绍了NDM在实际应用中的几个案例.     

Specification Diagrams for Actor Systems

Specification diagrams (SD's) are a novel form of graphical notation for specifying open distributed object systems. The design goal is to define notation for specifying message-passing behavior that is expressive, intuitively understandable, and that has formal semantic underpinnings. The notation generalizes informal notations such as UML's Sequence Diagrams and broadens their applicability to later in the design cycle. Specification diagrams differ from existing actor and process algebra presentations in that they are not executable per se; instead, like logics, they are inherently more biased toward specification. In this paper we rigorously define the language syntax and semantics and give examples that show the expressiveness of the language, how properties of specifications may be asserted diagrammatically, and how it is possible to reason rigorously and modularly about specification diagrams.     

From control law diagrams to Ada via Circus

Control engineers make extensive use of diagrammatic notations; control law diagrams are used in industry every day. Techniques and tools for analysis of these diagrams or their models are plentiful, but verification of their implementations is a challenge that has been taken up by few. We are aware only of approaches that rely on automatic code generation, which is not enough assurance for certification, and often not adequate when tailored hardware components are used. Our work is based on Circus, a notation that combines Z, CSP, and a refinement calculus, and on industrial tools that produce partial Z and CSP models of discrete-time Simulink diagrams. We present a strategy to translate Simulink diagrams to Circus, and a strategy to prove that a parallel Ada implementation refines the Circus specification; we rely on a Circus semantics for the program. By using a combined notation, we provide a specification that considers both functional and behavioural aspects of a large set of diagrams, and support verification of a large number of implementations. We can handle, for instance, arbitrarily large data types and dynamic scheduling.     

Nesting in Euler Diagrams: syntax,semantics and construction

This paper considers the notion of nesting in Euler diagrams, and how nesting affects the interpretation and construction of such diagrams. After setting up the necessary definitions for concrete Euler diagrams (drawn in the plane) and abstract diagrams (having just formal structure), the notion of nestedness is defined at both concrete and abstract levels. The concept of a dual graph is used to give an alternative condition for a drawable abstract Euler diagram to be nested. The natural progression to the diagram semantics is explored and we present a nested form for diagram semantics. We describe how this work supports tool-building for diagrams, and how effective we might expect this support to be in terms of the proportion of nested diagrams.     

Refactoring OCL annotated UML class diagrams

Refactoring of UML class diagrams is an emerging research topic and heavily inspired by refactoring of program code written in object-oriented implementation languages. Current class diagram refactoring techniques concentrate on the diagrammatic part but neglect OCL constraints that might become syntactically incorrect by changing the underlying class diagram. This paper formalizes the most important refactoring rules for class diagrams and classifies them with respect to their impact on attached OCL constraints. For refactoring rules that have an impact on OCL constraints, we formalize the necessary changes of the attached constraints. Our refactoring rules are specified in a graph-grammar inspired formalism. They have been implemented as QVT transformation rules. We finally discuss for our refactoring rules the problem of syntax preservation and show, by using the KeY-system, how this can be resolved.     

Aligning Logical and Psychological Perspectives on Diagrammatic Reasoning

We advance a theoretical framework which combines recent insights of research in logic, psychology, and formal semantics, on the nature of diagrammatic representation and reasoning. In particular, we wish to explain the varied efficacy of reasoning and representing with diagrams. In general we consider diagrammatic representations to be restricted in expressive power, and we wish to explain efficacy of reasoning with diagrams via the semantical and computational properties of such restricted `languages'. Connecting these foundational insights (from semantics and complexity theory) to the psychology of reasoning with diagrams requires us to develop the notion of the availability (to an agent) of constraints operating within representation systems, as a consequence of their direct semanticinterpretation. Thus we offer a number of fundamentaldefinitions as well as a research programme which alignscurrent efforts in the logical and psychological analysis ofdiagrammatic representation systems.