Search

We identify the (filter representation of the) logic behind the recent theory of coherent sets of desirable (sets of) things, which generalise coherent sets of desirable (sets of) gambles as well as coherent choice functions, and show that this identification allows us to establish various representation results for such coherent models in terms of simpler ones. • We identify the (filter representation of the) logic behind the recent theory of coherent sets of desirable (sets of) things. • We represent coherent sets of desirable sets of things in terms of collections of coherent sets of desirable things. • We identify two interesting special cases: uncertainty modelling using choice functions, and classical propositional logic. [ABSTRACT FROM AUTHOR]

A novel inference approach is presented based on knowledge Petri nets and resolution rules. First, a knowledge base is modeled as a knowledge Petri net, where logical clauses are represented by monitor places, called semantic places. Second, a resolution pair is defined to identify a pair of semantic places, which, corresponding to two clauses that can be resolved, can be used to generate a new place in the knowledge Petri net. Such a new place represents an unknown clause implied by the knowledge base. Third, a method is proposed to decide whether a resolution inference is redundant based on the resolution pair. The size of a knowledge Petri net can be reduced, and the inference computation is saved in this way. Fourth, an inference algorithm is proposed employing the resolution pair and knowledge Petri net, proven to be sound and complete. Its computational complexity is polynomial with respect to the number of logical variables and clauses. In addition, another inference algorithm is developed for a given complete knowledge base and a set of newfound clauses. The algorithm is proven to be sound and complete, which offers significantly reduced computational complexity and specifically is linear concerning the number of new clauses. Finally, the wumpus world problem is taken as an example to illustrate and verify the proposed inference algorithms. [ABSTRACT FROM AUTHOR]

Various neural network architectures rely on pooling operators to aggregate information coming from different sources. It is often implicitly assumed in such contexts that vectors encode epistemic states, i.e. that vectors capture the evidence that has been obtained about some properties of interest, and that pooling these vectors yields a vector that combines this evidence. We study, for a number of standard pooling operators, under what conditions they are compatible with this idea, which we call the epistemic pooling principle. While we find that all the considered pooling operators can satisfy the epistemic pooling principle, this only holds when embeddings are sufficiently high-dimensional and, for most pooling operators, when the embeddings satisfy particular constraints (e.g. having non-negative coordinates). We furthermore show that these constraints have important implications on how the embeddings can be used in practice. In particular, we find that when the epistemic pooling principle is satisfied, in most cases it is impossible to verify the satisfaction of propositional formulas using linear scoring functions, with two exceptions: (i) max-pooling with embeddings that are upper-bounded and (ii) Hadamard pooling with non-negative embeddings. This finding helps to clarify, among others, why Graph Neural Networks sometimes under-perform in reasoning tasks. Finally, we also study an extension of the epistemic pooling principle to weighted epistemic states, which are important in the context of non-monotonic reasoning, where max-pooling emerges as the most suitable operator. [ABSTRACT FROM AUTHOR]

The contradiction separation (CS) based automated deduction is an extension of the binary resolution principle for deductive inference rules, whose CSE prover and combined versions have unique performance among others in CADE ATP system competitions since their first appearances in 2018. The contradictions constructing method is one of the most important factors to determine the efficiency of the CS based deduction, which is more complex compared to the complementary pair finding in the binary resolution. To get structures and concrete forms of contradictions, this paper examines two types of standard contradictions, i.e., the regular standard contradictions and the standard contradictions for non-unit clauses sets. The concepts of the regular standard contradiction and its extended form are presented. Some properties of them are discussed. In order to get simpler contradiction separation clauses in every deductive step, four types of structures for standard contradictions obtained by adding related literals in the regular standard contradiction and its extended form are gotten. Two structures for the standard contradictions for non-unit clauses set are obtained. Two unified algorithms for constructing standard contradictions are also contrived. [ABSTRACT FROM AUTHOR]

Resolution as a famous rule of inference has played a key role in automated reasoning for over five decades. A number of variants and refinements of resolution have been also studied, essentially, they are all based on binary resolution, that is, the cutting rule of the complementary pair while every deduction involves only two clauses. In the present work, we consider an extension of binary resolution rule, which is proposed as a novel contradiction separation based inference rule for automated deduction, targeted for dynamic and multiple (two or more) clauses handling in a synergized way, while binary resolution is its special case. This contradiction separation based dynamic multi-clause synergized automated deduction theory is then proved to be sound and complete. The development of this new extension is motivated not only by our view to show that such a new rule of inference can be generic, but also by our wish that this inference rule could provide a basis for more efficient automated deduction algorithms and systems. [ABSTRACT FROM AUTHOR]

Quantifying conflicts is recognized as an important issue for handling inconsistencies. Indeed, an inconsistency measure can be employed to support knowledge engineers in building a consistent and usable knowledge base or providing insights on how to repair an inconsistent one. Good measures are supposed to satisfy a set of rational properties. However, defining sound properties is sometimes problematic. In this paper, we emphasize one such property, named dominance , rarely satisfied by syntactic measures. Based on prime implicates canonical representation, we first introduce the notion of conflicting variable and use it to refine an existing inconsistency measure defined by minimally unsatisfiable sets (MUSes). Then, we provide a semantics characterization allowing us to establish relationships with multi-valued semantics. Secondly, we propose a new measure based on the notion of deduced MUSes (DMUSes), to circumscribe the internal conflicts in a given knowledge base. We also prove that this measure satisfies a new but weaker form of dominance. Finally, we show how inconsistency measures based on hitting sets of minimal inconsistent sets can be extended using hitting sets of DMUSes. [ABSTRACT FROM AUTHOR]

There have been a number of proposals for measuring inconsistency in a knowledgebase (i.e. a set of logical formulae). These include measures that consider the minimally inconsistent subsets of the knowledgebase, and measures that consider the paraconsistent models (3 or 4 valued models) of the knowledgebase. In this paper, we present a new approach that considers the amount by which each formula has to be weakened in order for the knowledgebase to be consistent. This approach is based on ideas of knowledge merging by Konienczny and Pino-Perez. We show that this approach gives us measures that are different from existing measures, that have desirable properties, and that can take the significance of inconsistencies into account. The latter is useful when we want to differentiate between inconsistencies that have minor significance from inconsistencies that have major significance. We also show how our measures are potentially useful in applications such as evaluating violations of integrity constraints in databases and for deciding how to act on inconsistency. [ABSTRACT FROM AUTHOR]

A credal network associates a directed acyclic graph with a collection of sets of probability measures. Usually these probability measures are specified by tables containing probability values. Here we examine the complexity of inference in credal networks when probability measures are specified through formal languages. We focus on logical languages based on propositional logic and on the function-free fragment of first-order logic. We show that sub-Boolean and relational logics lead to interesting complexity results. In short, we explore the relationship between specification language and computational complexity in credal networks. [ABSTRACT FROM AUTHOR]

For the obstacle avoidance problem of space robots，a mixed integer predictive controller is developed for the free-floating space robots. Firstly, in the frame of model predictive control method, the joint physical limits and obstacle avoidance requirement are described as inequality constraints of the optimal control problem，and the controller with linear quadratic programming form can be obtained. Secondly，priorities of the constraints in the controller are established based on the prepositional logic theory to guarantee the optimal solution to be derived under the satisfaction of the maximum number of constraints，which effectively makes up for the deficiency issue that multiple constraints may lead to the optimal control problem infeasible when model predictive control method is used to control space robots. Finally, numerical simulations are conducted to prove the effectiveness of the proposed control strategy. [ABSTRACT FROM AUTHOR]

When looking for a propositional abductive explanation of a given set of manifestations, an ordering between possible solutions is often assumed. While the complexity of computing optimal solutions is already known, in this paper we consider second-best solutions with respect to different orderings, and different definitions of what a second-best solution is: an optimal solution not already found, or a solution that is optimal among the ones not previously found. [ABSTRACT FROM AUTHOR]

Abstract: This paper studies the relations which exist between Dempster–Shafer Theory and one of its extensions which considers frames of discernment with non-exclusive hypotheses. More precisely, we use propositional logic to show that this extension can be reformulated in the classical framework of Dempster–Shafer theory, showing that, even if it allows to manipulate more compact expressions, it is not more expressive. Finally, we believe that using propositional logic as the basics for modelling concepts in Dempster–Shafer Theory can help logicians to understand this theory and its extension to non-exclusive hypotheses. [Copyright &y& Elsevier]