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 3

Formes normales

Mettre en FNC et en FND, par calcul et par table, et exprimer des contraintes avec trois connecteurs seulement. Chapitre 3.

Corrigé
  1. $\lnot(p \to q) \lor \lnot\lnot(r \lor s) \equiv (p \land \lnot q) \lor r \lor s$.
  2. $\lnot(\lnot p \lor \lnot q \lor \lnot r) \equiv p \land q \land r$.
Corrigé
  1. Distribution : $(p \lor \lnot p \lor q) \land (p \lor r)$. La première clause est une tautologie : FNC $p \lor r$.
  2. Distribution : $(\lnot p \lor p \lor \lnot q) \land (q \lor p \lor \lnot q)$. Les deux clauses sont des tautologies : la formule est valide, sa FNC est la conjonction vide, $\top$ (on peut écrire la clause $p \lor \lnot p$).
  3. $(p \land \lnot q) \lor p \lor q \equiv p \lor q$ (absorption de $p \land \lnot q$ par $p$). FNC $p \lor q$.
Corrigé
  1. $\lnot p \lor \lnot(q \land r) \lor s \equiv \lnot p \lor \lnot q \lor \lnot r \lor s$ : quatre monômes d'un littéral.
  2. $(\lnot p \land q) \land (\lnot s \lor t) \equiv (\lnot p \land q \land \lnot s) \lor (\lnot p \land q \land t)$.
  3. $(\lnot p \lor \lnot q) \land (p \lor q)$, puis distribution : $(\lnot p \land p) \lor (\lnot p \land q) \lor (\lnot q \land p) \lor (\lnot q \land q)$. Les monômes contradictoires tombent : $(\lnot p \land q) \lor (p \land \lnot q)$, le ou exclusif.
Corrigé
  1. Vraie pour 011, 101, 110, 111 (dans l'ordre $p, q, r$).
  2. FND : $(\lnot p \land q \land r) \lor (p \land \lnot q \land r) \lor (p \land q \land \lnot r) \lor (p \land q \land r)$. FNC par les lignes à 0 (000, 001, 010, 100) : $(p \lor q \lor r) \land (p \lor q \lor \lnot r) \land (p \lor \lnot q \lor r) \land (\lnot p \lor q \lor r)$.
  3. $(p \land q) \lor (p \land r) \lor (q \land r)$. La FNC se simplifie de même en $(p \lor q) \land (p \lor r) \land (q \lor r)$.
Corrigé
  1. $(p \land \lnot q) \lor (\lnot p \land q)$, en FNC $(p \lor q) \land (\lnot p \lor \lnot q)$.
  2. FND : $(A \land \lnot B \land \lnot C) \lor (\lnot A \land B \land \lnot C) \lor (\lnot A \land \lnot B \land C)$. FNC : $(A \lor B \lor C) \land (\lnot A \lor \lnot B) \land (\lnot A \lor \lnot C) \land (\lnot B \lor \lnot C)$.
  3. Une clause « au moins un » et une clause par paire, soit $1 + \frac{n(n-1)}{2}$.
Corrigé
  1. $\lnot p \equiv p \uparrow p$ ; $p \land q \equiv \lnot(p \uparrow q) \equiv (p \uparrow q) \uparrow (p \uparrow q)$ ; $p \lor q \equiv \lnot p \uparrow \lnot q \equiv (p \uparrow p) \uparrow (q \uparrow q)$.
  2. $\{\lnot, \land, \lor\}$ est complet (toute formule a une FND), et chacun de ses connecteurs s'écrit avec $\uparrow$.