Éléments de logique mathématique

Objet de la logique mathématique

En logique mathématique, on s'intéresse à la véracité d'une affirmation, aussi appelée proposition (P). Typiquement, une affirmation peut-être vraie (V), fausse (F), ou ni-vraie ni-fausse. Par exemple,

En mathématique, on se limite généralement au cas des affimations qui sont vérifiables et que l'on peut qualifier de vraies ou de fausses.

Bien qu'il existe des affirmations universellement vraies, comme "un chien est un animal", la majorité des affirmations sont vraies seulement si une certaine condition est vraie. C'est le cas de l'affirmation P: "si T est un triangle rectangle, alors le carré de l'hypothénuse est égal à la somme du carré des cotés". Elle est composée de 2 sous-affirmations liées ensembles:

Il existe plusieurs symboles, connecteurs logiques, quantificateurs, etc, qui permettent de combiner les affirmations entres-elles. Ils traduisent les idées correspondantes aux mots "alors", "et", "ou", "négation", etc. Les plus courants étant:

Afin de simplifier l'écriture des expressions logiques en limitant l'utilisation des parenthèses, on convient d'un ordre de priorité dans l'application des opérateurs logiques:

On peut donc réécrire P en fonction de P1 et P2 via, P: (P1 ⇒ P2). Les parenthèses sont optionnelles, mais peuvent devenir essentielles dans une expression complexe. Par exemple, les expressions de gauche sont équivalentes à celles de droite:
P∧Q⇒R (P∧Q)⇒R
¬P⇒¬Q (¬P)⇒(¬Q)
¬P∨S⇒¬Q⇔R ( ((¬P)∨S)⇒(¬Q) )⇔R

On appelle souvent ces affirmations des propositions, ou des expressions logiques, ou des énoncés, et les divers éléments connectés entre-eux des termes.

Nous allons étudier 2 aspects de la logique mathématique:

  1. comment déterminer la véracité d'une expression logique en fonction de la véracité de ses termes
  2. comment construire, via des règles d'inférences, de nouvelles expressions à partir d'expressions données

La première partie est relativement mécanique et se fait souvent avec une simple table de vérité. La seconde partie est beaucoup plus difficile et nécessite l'application judicieuse de règles d'inférences. Elle est à la base même des méthodes de démonstration en mathématique.

La logique a été étudiée par plusieurs philosophes et mathématiciens à partir du grec Aristote il y a plus de 2300 ans. Le mathématicien irlandais Boole fut le premier à formaliser la logique des propositions (logique propositionnelle) dans un livre publié en 1854.

Terminons cette section par quelques exemples d'affirmations vraies:

Remarque: lorsque le contexte est clair, il est courant d'omettre d'écrire l'ensemble de référence pour les quantificateurs universels ∀ et ∃.

Logique propositionnelle

On présente souvent les éventualités relatives à la véracité d'une expression logique en fonction des cas possibles de véracité de ses termes dans un tableau appelé "table de vérité". En voici quelques exemples classiques.

Soit p un énoncé pouvant être vrai ou faux, la table de la négation ¬p est:
p ¬p
V F
F V

Soit p et q deux énoncés pouvant être vrais ou faux, la table de la disjonction p∨q et de la conjonction p∧q est:
p q p∨q p∧q
V V V V
V F V F
F V V F
F F F F

On remarque immédiatement une resemblance avec les tableaux d'appartenance des éléments d'un ensemble que l'on utilise en théorie des ensembles pour démontrer des équations ensemblistes. Par exemple, on remarque que si les 2 premières colonnes du tableau ci-dessus représentent l'appartenance à des ensembles, les 2 dernières représentent l'appartenance à l'union et à l'intersection des ensembles. Cette observation ne tient pas du hasard: on peut utiliser la théorie des ensembles pour définir et étudier la logique propositionnelle. La correspondance entre les principaux concepts est donnée dans le tableau:
logique expression ensemble expression
véracité V univers U
fausseté F vide
négation ¬p complément U-A
conjonction p∧q intersection A∩B
disjonction p∨q union A∪B
implication p⇒q   (U-A)∪B

Notons que bien qu'il soit usuel d'interpréter l'implication "p⇒q" comme étant "si p est vrai alors q est vrai", il faut être prudent. En effet, dans le langage courant, ce genre d'affirmation est interprété comme une relation causale. Par exemple, "si Pierre passe son cours, il aura son diplôme". En mathématique, il s'agit d'une implication formelle traduisant toujours une vérité, sauf dans le cas où p est vrai et q est faux. La table de vérité de l'implication est donnée ci-dessous et on remarque que "¬p∨q" est une expression équivalente à l'implication.
p q p⇒q ¬p ¬p∨q
V V V F V
V F F F F
F V V V V
F F V V V

On peut trouver surprenant que "p⇒q" soit vrai lorsque p est faux et q vrai, mais il est facile de voir pourquoi via des exemples. En effet, considérons l'implication "si j'ai 20 dollars, j'ai 25 cents". Il est possible d'avoir une pièce de 25 cents en poche, sans avoir un billet de 20$. Ou encore, "si il fait beau, j'irai dehors", rien ne vous empêche d'aller dehors même si il pleut.

L'équivalence est une double implication, c'est-à-dire que "p⇔q" est défini par "(p⇒q) ∧ (q⇒p)". La table de vérité correspondante étant:
p q p⇒q q⇒p p⇔q
V V V V V
V F F V F
F V V F F
F F V V V

Logique des prédicats (ou de premier ordre)

En logique des prédicats, on pousse plus loin l'analyse faite de la véracité des propositions en introduisant des variables. Elles vont donner leur pleine puissance aux quantificateurs, mais rendent la vérification plus difficile. En effet, en présence de variables, une table de vérité n'est généralement pas suffisante pour caractériser la véracité d'un proposition pour toutes les valeurs possibles des variables. Il faut alors s'en remettre aux définitions et manipuler algébriquement les expressions afin de les simplifier. De plus, nous verrons des règles d'inférence qui nous permetterons de transformer les expressions.

Les variables et constantes reliées entres-elles via des opérateurs arithmétiques et relationnels forment les prédicats (ou formules) atomiques. Ces prédicats peuvent ensuite être combinés ensemble afin de donner des prédicats (ou formules) plus complexes appelées molécules.

Exemples de prédicats, les 2 premiers sont atomiques, le dernier est moléculaire:
-(x+2)>1
y=2
-(x+2)>1 ∨ y=2

On donne souvent un nom symbolique à une formule pour la référencer plus facilement. Par exemple, on écrira P(x) ⇔ -(x+2)>1, ou encore, P(x): -(x+2)>1, pour affecter le nom symbolique P(x) à la formule (prédicat) -(x+2)>1.

A priori, la véracité d'un prédicat peut changer en fonction des valeurs prisent pas les variables dans l'ensemble de référence. Par exemple, considérant la définition de P(x) ci-dessus, P(-4) est vrai alors que P(1) est faux.

Quantificateurs universels

On utilise les quantificateurs universels ∀ et ∃ afin d'étudier la véracité d'un prédicat sur l'ensemble des valeurs que peut prendre les variables. Par exemple, on peut étudier la véracité de ∀x:P(x), connaissant l'ensemble de référence. Voici quelques cas possibles de combinaisons d'ensemble de référence et de quantificateurs, toujours pour la définition de P(x) donnée ci-dessus:
dans ℕ, ∀x:P(x) est faux
dans ℝ, ∀x:P(x) est faux
dans ℕ, ∃x:P(x) est faux
dans ℝ, ∃x:P(x) est vrai

Voici quelques exemples, avec 2 variables cettes fois, chacune prenant des valeurs dans ℕ:
∀x∀y(x≤y∨y≤x)
∀x(∃!y(4y≤x)) ⇒∃x(x≥4)

On remarque que le premier énoncé logique est toujours vrai pour les ensembles de références choisis et exprime la fait que la relation ≤ permet de comparer tous les nombres entiers naturels entre-eux, ce qui fait de ≤ un ordre linéaire sur ℕ. Le second est aussi vrai, car le second membre est vrai (le fait que le membre de gauche soit faux n'invalide pas l'implication).

L'utilisation de quantificateurs universels pour combiner des prédicats donne une nouvelle expression qui est elle aussi un prédicat (moléculaire).

Lorsque qu'il n'y a pas d'ambiguïté, il arrive que l'on omette le quantificateur ∀. Ainsi, les expressions suivantes sont équivalentes dans ℕ:
∀x∀y(x≤y∨y≤x) x≤y ∨ y≤x
∀x∀y(x+y=y+x) x+y=y+x
∀x∀y(x>y)⇒∃k(x=y+k) x>y ⇒∃k(x=y+k)

On remarque que la seconde exprime la règle de commutativité de l'addition des entiers naturels.

Règles d'inférence

Une théorie est un ensemble d'axiomes et de théorèmes. Les axiomes sont des prédicats que l'on pose comme étant vrai a priori. Il s'agit souvent de définitions qui introduisent de nouveaux concepts dans la théorie. Les théorèmes sont des prédicats dont la vérité est démontrable à partir des axiomes et des théorèmes préalablement démontrés. On utilise la combinaison et la simplification des prédicats (expression logique) et les règles d'inférence pour démontrer les théorèmes.

Lors de l'élaboration d'une théorie, le travail principal du mathématicien est de démontrer qu'une proposition A vraie, a comme conséquence une autre proposition B, ce que l'on symbolise par: A⇒B. On dit que la proposition A implique, ou a pour conséquence la proposition B. Presque tous les théorèmes sont des variations de l'implication.

Remarquons que le fait de savoir que A⇒B n'est pas suffisant pour garantir que B soit vrai. En effet, selon la table de vérité de l'implication, elle est vraie lorsque A et B sont fausses. Par exemple, dans ℕ, l'implication (1=2)⇒(2=5) est vraie, alors que (2=5) est faux.

On présente ici les principales règles d'inférences servant dans le processus de démonstration d'un théorème. Une inférence est plus qu'une implication car elle indique dans quel contexte on peut conclure à une proposition vrai. Ainsi, on utilise un symbole différent de celui de l'implication: ⊢. Un énoncé logique de la forme P⊢Q se lit comme "de P on déduit Q". Notons cependant, que certaines règles sont des conclusions dans prémisse.
A, A⇒B ⊢ B modus ponens
A, B ⊢ A∧B inférence cognitive
A∧B ⊢ A simplification cognitive
A⇒B, B⇒C ⊢ A⇒C syllogisme hypothétique
A⇒B ⊢ ¬B⇒¬A inférence par contrapositive
A⇒B, ¬B ⊢ ¬A modus toblons
A⇒B, C⇒B ⊢ A∨C⇒B inférence par cas
A⇒B, A⇒¬B ⊢ ¬A réfutation par l'absurde
¬A⇒B, ¬A⇒¬B ⊢ A raisonnement indirect
⊢ A∨¬A exclusion mutuelle
⊢ A⇒¬¬A double négation
⊢ ¬¬A⇒A double négation

Les règles d'inférence énoncées fournissent au mathématicien un arsenal important d'armes pour obtenir de nouveaux résultats à partir de résultats déjà démontrés ou supposés vrais par hypothèse.

Exemple de théorie: l'arithmétique des entiers naturels

Il y a la constante de base 0, l'opérateur unaire appelé successeur et noté +1, et la relation d'égalité =. On pose les axiomes (prédicats vrais), appelés "axiomes de Peano":

  1. ¬∃x(0=x+1), qui exprime que 0 n'est pas un successeur
  2. x+1=y+1 ⇒ x=y, qui exprime que les nombres différents on des successeurs différents
  3. P(0) ∧ ∀x(P(x)⇒P(x+1)) ⇒ ∀xP(x)

Notons que l'axiome 2 n'est rien d'autre que l'expression de l'injectivité de la relation "successeur". On note aussi la fonction successeur d'un entier a, S(a), qui vaut a+1.

L'axiome 3 est le célèbre axiome d'induction. C'est lui qui permet de formaliser l'addition de 2 entiers naturels. On peut aussi l'utiliser pour démontrer d'innombrable théorème impliquant des entiers naturels, comme la commutativité. Nous allons l'étudier plus en détail dans la section sur les stratégies de preuves en mathématique. Une variante fort utile de cet axiome est:

P(k) ∧ ∀x(x≥k∧P(x)⇒P(x+1)) ⇒ ∀x(x≥k⇒P(x))

Quelques théorèmes de l'arithmétique des entiers naturels:

  1. x+y=y+x
  2. x+(y+z)=(y+x)+z
  3. (x+y)+z=x+(y+z)

On peut démontrer ces théorèmes en utilisant l'axiome d'induction et le concept de successeur. Pour ce faire, on exprime ce dernier sous la forme équivalente: S(a)=a+1, qui peut aussi s'écrire a+S(b)=S(a+b).

Introduisons 2 nouvelles définitions classiques:

Ces définitions supplémentaires nous permettent d'enrichir la théorie avec de nouveaux théorèmes:

  1. ∀n∃({pi,i=1,k|Q(pi)}∧n=∏i=1,kpi)
  2. kx+ky=k(x+y)
  3. k=1,n(2k-1) = n²
  4. k=1,nk = n(n+1)/2
  5. k=1,nk²= n(n+1)(2n+1)/6
  6. r≠1 ⇒ ∑k=1,nark = a(rn+1-1)/(r-1)

Le premier théorème est appelé théorème fondamental de l'arithmétique et dit que tout entier naturel s'écrit comme produit de nombres premiers. On peut pousser plus loin et montrer que cette décomposition est unique. Nous allons prouver tous ces théorèmes dans la section suivante: le premier via une stratégie par contradiction, les autres en utilisant l'axiome (prédicat) d'induction.

Principales stratégies de preuves en mathématique

Une preuve en mathématique, ou démonstration, se fait toujours par l'application successive des règles d'inférence à des axiomes, théorèmes, et hypothèses d'une théorie donnée.

Dans cette section, nous allons voir comment appliquer les règles de manière stratégique afin de faire des démonstrations. Nous allons travailler dans 2 contextes: la théorie de l'arithmétique des entiers naturels et la théorie des ensembles (incluant les relations et les fonctions).

Proposition: il y a une infinité de nombres premiers dans ℕ

Le contexte est l'arithmétique des entiers naturels et la proposition à démontrer peut s'écrire (en utilisant la théorie des ensembles):

Q: card({p∈ℕ | p est premier} est infini

Preuve: On suppose ¬Q vrai, soit E l'ensemble des nombres permiers, puisqu'il est fini, il y a un plus grand élément e. Or, e+1 est aussi un nombre premier et il est plus grand que e, ce qui est impossible. Donc, si on note A la proposition "e est le plus grand nombre premier", on a ¬Q⇒A ∧ ¬Q⇒¬A. Ainsi, par la règle de réfutation par l'absurde ¬¬Q est vrai. D'où Q est vrai par la règle de la double négation.

Cette preuve est un exemple typique de raisonnement par l'absurde, c'est-à-dire une inférence via la règle de réfutation par l'absurde.

Proposition: pour tout n dans ℕ, on a P(n):∑k=1,nk = n(n+1)/2

Le contexte est l'arithmétique des entiers naturels et la stratégie pour démontrer la propriété est une application directe de l'axiome d'induction via le modus ponens. Cependant, avant de faire la démonstration, il est toujours jusdicieux de faire quelques exemples. Ainsi, pour:

Bien que ce soit vrai pour toute les valeurs de n que l'on essai, il faut nécessairement utiliser l'axiome d'induction afin d'avoir une démonstration irréfutable, valide quelquesoit la valeur de n:

Proposition: Soit R une relation d'équivalence et xR, yR deux classes distinctes, alors (x,y)∉R

Le contexte est la théorie des ensembles (relations) et la stratégie pour démontrer est une application de la règle d'inférence par contrapositive: supposons que (x,y)∈R, alors x∈yR, c'est-à-dire que les classes ne sont pas distinctes. L'inférence par contrapositive nous garantie donc que l'assertion initiale est valide.