# GetWiki

*completeness (logic)*

ARTICLE SUBJECTS

being →

database →

ethics →

fiction →

history →

internet →

language →

linux →

logic →

method →

news →

policy →

purpose →

religion →

science →

software →

truth →

unix →

wiki →

ARTICLE TYPES

essay →

feed →

help →

system →

wiki →

ARTICLE ORIGINS

critical →

forked →

imported →

original →

completeness (logic)

[ temporary import ]

**please note:**

- the content below is remote from Wikipedia

- it has been imported raw for GetWiki

**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.

## Other properties related to completeness

The property converse to completeness is called soundness: 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.Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Pres, 1971

### Strong completeness

A formal system {{mathcal|S}} is**strongly complete**or

**complete in the strong sense**if for every set of premises Î“, any formula that semantically follows from Î“ is derivable from Î“. That is:

Gammamodels_{mathcal S} varphi to Gamma vdash_{mathcal S} varphi.

### Refutation completeness

A formal system {{mathcal|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.BOOK, David A. Duffy, Principles of Automated Theorem Proving, 1991, Wiley, Here: sect. 2.2.3.1, p.33

*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.BOOK, Stuart J. Russell, Peter Norvig, (Artificial Intelligence: A Modern Approach), 1995, Prentice Hall, Here: sect. 9.7, p.286 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 {{mathcal|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 {{mathcal|S}}. This is also called

**negation completeness**, and is stronger than semantic 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). 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.

### Structural completeness

In superintuitionistic and modal logics, a logic is**structurally complete**if every admissible rule is derivable.

## References

{{reflist}}**- content above as imported from Wikipedia**

- "

- time: 12:57am EDT - Mon, Sep 23 2019

- "

__completeness (logic)__" does not exist on GetWiki (yet)- time: 12:57am EDT - Mon, Sep 23 2019

[ this remote article is provided by Wikipedia ]

LATEST EDITS [ see all ]

GETWIKI 09 JUL 2019

GETWIKI 09 MAY 2016

GETWIKI 18 OCT 2015

GETWIKI 20 AUG 2014

GETWIKI 19 AUG 2014

© 2019 M.R.M. PARROTT | ALL RIGHTS RESERVED