Logique Mathématique
Dr. Tarek ABABSA
[Link]@[Link]
2021/2022
Chapitre 1
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Chapitre 1
La Logique des Propositions
Introduction
Les Propositions
Le Paradoxe
Les Connecteurs Logiques
Priorité des Connecteurs
Le Langage Propositionnel
L'Alphabet
La Syntaxe
Sémantique
Variables et Formules Propositionnelles
Structure d’une Formule Logique
Satisfiabilité
Tautologies et Antilogies
Conséquence Logique
Équivalence Logique
Théorème de Remplacement
Conséquence de Théorème de Remplacemen
Les Formes Normales
La Forme Normale Disjonctive (FND)
Obtention de Forme Normale Disjonctive
Forme Normale Conjonctive (FNC)
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Chapitre 1
La Logique des Propositions
Les Propositions
En logique, une proposition (ou assertion) est une phrase à laquelle on peut attribuer
une valeur de vérité vrai ou faux.
Exemple
est un nombre entier : est une assertion fausse.
18 est divisible par 3 : est une assertion vrai.
Le Paradoxe
C’est une phrase informative mais elle n’est ni vraie ni fausse.
Exemple
La phrase ''je suis un menteur'', n’est pas une assertion logique car il est
logiquement impossible de savoir si cet individu dit ou non la vérité.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Chapitre 1
La Logique des Propositions
Les Connecteurs Logiques
Conjonction Disjonction
Négation
Conditionnel Biconditionnel
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Chapitre 1
La Logique des Propositions
Le Langage Propositionnel
Un langage propositionnel est composé de :
1 L’Alphabet
La phrase ''je suis un menteur'', n’est pas une assertion logique car il est
logiquement impossible de savoir si cet individu dit ou non la vérité.
2 La Syntaxe
Une formule est une composition de propositions à l’aide de connecteurs
logiques.
3 La Sémantique
La sémantique du langage propositionnel s’intéresse à donner une valeur
de vérité à chaque formule du langage.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Chapitre 1
La Logique des Propositions
Variables et FormulesPropositionnelles
Une variable est représentée par un symbole qui définit une quantité qui peut prendre
n’importe quelle valeur dans un ensemble de valeurs.
Une formule propositionnelle, (ou expression propositionnelle) est une expression
construite à partir de connecteurs et de variables propositionnelles.
Structure d’une formule logique
On peut représenter une formule sous forme d’un arbre. Cela permet de bien lire la
formule.
Satisfiabilité
Une formule α est satisfiable, ssi, sa table de vérité contient au moins une ligne
dont la valeur de vérité de α est vraie.
Exemple
Est une formule satisfiable.
N'est pas une formule satisfiable.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Chapitre 1
La Logique des Propositions
Tautologies et Antilogies
On dit qu'une formule α est une tautologie, si elle est vraie dans toutes les lignes de
sa table de vérité. On note
Une antilogie est une formule fausse dans toutes les lignes de sa table de vérité.
Exemple
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Chapitre 1
La Logique des Propositions
Conséquence Logique
On dit que la formule β est une conséquence logique de la formule α (α β) si la
valeur de vérité de β est vraie dans toutes les lignes où la valeur de vérité de α est
vraie.
En généralisant, on dit que la formule β est une conséquence logique de l'ensemble
de formules E = { } (E β) si la valeur de vérité de β est vraie
dans toutes les lignes où les valeurs de vérité des formules de E sont toutes vraies.
Exemple
Équivalence Logique
On dit que α et β sont logiquement équivalentes si et seulement si α et β ont les
mêmes valeurs de vérité (on note : α ≡ β)
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Chapitre 1
La Logique des Propositions
Théorème de Remplacement
Soient P et Q deux formules propositionnelles tel que P est de la forme :
P : ..........Q.........
P′ : ..........Q′.........
dans ce cas là si Q ≡ Q′ ⇒ P ≡ P′
Exemple
Selon le théorème on aura
Ensemble Complet de Connecteur
Toute formule propositionnelle est logiquement équivalente à une formule
propositionnelle où n’interviennent que les connecteurs ⌉ et ∧ donc on peut dire
que {⌉,∧} est un ensemble complet de connecteur.
Démonstration
P ∨ Q ≡ ⌉(⌉P ∧ ⌉Q)
P → Q ≡ ⌉P ∨ Q
P ↔ Q ≡ (P → Q) ∧ (Q → P)
≡ (⌉P ∨ Q) ∧ (⌉Q ∨ P)
≡ ⌉(P ∧ ⌉Q) ∧ ⌉(Q ∧ ⌉P)
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Chapitre 1
La Logique des Propositions
La Forme Normale Disjonctive (FND)
Une formule α est en forme normale disjonctive, si elle est de la forme :
( ) tel que chaque ( ) est un monôme de la forme:
( ) où chaque ( ) est un littéral de la forme ou .
Théorème.
Pour chaque formule α, il existe une formule α′ de la forme normale disjonctive,
tel que
Obtention de Forme Normale Disjonctive
Notation.
Soit ε ∈ {0, 1} et et F une formule propositionnelle. Alors :
désigne la formule si
désigne la formule si
Construire FND(F).
Étape1: On établit la table de vérité de F. Pour chaque lignecontenant 1 comme
valeur de vérité pour F, on y considère la distribution des valeurs de
vérité ( ) sur ( ) et on construit la formule
Étape2: La FND de la formule propositionnelle F est la disjonction de toutes les
formules construites à l’étape 1.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Chapitre 1
La Logique des Propositions
Exemple
(⌉P∧⌉Q∧R)
(P∧⌉Q∧R)
(P∧Q∧R)
FND(F) = (⌉P∧⌉Q∧R)∨(P∧⌉Q∧R)∨(P∧Q∧R)
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Chapitre 1
La Logique des Propositions
Forme Normale Conjonctive(FNC)
Une formule α est en forme normale disjonctive, si elle est de la forme :
( ) tel que chaque ( ) est un monôme de la forme:
( ) où chaque ( ) est un littéral de la forme ou .
Théorème.
Pour chaque formule α, il existe une formule α′ de la forme normale conjonctive,
tel que
Obtention de Forme Normale Conjonctive
Étape 1: Établir le tableau de F.
Étape 2: Rajouter une colonne ⌉F, doù le tableau de ⌉F.
Étape 3: On en déduit la FND de ⌉F.
Étape 4: enfin, remplacer dans la FND de ⌉F, toute disjonction par une conjonction,
toute conjonction par une disjonction, toute sous-formule ⌉p par p et toute
sous-formule p, non précédée par une négation, par ⌉p.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Chapitre 1
La Logique des Propositions
Exemple
(P ∨Q∨R)
(P∨⌉Q∨R)
(P∨⌉Q∨⌉R)
(⌉P ∨Q∨R)
(⌉P∨⌉Q∨R)
FNC(F) = (P ∨Q∨R)∧(P∨⌉Q∨R)∧(P∨⌉Q∨⌉R)∧
(⌉P ∨Q∨R)∧(⌉P∨⌉Q∨R)
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
