World Library  
Flag as Inappropriate
Email this Article

Completeness (logic)

Article Id: WHEBN0031271451
Reproduction Date:

Title: Completeness (logic)  
Author: World Heritage Encyclopedia
Language: English
Subject: Soundness, Predicate functor logic, Mathematical Logic, Monoidal t-norm logic, Foundations of mathematics
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Completeness (logic)

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. Kurt Gödel, Leon Henkin, and Emil Leon Post all published proofs of completeness. (See History of the Church–Turing thesis.)

Other properties related to completeness

The property converse to completeness is called soundness, or consistency: a system is sound with respect to a property (mostly semantical validity) if each of its theorems has that property.

Forms of completeness

Expressive completeness

A formal language is expressively complete if it can express the subject matter for which it is intended.

Functional completeness

A set of logical connectives associated with a formal system is functionally complete if it can express all propositional functions.

Semantic completeness

Semantic completeness is the converse of soundness for formal systems. A formal system is complete with respect to tautologousness or "semantically complete" when all its tautologies are theorems, whereas a formal system is "sound" when all theorems are tautologies (that is, they are semantically valid formulas: formulas that are true under every interpretation of the language of the system that is consistent with the rules of the system). That is,

\models_{\mathcal S} \varphi\ \to\ \vdash_{\mathcal S} \varphi.[1]

Strong completeness

A formal system S is strongly complete or complete in the strong sense if for every set of premises Γ, any formula which semantically follows from Γ is derivable from Γ. That is:

\Gamma\models_{\mathcal S} \varphi \ \to\ \Gamma \vdash_{\mathcal S} \varphi.

Refutation completeness

A formal system S is refutation-complete if it is able to derive false from every unsatisfiable set of formulas. That is,

\Gamma \models_{\mathcal S} \bot \to\ \Gamma \vdash_{\mathcal S} \bot.[2]

Every strongly complete system is also refutation-complete. Intuitively, strong completeness means that, given a formula set \Gamma, it is possible to compute every semantical consequence \varphi of \Gamma, while refutation-completeness means that, given a formula set \Gamma and a formula \varphi, it is possible to check whether \varphi is a semantical consequence of \Gamma.

Examples of refutation-complete systems include: SLD resolution on Horn clauses, superposition on equational clausal first-order logic, Robinson's resolution on clause sets.[3] The latter is not strongly complete: e.g. \{ a \} \models a \lor b holds even in the propositional subset of first-order logic, but a \lor b cannot be derived from \{ a \} by resolution. However, \{ a, \lnot (a \lor b) \} \vdash \bot can be derived.

Syntactical completeness

A formal system S is syntactically complete or deductively complete or maximally complete if for each sentence (closed formula) φ of the language of the system either φ or ¬φ is a theorem of S. This is also called negation completeness. In another sense, a formal system is syntactically complete if and only if no unprovable sentence can be added to it without introducing an inconsistency. Truth-functional propositional logic and first-order predicate logic are semantically complete, but not syntactically complete (for example, the propositional logic statement consisting of a single propositional variable A is not a theorem, and neither is its negation, but these are not tautologies). Gödel's incompleteness theorem shows that any recursive system that is sufficiently powerful, such as Peano arithmetic, cannot be both consistent and syntactically complete.

References

  1. ^ Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Pres, 1971
  2. ^ David A. Duffy (1991). Principles of Automated Theorem Proving. Wiley.  Here: sect. 2.2.3.1, p.33
  3. ^ Stuart J. Russell, Peter Norvig (1995). Artificial Intelligence: A Modern Approach. Prentice Hall.  Here: sect. 9.7, p.286
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 



Copyright © World Library Foundation. All rights reserved. eBooks from National Public Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.