Completeness (logic) (original) (raw)
In mathematical logic and metalogic, a formal system is called complete with respect to a particular property if every formula having the property can be derived using that system, i.e. is one of its theorems; otherwise the system is said to be incomplete.The term "complete" is also used without qualification, with differing meanings depending on the context, mostly referring to the property of semantical validity. Intuitively, a system is called complete in this particular sense, if it can derive every formula that is true.
| Property | Value |
|---|---|
| dbo:abstract | In mathematical logic and metalogic, a formal system is called complete with respect to a particular property if every formula having the property can be derived using that system, i.e. is one of its theorems; otherwise the system is said to be incomplete.The term "complete" is also used without qualification, with differing meanings depending on the context, mostly referring to the property of semantical validity. Intuitively, a system is called complete in this particular sense, if it can derive every formula that is true. (en) Der Begriff Vollständigkeit hat in der Logik verschiedene Bedeutungen. Er bezeichnet zwei unterschiedliche Eigenschaften formaler Systeme bzw. Kalküle: * Vollständigkeit von Theorien * Vollständigkeit von Kalkülen Daneben wird dieser Begriff auch im Sinne der * funktionalen Vollständigkeit von Junktorenmengen benutzt. (de) En metalógica, la completitud o completitud semántica es la propiedad metateórica que tienen los sistemas formales cuando todas las fórmulas lógicamente válidas (todas las verdades lógicas) del sistema son además teoremas del sistema. Es decir, cuando el conjunto de las verdades lógicas del sistema es un subconjunto del conjunto de teoremas. En otras palabras, si A es una fórmula cualquiera del lenguaje y S es el sistema formal bajo consideración, entonces se cumple que: Si entonces El segundo teorema de incompletitud de Gödel demuestra que ningún sistema (definido recursivamente) con cierto poder expresivo puede ser a la vez consistente y semánticamente completo. Por otra parte, la completitud sintáctica es la propiedad que tienen los sistemas formales cuando, para toda fórmula del lenguaje del sistema, o bien es un teorema o bien su negación lo es. Esto es, existe una prueba para cada fórmula o para su negación. La lógica proposicional y la lógica de primer orden son ambas semánticamente completas, pero no sintácticamente completas. Por ejemplo, en la lógica proposicional, la fórmula p no es un teorema, y tampoco lo es su negación, de modo que eso basta para mostrar que no es sintácticamente completa. No obstante, como ninguna de esas dos fórmulas es una verdad lógica, no afectan a la completitud semántica del sistema. Otra propiedad metateórica distinta es la completitud semántica fuerte, que dice: si en un sistema formal S, A es una fórmula bien formada cualquiera que es una consecuencia semántica de un conjunto de fórmulas, entonces existe una derivación de A a partir de . En símbolos: Si entonces (es) En logique mathématique et métalogique, un système formel est dit complet par rapport à une propriété particulière si chaque formule possédant cette propriété peut être prouvée par une démonstration formelle à l'aide de ce système, c'est-à-dire par l'un de ses théorèmes ; autrement, le système est dit incomplet. Le terme « complet » est également utilisé sans qualification, avec des significations différentes selon le contexte, la plupart du temps se référant à la propriété de la validité sémantique. Intuitivement, dans ce sens particulier, un système est dit complet si toute formule vraie y est démontrable. Kurt Gödel, et ont tous publié des preuves de complétude. (Voir la thèse de Church-Turing.) (fr) 数理論理学には完全性（かんぜんせい、英: completeness）と呼ばれる二つの関連するが異なる概念がある。 1. * 意味論的完全性: 形式論理体系が「恒真である命題が必ず証明できる」という性質を持つこと 2. * 構文論的完全性: 形式論理体系における理論が「（その理論で用いている言語で表現可能な）どの命題についても、肯定または否定を証明できる」という性質を持つこと ゲーデルが証明したゲーデルの完全性定理は一階述語論理が意味論的完全性の意味で完全であるとする。 同じくゲーデルが証明した有名な不完全性定理は、自然数論についてのある理論が 後者の意味では完全ではなく、完全であるように拡張すること（超越的な操作抜きには）もできないことを示した。現在では不完全性定理はPAなど他の自然数論の公理系や自然数論以外の公理系についても証明されており、一定の性質を満たす公理系であれば広く成り立つ定理であると理解されている。 (ja) 논리학에서 완전성(完全性, 영어: completeness)이란, 형식 체계 내에서 모든 참인 문장이 증명 가능한 성질이다. 더욱 일반화하면, 특정 성질을 가진 명제가 도출 가능한 성질을 가리킨다. (ko) Nella logica matematica il concetto di completezza esprime il fatto che un insieme di assiomi è sufficiente a dimostrare tutte le verità di una teoria e quindi a decidere della verità o falsità di qualunque enunciato formulabile nel linguaggio della teoria. (it) Ett axiomatiskt uppbyggt system eller ett formellt system är fullständigt, om allt det, som man önskar skall vara ett teorem i systemet också är ett teorem. Mer precist uttryckt är ett formellt system S, med språket L, fullständigt om och endast om varje tautologi i L är ett teorem i S. Man skiljer på semantiskt fullständiga system och syntaktiska sådana. (sv) Em lógica matemática e na metalógica, um sistema formal é chamado completo com respeito a uma propriedade específica se toda fórmula tendo a propriedade pode ser obtida usando esse sistema, isto é, é um de seus teoremas; caso contrário, o sistema é dito incompleto.O termo "completo" também é usado sem qualificação, com significados diferentes dependendo do contexto, geralmente se referindo à propriedade da validade semântica. Intuitivamente, um sistema é chamado de completo nesse sentido particular, se ele pode obter todas as fórmulas verdadeiras.Kurt Gödel, Leon Henkin, e Emil Leon Post publicaram provas de completude. (pt) Повнота (або неповнота) у математичній логіці та металогіці — характеристика формальної системи. Систему називають повною стосовно деякої властивості, якщо кожна формула системи з даною властивістю може бути доведена за допомогою цієї системи (тобто є однією з теорем системи). У протилежному випадку система називається неповною. Поняття повноти також використовується у інших значеннях, що можуть залежати від контексту, найчастіше стосовно семантичної валідності. З інтуїтивної точки зору, система є повною , якщо в її межах можна вивести кожну формулу, яка є істинною. Докази повноти було опубліковано в різні роки Куртом Геделем, Леоном Генкіном і (див. історію тези Черча–Тюрінга). (uk) |
| dbo:wikiPageID | 31271451 (xsd:integer) |
| dbo:wikiPageLength | 6530 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1115325560 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Propositional_calculus dbr:Modal_logic dbr:Metalogic dbr:Peano_arithmetic dbr:Resolution_(logic) dbr:Validity_(logic) dbr:Interpretation_(logic) dbc:Proof_theory dbr:Mathematical_logic dbr:Converse_(logic) dbr:Theorem dbr:Clause_(logic) dbr:Complete_theory dbr:Functional_completeness dbr:Horn_clause dbr:Superposition_calculus dbr:Admissible_rule dbr:Gödel's_completeness_theorem dbr:Propositional_function dbr:False_(logic) dbr:First-order_logic dbr:Formal_language dbr:Formal_proof dbr:Formal_system dbr:Logical_connective dbr:Well-formed_formula dbr:Property_(philosophy) dbr:Gödel's_incompleteness_theorems dbr:Tautology_(logic) dbc:Mathematical_logic dbc:Model_theory dbc:Metalogic dbr:SLD_resolution dbr:Sentence_(mathematical_logic) dbr:Soundness dbr:Superintuitionistic_logic |
| dbp:wikiPageUsesTemplate | dbt:Distinguish dbt:Main dbt:Reflist dbt:Short_description dbt:Mathcal dbt:Mathematical_logic |
| dct:subject | dbc:Proof_theory dbc:Mathematical_logic dbc:Model_theory dbc:Metalogic |
| rdf:type | owl:Thing |
| rdfs:comment | In mathematical logic and metalogic, a formal system is called complete with respect to a particular property if every formula having the property can be derived using that system, i.e. is one of its theorems; otherwise the system is said to be incomplete.The term "complete" is also used without qualification, with differing meanings depending on the context, mostly referring to the property of semantical validity. Intuitively, a system is called complete in this particular sense, if it can derive every formula that is true. (en) Der Begriff Vollständigkeit hat in der Logik verschiedene Bedeutungen. Er bezeichnet zwei unterschiedliche Eigenschaften formaler Systeme bzw. Kalküle: * Vollständigkeit von Theorien * Vollständigkeit von Kalkülen Daneben wird dieser Begriff auch im Sinne der * funktionalen Vollständigkeit von Junktorenmengen benutzt. (de) En logique mathématique et métalogique, un système formel est dit complet par rapport à une propriété particulière si chaque formule possédant cette propriété peut être prouvée par une démonstration formelle à l'aide de ce système, c'est-à-dire par l'un de ses théorèmes ; autrement, le système est dit incomplet. Le terme « complet » est également utilisé sans qualification, avec des significations différentes selon le contexte, la plupart du temps se référant à la propriété de la validité sémantique. Intuitivement, dans ce sens particulier, un système est dit complet si toute formule vraie y est démontrable. Kurt Gödel, et ont tous publié des preuves de complétude. (Voir la thèse de Church-Turing.) (fr) 数理論理学には完全性（かんぜんせい、英: completeness）と呼ばれる二つの関連するが異なる概念がある。 1. * 意味論的完全性: 形式論理体系が「恒真である命題が必ず証明できる」という性質を持つこと 2. * 構文論的完全性: 形式論理体系における理論が「（その理論で用いている言語で表現可能な）どの命題についても、肯定または否定を証明できる」という性質を持つこと ゲーデルが証明したゲーデルの完全性定理は一階述語論理が意味論的完全性の意味で完全であるとする。 同じくゲーデルが証明した有名な不完全性定理は、自然数論についてのある理論が 後者の意味では完全ではなく、完全であるように拡張すること（超越的な操作抜きには）もできないことを示した。現在では不完全性定理はPAなど他の自然数論の公理系や自然数論以外の公理系についても証明されており、一定の性質を満たす公理系であれば広く成り立つ定理であると理解されている。 (ja) 논리학에서 완전성(完全性, 영어: completeness)이란, 형식 체계 내에서 모든 참인 문장이 증명 가능한 성질이다. 더욱 일반화하면, 특정 성질을 가진 명제가 도출 가능한 성질을 가리킨다. (ko) Nella logica matematica il concetto di completezza esprime il fatto che un insieme di assiomi è sufficiente a dimostrare tutte le verità di una teoria e quindi a decidere della verità o falsità di qualunque enunciato formulabile nel linguaggio della teoria. (it) Ett axiomatiskt uppbyggt system eller ett formellt system är fullständigt, om allt det, som man önskar skall vara ett teorem i systemet också är ett teorem. Mer precist uttryckt är ett formellt system S, med språket L, fullständigt om och endast om varje tautologi i L är ett teorem i S. Man skiljer på semantiskt fullständiga system och syntaktiska sådana. (sv) Em lógica matemática e na metalógica, um sistema formal é chamado completo com respeito a uma propriedade específica se toda fórmula tendo a propriedade pode ser obtida usando esse sistema, isto é, é um de seus teoremas; caso contrário, o sistema é dito incompleto.O termo "completo" também é usado sem qualificação, com significados diferentes dependendo do contexto, geralmente se referindo à propriedade da validade semântica. Intuitivamente, um sistema é chamado de completo nesse sentido particular, se ele pode obter todas as fórmulas verdadeiras.Kurt Gödel, Leon Henkin, e Emil Leon Post publicaram provas de completude. (pt) Повнота (або неповнота) у математичній логіці та металогіці — характеристика формальної системи. Систему називають повною стосовно деякої властивості, якщо кожна формула системи з даною властивістю може бути доведена за допомогою цієї системи (тобто є однією з теорем системи). У протилежному випадку система називається неповною. Поняття повноти також використовується у інших значеннях, що можуть залежати від контексту, найчастіше стосовно семантичної валідності. З інтуїтивної точки зору, система є повною , якщо в її межах можна вивести кожну формулу, яка є істинною. Докази повноти було опубліковано в різні роки Куртом Геделем, Леоном Генкіном і (див. історію тези Черча–Тюрінга). (uk) En metalógica, la completitud o completitud semántica es la propiedad metateórica que tienen los sistemas formales cuando todas las fórmulas lógicamente válidas (todas las verdades lógicas) del sistema son además teoremas del sistema. Es decir, cuando el conjunto de las verdades lógicas del sistema es un subconjunto del conjunto de teoremas. En otras palabras, si A es una fórmula cualquiera del lenguaje y S es el sistema formal bajo consideración, entonces se cumple que: Si entonces Si entonces (es) |
| rdfs:label | Vollständigkeit (Logik) (de) Completitud (lógica) (es) Completeness (logic) (en) Complétude (logique) (fr) Completezza (logica matematica) (it) 완전성 (ko) 完全性 (ja) Completude (lógica) (pt) Fullständighet (logik) (sv) Повнота (логіка) (uk) |
| owl:differentFrom | dbr:Complete_(complexity) |
| owl:sameAs | freebase:Completeness (logic) wikidata:Completeness (logic) dbpedia-de:Completeness (logic) dbpedia-es:Completeness (logic) dbpedia-fa:Completeness (logic) dbpedia-fr:Completeness (logic) http://hy.dbpedia.org/resource/Լրիվություն dbpedia-it:Completeness (logic) dbpedia-ja:Completeness (logic) dbpedia-ko:Completeness (logic) dbpedia-pt:Completeness (logic) dbpedia-sv:Completeness (logic) dbpedia-uk:Completeness (logic) https://global.dbpedia.org/id/ZZqm |
| prov:wasDerivedFrom | wikipedia-en:Completeness_(logic)?oldid=1115325560&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Completeness_(logic) |
| is dbo:wikiPageDisambiguates of | dbr:Completeness |
| is dbo:wikiPageRedirects of | dbr:Incomplete_(logic) dbr:Refutation-complete dbr:Refutation_completeness dbr:Deductive_completeness dbr:Strong_completeness dbr:Syntactic_completeness dbr:Complete_(logic) dbr:Completeness_(in_logic) dbr:Semantic_completeness |
| is dbo:wikiPageWikiLink of | dbr:Carla_Gomes dbr:Bayesian_programming dbr:Beam_search dbr:Principia_Mathematica dbr:Program_synthesis dbr:Proof_of_impossibility dbr:Proof_sketch_for_Gödel's_first_incompleteness_theorem dbr:Propositional_calculus dbr:Quine–Putnam_indispensability_argument dbr:Metalogic dbr:Metatheory dbr:Algorithmic_program_debugging dbr:Peano_axioms dbr:Resolution_(logic) dbr:DPLL_algorithm dbr:David_Makinson dbr:Dynamic_epistemic_logic dbr:ESC/Java dbr:Incomplete_(logic) dbr:Index_of_logic_articles dbr:Index_of_philosophy_articles_(A–C) dbr:Index_of_philosophy_articles_(I–Q) dbr:Infinitary_logic dbr:Tarski's_axioms dbr:Penrose–Lucas_argument dbr:Presburger_arithmetic dbr:Propositional_proof_system dbr:String_diagram dbr:Consistency dbr:ZX-calculus dbr:Ehud_Shapiro dbr:Glossary_of_artificial_intelligence dbr:Contradiction dbr:Theorem dbr:State_space dbr:Orchestrated_objective_reduction dbr:Refutation-complete dbr:Refutation_completeness dbr:Andrzej_Grzegorczyk dbr:Armstrong's_axioms dbr:Legal_English dbr:Logic dbr:Simply_typed_lambda_calculus dbr:Functional_dependency dbr:Deductive_completeness dbr:Joseph_Sgro dbr:Key_exchange dbr:Kripke_semantics dbr:Leon_Henkin dbr:Automated_theorem_proving dbr:Willard_Van_Orman_Quine dbr:Distributed_constraint_optimization dbr:Join_dependency dbr:Law_of_excluded_middle dbr:Laws_of_Form dbr:DE-9IM dbr:Datalog dbr:First-order_logic dbr:Formalism_(philosophy_of_mathematics) dbr:Discrete_mathematics dbr:Failure_detector dbr:Farkas'_lemma dbr:Formal_system dbr:Foundations_of_geometry dbr:Foundations_of_mathematics dbr:History_of_logic dbr:Knowledge_representation_and_reasoning dbr:List_of_Hilbert_systems dbr:Predicate_functor_logic dbr:Relation_algebra dbr:2-satisfiability dbr:Gérard_Huet dbr:Hindley–Milner_type_system dbr:Tautology_(logic) dbr:Hypersequent dbr:Absolute_geometry dbr:Zeroth-order_logic dbr:Axiomatic_system dbr:BL_(logic) dbr:Bunched_logic dbr:Implicational_propositional_calculus dbr:Kurt_Gödel dbr:Search_algorithm dbr:Second-order_logic dbr:X-Machine_Testing dbr:Sequent_calculus dbr:Model_of_hierarchical_complexity dbr:Monoidal_t-norm_logic dbr:Turing_machine dbr:SLD_resolution dbr:Soundness dbr:Nicod's_axiom dbr:Completeness dbr:Philosophical_logic dbr:Evolutionary_computation dbr:Finitism dbr:Mr._Meeseeks dbr:T-norm_fuzzy_logics dbr:Philosophy_of_logic dbr:Revision_theory dbr:Outline_of_logic dbr:Truth-value_semantics dbr:Strong_completeness dbr:Syntactic_completeness dbr:Complete_(logic) dbr:Completeness_(in_logic) dbr:Semantic_completeness |
| is dbp:occupation of | dbr:Mr._Meeseeks |
| is owl:differentFrom of | dbr:Completeness_of_the_real_numbers |
| is foaf:primaryTopic of | wikipedia-en:Completeness_(logic) |