Chapitre 1

Logique
Il est important d'avoir un langage rigoureux. La langue française est souvent ambigüe.
Prenons l'exemple de la conjonction "`ou"' ; au restaurant "`fromage ou dessert"' signie
l'un ou l'autre mais pas les deux. Par contre si dans un jeu de carte on cherche "`les as ou
les coeurs "` alors il ne faut pas exclure l'as de coeur. Autre exemple : que répondre à la
question "`As-tu 500F en poche ?"' si l'on dispose de 1000F ?
Il y a des notions diciles à expliquer avec des mots : par exemple la continuité d'une
fonction est souvent expliquée par "` on trace le graphe sans lever le crayon"'. Il est clair
que c'est une dénition peu satisfaisante. Voici la dénition mathématique de la continuité
d'une fonction f : I → R en un point x0 ∈ I :

∀ε > 0 ∃δ > 0 ∀x ∈ I (|x− x0 | < δ ⇒ |f (x) − f (x0 )| < ε) .

Les mathématiques sont un langage qui nous permet d'exprimer aisement ces notions
diciles. Ce langage est adapté aux phénomènes aussi simples que complexes. Il utilise un
raisonnement dit logique. L'objet de cette unité est d'amener les étudiants à avoir une cer-
taine logique dans leurs raisonnements. Ils devront se familiariser avec un formalisme logique,
la notion de démonstration, de validité, la calculabilité. Bien que son domaine d'étude soit
les mathématiques, la logique est une branche des mathématiques à part entière avec de
nombreuses applications, en particulier en informatique. Elle est la science de la raison. Plus
précisément, c'est la science qui étudie les règles qui permettent de distinguer un raisonne-
ment valide d'un raisonnement qui ne l'est pas.
Objectifs de l'unité

À la n de cette unité, vous devriez être capable de :

1. Connaître les principaux opérateurs et leurs propriétés
2. Comprendre les notions d'implication et d'équivalence
3. Faire un raisonnement logique
4. Donner la table de verité d'une proposition.
5. Dénir et interpréter avec rigueur et précision les concepts
6. Eviter les mauvaises interprétations et détecter des erreurs de raisonnement.
Termes clés

5
6 CHAPITRE 1. LOGIQUE

Logique : c'est la science qui étudie les règles que doivent respecter tout raisonnement
valide
raisonnement : c'est un processus, une argumentation visant à établir une conclusion,
un processus qui permet d'obtenir de nouveaux résultats ou bien de vérier la réalité
la réalité d'un fait
Quanticateurs : sont des expressions utilisées pour formuler des propositions mathé-
matiques dans le calcul des predicats (pour tout, quelque soit et il existe).
Predicats : C'est une proposition dont la valeur de vérité dépend de variables qu'elle
renferme.
Connecteurs : sont des mots ou expressions permettant d'établir des relations entre
deux idées, deux faits.
Proposition : c'est une armation formée d'un assemblage de symboles et de mots,
portant sur des objets mathématiques, à laquelle on peut clairement attribuer la valeur
vraie ou la valeur faux.

1.1 Représentation symbolique et tautologie

L'objectif de cette activité est de vous amener à comprendre la notion de proposition. A
la n de cette activité, vous devez être à mesure de faire la diérence une propositions et une
phrase qui n'a pas de table de vérité. Vous devez être capable de traduire une proposition
en representation symbolique et reconnaître une tautologie.

1.1.1 Proposition
Dénition 1.1.1. Parmi les phrases ou enoncés possibles à formuler dans une langue, on
distingue ceux auxquels il est possible d'attribuer une valeur de vérité : vrai ou faux. Ces types
d'enoncés porteront le nom de propositions. En d'autres termes, est appelée proposition toute
expression qui peut être dite vraie ou fausse, ce qui exclut, entre autres, les questions, les
impératifs, les exclamatifs, et plus généralement tous les énoncées dits non assertifs. Cette
partie traitera les notions de propositions informatiques.

Exemple : "`L'Afrique a été colonisé en 1970,"' "`Le Burkina Faso est un pays indépendant
d'Afrique"' sont des propositions. Mais les phrases "`Ou est-il ?,"' "`Va-t-en !"' ne sont pas
des propositions

Remarque 1.1.1. Remarque : Un énoncé hypothétique ne peut pas être une proposition, de
même que certains paradoxes comme celui du menteur.

1.1.2 Axiomes
Les propositions répondent aux axiomes suivants :
Principe de non-contradiction : Une proposition ne peut etre simultanément vraie et
fausse ;
1.2. CONNECTEURS LOGIQUES ET LES VALEURS DE VÉRITÉ 7

Principe du tiers-exclu : Une proposition est vraie ou fausse (il n'y a pas de troisième
possibilité ).
Exercice 1. La phrase "`la présente armation est vraie"' possede-t-elle une valeur de
vérité ?
Exercice 2. Les armations suivantes sont-elles des propositions ?
1. "`l'armation qui suit est vraie,"'
2. "`La précédente armation est fausse"'
Dénition 1.1.2 (Tautologie). Une tautologie est une proposition qui est toujours vraie.
Exemples :
 "`100% de nos clients achètent nos produits."'
 "`100% des gagnants ont tenté leur chance."'
Dénition 1.1.3 (Equivalence logique). Deux propositions équivalentes P et Q sont deux
propositions simultanément vraies et simultanément fausses. On dira qu'elles ont les mêmes
valeurs de vérité.
Exemples : (x2 = 1) ⇔ (x = 1oux = −1).
Conclusion Le raisonnement scientique consiste à chercher à connaître la valeur de vérité
de diérentes propositions. Cette recherche se base sur des propositions dont les valeurs de
vérité sont connues.
Le calcul propositionnel s'intéresse à la façon dont les propositions sont liées entre elles et
aux conséquences qu'on peut en tirer sur leurs valeurs de vérité. Vous êtes à la n de cette
activité et vous devez être capable de faire la diérence entre les propositions et d'autres
types d'expressions. Savoir si une proposition est une tautologie ou pas.

1.2 Connecteurs logiques et les valeurs de vérité

Comme en linguistique, il existe beaucoup de connecteurs logique, utilisés dans le domaine
informatique. Ils permettent de construire de nouvelles propositions à partir de propositions
données, la valeur de vérité dépendant des valeurs de vérité des propositions données. Les plus
utilisés sont la négation ¬, la conjonction ∧, la disjonction ∨, l'implication → et l'équivalence
↔.

1.2.1 Quelques dénitions

La négation : La négation d'une proposition P, notée ¬P, est une proposition qui est vraie
quand P, est fausse et vis versa.

P ¬p
V F
F V
Exemple : La négation de la proposition "`Paris est en France ou Madrid est en chine"' est
la proposition "`Paris n'est pas en France et Madrid n'est pas en chine"'
8 CHAPITRE 1. LOGIQUE

La conjonction. La conjonction de deux propositions P et Q, notée p ∧ q, est vraie si et

seulement si P et Q sont vraies à la fois.

P Q P ∧Q
V V V
V F F
F V F
F F F
La disjonction. La disjonction de deux propositions P et Q, notée P ∨ Q, est vraie ssi P
ou Q (ou les deux) est vraie.
P Q P ∨Q
V V V
V F V
F V V
F F F
Exemple. On considère les propositions logiques
 P : "`Mon père est grand"'
 Q : "`Mon père a eu 4 enfants"'
Alors ¬P : "`Mon père n'est pas grand,"'
P ∧ Q : "`Mon père est grand et il a eu 4 enfants"' et
Q ∨ Q : "`Mon père est grand ou il a eu 4 enfants"'.
L'implication. L'implication, notée P ⇒ Q, est une proposition qui est vraie si et seule-
ment si (P est vraie et Q est vraie) ou (P est faux et Q est quelconque).

P Q P ⇒Q
V V V
V F F
F V V
F F V

Remarque 1.2.1. L'implication est intuitivement la plus dicile à appréhender : le faux

implique n'importe quoi ! Par exemple, notons P la proposition logique "`mon grand père saute
2m de hauteur"' et Q la proposition "`les enfants auront tous 20/20 au prochain examen."'
Et bien l'implication P ⇒ Q est vraie quelle que soit la valeur de vérité de Q, simplement
car P est faux

L'équivalence. L'équivalence de deux propositions P et Q, notée P ⇔ Q, est vraie si et

seulement si P et Q, ont même valeur de vérité (vraie à la fois et fausse à la fois).

P Q P ⇔Q
V V V
V F F
F V F
F F V
1.2. CONNECTEURS LOGIQUES ET LES VALEURS DE VÉRITÉ 9

1.2.2 Formules propositionnelles

On appelle formule propositionnelle la combinaison de propositions logiques et de connecteurs
logiques. On peut écrire la table de vérité d'une telle formule en fonction des valeurs de vérité
des propositions qui la constituent.
Exemple : Si P et Q sont deux propositions logiques, alors (¬P ) ∨ Q est une formule
propositionnelle.

Remarque 1.2.2. Si deux formules propositionnelles ont la même table de vérité, on dit
qu'elles sont logiquement équivalentes et on écrira l'égalité entre les deux formules.

Exemple.
Les formules propositionnelles P ⇒ Q et (¬P ) ∨ Q ont les mêmes valeurs de vérités. On écrit
P ⇒ Q = (¬P ) ∨ Q.

Dénition 1.2.1.  On appelle tautologie une formule propositionnelle qui est toujours
vraie.
 On appelle antilogie une formule propositionnelle qui est toujours fausse.

Proposition 1.2.1. Les connecteurs logiques que nous avons dénis satisfont un certain
nombre de propriétés énumérées dans la proposition suivante. Celles-ci nous permettront
souvent de simplier une formule propositionnelle.
 ¬(¬P ) = P
 associativité (P ∨ Q) ∨ R = P ∨ (Q ∨ R) et (P ∧ Q) ∧ R = P ∧ (Q ∧ R)
 commutativité P ∨ Q = Q ∨ P et P ∧ Q = Q ∧ P
 idempotence P ∨ P = p et P ∧ P = P
 distributivité P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R) et P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R)
 loi de De Morgan ¬(P ∨ Q) = (¬P ) ∧ (¬Q) et ¬(P ∧ Q) = (¬P ) ∨ (¬Q)

Remarque 1.2.3. Pour déterminer la vérité d'une formule, on doit déterminer la valeur
de vérité pour les diérentes valeurs des variables propositionnelles qui la composent. Par
exemple, soit la formule f (a, b, c) = a ∧ (b ∨ c). Il est cette fois nécessaire de construire une
table de vérité à 8 lignes (de manière générale, s'il y a n variables propositionnelles, il y a
aura 2n lignes dans la table de vérité) :

a bc b∨ c f (a, b, c) = a ∧ (b ∨ c)
F F F F F
F F V V F
F V F V F
F V V V F
V F F F F
V F V V V
V V F V V
V V V V V

On peut constater plusieurs choses dans cet exemple :

10 CHAPITRE 1. LOGIQUE

 On peut tout à fait réaliser la table de vérité pour des morceaux de la formule (ici b ∨ c)
avant de calculer la valeur de vérité de la formule elle même. Ici, il sut ensuite de
faire un ET entre la quatrième (b ∨ c) et la première colonne pour connaître la valeur
de vérité de la formule complète.
 La manière de remplir la table pour les variables a, b et c : quatre ”‘F ”′ suivit de 4
”′ V ”′ pour la première colonne, une alternance de 2 ”′ F ”′ et 2 ”‘V ”′ pour la deuxième
et une alternance de ”‘F ”′ et de ”‘V ”‘ pour la troisième. En procédant comme cela,
vous êtes sûr de couvrir les 8 cas de gure possible.
 On voit ici que f (a, b, c) ne peut être vraie que si a = V. Cela provient de ce qu'on a
observé précédemment : a ∧ b = V si a = b = V.
Conclusion Dans cette activité, nous nous sommes interessés aux connecteurs, aux formules
propositionnelles et aux table de verité. Les connecteurs vous permettent de construire des
formules propositionnelles assez compliquées et de dresser les tables de vérité.

1.3 Quanticateurs, prédicats

Le calcul propositionnel reste très limité, et ne permet essentiellement que d'exprimer des
opérations booléennes sur des propositions. Si l'on veut pouvoir raisonner sur des assertions
mathématiques, il nous faut autoriser des constructions plus riches. Par exemple, on peut
vouloir écrire l'énoncé ”‘x ≥ 2. Un tel énoncé n'est pas une proposition. Par ce que sa va-
leur de vérité dépend de la valeur de x. Dans cette partie du cours, on parlera d'un autre
type d'expression : les prédicats ou formes propositionnelles. On utilisera les quanticateurs
existentielles et universelles. Le calcul des prédicats, reste le formalisme le plus courant pour
exprimer des propriétés mathématiques. C'est aussi un formalisme très utilisé en informa-
tique pour décrire les objets : par exemple, les langages de requêtes à des bases de données
sont essentiellement basés sur ce formalisme, appliqué à des objets nis, qui représentent des
données.
Pour écrire une formule d'un langage du premier ordre, on utilise certains symboles qui sont
communs à tous les langages, et certains symboles qui varient d'un langage à l'autre. Les
symboles communs à tous les langages sont :
 les connecteurs (¬, ∧, ∨, ⇒, ⇔)
 les parenthèses () et la virgule ,
 le quanticateur universel ∀ et le quanticateur existentiel ∃
 un ensemble inni dénombrable de symboles V de variables

1.3.1 Prédicats
Dénition 1.3.1. Un prédicat est une proposition logique P (x) qui dépend d'une variable
x. La valeur de vérité de P (x) dépend du choix de x.
Exemple : P1 (x) =′ x est pair,′ alors P1 (2) est vrai mais P1 (3) est faux. P2 (x) =′ x > x − 1′
alors P2 (x) est toujours vrai quand x est dans R.
Remarque 1.3.1. Un prédicat peut dépendre de plusieurs variables (par ex. P (x, y) = ”′ x <
y”′ )
On peut opérer logiquement sur les prédicats comme on le fait avec les propositions logiques.
1.3. QUANTIFICATEURS, PRÉDICATS 11

Quanticateurs : Quand un prédicat P (x) est vrai pour toutes les valeurs de x d'un
ensemble E, on écrit ”‘∀x ∈ E, P (x)”′ et on lit "`Pour tout x dans E, P (x)"' ou "`Quel que
soit x dans E, P (x).”′
Exemple
∀x ∈ R, x2 ≥ 0 ∀x ∈] − 1, 1[, 0 ≤ x2 < 1
Ces assertions sont des propositions qui ne dépendent plus de x. Ici x est une variable muette,
on peut la remplacer par n'importe quel autre nom de variable.

Remarque 1.3.2. Quand un prédicat P (x) est vrai pour au moins une valeur de x d'un
ensemble E, on écrit ”‘∃x ∈ E, P (x)”′ et on lit "`Il existe au moins un x dans E, P (x)”′
Exemple :

∃x ∈ R, x2 = x
∃x ∈ R, x < 0
Remarque 1.3.3. Quand un prédicat P (x) est vrai pour exactement une valeur de x d'un
ensemble E, on écrit ”‘∃!x ∈ E, P (x)”′ et on lit "`Il existe un unique x dans E, P (x)”′
Exemple : ∃!x ∈]?1, 1[, x2 = 0

1.3.2 Quanticateurs et connecteurs logiques

Un prédicat auquel on applique un quanticateur devient une proposition logique. Dans
ce cas on peut appliquer les diérents connecteurs,¬ ∨ et ∧ à ces quanticateurs. Cependant,
il est nécessaire de faire très attention à ce qu'on écrit car une erreur est très vite arrivée et
peut en un instant transformer un énoncé correct en horreur innommable !
Il faut retenir deux choses très importantes : Faire très attention quand on mélange quanti-
cateurs et connecteurs logiques ! Ne jamais intervertir quanticateur et connecteur, ni deux
quanticateurs sans avoir pris la peine de rééchir.
Quelques règles :
Eet de la négation sur les quanticateurs
¬(∀x ∈ E, P (x)) = ∃x ∈ E, ¬(P (x))

¬(∃x ∈ E, P (x)) = ∀x ∈ E, ¬(P (x))

Eet de la conjonction sur les quanticateurs

∀x ∈ E, (P (x) ∧ Q(x)) ⇔ (∀x ∈ E, P (x)) ∧ (∀x ∈ E, Q(x))

∃x ∈ E, (P (x) ∧ Q(x)) ⇒ (∃x ∈ E, P (x)) ∧ (∃x ∈ E, Q(x))

Dans la deuxième implication la réciproque est fausse ! Par exemple si E = Z, P (x) =
”‘x est pair,”′ Q(x) = ”‘x est impair”′ eet de la disjonction sur les quanticateurs

(∀x ∈ E, P (x)) ∨ (∀x ∈ E, Q(x)) ⇒ ∀x ∈ E, (P (x) ∨ Q(x))

∃x ∈ E, (P (x) ∨ Q(x)) ⇔ (∃x ∈ E, P (x)) ∨ (∃x ∈ E, Q(x)).

12 CHAPITRE 1. LOGIQUE

Dans la première implication la réciproque est fausse ! Le même exemple que précédemment
le prouve.
Ces outils sont beaucoup utiles pour l'élaboration des démonstration de théorèmes. Voici
quelques exemples de types de démonstrations :
Preuve par l'absurde : pour prouver l'énoncé P, on fait l'hypothèse qu'il est faux et
on montre qu'on aboutit à une contradiction.
Pour prouver une implication P ⇒ Q, on suppose que P est vraie et on procède à
des déductions jusqu'à prouver que Q est vraie. En eet, dans le cas où P est fausse,
l'implication est toujours vraie.
Disjonction de cas : quand le nombre de possibilité est ni, il est envisageable d'étudier
tous les cas possibles.
Contraposée : basée sur l'équivalence (P ⇒ Q) ⇔ (¬Q ⇒ ¬P )
Raisonnement par récurrence : on souhaite montrer qu'un prédicat P (n) est vrai
pour toutes les valeurs de n, on démontre tout d'abord que P (0) est vrai, puisque
l'implication P (n) ⇒ P (n + 1) est vraie.
Conclusion : Comme le calcul des propositions, le calcul des prédicats se donne pour but
de dénir quels sont les énoncés qui sont valides et quels sont ceux qui ne le sont pas. Il est
complet comme le calcul des propositions, mais il n'est pas décidable.