All Topics  
Formal proof

 

 
   Email Print
   Bookmark   Link
 

 

Formal proof
 
 
  Topics Formal proof Topic Home

see also Mathematical proof
Mathematical proof

In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive reasoning or empirical arguments....
, Proof theory
Proof theory

Proof theory is a branch of mathematical logic that represents Mathematical proofs as formal mathematical objects, facilitating their analysis by mathematical techniques....
, and Axiomatic system
Axiomatic system

In mathematics, an axiomatic system is any Set of axioms from which some or all axioms can be used in conjunction to logically derive theorems....
.


A formal proof or derivation is a finite sequence of sentences
Proposition

This article is about the term proposition in logic and philosophy; for other uses see PropositionIn logic and philosophy, proposition refers to either the "content" or Meaning of a meaningful declarative sentence or the pattern of symbols, marks, or sounds that make up a meaningful declarative sentence....
 (called well-formed formula
Well-formed formula

In computer science and mathematical logic, a well-formed formula or simply formula is a symbol or string of symbols that is generated by the formal grammar of a formal language....
s in the case of a formal language
Formal language

A formal language is a set of words, i.e. finite string of letters, or symbols. The inventory from which these letters are taken is called the alphabet over which the language is defined....
) each of which is an axiom
Axiom

In traditional logic, an axiom or postulate is a proposition that is not proved or demonstrated but considered to be either self-evidence, or subject to necessary decision....
 or follows from the preceding sentences in the sequence by a rule of inference
Rule of inference

In logic, a rule of inference is a function from sets of formulae to formulae. The argument is called the premise set and the value the conclusion....
. The last sentence in the sequence is a theorem
Theorem

In mathematics, a theorem is a statement Mathematical proof on the basis of previously accepted or established statements such as axioms.In formal mathematical logic, the concept of a theorem may be taken to mean a formula that can be formal proof according to the deductive system of a fixed formal system....
 of a formal system
Formal system

In logic, a formal system consists of a formal language together with a deductive system which consists of a set of inference rules and/or axioms....
. The notion of theorem is not in general effective
Effective method

An effective method for a class of problems is a method for which each step in the method may be described as a mechanical operation and which, if followed rigor, and as far as may be necessary, is bound to:...
, therefore there may be no method by which we can always find a proof of a given sentence or determine that none exists.






Discussion
Ask a question about 'Formal proof'
Start a new discussion about 'Formal proof'
Answer questions from other users
Full Discussion Forum



Recent Posts

Formal proof on a theorem on sqrts
A formal proof of the theorem ,0x=0...for all x
Formal proof of 0x=0,laws of logic used








Encyclopedia


see also Mathematical proof
Mathematical proof

In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive reasoning or empirical arguments....
, Proof theory
Proof theory

Proof theory is a branch of mathematical logic that represents Mathematical proofs as formal mathematical objects, facilitating their analysis by mathematical techniques....
, and Axiomatic system
Axiomatic system

In mathematics, an axiomatic system is any Set of axioms from which some or all axioms can be used in conjunction to logically derive theorems....
.


A formal proof or derivation is a finite sequence of sentences
Proposition

This article is about the term proposition in logic and philosophy; for other uses see PropositionIn logic and philosophy, proposition refers to either the "content" or Meaning of a meaningful declarative sentence or the pattern of symbols, marks, or sounds that make up a meaningful declarative sentence....
 (called well-formed formula
Well-formed formula

In computer science and mathematical logic, a well-formed formula or simply formula is a symbol or string of symbols that is generated by the formal grammar of a formal language....
s in the case of a formal language
Formal language

A formal language is a set of words, i.e. finite string of letters, or symbols. The inventory from which these letters are taken is called the alphabet over which the language is defined....
) each of which is an axiom
Axiom

In traditional logic, an axiom or postulate is a proposition that is not proved or demonstrated but considered to be either self-evidence, or subject to necessary decision....
 or follows from the preceding sentences in the sequence by a rule of inference
Rule of inference

In logic, a rule of inference is a function from sets of formulae to formulae. The argument is called the premise set and the value the conclusion....
. The last sentence in the sequence is a theorem
Theorem

In mathematics, a theorem is a statement Mathematical proof on the basis of previously accepted or established statements such as axioms.In formal mathematical logic, the concept of a theorem may be taken to mean a formula that can be formal proof according to the deductive system of a fixed formal system....
 of a formal system
Formal system

In logic, a formal system consists of a formal language together with a deductive system which consists of a set of inference rules and/or axioms....
. The notion of theorem is not in general effective
Effective method

An effective method for a class of problems is a method for which each step in the method may be described as a mechanical operation and which, if followed rigor, and as far as may be necessary, is bound to:...
, therefore there may be no method by which we can always find a proof of a given sentence or determine that none exists. The concept of deduction
Deduction

Deduction can refer to one of the following usages: lower price on something* Deductive reasoning, inference in which the conclusion is of no greater generality than the premises...
 is a generalization
Generalization

Generalization is a foundational element of logic and reasoning. Generalization posits the existence of a domain or Set theory of elements, as well as one or more common characteristics shared by those elements....
 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 formulae in the proof sequence.

Formal proofs often are constructed with the help of computers in interactive theorem proving
Interactive theorem proving

Interactive theorem proving is the field of computer science and mathematical logic concerned with tools to develop formal proofs by man-machine collaboration....
. Significantly, these proofs can be checked automatically, also by computer. Checking formal proofs is usually simple, whereas finding proofs (automated theorem proving
Automated theorem proving

Automated theorem proving or automated deduction, currently the most well-developed subfield of automated reasoning , is the mathematical proof of mathematical theorems by a computer program....
) is generally computationally hard.

Background


Formal language


A formal language is an organized set
Set

A set is a collection of distinct objects, considered as an object in its own right. Sets are one of the most fundamental concepts in mathematics....
 of symbol
Symbol

A symbol is something such as an entity, picture, written word, sound, or particular mark that represents something else by association, resemblance, or convention....
s the essential feature of which is that it can be precisely defined in terms of just the shapes and locations of those symbols. Such a language can be defined, then, without any reference
Reference

A reference is a relation between Object in which one object designates by linking to another object. Such relations as these may occur in a variety of domains, including logic, computer science, time, art and scholarship....
 to any meaning
Meaning (linguistics)

Linguistic strings can be made up of phenomena such as words, phrases, and sentences, each of which has a different kind of meaning. Individual words, such as the word "bachelor", refer to some abstract concept....
s of any of its expressions; it can exist before any formal interpretation is assigned to it – that is, before it has any meaning. Formal proofs are expressed in some formal language

Formal grammar


A formal grammar (also called formation rules) is a precise description of the well-formed formula
Well-formed formula

In computer science and mathematical logic, a well-formed formula or simply formula is a symbol or string of symbols that is generated by the formal grammar of a formal language....
s of a formal language. It is synonymous with the set
Set

A set is a collection of distinct objects, considered as an object in its own right. Sets are one of the most fundamental concepts in mathematics....
 of strings
String (computer science)

In computer programming and some branches of mathematics, a string is an ordered sequence of symbols. These symbols are chosen from a predetermined set or alphabet....
 over the alphabet
Alphabet

An alphabet is a standardized set of letter basic written symbols each of which roughly represents a phoneme, a spoken language, either as it exists now or as it was in the past....
 of the formal language which constitute well formed formulas. However, it does not describe their semantics
Semantics

Semantics is the study of meaning in communication. The word is derived from the Greek language word s??a?t???? , "significant", from s??a??? , "to signify, to indicate" and that from s??a , "sign, mark, token"....
 (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 axiom
Axiom

In traditional logic, an axiom or postulate is a proposition that is not proved or demonstrated but considered to be either self-evidence, or subject to necessary decision....
s, or have both. A formal system is used to derive
Proof theory

Proof theory is a branch of mathematical logic that represents Mathematical proofs as formal mathematical objects, facilitating their analysis by mathematical techniques....
 one expression from one or more other expressions.

Formal 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 formal interpretations is called formal semantics. Giving an interpretation is synonymous with constructing a model
Structure (mathematical logic)

In universal algebra and in model theory, a structure consists of an underlying Set along with a collection of finitary functions and relations which are defined on it....
.

External links