Effective Replaceability of the Omega—Rule for Restricted Sequents of the First–Order Linear Temporal Logic

We consider an effective replaceability of the omega–rule for the always operator in a restricted first–order linear temporal logic. This work is a continuation of two previous papers of the author where an infinitary (with the omega–rule) calculus without loop rules was constructed and founded. In the present paper, we use this calculus to construct the so–called saturated calculus consisting of four decidable deductive procedures replacing the omega–rule for the always operator.     

Representability is not decidable for finite relation algebras

We prove that there is no algorithm that decides whether a finite relation algebra is representable.

Representability of a finite relation algebra is determined by playing a certain two player game over `atomic -networks'. It can be shown that the second player in this game has a winning strategy if and only if is representable.

Let be a finite set of square tiles, where each edge of each tile has a colour. Suppose includes a special tile whose four edges are all the same colour, a colour not used by any other tile. The tiling problem we use is this: is it the case that for each tile there is a tiling of the plane using only tiles from in which edge colours of adjacent tiles match and with placed at ? It is not hard to show that this problem is undecidable.

From an instance of this tiling problem , we construct a finite relation algebra and show that the second player has a winning strategy in if and only if is a yes-instance. This reduces the tiling problem to the representation problem and proves the latter's undecidability.

     

Generalized resolution and cutting planes

This paper illustrates how the application of integer programming to logic can reveal parallels between logic and mathematics and lead to new algorithms for inference in knowledge-based systems. If logical clauses (stating that at least one of a set of literals is true) are written as inequalities, then the resolvent of two clauses corresponds to a certain cutting plane in integer programming. By properly enlarging the class of cutting planes to cover clauses that state that at least a specified number of literals are true, we obtain a generalization of resolution that involves both cancellation-type and circulant-type sums. We show its completeness by proving that it generates all prime implications, generalizing an early result by Quine. This leads to a cutting-plane algorithm as well as a generalized resolution algorithm for checking whether a set of propositions, perhaps representing a knowledge base, logically implies a given proposition. The paper is intended to be readable by persons with either an operations research or an artificial intelligence background.This report was prepared as part of the activities of the Management Sciences Research Group, Carnegie-Mellon University. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.     

Polynomial Computability of Certain Rudimentary Predicates

The class of rudimentary predicates is defined as the smallest class of numerical predicates that contains the equality and concatenation predicates and is closed under the operations of propositional logic, explicit transformations, and bounded quantification. Two classes of rudimentary predicates are considered. The first of them consists of the predicates whose prenex normal form of a special type has the quantifier prefix of the form . Predicates of the second class can have an arbitrary quantifier prefix, but restrictions are imposed on the Skolem deciding functions. It is proved that any predicate from each of these classes can be computed by a suitable deterministic algorithm in polynomial time.     

Birkhoff variety theorem and fuzzy logic

An algebra with fuzzy equality is a set with operations on it that is equipped with similarity , i.e. a fuzzy equivalence relation, such that each operation f is compatible with . Described verbally, compatibility says that each f yields similar results if applied to pairwise similar arguments. On the one hand, algebras with fuzzy equalities are structures for the equational fragment of fuzzy logic. On the other hand, they are the formal counterpart to the intuitive idea of having functions that are not allowed to map similar objects to dissimilar ones. In this paper, we present a generalization of the well-known Birkhoffs variety theorem: a class of algebras with fuzzy equality is the class of all models of a fuzzy set of identities iff it is closed under suitably defined morphisms, substructures, and direct products. and Institute for Fuzzy Modeling, University of Ostrava, 30. dubna 22, 701 03 Ostrava, Czech Republic Mathematics Subject Classification (2000):03B52, 08B05     

The Qubits of Qunivac

We distinguish between ontic and praxic formulations of quantum theory and adopt a praxic one. We formulate a reversible higher-order quantum logic in a large Clifford algebra Cliff(). We use it to describe the operation of the Quantum Universe As Computer (Qunivac). The qubits of Qunivac are associated with Clifford units with a real Clifford-Wilczek statistics. We encode the spin- Dirac equation on Qunivac in an exactly Lorentz-invariant ultraquantum space-time. Qunivac violates the canonical Heisenberg indeterminacy principle and locality in a way that should show up at high energies only. Qunivac accommodates a field theory.     

ON THE RELIABILITY OF MEDIUM LOGIC(ML)

Medium logic (ML) is set up for the common theoritical foundation of the classical mathematics and fuzzy mathematics. It has been formalized as a new theory of logic. See note (1) and note (2). As mathematical logic the ML's construct reches the study of the informal deductive inference by means of studying the formal inference in it, and it demands the formal inference of ML reliable reflected the deductive inference. For this reason, this paper deals with its reliability. The result shows that the formal inference of M L consists with deductive inference, and that ML reliably reflects the deductive inference.