Two results in negation-free logic

Negation-free propositional logic (or first-order logic) is clearly less expressive than the corresponding full system with negation. However, we present two complexity results for logic without negation that are no different from those for the original system. First, the problem of determining logical implication between sentences composed solely of conjunctions and disjunctions is shown to be as difficult as that between arbitrary sentences. Second, we show that the problem of determining a minimum satisfying assignment for a propositional formula in negation-free conjunctive normal form, even with no more than two disjuncts per clause, is NP-complete. We also show that unless P = NP, no polynomial time approximation scheme can exist for this problem.     

A simple logic for reasoning about incomplete knowledge

The semantics of modal logics for reasoning about belief or knowledge is often described in terms of accessibility relations, which is too expressive to account for mere epistemic states of an agent. This paper proposes a simple logic whose atoms express epistemic attitudes about formulae expressed in another basic propositional language, and that allows for conjunctions, disjunctions and negations of belief or knowledge statements. It allows an agent to reason about what is known about the beliefs held by another agent. This simple epistemic logic borrows its syntax and axioms from the modal logic KD. It uses only a fragment of the S5 language, which makes it a two-tiered propositional logic rather than as an extension thereof. Its semantics is given in terms of epistemic states understood as subsets of mutually exclusive propositional interpretations. Our approach offers a logical grounding to uncertainty theories like possibility theory and belief functions. In fact, we define the most basic logic for possibility theory as shown by a completeness proof that does not rely on accessibility relations.     

An Infinitary Graded Modal Logic (Graded Modalities VI)

We prove a completeness theorem for K, the infinitary extension of the graded version K⁰ of the minimal normal logic K, allowing conjunctions and disjunctions of countable sets of formulas. This goal is achieved using both the usual tools of the normal logics with graded modalities and the machinery of the predicate infinitary logics in a version adapted to modal logic.     

Logical regularities in pattern recognition (Parametric Approach)

The search for logical regularities of classes in the recognition by precedents problems and the use of logical regularities for solving recognition and prediction problems are considered. Logical regularities of classes are defined as conjunctions of one-place predicates that determine the membership of a value of a feature in a certain interval of the real axis. The conjunctions are true on the subsets of reference objects of a certain class and are optimal. Various optimality criteria are considered and the problem of finding logical regularities is formulated as an integer programming problem. A qualitative analysis of these problems is performed. Models for evaluating estimates on the basis of systems of logical regularities are considered. Modifications of linear decision rules for finding estimates of how close the reference objects are to classes are proposed that are based on the search for the maximum gap. Approximations of logical regularities of classes by smooth functions is proposed. The concept of the dynamic logical regularity of classes is introduced, an algorithm for finding dynamic logical regularities is proposed, and a prediction method is developed.     

Algorithms for finding logical regularities in pattern recognition

Three algorithms for finding logical regularities of classes in the precedent-based recognition problem are proposed. Logical regularities of classes are defined as conjunctions of special oneplace predicates that determine the membership of a value of a feature in a certain interval of the real axis. The conjunctions are true on as large subsets of reference objects of a certain class as possible. The problem of finding logical regularities is formulated as a special integer programming problem. Relaxation, genetic, and combinatorial algorithms are proposed for solving this problem. Comparison results for these algorithms using model and real-time problems are presented. Comparison results for various estimate evaluation recognition algorithms that use logical regularities of classes in voting procedures are also presented.     

Generalized resolution and cutting planes

This paper illustrates how the application of integer programming to logic can reveal parallels between logic and mathematics and lead to new algorithms for inference in knowledge-based systems. If logical clauses (stating that at least one of a set of literals is true) are written as inequalities, then the resolvent of two clauses corresponds to a certain cutting plane in integer programming. By properly enlarging the class of cutting planes to cover clauses that state that at least a specified number of literals are true, we obtain a generalization of resolution that involves both cancellation-type and circulant-type sums. We show its completeness by proving that it generates all prime implications, generalizing an early result by Quine. This leads to a cutting-plane algorithm as well as a generalized resolution algorithm for checking whether a set of propositions, perhaps representing a knowledge base, logically implies a given proposition. The paper is intended to be readable by persons with either an operations research or an artificial intelligence background.This report was prepared as part of the activities of the Management Sciences Research Group, Carnegie-Mellon University. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.     

Infinitary S5-Epistemic Logic

It is known that a theory in S5-epistemic logic with several agents may have numerous models. This is because each such model specifies also what an agent knows about infinite intersections of events, while the expressive power of the logic is limited to finite conjunctions of formulas. We show that this asymmetry between syntax and semantics persists also when infinite conjunctions (up to some given cardinality) are permitted in the language. We develop a strengthened S5-axiomatic system for such infinitary logics, and prove a strong completeness theorem for them. Then we show that in every such logic there is always a theory with more than one model.     

Asymptotic estimates for the number of solutions of the dualization problem and its generalizations

Asymptotic estimates for the typical number of irreducible coverings and the typical length of an irreducible covering of a Boolean matrix are obtained in the case when the number of rows is no less than the number of columns. As a consequence, asymptotic estimates are obtained for the typical number of maximal conjunctions and the typical rank of a maximal conjunction of a monotone Boolean function of variables defined by a conjunctive normal form of clauses. Similar estimates are given for the number of irredundant coverings and the length of an irredundant covering of an integer matrix (for the number of maximal conjunctions and the rank of a maximal conjunction of a two-valued logical function defined by its zero set). Results obtained previously in this area are overviewed.     

A study of lattice reformulations for integer programming

Branch-and-bound for integer optimization typically uses single-variable disjunctions. Enumerative methods for integer optimization with theoretical guarantees use a non-binary search tree with general disjunctions based on lattice structure. These disjunctions are expensive to compute and challenging to implement. Here we compare two lattice reformulations that can be used to heuristically obtain general disjunctions in the original space, we develop a new lattice-based variant, and compare the derived disjunctions computationally with those produced by the algorithm of Lovász and Scarf.     

分布逻辑的理论与分析

以往的逻辑理论讨论的是理论上命题之间的逻辑关系,作为一种基本准则,可以放在许多情况下使用,但是一般的逻辑理论相对抽象,命题形式过于简单,这样有时不能很准确很方便地处理实际问题,在传统数学中,分布是一种重要的思想,基于这种思想建立了分布逻辑理论,同时对命题值在分布结构上的真假以及变化进行了讨论。     

What is a Logic Translation?

We study logic translations from an abstract perspective, without any commitment to the structure of sentences and the nature of logical entailment, which also means that we cover both proof- theoretic and model-theoretic entailment. We show how logic translations induce notions of logical expressiveness, consistency strength and sublogic, leading to an explanation of paradoxes that have been described in the literature. Connectives and quantifiers, although not present in the definition of logic and logic translation, can be recovered by their abstract properties and are preserved and reflected by translations under suitable conditions. In memoriam Joseph Goguen     

Separation logic and logics with team semantics

Separation logic is a successful logical system for formal reasoning about programs that mutate their data structures. Team semantics, on the other side, is the basis of modern logics of dependence and independence. Separation logic and team semantics have been introduced with quite different motivations, and are investigated by research communities with rather different backgrounds and objectives. Nevertheless, there are obvious similarities between these formalisms. Both separation logic and logics with team semantics involve the manipulation of second-order objects, such as heaps and teams, by first-order syntax without reference to second-order variables. Moreover, these semantical objects are closely related; it is for instance obvious that a heap can be seen as a team, and the separating conjunction of separation logic is (essentially) the same as the team-semantical disjunction. Based on such similarities, the possible connections between separation logic and team semantics have been raised as a question at several occasions, and lead to informal discussions between these research communities. The objective of this paper is to make this connection precise, and to study its potential but also its obstacles and limitations.     

Piaget's Logic of Meanings: Still Relevant Today

In his last book, Toward a Logic of Meanings ( Piaget & Garcia, 1991 ), Jean Piaget describes how thought can be categorized into a form of propositional logic, a logic of meanings. The intent of this article is to offer this analysis by Piaget as a means to understand the language and teaching of science. Using binary propositions, conjunctions, and disjunctions, a table of binary operations is used to analyze the structure of statements about conclusions drawn from observations of science phenomena. Two examples from science content illustrate how the logic of binary propositions is used to symbolize typical reasoning of secondary‐school science students. The content areas are the period of a pendulum and the Archimedes' Principle, which were chosen based on observations in secondary science classrooms. The analyses of the student responses in these two observations demonstrate the commonalities of arguments used by students of science as they try to make sense of observations. The analysis of students' reasoning, demonstrates that Piaget's logic of meanings is a useful and relevant tool for science educators' understanding of the syntactical aspects of pedagogical content knowledge.     

Complexity of fuzzy answer set programming under Łukasiewicz semantics

Fuzzy answer set programming (FASP) is a generalization of answer set programming (ASP) in which propositions are allowed to be graded. Little is known about the computational complexity of FASP and almost no techniques are available to compute the answer sets of a FASP program. In this paper, we analyze the computational complexity of FASP under Łukasiewicz semantics. In particular we show that the complexity of the main reasoning tasks is located at the first level of the polynomial hierarchy, even for disjunctive FASP programs for which reasoning is classically located at the second level. Moreover, we show a reduction from reasoning with such FASP programs to bilevel linear programming, thus opening the door to practical applications. For definite FASP programs we can show P-membership. Surprisingly, when allowing disjunctions to occur in the body of rules – a syntactic generalization which does not affect the expressivity of ASP in the classical case – the picture changes drastically. In particular, reasoning tasks are then located at the second level of the polynomial hierarchy, while for simple FASP programs, we can only show that the unique answer set can be found in pseudo-polynomial time. Moreover, the connection to an existing open problem about integer equations suggests that the problem of fully characterizing the complexity of FASP in this more general setting is not likely to have an easy solution.     

Leveraging Structure: Logical Necessity in the Context of Integer Arithmetic

Looking for, recognizing, and using underlying mathematical structure is an important aspect of mathematical reasoning. We explore the use of mathematical structure in children’s integer strategies by developing and exemplifying the construct of logical necessity. Students in our study used logical necessity to approach and use numbers in a formal, algebraic way, leveraging key mathematical ideas about inverses, the structure of our number system, and fundamental properties. We identified the use of carefully chosen comparisons as a key feature of logical necessity and documented three types of comparisons students made when solving integer tasks. We believe that logical necessity can be applied in various mathematical domains to support students to successfully engage with mathematical structure across the K–12 curriculum.     

模型论逻辑与理论计算机科学

近年来，逻辑中语义的思想与方法在理论计算机科学的许多分支中的渗透与应用，已愈来愈受重视．作为语义方法的逻辑基础，（一阶）模型论是研究（一阶）逻辑的语法构造与语义属性之间联系的一门数理逻辑的分支；而模型论逻辑（又称广义模型论）则是在抽象逻辑的框架中，用模型论的方法研究各种扩充逻辑系统的异、同及相互关系．本文从抽象逻辑的观点出发．介绍模型论中与计算机科学（ＣＳ）密切相关的若干概念及其应用．特别是广义的有限模型论，它在ＣＳ的刺激下于８０年代形成并急速发展起来，已在数据库、计算复杂性以及形式语言与自动机等理论中取得突出成果或重大的应用．     

Enumerating disjunctions and conjunctions of paths and cuts in reliability theory

Let G=(V,E) be a (directed) graph with vertex set V and edge (arc) set E. Given a set P of source-sink pairs of vertices of G, an important problem that arises in the computation of network reliability is the enumeration of minimal subsets of edges (arcs) that connect/disconnect all/at least one of the given source-sink pairs of P. For undirected graphs, we show that the enumeration problems for conjunctions of paths and disjunctions of cuts can be solved in incremental polynomial time. Furthermore, under the assumption that P consists of all pairs within a given vertex set, we also give incremental polynomial time algorithm for enumerating all minimal path disjunctions and cut conjunctions. For directed graphs, the enumeration problem for cut disjunction is known to be NP-complete. We extend this result to path conjunctions and path disjunctions, leaving open the complexity of the enumeration of cut conjunctions. Finally, we give a polynomial delay algorithm for enumerating all minimal sets of arcs connecting two given nodes s₁ and s₂ to, respectively, a given vertex t₁, and each vertex of a given subset of vertices T₂.     

Logic and Natural Selection

Is logic, feasibly, a product of natural selection? In this paper we treat this question as dependent upon the prior question of where logic is founded. After excluding other possibilities, we conclude that logic resides in our language, in the shape of inferential rules governing the logical vocabulary of the language. This means that knowledge of (the laws of) logic is inseparable from the possession of the logical constants they govern. In this sense, logic may be seen as a product of natural selection: the emergence of logic requires the development of creatures who can wield structured languages of a specific complexity, and who are capable of putting the languages to use within specific discursive practices.     

中介命题演算系统$MP^{M}$的代数系统

MP~M系统是在中介逻辑系统的基础上建立起来的,用于处理数据库中不完全信息的三值逻辑命题演算系统．本文通过在MP~M系统上建立一个代数系统,对MP~M系统进行了代数抽象,讨论了MP~M系统的代数性质．本文还研究了该代数系统的次直积,以及与其它一些代数系统之间的关系．     

A case study in logical deconstruction: Formalizing J.D. Thompson's Organizations in Action in a multi-agent action logic

Logic is a popular word in the social sciences, but it is rarely used as a formal tool. In the past, the logical formalisms were cumbersome and difficult to apply to domains of purposeful action. Recent years, however, have seen the advance of new logics specially designed for representing actions. We present such a logic and apply it to a classical organization theory, J.D. Thompson's Organizations in Action. The working hypothesis is that formal logic draws attention to some finer points in the logical structure of a theory, points that are easily neglected in the discursive reasoning typical for the social sciences. Examining Organizations in Action we find various problems in its logical structure that should, and, as we argue, could be addressed.