Version sans JavaScript, en lecture seule : les ateliers, les quiz et l’exécution du code n’y sont pas. Version complète · Catalogue · Se connecter

Feuille d'exercices 1

Lire et écrire des formules

Parenthèses, priorités, arbres de syntaxe, et la frontière entre formules et affirmations sur les formules. Chapitre 1.

Les conventions sont celles du chapitre 1 : $\lnot > \land > \lor > \to > \leftrightarrow$, et $\to$ associe à droite.

Corrigé
  1. $\lnot\lnot p \to q \lor r$
  2. $\lnot(\lnot p \to q \lor r)$. La négation porte sur toute l'implication : ses parenthèses restent.
  3. $p \land q \lor r \to p \to q$. Toutes les parenthèses tombent : comme $\to$ associe à droite, $\ldots \to p \to q$ se lit bien $\ldots \to (p \to q)$. Le piège est de croire qu'elles sont nécessaires ; l'arbre tranche.
  4. $(p \to q) \to r$. Ici les parenthèses sont obligatoires : $p \to q \to r$ se lirait $p \to (q \to r)$.
  5. $\lnot(p \land q) \leftrightarrow \lnot p \lor \lnot q$
Corrigé
  1. $(((p \to (q \lor r)) \land (q \to r)) \to (p \to r))$. Connecteur principal : le $\to$ du milieu.
  2. $((((\lnot p) \land q) \to r) \leftrightarrow ((\lnot r) \to ((\lnot q) \lor p)))$. Connecteur principal : $\leftrightarrow$, le moins prioritaire.
  3. $(p \to (q \to (r \to s)))$. Connecteur principal : le premier $\to$.
Corrigé
  1. Racine $\to$ ; à gauche $\lnot$ au-dessus de $\land(p, q)$ ; à droite $\lor$ au-dessus de $\lnot p$ et $\lnot q$.
  2. $A$, $\lnot(p \land q)$, $p \land q$, $\lnot p \lor \lnot q$, $\lnot p$, $\lnot q$, $p$, $q$ (les occurrences de $p$ et de $q$ donnent les mêmes sous-formules).
  3. Connecteurs : $\to, \lnot, \land, \lor, \lnot, \lnot$, soit 6, dont 3 binaires. Occurrences de variables : 4. Dans un arbre où chaque connecteur binaire a deux fils, il y a toujours une feuille de plus que de connecteurs binaires : $4 = 3 + 1$. Les $\lnot$ ne changent pas ce compte.
Corrigé
  1. Formule.
  2. Affirmation, vraie : tout modèle de $p$ rend $p \lor q$ vraie.
  3. Affirmation, fausse : le membre de droite est équivalent à $q$, et $p \not\equiv q$. La formule qu'on voulait sans doute écrire est $p \leftrightarrow (p \land q) \lor (\lnot p \land q)$ ; on peut demander si elle est valide.
  4. Affirmation, vraie : le membre de droite est équivalent à $p \lor q$.
  5. Ni l'un ni l'autre : aucune règle ne produit $p \land \lor q$.
  6. Affirmation, vraie : $p \to p$ est valide.
Corrigé
  1. $p \to q$
  2. $r \to p$ (« seulement si » : la condition nécessaire est à droite).
  3. $\lnot\lnot p \to q$, soit $p \to q$ : la même chose que la phrase 1.
  4. $\lnot p \land r$
  5. $\lnot r \land \lnot q$