Calculation of the proposals
See also: Deduction
General introductionEnough complexes to define in general, the concept of proposal was the subject of many debates during the history of the logique ; the consensual idea is that a proposal is a syntactic construction for which it makes direction of speaking about truth. In Logical mathematics, the calculation of the proposals is the first stage in the definition of logic and the reasoning. It defines the rules of deduction which connect the proposals between them, without examining the contents of it; it is thus a first stage in the construction of the Calcul of the predicates, which him is interested in the contents of the proposals and which are a completed formalization of the mathematical reasoning.
If one places in the traditional Logique, the propositional calculus is an algebraic structure which one calls Boolean algebra.
Though the calculation of the proposals does not deal with the contents of the proposals, but only of their relations, it can be interesting to discuss what could be these contents. A proposal gives information on a state of affair. Thus “2 + 2 = 4” or “it book is open” to take two very simple examples are two proposals in this direction. In a general way a state of affair can be a scientific truth, a fact empirically observable, a mathematical formula. In addition, a proposal can be true or false (or of unspecified statute if one agrees to leave traditional logic). This is why an optative sentence (which expresses a wish as for example “That God protects us! ”) or an imperative sentence (“come! ”, “keep silent yourself! ”) or an interrogation are not proposals. “That God protects us!” for example can be neither true nor false: it does nothing but express one wish of the speaker. On the other hand, a sentence like “ always in this calculation, all the data-processing variables is strictly positive ” is a proposal whose contents were modified by the “method” always , this type of proposal is studied in the modal Logique, more precisely the temporal Logique in this case.
All the mathematical statements do not have vocation to be proposals, ains the statement “ X > 0 ” does not have this vocation, because it depends on the variable X , on the other hand a statement like does not depend any more a , because in a certain way is hidden there, one could have just as easily written and, as for the proposals, one can raise the question to know if it is true or if it is false. Instead of calling it a proposal, the calculation of the predicates calls such a statement a closed formula .
Definition of a deductive system
A calculation or a deductive system is, in logic, a whole of rules allowing in a number finished of stages, according to explicit rules and processes which can be mechanized to determine if a proposal is true. Such a process is called a demonstration . One also associates with the proposals a mathematical structure which makes it possible to guarantee that this reasoning or demonstrations has direction, one says that him a semantics was given. In traditional calculation of the proposals, this semantics is consisted of the two elements true and false (often noted 1 and 0 ), when one gives direction to a proposal one gives him is the value true one says whereas it is about a tautology , that is to say the value false , one says whereas it is about a antilogy .
In the theories of mathematical logic, one thus considers two points of view known as syntactic and Sémantique, it is the calculation case of the proposals.
- syntactic Aspect : it is initially a question of defining the language of the calculation of the proposals by the rules of formation of the proposals, then to describe the rules of inference allowing the deduction of proposals from others. These rules of Déduction make it possible to generate specific proposals which one calls of the theorems .
- semantic Aspect : one gives a direction to the symbols representing the logical connectors according to the value of truth of the basic proposals (for example: means not). This direction is given, for example, by truth tables or model of Kripke.
The perfect correspondence between the deduction and semantics is called the complétude.
The system exposed below is within the framework of the traditional Logique. One will find further a presentation from nontraditional logics. The “traditional” adjective should not be taken in a direction of “normality”, but as an attribute which gave him the Histoire of logic, it could just as easily have been called “Boolean”.
Components of the language
At the base of the syntax of the calculation of the proposals there are the variable propositional or atomic , noted proposals p , Q , etc, forming an infinite unit Dénombrable. The second basic components of the language of the calculation of the proposals are the operators or connectors . In fact symbols make it possible to build more elaborate proposals. Most current of these logical connectors are and , or , not , implies , is equivalent . One considers often also the constant which aims at representing the false . Beside these symbols one uses brackets to raise ambiguities in the formulas though one can do some, as in the Polish Notation, invented by the Polish logician Jan Łukasiewicz. However after, for example, of Christopher Strachey, the logicians less and less give attention to syntax concretes selected to devote themselves to the bottom of the things: the deduction and semantics. They thus use conventions like associativeness for raising ambiguities and saving brackets.
A whole of propositional connectors is complete if any connector can be defined by means of the connectors of the unit. For example, in traditional logic, the unit are complete. Thus for example disjunction is defined par : . The unit made up of the only connector of incompatibility of Sheffer, noted by a bar | is also complete, because the connectors can be defined as follows:
- * is equivalent to
- * is equivalent to .
Well formed formulas or proposals
The calculation of the proposals rests moreover on rules of formation indicating how to build well built or “well formed” syntactic complex proposals.
A proposal or well formed formula (noted thereafter , , or , , ) is defined by induction on the structure of the expressions as follows:
- a propositional variable is a proposal,
- is a proposal.
- if and are proposals, then , , , and is proposals.
One generally omits the extreme brackets of the formulas.
Examples: If , and are proposals,
is a proposal.
- is a proposal.
- is a proposal.
- is a proposal.
- is not a proposal.
- is a proposal.
It is shown that only the opening brackets are necessary to not-ambiguity reading of the formulas which for this reason are replaced by a point ". " in certain notations. Thus just as the language of logic can have only one single connector (" |" to see supra ) it can have only one single symbol of punctuation (without using the Polish notation, which uses any no, to see supra ). That remains true for the Calcul of the predicates where the Polish notation is not possible any more and whose language can grow rich moreover by a single quantifier.
See also: Theory of the demonstration
The calculation of the proposal will enable us to present the three deductive systems most known. For that, we will limit ourselves to the proposal containing, in addition to the propositional variables, only of the implications, disjunctions and the occurrence of false in other words of . It is admitted that is a abbreviation of . If is a theorem, in other words a proposal which has a demonstration, one notes that by .
The deductive systems use rules of deduction (also called rules of inference ) which are written:
The are called the premises and is called the conclusion.
The deduction in Hilbert
There is only one rule called the modus ponens , it is written:
It can include/understand thus if is a theorem and is a theorem then is a theorem . To that, one can add three axioms for the implication and the false and three axioms for disjunction:
- the axiom is .
- the rule of introduction of the implication :
- the rule of elimination of the implication :
- two rules of introduction of disjunction , right-hand side and left:
- the rule of elimination of disjunction :
- the rule of elimination of the forgery :
Moreover, one needs a rule which is the reduction with the absurdity , necessary in traditional logic:
It will be noticed that the rule of elimination of the implication is very close to the modus ponens , moreover one calls it also modus ponens . It will be noticed that it there not rule of introduction of the false and that the rule of elimination of the false amounts saying that so whole of assumptions I then deduce the false (or the absurdity) from this same unit I can deduce anything. It will be noticed that the reduction with the absurdity is the rule which corresponds to the reasoning not the absurdity: to show , one adds to the assumptions and if the absurdity is obtained, then there is .
Multiensemble S of proposals. séquent is interpreted like the assertion conjunction of the one deduces disjunction from the . The are called the previous and the are called the consequent . If the list of the antecedents is empty one writes , if the list of consequent is empty one writes . A theorem is still one séquent without antecedents and with only one consequent.
the axiom is .
Introduction of the implication on the right :
Introduction of the implication on the left :
Introduction of disjunction on the right :
Introduction of disjunction on the left :
Introduction of the forgery on the right :
Introduction of the forgery on the left , it with the form of an axiom:
A cut translates the attitude of the mathematician who shows a lemma (the proposal) of which it is useful elsewhere in the demonstration of a theorem. This lemma can express something which has nothing to do with the principal theorem, from where the wish to eliminate these lemmas which are like turnings in the progression towards the principal result. A weakening corresponds to the addition of a superfluous proposal either like antecedent, or like consequent.
Examples of theoremsWe indicate a list of theorems below that one can show using the preceding rules, as well as the usual name which is allotted to them by the tradition.
CommentsIt will have been noticed that the three systems use the same symbol , but makes this notation of it is coherent. The format used for the natural deduction is in fact one séquent in which there is only one conclusion, one speaks then about one séquent natural. The format used for the theorems in the systems in Hilbert corresponds to one séquent natural where there is no assumption.
One can show that these three systems are equivalent in the direction where they have the same theorems exactly.
The “traditional” aspect of the calculation of the proposals is obtained, in the system in Hilbert, by the axiom of contraposition , it appears in the natural deduction through the reduction with the absurdity. The calculation of the séquents is traditional, but if one restricts oneself with the séquents with only one consequent, he becomes intuitionalist.
See also: Theory of the models
Semantics determines the rules of interpretations of the proposals. To allot values of truth to each elementary proposal intervening in a proposal amounts choosing a model this proposal.
In a more precise way, the interpretation of a proposal has is the fact of allotting a value of truth (0 or 1) to the propositional variables and to explain how the connectors behave with respect to the values of truth. One gives this behavior by a truth table. In this manner one can give a value 0 or 1 to each proposals which depends on the values taken by the truth tables. There exist three cases of interpretation:
- When the proposal always takes the valur 0 whatever the values of the propositional variables, the proposal is known as being a antilogy or a contradiction . It is also said that it is insatisfiable .
- When the proposal has always takes value 1, has is a tautology . It is also said that has is valid and one will note this assertion .
- If the proposal takes value 1 at least once, one says that has is satisfiable .
- If the proposal takes at least once value 1 and at least once value 0, it is a synthetic or contingent proposal.
Interpretation of the connectorsWe clarify the behavior, then give the associated table
- * will take value 1 if and only so at least one of the two proposals P or Q takes value 1.
- * Land will take value 1 if and only if the two proposals P and Q take simultaneously value 1.
- * will take value 0 if and only if P takes value 1 and Q the value 0.
- * will take value 1 if and only if P takes the value 0.
- * will take value 1 if and only if P and Q have the same value.
- * takes the value 0.
Example 1 :
- is a tautology.
Example 2 :
- is not a tautology.
Propositional calculation thus has several different means “to validate” the proposals: the systems of deduction which show the proposals and defines the theorems and the methods semantic which define the tautologies . The question which installation is to know these these methods coincide.
Decidability, coherence, complétude, compactnessThe fact that any proposal is demonstrable if and only if it is a tautology expresses a property of the propositional calculation which one calls the complétude , that means that the deductive presentation of propositional calculation is equivalent to the semantic presentation. The complétude rests on the following remarks.
- Any proposal shown results from an axiom or application of a rule on already shown proposals. However it is easy to check that the axioms provide tautologies and that the rules preserve tautologies. Any shown proposal is thus a tautology. Propositional calculation is correct .
- the reciprocal one rests on the following fact: one can show that for any proposal propositional calculation there exists a proposal such as and such as is in a form known as normal Land where each is form , where each is literal (i.e. a proposal of the form or ). If is a tautology, then in each , necessarily a propositional variable and its negation appear. If not there would exist which would not check this condition and it would be possible to allot values to the in order to give value 0 to , and thus with itself. But one can show that is demonstrable (), then that it is the same of each , then of itself and finally of . Any tautology is then demonstrable. Propositional calculation is complete .
The article Théorème of complétude of the calculation of the proposals proposes another more detailed demonstration.
It results from the complétude of the calculation of the proposals that:
- the calculation of the proposals is décidable , in the direction where there exists an algorithm making it possible to decide if a proposal is a theorem or not. It is enough to draw up its Truth table and to see whether it is about a tautology.
- the calculation of the proposals is coherent (consistent), i.e. noncontradictory. There does not exist any proposal such as one can have at the same time and because these two proposals would be tautologies and one would have 1 = 0.
- the calculation of the proposals is strongly complete (maximalement coherent), in the direction where any addition of a new diagram of axiom, nondemonstrable in the initial system, makes this system incoherent.
Let us suppose given an infinite number of proposals. Are these proposals simultaneously satisfiables? In other words, do there exist values of truth for their propositional variables which give 1 like value of truth to all the proposals? If the answer is positive for any finished subset of these proposals, then it is it for all the proposals. This property, which ensures that one can passes from all the subsets finished to the entire unit infinite, is called the compactness .
Methods of calculating, Np-complétudeWe saw that, to decide if a proposal is demonstrable, it is enough to check if it is a tautology, i.e. to check if it takes the value of truth 1 whatever the values of truth of its propositional variables.
This brutal approach runs up however against the computing time which it requires. Indeed, if the proposal has propositional N variable, it is necessary to calculate 2 N possible combinations of values for the propositional variables, which quickly becomes unfeasible for large N . Thus, if N = 30, it will be necessary to enumerate more than one billion combinations of values. If N = 100, the computing time necessary to enumerate all these combinations of values exceeds the age of the Universe by far.
There exist certainly possible improvements. For example, if one allots the value of truth 0 to a propositional variable p , one can directly allot value 0 to independently of the later value allotted to p , which decreases the number of calculations to be carried out.
One can also seek to see whether it is possible to invalidate the implications. Let us consider for example the proposal:
But the preceding improvements basically do not change the difficulty of the problem. One is thus in front of the following situation. Being given a proposal F , one wonders whether F is a tautology or not and for this reason, one wonders whether there exist values of truth ascribable to the propositional variables of F which would return F invalid.
- an exhaustive research requires 2 N checks if F has propositional N variable. This step is known as determinist, but its computing time is exponential.
- On the other hand, if F is not a tautology, it is enough to a checking to be made, namely to precisely test the configuration which invalidates F . The computing time ceases being exponential, on the condition of knowing which configuration to test. This one could for example be given by a oracle or an omniscient being. Such a step is known as not determinist.
The question of the insatisfiability of F , as all the problems which are solved according to the method that us have just outlined, are known as NP (for polynomial not determinist). The dual problem is that of the satisfiability of a proposal, namely to find a configuration which gives 1 like value of truth of the proposal. This question, called Problème SAT plays a fundamental role in Théorie of complexity, since one can show that the discovery of a deterministic algorithm in polynomial time for this problem would make it possible to deduce some from the deterministic algorithms in polynomial time for all the problems of the type NP. It is said that SAT (and thus also the problem of the demonstrability of a proposal) is a Np-complete problem .
Boolean algebraThat is to say E the whole of the proposals on a whole of propositional variables. That is to say the binary relation definite on E by equivalence () between two proposals. is a Relation of equivalence on E, compatible with and which gives to the unit quotient E/ a structure of Boolean algebra.
The Boolean algebra can be formalized with only one axiom:
- (P | (Q | R)) | ((T | (T | T)) | ((S | Q) | ((P | S) | (P | S))))
Veroff and McCune showed in 2000 by using their system of automatic Démonstration of theorems which one can formalize the Boolean algebra by the only equation
- ((P | R) | Q) | ((P | (P | Q)) | P) = Q.
Conjunctive normal forms, disjunctive normal forms
A disjunction is a proposal of the form and a conjunction is a proposal of the form Land. A proposal is in conjunctive normal form (FNC) if it is made up of conjunctions of disjunctions . A proposal is in disjunctive normal form (FND) if it is made up of disjunctions of conjunctions .
, , and are at the same time FNC and FND.
- is in conjunctive normal form .
- is in disjunctive normal form .
When each disjunctive block of a FND comprises one and only one occurrence of the same propositional variables, one then speaks about FND distinguished .
When each conjunctive block of a FNC comprises one and only one occurrence of the same propositional variables, one then speaks about FNC distinguished .
is in conjunctive normal form distinguished .
- is in disjunctive normal form distinguished .
One can show that any proposal is equivalent to a FND (by admitting that is the disjunction of an empty set of proposals) and is equivalent to a FNC (by admitting that T is the conjunction of an empty set of proposals). In other words, for any proposal there exists a proposal in disjunctive normal form such as and a proposal in conjunctive normal form such as .
Logic traditional, minimal, intuitionalist
The axioms and rules of propositional calculation that we presented are those of the traditional Logique. They induce the proposal , called Principe of the third excluded, the proposal , called elimination of the double negation and the called Loi of Peirce. This logic rests on the principle which a property P is necessarily true or false. It is one of pillar of the position described as formal, adopted by Hilbert and others. However this position which implies that it there demonstrations which do not build the object satisfying the proven proposal was given causes by several mathematicians, of which most known is Brouwer resulting in creating thereafter the Logique intuitionalist.
We now present two alternatives very close to nontraditional logic, the minimal Logique of I. Johansson (1936) and the Logique intuitionalist of Heyting (1930). The primitive connectors are , , and . One keeps the first two axioms of traditional logic:
Before introducing the negation, one states the axioms relative to :
and those relative to , (duaux of the precedents):
One introduces finally two axioms relating to the negation. The first expresses that, if F implies its own negation, then F is invalid.
- for minimal logic and for logic intuitionalist.
In the presence of a proposal and from its negation, three logics, traditional, intuitionalist and minimal, conclude all three with a contradiction . But the difference relates to the use which one makes of this contradiction:
- traditional logic deduced from the fact that P is true (reasoning by the absurdity).
- logic intuitionalist deduced from a contradiction that any proposal is demonstrable. From , she deduces the validity from , property weaker than .
- minimal logic deduces from a contradiction that any negation of proposal is demonstrable, which is weaker than than proposes logic intuitionalist.
Minimal logic and logical intuitionalist has both the proposal like theorem. On the other hand, is not a theorem of these logics.
In the same way, they make it possible to show but not the reciprocal one. On the other hand, they make it possible to show equivalence between and . Lastly, the proposal is a theorem of logic intuitionalist, but not a theorem of minimal logic.
Glivenko showed into 1929 which is a theorem of traditional propositional calculation if and only if is a theorem of propositional calculation intuitionalist. This result does not extend if one replaces “intuitionalist” by “minimal”. -----
- Gottfried Leibniz - George Boole - Auguste De Morgan - Gottlob Frege - Bertrand Russell - Ludwig Wittgenstein
- Calculation of the predicates
- natural Deduction
- Logical mathematics
- Logical Semantic intuitionalist
- of Kripke, which is a presentation of the model of Kripke
- modal Logique
- general-purpose Logique
- Switching function
- logical Porte
|Random links:||Puy-Guillaume | Maurice Zermatten | The Jordan de Hauteville | Jules-Henri-Marius Bergeret | GeoCities | Magnétisme|