logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the study of deductively valid inferences or logical truths. It examines how conclusions follow from premises based on the structure o ...

and

mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, a formal proof or derivation is a finite

sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...

of sentences (known as

well-formed formula In mathematical logic, propositional logic and predicate logic, a well-formed formula, abbreviated WFF or wff, often simply formula, is a finite sequence of symbols from a given alphabet that is part of a formal language. The abbreviation wf ...

s when relating to formal language), each of which is an

axiom An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that which is thought worthy or ...

, an assumption, or follows from the preceding sentences in the sequence, according to the

rule of inference Rules of inference are ways of deriving conclusions from premises. They are integral parts of formal logic, serving as norms of the Logical form, logical structure of Validity (logic), valid arguments. If an argument with true premises follows a ...

. It differs from a natural language argument in that it is rigorous, unambiguous and mechanically verifiable. If the set of assumptions is empty, then the last sentence in a formal proof is called a

theorem In mathematics and formal logic, a theorem is a statement (logic), statement that has been Mathematical proof, proven, or can be proven. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to esta ...

of the formal system. The notion of theorem is generally effective, but there may be no method by which we can reliably find proof of a given sentence or determine that none exists. The concepts of Fitch-style proof, sequent calculus and natural deduction are generalizations of the concept of proof. The theorem is a syntactic consequence of all the well-formed formulas preceding it in the proof. For a well-formed formula to qualify as part of a proof, it must be the result of applying a rule of the deductive apparatus (of some formal system) to the previous well-formed formulas in the proof sequence. Formal proofs often are constructed with the help of computers in interactive theorem proving (e.g., through the use of proof checker and automated theorem prover). Significantly, these proofs can be checked automatically, also by computer. Checking formal proofs is usually simple, while the problem of ''finding'' proofs (automated theorem proving) is usually computationally intractable and/or only semi-decidable, depending upon the formal system in use.

Background

Formal language

A ''formal language'' is a set of finite sequences of

symbol A symbol is a mark, Sign (semiotics), sign, or word that indicates, signifies, or is understood as representing an idea, physical object, object, or wikt:relationship, relationship. Symbols allow people to go beyond what is known or seen by cr ...

s. Such a language can be defined without

reference A reference is a relationship between objects in which one object designates, or acts as a means by which to connect to or link to, another object. The first object in this relation is said to ''refer to'' the second object. It is called a ''nam ...

to any meanings of any of its expressions; it can exist before any interpretation is assigned to it – that is, before it has any meaning. Formal proofs are expressed in some formal languages.

Formal grammar

A ''formal grammar'' (also called ''formation rules'') is a precise description of the

s of a formal language. It is synonymous with the set of strings over the

alphabet An alphabet is a standard set of letter (alphabet), letters written to represent particular sounds in a spoken language. Specifically, letters largely correspond to phonemes as the smallest sound segments that can distinguish one word from a ...

of the formal language which constitute well formed formulas. However, it does not describe their

semantics Semantics is the study of linguistic Meaning (philosophy), meaning. It examines what meaning is, how words get their meaning, and how the meaning of a complex expression depends on its parts. Part of this process involves the distinction betwee ...

(i.e. what they mean).

Formal systems

A ''formal system'' (also called a ''logical calculus'', or a ''logical system'') consists of a formal language together with a deductive apparatus (also called a ''deductive system''). The deductive apparatus may consist of a set of transformation rules (also called ''inference rules'') or a set of

s, or have both. A formal system is used to derive one expression from one or more other expressions.

Interpretations

An ''interpretation'' of a formal system is the assignment of meanings to the symbols, and truth values to the sentences of a formal system. The study of interpretations is called formal semantics. ''Giving an interpretation'' is synonymous with ''constructing a

model A model is an informative representation of an object, person, or system. The term originally denoted the plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin , . Models can be divided in ...

References

External links

*
2πix.com: Logic
Part of a series of articles covering mathematics and logic.
Archive of Formal Proofs

Mizar Home Page
* Pr∞fWiki
Definition:Proof System/Formal Proof
{{Authority control Formal languages Proof theory Formal systems Syntax (logic) Logical truth de:Axiomatischer Beweis