This modern, advanced textbook reviews modal logic, a field which caught the attention of computer scientists in the late 1970's.

Peirce introduced Existential Graphs in late 1896, and they were systematically investigated in his 1903 Lowell Lectures. Alpha graphs for classical propositional logic constitute the first part of EGs. The second and the third parts are the beta graphs for first-order logic and the gamma graphs for modal and higher-order logics, among others. As a logical syntax, EGs are two-dimensional graphs, or diagrams, in contrast to the linear algebraic notations. Peirce's theory of EGs is (...) not only a theory of logical syntax but also a proof theory for many logics. A set of transformation rules of graphs defines a proof system for a graphical logic. In this... (shrink)

It is well-known that by 1882, Peirce, influenced by Cayley’s, Clifford’s and Sylvester’s works on algebraic invariants and by the chemical analogy, had already achieved something like a diagrammatic treatment of quantificational logic of relatives. The details of that discovery and its implications to some wider issues in logical theory merit further investigation, however. This paper provides a reconstruction of the genesis of Peirce’s logical graphs from the early 1880s until 1896, covering the period of time during (...) which he already was acquainted with the works of his Johns Hopkins colleagues on the mathematical theory of graphs and was reaching the very first forms of his theory and method of... (shrink)

We prove that every monadic second-order property of the unfolding of a transition system is a monadic second-order property of the system itself. An unfolding is an instance of the general notion of graph covering. We consider two more instances of this notion. A similar result is possible for one of them but not for the other.

Graph games are interactive scenarios with a wide range of applications. This position paper discusses old and new graph games in tandem with matching logics and identifies general questions behind this match. Throughout, we pursue two strands: logic as a way of analyzing existing graph games, and logic as an inspiration for designing new graph games. Our aim is modest: we propose a perspective that complements existing game-theoretic and computational ones, we raise questions, make observations, and suggest research directions—technical results (...) are left to future work. But frankly, our main aim with this survey paper is to show that graph games are concrete, fun, easy to grasp, and yet challenging to study. (shrink)

A graph-theoretic account of fibring of logics is developed, capitalizing on the interleaving characteristics of fibring at the linguistic, semantic and proof levels. Fibring of two signatures is seen as a multi-graph (m-graph) where the nodes and the m-edges include the sorts and the constructors of the signatures at hand. Fibring of two models is a multi-graph (m-graph) where the nodes and the m-edges are the values and the operations in the models, respectively. Fibring of two deductive systems is an (...) m-graph whose nodes are language expressions and the m-edges represent the inference rules of the two original systems. The sobriety of the approach is confirmed by proving that all the fibring notions are universal constructions. This graph-theoretic view is general enough to accommodate very different fibrings of propositional based logics encompassing logics with non-deterministic semantics, logics with an algebraic semantics, logics with partial semantics and substructural logics, among others. Soundness and weak completeness are proved to be preserved under very general conditions. Strong completeness is also shown to be preserved under tighter conditions. In this setting, the collapsing problem appearing in several combinations of logic systems can be avoided. (shrink)

This first volume of the Logic of the Future edition collects Peirce's writings on the historical development, theory and application of his graphical method and diagrammatic reasoning. Its 28 selections of texts and extensive general and volume int.

Peirce considered the principal business of logic to be the analysis of reasoning. He argued that the diagrammatic system of Existential Graphs, which he had invented in 1896, carries the logical analysis of reasoning to the furthest point possible. The present paper investigates the analytic virtues of the Alpha part of the system, which corresponds to the sentential calculus. We examine Peirce’s proposal that the relation of illation is the primitive relation of logic and defend the view that (...) this idea constitutes the fundamental motive of philosophy of notation both in algebraic and graphical logic. We explain how in his algebras and graphs Peirce arrived at a unifying notation for logical constants that represent both truth-function and scope. Finally, we show that Shin’s argument for multiple readings of Alpha graphs is circular. (shrink)

We describe Peirce’s 1903 system of modal gamma graphs, its transformation rules of inference, and the interpretation of the broken-cut modal operator. We show that Peirce proposed the normality rule in his gamma system. We then show how various normal modal logics arise from Peirce’s assumptions concerning the broken-cut notation. By developing an algebraic semantics we establish the completeness of fifteen modal logics of gamma graphs. We show that, besides logical necessity and possibility, Peirce proposed an epistemic (...) interpretation of the broken-cut modality, and that he was led to analyze constructions of knowledge in the style of epistemic logic. (shrink)

This paper examines the contemporary philosophical and cognitive relevance of Charles Peirce's diagrammatic logic of existential graphs (EGs), the ‘moving pictures of thought’. The first part brings to the fore some hitherto unknown details about the reception of EGs in the early 1900s that took place amidst the emergence of modern conceptions of symbolic logic. In the second part, philosophical aspects of EGs and their contributions to contemporary logical theory are pointed out, including the relationship between iconic logic (...) and images, the problem of the meaning of logical constants, the cognitive economy of iconic logic, the failure of the Frege–Russell thesis, and the failure of the Language of Thought hypothesis. (shrink)

The study of random graphs was begun in the 1960s and now has a comprehensive literature. This excellent book by one of the top researchers in the field now joins the study of random graphs (and other random discrete objects) with mathematical logic. The methodologies involve probability, discrete structures and logic, with an emphasis on discrete structures.

A graph-theoretic account of logics is explored based on the general notion of m-graph (that is, a graph where each edge can have a finite sequence of nodes as source). Signatures, interpretation structures and deduction systems are seen as m-graphs. After defining a category freely generated by a m-graph, formulas and expressions in general can be seen as morphisms. Moreover, derivations involving rule instantiation are also morphisms. Soundness and completeness theorems are proved. As a consequence of the generality of (...) the approach our results apply to very different logics encompassing, among others, substructural logics as well as logics with nondeterministic semantics, and subsume all logics endowed with an algebraic semantics. (shrink)

To Peirce scholars and other aficionados of logic, semiotics, and pragmatism, 2017 brought the great news of Bellucci’s Speculative Grammar book, providing the eye-opening first detailed chronological overview over Peirce’s career-length developing of his semiotics. Now, the first volume of Ahti Pietarinen’s long-awaited three-volume publication of the totality of Peirce’s writings on his mature logic representation system known as Existential Graphs not only gives us a plethora of hitherto unpublished Peirce papers but also a new and in many ways (...) surprising view into the origin and development of this important fruit of Peirce’s last, creative philosophical burst taking its beginning around 1896, famously to... (shrink)

The study of graph structure has advanced in recent years with great strides: finite graphs can be described algebraically, enabling them to be constructed out of more basic elements. Separately the properties of graphs can be studied in a logical language called monadic second-order logic. In this book, these two features of graph structure are brought together for the first time in a presentation that unifies and synthesizes research over the last 25 years. The author not only (...) provides a thorough description of the theory, but also details its applications, on the one hand to the construction of graph algorithms, and, on the other to the extension of formal language theory to finite graphs. Consequently the book will be of interest to graduate students and researchers in graph theory, finite model theory, formal language theory, and complexity theory. (shrink)

The logic of assertive graphs (AGs) is a modification of Peirce’s logic of existential graphs (EGs), which is intuitionistic and which takes assertions as its explicit object of study. In this paper we extend AGs into a classical graphical logic of assertions (ClAG) whose internal logic is classical. The characteristic feature is that both AGs and ClAG retain deep-inference rules of transformation. Unlike classical EGs, both AGs and ClAG can do so without explicitly introducing polarities of areas in (...) their language. We then compare advantages of these two graphical approaches to the logic of assertions with a reference to a number of topics in philosophy of logic and to their deep-inferential nature of proofs. (shrink)

We prove that a finitely generated group is context-free whenever its Cayley-graph has a decidable monadic second-order theory. Hence, by the seminal work of Muller and Schupp, our result gives a logical characterization of context-free groups and also proves a conjecture of Schupp. To derive this result, we investigate general graphs and show that a graph of bounded degree with a high degree of symmetry is context-free whenever its monadic second-order theory is decidable. Further, it is shown that (...) the word problem of a finitely generated group is decidable if and only if the first-order theory of its Cayley-graph is decidable. (shrink)

Graphs are among the most frequently used structures in Computer Science. Some of the properties that must be checked in many applications are connectivity, acyclicity and the Eulerian and Hamiltonian properties. In this work, we analyze how we can express these four properties with modal logics. This involves two issues: whether each of the modal languages under consideration has enough expressive power to describe these properties and how complex it is to use these logics to actually test whether a (...) given graph has some desired property. First, we show that these properties are not definable in a basic modal logic or in any bisimulation-invariant extension of it, like the modal μ-calculus. We then show that it is possible to express some of the above properties in a basic hybrid logic. Unfortunately, the Hamiltonian and Eulerian properties still cannot be efficiently checked. In a second attempt, we propose an extension of CTL* with nominals and show that the Hamiltonian property can be more efficiently checked in this logic than in the previous one. In a third attempt, we extend the basic hybrid logic with the ↓ operator and show that we can check the Hamiltonian property with optimal complexity in this logic. Finally, we tackle the Eulerian property in two different ways. First, we develop a generic method to express edge-related properties in hybrid logics and use it to express the Eulerian property. Second, we express a necessary and sufficient condition for the Eulerian property to hold using a graded modal logic. (shrink)

In 2001, Le Bars proved that there exists an existential monadic second-order sentence such that the probability that it is true on [Formula: see text] does not converge and conjectured that, for EMSO sentences with two first-order variables, the zero–one law holds. In this paper, we prove that the conjecture fails for [Formula: see text], and give new examples of sentences with fewer variables without convergence.

A case study of multimodal systems and a new interpretation of Charles S. Peirce's theory of reasoning and signs based on an analysis of his system of ...

In this paper a logical interpretation of semantic nets and graph grammars is proposed for modelling natural language understanding and creating language understanding computer systems. An example of parsing a Finnish question by graph grammars and inferring the answer to it by a semantic net representation is provided.

Although modern modal logic came about largely after Peirce’s death, he anticipated some of its key aspects, including strict implication and possible worlds semantics. He developed the Gamma part of Existential Graphs with broken cuts signifying possible falsity, but later identified the need for a Delta part without ever spelling out exactly what he had in mind. An entry in his personal Logic Notebook is a plausible candidate, with heavy lines representing possible states of things where propositions denoted by (...) attached letters would be true, rather than individual subjects to which predicates denoted by attached names are attributed as in the Beta part. New transformation rules implement various commonly employed formal systems of modal logic, which are readily interpreted by defining a possible world as one in which all the relevant laws for the actual world are facts, each world being partially but accurately and adequately described by a closed and consistent model set of propositions. In accordance with pragmaticism, the relevant laws for the actual world are represented as strict implications with real possibilities as their antecedents and conditional necessities as their consequents, corresponding to material implications in every possible world. (shrink)

Let L ω ∞ω be the infinitary language obtained from the first-order language of graphs by closure under conjunctions and disjunctions of arbitrary sets of formulas, provided only finitely many distinct variables occur among the formulas. Let p(n) be the edge probability of the random graph on n vertices. It is shown that if p(n) ≪ n -1 satisfies certain simple conditions on its growth rate, then for every σ∈ L ω ∞ω , the probability that σ holds for (...) the random graph on n vertices converges. In fact, if $p(n) = n^{-\alpha}, \alpha > 1$ , then the probability is either smaller than 2 -n d for some $d > 0$ , or it is asymptotic to cn -d for some $c > 0, d \geq 0$ . Results on the difficulty of computing the asymptotic probability are given. (shrink)

A clausal logic allowing to handle term-graphs is defined. Term-graphs are a generalization of terms (in the usual sense) possibly containing shared subterms and cycles. The satisfiability problem for this logic is shown to be undecidable (not even semi-decidable), but some fragments are identified for which it is semi-decidable. A complete (w.r.t validity) calculus for these fragments is proposed. Some simple examples give a taste of this calculus at work.

Charles S. Peirce’s pragmatist theory of logic teaches us to take the context of utterances as an indispensable logical notion without which there is no meaning. This is not a spat against compositionality per se , since it is possible to posit extra arguments to the meaning function that composes complex meaning. However, that method would be inappropriate for a realistic notion of the meaning of assertions. To accomplish a realistic notion of meaning (as opposed e.g. to algebraic meaning), (...) Sperber and Wilson’s Relevance Theory (RT) may be applied in the spirit of Peirce’s Pragmatic Maxim (PM): the weighing of information depends on (i) the practical consequences of accommodating the chosen piece of information introduced in communication, and (ii) what will ensue in actually using that piece in further cycles of discourse. Peirce’s unpublished papers suggest a relevance-like approach to meaning. Contextual features influenced his logic of Existential Graphs (EG). Arguments are presented pro and con the view in which EGs endorse non-compositionality of meaning. (shrink)

In every undirected graph or, more generally, in every undirected hypergraph of bounded rank, one can specify an orientation of the edges or hyperedges by monadic second-order formulas using quantifications on sets of edges or hyperedges. The proof uses an extension to hypergraphs of the classical notion of a depth-first spanning tree. Applications are given to the characterization of the classes of graphs and hypergraphs having decidable monadic theories.

Graph theory is a specific concept that has numerous applications throughout many industries. Despite the advancement of this technique, graph theory can still yield ambiguous and imprecise results. In order to cut down on these indeterminate factors, neutrosophic logic has emerged as an applicable solution that is gaining significant attention in solving many real-life decision-making problems that involve uncertainty, impreciseness, vagueness, incompleteness, inconsistency, and indeterminacy. However, empirical research on this specific graph set is lacking. Neutrosophic Graph Theory and Algorithms is (...) a collection of innovative research on the methods and applications of neutrosophic sets and logic within various fields including systems analysis, economics, and transportation. While highlighting topics including linear programming, decision-making methods, and homomorphism, this book is ideally designed for programmers, researchers, data scientists, mathematicians, designers, educators, researchers, academicians, and students seeking current research on the various methods and applications of graph theory. (shrink)

We show that there exist 2 ℵ 0 equational classes of Boolean algebras with operators that are not generated by the complex algebras of any first-order definable class of relational structures. Using a variant of this construction, we resolve a long-standing question of Fine, by exhibiting a bimodal logic that is valid in its canonical frames, but is not sound and complete for any first-order definable class of Kripke frames (a monomodal example can then be obtained using simulation results of (...) Thomason). The constructions use the result of Erd $\H{o}$ s that there are finite graphs with arbitrarily large chromatic number and girth. (shrink)

Topics covered in Discrete Mathematics have become essential tools in many areas of studies in recent years. This is primarily due to the revolution in technology, communications, and cyber security. The book treats major themes in a typical introductory modern Discrete Mathematics course: Propositional and predicate logic, proof techniques, set theory (including Boolean algebra, functions and relations), introduction to number theory, combinatorics and graph theory. An accessible, precise, and comprehensive approach is adopted in the treatment of each topic. The ability (...) of abstract thinking and the art of writing valid arguments are emphasized through detailed proof of (almost) every result. Developing the ability to think abstractly and roguishly is key in any areas of science, information technology and engineering. Every result presented in the book is followed by examples and applications to consolidate its comprehension. The hope is that the reader ends up developing both the abstract reasoning as well as acquiring practical skills. All efforts are made to write the book at a level accessible to first-year students and to present each topic in a way that facilitates self-directed learning. Each chapter starts with basic concepts of the subject at hand and progresses gradually to cover more ground on the subject. Chapters are divided into sections and subsections to facilitate readings. Each section ends with its own carefully chosen set of practice exercises to reenforce comprehension and to challenge and stimulate readers. As an introduction to Discrete Mathematics, the book is written with the smallest set of prerequisites possible. Familiarity with basic mathematical concepts (usually acquired in high school) is sufficient for most chapters. However, some mathematical maturity comes in handy to grasp some harder concepts presented in the book. (shrink)

Graphs are employed to define a variety of distance-based binary merging operators. We provide logical characterization results for each class of merging operators introduced and discuss the extension of this approach to the merging of sequences and multisets.

We introduce a framework for a graph-theoretic analysis of the semantic paradoxes. Similar frameworks have been recently developed for infinitary propositional languages by Cook and Rabern, Rabern, and Macauley. Our focus, however, will be on the language of first-order arithmetic augmented with a primitive truth predicate. Using Leitgeb’s notion of semantic dependence, we assign reference graphs (rfgs) to the sentences of this language and define a notion of paradoxicality in terms of acceptable decorations of rfgs with truth values. It (...) is shown that this notion of paradoxicality coincides with that of Kripke. In order to track down the structural components of an rfg that are responsible for paradoxicality, we show that any decoration can be obtained in a three-stage process: first, the rfg is unfolded into a tree, second, the tree is decorated with truth values (yielding a dependence tree in the sense of Yablo), and third, the decorated tree is re-collapsed onto the rfg. We show that paradoxicality enters the picture only at stage three. Due to this we can isolate two basic patterns necessary for paradoxicality. Moreover, we conjecture a solution to the characterization problem for dangerous rfgs that amounts to the claim that basically the Liar- and the Yablo graph are the only paradoxical rfgs. Furthermore, we develop signed rfgs that allow us to distinguish between ‘positive’ and ‘negative’ reference and obtain more fine-grained versions of our results for unsigned rfgs. (shrink)

Studies to neutrosophic graphs happens to be not only innovative and interesting, but gives a new dimension to graph theory. The classic coloring of edge problem happens to give various results. Neutrosophic tree will certainly find lots of applications in data mining when certain levels of indeterminacy is involved in the problem. Several open problems are suggested.

This erratum is to correct in the paper of Daniele Chiffi and Ahti-Veikko Pietarinen, On the Logical Philosophy of Assertive Graphs.

Using the programming-language concept of continuations, we propose a new, multimodal analysis of quantification in Type Logical Grammar. Our approach provides a geometric view of in-situ quantification in terms of graphs, and motivates the limited use of empty antecedents in derivations. Just as continuations are the tool of choice for reasoning about evaluation order and side effects in programming languages, our system provides a principled, type-logical way to model evaluation order and side effects in natural language. We (...) illustrate with an improved account of quantificational binding, weak crossover, wh-questions, superiority, and polarity licensing. (shrink)

In this paper, we analyze and discuss Schopenhauer’s n-term diagrams for eristic dialectics from a graph-theoretical perspective. Unlike logic, eristic dialectics does not examine the validity of an isolated argument, but the progression and persuasiveness of an argument in the context of a dialogue or even controversy. To represent these dialogue situations, Schopenhauer created large maps with concepts and Euler-type diagrams, which from today’s perspective are a specific form of graphs. We first present the original method with Euler-type diagrams, (...) then give the most important graph-theoretical definitions, then discuss Schopenhauer’s diagrams graph-theoretically and finally give an example of how the graphs or diagrams can be used to analyze dialogues. (shrink)

We investigate the definability in monadic ∑11 and monadic Π11 of the problems REGk, of whether there is a regular subgraph of degree k in some given graph, and XREGk, of whether, for a given rooted graph, there is a regular subgraph of degree k in which the root has degree k, and their restrictions to graphs in which every vertex has degree at most k, namely REGkk and XREGkk, respectively, for k ≥ 2 . Our motivation partly stems (...) from the fact that REGkk and XREGkk are logspace equivalent to CONN and REACH, respectively, for k ≥ 3, where CONN is the problem of whether a given graph is connected and REACH is the problem of whether a given graph has a path joining two given vertices. We use monadic first - order reductions, monadic ∑11 games and a recent technique due to Fagin, Stockmeyer and Vardi to almost completely classify whether these problems are definable in monadic ∑11 and monadic Π11, and we compare the definability of these problems. (shrink)

Review by: Achim Blumensath The Bulletin of Symbolic Logic, Volume 19, Issue 3, Page 394-396, September 2013.