INFZ21, logiques du raisonnement valide

Formules bien formées

Les « formules » suivantes sont-elles des formules bien formées ?

Parenthèsage

Explicitez le parenthèsage implicite des formules suivantes :

1. a → b → c ≡ ((a → b) → c)
2. a ∨ b ∧ c ≡ (a ∨ (b ∧ c))
3. a ∨ b ∧ c ↔ d → ￢ e ∨ f ∧ g ≡ ((a ∨ (b ∧ c)) ↔ (d → ((￢e) ∨ (f ∧ g))))

Simplifiez au maximum le parenthèsage des formules suivantes :

1. (a) ≡ a
2. ((a ∨ b)) ≡ a ∨ b
3. ((a) ∧ (b)) ≡ a ∧ b
4. (￢(a ∨ b)) ≡ ￢(a ∨ b)
5. ￢(((a) ∧ b)) ≡ ￢(a ∧ b)
6. a ∨ (b ∧ c) ≡ a ∨ b ∧ c
7. (a ∨ b) ∧ c ≡ (a ∨ b) ∧ c
8. ((a ∧ b) → c) ≡ a ∧ b → c
9. (a ∧ (b → c)) ≡ a ∧ (b → c)
10. ((a ∨ b) ∧ c) ↔ e ≡ (a ∨ b) ∧ c ↔ e
11. (((a ∨ b) ∧ c) ↔ e) → f ≡ ((a ∨ b) ∧ c ↔ e) → f
12. ((a ∧ b) ∨ c) ↔ (e → f) ≡ a ∧ b ∨ c ↔ e → f
13. (((a → b) → c) → d) ≡ a → b → c → d
14. (a ∧ (b ∧ c)) ≡ a ∧ b ∧ c
15. (a → (b → c)) ≡ a → (b → c)

Formalisation d'un énoncé

Traduisez les énoncés suivants en formule logique :

1. Quand il fait beau, Jean est heureux ;
   il fait soleil ;
   donc, Jean est heureux.
2. Quand il fait beau, Jean est heureux ;
   or, Jean est malheureux ;
   donc il fait mauvais.
3. Propositions élémentaires :
   b ≡ il fait beau ;
   h ≡ Jean est heureux.
   Hypothèse 1 : H₁ ≡ b → h (Quand il fait beau, Jean est heureux)
   Hypothèse 2 : H₂ ≡ b (il fait soleil)
   Conclusion : C ≡ h (Jean est heureux)
   Formulation : H₁ ∧ H₂ → C ≡ (b → h) ∧ b → h
4. Propositions élémentaires :
   b ≡ il fait beau ;
   h ≡ Jean est heureux.
   Hypothèse 1 : H₁ ≡ b → h (Quand il fait beau, Jean est heureux)
   Hypothèse 2 : H₂ ≡ ￢b (il fait mauvais)
   Conclusion : C ≡ ￢h (Jean est malheureux)
   Formulation : H₁ ∧ H₂ → C ≡ (b → h) ∧ ￢b → ￢h
5. Propositions élémentaires :
   b ≡ il fait beau ;
   h ≡ Jean est heureux.
   Hypothèse 1 : H₁ ≡ b → h (Quand il fait beau, Jean est heureux)
   Hypothèse 2 : H₂ ≡ ￢h (Jean est malheureux)
   Conclusion : C ≡ ￢b (il fait mauvais)
   Formulation : H₁ ∧ H₂ → C ≡ (b → h) ∧ ￢h → ￢b

Ajouter la proposition élémentaire s ≡ il fait soleil produirait une traduction correcte, mais de piètre qualité, car elle aboutirait à une formule dont on ne pourrait rien tirer.

Équivalence de formules

À l'aide d'une table de vérité, vérifiez les deux équivalences de Morgan.

Première équivalence : ￢(A ∨ B) ≡ ￢A ∧ ￢B

Les deux formules sont équivalentes (soit toutes les deux fausses, soit toutes les deux vraies) dans toutes les interprétations (quelles que soient les valuations de A et B), il s'agit donc de formules équivalentes.

Deuxième équivalence : ￢(A ∧ B) ≡ ￢A ∨ ￢B

Les deux formules sont équivalentes dans toutes les interprétations, elles sont donc équivalentes.

Valeur de formules

1. À l'aide d'une table de vérité, étudiez la validité et la consistance des formules que vous avez trouvées pour l'exercice « Formalisation d'un énoncé » du TD 1.2.2Travaux dirigés (la syntaxe).

   b	h		b → h	(b → h) ∧ b	(b → h) ∧ b → h
   F	F		T	F	T
   F	T		T	F	T
   T	F		F	F	T
   T	T		T	T	T

   Premier énoncé : (b → h) ∧ b → h

   L'énoncé est vrai dans toutes les interprétations (quelles que soient les valuations de b et h), il est donc valide et donc, à fortiori, consistant.

   L'énoncé est vrai dans toutes les interprétations, il est donc valide et donc, à fortiori, consistant.

   Deuxième énoncé : (b → h) ∧ ￢h → ￢b

   b	h		b → h	￢h	(b → h) ∧ ￢h	￢b	(b → h) ∧ ￢h → ￢b
   F	F		T	T	T	T	T
   F	T		T	F	F	T	T
   T	F		F	T	F	F	T
   T	T		T	F	F	F	T

2. À l'aide d'une table de vérité, étudiez la validité et la consistance de la formule suivante :

   

Pour simplifier les écritures, nous désigneront par F₁ la formule P ∧Q → ￢R et par F₂ la formule ￢P ∧ R.

L'écriture de table de vérité complète devient vite fastidieuse. Aussi est-il souvent intéressant de ne construire qu'une table de vérité partielle. Par exemple, pour la formule précédente, on peut construire une table de vérité partielle comme décrit ci-dessous.

1. Si on regarde la table de vérité de l'implication A → B () on se rend compte que quand B est vrai, A → B est vrai quelle que soit la valeur de A.

   Or ￢Q vrai est équivalent à Q faux. Donc, quand Q est faux la formule F est vrai.

   Ainsi, quand ￢Q est vrai est également vrai, quelle que soit la valeur de (P ∧ Q → ￢R) ∧ ￢P ∧ R.

   On en déduit immédiatement les lignes (1), (2), (5) et (6), soit la moitié de la table de vérité !

2. De même, si on regarde à nouveau la table de vérité de l'implication A → B () on se rend compte que quand A est faux, A → B est vrai quelle que soit la valeur de B.

   Ainsi, quand (P ∧ Q → ￢R) ∧ ￢P ∧ R est faux, la formule est vrai, quelle que soit la valeur de ￢Q.

   On en déduit immédiatement les lignes (3) et (7).

   Ainsi, quand R est faux, la conjonction (P ∧Q → ￢R)∧￢P ∧R est également fausse et la formule F est alors vraie.

   Or (P ∧Q → ￢R)∧￢P ∧R est la conjonction des trois formules : P ∧Q → ￢R, ￢P et R. Donc (P ∧Q → ￢R)∧￢P ∧R est faux dès que l'une des trois formules est fausse.

3. De même, quand P est vrai, ￢P est faux, ce qui entraîne que la conjonction (P ∧ Q → ￢R) ∧ ￢P ∧ R est également fausse et donc que la formule F est vraie.

   On en déduit immédiatement la ligne (8).

4. Il ne reste plus qu'à évaluer de manière classique la ligne (4) de la table de vérité.

Traduction

Traduire en formule logique les énoncés suivants, puis étudier leur validité et leur consistance :

1. Quand on fait de l'alpinisme, on est montagnard ou sportif ;
   un montagnard est un sportif ;
   donc, quand on n'est pas sportif, on ne fait pas d'alpinisme.
2. Il ne dit rien s'il travaille ou s'il est seul ;
   il se repose, mais il se tait ;
   donc il est seul.
3. Jean ne sort que s'il fait beau ;
   or, il pleut ;
   donc, Jean reste chez lui.
4. Propositions élémentaires :
   A ≡ Faire de l'alpinisme ;
   M ≡ Être montagnard ;
   S ≡ Être sportif.
   Hypothèse 1 : H₁ ≡ A → M ∨ S
   Hypothèse 2 : H₂ ≡ M → S
   Conclusion : C ≡ ￢S → ￢A
   Formulation : H₁ ∧ H₂ → C ≡ (A → M ∨ S) ∧ (M → S) → (￢S → ￢A)
   Une table de vérité permettra de montrer que cette formule est valide (et donc, à fortiori, consistante).
5. Propositions élémentaires :
   P ≡ Ne pas parler ;
   T ≡ Travailler ;
   S ≡ Être seul.
   Hypothèse 1 : H ≡ T ∨ S → P
   Hypothèse 2 : H ≡ ￢T ∧ P
   Conclusion : C ≡ S
   Formulation : H ∧ H → C ≡ (T ∨ S → P) ∧ (￢T ∧ P) → S
   Une table de vérité permettra de montrer que cette formule est invalide, mais consistante. En fait, elle n'est fausse que dans l'interprétation :

   {m(T) = F, m(S) = F, m(P) = T}

6. Propositions élémentaires :
   S ≡ Sortir ;
   B ≡ Beau temps.
   Hypothèse 1 : H₁ ≡ S → B
   Hypothèse 2 : H₂ ≡ ￢B
   Conclusion : C ≡ ￢S
   Formulation : H₁ ∧ H₂ → C ≡ (S → B) ∧ ￢B → ￢S
   Une table de vérité permettra de montrer que cette formule est valide (et donc, à fortiori, consistante).

Démonstration

Montrer que les deux premières équivalences de l'absorption sont justes en utilisant, entre autres, la distributivité.

• A ∨ (￢A ∧ B) ≡ A ∨ B
  ≡ (A ∨ ￢A) ∧ (A ∨ B)
  ≡ T ∧ (A ∨ B)
  ≡ A ∨ B
• A ∧ (￢A ∨ B) ≡ A ∧ B
  ≡ (A ∧ ￢A) ∨ (A ∧ B)
  ≡ F ∨ (A ∧ B)
  ≡ A ∧ B

Simplification

En utilisant des équivalences de formules (propriété 1.1), tenter de trouver une forme plus simple pour les formules qui suivent. Entre parenthèses est précisée la règle d'équivalence utilisée pour la nouvelle formule. La règle de commutativité, qui intervient souvent, est généralement non spécifiée.

Algorithme de Quine

Étudiez la validité et la consistance de la formule suivante :

F = (P ∧ Q → ￢R) ∧ ￢P ∧ R → ￢Q 

Cet algorithme permet de construire l'arbre sémantique partiel représenté sur la figure A.1. L'explication de la construction est la même que celle de la table de vérité partielle vue dans le TD 1.3.5Travaux dirigés (validité, consistance, formules équivalentes) pour cette même formule. La valeur (1) correspond à l'interprétation partielle {Q = F}. La formule F est donc vraie pour toutes les interprétations où Q est faux…

Algorithme de réduction

En utilisant l'algorithme de réduction, étudiez la validité de la formule suivante :

F = (A → B) ∧ (B → C) → (A → C)

On va suppose qu'il existe une assignation de A, B et C qui rend cette formule fausse.

On en déduit alors :

1. (A → B)∧(B → C) est assigné à T et A → C est assigné à F (seule interprétation qui peut rendre la formule fausse) ;
2. A → C assigné à F implique A = T et C = F ;
3. (A → B) ∧ (B → C) assigné à T implique A → B assigné à T et B → C assigné à T ;
4. A → B assigné à T implique A = F ou B = T, or, d'après (2), A = T, donc on ne peut avoir que B = T ;
5. B → C assigné à T implique B = F ou C = T, or B = F est en contradiction avec (4) et C = T est en contradiction avec (2), donc la formule est valide.

Formes conjonctives normales

Les formules suivantes sont-elles en forme conjonctive normale ? Combien contiennent-elles de clauses ?

Normalisation

Forme normale conjonctive des formules :

1. p ∧ q → p ∨ q,
   f.n.c. : ￢p ∨ ￢q ∨ p ∨ q ;
   f.n.c.p. sous d'ensemble de clauses : {} ;
2. p ∨ q → p ∧ q ,
   f.n.c. : (￢p ∨ q) ∧ (￢q ∨ p) ;
   f.n.c.p. sous d'ensemble de clauses : {￢p ∨ q , ￢q ∨ p} ;
3. p ↔ (p → r),
   f.n.c. : (￢p ∨ r) ∧ p ;
   f.n.c.p. sous d'ensemble de clauses : {￢p ∨ r} ;
4. p ↔ (q → r),
   f.n.c. : (￢p ∨ ￢q ∨ r) ∧ (q ∨ p) ∧ (￢r ∨ p) ;
   f.n.c.p. sous d'ensemble de clauses : {￢p ∨ ￢q ∨ r , q ∨ p , ￢r ∨ p} ;

Principe de résolution

Voici le raisonnement que nous suivrons pour chacun des énoncés :

• F est valide ;
• ssi ￢F est inconsistant ;
• ssi l'ensemble de clauses correspondant à la forme conjonctive normale de ￢F est insatisfiable ;
• ssi on peut déduire Ø de cet ensemble de clauses.

1. F ≡ (A → B) ∧ A → B
   ￢F ≡ (A → B) ∧ A ∧ ￢B
   
   (a) Résolvante entre (3) et (1) : R₄ = ￢A.
   (b) Résolvante entre R₄ et (2) : R₅ = Ø.
   F est valide.
2. F ≡ (A → B) ∧ ￢B → ￢A
   ￢F ≡ (A → B) ∧ ￢B ∧ A
   
   Même résolution que pour la formule 1. ci-dessus.
3. F ≡ (A → B) ∧ (B → C) → (A → C)
   Non corrigé.
4. (A → M ∨ S) ∧ (M → S) → (￢S → ￢A)
   Non corrigé.

Comparatif

Soit la formule suivante :

(p → q) ∧ ((q ∧ ￢r) → s) ∧ (￢t → (￢r ∧ ￢s)) → (p → t)

Table de vérité : la formule contient 5 variables propositionnelles différentes (p, q, r, s, et t), la table de vérité contiendra donc 2ⁿ = 32 lignes. Sa réalisation est relativement fastidieuse et le risque d'erreur sur une telle table n'est pas négligeable.
Non corrigé.

Table de vérité partielle Non corrigé.

Algorithme de Quine Non corrigé.

Principe de résolution Non corrigé.

Exercice complet

Traduire l'énoncé suivant dans le formalisme de la logique des propositions, puis étudier sa validité au moyen de l'algorithme de Quine puis du principe de résolution :

• quand un bateau fait naufrage, cela fait parler les journalistes ;
• les sponsors sont inquiets quand les journalistes parlent et qu'un bateau fait naufrage ;
• un bateau fait naufrage ;

• donc les sponsors sont inquiets.

Traduction de l'énoncé Non corrigé.

Algorithme de Quine Non corrigé.

Algorithme de réduction Non corrigé.

Principe de résolution sur des clauses de Horn

Utiliser le principe de résolution appliqué à des clauses de Horn pour étudier la validité des énoncés suivants :

1. (A → B) ∧ A → B
2. (A → B) ∧ ￢B → ￢A
3. (A → B) ∧ (B → C) → (A → C)

Enquête logique

Trois personnes, Adrien, Béatrice et Christophe, accusées d'un meurtre, déclarent respectivement :

• Béatrice est coupable et Christophe est innocent (Adrien) ;
• si Adrien est coupable, alors Christophe l'est aussi (Béatrice) :
• je suis innocent, mais au moins l'une des deux personnes est coupable (Christophe).

Utiliser le formalisme du calcul des propositions pour traduire les questions suivantes et donner la réponse :

1. Les trois déclarations sont-elles compatibles ? (Non corrigé)
2. L'un des témoignages peut-il se déduire des autres ? Lequel ? (Non corrigé)
3. Si tous sont innocents, lequel a menti ? (Non corrigé)
4. Si tous disent la vérité, qui est coupable ? (Non corrigé)
5. Si seuls les innocents disent la vérité, qui est coupable ? (Non corrigé)