LF INFO2 DS1 .pdf



Nom original: LF_INFO2_DS1.pdf

Ce document au format PDF 1.4 a été généré par TeX / MiKTeX pdfTeX-1.40.10, et a été envoyé sur fichier-pdf.fr le 29/12/2009 à 12:42, depuis l'adresse IP 41.230.x.x. La présente page de téléchargement du fichier a été vue 1716 fois.
Taille du document: 156 Ko (6 pages).
Confidentialité: fichier public


Aperçu du document


Logique Math´
ematique
Devoir Surveill´
e

E·S·S·T·T

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

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.


Aperçu du document LF_INFO2_DS1.pdf - page 1/6

Aperçu du document LF_INFO2_DS1.pdf - page 2/6

Aperçu du document LF_INFO2_DS1.pdf - page 3/6

Aperçu du document LF_INFO2_DS1.pdf - page 4/6

Aperçu du document LF_INFO2_DS1.pdf - page 5/6

Aperçu du document LF_INFO2_DS1.pdf - page 6/6




Télécharger le fichier (PDF)


LF_INFO2_DS1.pdf (PDF, 156 Ko)

Télécharger
Formats alternatifs: ZIP



Documents similaires


h8qwrj3
in100 poly td 2016 2017 13351076 1
synthese du module 2 point 16 inclus
oracle
acpstid2 copy
c polycop2

Sur le même sujet..




🚀  Page générée en 0.194s