Titre

Plan
Introduction et historique
Élément de logique formelle
Quanticateurs

ch1 La logique

Pierre-Yves Bischo
IUT SRC

2009

Pierre-Yves Bischo ch1 La logique

 Titre
Plan
Introduction et historique
Élément de logique formelle
Quanticateurs

Plan

1 Introduction et historique

2 Élément de logique formelle

3 Quanticateurs

Pierre-Yves Bischo ch1 La logique

 Titre
Plan
Introduction et historique
Élément de logique formelle
Quanticateurs

Plan

1 Introduction et historique

2 Élément de logique formelle

3 Quanticateurs

Pierre-Yves Bischo ch1 La logique

 Titre
Plan
Introduction et historique
Élément de logique formelle
Quanticateurs

I La logique (du grec(logos), signiant entre autres, raison,

science, langage, rapport) est dans une première approche
l'étude des règles formelles que doit respecter toute déduction
correcte.

I Elle est depuis l'Antiquité l'une des grandes disciplines de la

philosophie.

I Au XXe siècle : développement fulgurant d'une approche

mathématique et informatique de la logique.

Pierre-Yves Bischo ch1 La logique

 Titre
Plan
Introduction et historique
Élément de logique formelle
Quanticateurs

La logique est à l'origine la recherche de règles générales et

formelles permettant de distinguer un raisonnement
concluant de celui qui ne l'est pas.

I Elle trouve ses premiers tâtonnements dans les mathématiques

et surtout dans la géométrie mais c'est principalement sous
l'impulsion d'Aristote (IVe BC) qu'elle prit son envol.
I Kant (XVIIIe) dénit la logique comme  une science qui
expose dans le détail et prouve de manière stricte, uniquement
les règles formelles de toute pensée .
I Leibniz (XVIIe) fait de la logique un véritable calcul
algorithmique.
Pierre-Yves Bischo ch1 La logique
 Titre
Plan
Introduction et historique
Élément de logique formelle
Quanticateurs

1. Le démontrable.

I Dénition : Il y a donc ce qui est démontrable et le reste.

I Dans ce  reste  :
les propositions réfutables, c'est-à-dire dont la négation est

démontrable

et des propositions au statut incertain, ni démontrable, ni

réfutable.

Pierre-Yves Bischo ch1 La logique

 Titre
Plan
Introduction et historique
Élément de logique formelle
Quanticateurs

2. Notions élémentaires de logique formelle

I En mathématiques, il y a 3 processus fondamentaux :

construire des objets,

établir des relations entre les objets,

démontrer ces relations.

I Du fait de la disparité des langages dans le monde, on traduit

les propositions mathématiques en un langage articiel formel.
I Dénition : la logique formelle est l'étude des raisonnements
du point de vue de leur validité.
I La validité d'un raisonnement n'est pas à confondre avec la
vérité d'une proposition.
Pierre-Yves Bischo ch1 La logique
 Titre
Plan
Introduction et historique
Élément de logique formelle
Quanticateurs

3. Exemple de logique formelle

1 Tout multiple de 4 est pair. 8 est pair donc c'est un multiple

de 4.

2 Tout multiple de 4 est impair. Donc il existe un nombre impair

multiple de 4.

I Le premier raisonnement est non valide (faux, illogique). ALors

que les propositions sont  vraies .
I A contrario, le second raisonnement est valide (juste, correcte,
logique, vrai) même s'il est formé de propositions fausses.

Pierre-Yves Bischo ch1 La logique

 Titre
Plan
Introduction et historique
Élément de logique formelle
Quanticateurs

Plan

1 Introduction et historique

2 Élément de logique formelle

3 Quanticateurs

Pierre-Yves Bischo ch1 La logique

 Titre
Plan
Introduction et historique
Élément de logique formelle
Quanticateurs

1. Propositions

I Dénition : une proposition est un énoncé ne contenant pas

de variable susceptible de l'une ou l'autre de 2 valeurs
logiques : 1 (Vrai) ou 0 (Faux).
I Exemples :
A : 5 est un nombre premier.

B : 3 est un nombre pair.

C : tout entier pair a un carré pair.

P A B C
v(P) 1 0 1
I

Pierre-Yves Bischo ch1 La logique

 Titre
Plan
Introduction et historique
Élément de logique formelle
Quanticateurs

1. a) Connections des propositions

I De nombreuses propositions sont constituées de parties qui

sont elles-mêmes des propositions.
I Par exemple la proposition A : 3 est impair et 3 est un nombre
premier est constitué de la proposition B : 3 est impair et de

C : 3 est premier.
I Connecteurs :
¬ : non, négation ;
∧ : et ;
∨ : ou ;
⇒ : implique ;
⇔ : équivalent.

Pierre-Yves Bischo ch1 La logique

 Titre
Plan
Introduction et historique
Élément de logique formelle
Quanticateurs

1. b) Tables de vérité des connecteurs

I La valeur de vérité d'une proposition peut être déterminée par

la connaisance des tables de vérité de ses parties.
A ¬A
I Table de vérité de la négation : 1 0
0 1
I Table de vérité des connecteurs :
A B A∧B A∨B A⇒B A⇔B
1 1 1 1 1 1
1 0 0 1 0 0
0 1 0 1 1 0
0 0 0 0 1 1
Pierre-Yves Bischo ch1 La logique
 Titre
Plan
Introduction et historique
Élément de logique formelle
Quanticateurs

1. c) Propriétés des connecteurs

A ≡ ¬(¬A) A ≡A∧A A ≡A∨A (1)

A ∨B ≡B ∨A A ∧ B ≡ B ∧ A (2)
(A ∧ B ) ∧ C ≡ A ∧ (B ∧ C ) (A ∨ B ) ∨ C ≡ A ∨ (B ∨ C ) (3)
A ⇒ B ≡ ¬A ∨ B A ⇔ B ≡ (A ⇒ B ) ∧ (B ⇒ A) (4)

¬(A ∨ B ) ≡ ¬A ∧ ¬B ¬(A ∧ B ) ≡ ¬A ∨ ¬B (5)

A ∨ (B ∧ C ) ≡ (A ∨ B ) ∧ (A ∨ C )(6)

A ∧ (B ∨ C ) ≡ (A ∧ B ) ∨ (A ∧ C )(7)

Pierre-Yves Bischo ch1 La logique

 Titre
Plan
Introduction et historique
Élément de logique formelle
Quanticateurs

Equivalences les plus importantes :

A ∧ ¬B ≡ ¬(A ⇒ B ) (8)

Raisonnement par contraposition

A ⇒ B ≡ ¬B ⇒ ¬A (9)

Pierre-Yves Bischo ch1 La logique

 Titre
Plan
Introduction et historique
Élément de logique formelle
Quanticateurs

1. d) Tautologie

Il existe des propositions qui prennent la valeur vraie

indépendamment des valeurs logiques des propositions :

Principe du tiers exclu : A ∨ ¬A (10)

Principe de non contradiction : ¬(A ∧ ¬A) (11)
Transitivité de ⇒ : (A ⇒ B )∧ (B ⇒ C ) ⇒ (A ⇒ C ) (12)

Pierre-Yves Bischo ch1 La logique

 Titre
Plan
Introduction et historique
Élément de logique formelle
Quanticateurs

Plan

1 Introduction et historique

2 Élément de logique formelle

3 Quanticateurs

Pierre-Yves Bischo ch1 La logique

 Titre
Plan
Introduction et historique
Élément de logique formelle
Quanticateurs

2. Quanticateurs
2. a) Prédicats

I Dénition : un prédicat est une proposition A(x , y , ...)

contenant des lettres x , y , ... variables d'un certain ensemble E .

1 Pour
√ x ∈ R A(x ) = x est un entier pair.
A( 5), A(3) sont fausses mais A(6) est vraie.
2 Pour x , y ∈ N × N A(x , y ) = x est un multiple de y .
A(5, 2), A(3, 4) sont fausses mais A(6, 2) est vraie.

Pierre-Yves Bischo ch1 La logique

 Titre
Plan
Introduction et historique
Élément de logique formelle
Quanticateurs

2. b) Quanticateurs

I La proposition A(a) est vraie pour tout a ∈ E s'écrit :

∀x ∈ EA(x ).
I S'il existe au moins un objet a ∈ E pour lequel la proposition
A(a) est vraie s'écrit : ∃x ∈ E A(x ).

1 Les deux propositions précédentes ne contiennent pas de

variable, la lettre x est une variable muette.
2 S'il existe un unique objet a ∈ E pour lequel la proposition
A(a) est vraie s'écrit : ∃!x ∈ E A(x ).

Pierre-Yves Bischo ch1 La logique

 Titre
Plan
Introduction et historique
Élément de logique formelle
Quanticateurs

2. c) Propriétés des quanticateurs

Equivalence tautologique

¬(∃x A x( ) ≡ ∀x ¬A(x ) (13)

¬(∀x A x( ) ≡ ∃x ¬A(x ) (14)
∀x (∀y ( , ) ≡ ∀y (∀x
A x y ( , )
A x y (15)
∃x (∃y ( , ) ≡ ∃y (∃x
A x y ( , )
A x y (16)

∀x (∃y ( , )
A x y n'est pas equivalent tautologiquement
à ∃y (∀x A(x , y )

Pierre-Yves Bischo ch1 La logique