Vérité, modèles, conséquence · Logique pour l'informatique

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

Vérité, modèles, conséquence

Tables de vérité, modèles, classer une formule, et démontrer des propriétés de la conséquence. Chapitre 2.

Corrigé

$p \to q$ vaut 0 seulement pour $p = 1, q = 0$. Quand $p$ est fausse, l'implication n'affirme rien : elle n'est pas démentie, donc vraie.
Voir le chapitre 2.
Les deux membres ont la même colonne (1, 1, 0, 1 dans l'ordre 00, 01, 10, 11), donc la formule vaut 1 partout : elle est valide, et $p \to q \equiv \lnot q \to \lnot p$ (contraposée).

Corrigé

Un modèle de $A$ est une interprétation dans laquelle $A$ est vraie.
$(p \lor q) \land \lnot(p \land q)$ : exactement une des deux est vraie, donc deux modèles, $p = 1, q = 0$ et $p = 0, q = 1$. $(p \to q) \land (q \to r) \land p$ : $p = 1$ force $q = 1$, qui force $r = 1$. Un seul modèle : tout à 1.

Exercice · Satisfiable, insatisfiable ou valide ?

Pour chaque formule, dire si elle est valide, satisfiable sans être valide, ou insatisfiable. Justifier : un contre-modèle, un modèle, un calcul par équivalences ou une recherche de contre-modèle qui échoue.

$(p \land q) \lor (\lnot p \to q)$
$\lnot(\lnot p \to q) \lor r$
$(\lnot p \to q) \to (q \to (p \to q))$
$\lnot(p \to q) \land (\lnot q \to \lnot p)$
$p \leftrightarrow (p \land q) \lor (\lnot p \land q)$
$p \lor q \to (\lnot p \land q) \lor (p \land \lnot q) \lor (p \land q)$
$(q \lor (r \land \lnot q) \lor (\lnot r \land q)) \land (s \lor p \lor (\lnot s \land \lnot p))$
$(p \land s) \lor (q \land r) \to (p \lor q) \land (s \lor r)$
$(\lnot(p \land q) \to r) \to (\lnot(p \land q) \lor r)$
$p \land (q \to \lnot p) \land (q \lor r) \land \lnot r \to q$

Corrigé

$\lnot p \to q \equiv p \lor q$, et $(p \land q) \lor p \lor q \equiv p \lor q$ (absorption). Satisfiable, non valide : fausse pour $p = q = 0$.
$\equiv \lnot(p \lor q) \lor r \equiv (\lnot p \land \lnot q) \lor r$. Satisfiable, non valide : fausse pour $p = 1, r = 0$.
$q \to (p \to q)$ est valide : si $q = 1$, $p \to q$ vaut 1. Une implication dont le conséquent est valide est valide. Valide.
$\lnot(p \to q) \equiv p \land \lnot q$ et $\lnot q \to \lnot p \equiv p \to q$. On a $(p \land \lnot q) \land (p \to q)$ : $p = 1, q = 0$ rend $p \to q$ fausse. Insatisfiable.
$(p \land q) \lor (\lnot p \land q) \equiv q$ (distributivité puis tiers exclu), donc la formule est $\equiv p \leftrightarrow q$. Satisfiable, non valide.
Le conséquent énumère les trois lignes où $p \lor q$ est vraie : il est $\equiv p \lor q$. La formule est $\equiv p \lor q \to p \lor q$. Valide.
Première parenthèse : $q \lor (r \land \lnot q) \equiv q \lor r$, et $\lnot r \land q$ est absorbé par $q$ : $\equiv q \lor r$. Seconde : $(s \lor p) \lor \lnot(s \lor p) \equiv \top$. Formule $\equiv q \lor r$. Satisfiable, non valide.
Contre-modèle cherché : antécédent vrai, conséquent faux. Si $p \land s$ est vraie, $p \lor q$ et $s \lor r$ le sont ; si $q \land r$ est vraie, aussi. Échec. Valide.
$\lnot(p \land q) \to r \equiv (p \land q) \lor r$. Avec $p = q = 1, r = 0$ : antécédent vrai, conséquent $0 \lor 0$ faux. Et elle est vraie pour $r = 1$. Satisfiable, non valide.
Contre-modèle : il faudrait $q = 0$ et l'antécédent vrai, donc $p = 1$, $r = 0$ ; mais alors $q \lor r$ est fausse. Échec. Valide. (L'antécédent est même insatisfiable : $\lnot r$ et $q \lor r$ forcent $q$, et $q \to \lnot p$ contredit $p$.)

Corrigé

Une formule sans modèle : fausse dans toute interprétation.
$p \land \lnot p$ ; $\lnot(p \lor \lnot p)$ ; $(p \to q) \land p \land \lnot q$.
Si $A$ est satisfiable, $\lnot A$ n'est pas valide (elle est fausse dans un modèle de $A$) ; on ne peut rien dire de plus : $\lnot p$ est satisfiable, $\lnot(p \lor \lnot p)$ ne l'est pas. Si $A$ est valide, $\lnot A$ est insatisfiable.

Corrigé

Sens direct : soit $v$ un modèle de $\Sigma$. Si $v \vDash A$, $v$ est modèle de $\Sigma \cup \{A\}$, donc $v \vDash B$, et $A \to B$ est vraie. Sinon $A$ est fausse et $A \to B$ est vraie. Réciproque : soit $v$ un modèle de $\Sigma \cup \{A\}$ ; alors $v \vDash A \to B$ et $v \vDash A$, donc $v \vDash B$.
Soit $v$ un modèle de $\Sigma$ : $v \vDash A$ et $v \vDash A \to B$, donc $v \vDash B$ par la table de $\to$.
Le sens « $\Leftarrow$ » est vrai : si tout modèle de $\Sigma$ rend $A$ vraie, il rend $A \lor B$ vraie. Le sens « $\Rightarrow$ » est faux : avec $\Sigma = \emptyset$, $A = p$, $B = \lnot p$, on a $\vDash p \lor \lnot p$, mais ni $\vDash p$ ni $\vDash \lnot p$.

Corrigé

sat(P) = non valid(¬P). En effet $P$ est satisfiable si et seulement si $\lnot P$ n'est pas valide (chapitre 2).
valid(P) = non sat(¬P) : $P$ est valide si et seulement si $\lnot P$ est insatisfiable. Les deux problèmes sont donc aussi difficiles l'un que l'autre.