The Expressiveness of Spider Diagrams

摘要

Spider diagrams are a visual language for expressing logical statements. In this paper we identify a well-known fragment of first-order predicate logic that we call MFOL_=, equivalent in expressive power to the spider diagram language. The language MFOL_= is monadic and includes equality but has no constants or function symbols. To show this equivalence, in one direction, for each diagram we construct a sentence in MFOL_= that expresses the same information. For the more challenging converse we prove that there exists a finite set of models for a sentence S that can be used to classify all the models for 5. Using these classifying models we show that there is a diagram expressing the same information as S.