Disjunction property and complexity of substructural logics

We systematically identify a large class of substructural logics that satisfy the disjunction property (DP), and show that every consistent substructural logic with the DP is PSPACE-hard. Our results are obtained by using algebraic techniques. PSPACE-completeness for many of these logics is furthermore established by proof theoretic arguments.     

On Resolving Conflicts Between Arguments

Argument systems are based on the idea that one can construct arguments for propositions—structured reasons justifying the belief in a proposition. Using defeasible rules, arguments need not be valid in all circumstances, therefore, it might be possible to construct an argument for a proposition as well as its negation. When arguments support conflicting propositions, one of the arguments must be defeated, which raises the question of which (sub‐) arguments can be subject to defeat. In legal argumentation, metarules determine the valid arguments by considering the last defeasible rule of each argument involved in a conflict. Since it is easier to evaluate arguments using their last rules, can a conflict be resolved by considering only the last defeasible rules of the arguments involved? We propose a new argument system where, instead of deriving a defeat relation between arguments, arguments for the defeat of defeasible rules are constructed. This system allows us to determine a set of valid (undefeated) arguments in linear time using an algorithm based on a JTMS, allows conflicts to be resolved using only the last rules of the arguments, allows us to establish a relation with Default Logic, and allows closure properties such as cumulativity to be proved. We propose an extension of the argument system based on a proposal for reasoning by cases in default logic.     

A theory of legal reasoning and a logic to match

This paper describes a model of legal reasoning and a logic for reasoning with rules, principles and goals that is especially suited to this model of legal reasoning. The paper consists of three parts. The first part describes a model of legal reasoning based on a two-layered view of the law. The first layer consists of principles and goals that express fundamental ideas of a legal system. The second layer contains legal rules which in a sense summarise the outcome of the interaction of the principles and goals for a number of case types. Both principles, goals and rules can be used in legal arguments, but their logical roles are different. One characteristic of the model of legal reasoning described in the first part of the paper is that it takes these logical differences into account. Another characteristic is that it pays serious attention to the phenomena of reasoning about the validity and acceptance of rules, respectively principles and goals, and about the application of legal rules, and the implications of these arguments for the use of rules, principles and goals in deriving legal conclusions for concrete cases.The second part of the paper first describes a logic (Reason-Based Logic) that is especially suited to deal with legal arguments as described in terms of the previously discussed model. The facilities of the logic are illustrated by means of examples that correspond to the several aspects of the model.The third part of the paper deals with a number of logico-philosophical reflections on Reason-Based Logic. The occasion is also used to compare these presuppositions with theories of defeasible reasoning based on the comparison of arguments.The ideas developed in this paper are based on the draft of my book Reasoning with rules which will be published by Kluwer Academic Publishers in the Law and Philosophy Series. The book offers not only more elaborate and sometimes different treatments of the topics of this paper, but also pays more attention to the philosophical background of this work.     

复合模糊命题中基于弱逻辑的拟三角模算子研究

修正了f范数的概念,指出了符合弱逻辑关系的算子实际上是一种拟三角模算子中的Uninorm算子,接着给出了严格弱逻辑关系的拟三角模算子概念,在提出概念时,考虑了多维、基于单一数值和基于区间值以及加权的情况,并证明了符合弱逻辑关系的连续拟三角模算子是不存在的;给出了弱逻辑拟三角模算子的具体形式,给出了具体的四类弱逻辑关系的拟三角模算子,讨论了它们的性质,并进行了比较;定义了评价算子的边缘性测度和敏感性测度,对各算子进行了对比和评价.结果表明,文中给出的弱逻辑拟三角模算子可以在不同应用背景下,有效地处理不同类型的复合模糊命题真值运算,也可以在其它的模糊系统中有效处理多个模糊子集之间的聚集运算.     

基于直觉模糊逻辑的近似推理方法

针对直觉模糊逻辑及命题演算，提出了利用隶属度和犹豫度计算直觉模糊逻辑命题真值的合成方法．给出了直觉模糊逻辑命题的运算规则，重点研究了基于直觉模糊逻辑的近似推理方法．该方法包括直觉模糊取式推理，直觉模糊拒武推理及直觉模糊假官推理．井推导了相关的推理合成运算公式．以具体算例验证和表明了所提出的推导方法的正确性和有效性，以及对方法进行验证的详细步骤．     

Dialectic proof procedures for assumption-based, admissible argumentation

We present a family of dialectic proof procedures for the admissibility semantics of assumption-based argumentation. These proof procedures are defined for any conventional logic formulated as a collection of inference rules and show how any such logic can be extended to a dialectic argumentation system.The proof procedures find a set of assumptions, to defend a given belief, by starting from an initial set of assumptions that supports an argument for the belief and adding defending assumptions incrementally to counter-attack all attacks.The proof procedures share the same notion of winning strategy for a dispute and differ only in the search strategy they use for finding it. The novelty of our approach lies mainly in its use of backward reasoning to construct arguments and potential arguments, and the fact that the proponent and opponent can attack one another before an argument is completed. The definition of winning strategy can be implemented directly as a non-deterministic program, whose search strategy implements the search for defences.     

Partial information basis for agent-based collaborative dialogue

We propose a partial information state-based framework for collaborative dialogue and argument between agents. We employ a three-valued based nonmonotonic logic, NML3, for representing and reasoning about Partial Information States (PIS). NML3 formalizes some aspects of revisable reasoning and it is sound and complete. Within the framework of NML3, we present a formalization of some basic dialogue moves and the rules of protocols of some types of dialogue. The rules of a protocol are nonmonotonic in the sense that the set of propositions to which an agent is committed and the validity of moves vary from one move to another. The use of PIS allows an agent to expand consistently its viewpoint with some of the propositions to which another agent, involved in a dialogue, is overtly committed. A proof method for the logic NML3 has been successfully implemented as an automatic theorem prover. We show, via some examples, that the tableau method employed to implement the theorem prover allows an agent, absolute access to every stage of a proof process. This access is useful for constructive argumentation and for finding cooperative and/or informative answers.     

A Matrix Characterization for Multiplicative Exponential Linear Logic

We develop a matrix characterization of logical validity in MELL, the multiplicative fragment of propositional linear logic with exponentials and constants. To prove the correctness and completeness of our characterization, we use a purely proof-theoretical justification rather than semantical arguments. Our characterization is based on concepts similar to matrix characterizations proposed by Wallen for other nonclassical logics. It provides a foundation for developing proof search procedures for MELL by adopting techniques that are based on these concepts and also makes it possible to adopt algorithms that translate the machine-found proofs back into the usual sequent calculus for MELL.     

On judgment aggregation in abstract argumentation

Judgment aggregation is a field in which individuals are required to vote for or against a certain decision (the conclusion) while providing reasons for their choice. The reasons and the conclusion are logically connected propositions. The problem is how a collective judgment on logically interconnected propositions can be defined from individual judgments on the same propositions. It turns out that, despite the fact that the individuals are logically consistent, the aggregation of their judgments may lead to an inconsistent group outcome, where the reasons do not support the conclusion. However, in this paper we claim that collective irrationality should not be the only worry of judgment aggregation. For example, judgment aggregation would not reject a consistent combination of reasons and conclusion that no member voted for. In our view this may not be a desirable solution. This motivates our research about when a social outcome is ‘compatible’ with the individuals’ judgments. The key notion that we want to capture is that any individual member has to be able to defend the collective decision. This is guaranteed when the group outcome is compatible with its members views. Judgment aggregation problems are usually studied using classical propositional logic. However, for our analysis we use an argumentation approach to judgment aggregation problems. Indeed the question of how individual evaluations can be combined into a collective one can also be addressed in abstract argumentation. We introduce three aggregation operators that satisfy the condition above, and we offer two definitions of compatibility. Not only does our proposal satisfy a good number of standard judgment aggregation postulates, but it also avoids the problem of individual members of a group having to become committed to a group judgment that is in conflict with their own individual positions.     

Unnatural Language Processing

Computer-based logic proofs are a form of unnatural language in which the process and structure of proof generation can be observed in considerable detail. We have been studying how students respond to multimodal logic teaching, and performance measures have already indicated that students' pre-existing cognitive styles have a significant impact on teaching outcome. Furthermore, a large corpus of proofs has been gathered via automatic logging of proof development. This paper applies a series of techniques, including corpus statistical methods, to the proof logs. The results indicate that students' cognitive styles influence the structure of their logical discourse, via their differing methods of handling abstract information in diagrams, and transferring information between modalities.     

Using bisimulation proof techniques for the analysis of distributed abstract machines

We illustrate the use of recently developed proof techniques for weak bisimulation by analysing a generic framework for the definition of distributed abstract machines based on a message-passing implementation. We first define this framework, and then focus on the algorithm which is used to route messages asynchronously to their destination.A first version of this algorithm can be analysed using the standard bisimulation up to expansion proof technique. We show that in a second, optimised version, rather complex behaviours appear, for which more sophisticated techniques, relying on termination arguments, are necessary to establish behavioural equivalence.     

Theorem Proving Modulo

Deduction modulo is a way to remove computational arguments from proofs by reasoning modulo a congruence on propositions. Such a technique, issued from automated theorem proving, is of general interest because it permits one to separate computations and deductions in a clean way. The first contribution of this paper is to define a sequent calculus modulo that gives a proof-theoretic account of the combination of computations and deductions. The congruence on propositions is handled through rewrite rules and equational axioms. Rewrite rules apply to terms but also directly to atomic propositions. The second contribution is to give a complete proof search method, called extended narrowing and resolution (ENAR), for theorem proving modulo such congruences. The completeness of this method is proved with respect to provability in sequent calculus modulo. An important application is that higher-order logic can be presented as a theory in deduction modulo. Applying the ENAR method to this presentation of higher-order logic subsumes full higher-order resolution. This revised version was published online in August 2006 with corrections to the Cover Date.     

Toward Automating the Discovery of Decreasing Measures

An often neglected part of proof automation is simply admitting recursive function definitions into a constructive logic. Since function termination in general is undecidable, current generation theorem provers are quick to involve the human. There is, however, a substantial subset of the class of recursive functions for which termination arguments can be provided automatically. In particular, when the ordinal measure used to justify termination is less than , we provide algorithms and proofs that guarantee optimum results, given the capability of existing proof libraries on the theorem-proving system.     

Abstract argumentation

In this paper we explore the thesis that the role of argumentation in practical reasoning in general and legal reasoning in particular is to justify the use of defeasible rules to derive a conclusion in preference to the use of other defeasible rules to derive a conflicting conclusion. The defeasibility of rules is expressed by means of non-provability claims as additional conditions of the rules.We outline an abstract approach to defeasible reasoning and argumentation which includes many existing formalisms, including default logic, extended logic programming, non-monotonic modal logic and auto-epistemic logic, as special cases. We show, in particular, that the admissibility semantics for all these formalisms has a natural argumentation-theoretic interpretation and proof procedure, which seem to correspond well with informal argumentation.In the admissibility semantics there is only one way for one argument to attack another, namely by undermining one of its non-provability claims. In this paper, we show how other kinds of attack between arguments, specifically how rebuttal and priority attacks, can be reduced to the undermining of non-provability claims.     

Using coalgebras and the Giry monad for interpreting game logics — a tutorial

The stochastic interpretation of Parikh’s game logic should not follow the usual pattern of Kripke models, which in turn are based on the Kleisli morphisms for the Giry monad, rather, a specific and more general approach to probabilistic nondeterminism is required.We outline this approach together with its probabilistic and measure theoretic basis, introducing in a leisurely pace the Giry monad and its Kleisli morphisms together with important techniques for manipulating them. Proof establishing specific techniques are given, and pointers to the extant literature are provided.After working through this tutorial, the reader should find it easier to follow the original literature in this and related areas, and it should be possible for her or him to appreciate measure theoretic arguments for original work in the areas of Markov transition systems, and stochastic effectivity functions.     

On the logic of preference and judgment aggregation

Agents that must reach agreements with other agents need to reason about how their preferences, judgments, and beliefs might be aggregated with those of others by the social choice mechanisms that govern their interactions. The emerging field of judgment aggregation studies aggregation from a logical perspective, and considers how multiple sets of logical formulae can be aggregated to a single consistent set. As a special case, judgment aggregation can be seen to subsume classical preference aggregation. We present a modal logic that is intended to support reasoning about judgment aggregation scenarios (and hence, as a special case, about preference aggregation): the logical language is interpreted directly in judgment aggregation rules. We present a sound and complete axiomatisation. We show that the logic can express aggregation rules such as majority voting; rule properties such as independence; and results such as the discursive paradox, Arrow’s theorem and Condorcet’s paradox—which are derivable as formal theorems of the logic. The logic is parameterised in such a way that it can be used as a general framework for comparing the logical properties of different types of aggregation—including classical preference aggregation. As a case study we present a logical study of, including a formal proof of, the neutrality lemma, the main ingredient in a well-known proof of Arrow’s theorem.     

A GENERALIZED VIEW OF NONMONOTONIC KNOWLEDGE: A SET OF THEORETIC PERSPECTIVE

We provide a set theoretic framework for looking at the classical logical inference problem. We then introduce within this framework a new class of propositions, called second order propositions, which provide a prototypical characterization of nonmonotonic type default knowledge. We study the properties of this new class of propositions.     

一种新的辩论推理模式及其应用

文中定义了一个新的辩论推理模式,建立了一个形式化的知识表示框架,并把它应用于研究扩展逻辑程序类的说明语义,结果表明,新语义克服了择优语义的不足。作者还根据上述研究结果实现了逻辑程序设计风格下的知识框架。     

What You Always Wanted to Know about Rigid E-Unification

This paper solves an open problem posed by a number of researchers: the construction of a complete calculus for matrix-based methods with rigid E-unification. The use of rigid E-unification and simultaneous rigid E-unification for such methods was proposed by Gallier et al., in 1987. After our proof of the undecidability of simultaneous rigid E-unification in 1995. (Degtyarev and Voronkov, 1996d), it became clear that one should look for more refined techniques to deal with equality in matrix-based methods. In this article, we define a complete proof procedure for first-order logic with equality based on an incomplete but terminating procedure for rigid E-unification. Our approach is applicable to the connection method and the tableau method and is illustrated on the tableau method.