辅助变元之于命题与量化布尔公式的作用

使用辅助变元来引入定义,在知识表达中是一个流行和有力的技巧,能够得到更短、更自然的编码而无需冗长的重复。这篇论文中,我们形式地定义了辅助变元的概念,检验了其表达力并讨论了有趣的相关应用。我们把以下两者联系起来:一是,反复使用中间结果而不通过定义重复;二是,布尔函数其他表达中的相似概念。特别的,我们表明带定义的命题逻辑与具有任意输出端的布尔线路以及约束变元满足Horn性质的存在量化布尔公式(记作(?)HORN~b)具有相同的表达力。本文还考虑了定义结构的限制,以及命题定义的扩充。特别的,我们检验了正命题定义与带存在量化的正定义之间的关系(或等价地,检验了(?)HORN~b公式和约束变元未被Horn限定的存在量化的CNF公式(记作(?)CNF~*)之间的关系)。对命题定义的进一步扩充,是允许在定义中使用任意的量词,或等价地,允许布尔公式的嵌入。我们还证明了,量化CNF公式中的约束变元的表达力,是由子句中被约束部分的极小不可满足子公式或极小假子公式的结构所决定的。     

Classifying ℵ0-categorical theories

Among the complete ₀-categorical theories with finite non-logical vocabularies, we distinguish three classes. The classification is obtained by looking at the number of bound variables needed to isolated complete types. In classI theories, all types are isolated by quantifier free formulas; in classII theories, there is a leastm, greater than zero, s.t. all types are isolated by formulas in no more thanm bound variables: and in classIII theories, for eachm there is a type which cannot be isolated inm or fewer bound variables. ClassII theories are further subclassified according to whether or not they can be extended to classI theories by the addition of finitely many new predicates. Alternative characterizations are given in terms of quantifier elimination and homogeneous models. It is shown that for each primep, the theory of infinite Abelian groups all of whose elements are of orderp is classI when formulated in functional constants, and classIII when formulated in relational constants.     

Frame Based Formulas for Intermediate Logics

In this paper we define the notion of frame based formulas. We show that the well-known examples of formulas arising from a finite frame, such as the Jankov-de Jongh formulas, subframe formulas and cofinal subframe formulas, are all particular cases of the frame based formulas. We give a criterion for an intermediate logic to be axiomatizable by frame based formulas and use this criterion to obtain a simple proof that every locally tabular intermediate logic is axiomatizable by Jankov-de Jongh formulas. We also show that not every intermediate logic is axiomatizable by frame based formulas. Presented by Johan van Benthem     

Translation of first order formulas into ground formulas via a completion theory

A translation technique is presented which transforms a class of First Order Logic formulas, called Restricted formulas, into ground formulas. For the formulas in this class the range of quantified variables is restricted by Domain formulas.If we have a complete knowledge of the predicates involved in the Domain formulas their extensions can be evaluated with the Relational Algebra and these extensions are used to transform universal (respectively existential) quantifiers into finite conjunctions (respectively disjunctions).It is assumed that the complete knowledge is represented by Completion Axioms and Unique Name Axioms à la Reiter. These axioms involve the equality predicate. However, the translation allows to remove the equality in the ground formulas and for a large class of formulas their consequences are the same as the initial First Order formulas. This result open the door for the design of efficient deduction techniques.     

λ-Normal forms in an intensional logic for English

Montague [7] translates English into a tensed intensional logic, an extension of the typed -calculus. We prove that each translation reduces to a formula without -applications, unique to within change of bound variable. The proof has two main steps. We first prove that translations of English phrases have the special property that arguments to functions are modally closed. We then show that formulas in which arguments are modally closed have a unique fully reduced -normal form. As a corollary, translations of English phrases are contained in a simply defined proper subclass of the formulas of the intensional logic.This research is supported in part by National Science Foundation Grant BNS 76-23840.     

Upper bounds for Kruskal's stress

In this paper the relationships between the two formulas for stress proposed by Kruskal in 1964 are studied. It is shown that stress formula one has a system of nontrivial upper bounds. It seems likely that minimization of this loss function will be liable to produce solutions for which this upper bound is small. These are regularly shaped configurations. Even though stress formula two yields less equivocal results, it seems to be expected that minimization of this loss function will tend to produce configurations in which the points are clumped. These results give no clue as to which of the two loss functions is to be preferred.This study has been supported by the Nederlandse Organisatie voor Zuiver-Wetenschappelijk Onderzoek (Netherlands Organization for the Advancement of Pure Research), under grant 56-146.Comments by Willem Heiser and Frank Critichley have been very helpful.The second author presently is employed by the Netherlands Central Bureau of Statistics, Voorburg.     

Hyperformulas and Solid Algebraic Systems

Defining a composition operation on sets of formulas one obtains a many-sorted algebra which satisfies the superassociative law and one more identity. This algebra is called the clone of formulas of the given type. The interpretations of formulas on an algebraic system of the same type form a many-sorted algebra with similar properties. The satisfaction of a formula by an algebraic system defines a Galois connection between classes of algebraic systems of the same type and collections of formulas. Hypersubstitutions are mappings sending pairs of operation symbols to pairs of terms of the corresponding arities and relation symbols to formulas of the same arities. Using hypersubstitutions we define hyperformulas. Satisfaction of a hyperformula by an algebraic system defines a second Galois connection between classes of algebraic systems of the same type and collections of formulas. A class of algebraic systems is said to be solid if every formula which is satisfied is also satisfied as a hyperformula. On the basis of these two Galois connections we construct a conjugate pair of additive closure operators and are able to characterize solid classes of algebraic systems. Presented by Wojciech Buszkowski     

Approximate sample size formulas for the two‐sample trimmed mean test with unequal variances

Yuen's two‐sample trimmed mean test statistic is one of the most robust methods to apply when variances are heterogeneous. The present study develops formulas for the sample size required for the test. The formulas are applicable for the cases of unequal variances, non‐normality and unequal sample sizes. Given the specified α and the power (1?β), the minimum sample size needed by the proposed formulas under various conditions is less than is given by the conventional formulas. Moreover, given a specified size of sample calculated by the proposed formulas, simulation results show that Yuen's test can achieve statistical power which is generally superior to that of the approximate t test. A numerical example is provided.     

可满足性问题的归约技术

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

Multiple rectilinear prediction and the resolution into components

It is assumed that a battery ofn tests has been resolved into components in a common factor space ofr dimensions and a unique factor space of at mostn dimensions, wherer is much less thann. Simplified formulas for ordinary multiple and partial correlation of tests are derived directly in terms of the components. The best (in the sense of least squares) linear regression equations for predicting factor scores from test scores are derived also in terms of the components. Spearman's single factor prediction formulas emerge as special cases. The last part of the paper shows how the communality is an upper bound for multiple correlation. A necessary and sufficient condition is established for the square of the multiple correlation coefficient of testj on the remainingn—1 tests to approach the communality of testj as a limit asn increases indefinitely whiler remains constant. Limits are established for partial correlation and regression coefficients and for the prediction of factor scores.I am indebted to Professor Dunham Jackson for helpful criticism of most of this paper.     

Reliability formulas for noncompleted or speeded tests

New formulas are developed to give lower bounds to the reliability of a test, whether or not all respondents attempt all items. The formulas apply in particular, then, to completed tests, pure speed tests, pure power tests, and any mixture of speed and power. For the case of completed tests, the formulas give the same answer as certain standard ones; for noncompleted tests the formulas give a correct answer where previous standard formulas are inappropriate. The formulas hold both in the sense of retest reliability and of parallel tests.This research was facilitated by an uncommitted grant-in-aid to the writer from the Behavioral Sciences Division of the Ford Foundation.     

Effects of meaningfulness and organization on problem solving and computability judgments

When subjects were required to calculate answers for computable problems and answer questions, an interaction was found corresponding to that obtained by Kieras and Greeno (1975) from judgments of computability. With nonsense formulas, much longer times were required to identify noncomputable problems than to compute answers, with a much smaller difference when formulas consisted of meaningful concepts. The better performance on noncomputable problems and questions with meaningful formulas corroborates an interpretation that those items test the connection of algorithms with general conceptual knowledge. Finally, it was found that for relatively complex problems, solution times and time to judge computability were longer if nonsense formulas were learned in separate sets than if they were learned in a single set; however, no such effect was found with meaningful formulas. It was concluded that learning conditions influenced the integration of cognitive structure in the case of nonsense formulas, while subjects were able to adjust organization of the meaningful formulas.     

A Bayesian hierarchical model for the measurement of working memory capacity

Working memory is the memory system that allows for conscious storage and manipulation of information. The capacity of working memory is extremely limited. Measurements of this limit, and what affects it, are critical to understanding working memory. Cowan (2001) and Pashler (1988) suggested applying multinomial tree models to data from change detection paradigms in order to estimate working memory capacity. Both Pashler and Cowan suggested simple formulas for estimating capacity with these models. However, in many cases, these simple formulas are inadequate, and may lead to inefficient or biased estimation of working memory capacity. I propose a Bayesian hierarchical alternative to the Pashler and Cowan formulas, and show that the hierarchical model outperforms the traditional formulas. The models are easy to use and appropriate for a wide range of experimental designs. An easy-to-use graphical user interface for fitting the hierarchical model to data is available.     

Some uses of the square root method as a tool in multiple prediction

It is shown how the square root method can be used in the derivation of formulas in multiple prediction and in the computations necessary for their application. A formula derived by Horst indicates the validity a test must possess in order to contribute a specified amount to the multiple correlation of a battery. Then a formula is derived which relates the length of one test in a battery to the multiple correlation of the battery as a whole. The formulas hold for population parameters; in this paper, sampling theory is not discussed. A numerical example is presented; it is shown that one square root analysis provides all the data needed for the formulas.     

Wittgenstein's ab-Notation: An Iconic Proof Procedure

This paper systematically outlines Wittgenstein's ab-notation. The purpose of this notation is to provide a proof procedure in which ordinary logical formulas are converted into ideal symbols that identify the logical properties of the initial formulas. The general ideas underlying this procedure are in opposition to a traditional conception of axiomatic proof and are related to Peirce's iconic logic. Based on Wittgenstein's scanty remarks concerning his ab-notation, which almost all apply to propositional logic, this paper explains how to extend his method to a subset of first-order formulas, namely, formulas that do not contain dyadic sentential connectives within the scope of any quantifier.     

Measuring coherence using LP-models

This paper introduces a technique for measuring the degree of (in)coherence of inconsistent sets of propositional formulas. The coherence of these sets of formulas is calculated using the minimal models of those sets in G. Priest's Logic of Paradox. The compatibility of the information expressed by a set of formulas with the background or domain knowledge can also be measured with this technique. In this way, Hunter's objections to many-valued paraconsistent logics as instruments for measuring (in)coherence are addressed.     

The reliability of speeded tests

Some methods are presented for estimating the reliability of a partially speeded test without the use of a parallel form. The effect of these formulas on some test data is illustrated. Whenever an odd-even reliability is computed it is probably desirable to use one of the formulas noted in Section 2 of this paper in addition to the usual Spearman-Brown correction. Since the formulas given here involve the mean and the standard deviation of the “number unattempted score,” a method is given in Section 4 for computing this mean and standard deviation from item analysis data. If the item analysis data are available, this method will save considerable time as compared with rescoring answer sheets.     

Modal Horn Classes

This paper deals with modal Horn formulas. It contains a characterization of the classes of models definable by modal universal Horn formulas as well as a preservation result for modal universal Horn formulas. This revised version was published online in June 2006 with corrections to the Cover Date.     

Measures of attitudinal polarization

Abstract.— Criteria for measures of attitudinal polarization, i. e., degree of opposition among people on a specific issue, are proposed and some formulas, including the standard deviation, are evaluated in relation to the criteria. The formulas were also tested on empirical data with respect to level, dispersion and agreement of received values. The measures on the whole showed a high degree of agreement. There clearly exist instances where the standard deviation is not an adequate measure of attitudinal polarization. Some guidelines are given for the choice of constant values in one of the formulas.     

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

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