Wyniki wyszukiwania - Biblioteka Nauki

1

Logical Undecidabilities Made Easy

100%

Leivan D.

|

2008

|

tom Vol. 89, nr 2-3

307-312

EN

Referring to symbolic computing permits extremely simple proofs of undecidability for first-order logic and theories of basic structures. Using grammars we obtain a trivial proof that firstorder validity is undecidable (already for formulas with quantifier prefix ∃∃ and referring to only one unary relation and one binary function [2]). A similar proof yields Gödel's First Incompleteness Theorem for the structure of strings; undecidability for arithmetic follows by noting that addition and multiplication permit direct coding of string concatenation.

2

Composition Theorem for Generalized Sum

80%

Rabinovich A.

|

2007

|

tom Vol. 79, nr 1-2

137-167

EN

Composition theorems are tools which reduce sentences about some compound structure to sentences about its parts. A seminal example of such a theorem is the Feferman-Vaught Theorem [3] which reduces the first-order theory of generalized products to the first order theory of its factors and the monadic second-order theory of index structure. Shelah [23] used the composition theorem for linear orders as one of the main tools for obtaining very strong decidability results for the monadic second-order theory of linear orders. The main technical contribution of our paper is (1) a definition of a generalized sum of structures and (2) a composition theorem for first-order logic over the generalized sum. One of our objectives is to emphasize the work-out of the composition method.

3

A General Similarity Framework for Horn Clause Logic

80%

Ferilli S. , Basile T. M. A. , Biba M. , Di Mauro N. , Esposito F.

|

2009

|

tom Vol. 90, nr 1-2

43-66

EN

First-Order Logic formulć are a powerful representation formalism characterized by the use of relations, that cause serious computational problems due to the phenomenon of indeterminacy (various portions of one description are possibly mapped in different ways onto another description). Being able to identify the correct corresponding parts of two descriptions would help to tackle the problem: hence, the need for a framework for the comparison and similarity assessment. This could have many applications in Artificial Intelligence: guiding subsumption procedures and theory revision systems, implementing flexible matching, supporting instance-based learning and conceptual clustering. Unfortunately, few works on this subject are available in the literature. This paper focuses on Horn clauses, which are the basis for the Logic Programming paradigm, and proposes a novel similarity formula and evaluation criteria for identifying the descriptions components that are more similar and hence more likely to correspond to each other, based only on their syntactic structure. Experiments on real-world datasets prove the effectiveness of the proposal, and the efficiency of the corresponding implementation in the above tasks.

4

On First-Order Fragments for Mazurkiewicz Traces

80%

Diekert V. , Horsch M. , Kufleitner M.

|

2007

|

tom Vol. 80, nr 1-3

1-29

EN

Mazurkiewicz traces form a model for concurrency. Temporal logic and first-order logic are important tools in order to deal with the abstract behavior of such systems. Since typical properties can be described by rather simple logical formulas one is interested in logical fragments. One focus of this paper is unary temporal logic and first-order logic in two variables. Over words, this corresponds to the variety of finite monoids called DA. However, over Mazurkiewicz traces it is crucial whether traces are given as dependence graphs or as partial orders (over words these notions coincide). The main technical contribution is a generalization of important characterizations of DA from words to dependence graphs, whereas the use of partial orders leads to strictly larger classes. As a consequence we can decide whether a first-order formula over dependence graphs is equivalent to a first-order formula in two variables. The corresponding result for partial orders is not known. This difference between dependence graphs and partial orders also affects the complexity of the satisfiability problems for the fragments under consideration: for first-order formulas in two variables we prove an NEXPTIME upper bound, whereas the corresponding problem for partial orders leads to EXPSPACE. Furthermore, we give several separation results for the alternation hierarchy for first-order logic. It turns out that even for those levels at which one can express the partial order relation in terms of dependence graphs, the fragments over partial orders have more expressive power.

5

Praktyczny aspekt logiki (stanowisko Kazimierza Ajdukiewicza)

80%

Czernecka-Rej B.

Prakseologia

|

2012

|

nr 152

223-235

EN

The aim of this article is to present and discuss the Ajdukiewicz’s concept of the practical aspect of logic. To begin, I describe his concept of the practical importance of science and especially his concept of logic – i.e., the deﬁnition and range of logic. The idea of “logical culture” is fundamental to his conceptualization. I also present Ajdukiewicz’s idea that making the course of logic more practical should be required. At the end of the article I discuss the importance of Ajdukiewicz’s view.

6

A Logical Approach to Control. Some New Logical Concepts and their Application to the Notion of Safety for Control Variants

70%

Terlikowski T.

|

2002

|

tom Vol. 52, nr 4

377-394

EN

In this paper, we introduce logical notions of positive implication and positive correspondence aimed at a formalization of notions of safety of control variants in control theory.

7

Automated deduction techniques for studying Rough Algebras

60%

Vigneron L.

|

1998

|

tom Vol. 33, nr 1

85-103

EN

We present a non-exhaustive state of the art. In the domain of deduction in first-order logic with equality, describing different strategies introduced over the years: strategies for selecting deduction steps, for eliminating redundant information, for delaying the resolution of unsolved or too difficult problems, for applying deductions with built-in-properties. We also present the system dalac that implements our deduction techniques modulo associative-commutative properties. Finally we detail an application of those techniques to the study of non-classical logics, work realised in collaboration with Prof. Wasilewska (Stony Brook University, New York).

8

A Short and Readable Proof of Cut Elimination for Two First-Order Modal Logics

51%

Gao F. , Tourlakis G.

|

nr 3-4

EN

A well established technique toward developing the proof theory of a Hilbert-style modal logic is to introduce a Gentzen-style equivalent (a Gentzenisation), then develop the proof theory of the latter, and finally transfer the metatheoretical results to the original logic (e.g., [1, 6, 8, 18, 10, 12]). In the first-order modal case, on one hand we know that the Gentzenisation of the straightforward first-order extension of GL, the logic QGL, admits no cut elimination (if the rule is included as primitive; or, if not included, then the rule is not admissible [1]). On the other hand the (cut-free) Gentzenisations of the first-order modal logics M3 and ML3 of [10, 12] do have cut as an admissible rule. The syntactic cut admissibility proof given in [18] for the Gentzenisation of the propositional provability logic GL is extremely complex, and it was the basis of the proofs of cut admissibility of the Gentzenisations of M3 and ML3, where the presence of quantifiers and quantifier rules added to the complexity and length of the proof. A recent proof of cut admissibility in a cut-free Gentzenisation of GL is given in [5] and is quite short and easy to read. We adapt it here to revisit the proofs for the cases of M3 and ML3, resulting to similarly short and easy to read proofs, only slightly complicated by the presence of quantification and its relevant rules.

9

Identity, Equality, Nameability and Completeness

51%

Manzano M. , Moreno M. C.

Bulletin of the Section of Logic

|

2017

|

tom 46

|

nr 3/4

EN

This article is an extended promenade strolling along the winding roads of identity, equality, nameability and completeness, looking for places where they converge. We have distinguished between identity and equality; the first is a binary relation between objects while the second is a symbolic relation between terms. Owing to the central role the notion of identity plays in logic, you can be interested either in how to define it using other logical concepts or in the opposite scheme. In the first case, one investigates what kind of logic is required. In the second case, one is interested in the definition of the other logical concepts (connectives and quantifiers) in terms of the identity relation, using also abstraction. The present paper investigates whether identity can be introduced by definition arriving to the conclusion that only in full higher-order logic a reliable definition of identity is possible. However, the definition needs the standard semantics and we know that with this semantics completeness is lost. We have also studied the relationship of equality with comprehension and extensionality and pointed out the relevant role played by these two axioms in Henkin’s completeness method. We finish our paper with a section devoted to general semantics, where the role played by the nameable hierarchy of types is the key in Henkin’s completeness method.

10

Universality of Logic

51%

Woleński J.

Bulletin of the Section of Logic

|

2017

|

tom 46

|

nr 1/2

EN

This paper deals with the problem of universality property of logic. At first, this property is analyzed in the context of first-order logic. Three senses of the universality property are distinguished: universal applicability, topical neutrality and validity (truth in all models). All theses senses can be proved to be justified. The fourth understanding, namely the amount of expressive power, is connected with the criticism of the first-order thesis: first-order logic is the logic. The categorical approach to logic is presented as associated with the last understanding of universality. The author concludes that two senses of universality should be sharply discriminated and defends the first-order thesis.

11

A New Arithmetically Incomplete First-Order Extension of Gl All Theorems of Which Have Cut Free Proofs

51%

Tourlakis G.

Bulletin of the Section of Logic

|

2016

|

tom 45

|

nr 1

EN

Reference [12] introduced a novel formula to formula translation tool (“formula-tors”) that enables syntactic metatheoretical investigations of first-order modallogics, bypassing a need to convert them first into Gentzen style logics in order torely on cut elimination and the subformula property. In fact, the formulator tool,as was already demonstrated in loc. cit., is applicable even to the metatheoreticalstudy of logics such as QGL, where cut elimination is (provably, [2]) unavailable. This paper applies the formulator approach to show the independence of the axiom schema ☐A → ☐∀ A of the logics M3and ML3 of [17, 18, 11, 13]. This leads to the conclusion that the two logics obtained by removing this axiom are incomplete, both with respect to their natural Kripke structures and to arithmetical interpretations. In particular, the so modified ML3 is, similarly to QGL, an arithmetically incomplete first-order extension of GL, but, unlike QGL, all its theorems have cut free proofs. We also establish here, via formulators, a stronger version of the disjunction property for GL and QGL without going through Gentzen versions of these logics (compare with the more complexproofs in [2,8]).

12

A model-theoretic version of the complement theorem

41%

Nowak K.

|

1999

|

tom Vol. 47, no 4

345-353

EN

This paper deals with an axiomatic theory T[sub an] and the expansion R[sub an] of the ordered field of reals, formed by attaching the restricted analytic functions. We show that the theory T[sub an] is model-complete, which may be regarded as a version of Gabrielov's complement theorem. Our proof is based on Robinson's test and it does not involve a partition technique. An immediate corollary is that T[sub an] coincides with the semantic theory Th(R[sub an]) of all sentences true in the structure R[sub an].

13

A model-theoretic version of the complement theorem : applications

41%

Nowak K.

|

1999

|

tom Vol. 47, no 4

355-361

EN

The paper treats of some consequences of the model-theoretic version of Gabrielov's complement theorem from [11], which asserts that the theories T[sub an] (introduced in [11] and T'[sub an] (defined herein) are model-complete. The theory T'[sub an] is a universal modification of T[sub an] in the language L'[sub an] of ordered rings expanded by the symbols of restricted analytic functions, arithmetic roots and multiplicative inverse l/x. We give a short proof of the curve selecting lemma, and next we demonstrate how quantifier elimination, within the structure R[sub an] expanded by multiplicative inverse 1/x (a result due to Denef-van den Dries [4], can be obtained from the complement theorem through a general method of logic. Also presented is an application to definability problems ; namely, a piecewise description of a subanalytic function by restricted analytic functions, arithmetic roots and l/x.