Logiques formelles

Elaboré par Mme Elkamel Hager

[email protected]

Faculté des Sciences de Monastir 2023-2024

1ereannée Licence en Sciences de l’Informatique

Logiques formelles FSM 23-24 H. Jamoussi Elkamel

La logique

La logique consiste à
• valider et caractériser les raisonnements
valides
• en utilisant des règles de la logique
permettent d'effectuer les raisonnements de
façon formelle,
• c'est à dire en appliquant des règles précises
de manipulation de symboles qui ne laissent
aucune place à l'ambiguïté et à l'erreur

H. Jamoussi Elkamel 2
Logiques formelles FSM 23-24

1
 La Logique
• La démarche consiste à
 considérer des raisonnements et de tenter de mettre en
évidence les propriétés de validité en faisant abstraction
des éléments non pertinents
 modéliser et formaliser l'expression de la pensée (une
phrase, un raisonnement ou un discours) dite en langage
Naturel à l’aide des symboles (formules) qui se prêtent à
un calcul mathématiques,
 ensuite d’attribuer une valeur de vérité à ce
raisonnement.

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 3

Plan du cours
3

Chapitre 1 : introduction à la Logique

Partie I : la logique de propositions
Chapitre 2 : Syntaxe de la logique de propositions
Chapitre 3 : Sémantique de la logique de propositions
Chapitre 4 : Systèmes de preuve dans la logique de
propositions
Partie II : la logique de prédicats du premier ordre
Chapitre 5 : Syntaxe de la logique de prédicats du premier
ordre
Chapitre 6 : Sémantique de la logique de prédicats du
premier ordre
Chapitre 7 : Systèmes de preuve dans logique de
prédicats du premier ordre
Logiques formelles FSM 23-24 H. Jamoussi Elkamel

2
 Partie I : Logique propositionnelle

Logiques formelles FSM 23-24 H. Jamoussi Elkamel

Introduction
La logique propositionnelle, ou calcul propositionnel, est
• un cadre mathématique élémentaire
• qui constitue un noyau minimal commun à tous les
systèmes logiques utilisés actuellement.
• Son but est de donner un fondement formel pour un
ensemble restreint d’énoncés du langage naturel.
Son objet d'étude est
• l'ensemble des énoncés d'un langage (syntaxe),
• leur interprétation sémantique
• ainsi que les systèmes de déduction permettant de
construire des preuves dans ce langage.
H. Jamoussi Elkamel 6
Logiques formelles FSM 23-24

3
 Introduction
En général , on décrit une logique par les éléments suivants
– Syntaxe
• qu'est-ce qu'une formule ?
• comment s’écrit-elle ?
L'ensemble des énoncés, ou formules, est défini par induction « constructive » et la
démonstration de nombreux résultats les concernant utilise cette construction.

– Sémantique
• quel est le sens donné a chaque formule ?
L'interprétation des formules est faite en terme de valeurs de vérité (vrai, faux) et donne un
sens aux notions de formules équivalentes et de conséquence logique.

– Système de déduction
• une méthode de preuve pour déterminer si une formule est vraie.
La forme normale sera utilisée pour présenter un système de déduction automatique.
Logiques formelles FSM 23-24 H. Jamoussi Elkamel 7

1. Les objets de base de la logique de

propositions

Les objets de base de la logique de propositions sont

• Les propositions
• Et les connecteurs

H. Jamoussi Elkamel 8
Logiques formelles FSM 23-24

4
 1.1 Les Propositions
Aristote a défini ainsi le concept de proposition :
"... tout discours n'est pas une proposition, mais seulement le
discours dans lequel réside le vrai ou le faux, ce qui
n'arrive pas dans tous les cas : ainsi la prière est un discours,
mais elle n'est ni vraie ni fausse .. " .

Une proposition est une phrase susceptible d’être vraie ou

fausse mais pas les deux (principe de tiers-exclu).
En français, on parle souvent de “phrase énonciative” ou
“phrase déclarative”.

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 9

1.1 Les Propositions

On s'intéresse aux phrases déclaratives qui peuvent être
"vraies" ou "fausses" sans se soucier comment obtenir ses
valeurs de vérité
Voici quelques exemples de propositions,
1. Un plus deux égalent trois.
2. 1+1 = 3.
3. π > e.
4. Il n’existe que cinq polyèdres réguliers convexes.
5. Il existe une infinité de nombres premiers x tels que x + 2
est aussi premier.
6. Il pleut.
7. Je donne cours de logique le vendredi.
8. Je suis en vacance.
H. Jamoussi Elkamel 10
Logiques formelles FSM 23-24

5
 1.1 Les Propositions
• Remarquons que certaines phrases de la langue courante ne
sont pas de propositions, elles ne sont ni vraies ni fausses.

Exemples de non propositions

a. Est-ce que Paul aime la marche à pied ? (question)

b. Fermez la porte ! (impératif)
c. Qu’elle est gentille ! (exclamatif)
d. Je te promets de venir (énoncé non assertif )
e. La bataille aura lieu demain (énoncé modalisé)

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 11

1.2 Les connecteurs

Les connecteurs sont des opérateurs qui permettent, en
reliant deux propositions, de former une nouvelle
proposition complexe (une phrase)
a. Il pleut à Tunis
b. Il neige à Paris
c. Il pleut à Tunis et il neige à Paris

Les connecteurs qui nous intéressent ici sont caractérisés par

leur sensibilité exclusive à la vérité ou la fausseté de leurs
opérandes, c’est ce que l’on appelle le caractère
vérifonctionnel des connecteurs.

H. Jamoussi Elkamel 12
Logiques formelles FSM 23-24

6
 Chapitre 2 : syntaxe de la logique
propositionnelle

Logiques formelles FSM 23-24 H. Jamoussi Elkamel

Ch2: Syntaxe de la logique propositionnelle

1 . Syntaxe de la logique des propositions
1.1 Langage propositionnel
1.2 Les atomes
1.3 Formule bien formée.
1.4 Décomposition d'une formule
1.5 Sous-formule
1.6 Arbre d'une formule
1.7 Substitution d'une sous-formule par une autre
2. Représentation des connaissances dans la logique de
propositions

H. Jamoussi Elkamel 14
Logiques formelles FSM 23-24

7
 1 . Syntaxe de la logique propositionnelle

Pour étudier la syntaxe d’une logique il faut donner

• Un alphabet ou vocabulaire : c’est l’ensemble de
symboles utilisés
• Et les règles de construction syntaxique des
formules bien formées à partir de ces symboles

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 15

1.1 Langage propositionnel

Le langage propositionnel est caractérisé par un ensemble de
symboles appelé alphabet, constitué par :
• un ensemble P ={ p, q, r, ...} fini ou dénombrable de
symboles appelés variables propositionnelles (formules
atomiques ou atomes),
• un ensemble de connecteurs (ou symboles logiques)
comportant
– un connecteur unaire :  (non)
– des connecteurs binaires :
•  (et : conjonction )
•  (ou: disjonction )
•  (implique: implication )
•  (équivalent à: équivalence )
• et les parenthèses ( et )
H. Jamoussi Elkamel 16
Logiques formelles FSM 23-24

8
 1.2 Atomes
• Un atome appelé aussi formule atomique ou variable
propositionnelle est une proposition élémentaire dont
nous ne connaissons pas (et ne chercherons pas à connaître)
la structure interne, et qui garde son identité tout au long du
calcul propositionnel qui nous occupe.
• On désigne une proposition élémentaire par des lettres p, q,
r
• P ={ p, q, r, ...} est l’ensemble des variables
propositionnelles

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 17

1.2 Atomes

Phrases déclaratives ou atomes (propositions)

p : "la neige est blanche"

q : "le pain est un aliment"
r : "Salah a une voiture"
s : "le ciel est bleu"

H. Jamoussi Elkamel 18
Logiques formelles FSM 23-24

9
 1.3 Formule bien formée
• Une formule est une proposition composée.
Définition 1:
• L'ensemble des formules de la logique propositionnelle
(formules bien formées FBF, Well-Formed-Formula WFF)
construit sur P est le plus petit ensemble F tel que :
- toute variable propositionnelle (atome) est dans F
- si F  F alors  F  F
- si F, G  F alors (F  G)  F ,
(F  G)  F ,
(F  G)  F ,
(F  G)  F
L'ensemble F est bien défini.
Logiques formelles FSM 23-24 H. Jamoussi Elkamel 19

Exemples
Exemple 1
Phrases déclaratives ou atomes (propositions)
p : "la neige est blanche"
q : "le pain est un aliment"
r : "Salah a une voiture"
s : "le ciel est bleu"

A partir de ces atomes, on construit des propositions

composées :
(p  s) "la neige est blanche et le ciel est bleu"
H. Jamoussi Elkamel 20
Logiques formelles FSM 23-24

10
 Exemples
Exemple 2
p : "le taux d'humidité est élevé"
q : "la température est élevée"
t : "On se sent bien"

Alors la phrase suivante :

"Si le taux d'humidité est élevé et la température est
élevée, alors on ne se sent pas bien"
peut être formulée par la proposition composée
( (pq)t)

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 21

1.4 Décomposition d'une formule

• Etant donné une formule, existe-t-il plusieurs manières
de la décomposer en formules "plus simples"?
Théorème 1 : de décomposition d’une formule
Soit F une formule. Alors elle est de l'une, et une seule,
des formes suivantes :
1. une variable propositionnelle,
2.  G où G est une formule,
3. (G  H) où G, H sont des formules,
4. (G  H) où G, H sont des formules,
5. (G  H) où G, H sont des formules,
6. (G  H) où G, H sont des formules,
De plus, dans les cas 2, 3, 4, 5, et 6 les formules G et H sont
déterminées de manière unique.
H. Jamoussi Elkamel 22
Logiques formelles FSM 23-24

11
 Exemple de décomposition d’une formule

L'expression suivante est-elle une formule bien formée?

M = ( ( ( p  q)   (r  s) )  p)
• M est de la forme (F1  F2) où F2 = p et p est une variable
propositionnelle donc formule
• F1 est de la forme ( F3  F4)
• F3 est de la forme ( F5  F6) où
F5=  F7, F6 = q et F7=p
p, q des variables propositionnelles
• F4 est de la forme  F8 et F8 est de la forme ( F9  F10) où
F9= r, F10 = s et r, s des variables propositionnelles
L'expression M est bien une formule.

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 23

1.5 Sous-formule
Définition 2:
• Une sous-formule d'une formule F est une formule
apparaissant dans la décomposition de F.

• Exemple 4:
Les formules ( p  q), (r  s) et p sont des sous-
formules de l'expression M traitée dans l'exemple
précédent.
L’ensemble de sous formules de M est
{M, F1, F2, F3, F4, F5, F6, F7, F8, F9, F10}

H. Jamoussi Elkamel 24
Logiques formelles FSM 23-24

12
 Exercice
lesquelles sont des formules bien formées ?
• ¬(¬P ∨ Q)
• ¬(Q)
• P ∨ (Q)
• (P → ((P → Q)))
• (P ∨ (Q ∨ R))
• ((P → P) → (Q → Q))
• −P ∨ Q ∨ R
• ((P28 → P3) → P4)
• (¬P ∨ ¬ ¬P)
• (P2 → (P2 → (P2 → P2)))
• (P → (P → Q) → Q)
• (P ∨ P) H. Jamoussi Elkamel 25
Logiques formelles FSM 23-24

Exercice
lesquelles sont des formules bien formées ?
• ¬(¬P ∨ Q) Oui
• ¬(Q) Non
• P ∨ (Q) Non
• (P → ((P → Q))) Non
• (P ∨ (Q ∨ R)) Oui
• ((P → P) → (Q → Q)) Oui
• −P ∨ Q ∨ R Non
• ((P28 → P3) → P4) Oui
• (¬P ∨ ¬ ¬P) Oui
• (P2 → (P2 → (P2 → P2))) Oui
• (P → (P → Q) → Q) Non
• (P ∨ P) Oui
H. Jamoussi Elkamel 26
Logiques formelles FSM 23-24

13
 1.6 Arbre de décomposition d'une formule
 L’arbre de décomposition d’une formule
• montre comment la formule M est construite à
partir des variables propositionnelles en utilisant
les connecteurs
• et fournit, toutes les sous-formules entrant dans
la construction de M
 Toute formule bien formée a un et un seul arbre
de construction (c’est une conséquence du fait
que le langage de la logique est syntaxiquement
non ambigu).
Logiques formelles FSM 23-24 H. Jamoussi Elkamel 27

1.6 Arbre de décomposition d'une formule

Définition 3 : Un arbre est un ensemble ordonné

satisfaisant les conditions suivantes:
• il possède un plus petit élément appelé racine de
l'arbre,

• l'ensemble des minorants de chaque élément est

totalement ordonné (relation d’ordre totale).

H. Jamoussi Elkamel 28
Logiques formelles FSM 23-24

14
 1.6 Arbre de décomposition d'une formule
• Le théorème sur la décomposition des formules justifie
la méthode qui permet de :
– reconnaître si une expression donnée est une formule,
– construire, dans le cas d'une réponse positive, l'arbre de
décomposition de cette formule, c'est à dire l'ensemble
des formules qui entrent dans la construction de la
formule donnée, muni de la relation d'ordre "G est de
profondeur plus grande que F".

• Si G est une sous formule de F alors G est de

profondeur plus grande que F.

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 29

1.6 Arbre de décomposition d'une formule

• La formule M = ( ( ( p  q)   (r  s) )  p)
• L'expression M est la racine de l'arbre.
• Un sous-arbre de l’arbre de décomposition 
est associé à une sous-formule
qui entre dans la décomposition  p
de la formule
 

 q 

p r s
H. Jamoussi Elkamel 30
Logiques formelles FSM 23-24

15
 1.6 Méthode procédurale pour construire
l'arbre de décomposition d'une formule
• A une variable propositionnelle p correspond un arbre réduit à sa
racine, étiquetée par p.
• Supposons construits les arbres Arb1 et Arb2 associées aux formules Q1
et Q2 :
– à la formule  Q1 on fait correspondre l'arbre dont la racine est étiquetée par ,
et qui a Arb1 comme sous-arbre unique.
– à la formule ( Q1  Q2) on fait correspondre l'arbre dont la racine est étiquetée
par , et qui a Arb1 comme sous-arbre gauche et , Arb2 comme sous-arbre droit.
– à la formule ( Q1  Q2) on fait correspondre l'arbre dont la racine est étiquetée
par , et qui a Arb1 comme sous-arbre gauche et , Arb2 comme sous-arbre droit.
– à la formule ( Q1  Q2) on fait correspondre l'arbre dont la racine est étiquetée
par , et qui a Arb1 comme sous-arbre gauche et , Arb2 comme sous-arbre droit.
– à la formule ( Q1  Q2) on fait correspondre l'arbre dont la racine est étiquetée
par , et qui a Arb1 comme sous-arbre gauche et , Arb2 comme sous-arbre
droit.
Logiques formelles FSM 23-24 H. Jamoussi Elkamel 31

Exercice

Donner l'arbre associé à la formule

• Q=(  (q   q)  (q  r) )

H. Jamoussi Elkamel 32
Logiques formelles FSM 23-24

16
1.7 Substitution d'une sous-formule par une autre

• Soient
– Q1 et Q2 deux formules bien formées,
– et Q' une sous-formule de Q1.
L'expression obtenue en remplaçant dans Q1 la sous-
formule Q' par Q2 est une formule Q3 bien formée

Q1 Q' Q2

Q3 Q2

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 33

Exemple 5

• Substitution d'une formule à une sous-formule

Q1 = ( ( p   q )  ( p   r) )
Q' = ( p   q ) une sous formule de Q1

Q2 = ( ( p   q )  (p q))

Q3 = ( (  ( p   q )  (p q) )  ( p   r ) )

• La substitution d'une sous-formule par une autre, se

traduit par la substitution d'un sous-arbre à un autre.

H. Jamoussi Elkamel 34
Logiques formelles FSM 23-24

17
 2. Représentation des connaissances dans la
logique de propositions

• Le sens des connecteurs ne veulent pas dire exactement la

même chose que ceux du langage naturel.
• La capacité d'expression dans la représentation de la
connaissance en logique des propositions est beaucoup
moins riche qu'en langage naturel.
• Mais toutefois les connecteurs logique ont des
correspondances ou "équivalents" dans la langue
naturelle.

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 35

2. Représentation des connaissances

dans la logique de propositions
La conjonction (P  Q) peut se traduire :
– P et Q
– Q et P
– à la fois P et Q
– P, Q
– P bien que Q
– P quoique Q
– P mais Q (sous-entendu mais aussi)
– Non seulement P mais Q
– P et pourtant Q
– P tandis que Q
H. Jamoussi Elkamel 36
Logiques formelles FSM 23-24

18
 2. Représentation des connaissances
dans la logique de propositions
La disjonction (P  Q) peut se traduire :
– P ou Q
– ou P ou Q
– ou bien P ou bien Q
– soit P soit Q
– P à moins que Q
– P sauf si Q
– P ou Q ou les deux (OU inclusif)

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 37

2. Représentation des connaissances

dans la logique de propositions
• Le conditionnel (P  Q) peut traduire :
– si P alors Q
– P condition suffisante de Q
– Q condition nécessaire de P
– P alors Q
– Q si P
– Q lorsque P
– P seulement si Q
– Q pourvu que P
– ...
H. Jamoussi Elkamel 38
Logiques formelles FSM 23-24

19
 2. Représentation des connaissances
dans la logique de propositions
• L'équivalence (P  Q) peut se traduire :
– P si et seulement si Q
– P si Q et Q si P
– P condition nécessaire et suffisante de Q

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 39

3. Représentation des connaissances

dans la logique de propositions
• Les ressemblances entre les connecteurs logiques et ceux
de la langue naturelle sont limitées.
– Il mange ou il dort et il dort ou il mange semblent
synonymes
– Par contre, il a faim et il mange n'est pas semblable à
il mange et il a faim car le "et" a une connotation de
causalité et de temps.
– La porte est ouverte ou la porte est fermée. Le "ou" du
français est parfois exclusif
• La traduction est en général liée au contexte. Il peut aussi
exister plusieurs traductions possibles.
H. Jamoussi Elkamel 40
Logiques formelles FSM 23-24

20
 Exercice EX5 TD1
En notant P et Q les affirmations suivantes :
• P= "Jean est fort en Maths"
• Q=" Jean est fort en chimie"
Représenter les affirmations
"Jean est fort en Maths mais faible en Chimie"
"Jean n'est fort ni en Maths ni en Chimie"
"Jean est fort en Maths ou il est à la fois fort en Chimie et
faible en Maths"
"Jean est fort en Maths s'il est fort en Chimie"
"Jean est fort en Chimie et en Maths ou il est fort en Chimie
et faible en Maths"
Logiques formelles FSM 23-24 H. Jamoussi Elkamel 41

Exercice 5 TD1
• P= "Jean est fort en Maths"
• Q=" Jean est fort en chimie"

"Jean est fort en Maths mais faible en Chimie "

H. Jamoussi Elkamel 42
Logiques formelles FSM 23-24

21
 Exercice 5 TD1
• P= "Jean est fort en Maths"
• Q=" Jean est fort en chimie"

"Jean est fort en Maths mais faible en Chimie "

(p   q)

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 43

Exercice 5 TD1
• P= "Jean est fort en Maths"
• Q=" Jean est fort en chimie"

"Jean n'est fort ni en Maths ni en Chimie"

H. Jamoussi Elkamel 44
Logiques formelles FSM 23-24

22
 Exercice 5 TD1
• P= "Jean est fort en Maths"
• Q=" Jean est fort en chimie"

"Jean n'est fort ni en Maths ni en Chimie"

( p   q)

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 45

Exercice 5 TD1
• P= "Jean est fort en Maths"
• Q=" Jean est fort en chimie"

"Jean est fort en Maths ou il est à la fois fort en Chimie et

faible en Maths"

H. Jamoussi Elkamel 46
Logiques formelles FSM 23-24

23
 Exercice 5 TD1
• P= "Jean est fort en Maths"
• Q=" Jean est fort en chimie"

"Jean est fort en Maths ou il est à la fois fort en Chimie et

faible en Maths"

( p  (q   p ) )

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 47

Exercice 5 TD1
• P= "Jean est fort en Maths"
• Q=" Jean est fort en chimie"

"Jean est fort en Maths s'il est fort en Chimie"

H. Jamoussi Elkamel 48
Logiques formelles FSM 23-24

24
 Exercice 5 TD1
• P= "Jean est fort en Maths"
• Q=" Jean est fort en chimie"

"Jean est fort en Maths s'il est fort en Chimie"

(q  p)

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 49

Exercice 5 TD1
• P= "Jean est fort en Maths"
• Q=" Jean est fort en chimie"

« (Jean est fort en Chimie et en Maths) ou (il est fort en

Chimie et faible en Maths) "

H. Jamoussi Elkamel 50
Logiques formelles FSM 23-24

25
 Exercice 5 TD1
• P= "Jean est fort en Maths"
• Q=" Jean est fort en chimie"

« (Jean est fort en Chimie et en Maths) ou (il est fort en

Chimie et faible en Maths) "

• ( ( q  p )  ( q   p) )

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 51

Exercice 6 TD1
En notant P, Q et R les affirmations suivantes :
P= "Pierre fait des Maths"
Q=" Pierre fait de la chimie"
R=" Pierre fait de l'Anglais"
Représenter les affirmations suivantes

"Pierre fait des Maths et de l'Anglais mais pas de Chimie"

H. Jamoussi Elkamel 52
Logiques formelles FSM 23-24

26
 Exercice 6 TD1
En notant P, Q et R les affirmations suivantes :
P= "Pierre fait des Maths"
Q=" Pierre fait de la chimie"
R=" Pierre fait de l'Anglais"
Représenter les affirmations suivantes

"( Pierre fait des Maths et de l'Anglais ) mais ( pas de Chimie)"

( ( P  R )  Q )

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 53

Exercice 6 TD1
En notant P, Q et R les affirmations suivantes :
P= "Pierre fait des Maths"
Q=" Pierre fait de la chimie"
R=" Pierre fait de l'Anglais"
Représenter les affirmations suivantes

Pierre fait des Maths et de la Chimie mais pas à la fois de la

Chimie et de l'Anglais

H. Jamoussi Elkamel 54
Logiques formelles FSM 23-24

27
 Exercice 6 TD1
En notant P, Q et R les affirmations suivantes :
P= "Pierre fait des Maths"
Q=" Pierre fait de la chimie"
R=" Pierre fait de l'Anglais"
Représenter les affirmations suivantes

( Pierre fait des Maths et de la Chimie ) mais ( pas à la fois

(de la Chimie et de l'Anglais) )

(( PQ )   ( QR ))

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 55

Exercice 6 TD1
En notant P, Q et R les affirmations suivantes :
P= "Pierre fait des Maths"
Q=" Pierre fait de la chimie"
R=" Pierre fait de l'Anglais"
Représenter les affirmations suivantes

"il est faux que Pierre fasse de l'Anglais sans faire de Maths"

H. Jamoussi Elkamel 56
Logiques formelles FSM 23-24

28
 Exercice 6 TD1
En notant P, Q et R les affirmations suivantes :
P= "Pierre fait des Maths"
Q=" Pierre fait de la chimie"
R=" Pierre fait de l'Anglais"
Représenter les affirmations suivantes

"il est faux que ( Pierre fasse de l'Anglais sans faire de Maths ) "
 ( R  P )

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 57

Exercice 6 TD1
En notant P, Q et R les affirmations suivantes :
P= "Pierre fait des Maths"
Q=" Pierre fait de la chimie"
R=" Pierre fait de l'Anglais"
Représenter les affirmations suivantes

"il est faux que Pierre ne fasse pas des Maths et fasse quand
même de la Chimie"

H. Jamoussi Elkamel 58
Logiques formelles FSM 23-24

29
 Exercice 6 TD1
En notant P, Q et R les affirmations suivantes :
P= "Pierre fait des Maths"
Q=" Pierre fait de la chimie"
R=" Pierre fait de l'Anglais"
Représenter les affirmations suivantes
"il est faux que ( ( Pierre ne fasse pas des Maths ) et
(fasse quand même de la Chimie)) "
 ( P  Q)

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 59

Exercice 6 TD1
En notant P, Q et R les affirmations suivantes :
P= "Pierre fait des Maths"
Q=" Pierre fait de la chimie"
R=" Pierre fait de l'Anglais"
Représenter les affirmations suivantes

"il est faux que Pierre fasse de l'Anglais ou de la Chimie sans

faire de Maths"

H. Jamoussi Elkamel 60
Logiques formelles FSM 23-24

30
 Exercice 6 TD1
En notant P, Q et R les affirmations suivantes :
P= "Pierre fait des Maths"
Q=" Pierre fait de la chimie"
R=" Pierre fait de l'Anglais"
Représenter les affirmations suivantes

"il est faux que ( ( Pierre fasse de l'Anglais ou de la Chimie)

sans faire de Maths ) «

 ( ( R  Q )  P)

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 61

Exercice 6 TD1
En notant P, Q et R les affirmations suivantes :
P= "Pierre fait des Maths"
Q=" Pierre fait de la chimie"
R=" Pierre fait de l'Anglais"
Représenter les affirmations suivantes

"Pierre ne fait ni Anglais ni Chimie mais il fait des Maths"

H. Jamoussi Elkamel 62
Logiques formelles FSM 23-24

31
 Exercice 6 TD1
En notant P, Q et R les affirmations suivantes :
P= "Pierre fait des Maths"
Q=" Pierre fait de la chimie"
R=" Pierre fait de l'Anglais"
Représenter les affirmations suivantes

"( Pierre ne fait ni Anglais ni Chimie ) mais il fait des

Maths"
( ( R  Q )  P )

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 63

Exercice 7 TD1
Traduire ce raisonnement dans un langage de la logique de
propositions

H1 : quand je suis énervé je fais du yoga ou de la relaxation

H2 : un adepte du yoga fait de la relaxation
C : donc, quand je ne fais pas de relaxation, je suis calme.

H. Jamoussi Elkamel 64
Logiques formelles FSM 23-24

32
 Exercice 7 TD1
H1 : quand je suis énervé ( je fais du yoga ou de la relaxation)
H2 : un adepte du yoga fait de la relaxation
C : donc, quand je ne fais pas de relaxation, je suis calme.
Soient les propositions suivantes
P = je suis énervé
Q = je fais du yoga
R= je fais de la relaxation
Les formules
H1 = ( P  ( Q  R) )
H2 = ( Q  R )
C = (  R   P)
Logiques formelles FSM 23-24 H. Jamoussi Elkamel 65

Exercice 7 TD1
Traduire chacun des raisonnements dans un langage de la logique
de propositions

H1 : on prendra l’avion s’il n’y a plus de grève et si l’aéroport fonctionne

H2 : quand on prend l’avion et qu’on doit se lever tôt, on se sent fatigué
H3 : on se lève tôt et en forme quand on a bien dormi
C : donc, s’il n’y a plus de grève et si l’aéroport fonctionne, on dormira
mal

H. Jamoussi Elkamel 66
Logiques formelles FSM 23-24

33
 Exercice 7 TD1
H1 : on prendra l’avion s’il n’y a plus de grève et si l’aéroport fonctionne
H2 : quand ( on prend l’avion et qu’on doit se lever tôt) , on se sent fatigué
H3 : on se lève tôt et en forme quand on a bien dormi
C : donc, s’il n’y a plus de grève et si l’aéroport fonctionne, on dormira
mal
les propositions
A = on prend l’avion T= on doit se lever tôt
G = il y a grève S= on se sent fatigué
F= aéroport fonctionne D= on a bien dormi
Les formules
H1= ( (G F) A ) H3= ( D  (T   S ) )
H2= ( (A  T) S ) C= ( (G F)   D )
Logiques formelles FSM 23-24 H. Jamoussi Elkamel 67

Exercice 8 TD1
Enoncer la négation des affirmations suivantes en évitant
d'employer l'expression "il est faux que.«

1. "ce quadrilatère n'est ni un rectangle ni un losange"

2. "le nombre 522 n'est pas divisible par 3 mais il est
divisible par 7"
3. "si Paul ne va pas travailler ce matin il va perdre son
emploi"

4. "s'il pleut demain ou s'il fait froid, je ne sortirai pas "

H. Jamoussi Elkamel 68
Logiques formelles FSM 23-24

34
 Exercice 8 TD1
1. "ce quadrilatère n'est ni un rectangle ni un losange"

La phrase est une conjonction de négation (  F G)

La négation est une disjonction :

 (  F G)≡ (   F  G) ≡ (F  G)

ce quadrilatère est un rectangle ou un losange

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 69

Exercice 8 TD1
" le nombre 522 n'est pas divisible par 3 mais il est divisible
par 7 "

La phrase est une conjonction ( F G)

La négation d’une conjonction est la disjonction de négation
 ( F  G) ≡ (  F   G)

" le nombre 522 est divisible par 3 ou il n’ est pas divisible par
7"

H. Jamoussi Elkamel 70
Logiques formelles FSM 23-24

35
 Exercice 8 TD1

"si Paul ne va pas travailler ce matin, il va perdre son emploi"

La phrase est une implication (F  G)
La négation d’une implication est une conjonction de F et  G
 (F  G) ≡  ( F  G) ≡ (  F  G) ≡ ( F   G)

Paul n’ ira pas travailler ce matin et il ne perdra pas son emploi

Ou encore

Paul n’ira pas travailler ce matin mais il ne perdra pas son emploi

Logiques formelles FSM 23-24 H. Jamoussi Elkamel 71

Exercice 8 TD1

"s'il pleut demain ou s'il fait froid je ne sortirai pas "

( S’il pleut demain ou s'il fait froid ) alors je ne sortirai pas

La phrase est une implication (F  G)

Négation
 (F  G) ≡  ( F  G) ≡ (  F  G) ≡ ( F   G)

La négation d’une implication est une conjonction de F et  G

( S'il pleut demain ou s'il fait froid) et je sortirai

H. Jamoussi Elkamel 72
Logiques formelles FSM 23-24

36