TD1 Et TD2

TRAVAUX DIRIGES N°1
Exercice 1: Parmi les assertions suivantes, lesquelles sont vraies, lesquelles

sont fausses et pourquoi ?
1.Soit Cléopâtre était chinoise, soit les grenouilles aboient. 2.Soit les
roses sont des animaux, soit les chiens ont 4 pattes. 3.Si l’homme est
un quadrupède, alors il parle. 4.Les roses ne sont ni des animaux, ni
des fleurs. 5.Alger est en Algerie ou Madrid est en chine. Exercice 2:
Soient (P), (Q)
Exercice 3: Soient les 4 assertions suivantes :

Les assertions 1,2,3 et 4 sont-elles vraies ou fausses ? Donner leur
négation.
Exercice 4: Traduisez les énoncés suivants en formule logique:
1. Quand il fait beau, Jean est heureux; il fait mauvais; donc Jean
est heureux.
2. Quand il fait beau, Jean est heureux; or il fait mauvais donc Jean
est
3. Quand il fait beau, Jean est heureux; or, Jean est malheureux;
donc il fait mauvais.
Exercice 4: soit le raisonnement suivant :
- Quand il fait soleil, je mets mes lunettes ou je ne sors pas.

- je ne reste à la maison que sans lunettes et par temps gris.
Donc si je ne mets pas mes lunettes, c’est qu’il fait gris.
1. Formuleser ce raisonnement en utilisaant les variable suivants :

s: il fait soleil, l: je mets mes lunettes, m: je reste à la maison
2. Montres que raisonnement ci-dessous est coorect(valide):

(a) en utilisant la table de verité;
(b) en utilisant une mise en formule normale par le calcul (algébriquement)
Exercice 5:
1. Dire si l’affirmation suivant est correcte ou non, justifier votre

réponse. -Soit valid un algorithme qui répond vrais pour une
formule P si la formule P est valide et faux sinon. Apartir de
valid,il est posible de construire un algoritheme sat qui repond
vrai si son entrée est une formule satisfiable et faux sinon.
1
2. Ecrire a l’aide de quantificateurs les propositions suivantes: - Le
carré de tout réel est positif.
- Certaines réels sont strictement supperieurs a leur carré.
Exercice 6: Trois collègues, Albert, Bernard et Charles déjeunent en-

semble chaque jour ouvrable. Les
affirmations suivantes sont vraies :
1. Si Albert commande un dessert, Bernard en commande un aussi.
2. Chaque jour, soit Bernard, soit Charles, mais pas les deux, com-
mandent un dessert.
3. Albert ou Charles, ou les deux, commandent chaque jour un dessert.
4. Si Charles commande un dessert, Albert fait de même.
Question : Exprimer les données du problème comme des formules
propositionnelles
Exercice 7: Dire si les affirmation suivants correctes ou non, justifier

vos reponses.
1. Soit valid un algorithme qui répond vrai pour une formule P si

la formule P est valide et faux sinon.
2. il existe un algoritheme qui etant donnée une formule du calcule
des predicats repond vrai sur une entrée P si la formule P est
satisfiable et faux sinon.
Exercice 8 Compléter les pointillés par les connecteur logique qui

s’impose : ⇔, ⇐, ⇒.
1. x ∈ Rx2 = 4......x = 2;
2. z ∈ Cz = z.......z ∈ R;
3. x ∈ Rx = π.......e2 ix = 1
Exercice 9: Soit les quatre assertions suivantes:
1. assertions a,b,c et d sont-elles vraies ou fausses ?

2. Donner leur négation.
Exercice 11 Nier la proposition : ”tous les habitants de la rue de havre

qui ont les yeux bleus gangneront au loto et prendront leur retraite
avant 50 ans ”
Exercice 12 Nier les assersions suivantes :
1. tout triangle regtangle posséde un angle droit;

2. dans toutes les ecuiries, tous les chevaux sont noirs;
2
3. pour tout entier x, il existe un entier y tel que, pour tout entier
z, la relation z¡x implique le relation z¡x+1;
4. ∀ > 0∃α > 0(|x − 7/5| < α ⇒ |5x − 7| < .
Exercice 13 P, QetR designe trois propositions logiques.
1. Construire les tables de vérité des propositions suivantes:

(a) P ⇒ (Q ⇒ P )
V
(b) P ⇒ (Q ⇒ (P Q))
V
(c) (P Q) ⇔ (¬(P ⇒ ¬Q))
2. Exprimer sans ⇒ ni ⇔
(a) ¬(Q ⇔ P )
(b) ¬((P ∨ Q) ⇒ Q)
(c) ¬(P ⇒ (Q ⇒ R))
Exercice 14
1. Laquelle des formules suivantes est equivalente à P et(P ouQ)?

(a) P etQ
(b) P ouQ
(c) P
(d) Q
2. Laquelle des formules suivantes est equivalente à (P etQ)etQ)?
(a) P etQ
(b) P ouQ
(c) P
(d) Q
Exercice 15
1. Quelle est la negation de : (nonP )etQ?

(a) P et(nonQ)
(b) P ou(nonQ)
(c) (nonP )ouQ
2. Quelle est la negation de : P ou(nonQ)?
(a) (nonP )ouQ
(b) (nonP )etQ
(c) (nonP )et(nonQ)
(d) P et(nonQ)
3. Quelle est la negation de : (nonP )ou(nonQ)?
3
(a) P etQ
(b) P ouQ
(c) (nonP )et(nonQ)
(d) (nonP )et(nonQ)
Exercice 16 Dans un journal est annoncée la nouvelle suivante :

L’armée ne quittera pas le pays tant que le calme n’est pas revenue.
En considerant l’annonce officielle précédente comme vraie, dire si les
argumentations suivants sont correctes:
1. ”le calme est revenu, donc l’armé quitte le pays.”

2. ”L’armé quitte le pays, donc le calme est revenu.”
3. ”L’armé n’a pas quitte le pays, donc le calme n’est pas revenu. ”
Exercice 17 Onsuppose que a et b sont des nombres réels.Representer

par une formule logique la valeur de chacune des expressions suivantes
en langages Python:
1. if a ¿ b: a ¡ 2*b else: True

2. if a ¿ b: a ¡ 2*b else: False
3. if a ¿ b: a ¡ 2*b else: b ¡ 3*a
Exercice 18 Parmi les formules suivants lequelles sont satisfiables, des

antilogies, valides, des tautologies ?
1. x ⇒ (y ⇒ x)
2. (x ⇒ (y ⇒ z)) ⇒ ((x ⇒ y) ⇒ (x ⇒ z))
3. (x ⇒ y) ⇒ (¬y ∨ x)
Exercice 19: soit le rapport de police suivant:
si le prevenu a commis le vol, c’est que ce vol a été minitieusement

préparé, ou alors le perevenu avait un complice. Si le vol a été
minitieusement préparé, alors, si le prevenu avait un complice, un
butin important a été emporté. Or le butin n’a pasété important.
Donc, le prevenu n’a pas commis le vol.
1. Modeliser ce raisonement en logique de proposition.

2. Ce raisonement est il valide ? justifiez la reponse.
Exercice 20 Les Formules suivante sont elle sémantiquement équivalentes

? (justifier la reponse)
V
- A → C (C → ¬A)et¬A
4
V
- A→C (C → ¬A)etA
V V V
- (p → q) (¬P → r)et(p q) ∨ (¬p r)
V V V
- (p q) ∨ (¬p r)et(¬p ∨ q) (p ∨ q)
TRAVAUX DIRIGES N°2
Exercice 1
1-Effectuez les substitutions textuelles suivantes, puis supprimez les par-
enthèses superflues :
(a)(a + b.3)[b, a := a.b, a.a]
(b)((x + y).z)[x, y := x, y]
(c)(x + x.2)[x, y := x, z][x := y]
(d)(x + x.y + x.y.z)[x, y := y, x][y := 2.y]
Exercice 2
La règle d’inférence de Leibniz (1.13) donne lieu à une infinité de règles
d’inférence particulières obtenues en assignant une expression à ses trois
paramètres E, XetY .Il y a ci-dessous des cas particuliers de la règle de Leib-
niz, avec une partie manquante.
Trouvez la partie manquante et donnez l’expression E correspondante. Don-
nez toutes les réponses possibles.
x=x+2
(a) 4.x+y=?
a=b+2
(b) ?=3.(b+2)+3.b+1
Exercice 3
Cet exercice porte sur la règle de Leibniz (1.13). On vous donne l’expression
E[z := X] ainsi que l’indice X = Y . Trouvez l’expression résultante
E[z := Y ].
E[z := X] X=Y
(x + y) · w w =x·y
p∩q q =q∪r
Exercice 4
Cet exercice porte sur la règle de Leibniz (1.13). Pour chacune des paires
d’expressions E[z := X] et E[z := Y ] ci-dessous, donnez les expressions X et
Y telles que E[z := X] = E[z := Y ]. Indiquez ensuite quelle est l’expression
E. Donnez toutes les réponses possibles.
E[z := X] E[z := Y ]
(b · y · x y·x·x
p ⇒ q ∧ (r ∨ p) p⇒q∧q
5
Exercice 5
Utilisez la table de préséance suivante pour faire les substitutions demandées.
A l’exception de la substitution, tous les opérateurs sont des expressions bi-
naires. La priorité 1 est la plus élevée et 7 la plus faible.
Priorité Opérateur
1 [x := e](substitution)
2 >k
3 ♥
4 ♦
*5 ♣
6 ♠
7 ?†4
(a) ((x>y)kz♦x) [x := y♥x]
(b) ((x♥y)>(z ? x♥y) ? x)[x := z♦z]
(c) x♥y♠x ? z♦x♥y[x, y := x>y, y4x]
(d) ((x ? y) † x)[x, y := x♦x, x4x]
(e) (x>x4x)[x, y := y, z]
(f) (x>x4x)[x := y][y := z]
(g) ((x ? y) † x)[x := x♦x][y := x4x]
(h) (x♥y♠x ? z♦x♥y)[x := x>y][y := y4x]
Exercice 6
Nous aimerions que les expressions X = Y et (X = Y ) = (Y = X) soient
des théorèmes, où XetY sont des expressions quelconques. Cependant les
axiomes (1.10) et (1.11) sont restreints au cas où XetY sont des variables
(xety). Perd-on de la généralité avec (1.10)(1.11) ?
Exercice 7
La Loi de Leibniz dit que deux expressions sont égales si et seulement si
le remplacement de l’une par l’autre dans n’importe quelle expression E ne
change pas la valeur de E .Cette Loi peut et̂re décomposée en deux parties
(les symboles XetY sont ajoutés pour que le passage à la règle (1.13) soit
plus clair) :
- Si deux expressions XetY sont égales, alors le remplacement de l’une par
l’autre dans n’importe quelle expression E ne change pas la valeur de E.
- Si, quelle que soit l’expression E, le remplacement d’une expression X par
une expression Y dans E ne change pas la valeur de E, alors XetY sont
6
égales.
La règle (1.13) correspond à la première partie. En effet, la règle (1.13)

dit que si X = Y , alors E[z := X] = E[z := Y ] est un théorème pour toute
expression E, alors X = Y .
Exercice 8
a)
(1) (A ∩ B) ∪ B c = A ∪ B c
(2) (A − B) − C = A − (B ∪ C).
(3) A − (B ∩ C) = (A − B) ∪ (A − C)
b) Simplifier
(1) (A ∪ B)∩ (C ∪ Ā)
(2) (A ∪ B)∪ (C ∪ Ā)
Exercice 9
Soient E = [0, 1], F = [−1, 1], etG = [0, 2] trois intervalles de R.
Considérons l’application f de E dans G définie par : f (x) = 2 − x, et
l’application g de F dans G définie par : g(x) = x2 + 1
(1) Déterminer f (1/2), f − 1(0), g([−1, 1]), g − 1[0, 2].
(2) l’application f est-elle bijective ? justifier.
(3) L’application g est-elle bijective ? justifier . Exercice 10
On définit sur R2 la relation R par :

0 0 0
(x, y)R(x , y) ⇔ x + y = x + y
(1) Montrer que R une relation d’équivalence.
(2) Trouver la classe d’équivalence du couple (0,0).
Exercice 11
On définit sur R2 la relation T par
0 0 0
(x, y)R(x , y ) ⇔ |x − x | ≤ y 0 − y
(1) Vérifier que T est une relation d’ordre. Cet ordre est-il total ?
(2) Soit (a, b) ∈ R2 , représenter l’ensemble (x, y) ∈ R2 /(x, y)T (a, b).
Exercice 12
Déterminer la table de vérité de la proposition suivante :
((P ∧ Q) ∨ (Q ∧ P )) ⇔ ((P ∨ Q) ∧ (Q ∨ P )).
Exercice 13
Sur l’ensemble Z des nombres entiers, on définit la relation binaire R suiv-
ante :
xRy ⇔ 3x − y est un nombre pair.
i)
7
ii)
iii) Déterminez l’ensemble quotidien Z/R.
Exercice 14
Sur l’ensemble A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} on définit la relation binaire
suivante :
x y ⇔ y − x ∈ Np
où Np = {0, 2, 4, 6, . . .} est l’ensemble des nombres naturels pairs.
i) Montrez que est une relation d’ordre.
ii) Déterminez, s’ils existent, les éléments maximaux de A.A admet-il un
maximum?
iii) Déterminez, s’ils existent, les éléments minimaux de A.A admet-il un
minimum?
iv) L’ordre est-il total?
v) Déterminez, s’ils existent, les majorants du sous-ensemble B = {3, 8}.B
a-t-il une borne supérieure?
vi) Déterminez, s’ils existent, les majorants du sous-ensemble C = {3, 5}.C
a-t-il une borne supérieure?
Exercice 15
soient n, p des nombres naturels, avec p ≤ n. Démontrez que
Pn
k=p (k/p) = (n + 1p + 1)
par récurrence sur n :

i) Prouvez le résultat pour n=0.
ii) Maintenant on suppose le résultat vrai pour n. Prouvez-le pour n + 1 (il
faut d’abord considérer le cas p ≤ n) et en suite le cas p = n + 1. (indication
:formule de Pascale).
iii) Concluez.
Exercice 16
Pnsoient n, p des nombres naturels, avec p ≤ n. On veut montrer que

i=p (ip) = (n + 1n − p)
Par récurrence sur n.

i) Prouvez le résultat pour n=0.
ii) Maintenant on suppose le résultat vrai pour n. Prouvez-le pour n + 1 (il
faut d’abord considérer le cas p ≤ n) et en suite le cas p = n + 1. (indication
:formule de Pascale).
iii) Concluez.

TD1 Et TD2

Transféré par

Droits d'auteur :

Formats disponibles

TD1 Et TD2

Transféré par

Informations du document

Description originale:

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

TD1 Et TD2

Transféré par

Droits d'auteur :

Formats disponibles

TRAVAUX DIRIGES N°1

Exercice 1: Parmi les assertions suivantes, lesquelles sont vraies, lesquelles

Exercice 3: Soient les 4 assertions suivantes :

 Exercice 4: Traduisez les énoncés suivants en formule logique:

Exercice 4: soit le raisonnement suivant :

- Quand il fait soleil, je mets mes lunettes ou je ne sors pas.

Donc si je ne mets pas mes lunettes, c’est qu’il fait gris.

1. Formuleser ce raisonnement en utilisaant les variable suivants :

2. Montres que raisonnement ci-dessous est coorect(valide):

1. Dire si l’affirmation suivant est correcte ou non, justifier votre

Exercice 6: Trois collègues, Albert, Bernard et Charles déjeunent en-

Exercice 7: Dire si les affirmation suivants correctes ou non, justifier

1. Soit valid un algorithme qui répond vrai pour une formule P si

Exercice 8 Compléter les pointillés par les connecteur logique qui

 Exercice 9: Soit les quatre assertions suivantes:

1. assertions a,b,c et d sont-elles vraies ou fausses ?

Exercice 11 Nier la proposition : ”tous les habitants de la rue de havre

Exercice 12 Nier les assersions suivantes :

1. tout triangle regtangle posséde un angle droit;

 Exercice 13 P, QetR designe trois propositions logiques.

1. Construire les tables de vérité des propositions suivantes:

1. Laquelle des formules suivantes est equivalente à P et(P ouQ)?

1. Quelle est la negation de : (nonP )etQ?

Exercice 16 Dans un journal est annoncée la nouvelle suivante :

1. ”le calme est revenu, donc l’armé quitte le pays.”

Exercice 17 Onsuppose que a et b sont des nombres réels.Representer

1. if a ¿ b: a ¡ 2*b else: True

Exercice 18 Parmi les formules suivants lequelles sont satisfiables, des

 Exercice 19: soit le rapport de police suivant:

si le prevenu a commis le vol, c’est que ce vol a été minitieusement

1. Modeliser ce raisonement en logique de proposition.

Exercice 20 Les Formules suivante sont elle sémantiquement équivalentes

TRAVAUX DIRIGES N°2

(a) ((x>y)kz♦x) [x := y♥x]

(b) ((x♥y)>(z ? x♥y) ? x)[x := z♦z]

(c) x♥y♠x ? z♦x♥y[x, y := x>y, y4x]

(d) ((x ? y) † x)[x, y := x♦x, x4x]

(f) (x>x4x)[x := y][y := z]

(g) ((x ? y) † x)[x := x♦x][y := x4x]

(h) (x♥y♠x ? z♦x♥y)[x := x>y][y := y4x]

La règle (1.13) correspond à la première partie. En effet, la règle (1.13)

On définit sur R2 la relation R par :

par récurrence sur n :

Pnsoient n, p des nombres naturels, avec p ≤ n. On veut montrer que

Par récurrence sur n.

Vous aimerez peut-être aussi

Exercice 4: Traduisez les énoncés suivants en formule logique:

Exercice 9: Soit les quatre assertions suivantes:

Exercice 13 P, QetR designe trois propositions logiques.

Exercice 19: soit le rapport de police suivant: