9. Exercices et résultats

9. Exercices et résultats

9.1 Logique propositionnelle

Exercice 1 — tautologie. ¬p→(p→q) est vraie dans les quatre interprétations de p et q.

Exercice 2 — équivalence. La colonne de ¬(¬(p∨q)∨¬(p∨¬q)) coïncide avec celle de p.

Exercice 3 — déduction. À partir de p→q, q→r et r→¬p :

1. convertir en ¬p∨q, ¬q∨r, ¬r∨¬p;
2. résoudre les deux dernières clauses : ¬q∨¬p;
3. résoudre avec ¬p∨q : ¬p∨¬p;
4. appliquer l'idempotence : ¬p.

Exercice 4 — stationnement. Les réponses officielles traduisent les permissions au moyen de Congé, Personnel, Direction, Visiteur et Heure. Pour le second texte, « libre dans les zones blanche et jaune » demande normalement Congé→(Blanche∧Jaune), et non la disjonction donnée dans le corrigé.

9.2 Calcul des prédicats

Exercice 1 — français vers logique. Les catégories générales prennent la forme ∀x(Catégorie(x)→Propriété(x)); les propriétés conjointes d'une catégorie se placent ensemble dans l'antécédent, par exemple ∀x((champignon(x)∧violet(x))→vénéneux(x)).

Exercice 2 — logique vers français. ∀x((temps(nuit)∧chat(x))→couleur(x,gris)) se lit « la nuit, tous les chats sont gris ». La seconde formule contient ¬riche(x); sa lecture littérale est donc « tous les non-riches et intelligents sont heureux », même si le corrigé omet la négation.

Exercice 3 — Pierre ne travaille pas. La structure de preuve visée est : température supérieure à 38 ⇒ fièvre; fièvre et toux ⇒ grippe; grippe ⇒ ne pas travailler. Pour que cette preuve soit valide, la règle de température peut être écrite :

∀x∀t((temp(x,t)∧sup(t,38))→fievre(x))

ou :

∀x((∃t(temp(x,t)∧sup(t,38)))→fievre(x)).

La formule officielle ∀x∃t((temp(x,t)∧sup(t,38))→fievre(x)) est trop faible : le témoin peut rendre l'antécédent faux, donc elle ne justifie pas le modus ponens présenté.

Exercice 4 — unification. Résultats mathématiques :

1. P(x,y) avec P(F(v),s) : {x:=F(v), y:=s};
2. P1(P2(x,y),y) avec P1(v,v) : échec par contrôle d'occurrence;
3. PlusGrand(x,y) avec PlusPetit(y,x) : échec, symboles de prédicat différents;
4. A(C1,x) avec A(P(y),z) : échec si C1 est une constante et P(y) un terme composé;
5. A(x,x) avec A(P(y),z) : {x:=P(y), z:=P(y)}.

Le corrigé officiel donne une substitution à la question 4 et remplace P(y) par la notation f(y); cette réponse est structurellement incompatible avec l'énoncé affiché.