LF INFO2 DS1 .pdf

Logique Math´
ematique
Devoir Surveill´
e

E·S·S·T·T
D´
epartement de Math´
ematiques

LF2·INFO 2009
Dur´
ee:1h30

Exercice 1 (6 points)
Deux fbf A et B sont repr´
esent´
ees par les arbres de formation suivantes :
A
∨
∧
p

B
∧
∧

q ¬ r

−→
p

∨
∧

q r

p

p

q

1. Donner l’ensemble des sous-formules des fbf A et B.
2. Dresser les tables de v´
erit´
e de A et B, d´
eduire.
3. Simplifier les fbf A ; ¬B ; (¬A → B) lorsque q ≡ p et r ≡ ¬p.
Exercice 2 (10 points)
Consid´
erons les propositions


P ≡ (A ∧ B) → C ; Q ≡ A → (B → C) ;


R ≡ (A → C) ∨ (B → C)

1. D´
emontrer, par les tables de v´
erit´
e, que (P ↔ Q) et (P ↔ R) sont tautologiques.
´
2. Etudier
par la m´
ethode des tableaux la validit´
e de (P ↔ Q) et (P ↔ R).
3. Exprimer les formules P , Q et R en utilisant seulement les connecteurs ¬ et ∨.
4. En utilisant les lois logiques, d´
emontrer que (P ∨ ¬R) ≡ > et (Q ∧ ¬R) ≡ ⊥.
Exercice 3 (4 points)
Trois personnes A, B et C sont accus´
ees d’un crime d´
eclarent respectivement :
DA : B est coupable et C est innocent.
DB : Si A est coupable alors C l’est aussi.
DC : Je suis innocent mais au moins l’une des deux autres est coupable.
Utiliser le formalisme du calcul des propositions pour traduire les questions suivantes
et donner la r´
eponse :
(a) Les trois d´
eclarations sont-elles compatibles ? Lorsqu’elles sont compatibles qui est
coupable ?
(b) Si tous sont innocents lequel a menti ?
(c) Si tous disent la v´
erit´
e qui est coupable ?

Logique Math´
ematique
Devoir Surveill´
e

E·S·S·T·T
D´
epartement de Math´
ematiques

LF2·INFO 2009
Dur´
ee:1h30

Exercice 1 (6 points)
1)

• Les sous-formules de A sont : (p ∧ q) ∨ (¬p ∧ r) , (p ∧ q), (¬p ∧ r), p, q, ¬p et r

• Les sous-formules de B sont : (p → q) ∧ (r ∨ (p ∧ q)) , (p → q), (r ∨ (p ∧ q)), (p ∧ q),p,
q et r
2)
((p
1
1
1
1
0
0
0
0
(1)

∧
1
1
0
0
0
0
0
0
(3)

q)
1
1
0
0
1
1
0
0
(1)

∨
1
1
0
0
1
0
1
0
(4)
N

(¬
0
0
0
0
1
1
1
1
(2)

p
1
1
1
1
0
0
0
0
(1)

∧
0
0
0
0
1
0
1
0
(3)

r))
1
0
1
0
1
0
1
0
(1)

(p
1
1
1
1
0
0
0
0
(1)

→
1
1
0
0
1
1
1
1
(3)

q)
1
1
0
0
1
1
0
0
(1)

∧ (r
1
1
1
0
0
1
0
0
1
1
0
0
1
1
0
0
(4) (2)
N

∨
1
1
1
0
1
0
1
0
(3)

(p
1
1
1
1
0
0
0
0
(1)

∧
1
1
0
0
0
0
0
0
(2)

Conclusion :A ≡ B


q))
1
1
0
0
1
1
0
0
(1)

3)
A ≡


(p ∧ p) ∨ (¬p ∧ ¬p)

≡ (p ∨ ¬p) idempotence
≡ > tautologie


¬B ≡ ¬ (p → p) ∧ (¬p ∨ (p ∧ p))

≡ ¬ (¬p ∨ p) ∧ (¬p ∨ (p ∧ p)) implication

≡ ¬ (¬p ∨ p) ∧ (¬p ∨ p) idempotence
≡ ¬ > ∧ >) idempotence
≡ ¬> identit´e
≡ ⊥

Exercice 2 (10 points)
1)
(A ∧ B)
1
1
1
1
0
0
0
0

1
1
0
0
0
0
0
0

1
1
0
0
1
1
1
0

→ C
1
0
1
1
1
1
1
1



1
0
1
0
1
0
1
0

↔

A

→ (B


→ C)

1
1
1
1
1
1
1
1
N

1
1
1
1
0
0
0
0

1
0
1
1
1
1
1
1

1
0
1
1
1
0
1
1

Conclusion : (P ↔ Q) est une tautologie

1
1
0
0
1
1
0
0

1
0
1
0
1
0
1
0

2)

F : ((A ∧ B) → C) ↔ (A → (B → C))

√
V : ((A ∧ B) → C)
√
F : (A → (B → C))

√
F : ((A ∧ B) → C)
√
V : (A → (B → C))
V : (A ∧ B)
F:C
V : (B → C)

√

V:A
V:B
V:B
V:C
×

√

√

F:A

V:C
V:A
√
F : (B → C)
V:A
V:B
F:C
×

V:A
V:B
×

F:B
×

√
F : (A ∧ B)
V:A
√
F : (B → C)
F:A
V:A
×

F:B
V:B
F:C
×


√
F : (A ∧ B) → C ↔ (A → C) ∨ (B → C)

√
F : (A ∧ B) → C
√
V : (A → C) ∨ (B → C)
V : (A ∧ B)
F:C

V : (A → C)
V:A
V:B
V : ¬A
V:C
×

√

√
V : (A ∧ B) → C
√
F : (A → C) ∨ (B → C)

√

V : (B → C)
V:A
V:B

√

V : ¬B
V:C
×

3)
P ≡
≡
≡
≡
Q ≡
≡
≡
R ≡
≡

(A ∧ B) → C



¬ (¬A ∨ ¬B) → C




De Morgan

¬¬ (¬A ∨ ¬B) ∨ C
implication

(¬A ∨ ¬B) ∨ C
double n´egation

A → (B → C)

¬A ∨ (B → C)
implication

¬A ∨ (¬B ∨ C)
implication

(A → C) ∨ (B → C)

(¬A ∨ C) ∨ (¬B ∨ C)
implication

4)


(P ∨ ¬R) ≡





(¬A ∨ ¬B) ∨ C ∨ ¬ (¬A ∨ C) ∨ (¬B ∨ C)
commutativit´e



≡
(¬A ∨ ¬B) ∨ C ∨ ¬ (¬A ∨ ¬B) ∨ (C ∨ C)
associativit´e




≡
(¬A ∨ ¬B) ∨ C ∨ ¬ (¬A ∨ ¬B) ∨ C
idempotence


≡ (P ∨ ¬P )
≡ >

hypoth`ese

tautologie




¬A ∨ (¬B ∨ C) ∧ ¬


≡
¬A ∨ (¬B ∨ C) ∨ ¬


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


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

(Q ∧ ¬R) ≡

≡ (P ∧ ¬P )
≡ ⊥

hypoth`ese

antilogie

(¬A ∨ C) ∨ (¬B ∨ C)




la commutativit´e

(¬A ∨ ¬B) ∨ (C ∨ C)
associativit´e


idempotence
(¬A ∨ ¬B) ∨ C


¬A ∨ (¬B ∨ C)
associativit´e

Exercice 3 (4 points)
(a) DA ≡ B ∧ ¬C
DB ≡ A → C
DC ≡ ¬C ∧ ( A ∨ B )
B

∧

¬

C

A

→

C

¬

C

∧

(A

∨

B)

1
1
1
1
0
0

0
0
1
1
0
0

0
0
1
1
0
0

1
1
0
0
1
1

1
0
1
0
1
0

1
1
0
1
1
1

1
1
0
0
1
1

0
0
1
1
0
0

1
1
0
0
1
1

0
0
0
0
0
1

1
0
1
0
1
0

1
1
1
1
1
0

1
1
1
1
0
0

`1
`2
`3
`4
`5
`6

0

0

1

0

1

0

0

1

0

0

1

1

0

`7

0

0

1

0

0

1

0

1

0

1

0

0

0

`8

A1

A3

A2

A1

B1

B2

B1

C2

C1

C3

C1

C2

C3

Les trois d´eclarations sont compatibles pour la 7i`eme ligne de la table de v´erit´e,
c’est a` dire dans le cas qui correspond aux A coupable B innocent et C innocent.

(d) Tous sont innocents donc la valeur de v´erit´e pour chaque personne A, B et C est 0,
et leurs d´eclarations est alors comme suit :
B ∧ ¬C est fausse
A → C est vraie
¬C ∧ ( A ∨ B ) est vraie
Conclusion : A ment.
(d) Tous disent la v´erit´e donc la valeur de v´erit´e pour les t´emoignages DA , DB et DC est
1:
la d´eclaration DA ≡ B ∧ ¬C est vraie pour B coupable et C innocent
la d´eclaration DB = A → C ≡ ¬A ∨ C est vraie puisque C est innocent alors A est
innocent
la d´eclaration DC = ¬C ∧ ( A ∨ B ) est vraie est confirmer par le choix de B coupable et
A et C innocents
Conclusion : B est coupable , A est innocent et C est innocent.