Reflection of Long Game Formulas

We study game formulas the truth of which is determined by a semantical game of uncountable length. The main theme is the study of principles stating reflection of these formulas in various admissible sets. This investigation leads to two weak forms of strict-II¹₁ reflection (or ∑₁-compactness). We show that admissible sets such as H(ω₂) and L_ω2 which fail to have strict-II¹₁ reflection, may or may not, depending on set-theoretic hypotheses satisfy one or both of these weaker forms. Mathematics Subject Classification : 03C70, 03C75.     

Some model theory for monotone quantifiers

A generalization of the existential and universal quantifier, the monotone quantifiers, are studied. It is shown that the model theory for monotone quantifiers behaves very much like classical model theory. Completeness theorems, definability theorems and preservation theorems are given. Ultraproducts, reduced products and Back and Forth arguments are studied.This work is part of the research program of the G.N.S.A.G. group of the Italian C.N.R.     

Degrees of logics with Henkin quantifiers in poor vocabularies

We investigate some logics with Henkin quantifiers. For a given logic L, we consider questions of the form: what is the degree of the set of L–tautologies in a poor vocabulary (monadic or empty)? We prove that the set of tautologies of the logic with all Henkin quantifiers in empty vocabulary L* is of degree 0. We show that the same holds also for some weaker logics like L(H) and L(E). We show that each logic of the form L^(k)(Q), with the number of variables restricted to k, is decidable. Nevertheless – following the argument of M. Mostowski from [Mos89] – for each reasonable set theory no concrete algorithm can provably decide L^(k)(Q), for some (Q). We improve also some results related to undecidability and expressibility for logics L(H₄) and L(F₂) of Krynicki and M. Mostowski from [KM92].Mathematics Subject Classification (2000): 03C80, 03D35, 03B25Revised version: 28 August 2003     

A fuzzy-stochastic OWA model for robust multi-criteria decision making

All realistic Multi-Criteria Decision Making (MCDM) problems face various kinds of uncertainty. Since the evaluations of alternatives with respect to the criteria are uncertain they will be assumed to have stochastic nature. To obtain the uncertain optimism degree of the decision maker fuzzy linguistic quantifiers will be used. Then a new approach for fuzzy-stochastic modeling of MCDM problems will be introduced by merging the stochastic and fuzzy approaches into the OWA operator. The results of the new approach, entitled FSOWA, give the expected value and the variance of the combined goodness measure for each alternative. Robust decision depends on the combined goodness measures of alternatives and also on the variations of these measures under uncertainty. In order to combine these two characteristics a composite goodness measure will be defined. The theoretical results will be illustrated in a watershed management problem. By using this measure will give more sensitive decisions to the stakeholders whose optimism degrees are different than that of the decision maker. FSOWA can be used for robust decision making on the competitive alternatives under uncertainty.     

CUT ELIMINATION FOR PROPOSITIONAL DYNAMIC LOGIC WITHOUT

The aim of this paper is to extend the semantic analysis of tense logic in Rescher/Urquhart [3] to propositional dynamic logic without*. For this we develop a nested sequential calculus whose axioms and rules directly reflect the steps in the semantic analysis. It is shown that this calculus, with the cut rule omitted, is complete with respect to the standard semantics. It follows that cut elimination does hold for this nested sequential calculus. MSC: 03B45.     

Boole代数上的度量结构及其在命题逻辑中的应用

设B是一个Boole代数, Ω是从B到Boole代数{0,1}的全体同态之集,μ是Ω上的概率测度.本文基于μ在B中引入了元素的尺寸概念以及元素对之间的相似度概念,并由此在B上建立了度量结构.作为应用,本文改进了新近提出的命题逻辑中的近似推理理论.     

命题逻辑公式的压缩表示及其相应的形式系统

提出一种将命题逻辑公式压缩表示的方法--公式的压缩图,给出相应的形式系统,并证明该系统的证明效率比传统相继式演算系统Gentzen\{cut}有指数级的提高,从而为命题逻辑提供了一种新的有效的推理系统.     

扰动模糊命题逻辑系统中的广义重言式

通过定义二维R0-蕴涵算子，将王国俊教授在逻辑系统形中的广义重言式理论推广并应用到二维赋值的扰动模糊命题逻辑系统西中，证明了这一系统中（μ，δ）-重言式就是某个（λ，1-λ）-重言式，最终获得与一维线性赋值格上完全相应的广义重言式分类。     

The effect of structural branching on the efficiency of clause learning SAT solving: An experimental study

The techniques for making decisions (branching) play a central role in complete methods for solving structured instances of propositional satisfiability (SAT). Experimental case studies in specific problem domains have shown that in some cases SAT solvers can determine satisfiability faster if branching in the solver is restricted to a subset of the variables at hand. The underlying idea in these approaches is to prune the search space substantially by restricting branching to strong backdoor sets of variables which guarantee completeness of the search. In this paper we present an extensive experimental evaluation of the effects of structure-based branching restrictions on the efficiency of solving structural SAT instances. Previous work is extended in a number of ways. We study state-of-the-art solver techniques, including clause learning and related heuristics. We provide a thorough analysis of the effect of branching restrictions on the inner workings of the solver, going deeper than merely measuring the solution time. Extending previous studies which have focused on input-restricted branching, we also consider relaxed branching restrictions that are based on underlying structural properties of the variables.