可满足性问题的归约技术

通过一个恰当的归约变换,可以将一个CNF公式变换为另一个具有某种特殊结构或性质的公式,使其两者具有相同的可满足性。一个典型的归约是将一般的CNF公式变换为3．GVF公式。通过构造一些恰当的工具,可以将公式类变换为所要求的正则类。极小不可满足公式具有一个临界特征,公式本身不可满足,从原始公式中删去任意一个子句后得到的公式可满足。我们提供了一种归约技术,通过构造恰当的极小不可满足公式作为工具,将公式类变换为具有正则结构的公式类。研究正则结构的公式的复杂性及性质很有意义。如,将一个从3．CNF公式变换为（3,4）一CNF公式,这里（3,4）一CNF公式是指公式中每个子句的长度恰为3,每个变元出现的次数恰为4。因此,（3,4）．SAT是一个NP．完全问题,并且正N-部图的诸多良好性质对于研究正则结构的SAT问题具有许多潜在的作用。     

模态逻辑的集合论语义与互模拟不变性

含有命题变元的非良基集合能够被看作解释模态语言的模型。任给非良基集合a,一个命题变元p在a上真当且仅当p属于a。命题联结词的解释与古典命题逻辑相同。一个公式3A在a上真当且仅当存在集合b属于a,使得A在b上是真的。在一个集合中,属于关系被看作可及关系。在这种思想下,我们可以定义从模态语言到一阶集合论语言的标准翻译。对任意模态公式A和集合变元x,可以递归定义一阶集合论语言的公式ST(A,x)。在关系语义学下,van Benthem刻画定理是说,在带有唯一的二元关系符号R的一阶语言中,任何一阶公式等价于某个模态公式的标准翻译当且仅当这个一阶公式在互模拟下保持不变。因此,模态语言是该一阶关系语言的互模拟不变片段。同样,我们可以在集合上定义互模拟关系,证明van Benthem刻画定理对于集合论语义和集合上的互模拟不变片段成立,即模态语言是一阶集合论语言的集合互模拟不变片段。     

层次图(混合Horn)公式的部分极大可满足性

本文为解决一类混合Horn公式([13,14]),又称为层次图公式([15])的MAXSAT问题进行了基于随机局部搜索过程的经验研究。具体地,我们首先在随机CNF公式的MAX2SAT及MAX3SAT问题上进行WalkSAT和Tabu-Sat(及其变种)的比较,其次,我们在层次图公式上比较了上述过程的改进版本,这些公式编码了随机生成层次图的最小化跨边问题。本文所引入的Tabu-Sat过程,当在搜索空间中检测到一个圈的时候,动态地改变Tabu长度参数。另一个被称为Vector-Tabu-Sat的过程,对所有的布尔变元进行独立的Tabu长度参数管理。一些数值实验的结果显示,我们改进的Tabu-Sat变种在子句个数增长的时候优于Walksat.     

一个关于非直谓语句的逻辑系统

非直谓现象普遍存在于许多领域中。在数学中,对集合的最小元的定义是非直谓的。在逻辑中,罗素悖论的产生是由于允许非直谓地定义一个集合,即“所有不包含它自身的集合的集合”。莱布尼兹对“同一性”的定义——“a与b是相同实体当且仅当对所有性质f,如果f（a）则f（b）,反之亦然”——是非直谓的。罗素构造分歧类型论的动机不是来自形式系统的悖论,而是来自日常语言中的悖论。本文的目标是构造一文化景观命题逻辑来刻画关于特定的非直谓语句的推理。一个非直谓语句的表达预设了一个语句集,一个典型的非直谓语句是“拿破仑具备一名伟人将军的所有德性”（罗素的例子）。本文所关注的是“一阶”非直谓语句,即仅预设直谓语句集的非直谓语句。非直谓语句的一个性质是：一个非直谓语句等价于它所预设的语句集中的成员（可能无穷）的合取。这一性质需要在要构造的逻辑系统的句法中被表达出来,而针对此本文所采用的手段是在命题逻辑系统的符号中加入“命题量词”,也就是说本文要构造一个量化命题逻辑系统。在形式化部分,本文给出了这个逻辑的句法、语义、希尔伯特公理系统和它的完全性证明。     

偏好变化的一个量化模型

偏好是哲学、博弈论、决策论和效益理论等学科的核心概念,偏好及其逻辑性质在行为哲学和理性选择理论中尤其占有十分重要的地位。偏好的概念使得我们对世界的看法变得多姿多彩,它驱使着我们在尘世的种种行为选择。然而,偏好不是静止不变的,建议、命令、以及其他的信息不断改变着我们的偏好。近年来,逻辑学家们开始对偏好的改变进行深入的研究。到目前为止,关于偏好变化的模型主要有以下两种：第一、采取AGM理论研究偏好变化,给出变化的逻辑公设。第二、采用新近发展起来的动态认知逻辑的方法,对偏好的具体变化机制进行研究,给出动态偏好逻辑系统。无论是上面提到的哪种方法,都是采用定性的视角,即,偏好被表示成一个序关系。与此相反,本文采取量化的视角来研究偏好,利用偏好赋值函数给出偏好的量化语义。就逻辑语言而言,我们给出一个包括命题常元的新语言。这个语言既简练又富于表达力。基于这样的量化语义,处理偏好变化的方法就与以往的方法有所不同。根据经典的乘积更新的机制,我们提出了新的加法规则和一个参数化规则,来刻画偏好赋值的细微变化之处。同时,我们给出一个动态认知赋值逻辑,并证明其完全性。此外,我们还考虑道义逻辑最近的一些研究成果,表明本文给出的模型同样适用于道义的情境。特别是,这个新的模型能够解决困扰人们已久的义务冲突问题。最后,针对赋值偏好模型,我们定义了适用于它“赋值互模拟”。而且,我们还进一步给出了一个新的互模拟概念“距离互模拟”以结束本文。     

普遍命题和因果性

本文遵循信念指导我们的行动这一皮尔士观点,将基本信念描述为地图,而具有普遍内容的普遍信念则根本就不是命题,而是形成“说话者迎接未来的系统”的变形假言陈述。因果律是一种变形假言陈述,具有特殊的重要性和客观性。对于量化语句所表达的普遍信念,本文认为它们表达的是认知态度而非命题,从而明确支持了实用主义意义理论的核心论题。     

论模态逻辑的集合论语义

引入非良基集合可以为模态逻辑提供一种新的语义学。这种语义是在集合上解释模态语言,使用集合中作为元素的集合之间的属于关系解释模态词,并在集合中采用命题变元作为本元,从而解释原子命题的真假。在这种新的语义下,从模型构造的角度看可以引入几种非标准的集合运算：不交并、生成子集合、p-态射、树展开等等,证明模态公式在这些运算下的保持或不变结果。利用这些结果还可以证明一些集合类不是模态可定义的。     

《可能世界的名字》述评CSSCI

刘新文,祝瑞,可能世界的名字,2017年,北京:中国社会科学出版社混合逻辑(hybrid logic)是模态逻辑中一个十分活跃的分支,它为模态逻辑的许多经典结论都提供了良好的改进方法。混合逻辑的基本观点,即“对命题变元分类”和“词项用作公式”,来自于上世纪六十年代的逻辑学家普莱尔(A.Prior)在时态逻辑领域中所做的工作。     

概率语义与句子系统

本文讨论概率语义与句子系统的关系,我们考虑的概率语义分两种:句子型的语义和命题型的语义。令L0是由可数个句符和常用句子联结词构成的语言,令LL0是任意句子语言,即L还可以有(作用在句子上的)n元算子。我们用FL0和FL分别表示L0和L的所有句子的集合。令PC指称下列经典句子系统:PCFL0使得PC包含下列公理模式Ax1—Ax3且在推理规则MP下封闭:(Ax1)　A→A∧A;(Ax2)　A∧B→A;(Ax3)　(A→B)→((B∧C)→(C∧A));(MP)　A,A→BB。这里我们采用Rosser在1953年提出的、主要用∧和表述的系统,之所以这样做是因为下面的概率语义是相对…     

空名与虚构实体

本文论证了如下观点:第一,存在是个体的一个真正的谓词.尽管说每一样东西存在可能是不足道的,但很多东西只具有偶然的存在.第二,虚构实质上是一种假装,虚构名称不具有普通名称的功能,它们只是在假装进行指称,关于虚构对象的陈述也只是假装表达了命题,而不是真的表达命题.第三,“虚构的”一词可以叠置,虚构实体是由于人们的活动才得以存在的一种特定类型的抽象实体,它们的存在取决于虚构作品是否被创造出来,因而虚构实体的存在是一个诉诸经验便可解决的问题,在日常语言中,我们完全可以对虚构实体进行量化并建立同一性.     

The Monodic Fragment of Propositional Term Modal Logic

We study term modal logics, where modalities can be indexed by variables that can be quantified over. We suggest that these logics are appropriate for reasoning about systems of unboundedly many reasoners and define a notion of bisimulation which preserves propositional fragment of term modal logics. Also we show that the propositional fragment is already undecidable but that its monodic fragment (formulas using only one free variable in the scope of a modality) is decidable, and expressive enough to include interesting assertions.

     

Preservation Theorems Without Continuum Hypothesis

Many results concerning the equivalence between a syntactic form of formulas and a model theoretic conditions are proven directly without using any form of a continuum hypothesis. In particular, it is demonstrated that any reduced product sentence is equivalent to a Horn sentence. Moreover, in any first order language without equality one now has that a reduced product sentence is equivalent to a Horn sentence and any sentence is equivalent to a Boolean combination of Horn sentences.     

A catalog of Boolean concepts

Boolean concepts are concepts whose membership is determined by a Boolean function, such as that expressed by a formula of propositional logic. Certain Boolean concepts have been much studied in the psychological literature, in particular with regard to their ease of learning. But research attention has been somewhat uneven, with a great deal of attention paid to certain concepts and little to others, in part because of the unavailability of a comprehensive catalog. This paper gives a complete classification of Boolean concepts up to congruence (isomorphism of logical form). Tables give complete details of all concepts determined by up to four Boolean variables. For each concept type, the tables give a canonic logical expression, an approximately minimal logical expression, the Boolean complexity (length of the minimal expression), the number of distinct Boolean concepts of that type, and a pictorial depiction of the concept as a set of vertices in Boolean D-space. Some psychological properties of Boolean concepts are also discussed.     

Bi-Simulating in Bi-Intuitionistic Logic

Bi-intuitionistic logic is the result of adding the dual of intuitionistic implication to intuitionistic logic. In this note, we characterize the expressive power of this logic by showing that the first order formulas equivalent to translations of bi-intuitionistic propositional formulas are exactly those preserved under bi-intuitionistic directed bisimulations. The proof technique is originally due to Lindström and, in contrast to the most common proofs of this kind of result, it does not use the machinery of neither saturated models nor elementary chains.     

Logical feedback

Just as non-well-founded sets extend the usual sets of ZF, so do root reflexive propositional formulas extends the usual class of Boolean expressions. Though infinitary, these formulas are generated by finite patterns. They possess transition functions instead of truth values and have applications in electric circuit theory.     

Probabilistic argumentation systems: A new way to combine logic with probability

Probability is usually closely related to Boolean structures, i.e., Boolean algebras or propositional logic. Here we show, how probability can be combined with non-Boolean structures, and in particular non-Boolean logics. The basic idea is to describe uncertainty by (Boolean) assumptions, which may or may not be valid. The uncertain information depends then on these uncertain assumptions, scenarios or interpretations. We propose to describe information in information systems, as introduced by Scott into domain theory. This captures a wide range of systems of practical importance such as many propositional logics, first order logic, systems of linear equations, inequalities, etc. It covers thus both symbolic as well as numerical systems. Assumption-based reasoning allows then to deduce supporting arguments for hypotheses. A probability structure imposed on the assumptions permits to quantify the reliability of these supporting arguments and thus to introduce degrees of support for hypotheses. Information systems and related information algebras are formally introduced and studied in this paper as the basic structures for assumption-based reasoning. The probability structure is then formally represented by random variables with values in information algebras. Since these are in general non-Boolean structures some care must be exercised in order to introduce these random variables. It is shown that this theory leads to an extension of Dempster–Shafer theory of evidence and that information algebras provide in fact a natural frame for this theory.     

Propositional quantifiers

Summary In discussing propositional quantifiers we have considered two kinds of variables: variables occupying the argument places of connectives, and variables occupying the argument places of predicates.We began with languages which contained the first kind of variable, i.e., variables taking sentences as substituends. Our first point was that there appear to be no sentences in English that serve as adequate readings of formulas containing propositional quantifiers. Then we showed how a certain natural and illuminating extension of English by prosentences did provide perspicuous readings. The point of introducing prosentences was to provide a way of making clear the grammar of propositional variables: propositional variables have a prosentential character — not a pronominal character. Given this information we were able to show, on the assumption that the grammar of propositional variables in philosopher's English should be determined by their grammar in formal languages (unless a separate account of their grammar is provided), that propositional variables can be used in a grammatically and philosophically acceptable way in philosophers' English. According to our criteria of well-formedness Carnap's semantic definition of truth does not lack an essential predicate - despite arguments to the contrary. It also followed from our account of the prosentential character of bound propositional variables that in explaining propositional quantification, sentences should not be construed as names.One matter we have not discussed is whether such quantification should be called propositional, sentential, or something else. As our variables do not range over (they are not terms) either propositions, or sentences, each name is inappropriate, given the usual picture of quantification. But we think the relevant question in this context is, are we obtaining generality with respect to propositions, sentences, or something else?Because people have argued that all bound variables must have a pronominal character, we presented and discussed in the third section languages in which the variables take propositional terms as substituends. In our case we included names of propositions, that-clauses, and names of sentences in the set of propositional terms. We made a few comparisons with the languages discussed in the second section. We showed among other things how a truth predicate could be used to obtain generality. In contrast, the languages of the second section, using propositional variables, obtain generality without the use of a truth predicate.Special thanks are due to Nuel D. Belnap, Jr., who has given me much valuable assistance with the preparation of this paper. I also thank Alan Ross Anderson, Joseph Camp, Jr., Steven Davis, and Wilfrid Sellars for suggestions and corrections.The preparation of this paper was partly supported by a NSF grant.     

Expressivity of Second Order Propositional Modal Logic

We consider second-order propositional modal logic (SOPML), an extension of the basic modal language with propositional quantifiers introduced by Kit Fine in 1970. We determine the precise expressive power of SOPML by giving analogues of the Van Benthem–Rosen theorem and the Goldblatt Thomason theorem. Furthermore, we show that the basic modal language is the bisimulation invariant fragment of SOPML, and we characterize the bounded fragment of first-order logic as being the intersection of first-order logic and SOPML.