In this paper we describe an improvement of Smullyan's analytic tableau method for the propositional calculus-Improved Parent Clash Restricted (IPCR) tableau-and show that it is equivalent to SL-resolution in complexity.

Logics for generally were introduced for handling assertions with vague notions,such as generally, most, several, etc., by generalized quantifiers, ultrafilter logic being an interesting case. Here, we show that ultrafilter logic can be faithfully embedded into a first-order theory of certain functions, called coherent. We also use generic functions (akin to Skolem functions) to enable elimination of the generalized quantifier. These devices permit using methods for classical first-order logic to reason about consequence in ultrafilter logic.

Logics for ‘generally’ were introduced for handling assertions with vague notions, by non-standard generalized quantifiers, and to reason qualitatively about them . Filter logic is intended to address ‘most’. Here, we show that filter logic can be faithfully embedded into a classical first-order theory of certain predicates, called compatible. We also use representative predicates to enable elimination of the generalized quantifier. These devices permit using classical first-order methods to reason about consequence in filter logic and help clarifying the role of (...) such extended logics for ‘generally’. (shrink)

Fuzzy logics are systems of logic with infinitely many truth values. Such logics have been claimed to have an extremely wide range of applications in linguistics, computer technology, psychology, etc. In this note, we canvass the known results concerning infinitely many valued logics; make some suggestions for alterations of the known systems in order to accommodate what modern devotees of fuzzy logic claim to desire; and we prove some theorems to the effect that there can be no fuzzy logic which (...) will do what its advocates want. Finally, we suggest ways to accommodate these desires in finitely many valued logics. (shrink)

Condensed detachment is usually regarded as a notation, and defined by example. In this paper it is regarded as a rule of inference, and rigorously defined with the help of the Unification Theorem of J. A. Robinson. Historically, however, the invention of condensed detachment by C. A. Meredith preceded Robinson's studies of unification. It is argued that Meredith's ideas deserve recognition in the history of unification, and the possibility that Meredith was influenced, through ukasiewicz, by ideas of Tarski going back (...) at least to 1939, and possibly to 1930 or earlier, is discussed. It is proved that a term is derivable by substitution and ordinary detachment from given axioms if and only if it is a substitution instance of a term which is derivable from these axioms by condensed detachment, and it is shown how this theorem enables the ideas of ukasiewicz and Tarski mentioned above to be formalized and extended. Finally, it is shown how condensed detachment may be subsumed within the resolution principle of J. A. Robinson, and several computer studies of particular Hilbert-type propositional calculi using programs based on condensed detachment or on resolution are briefly discussed. (shrink)

In Artificial Intelligence, abduction is often formalized in first-order logic. In this article, we focus on the problem of identifying equivalence of two abductive theories represented in first-order logic. To this end, two definitions of equivalence are given for abduction. Explainable equivalence requires that two abductive theories have the same explainability for any observation. On the other hand, explanatory equivalence guarantees that any observation has exactly the same explanations in each abductive theory. Explanatory equivalence is a stronger notion than explainable (...) equivalence. In first-order logic, explainable equivalence can be veri.ed by the notion of extensional equivalence in default theories, while explanatory equivalence reduces to logical equivalence between background theories. We also show the complexity results for abductive equivalence. (shrink)

We show that Smullyan's analytic tableaux cannot p-simulate the truth-tables. We identify the cause of this computational breakdown and relate it to an underlying semantic difficulty which is common to the whole tradition originating in Gentzen's sequent calculus, namely the dissonance between cut-free proofs and the Principle of Bivalence. Finally we discuss some ways in which this principle can be built into a tableau-like method without affecting its analytic nature.

The proof theory of many-valued systems has not been investigated to an extent comparable to the work done on axiomatizatbility of many-valued logics. Proof theory requires appropriate formalisms, such as sequent calculus, natural deduction, and tableaux for classical (and intuitionistic) logic. One particular method for systematically obtaining calculi for all finite-valued logics was invented independently by several researchers, with slight variations in design and presentation. The main aim of this report is to develop the proof theory of finite-valued first order (...) logics in a general way, and to present some of the more important results in this area. In Systems covered are the resolution calculus, sequent calculus, tableaux, and natural deduction. This report is actually a template, from which all results can be specialized to particular logics. (shrink)