Orthogonal forms of positive Boolean functions play an important role in reliability theory, since the probability that they take value 1 can be easily computed. However, few classes of disjunctive normal forms are known for which orthogonalization can be efficiently performed. An interesting class with this property is the class of shellable disjunctive normal forms (DNFs). In this paper, we present some new results about shellability. We establish that every positive Boolean function can be represented by a shellable DNF, we propose a polynomial procedure to compute the dual of a shellable DNF, and we prove that testing the so-called lexico-exchange (LE) property (a strengthening of shellability) is NP-complete.

Given a Boolean function f, we define the importance of a set S of variables by an expression measuring to what extent the variables in S determine the value of f. This "evaluation" uses a "constancy" measure which is assumed to be a real-valued convex function defined on [0,1]. In spite of the generality of the constancy measure, it is shown that any such evaluation is in strong agreement with the classical concept of the Winder-strength of variables of a monotone Boolean function. Further, we study a special class of evaluations called relevances, characterize completely the cases of extreme relevance value, relating the sets of maximum relevance to fictitious (dummy) variables and support sets, and establish a lower bound on the relevance of sets "containing" implicants or implicates of a Boolean function.

Describes a new, logic-based methodology for analyzing observations. The key features of this “logical analysis of data” (LAD) methodology are the discovery of minimal sets of features that are necessary for explaining all observations and the detection of hidden patterns in the data that are capable of distinguishing observations describing “positive” outcome events from “negative” outcome events. Combinations of such patterns are used for developing general classification procedures. An implementation of this methodology is described in this paper, along with the results of numerical experiments demonstrating the classification performance of LAD in comparison with the reported results of other procedures. In the final section, we describe three pilot studies on applications of LAD to oil exploration, psychometric testing and the analysis of developments in the Chinese transitional economy. These pilot studies demonstrate not only the classification power of LAD but also its flexibility and capability to provide solutions to various case-dependent problems.

The tetrad representation theorem, due to Spirtes, Glymour, and Scheines (1993), gives a graphical condition necessary and sufficient for the vanishing of an individual tetrad difference in a recursive path model with uncorrelated errors. In this paper, we generalize their result from individual tetrad differences to sets of tetrad differences of a certain form, and we simplify their proof. The generalization allows tighter constraints to be placed on the set of models compatible with given data and thereby facilitates the search for parsimonious models for large data sets.

Horn knowledge bases are widely used in many applications. The paper is concerned with the optimal compression of propositional Horn production rule bases-one of the most important knowledge bases used in practice. The problem of knowledge compression is interpreted as a problem of Boolean function minimization. It was proved by P.L. Hammer and A. Kogan (1993) that the minimization of Horn functions, i.e., Boolean functions associated with Horn knowledge bases, is NP complete. The paper deals with the minimization of quasi acyclic Horn functions, the class of which properly includes the two practically significant classes of quadratic and of acyclic functions. A procedure is developed for recognizing in quadratic time the quasi acyclicity of a function given by a Horn CNF, and a graph based algorithm is proposed for the quadratic time minimization of quasi acyclic Horn functions.>