Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "deduction" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-8 z 8
    Tytuł:
    An Alternative Natural Deduction for the Intuitionistic Propositional Logic
    Autorzy:
    Ilić, Mirjana
    Powiązania:
    https://bibliotekanauki.pl/articles/749978.pdf
    Data publikacji:
    2016
    Wydawca:
    Uniwersytet Łódzki. Wydawnictwo Uniwersytetu Łódzkiego
    Tematy:
    natural deduction
    intuitionistic logic
    Opis:
    A natural deduction system NI, for the full propositional intuitionistic logic, is proposed. The operational rules of NI are obtained by the translation from Gentzen’s calculus LJ and the normalization is proved, via translations from sequent calculus derivations to natural deduction derivations and back.
    Źródło:
    Bulletin of the Section of Logic; 2016, 45, 1
    0138-0680
    2449-836X
    Pojawia się w:
    Bulletin of the Section of Logic
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Proof Compression and NP Versus PSPACE II: Addendum
    Autorzy:
    Gordeev, Lew
    Haeusler, Edward Hermann
    Powiązania:
    https://bibliotekanauki.pl/articles/2142754.pdf
    Data publikacji:
    2022-01-07
    Wydawca:
    Uniwersytet Łódzki. Wydawnictwo Uniwersytetu Łódzkiego
    Tematy:
    graph theory
    natural deduction
    computational complexity
    Opis:
    In our previous work we proved the conjecture NP = PSPACE by advanced proof theoretic methods that combined Hudelmaier’s cut-free sequent calculus for minimal logic (HSC) with the horizontal compressing in the corresponding minimal Prawitz-style natural deduction (ND). In this Addendum we show how to prove a weaker result NP = coNP without referring to HSC. The underlying idea (due to the second author) is to omit full minimal logic and compress only “naive” normal tree-like ND refutations of the existence of Hamiltonian cycles in given non-Hamiltonian graphs, since the Hamiltonian graph problem in NPcomplete. Thus, loosely speaking, the proof of NP = coNP can be obtained by HSC-elimination from our proof of NP = PSPACE.
    Źródło:
    Bulletin of the Section of Logic; 2022, 51, 2; 197-205
    0138-0680
    2449-836X
    Pojawia się w:
    Bulletin of the Section of Logic
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    From Gentzen to Jaskowski and Back: Algorithmic Translation of Derivations Between the Two Main Systems of Natural Deduction
    Autorzy:
    von Plato, Jan
    Powiązania:
    https://bibliotekanauki.pl/articles/749936.pdf
    Data publikacji:
    2017
    Wydawca:
    Uniwersytet Łódzki. Wydawnictwo Uniwersytetu Łódzkiego
    Tematy:
    proof systems
    linear natural deduction
    Gentzen
    Jaśkowski
    Opis:
    The way from linearly written derivations in natural deduction, introduced by Jaskowski and often used in textbooks, is a straightforward root-first translation. The other direction, instead, is tricky, because of the partially ordered assumption formulas in a tree that can get closed by the end of a derivation. An algorithm is defined that operates alternatively from the leaves and root of a derivation and solves the problem.
    Źródło:
    Bulletin of the Section of Logic; 2017, 46, 1/2
    0138-0680
    2449-836X
    Pojawia się w:
    Bulletin of the Section of Logic
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Proof Compression and NP Versus PSPACE II
    Autorzy:
    Gordeev, Lew
    Haeusler, Edward Hermann
    Powiązania:
    https://bibliotekanauki.pl/articles/1023196.pdf
    Data publikacji:
    2020-11-04
    Wydawca:
    Uniwersytet Łódzki. Wydawnictwo Uniwersytetu Łódzkiego
    Tematy:
    natural deduction
    sequent calculus
    minimal logic
    computational complexity
    Opis:
    We upgrade [3] to a complete proof of the conjecture NP = PSPACE that is known as one of the fundamental open problems in the mathematical theory of computational complexity; this proof is based on [2]. Since minimal propositional logic is known to be PSPACE complete, while PSPACE to include NP, it suffices to show that every valid purely implicational formula ρ has a proof whose weight (= total number of symbols) and time complexity of the provability involved are both polynomial in the weight of ρ. As is [3], we use proof theoretic approach. Recall that in [3] we considered any valid ρ in question that had (by the definition of validity) a “short” tree-like proof π in the Hudelmaier-style cutfree sequent calculus for minimal logic. The “shortness” means that the height of π and the total weight of different formulas occurring in it are both polynomial in the weight of ρ. However, the size (= total number of nodes), and hence also the weight, of π could be exponential in that of ρ. To overcome this trouble we embedded π into Prawitz’s proof system of natural deductions containing single formulas, instead of sequents. As in π, the height and the total weight of different formulas of the resulting tree-like natural deduction ∂1 were polynomial, although the size of ∂1 still could be exponential, in the weight of ρ. In our next, crucial move, ∂1 was deterministically compressed into a “small”, although multipremise, dag-like deduction ∂ whose horizontal levels contained only mutually different formulas, which made the whole weight polynomial in that of ρ. However, ∂ required a more complicated verification of the underlying provability of ρ. In this paper we present a nondeterministic compression of ∂ into a desired standard dag-like deduction ∂0 that deterministically proves ρ in time and space polynomial in the weight of ρ.2 Together with [3] this completes the proof of NP = PSPACE.Natural deductions are essential for our proof. Tree-to-dag horizontal compression of π merging equal sequents, instead of formulas, is (possible but) not sufficient, since the total number of different sequents in π might be exponential in the weight of ρ – even assuming that all formulas occurring in sequents are subformulas of ρ. On the other hand, we need Hudelmaier’s cutfree sequent calculus in order to control both the height and total weight of different formulas of the initial tree-like proof π, since standard Prawitz’s normalization although providing natural deductions with the subformula property does not preserve polynomial heights. It is not clear yet if we can omit references to π even in the proof of the weaker result NP = coNP.
    Źródło:
    Bulletin of the Section of Logic; 2020, 49, 3; 213-230
    0138-0680
    2449-836X
    Pojawia się w:
    Bulletin of the Section of Logic
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A Binary Quantifier for Definite Descriptions in Intuitionist Negative Free Logic: Natural Deduction and Normalisation
    Autorzy:
    Kürbis, Nils
    Powiązania:
    https://bibliotekanauki.pl/articles/749954.pdf
    Data publikacji:
    2019
    Wydawca:
    Uniwersytet Łódzki. Wydawnictwo Uniwersytetu Łódzkiego
    Tematy:
    definite descriptions
    negative intuitionist free logic
    natural deduction
    normalization
    Opis:
    This paper presents a way of formalising definite descriptions with a binary quantifier ℩, where ℩x[F, G] is read as `The F is G'. Introduction and elimination rules for ℩ in a system of intuitionist negative free logic are formulated. Procedures for removing maximal formulas of the form ℩x[F, G] are given, and it is shown that deductions in the system can be brought into normal form.
    Źródło:
    Bulletin of the Section of Logic; 2019, 48, 2; 81-97
    0138-0680
    2449-836X
    Pojawia się w:
    Bulletin of the Section of Logic
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Analytic Non-Labelled Proof-Systems for Hybrid Logic: Overview and a couple of striking facts
    Autorzy:
    Braüner, Torben
    Powiązania:
    https://bibliotekanauki.pl/articles/2142755.pdf
    Data publikacji:
    2022-01-07
    Wydawca:
    Uniwersytet Łódzki. Wydawnictwo Uniwersytetu Łódzkiego
    Tematy:
    hybrid logic
    natural deduction systems
    sequent systems
    normalization
    cut-elimination
    analycity
    Opis:
    This paper is about non-labelled proof-systems for hybrid logic, that is, proofsystems where arbitrary formulas can occur, not just satisfaction statements. We give an overview of such proof-systems, focusing on analytic systems: Natural deduction systems, Gentzen sequent systems and tableau systems. We point out major results and we discuss a couple of striking facts, in particular that nonlabelled hybrid-logical natural deduction systems are analytic, but this is not proved in the usual way via step-by-step normalization of derivations.
    Źródło:
    Bulletin of the Section of Logic; 2022, 51, 2; 143-162
    0138-0680
    2449-836X
    Pojawia się w:
    Bulletin of the Section of Logic
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Two Treatments of Definite Descriptions in Intuitionist Negative Free Logic
    Autorzy:
    Kürbis, Nils
    Powiązania:
    https://bibliotekanauki.pl/articles/750050.pdf
    Data publikacji:
    2019
    Wydawca:
    Uniwersytet Łódzki. Wydawnictwo Uniwersytetu Łódzkiego
    Tematy:
    definite descriptions
    binary quantifier
    term forming operator
    Lambert's Law
    intuitionist negative free logic
    natural deduction
    Opis:
    Sentences containing definite descriptions, expressions of the form `The F', can be formalised using a binary quantier that forms a formula out of two predicates, where ℩x[F;G] is read as `The F is G'. This is an innovation over the usual formalisation of definite descriptions with a term forming operator. The present paper compares the two approaches. After a brief overview of the system INF℩ of intuitionist negative free logic extended by such a quantier, which was presented in [4], INF℩ is first compared to a system of Tennant's and an axiomatic treatment of a term forming ℩ operator within intuitionist negative free logic. Both systems are shown to be equivalent to the subsystem of INF℩ in which the G of ℩x[F;G] is restricted to identity. INF℩ is then compared to an intuitionist version of a system of Lambert's which in addition to the term forming operator has an operator for predicate abstraction for indicating scope distinctions. The two systems will be shown to be equivalent through a translation between their respective languages. Advantages of the present approach over the alternatives are indicated in the discussion.
    Źródło:
    Bulletin of the Section of Logic; 2019, 48, 4
    0138-0680
    2449-836X
    Pojawia się w:
    Bulletin of the Section of Logic
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Functional Completeness in CPL via Correspondence Analysis
    Autorzy:
    Leszczyńska-Jasion, Dorota
    Petrukhin, Yaroslav
    Shangin, Vasilyi
    Jukiewicz, Marcin
    Powiązania:
    https://bibliotekanauki.pl/articles/749866.pdf
    Data publikacji:
    2019
    Wydawca:
    Uniwersytet Łódzki. Wydawnictwo Uniwersytetu Łódzkiego
    Tematy:
    correspondence analysis
    invertible rules
    classical propositional logic
    functional completeness
    sequent calculus
    automated deduction
    automated rules generation
    Opis:
    Kooi and Tamminga's correspondence analysis is a technique for designing proof systems, mostly, natural deduction and sequent systems. In this paper it is used to generate sequent calculi with invertible rules, whose only branching rule is the rule of cut. The calculi pertain to classical propositional logic and any of its fragments that may be obtained from adding a set (sets) of rules characterizing a two-argument Boolean function(s) to the negation fragment of classical propositional logic. The properties of soundness and completeness of the calculi are demonstrated. The proof of completeness is conducted by Kalmár's method. Most of the presented sequent-calculus rules have been obtained automatically, by a rule-generating algorithm implemented in Python. Correctness of the algorithm is demonstrated. This automated approach allowed us to analyse thousands of possible rules' schemes, hundreds of rules corresponding to Boolean functions, and to nd dozens of those invertible. Interestingly, the analysis revealed that the presented proof-theoretic framework provides a syntactic characteristics of such an important semantic property as functional completeness.
    Źródło:
    Bulletin of the Section of Logic; 2019, 48, 1
    0138-0680
    2449-836X
    Pojawia się w:
    Bulletin of the Section of Logic
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-8 z 8

      Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies